单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,,,*,计算机二级考试公共基础之,《,数据结构与算法,》,1,．,4,算法与算法分析,算法与算法分析,一 算法的概念,,算法是对特定问题求解步骤的一种描述,,算法的基本特征：,,1,）,可行性,：组成算法的操作必须能够在计算机上实现2,）,确定性,：算法的每一步操作必须清晰无二义性3,）,有穷性,：算法必须在有限步内结束；,4,）,有足够的情报,：,0,个或多个输入；,1,个或多个输出；,算法描述的方法很多，如自然语言、框图、类,C,等,,例,:,求两个正整数,m,，,n,中的最大数,MAX,的算法,（,1,）,若,m > n,则,max=m,（,2,）,若,m <= n,则,max=n,,程序,=,算法,+,数据结构,,1,、,正确性,：,(1),没有语法错误； ,(2),对于几组输入数据能够得出满足要求的结果；,(3),对于精心选择的典型而苛刻的几组输入数据能够得到满足要求的结果4),对于一切合法的输入数据都能产生满足要求的结果。
2,、,可读性：,便于阅读、理解、调试、修改；,3,、,健壮性：,对不合法的输入能作出正确的反映与处理；,4,、,高效性：,执行时间短（,时间复杂度,）、,需求存储空间省（,空间复杂度,）,评价算法标准,,1,时间复杂度,T,（,n,）,以求解问题的基本操作的,执行次数,作为算法时间的度量算法与算法分析,O,（,n,3,）,,称为矩阵相乘算法时间复杂度；,O,（,n,3,）表示矩阵相乘算法执行时间与,n,3,成正比,,,即,O,（,n,3,）与,n,3,同一数量级；,,例：,n,阶矩阵相乘的算法,For ( i = 1; i<=n; i++ ) For (j = 1; j<=n; j++ ),{ c[ i ][ j ] = 0 ; For (k = 1; k<= n; k++ ) c[ i ][ j ] += a[ i ][ k ] * b[ k ] [ j ],},,乘法 加法,执行次数均为,n,3,,,矩阵相乘的基本运算：乘法 加法；,,数据结构中常用的时间复杂度频率计数有,7,个：,,O(1),常数型,O(n),线性型,O(n,2,),平方型,,O(n,3,),立方型,O(2,n,),指数型,,O(log,2,n),对数型,O(nlog,2,n),二维型,2,算法空间复杂度 用执行算法所需的,内存空间的大小,作为算法所需空间的度量。
设执行算法所需的内存空间是问题规模,n,的某个函数,g(n),,则算法空间复杂度记作：,S,（,n,）,= O(g(n)),表示算法内存空间的增长率,与,g(n),的增长率相同,例计算,,解法,1,先计算,x,的幂,,,存于,power[ ],中,,,再分别乘以相应的系数,,# define N 100,float evaluate (float coef[ ], float x , int n ),{ float power[N], f; int i;,for (power[ 0]=1, i = 1; i<=n; i++ ) power[i]=x*power[i-1]; for (f = 0, i=0; i<=N; i ++) f=f+coef[i]*power[i];,return(f);,},问题规模为,n,,算法时间复杂度,: O(n),空间复杂度：,O(N),(1),在计算机中，算法是指（ ）A.,查询方法,B.,加工方法,C.,解题方案的准确而完整的描述,D.,排序方法,(2),下列叙述中正确的是（ ）A),算法的效率只与问题的规模有关，而与数据的存储结构无关,B),算法的时间复杂度是指执行算法所需要的计算工作量,C),数据的逻辑结构与存储结构是一一对应的,D),算法的时间复杂度与空间复杂度一定相关,(3),算法的有穷性是指（ ）。
A,）算法程序的运行时间是有限的,B,）算法程序所处理的数据量是有限的,C,）算法程序的长度是有限的,D,）算法只能被有限的用户使用,(c),(B),算法习题,(A),(4),算法的时间复杂度是指,( ),,A),算法的执行时间,,B),算法所处理的数据量,,C),算法程序中的语句或指令条数,,D),算法在执行过程中所需要的基本运算次数,(5),算法的空间复杂度是指,( ),A,）算法在执行过程中所需要的计算机存储空间,B,）算法所处理的数据量,C,）算法程序中的语句或指令条数,D,）算法在执行过程中所需要的临时工作单元数,(6),下列叙述中正确的是,( ),,A,）一个算法的空间复杂度大，则其时间复杂度也必定大,,B,）一个算法的空间复杂度大，则其时间复杂度必定小,,C,）一个算法的时间复杂度大，则其空间复杂度必定小,,D,）上述三种说法都不对,(D),计算工作量,(A),(D),数据结构,大量的数据元素在计算机中如何组织，以便提高数据处理的效率，并且节省计算机的存储空间，这是进行数据处理的关键问题数据结构是指相互有关联的数据元素的集合，既按某种逻辑关系把一批数据组织起来，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义一个运算的集合。
归纳为三部分：,,逻辑结构、存储结构和运算集合,1.,逻辑结构,,数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构数据的逻辑结构包含：,（,1,）表示数据元素的信息；,（,2,）表示各数据元素之间的前后件关系例：,1.,一年四季的数据结构,,B=(D,R),D={,春，夏，秋，冬,},R={(,春，夏,) ,(,夏，秋,),(,秋，冬,)},2.,家庭成员的数据结构,,B=(D,R),D={,父亲，儿子，女儿,},R={(,父亲，儿子,) ,(,父亲，女儿,)},,春,夏,秋,冬,数据结构的图形表示,父亲,儿子,女儿,常见的,逻辑结构,有：,线性结构、树形结构和图形结构线性结构,树形结构,图形结构,① 线性结构,结构中的每个元素之间存在一个对一个的关系；,线性表、栈、队、字符串、数组,② 树形结构 （非线性）,结构中的每个元素之间存在一个对多个的关系；,③ 图形结构或网状结构（非线性）,结构中的每个元素之间存在多个对多个的关系2.,存储结构（物理结构）,计算机在实际进行数据处理时，被处理的各数据元素总是被存放在计算机的存储空间中，并且，各数据元素在计算机存储空间中的位置与它们的逻辑关系不一定是相同的，而且一般也不可能相同。
如：一年四季,家庭成员 计算机存储空间怎样存放？,存储结构指数据结构在计算机存储空间中的具体实现常见的存储结构有：,顺序存储结构 链式存储结构 索引存储结构,3.,数据的运算,检索,插入,删除,更新,排序,,通常，一个数据结构中的元素结点可能是动态变化的根据需要或在处理过程中，可以在一个数据结构中增加一个新结点（插入运算），也可以删除某个结点（删除运算），除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改数据结构是研究数据和数据之间关系的一门学科，研究以下三方面内容：,数据的逻辑结构,数据的存储结构,数据的运算,常见的数据结构,,,1.,线性表,,,2.,栈和队列,,,3.,树,１． 线性表（,Linear List,）,线性表是由,n,（,n≥0,）个数据元素,,a,1,，,a,2,，,…,，,a,i,，,…,，,a,n,组成的一个有限序列线性表是最简单、最常用的数据结构栈、队列、串,是特殊的线性表,数组和广义表,是线性表的扩展,--,线性结构,,,例、英文字母表（,A, B, C, D, E,,Z,） 某单位的电话号码簿线性表的概念,设,A=,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）是一线性表，,1,） 同一线性表中的元素必须是,同一类型,的；,2,） 在表中,a,i-1,,领先于,a,i,，,a,i,,领先于,a,i+1,,，称,a,i-1,,是,a,i,,的前件，,a,i+1,,是,a,i,,的后件；,3,） 在线性表中，除第一个元素和最后一个元素之外，其他元素都有且,仅有一个前件，有且仅有一个后件,；,4,） 线性表中元素的个数,n,称为线性表的长度，,n=0,时称为空表；,,用,一组连续的内存单元依次存放,线性表的数据元素。
a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,线性表（,a,1,,a,2,,a,3,,... a,n,,）,的顺序存储结构,用顺序存储结构存储的线性表,——,称为顺序表,线性表的顺序存储和实现,一 、 线性表的顺序存储结构,,线性表的顺序存储和实现,说明：,元素之间的逻辑关系，通过元素的存储顺序表示出来,.,设线性表中每个数据元素占,t,个存储单元，那么，在顺序存储结构中，线性表的第,i,个元素的存储位置与第,1,个元素的存储位置的关系是：,,,Loc(a,i,) = Loc( a,1,)+ ( i – 1),,t,其中,Loc( a,1,),基地址，随机存取,,a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,,t,个单元,Loc( a,1,),Loc(a,i,),线性表的顺序存储和实现,,插入位置 移动元素个数,1 n 2 n-1 i n-i+1 n 1 n+1 0,插入算法时间复杂度分析,算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与插入位置有关。
a,1,a,2,,a,i-1,a,i,a,i+1,,a,n,0,1,i-1,i-2,n-1,.,.,由此可见 在顺序表中插入一个元素 ，平均要移动表的一半元素 表长为,n,的顺序表，插入算法的时间复杂度为,O,（,n,）,假设在线性表的任何位置插入元素的概率相同，即,,pi= 1/(n+1),,设,p,i,为在第,i,个元素之前插入元素的概率，在长度为,n,的顺序表中插入一个元素，所需移动元素个数数学期望值为：,,删除算法时间复杂度分析,假设在线性表的任何位置删除元素的概率相同，即,,pi= 1/n,删除,所需移动元素个数的数学期望值：,,,线性表的顺序存储和实现,,顺序表是线性表最简单的一种存储结构,,,小结,顺序表的特点：,1,通过元素的存储顺序反映 线性表中,数据元素之间的逻辑关系；,2,可随机存取顺序表的元素；,3,顺序表的插入、删除操作要通过,移动,元素实现；,线性表的链式存储和实现,,线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素为了表示线性表中元素的先后关系，每个元素除需要存储自身的信息外，还要保存直接前趋元素或直接后继元素的存储位置a,i,+1,,a,1,,a,i-,1,,a,2,,a,i,,a,n,一 线性链表的概念,,1,线性链表,,a,4,,a,3,,a,1,a,2,,,,0,,1010,,,,1024,,,1014,1010,1012,1014,1016,1018,1020,1022,1024,1026,,用一组任意的存储单元存储线性表中的数据元素，对每个数据元素保存自身信息和直接后继元素的存储位置。
用链表存储线性表时，数据元素之间的关系是通过,保存直接后继元素的存储位置来表示的,,ai-1,,a,i,,a,2,,a1,,a,i+,1,n,,a,n,,结点：,数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；,结点的数据域 ：,保存数据元素,;,结点的指针域 ：,保存数据元素直接后继的存储地址,;,,线性链表有关术语,存储数据元素,存储后继结点,存储地址,,结点,数据域,指针域,头指针：,存放线性链表中第一个结点的存储地址,;,空指针：,不指向任何结点，线性链表最后一个结点的指针通常是空指针,;,头结点：,链表的第一个元素结点前的附加结点；,带头结点的线性链表,：第一个元素结点前增加一个附加结点的线性链表称为 带头结点的线性链表；,,head,是头指针,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,头结点,,空指针,head,线性链表的每个结点中只有一个指针域,故也称为,单链表,插入结点,(,存,a,),q=(LNODE *)malloc(sizeof(LNODE));,q->deta=‘a’;,q->next=p-> next;,p-> next =q;,head,,z,,y,,x,,p,,y,,x,,z,,p,head,,a,q,插入操作功能：在线性链表的第,i,个元素结点之前插入一个新元素结点,e,；,插入操作图示：,插入前,插入后,,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,head,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,,e,head,,4,）,删除结点,q=p->next;,p-> next =q-> next;,free(q);,head,,z,,y,,x,,q,,y,,x,,z,,q,head,p,p,删除前,删除后,,a,i-,1,,a,i,,a,2,,a,1,,a,i+,1,n,,a,n,,head,,a,i-,1,,ai,,a,2,,a,1,,a,i+,1,n,,a,n,,,head,p,p,q,q,线性链表小结,线性链表是线性表的一种链式存储结构,,线性链表的特点,,,1,通过保存直接后继元素的存储位置来表示,数据元素之间的逻辑关系；,,2,插入、删除操作通过修改结点的指针实现；,,3,不能随机存取元素,；,1,循环链表的概念,循环链表的特点是将线性链表的最后一个结点的指针指向链表的第一个结点（首尾相连的单链表）,2,循环链表图示,循环链表,(a),非空表 （,b,）空表,,head,,,,,,,head,a,1,a,n,循环链表,说明,,在解决某些实际问题时循环链表可能要比线性链表方便些。
如将一个链表链在另一个链表的后面；,对循环链表，有时不给出头指针，而是给出尾指针,,a,,,,a1,an,a->next,给出尾指针的循环链表,,,,双向链表,,循环单链表，虽然从任一结点出发沿着指针链能找到其前件，但时间耗费是,O(n),如果希望从表中快速确定某一个结点的前件，另一个解决方法是在链表的每个结点里再增加一个指向其前件的指针域,prior, 这样形成的链表中就有两条方向不同的链，称为双向链表线性表小结,,线性表的顺序存储结构,—,顺序表，,链式存储结构,----,线性链表,,,循环链表,,,双向链表,.,不同的存储结构，线性表的同一操作的算法是不同的,:,,在顺序存储结构下，线性表的插入、删除操作，通过移动元素实现,;,,在线性链表存储结构下，线性表的插入、删除操作，通过修改指针实现2,栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）,插入,删除,栈的概念,一 什么是栈,?,将表中允许进行插入、删除操作的一端称为,栈顶,(Top),，,栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。
表的另一端称为栈底,(Bottom),当栈中没有元素时称为空栈栈的插入操作称为,进栈或入栈,，删除操作称为,出栈或退栈,栈,,栈的示意图,出栈,进栈,栈的特点,后进先出,第一个进栈的元素在栈底， 最后一个进栈的元素在栈顶，,第一个出栈的元素为栈顶元素，,最后一个出栈的元素为栈底元素,,,栈顶,栈底,a,n,a,2,a,1,,,小 结,,,1,栈是限定仅能在表尾一端进行插入、,删除操作的线性表；,,2,栈的元素具有后进先出的特点；,,3,栈顶元素的位置由一个称为栈顶指针的,变量指示，,进栈、出栈操作要修改栈顶指针；,,,2,栈,3,队列,3.1,队列的概念,一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（,a,1,, a,2,, ... , a,i -1,, a,i,, a,i+1,, …, a,n,,）,插入,删除,3,队列,,a,1,a,2,a,3,,a,n,入队列,队头,队尾,出队列,队 列 的 示 意 图,队列的特点,先进先出,第一个入队的元素在队头， 最后一个入队的元素在队尾，,第一个出队的元素为队头元素，,最后一个出队的元素为队尾元素,,rear,front,J1,,rear,front,J2,（,a),空队列,(b)J1,J2,相继入队列,(c)J1,出队,(d)J3,J4, J5,和,J6,相继入队之后,,J2,出队,rear,front,,0,1,2,3,4,5,,rear,front,J5,J4,J3,front,rear,为整数,,,又有,J7,入队,,,怎么办？,,？,J2,J6,3 .,循环队列,,front,,rear,,,J6,J4,J5,3 1,2,4 0,5,rear,,,5,4 0,3 1,2,,,front,J6,J7,J8,J9,J4,J5,,front,,rear,,,5,4 0,3 1,2,,,,(b),队空,(a),队满,J7,,,rear,判分队空、队满方法：,1,）另设一个标志,S,以区分队空、队满。
2,）,S=0,队空：,front=rear;,S=1,队满：,front=rear;,或少用一个空间,Real+1=front,为满,,,front,,,5,4 0,3 1,2,J6,J7,J8,J4,J5,（,c,）,rear,,入队操作,,：,将元素,x,插入队尾,,,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,x,front,,,rear,,,5,4 0,3 1,2,J1,J3,J2,元素,x,入队前,元素,x,入队后,出队操作,,：删除队头,元素；,,,,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出队操作前,,front,,rear,,,5,4 0,3 1,2,J1,J3,J2,出队操作后,,,小 结,,1,队列是限定仅能在表尾一端进行插入，表头一端删除 操作的线性表；,,2,队列中的元素具有先进先出的特点；,,3,队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，,,4,入队操作要修改队尾指针，出队操作要修改队头指针；,,,数据存储结构方面的考题,,1,：数据的存储结构是指 （,,）。
A),存储在外存中的数据,B),数据所占的存储空间量,,C),数据在计算机中的顺序存储方式,D),数据的逻辑结构在计算机中的表示,2.,下列叙述中正确的是 （,,）A,）栈是“先进先出”的线性表,,B,）队列是“先进后出”的线性表,,C,）循环队列是非线性结构,,D,）有序线性表既可以采用顺序存储结构，也可以采用链式存储结构,3.,数据结构分为线性结构和非线性结构，带链的队列属于（ ）4.,下列数据结构中，属于非线性结构的是（ ）A,）循环队列,B),带链队列,C),二叉树,D,）带链栈,答案：,D,答案：,D,答案：线性结构答案：,c,5.,下列叙述中正确的是（ ）A,）顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的,,B,）顺序存储结构只针对线性结构，链式存储结构只针对非线性结构,,C,）顺序存储结构能存储有序表，链式存储结构不能存储有序表,,D,）链式存储结构比顺序存储结构节省存储空间,答案：,A,6.,下列关于栈的叙述正确的是,（,,）,,,A,）栈按“先进先出”组织数据,B),栈按“先进后出”组织数据,,C,）只能在栈底插入数据,D,）不能删除数据,,答案：,B,。
7.,一个队列的初始状态为空现将元素,A,，,B,，,C,，,D,，,E,，,F,，,5,，,4,，,3,，,2,，,1,依次入队，然后再依次退队，则元素退队的顺序为,【1】,答案：,A，B，C，D，E，F，5，4，3，2，1,9.,设某循环队列的容量为,50,，如果头指针,front=45(,指向队头元素的前一位置,),，尾指针,rear=10(,指向队尾元素,),，则该循环队列中共有,【2】,个元素8.,假设用一个长度为,50,的数组（数组元索的下标从,0,到,49,）作为栈的存储空间，栈底指针,bottom,指间栈底元素，栈顶指针,top,指向栈顶元素，如果,bottom=49,，,top=30,（数组下标），则栈中具有,【 】,个元素2009,年,3,月）,,答案：,19,答案：,15,4,树和二叉树,,1,．树的定义,,树是,n,个结点的有限集合,T,，当,n=0,时，称为空树；当,n>0,时，,T,满足如下条件：在任一棵非空树中： （,1,）有且仅有一个称为根的结点 （,2,）其余结点可分为,M,个互不相交的子集合，而且这些子集中的每一个本身又是一棵树，也称为根的子树J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,2,．树的实例 树可表示具有分枝结构关系的对象,,例,1,．家族族谱,设某家庭有,13,个成员,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,、,I,、,J,、,K,、,L,、,M,，他们之间的关系可用树表示：,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,计算机中树是常用的数据组织形式,尽管有些应用中数据元素之间并不存在分支结构关系，但为了便于管理和使用数据，将它们用树的形式来组织。
例,2,计算机的文件系统 不论是,DOS,文件系统还是,window,文件系统，所有的文件都是用树的形式来组织的文件夹,1,文件夹,n,文件,1,文件,2,文件夹,11,文件夹,12,文件,11,文件,12,C,盘,3,、树的 基本术语,,树的结点：包含一个数据元素及若干指,向子树的分支；,孩子结点：结点的子树的根称为该结点,的孩子，,B,、,C,是,A,的孩子；,双亲结点：,B,结点是,A,结点的孩子，则,A,,结点是,B,结点的双亲；,兄弟结点：同一双亲的孩子结点，,,H,、,I,、,J,互为兄弟；,堂兄结点,：,同一层上结点，,E,、,F,、,G,、,H,、,I,、,J,、,互为堂兄弟；,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,3,、树的 基本术语,结点的层次：根结点的层次定义为,1,；根的孩子为第二层，依此类推；,树的深度：,树中所有结点的层次的最大值,结点的度：,结点子树的个数,树的度：,树中结点度的最大值叶子结点,：度为,0,的结点；,分枝结点：,度不为,0,的结点；,,,J,,I,,A,,C,,B,,D,,H,,G,,F,,E,,K,,L,,M,,一 二叉树的概念,,1,二叉树的定义,二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。
A,,,F,,,G,,,E,,,D,,,C,,,B,一 二叉树的概念,二叉树,说明,1,）二叉树中每个结点最多有两个子树；,既：二叉树每个结点度小于等于,2;,2,）左、右子树不能颠倒,——,有序树,;,3,）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念,;,,,(a),、,(b),是不同的二叉树，,,(a),的左子树有四个结点,，,(b),的左子树有两个结点,(a),(b),,,,,G,,E,,,,D,,,C,,B,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,F,A,,2,． 二叉树的基本形态,,,,,,,,,,φ,(a),空树,(b),只有根,(c),右子树空,(e),左子树空,(d),左、右子树非空,,二、 二叉树的性质,,,性质,1:,在二叉树的第,i,层上至多有,2,i-1,个结点,(i≥1), ,,性质,2:,深度为,k,的二叉树至多有,2,k,-1,个结点（,k≥1,）性质,3:,,对任意一棵二叉树,T,，若叶结点数为,n,0,，而其度为,2,的结点数为,n,2,，则,n,0,=n,2,+1,,,,两种特殊的二叉树,满二叉树：深度为,k,的二叉树，如有,2,k,-1,个结点则称为满二叉树；,,,A,,,G,,,F,,,E,,,D,,,C,,,B,,,A,,,C,,,B,K=3,的满二叉树,K=2,的满二叉树,,满二叉树的顺序表示：,,从二叉树的根开始， 从上到下， 从左到右，逐层进行编号（,1,，,2,，,…,，,n,）。
例如图（,a,）所示的满二叉树的顺序表示为,:,(1,，,2,，,3,，,4,，,5,，,6,，,7,，,8,，,9,，,10,，,11,，,12,，,13,，,14,，,15),,,,完全二叉树：,,深度为,k,，结点数为,n,的二叉树，如果其结点,1~n,的位置序号分别与满二叉树的结点,1~n,的位置序号一一对应，则为完全二叉树， 如上图,(b),所示满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树性质,4,：具有,n,个结点的完全二叉树的深度为［,log,2,n,］,+1,性质,5:,,对于有,n,个结点的完全二叉树， 按照从上到下、从左到右的顺序对二叉树中的所有结点从,1,开始顺序编号， 则对于任意的序号为,i,的结点有：,,（,1,） 如,i=1,，则序号为,i,的结点是根结点， 无双亲结点； 如,i>1,， 则序号为,i,的结点的双亲结点序号为［,i/2,］,（下取整）,,（,2,） 如,2i>n,，则序号为,i,的结点无左孩子；如,2i≤n,，则序号为,i,的结点的左孩子结点的序号为,2i, ,（,3,） 如,2i,＋,1>n,，则序号为,i,的结点无右孩子；如,2i,＋,1≤n,， 则序号为,i,的结点的右孩子结点的序号为,2i,＋,1,。
二叉树,存储结构,---,二叉链表,二叉链表中每个结点包含三个域：数据域、左指针域、右指针域,,,A,,,F,,,E,,,D,,,C,,,B,,二叉链表图示,,∧,,D,,,,A,,B ∧,,C,,∧,,∧,E ∧,,∧,F ∧,,若一个二叉树含有,n,个结点，则它的二叉链表中必含有,2n,个指针域， 其中必有,n+1,个空的指针域,,,二、二叉树的遍历（必考）,遍历,：,按某种顺序访问二叉树的每个结点，而且每个结点仅被访问一次访问：,含义很广，可以是对结点的各种处理,，如修改结点数据、输出结点数据如何访问二叉树的每个结点，,而且每个结点仅被访问一次？,？,,二叉树的遍历方法（必考）,,二叉树由根、左子树、右子树三部分组成,二叉树的遍历,可以分解为：访问根，遍历,左子树,和,遍历,右子树,令,：,L,：,遍历左子树,,T,：,访问根结点,,R,：,遍历右子树,,约定先左后右,,,有三种遍历方法：,,T,L R,前序遍历、,,,L,T,R,中序遍历,、,,L R,T,后序遍历A,,,F,,,G,,,E,,,D,,,C,,,B,,,,,先序遍历,（,T,,L,R,）,,若二叉树非空 （,1,）访问根结点；,（,2,）先序遍历左子树； （,3,）先序遍历右子树,；,,先序遍历序列,：,A,,,B,D,,E,,G,,C,,,F,例：先,序遍历右图所示的二叉树,（,1,）访问根结点,A,,（,2,）先序遍历左子树：即按,,T,,L,R,的顺序遍历,左子树,（,3,）先序遍历右子树：即按,,T,,L,R,的顺序遍历,右子树,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,中序遍历（,L,T,,R,）,若二叉树非空 （,1,）中序遍历左子树 （,2,）访问根结点,（,3,）中序遍历右子树,,中序遍历序列,：,,D,B,G,,E,,,A,,,C,F,例：,中序遍历右图所示的二叉树,（,1,）中序遍历左子树：即按,,L,T,,R,的顺序遍历,左子树,,（,2,）访问根结点,A,,（,3,）中序遍历右子树：即按,,L,T,,R,的顺序遍历,右子树,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,后序遍历（,L,R,T,）,若二叉树非空 （,1,）后序遍历左子树 （,2,）后序遍历右子树,（,3,）访问根结点,,后序遍历序列：,,D,G,,E,,B,,F,C,,,A,例：后,序遍历右图所示的二叉树,（,1,）后序遍历左子树：即按,,L,R,T,,的顺序遍历,左子树,,（,2,）后序遍历右子树：即按,,L,R,T,,的顺序遍历,右子树,,（,3,）访问根结点,A,,,,A,,,F,,,G,,,E,,,D,,,C,,,B,,,,后序遍历序列,：,a,b,c,d,-,*,+,,e,f,/,,,-,中序遍历序列,：,a,+,b,*,c,-,d,,-,,,e,/,f,,例：,中序遍历、,后,序,遍历下图所示的二叉树,,,e,,,d,,,c,,,b,,,f,,,a,,,+,,,*,,,/,,,-,,,-,例,:,已知一棵二叉树前序遍历和中序遍历分别为,ABDEGCFH,和,DBGEACHF,，则该二叉树的后序遍历为,?,,A) GEDHFBCA B) DGEBHFCA C) ABCDEFGH D) ACBFEDHG,B,,二叉树,,1,二叉树： 或为空树，或由根及两颗互不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；,,2,二叉树可以用链式结构存储；,遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。
二叉树的遍历可以分解为：访问根，遍历,左子树和,遍历,右子树，常用的三种遍历算法：,先序遍历、中序遍历、后序遍历；,,5,查找,,5.1,查找的基本概念,,查找（列）表：由同一类型的数据元素（或记录）构成的集合， 可利用任意数据结构实现 ,关键字：,数据元素的某个（几个）数据项的值如果一个数据项可以,唯一标识列表中的一个数据元素,， 则称其为关键字查找： 根据给定的关键字值，在特定的查找（列）表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置若找到相应的数据元素， 称查找成功，否则称查找失败,,5,．,2,线性表的查找,5.2.1,顺序查找,---,最简单的查找方法,顺序查找的基本思想,,,从表的一端开始，顺序扫描线性表，,依次将扫描到的结点关键字和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元素，则查找失败顺序查找既适用于顺序表，也适用于链表若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描另外，顺序查找的表中元素可以是无序的,顺序查找算法的性能假设列表长度为,n,，那么查找第,i,个数据元素时需进行,n-i+1,次比较，即,C,i,=n-i+1,。
又假设查找每个数据元素的概率相等，即,P,i,=1/n,， 则顺序查找算法的平均查找长度为：,顺序查找的特点,,,,,,顺序查找的,优点是算法简单,，对查找表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序排，它都同样适用顺序查找的缺点是,查找效率低,，当,n,较大时，不宜采用顺序查找,二分,查找（折半查找）,1.,二分查找的基本思想,,,高效率的查找方法要求表中元素按关键字有序,(,升序或降序,),假设表中元素为升序排列二分查找的基本思想是：,首先将表,中间位置记录的关键字与查找关键字,比较，如果两者相等，则查找成功；,否则利用中间位置记录,将表分成前、后两个子表， 如果中间位置记录的关键字大于查找关键字，,则进一步查找前一子表，否则进一步查找后一子表重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功例如，假设给定有序表中关键字为：,{05,13,19,21,37,56,64,74,80,88,92},，查找,K=21,的情况：,,,,,0 1 2 3 4 5 6 7 8 9 10,,0 1 2 3 4 5 6 7 8 9 10,,,,0 1 2 3 4 5 6 7 8 9 10,,0 1 2 3 4 5 6 7 8 9 10,3.,二分查找的性能分析,二分查找的过程可以用二叉树来描述。
把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树例如，给定的关键字序列,05,13,19,21,37,56,64,74,80,88,92,，的判定树0 1 2 3 4 5 6 7 8 9 10,,,,在长度为,n,的有序线性表中进行二分查找最坏的情况下，需要的比较次数为,log,2,n,,,,6,排序,,6,．,1,基本概念,,6.1.1,排序定义,,排序就是把一组记录（元素）按照某个域的值的递增或递减的次序重新排列的过程按学号的递增,),表,7-1,学生档案表,,学号,,,姓名,,,年龄,,,性别,,,99001,,,王晓佳,,,18,,,男,,,99002,,,林一鹏,,,19,,,男,,,99003,,,谢宁,,,17,,,女,,,99004,,,张丽娟,,,18,,,女,,,99005,,,周涛,,,20,,,男,,,99006,,,李小燕,,,16,,,女,,,,为讨论方便，我们直接将排序码写成一个一维数组的形式，,并且在没有声明的情形下，所有排序都按排序码的值递增排列。
排序,,,插入排序（直插排序、希尔排序）,,,交换排序（冒泡排序、快速排序）,,,选择排序 （直选排序、堆排序）,,归并排序（二路归并排序）,,,,6,．,2,插入排序,,直接插入排序,1,．直接插入排序（,Straight Insertion Sorting,）,,基本思想：把,n,个待排序的元素看成一个有序表和一个无序表，,开始时有序表中只包含一个元素，无序表中包含有,n-1,个元素，,排序过程中每次从无序表中取出第一个元素，把它的排序码,依次与有序表元素的排序码进行比较，将它插入到有序表中,的适当位置，使之成为新的有序表例如，,n=6,，数组,R,的六个排序码分别为：,17,，,3,，,25,，,14,，,20,，,9,它的直接插入排序的执行过程如图,7-1,所示3,．直接插入排序的效率分析,直接插入排序算法十分简单空间,:,只需要一个元素的辅助空间，用于元素的位置交换,时间,:,外层循环要进行,n-1,次插入，每次插入最少比较一次（正序），移动两次；最多比较,i,次，移动,i,＋,2,次（逆序）（,i=1,，,2,，,…,，,n-1,）直接插入排序的时间复杂度为,O,（,n,2,）。
最坏情况比较,n(n-1)/2,,希尔排序,,希尔排序,(,缩小增量排序,):1959,年由提出来的基本思想：先将整个待排元素序列分割成若干个子序列（由 “增量”确定）分别进行直接插入排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的例如，,n=8,，数组,array[ ],的八个元素分别为：,91,，,67,，,35,，,62,，,29,，,72,，,46,，,57,下面用图,7-2,给出希尔排序算法的执行过程希尔排序的效率分析,与增量有关，,最坏情况，希尔排序的时间复杂性在,O,（,nlog,2,n,）6,．,3,交换排序,6.3.1,冒泡排序,基本思想,:,,对待排序序列从后向前（从下标较大的元素开始），依次比较相邻元素的排序码，若发现逆序则交换，使排序码较小的元素逐渐从后部移向前部，就象水底下的气泡一样逐渐向上冒例如，,n=6,，数组,R,的六个排序码分别为：,17,，,3,，,25,，,14,，,20,，,9,下面用图,7-3,给出冒泡排序算法的执行过程冒泡排序的效率分析,,若待排序的元素为正序，则只需进行一趟排序，比较次数为（,n-1,）次，移动元素次数为,0,；,若待排序的元素为逆序，则需进行,n-1,趟排序，比较次数为,(n,2,-n)/2,，移动次数为,3(n,2,-n )/2,，,最坏情况比较,n(n-1)/2,因此冒泡排序算法的时间复杂度为,O,（,n,2,）。
由于其中的元素移动较多，所以属于内排序中速度较慢的一种6.3.2,快速排序,基本思想是：取待排序序列中的某个元素（一般第一个元素）作为基准，通过一趟排序，将待排元素分为左右两个子序列，,左子序列元素的排序码均小于或等于基准元素的排序码，,右子序列的排序码则大于基准元素的排序码，,然后分别对两个子序列继续进行,快速,排序，直至整个序列有序元素的比较和交换是从两端向中间进行的，排序码较大的元素一次就能够交换到后面，排序码较小的记录一次就能够交换到前面，记录每次移动的距离较远，因而总的比较和移动次数较少例如，给定排序码为：（,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,），具体划分如图,7-4,所示3,．快速排序的效率分析,,若快速排序出现最好的情形（左、右子区间的长度大致相等），则结点数,n,与二叉树深度,h,应满足,log,2,n 因此，,快速排序的最坏时间复杂度为,O(n,2,),快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为,O,（,log,2,n,），最坏的空间复杂度为,O(n),快速排序是一种不稳定的排序方法6,．,4,选择排序,,6 . 4.1,直接选择排序,基本思想,直接选择排序是一种简单的排序方法基本思想是：第一次从,array[0]~array[n-1],中选取最小值，与,array[0],交换，第二次从,array[1]~array[n-1],中选取最小值，与,array[1],交换，第三次从,array[2]~array[n-1],中选取最小值，与,array[2],交换，,…,，第,i,次从,array[i-1]~array[n-1],中选取最小值，与,array[i-1],交换，,…,,第,n-1,次从,array[n-2]~array[n-1],中选取最小值，与,array[n-2],交换，总共通过,n-1,次，得到一个按排序码从小到大排列的有序序列,例如，给定,n=8,，数组,R,中的,8,个元素的排序码为：（,8,，,3,，,2,，,1,，,7,，,4,，,6,，,5,），则直接选择排序过程如图,7-5,所示。 直接选择排序的效率分析,,,在直接选择排序中，共需要进行,n-1,次选择和交换，每次选择需要进行,n-i,次比较（,1≤i≤n-1,），而每次交换最,多需,3,次移动，因此，总的比较次数,C= =(n,2,-n)/2,，,总的移动次数,M= =3(n-1),直接选择排序的时间复杂度为,O(n,2,),数量级，所以当记录占用的字节数较多时，通常比直接插入排序的执行速度要快一些,最坏情况比较,n(n-1)/2,,,,7,．,5,归并排序,,,1,、,基本思想：将两个有序子区间（有序表）合并成一个有序子区间，一次合并完成后，有序子区间的数目减少一半，而区间的长度增加一倍，当区间长度从,1,增加到,n,（元素个数）时，整个区间变为一个，即为有序序列,.,,例如，给定排序码,46,，,55,，,13,，,42,，,94,，,05,，,17,，,70,，二路归并排序过程如图,7-10,所示算法,P284,归并排序的效率分析,,归并排序的时间复杂度为,O(nlog,2,n),归并排序时，需要利用与待排序数组相同的辅助数组作临时单元，故该排序方法的空间复杂度为,O(n),，比前面介绍的其它排序方法占用的空间大。 对于长度为,n,的线性表，在最坏情况下，下列各排序法所对应的比较次数中正确的是,A),冒泡排序为,n/2,B),冒泡排序为,n,,C),快速排序为,n,D),快速排序为,n(n-1)/2,D,第二部分 程序设计,,程序设计基础,2.1,程序设计方法与风格,如何形成良好的程序设计风格，主要包含以下几个因素：,（,1,）源程序文档化2,）数据说明的方法3,）语句的结构4,）输入和输出5,）适当的注释,注,释分序言性注释和功能性注释2,程序设计基础,2.2,结构化程序设计,结构化程序设计方法的四条原则是,（必考）：,1.,自顶向下；,2.,逐步求精；,3.,模块化；,4.,限制使用,goto,语句结构化程序的基本结构和特点：,（,1,）顺序结构：一种简单的程序设计，最基本、最常用的结构；,（,2,）选择结构：又称分支结构，包括简单选择和多分支选择结构，可根据条件，判断应该选择哪一条分支来执行相应的语句序列；,（,3,）重复结构：又称循环结构，可根据给定条件，判断是否需要重复执行某一相同程序段2,程序设计基础,2.3,面向对象程序设计,1,、面向对象方法的,优点,：,（,1,）与人类习惯的思维方法一致。 （,2,）稳定性好3,）可重用性好 （,4,）易于开发大型软件产品5,）可维护性好2,、面向对象方法的基本概念,（,1,）对象,-,对象是面向对象方法中最基本的概念，可以用来表示客观世界中的任何实体，对象是实体的抽象属性即对象所包含的信息，操作描述了对象执行的功能，操作也称为方法或服务2,程序设计基础,（,2,）类和实例,——,类是指具有共同属性、共同方法的对象的集合所以类是对象的抽象，对象是对应类的一个实例3,）消息,——,消息是一个实例与另一个实例之间传递的信息消息的组成包括,1,、接收消息的对象的名称；,2,、消息标识符，也称消息名；,3,、零个或多个参数4,）继承,——,继承是指能够直接获得已有的性质和特征，而不必重复定义他们继承分单继承和多重继承单继承指一个类只允许有一个父类，多重继承指一个类允许有多个父类5,）多态性,——,多态性是指同样的操作在接受不同消息时可导致完全不同的行动的现象比如汽车一个类，而具体到某辆汽车则是一个对象图,21,中，机动车类是对机动车特征和功能的总体描述，机动车,A,是具体到某辆车的特征3,软件工程基础,3.1,软件工程基本概念,1,、软件定义及特点,2,、软件危机与软件工程,3,、软件工程过程和软件生命周期,软件生命周期三个阶段,:,软件定义、软件开发、运行维护，主要活动阶段是：,（,1,）可行性研究与计划制定；,（,2,）需求分析；,（,3,）软件设计；,（,4,）软件实现；,（,5,）软件测试；,（,6,）运行和维护。 3,软件工程基础,4,、软件工程的目标和与原则,目标：在给定成本、进度的前提下，开发出具有有效性、可靠性、可理解性、可维护性、可重用性、可适应性、可移植性、可追踪性和可互操作性且满足用户需求的产品基本目标：付出较低的开发成本；达到要求的软件功能；取得较好的软件性能；开发软件易于移植；需要较低的费用；能按时完成开发，及时交付使用软件工程的理论和技术性研究的内容主要包括：软件开发技术和软件工程管理软件开发技术包括：软件开发方法学、开发过程、开发工具和软件工程环境软件工程管理包括：软件管理学、软件工程经济学、软件心理学等内容软件管理学包括人员组织、进度安排、质量保证、配置管理、项目计划等软件工程原则包括抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可验证性3,软件工程基础,3.2,结构化分析方法,1,、需求分析,——,指用户对目标软件系统在功能、行为、性能、设计约束等方面的期望1,）结构化需求分析方法2,）面向对象的分析的方法（,OOA,）2,、结构化分析方法,结构化分析方法的实质：着眼于数据流，自顶向下，逐层分解，建立系统的处理流程，以数据流图和数据字典为主要工具，建立系统的逻辑模型。 步骤：,调查原系统（获得当前系统如何工作）,原系统逻辑模型,à,需求分析（得出新系统应如何工作）,新系统逻辑模型,结构化分析的常用工具：（,1,）数据流图、（,2,）数据字典（,D-D,）、（,3,）判定树、（,4,）判定表,,,,,,,3,软件工程基础,3,、软件需求规格说明书,作用：,（,1,）便于用户与开发人员进行交流2,）是软件开发工作的基础和依据3,）作为确认测试和验收的依据内容：,（,1,）概述 （,2,）数据描述,（,3,）功能描述 （,4,）性能描述5,）参考目录 （,6,）附录特点：,（,1,）正确性；（,2,）无岐义性；,（,3,）完整性；（,4,）可验证性；,（,5,）一致性；（,6,）可理解性；,（,7,）可追踪性3,软件工程基础,3.3,结构化设计方法,1,、软件设计基本概念,软件设计的基本目标：是用比较抽象概括的方式确定目标系统如何完成预定的任务，软件设计是确定系统的物理模型结构设计：定义软件系统各主要部件之间的关系数据设计：将分析时创建的模型转化为数据结构的定义接口设计：描述软件内部、软件和协作系统之间以及软件与人之间如何通信过程设计：把系统结构部件转换成软件的过程描述。 软件设计的基本原理：,（,1,）抽象2,）模块化3,）信息隐藏4,）模块独立性3,软件工程基础,衡量软件模块独立性使用,耦合性和内聚,性两个定性的度量标准内聚性指一个模块内容各部分之间的紧密程度内聚性越高越好耦合性指模块之间的相互依赖关系耦合性越低越好在程序结构中各模块的内聚性越强，则耦合性越弱优秀软件应高内聚，低耦合按内聚性由弱到强：偶然内聚、逻辑内聚、时间内聚、过程内聚、顺序内聚、功能内聚耦合性按由高到低：内容耦合、公共耦合、外部耦合、控制耦合、标记耦合、数据耦合、。
