数据结构复习指南

1、第一章绪论1、根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？各有什么特点？根据数据元素之间的逻辑关系，有4种基本结构1、集合特点：结构中的数据元素属于一个集合2、线性结构特点：一个对一个的关系3、树形结构：一个对多个的关系4、图状或网状结构：多个对多个的关系2、根据数据元素之间的关系在计算机中的表示方法，数据的存储结构有几种？各有什么特 点？1、顺序存储结构特点：用相对位置来表示数据元素之间的逻辑关系2、链式存储结构特点：用指示元素存储地址的指针表示具有非连续性3、算法的重要特性是什么？算法设计的要求是什么？特性：有穷性确定性 可行性输入输出设计要求：正确性可读性健壮性效率与地存储量

2、需求4、数据结构中评价算法的两个重要指标是什么？时间复杂度 空间复杂度第二章线性表1、理解并能简述线性表的两种存储结构的主要优缺点及各自适用的场合。顺序存储结构优点是可以实现随机读取，时间复杂度为0(1),空间利用率高;缺点是进行插入 和删除操作时比较麻烦，时间复杂度为0(n),同时容量受限制，需要事先确定容量大小,容量过 大浪费空间资源，过小不能满足使用要求，会产生溢出问题,虽然可以扩容，但是需要耗时间 的；链式存储结构优点,插入和删除非常简单，前提条件是知道操作位置，时间复杂度是0(1),但如 果不知道操作位置则要定位元素，时间复杂度也是0(n),还有一个很大的优点是没有容量的 限制，可以

3、在使用过程中动态的分配内存空间，不用担心溢出的问题;缺点是它不能实现随机 读取，同时空间利用率不高.这两个结构各有优缺点,不同的地方选择不同的结构.尽量利用其优点,避免其缺点.2、定义线性表顺序存储结构。线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性的数据元素。优点：随机存取表中元素。缺点：插入和删除操作需要移动元素。3、顺序表存储结构下初始化、取第i个数据元素、插入、删除、定位Locate.销毁操作的 实现。4、设顺序表La中的数据元素递增有序。请写出将x插入到顺序表的适当位置上以保持该 表有序的算法。5、定义线性链表存储结构线性链表的链式存储结构的特点是用一组任鲤存储单元存储线

4、性表的数据结构。对每个 数据元素，除了存储本身的信息之外，还需要存储一个指示其直接后继的信息。这两部分信 息组成数据元素的的存储影像，称为结点。它包括两个域：其中存储数据元素信息的域称为 数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点链结成一个链表，即为线性表的链式存储结构。6、单链表存储结构下初始化、取第i个数据元素、插入、删除、定位Locate、求长度、创 建单链表、销毁操作的实现。7、实现单链表就地逆置的算法。第三章栈和队列1、栈的特点是什么？后进先出2、栈的顺序存储结构定义：顺序存储下初始化、取栈顶、入栈、出栈操作的实现。顺序栈，即栈的顺序存储结构

