数据结构期末复习知识点(兼容版).doc

数据结构期末复习复习要点：第一章1.相关基本概念：数据、数据元素（基本单位）、数据项（最小单位）、算法及其特征等；数据：所有能输入到计算机中并被计算机程序处理的符号总称。数据元素：基本单位。数据项：最小单位。算法特征（5点）：有穷性；确定性；可行性；输入；输出。2.逻辑结构、存储结构（物理结构）及其类型；逻辑结构有四种基本类型：集合、线性结构、树形结构和网状结构。数据元素之间的关系有两种不同的表示方法：顺序映象和非顺序映象，并由此得到两种不同的存储结构：顺序存储结构和链式存储结构。注：期中考题目数据结构分为两大类，即为逻辑结构和存储结构。其中逻辑结果又分为 线性结构和非线性结构 ，存储结构一共有四种（顺序、链接、索引、散列）。3.算法分析：语句频度（执行次数）计算、时间和空间复杂度分析。表示方法语句频度：直接写次数。时间复杂度：O(执行次数),如：O(n)。空间复杂度：O(所需空间)第二章 1.顺序表（数组）插入、删除、有序表合并算法及其移动次数计算；1213212428304277 数据元素 序号 1 2 3 4 5 6 7 8表示 L.elem0 1 2 3 4 5 6 7顺序表插入 算法思想：如果要在序号5前插入元素e，需要将序号58向后移动一个位置。 移动次数为4次，公式n-i+1 顺序表删除 算法思想：如果要删除序号5元素，需要将68依次向前移动一位移动次数为3次，公式n-i 有序表合并 LA = (3,5,8,11) LB = (2,6,8,9,11,15,20) 则LC = (2,3,5,6,8,8,9,11,11,15,20) 算法思想（以非递减为例）：La和Lb非递减排列，La与Lb中元素逐个比较，较小的先插入Lc中。 注：非递减是指递增排序，但元素有可能相等，与之相对的有非递增排序。 移动次数为（La.length + Lb.length） 2.链表（有无头节点、单双、循环）插入(前、后)、删除（前、本身、后）的指针挂接、建立（不带头节点）算法。单链表 每个节点有数据域和指针域 data next 头 a1 a2 a3 a4 a5 a6带头节点L P a1 a2 a3 a4 a5 a6 不带头节点L P单循环链表 在P（a3）节点前插入S节点 (1)Q = P; /先让Q指向a3(2)P = L; /P指向第一个节点（带头结点指向头结点，不带头结点指向a1）(3)while(P-next != Q) P = P-next; /找到a3的前驱a2，P指向a2(4)S-next = P-next; /P-next为a3，让S-next等于a3(5)P-next = S; /a2指针域指向节点S在P（a3）节点后插入S节点(1)S-next = P-next;(2)P-next = S;删除P（a3）前一个节点 (1)Q = P; (2)P = L; (3)while(P-next-next != Q) P = P-next; /找到a1 (4)P-next = P-next-next; /让a1指针域指向a3，从而删除a2删除P（a3）节点 (1)Q = P; (2)P = L; (3)while(P-next != Q) P = P-next; /找到a2 (4)P-next = P-next-next; /让a2指针域指向a4，从而删除a3删除P（a3）后一个节点 (1)P-next = P-next-next; /让a3指针域指向a5，从而删除a4双链表 每个节点有前驱指针、数据域、后继指针 prior data next 双循环链表 头 a1 a2 a3 a4 在P（a2）节点前插入S节点 技巧：先让S-prior 和S-next与链表建立关系 注：步骤(4)必须在步骤(3)后面 (1)S-next = P; /先让S-next指向a2 (2)S-prior = P-prior; /S-prior指向a1 (3)P-prior-next = S; /再把a1-next指向S (4)P-prior = S; / a2-prior指向S在P（a2）节点后插入S节点 注：步骤(4)必须在步骤(3)后面 (1)S-prior = P; (2)S-next = P-next; (3)P-next-prior = S; /a3-prior指向S (4)P-next = S;删除P（a2）前一个节点a1 (1)Q = P-prior; /Q指向要被删除的a1; (2)P-prior = P-prior-prior; /P-priro指向头 (3)P-prior-next = P; /头-next指向P (4)free(Q); /释放a1的存储空间删除P（a2）节点 (1)P-next-prior = p-prior; (2)P-prior-next = p-next; (3)free(P);删除P（a2）后一个节点a3 (1)Q = P-next; (2)P-next = P-next-next; /a2-next指向a4 (3)P-next-prior = P; /a4-prior = P (4)free(Q); /释放a3存储空间建立（不带头节点）单链表读程序：设n为2（i取0，1）i = 0时， pLqi = 1时， Lq p Lq p L qp第三章 1.栈的进出序列、栈、队列、循环队列的满/空条件; 由于栈的插入、删除操作是限制在栈顶进行的，因而后进栈的元素必然是先出栈，0.所以栈是“后进先出”表。由于队列的输入、输出操作分别在队的两端进行，因此先入队的元素必然先输出，故队列又称为“先进先出”表 栈的进出序列 例题：进栈序列为123，可能得到的出栈序列是什么？ 答：共五种123/132/213/231/321 进出栈情况（以132序列为例）：1进栈1出栈，输出12进栈3进栈3出栈2出栈 输出32栈、队列、循环队列的满/空条件 栈空条件：s.top = s.base;栈满条件：s.top - s.base = stacksize; 队空条件：Q.front=Q.rear; 队满条件：q-rear - q-front = MAXSIZE循环队列空条件：Q.front=Q.rear循环队列满条件：为避免在队满是队头指针和队尾指针也是重合的情况，规定队列中还有一个空的存储单元时为队满，即为Q.front=(Q.rear+1)MOD maxsize(MOD为取余运算符）。因而，这种循环队列不适合用动态数组作为存储结构。 2. 栈、队列的存储结构、基本操作算法（双向栈）; 栈存储结构顺序栈 typedef structSElemType *base;SElemType *top;int stacksize; SqStack;链式栈队列存储结构 顺序存储结构 链式存储结构 双向栈存储结构：typedef struct Elemtype *base2; Elemtype *top2; BDStacktype; /双向栈类型初始化：Status Init_Stack(BDStacktype &tws, int m)/初始化一个大小为m的双向栈tws tws.base0 = (Elemtype*)malloc(sizeof(Elemtype)*m); tws.base1 = tws.base0 + m; tws.top0 = tws.base0; tws.top1 = tws.base1; return OK; /Init_Stack入栈：Status push(BDStacktype &tws, int i, Elemtype x)/x入栈,i=0表示低端栈,i=1表示高端栈 if(tws.top0 tws.top1) return OVERFLOW; /注意此时的栈满条件 if (i = 0) *tws.top0+ = x; else if (i = 1) *tws.top1- = x; else return ERROR;return OK; /push出栈：Status pop(BDStacktype &tws, int i, Elemtype &x) /x出栈,i=0表示低端栈,i=1表示高端栈 if (i = 0) if (tws.top0 = tws.base0) return OVERFLOW; x = *-tws.top0; else if(i = 1) if(tws.top1 = tws.base1) return OVERFLOW; x = *+tws.top1; else return ERROR; return OK; /pop第四章 1.字符串模式匹配的简单算法；int Index(SString S, SString T, int pos) / 算法4.5 / 返回子串T在主串S中第pos个字符之后的位置。 / 若不存在，则函数值为0。 / 其中，T非空，1posStrLength(S)。 int i = pos; int j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index 2.计算NEXT。 j ：1 2 3 4 5 6 7串 ：a b c a b a anextj：0 1 1 1 2 3 2技巧：第一二个肯定是0，1！如果要计算next4，找的字符串必须是以第3个字符c为结尾，第1个字符a为开头的。以第6个为例，a前一个字母是b，以第5个字符b为结尾的ab刚好和以第1个字符为开头的ab匹配，所以next6 = 2+1 = 3。第五章 1.二维数组的地址（下标）换算；习题5.1假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，计算：（1）数组A的体积（即存储量）6*8*6 = 288字节（3）按行存储是，元素a14的第一个字节的地址 1000+(8*1+4)*6 = 1072 基址+(每行的元素个数*行数+当前列序)*每个元素所占存储单元（4）按列存储时，元素a47的第一个字节的地址 1000+(6*7+4)*6 = 6276 基址+(每列的元素个数*列数+当前行序)*每个元素所占存储单元习题5.2假设按低下标优先存储整数组A9*3*5*8时，第一个元素的字节地址是100，每个整数占四个字节。问下列元素的存储地址是什么？（2）a1111 地址：100+(3*5*8*1+5*8*1+8*1+1)*4 = 776（3）a3125 地址：100+(3*5*8*3+5*8*1+8*2+5)*4 = 1784（4）a8247 地址：100+(3*5*8*8+5*8*2+8*4+7)*4 = 4416 2.特殊矩阵（三角、其他有规律）压缩为一维的下标计算；下三角矩阵压缩为一维数组（记忆公式） 技巧：推荐把公式(2)背下来（i,j,R范围都是从0开始），其他根据范围变化公式 (1)若1=j,j=n, 0=R=j时，k = i(i-1)/2+j-1; 当ij时，k = j(j-1)/2+i-1.(2)若0=i,j=n-1, 0=R=j时，k = (i+1)i/2+j; 当jj时，k = (j+1)j/2+i.(3)若1=j,j=n, 1=R=j时，k = i(i-1)/2+j; 当ij时，k = j(j-1)/2+i;(4)若0=j,j=n-1, 1=R=j时，k = (i+1)i/2+j+1; 当i1，则其双亲是i/2。 (2)如果2in，则结点i无左孩子； 如果2in，则其左孩子是2i。 (3)如果2i+1n，则结点i无右孩子； 如果2i+1n，则其右孩子是2i+1。 2.二叉树的先序、中序、后序、层次遍历过程；树的先序、后序、层次遍历过程；二叉树遍历过程：先（根）序遍历：根左子树右子树中（根）序遍历：左子树根右子树后（根）序遍历：左子树右子树根层次遍历：从上到下，从左往右，逐个遍历树的遍历过程：先根（次序）遍历：先访问根结点，然后依次先根遍历根的每棵子树(根子树)后跟（次序）遍历：先依次后根遍历每棵子树，然后访问根结点（子树根）层次遍历：从上到下，从左往右，逐个遍历注：树与二叉树相互转化后树的先根遍历相当于二叉树的先序遍历树的后根遍历相当于二叉树的中序遍历 3.给出两个遍历序列，画出树（二叉树、树）习题6.23画出和下列已知序列对应的树T：(1)树的先根次序访问序列为GFKDAIEBCHJ;(2)树的后根次序访问序列为DIAEKFCJHBG。注：树的后根遍历相当于二叉树的中序遍历G 由(1)知G为根； G为根，联系(2)知G无右子树； 观察(1)，F为G左子树；F 根据，观察(2)知DIAEK在F左边， CJHB在F右边；BK 观察(1)，K为F左子树； 根据，观察(2)知K无右子树； 观察(1)，D为K左子树；CD 根据，观察(2)知D无左子树； 观察(1)，A为D右子树； 观察(2)，IE分别为A左右子树；AH F的右子树自行观察判断。JEI 4.二叉树与树相互转换；树转化成二叉树： 规则：树的最左孩子变成二叉树左子树，该左孩子的兄弟变成二叉树左子树的右子树 注：原树中B为A最左孩子，C,D为B兄弟，变成二叉树后C成为B右子树，D成为C右子树。 二叉树转化成树 5.求哈夫曼树和给出编码、带权路径长度计算。习题6.26假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.21, 0.10。试为这8个字母设计哈夫曼编码，并求带权路径长度设这8个结点为A、B、C、D、E、F、G、H，其相应的权为7、19、2、6、32、3、21、10。当前未用权：7、19、2、6、32、3、21、10，选出2、3构造出5。当前未用权：7、19、6、32、21、10、5，选出5、6构造出11。当前未用权：7、19、32、21、10、11，选出7、10构造出17。当前未用权：19、32、21、11、17，选出11、17构造出28。当前未用权：19、32、21、28，选出19、21构造出40。当前未用权：32、28、40，选出32、28构造出60。剩下权：40、60，构造出100 编码：树的左分支为0，右分支为1。得到哈夫曼编码为A:1101 B:01 C:11111 D:1110 E:10 F:11110 G:00 H:1100带权路径长度：(7*4+19*2+2*5+6*4+32*2+3*5+21*2+10*4)/100 = 2.61注：该公式为：A路径长*A权+B路径长*B权+H路径长*H权，因为设的权值是原来的100倍，所以结果除以100。第七章 1.邻接矩阵、邻接表存储结构及其特征；注：以有向图G1为例(有路径用1，否则0)v1 v2 v3 v4v1 0 1 1 0 v2 0 0 0 0v3 0 0 0 1v4 1 0 0 0 注：以有向图G1为例标号 0 1 2 3 0 0 1 1 0 1 0 0 0 0 2 0 0 0 1 3 1 0 0 0第0行值为1的是1、2，所以有V121。第1行值全为0，所以有V2。第2行值为1的是3，所以有V33。第3行值为1的是0，所以有V40。 2.求最小生成树（Prim、Kruskal）； 普里姆（Prim）： 以点为基础从V1开始，找到最小边(V1,V3)；寻找与V1、V3相关联的最小边，找到(V3,V6)；寻找与V1、V3、V6相关联的最小边，找到(V6，V4)；寻找与V1、V3、V6、V4相关联的最小边，此时有(V4,V1)和(V3,V2)，因为(V4,V1)与原来的边构成圈，所以选择(V3,V2)。（如果(V4,V1)不与原来的边构成圈，则二条边任选一条）；寻找与V1、V3、V6、V4、V2相关联，并且不与原来边构成圈的最小边，找到(V2,V5)；克鲁斯卡尔(Kruskal)（避圈法）：以边为基础 方法介绍：依次寻找权最小边，避免生成一个圈，所有点联通时生成最小树。 3.拓扑排序；步骤：（1）在有向图中选一个没有前驱的顶点且输出之。 （2）从图中删除该顶点和所有以它为尾的弧。输出： V6 V1 V4 V2 V5注：拓扑排序不唯一。4.求最短路径过程（Dijkstra、Floyd）。迪杰斯特拉(Dijkstra) 习题7.11试利用Dijkstra算法求题7.11图中从顶点a到其他各顶点间的最短路径，写出执行算法过程中各步状态。求解过程：K=1时，找a能直接到达的点，有b,c,d，(a,c)权最小，(a,c)为a到c最短路径，将c放如终点集S；K=2时，找a能直接到达的点，或通过(a,c)能到达的点，(a,c,f)权最小，(a,c,f)为a到f的最短路径，将f放入终点集S；K=3时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，(a,c,e)权最小，(a,c,e)为a到e最短路径，将e放入终点集S；K=4时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，(a,c,f,d)为a到d最短路径，将d放入终点集S；K=5时，找a能直接到达的点，或通过(a,c)能到达的点，或通过(a,c,f)能到达的点，或通过(a,c,e)能到达的点，或通过(a,c,f,d)能到达的点，(a,c,f,d,g)权最小，为a到g最短路径，将g放入终点集S；K=6时，只剩下(a,b)，(a,b)为a到b最短路径，将b放入终点集S。弗洛伊德(Floyd) 注：D(1)ij是从Vi到Vj的中间顶点的序号不大于1的最短路径的长度；D(k) ij是从Vi到Vj的中间顶点的序号不大于k的最短路径的长度；D(n-1) ij就是从Vi到Vj的最短路径的长度。D(-1)栏中，ViVj不允许有转折点。直接填邻接矩阵。D(0)栏中，ViVj只允许通过V0转折，或者不转折。通过V0转折权值小于原权值，就把原权值替换掉。D(1)栏中，ViVj只允许通过V0、V1转折，或者不转折。如果转折后权值小于原权值，替换。D(2)栏中，VjVj允许通过V0、V1、V2转折，或者不转折，如果转折后权值小于原权值，替换。此时p(2)中就是各点间的最短路径。第九章 1.以下所有查找成功平均查找长度2.顺序查找；折半查找；顺序查找：从表中最后一个记录开始，逐个进行比较。平均查找长度 等概率时，平均查找长度ASL = (n+1)/2 不等概率时，ASL = nP1 + (n-1)P2 + + 2Pn-1 + Pn折半查找：指针low和high分别指示待查元素所在范围的下界和上界，mid=(low+high)/2，如果要找的值大于Smid，则让mid = (mid+1 + high)/2，继续比较；如果要找的值小于Smid，则让mid = (low + mid-1)/2，继续比较。平均查找长度 等概率条件下，ASL= n+1nlog2(n+1)-1当n50时，有近似结果ASL=log2(n+1)-13.二叉排序树的插入（建立）、删除、平衡过程；二叉排序树建立 (1)若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； (2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； (3)它的左、右子树也分别为二叉排序树。注：中序遍历二叉 排序树，得到从小到大序列根据字母的先后确定大小插入Jan；F小于J，Feb成为Jan左子树；M大于J，Mar成为Jan右子树；Apr小于Jan，且Apr小于Feb，Apr成为Feb左子树；May大于Jan，且May大于Mar，May成为Mar右子树；June大于Jan，且June小于Mar，June成为Mar左子树。剩下的略。二叉排序树删除（） 3种情况：(1)*p为叶子节点，直接删除。(2) *p只有一个孩子*child只需将*child和*p的双亲直接连接后，即可删去*p。(3)*p有两个孩子用*p的直接前驱或直接后继代替*p，然后删除它的直接前驱或直接后继。平衡二叉树：树上任何节点的左右子树深度差都不超过1 插入节点P后不平衡，找到离P最近的不平衡点，根据二叉排序树的建立进行调整。 序列：Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec(1) 插入Aug时，Feb左右子树深度差超过1不平衡(2) 插入Oct时，最近不平衡点为May。因为SepOctMay，所以Oct作为双亲(3) 插入Nov时，Jan不平衡。把Jan左转，Mar的左子树变成Jan右子树。最终平衡树4.哈希表构造、冲突解决方法；除留余数法、线性探测或链地址法。构造：除留余数法：H(key) = key MOD p, p=m 冲突解决：线性探测法：Hi = (H(key)+ di) Mod m i = 1, 2, , k(k = m-1)链地址法：将所有关键字为同义词的记录存储在同一线性链表中。例题：已知一个线性表（38，25，74，63，52，48），假定采用散列函数h(key)=key%7计算散列地址，并散列存储在散列表A0.6中，采用线性探测方法解决冲突。38：38%7 = 3，查找次数为1。25：25%7 = 4，查找次数为1。74：74%7 = 4，与25冲突，(4+1)%7 = 5，查找次数为2。63：63%7 = 0，查找次数为1.52：52%7 = 3，与38冲突，(3+1)%7 = 4，与25冲突，(4+1)%7 = 5，与74冲突，(5+1)%7 = 6，查找次数为4。48：48%7=6，与52冲突， (6+1)%7 = 0，与63冲突， (0+1)%7 = 1，查找次数为3地址： 0 1 2 3 4 5 6633825745248次数： 1 3 1 1 2 4 等概率成功查找的平均查找长度为： (1+3+1+1+2+4)/6 = 2第十章1.简单排序（直接插入、选择、冒泡）的过程；直接插入（略）选择排序基本思想：依次在序列中选出最小的记录Rk，将它与第1个记录R1交换。模式：for (i = 0; i 10; i+)for (j = i; j 10; j+);冒泡排序： 基本思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。 模式：for(i = 0; i n; i+)for(j = 0; j n-i-1; j+);2.先进排序（希尔、快速、堆、归并、基数）过程；希尔排序：基本思想：先取一个小于n的整数d1作为第一个增量，所有距离为dl的倍数的记录放在同一个组中，先在各组内进行直接插人排序；然后，取第二个增量d2d1重复上述的分组和排序，直至所取的增量di=1。快速排序：基本思想：选第一个记录为支点，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录关键字比支点小，另一个部分记录的关键字比支点大。再可分别找两个支点，对这两部分记录继续进行快速排序。堆排序：n个关键字序列Kl，K2，Kn称为堆，必须所有根大于（或小于）其子树。例题：无序序列49, 38, 65, 97, 76, 13, 27, 49，进行堆排序思路：将次序列写出完全二叉树形式，然后从最有一个非终端结点开始筛选。归并排序：基数排序： 先将个位数值与fi中的i值相等的放入相应位置 将十位数值与fi中的i值相等的放入相应位置 将百位数值与fi中的i值相等的放入相应位置3.各种排序的特点、稳定性、时间复杂度（包括平均、最好、最坏）。希尔排序 O(nlogn) O(n2)排序方法稳定性插入排序稳定选择排序不稳定冒泡排序稳定希尔排序不稳定快速排序不稳定堆排序不稳定归并排序稳定基数排序稳定数据结构复习数据结构：带有结构和操作的数据元素集合 结构：数据元素之间的关系；操作：对数据的加工处理 ； 数据结构研究的问题：非数值数据之间的结构关系，及如何表示，如何存储，如何处理。（字符 字符串 文字 图形 图象 声音）v 对每种数据结构，主要讨论如下三方面的问题：v 数据的逻辑结构；逻辑结构 它属于用户的视图，是 面向问题的 数据结构从逻辑上分为四类：集合：“属于同一个集合”；线性结构：一对一的线性关系；树结构：一对多的层次关系；图结构：多对多的任意关系。v 数据的存储结构；数据的存储结构是逻辑结构的物理存储方式，属于具体 实现的视图 ，是 面向计算机 的 通常有两种存储结构：1. 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。2. 链接存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针来表示。 一种数据的逻辑结构可以用多种存储结构来存储 数据结构的抽象层次 线性结构 直接存取类 数组 , 文件 顺序存取类 表, 栈, 队列 , 优先队列 广义索引类 线性索引 , 搜索树非线性结构 层次结构类 树，二叉树，堆 群结构类 集合，图v 3）数据的运算，即对数据施加的操作 算法分析:时间复杂度 算法的概念:算法是求解问题的操作序列（或操作步骤）。 时间复杂度T（n）:以求解问题的基本操作（原操作）的执行次数作为算法时间的度量for (i=1; i=n; i+)for (j=1; j=n; j+)x+;单条语句O（1）一条循环O（n）两条循环O(n2).1、 线性表线性表的逻辑结构：在线性表中，除第一个元素和最后一个元素外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继。 顺序表存储特点：1）元素存储在一组连续的内存单元中2）通过元素的存储顺序反映线性表中数据元素之间的逻辑顺序；顺序表操作特点：1）可随机存取顺序表的元素；2）顺序表的插入删除操作要通过移动元素实现线性链表存储特点：1）用任意一组的存储单元存储线性表中的数据元素；2） 通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；线性链表操作特点1）不能随机存取元素； 2）插入、删除操作通过修改结点的指针实现；顺序表的插入平均要移动表的一半元素 n/2、删除操作平均要移动(n-1)/2顺序表能随机存取元素的原因是：顺序表能通过L.elemi-1或L.elem+(i-1)直接定位元素的存储地址。线性链表不能随机存取元素的原因是： 需从线性链表的头指针开始，顺着链指针定位元素的存储地址对于经常要存取元素的应用，线性表应采用顺序存储结构10 对于经常要插入删除元素的应用，线性表应采用链式存储结构2、 栈和队列栈：栈是限定仅能在表尾一端进行插入、删除操作的线性表；后进先出2 表尾称为栈顶，表头称为栈底；3 栈的满空判断4 栈顶元素的位置由一个栈顶指针指示；5 进栈、出栈操作要修改栈顶指针；6 一个栈的输入序列为a,b,c，则所有可能的出栈序列为： abc,acb,bac,bca,cba7栈的顺序存储结构 1） 用一组连续的内存单元依次存放自栈底到栈顶的数据元素； 2） 栈顶元素的位置由栈顶指针指示；8 栈的链式存储和实现 栈的链式存储与线性表的链式存储类似，可用带头结点的线性链表存储。注意：栈顶指针就是带头结点的线性链表的头指针队列：队列是限定仅能在表尾一端插入，表头一端删除操作的线性表；先进先出2 表尾称为队头，表头称为队尾 3 队头、队尾元素的位置分别由队头指针和队尾指针指示；4 队列的满空判断5 入队操作要修改队尾指针，出队操作要修改队头指针；6 循环队列队列的顺序存贮结构3、 数和二叉树1 树的逻辑结构树：是一种一对多的结构关系或称为分枝结构关系，除了根之外，每个元素只有一个直接前趋；，但每个元素可以有零个或多个直接后继；2 树的基本术语：树的结点 孩子结点 双亲结点 兄弟结点 结点层（根为1） 树的高度（层数） 结点的度（结点子树的个数） 树的度（树中最大的结点度） 叶子结点（度为0的结点） 分枝结点（度不为0的结点） 森林（互不相交的树集合）3 二叉树的定义：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。4 二叉树的五种基本形态l 5 二叉树性质性质1 在二叉树的第i 层上最多有2(i-1)个结点性质2 深度为k的二叉树最多有 2k-1 个结点，最少有k个结点性质3 设二叉树叶子结点数为n0，度为2的结点数为n2，则n0 = n2 +1性质4 具有n个结点的完全二叉树的深度为log2(n+1) 性质5 在完全二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；4) 结点所在层次为log2i+15) 若i为奇数，且i！=1，它处于右兄弟位置，则它的左兄弟为结点i-16) 若i为偶数，且i！=n，它处于左兄弟位置，则它的右兄弟为结点i+16 两种特殊的二叉树:满二叉树/完全二叉树7 二叉树的顺序结构8 二叉树的链式结构：二叉链表 二叉链表中每个结点至少包含三个域：数据域、左指针域、右指针域 9 遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。先序遍历、中序遍历、后序遍历10 遍历的递归算法、遍历的非递归算法递归：若二叉树为空，结束 基本项（也叫终止项）若二叉树非空 递归项 （1）访问根结点； （2）先序遍历左子树 （3）先序遍历右子树；11 线索二叉树：加上结点前趋后继信息（线索）的二叉树称为线索二叉树l 12 树与二叉树的转换树二叉树根根结点X的第一个孩子 结点X的左孩子结点X紧邻的右兄弟 结点X的右孩子l 13 哈夫曼树结点的带权路径长度：从根到该结点的路径长度与该结点权的乘积。带权路径长度最小的二叉树称为哈夫曼树l 14 哈夫曼编码左0右14、 图1 生成树：若T是G的生成树当且仅当T满足如下条件 T是G的连通子图，在该子图中删除任何一条边，子图不再连通 T包含G的所有顶点 T中无回路2 数组表示法（邻接矩阵）是图的一种顺序存储结构，邻接表（逆邻接表）是图的链式存储结构3 无向图数组（邻接矩阵）表示法特点：1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2）顶点v的度：等于二维数组对应行（或列）中1的个数；3）判断两顶点v、u是否为邻接点：只需判二维数组对应分量是否为1；4）顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值1或清0；5）设存储顶点的一维数组大小为m(m图的顶点数n), G占用存储空间：m+m2；G占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；对有向图的数组表示法可做类似的讨论4 有两种遍历方法（它们对无向图，有向图都适用）： 深度优先遍历 广度优先遍历5 拓扑排序：1）在有向图选一无前趋的顶点v，输出；2）从有向图中删除v及以v为尾的孤；3）重复1、2、直接全部输出全部顶点或有向图中不存在无前趋顶l 6 最小生成树l