5、是利用一组地址连续的存储单元依次存放自栈底到栈顶的 数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。3、栈的链式存储结构定义：链式存储下初始化、取栈顶、入栈、出栈操作的实现。 采用链式存储的栈称为链栈 头结点栈预结点 栈离结点 初始化栈mitStack()建立一个空栈So实际上是创建链栈的头结点，并将其next域置为NULLo对应算法 如下：LiStack * IiiitStack( void )LiStack * s;s=(LiStack *)malloc(sizeofi(LiStack);s-next=NULL;return s;进栈 Push(&s,e)将新数据结点插入到头结点

6、之后。对应算法如下：void Push(LiStack *s,ElemType e)(LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;p-next=s-next; /*插入*p结点作为第一个数据结点*/s-next=p;)出栈 Pop(&s,&e)在栈不为空的条件下，将头结点后继数据结点的数据域赋给e,然后将其删除。对应算 法如下：hit Pop(LiStack *s.ElemType *e)( LiStack *p;if (s-next=NULL) return 0; /* 栈空的情况 */p=s-next;/*p指向第一个数据

7、结点*/*e=p-data;s-next=p-next;丘 ee(p);return 1;取栈顶元素GetTop(s)在栈不为空的条件下，将头结点后继数据结点的数据域赋给e。对应算法如下：hit GetTop(LiStack *s,ElemType &e)LiStack *p;if (s-next=NULL) return 0;/* 栈空的情况 */p= s-next;e=p-data;return 1;)4、队列的特点是什么？先进先出front real5、循环队列存储结构定义：该存储结构下初始化、入队、出队、求队列中元素个数操作的 实现。收尾相连6、链队列存储结构定义；该存储结构下初始化、

8、入队、出队、求队列中元素个数操作的实 现。用链表表示的队列称为链队列。产链队列初始化”void QueueImtialize(LuikQueue *pQ) (pQ-rear=(QLHik)malloc(sizeof(QNode); if(!pQ-rear)exit(EXIT_FAILURE); pQ-rear-next=pQ-rear; pQ-len=0;)/*链队列入队列操作*/void EnQueue(LnikQueue *pQ, QueueDT d) (QLuik p;p=(QLiiik)malloc(sizeof(QNode);exit(EXIT_FAILURE);p-next=pQ-

9、rear-next;/llen+;/4 )/*链队列出队列操作*/BOOL DeQueue(LmkQueueBOOL flg=TRUE;p-data=d;pQ -rear-next=p ;/2pQ-iear=p;/3 pQ-*pQ, QueueDT *pd) ( QLuik p,front;flg=FALSE; elsefiont=pQ-rear-next;fiont-next=p-next;iear=fiont; fiee(p);return fig; 第六章树和二叉树1、二叉树的性质及其证明。性质1 ：在二叉树的第1层上至多有21-1性质2 :p=fiont-next;*pd=p-data

10、; if(pQ-reai=p) pQ-len;)pQ-if(QueueEmpty(*pQ)深度为k的二叉树上至多含2k-l个结点(kl)性质3 :对任何一棵二叉树，若它含有nO个叶子结点、n2个度为2的结点，则必存在关系式:nO = 112+1性质4 :具有n个结点的完全二叉树的深度为log2n +1性质5：若对含11个结点的完全二叉树从上到下旦从左至右进行1至n的编号，则对完全二叉树 中任意一个编号为1的结点：若1=1，则该结点是二叉树的根，无双亲，否则，编号为 1/2的结点为其双亲结点;若2in,则该结点无左孩子，否则，编号为21的结点为其左孩子结点；若2i+ln,则该结点无右孩子结点，否

11、则，编号为21+1的结点为其右孩子结点。两类特殊的二叉树：1)满二叉树：指的是深度为k且含有2k-l个结点的二叉树。2)完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。2、二叉树的顺序存储表示，要求能根据二叉树画出其顺序存储结构，或根据二叉树的顺序 存储结构画出相应的二叉树。用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完 全二叉树上编号为1的结点元素存储在如上定义的一维数组中下标为1-1的分量中。对于一 般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中, 以“0”表示不存在此结点。党全二叉树：从上到下，从左

12、往右依次编413、二叉树的二叉链表存储结构定义。二叉树的结点由一个数据元素和分别指向其左右子树的两个分支构成，则表示二叉树的 链表中的结点至少包含3个域：数据域和左、右指针域。链表的头指针指向链表的根结点。4、二叉树的先序、中序、后序遍历算法。先序遍历若二叉树为空树，则空操作；否则，（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树 中序遍历若二叉树为空树，则空操作；否则，中序遍历左子树；访问根结点；中序遍历右子树Status IiiOrdeiTraverse(BiTiee T,Status( *visit)(TElemType& e)IiiitStack(S); p=T;While(p

13、 | !StackEmpty(S)if (p) Push(S,p);p=p-lcliild;)else(Pop(S,p);if (!visit(p-data) return ERROR: p=p-icliild;/else/whileretuin OK;后序遍历若二叉树为空树，则空操作；否则,后序遍历左子树；后序遍历右子树；访问根结点。先片片列=中片片列xB D data=x) return (T)；p=Preorder(T-lchild. x);lf(p)返回值不是空指针，则表示X在左子树中retuin(p);elseretuin(Preoider(T-rchild. x);统计二叉树中叶子

14、结点的个数void PreOrdei (BiTiee T)(】f(T)if (!T-lchild)& (!T-rcliild)count+; /对叶子结点计数Pieorder( T-lchild);Pieoider( T-rchild);/if hit count=0; main()PreOider(T);%d” ,count);求二叉树深度mt Depth (BiTree T)(/返回二叉树的深度if ( !T) return (0);deptliLeft = Depth( T-lchild );deptliRight= Depth( T-rcluld );depthval = 1 + (d

15、eptliLeft deptliRight ?depthLeft :deptliRight);return depthval; 6、根据二叉树的先序序列和中序序列构造相应的二叉树。二叉树的先序序列：根左子树-右子树 中序序列：左子树根一右子树先序:a b c d e f g 中序:c b d_a e g f中序：7、树、森林的遍历及与二叉树之间的对应关系：树的先根遍历和后根遍历序列、森林的先 序和中序遍历序列以及与对应二叉树遍历的关系。树与二叉树的对应关系：给定一棵树，通过树的二叉链表表示法可以找到唯一的一棵二叉树 与之对应。树的二叉链表的右子树一定是空的。森林与二叉树的对应关系：将森林中的第

16、二棵树看成第一棵树的兄弟即可。 左子树是孩子，右子树是兄弟。8、哈夫曼树的构造过程、求哈夫曼编码的方法、哈夫曼树的特点、带权路径长度的求解。 哈夫曼树的构造过程根据给定的n个权值wl,w2, -,wn),构造n棵二叉树的集合F = T1,T2,，Tn,其中每棵二叉树中均只含一个带权值为Wl的根结点,其左、右子树为空树；在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;从F中删去这两棵树，同时将刚生成的新树加入到F中；重复(2)和(3)两步，直至F中只含一棵树为止。例如：己知权值W=5,6,2,9,71

17、) 2)Ek求哈夫曼编码的方法：求5个字符的编码立哈夫受树2、对边编号3、求出叶亍结点的路径4、得到字符编码67259100101ABCDE0001100 10111最优二叉树：结点的路径长度定义为：从根结点到该结点的路径上分支的数目。树的路径长度定义为：树中每个结点的路径长度之和。树的带权路径长度定义为：树中所有叶子结点的带权路径长度之和WPL(T) = wklk (对所有叶子结点)最优二叉树定义为：带权路径长度WPL最小的二叉树，又称为哈夫曼树。哈夫曼树的特点：1、有n个叶子结点2、没有度为1的结点3、总的结点数为2n-l4、形态不唯一第七章图1、理解与图相关的定义和术语。有向图(Digr

18、agh)G= (V, A)其中，V为顶点的有穷非空集合A为顶点之间的关系集合Gl= (V, (A)V=(vl, v2, v3, v4)A=(, , , 其中vx,y表示从x到y的一条弧(aic), A为弧集合，x为弧尾(tail), y为弧头(head) 无向图(Undigraph)G=(V,E)入度，记其中，V同有向图，E为顶点之间的关系集合,E为边集合G2= (V, A)V=(vl, v2, v3, v4, v5)E=(vl, v2), (vl, v4), (v2, v3), (v3, v4), (v2,v5), (v3,v5)其中，(x, y)表示x与y之间的一条连线，称为边(edge)

19、 设n为顶点数，e为边或弧的条数对无向图有：0=e=n(n-l)/2 有向图有：0=e=n(n-l) 权：与图的边或弧相关的数 网：边或孤上带有权值的图 顶点的度TD (V)无向图：为依附于顶点V的边数有向图：等于以顶点V为弧头的弧数(称为V的为ID (V)与以顶点V为孤尾的弧数(称为V 的出度，记为OD (V)之和。艮区TD (V) =ID (V) 4OD (V)路径长度：路径上边或弧的数目回路或环：首尾顶点相同的路径，称为回路或环。艮化(v=viO, vil, ，vim=v =v )简单路径：路径中不含相同顶点的路径简单回路：除首尾顶点外，路径中不含相同顶点的回路连通顶点连通：若顶点v到顶

20、点W有路径，则称顶点v与V，是连通的连通图：包括无向连通图和有向连通图无向图：若图中任意两个顶点vi,vj都是连通的，则称该图是连通图(viovj)有向图：若图中任意两个顶点vi,巧，都存在从VI到vj和从VJ到VI的路径，则称该有向图为强连通图(WOVJ)连通分量：无向图：无向图中极大连通子图，称为连通分量有向图：有向图中极大强连通子图，称为强连通分量 生成树定义：设无向图G是含有n个顶点的连通图，则图G的生成树是含有n个顶点，且只有n-1条边的连通子图三要素：n个顶点n-1条边连通2、图的邻接矩阵、邻接表存储结构。图的邻接矩阵 设图G=其中：A1,(V,J=E)10有n个顶点，则G的邻接矩

21、阵定义为n阶方阵A。若（vi, yj ）或 EE，lAj例如；G1的邻接矩阵0 1 0 1 0 - 10 10 1 0 10 1110 10 0-01100-1无向图的邻接矩阵为对称矩阵|特点，判定两个顶点VI与VJ是否关够只需判AUJ是否为1 顶点的应容易 求待： TOC o 1-5 h z .nn- 无向国中=TD（Xri）= X： Ati, jl= 12 At j, iJ=1J=1|即1点*哪）成等于邻接矩阵中第布（或至说I）的元素之和（非。元肃个裁之 和） 有向图中 TD（Vl）-OD（Vl）4-IIXVi）nn=12 Ai,ACj, iJj=lJ=1IJ即顶点VI的出皮为邻接矩阵中第

22、I行元去之却顶点VI的入 皮为邻接 矩阵中笫，列 元*之和邻接表无向图邻接表对图中每个顶点V1建立一个单链表，链表中的结点表示依附于顶点V1的边，每个链表结点为两个域：其中：邻接点域（adjvex）记载与顶点Vi邻接的顶点信息；链域（nextarc）指向下一个与顶点Vi邻接的邻接的链表p结点每个链表附设一个头结点，头结点结构为：其中：vexdata存放顶点信息（姓名、编号等）；如图G的今侈抉参为=5W它的邻 该RK m个头结志本D 2。令表结点;JM点、的庶TTD cv-i）中 的表结点裁ofiistarc指向链表的第一个结点。如囹G1的邻痰表为，。来瓠的有向 图. 需U个衣头结点.e 个表结

23、点有向图邻接表与无向图的邻技表结构一样。只是在第I条使衣上的结点是以VI为 弧尾的各个弧头顶点特点z 1. 11个顶点，2.第条依表上的结点数为VI的出屋 （:求顶点的出度易求入度难虾头的各个g居顿点如图3的逆邻接夜为.12-d_i_LA_l0) write(closedgek.vex, k); 输出生成树的边 closedgek.lowcost:=0; 顶点 k 并入 U FOR v:=l TO vtxnum DOIF gnk, vclosedgev.lowcost THENclosedgev.lowcost:=gnk.v;closedgev.vex:=k 新顶点并入U后，重选最小代价边ENDP:nmuspantree.PRIM)算法nuiuspantiee_PRIM的几点说明：gn为网的邻接矩阵即gni, j=wij或为无穷大辅助数组closedgel.n有两个分量：closedgek.vex存放边(k,j)依附的另一顶点j(jEU)closedgek.lowcost存放边(k, j)的权值，当值为0时,表示顶点k己加入到集合U中。 区别顶点CU或CV-U,是根据，.lowcost=0 eu.lowcost0 GV-Uclosedgek.vex EU 而 k EV-U