数据结构复习资料亲自整理.pdf
一、简答题 1、链表：链表就是一串存储数据的链式结构。链式的优点在于，每个数据之间都是相关联的。2、线性结构：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。3、树与二叉树 二叉树是每个结点最多有两个子树的有序树；树是由 n（n=1）个有限节点组成一个具有层次关系的集合。树和二叉树的 2 个主要差别：1.树中结点的最大度数没有限制，而二叉树结点的最大度数为 2；2.树的结点无左、右之分，而二叉树的结点有左、右之分。4、堆 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。5、二叉排序树 二叉排序数的（递归）定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。二、应用题 1、树与二叉树 前中后序遍历序列 一、已知前序、中序遍历，求后序遍历 例：前序遍历:GDAFEMHZ 中序遍历:ADEFGHMZ 画树求法：第一步，根据前序遍历的特点，我们知道根结点为 G 第二步，观察中序遍历 ADEFGHMZ。其中 root 节点 G 左侧的 ADEF 必然是 root 的左子树，G 右侧的 HMZ 必然是 root 的右子树。第三步，观察左子树 ADEF，左子树的中的根节点必然是大树的 root 的 leftchild。在前序遍历中，大树的 root 的 leftchild 位于 root 之后，所以左子树的根节点为 D。第四步，同样的道理，root 的右子树节点 HMZ 中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把 root 和 root 的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。树与二叉树的转换 树转换为二叉树：二叉树转换为树：二叉树线索化 注意：图中的实线表示指针，虚线表示线索。结点 C 的左线索为空，表示 C 是中序序列的开始结点，无前趋；结点 E 的右线索为空，表示 E 是中序序列的终端结点，无后继。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是 1。2、图 邻接表 一、邻接表 邻接表是图的一种链式存储结构。邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi的边（对有向图是以顶点 Vi为尾的弧）。邻接表中的表结点和头结点结构：表 结 点 adjvex nextarc info 头结点 data firstarc 二、无向图的邻接表 3、4、图 7-5 三、有向图的邻接表和逆邻接表（一）在有向图的邻接表中，第 i 个单链表链接的边都是顶点 i 发出的边。（二）为了求第 i 个顶点的入度，需要遍历整个邻接表。因此可以建立逆邻接表。（三）在有向图的逆邻接表中，第 i 个单链表链接的边都是进入顶点 i 的边。四、邻接表小结 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个顶点结点，2e 个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个顶点结点，e 个边结点。在无向图的邻接表中，顶点 vi的度恰为第 i 个链表中的结点数。在有向图中，第 i 个链表中的结点个数只是顶点 vi的出度。在逆邻接表中的第 i 个链表中的结点个数为 vi的入度。邻接矩阵（有向、无向）1图的邻接矩阵表示法 在图的邻接矩阵表示法中：用邻接矩阵表示顶点间的相邻关系 用一个顺序表来存储顶点信息 2图的邻接矩阵(Adacency Matrix)设 G=(V，E)是具有 n 个顶点的图，则 G 的邻接矩阵是具有如下性质的 n 阶方阵：【例】下图中无向图 G 5 和有向图 G 6 的邻接矩阵分别为 A l 和 A 2。广度优先遍历 广度优先遍历是连通图的一种遍历策略。其基本思想如下：1、从图中某个顶点 V0 出发，并访问此顶点；2、从 V0 出发，访问 V0 的各个未曾访问的邻接点 W1，W2，,Wk;然后,依次从 W1,W2,Wk出发访问各自未被访问的邻接点；3、重复步骤 2，直到全部顶点都被访问为止。例如下图中：1.从 0 开始，首先找到 0 的关联顶点 3,4 2.由 3 出发，找到 1，2；由 4 出发，找到 1，但是 1 已经遍历过，所以忽略。3.由 1 出发，没有关联顶点；由 2 出发，没有关联顶点。所以最后顺序是 0,3,4,1,2 深度优先遍历 深度优先遍历是连通图的一种遍历策略。其基本思想如下：设 x 是当前被访问顶点，在对 x 做过访问标记后，选择一条从 x 出发的未检测过的边(x，y)。若发现顶点 y 已访问过，则重新选择另一条从 x 出发的未检测过的边，否则沿边(x，y)到达未曾访问过的 y，对 y 访问并将其标记为已访问过；然后从 y 开始搜索，直到搜索完从 y 出发的所有路径，即访问完所有从 y 出发可达的顶点之后，才回溯到顶点 x，并且再选择一条从 x 出发的未检测过的边。上述过程直至从 x 出发的所有边都已检测过为止。例如下图中：1.从 0 开始，首先找到 0 的关联顶点 3 2.由 3 出发，找到 1；由 1 出发，没有关联的顶点。3.回到 3，从 3 出发，找到 2；由 2 出发，没有关联的顶点。4.回到 4，出 4 出发，找到 1，因为 1 已经被访问过了，所以不访问。所以最后顺序是 0,3,1,2,4 Prim 算法 基本思想：假设 G(V，E)是连通的，TE 是 G 上最小生成树中边的集合。算法从 Uu0（u0V）、TE开始。重复执行下列操作：在所有 uU，vVU 的边(u，v)E 中找一条权值最小的边(u0,v0)并入集合 TE 中，同时 v0 并入 U，直到VU 为止。此时，TE 中必有 n-1 条边，T=(V，TE)为 G 的最小生成树。Prim 算法的核心:始终保持 TE 中的边集构成一棵生成树。注意：prim 算法适合稠密图，其时间复杂度为 O(n2)，其时间复杂度与边得数目无关，而 kruskal 算法的时间复杂度为 O(eloge)跟边的数目有关，适合稀疏图。Krusal 算法 图中先将每个顶点看作独立的子图，然后查找最小权值边，这条边是有限制条件的，边得两个顶点必须不在同一个图中，如上图，第一个图中找到最小权值边为（v1，v3），且满足限制条件，继续查找到边（v4，v6），（v2，v5），（v3，v6），当查找到最后一条边时，仅仅只有（v2，v3）满足限制条件，其他的如（v3，v4），（v1，v4）都在一个子图里面，不满足条件，至此已经找到最小生成树的所有边。拓扑排序 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。对上图进行拓扑排序的结果：2-8-0-3-7-1-5-6-9-4-11-10-12 5、检索 二叉排序建立 typedefstruct node int data;struct node*lchild;struct node*rchild;node;voidInit(node*t)t=NULL;void InOrder(node*t)/中序遍历输出 if(t!=NULL)InOrder(t-lchild);printf(%d,t-data);InOrder(t-rchild);二叉排序删除 btree*DelNode(btree*p)if(p-lchild)btree*r=p-lchild;/r 指向其左子树;btree*prer=p-lchild;/prer 指向其左子树;while(r-rchild!=NULL)/搜索左子树的最右边的叶子结点 r prer=r;r=r-rchild;p-data=r-data;if(prer!=r)/若 r 不是 p 的左孩子，把 r 的左孩子作为 r 的父亲的右孩子 prer-rchild=r-lchild;else p-lchild=r-lchild;/否则结点 p 的左子树指向 r 的左子树 free(r);return p;else btree*q=p-rchild;/q 指向其右子树;free(p);return q;Huffman 树、编码与解码 例.给定有 18 个字符组成的文本：A A D A T A R A E F R T A A F T E R 求各字符的哈夫曼码。（1）统计：（2）构造 Huffman 树：（3）在左分枝标 0,右分枝标 1:（4）确定 Huffman 编码：（5）译码：例.给定代码序列：0 0 1 0 0 0 1 1 1 0 1 0 1 0 1 0 1 1 1 10 文本为：A A F A R A D E T 散列存储 6、内排序 希尔排序 void ShellPass(SeqList R，int d)/希尔排序中的一趟排序，d 为当前增量 for(i=d+1;i=n；i+)/将 Rd+1n分别插入各组当前的有序区 if(Ri.key0&R0.key0 do increment=increment/3+1；/求下一增量 ShellPass(R，increment)；/一趟增量为 increment 的 Shell 插入排序 while(increment1)/ShellSort 直接插入排序 voidlnsertSort(SeqList R)/对顺序表 R 中的记录 R1.n按递增序进行插入排序 int i，j；for(i=2;i=n；i+)/依次插入 R2，Rn if(Ri.keyRi-1.key)/若 Ri.key 大于等于有序区中所有的 keys，则 Ri /应在原有位置上 R0=Ri;j=i-1;/R0是哨兵，且是 Ri的副本 do/从右向左在有序区 R1i-1中查找 Ri的插入位置 Rj+1=Rj；/将关键字大于 Ri.key 的记录后移 j-；while(R0.keyRj.key)；/当 Ri.keyRj.key 时终止 Rj+1=R0；/Ri插入到正确的位置上 /endif /InsertSort 选择排序 voidSelectSort(SeqList R)int i，j，k；for(i=1;in;i+)/做第 i 趟排序(1in-1)k=i；for(j=i+1;j=n;j+)/在当前无序区 Ri.n中选 key 最小的记录 Rk if(Rj.keyRk.key)k=j;/k 记下目前找到的最小关键字所在的位置 if(k!=i)/交换 Ri和 Rk R0=Ri；Ri=Rk；Rk=R0；/R0作暂存单元 /endif /endfor /SeleetSort 交换排序 voidBubbleSort(SeqList R)/R（l.n)是待排序的文件，采用自下向上扫描，对 R 做冒泡排序 int i，j；Boolean exchange；/交换标志 for(i=1;i=i；j-)/对当前无序区 Ri.n自下向上扫描 if(Rj+1.keyRj.key)/交换记录 R0=Rj+1；/R0不是哨兵，仅做暂存单元 Rj+1=Rj；Rj=R0；exchange=TRUE；/发生了交换，故将交换标志置为真 if(!exchange)/本趟排序未发生交换，提前终止算法 return；/endfor(外循环)/BubbleSort void QuickSort(SeqList R，int low，int high)/对 Rlow.high快速排序 intpivotpos；/划分后的基准记录的位置 if(lowhigh)/仅当区间长度大于 1 时才须排序 pivotpos=Partition(R，low，high)；/对 Rlow.high做划分 QuickSort(R，low，pivotpos-1)；/对左区间递归排序 QuickSort(R，pivotpos+1，high)；/对右区间递归排序 /QuickSort 归并排序 void Merge(SeqList R，int low，int m，int high)/将两个有序的子文件 Rlow.m)和 Rm+1.high归并成一个有序的 /子文件 Rlow.high int i=low，j=m+1，p=0；/置初始值 RecType*R1；/R1 是局部向量，若 p 定义为此类型指针速度更快 R1=(ReeType*)malloc(high-low+1)*sizeof(RecType)；if(!R1)/申请空间失败 Error(Insufficient memory available!)；while(i=m&j=high)/两子文件非空时取其小者输出到 R1p上 R1p+=(Ri.key=Rj.key)?Ri+：Rj+；while(i=m)/若第 1 个子文件非空，则复制剩余记录到 R1 中 R1p+=Ri+；while(j=high)/若第 2 个子文件非空，则复制剩余记录到 R1 中 R1p+=Rj+；for(p=0，i=low；i=high；p+，i+)Ri=R1p；/归并完成后将结果复制回 Rlow.high /Merge 三、选择题 1、二叉树的第 i 层至多有 2(i 1)个结点；深度为 k 的二叉树至多有 2k 1 个结点（根结点的深度为1）2、二维数组 A10.20，5.10采用行序为主存方式存储，每个元素占 4 个存储单元，且 A10，5的存储地址为 1000，则 A18，9的存储地址？a.不管按行还是按列，都是顺序存储。按行存储，每行 10-5+1 共 6 个元素。A10,9距离 A10,5之间相差 4 个元素；A18,9与 A10,9相差 8 行，共 86=48 个元素；所以 A18,9与 A10,5相差 4+48=52个元素，共 524=208 个存储单元；A18,9的地址应该是 1208。b.更一般的算法：基地址+（行标之差每行元素个数+列标之差）元素所占存储单元 3、n 个顶点的连通图最多多少边、最少多少条边？答：最多 n（n-1）/2,最少 n-1 4、设一个无向图有 5 顶点,度数分别是 4,3,3,2,2,求该图边数？答：每条边与两个顶点相连接,所以所有顶点上的度数之和就是图中边的两倍,本题中共有 4+3+3+2+2=14 个边的端点,因而共有 14/2=7 条边。6、建立最小堆 建堆过程 6、huffman 编码 7、直接排序法过程 用直接排序法将无序列49，38，65，97，76，13，27按照从大到小的顺序排为有序列时，每一趟将把当前最大的放到第一位，然后例举出前五趟 就是每一趟将把当前最大的放到第一位即第一趟97，49，38，65，76，13，27 第二趟97，76，49，38，65，13，27，第三趟97，76，65，49，38，13，27，第四趟97，76，65，49，38，13，27，第五趟97，76，65，49，38，13，27 8、四、编程题 1、二叉树：二叉树的建立：#include#define ElemType char/节点声明，数据域、左孩子指针、右孩子指针 typedefstructBiTNode char data;structBiTNode*lchild,*rchild;BiTNode,*BiTree;/先序建立二叉树 BiTreeCreateBiTree()charch;BiTree T;scanf(%c,&ch);if(ch=#)T=NULL;else T=(BiTree)malloc(sizeof(BiTNode);T-data=ch;T-lchild=CreateBiTree();T-rchild=CreateBiTree();return T;/返回根节点 /先序遍历二叉树 voidPreOrderTraverse(BiTree T)if(T)printf(%c,T-data);PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);/中序遍历 voidInOrderTraverse(BiTree T)if(T)PreOrderTraverse(T-lchild);printf(%c,T-data);PreOrderTraverse(T-rchild);/后序遍历 voidPostOrderTraverse(BiTree T)if(T)PreOrderTraverse(T-lchild);PreOrderTraverse(T-rchild);printf(%c,T-data);void main()BiTree T;T=CreateBiTree();/建立 PreOrderTraverse(T);/输出 getch();在二叉树中插入结点 x，找中序首点（顺着左支一直走）、尾点（顺右）/首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。/一 typedefstruct node int data;struct node*lchild;struct node*rchild;node;node*Insert(node*t,int key)if(t=NULL)node*p;p=(node*)malloc(sizeof(node);p-data=key;p-lchild=NULL;p-rchild=NULL;t=p;else if(key data)t-lchild=Insert(t-lchild,key);else t-rchild=Insert(t-rchild,key);return t;/important!二 typedefstruct Node int data;struct Node*lc,*rc;node,*Link;void insert(Link*L,int n)if(*L=NULL)(*L)=new node;/若找到插入位置，则新申请节点(*L)-lc=(*L)-rc=NULL;(*L)-data=n;else if(n=(*L)-data)/若 n 与当前节点的值相等，则不需插入了 return;else if(n data)/若 n 比当前节点的值小，则往当前节点的左子树插 insert(&(*L)-lc,n);else/若 n 比当前节点的值大，则往当前节点的右子树插 insert(&(*L)-rc,n);中序遍历：typedefstructBiTNode/*结点结构*/int data;structBiTNode*lchild,*rchild;BiTNode,*BiTree;voidInorder(BiTree T)/*中序遍历二叉树 */if(T)Inorder(T-lchild);/*遍历左子树 */printf(%d,T-data);/*访问结点*/Inorder(T-rchild);/*遍历右子树*/当调用该子函数时：加入传的就是根节点，他将不断的递归一直到最左的一个叶子节点，就是不断重复 T 位最左叶子节点是那么第一句再递归式就失败了，所有退回上一层输出，紧接着就执行开始递归 以此类推在递归第三句时候也是严格按着 1,2,3 这个顺序执行。求一度结点，叶子结点 int count=0;voidpreOrder(TTree:tree)if(tree!=NULL)count+;/先根访问，且计数/这里显示 tree 的数据 if(tree-Left!=NULL)preOrder(tree-Left);if(tree-Right!=NULL)preOrder(tree-Right);main()count=0;preOrder(tree);/显示 count 2、检索：二分法搜索（递归与非递归）必背！递归：void Search(int p,intlow,intheight,int key)int middle=(low+height)/2;if(lowheight)printf(没有该数！);return;if(pmiddle=key)printf(%dn,middle);return;else if(pmiddlekey)Search(p,low,middle-1,key);else if(pmiddlekey)Search(p,middle+1,height,key);int main()int p5=1,2,3,4,5;Search(p,0,4,4);return 0;非递归 intBinarySearch(int*s,int x,int low,int high)int mid;while(low=high)mid=(low+high)/2;if(smid=x)return mid;else if(smid data)*p=T;return TRUE;if(key T-data)s=T;T=T-rchild;else s=T;T=T-lchild;*p=s;return FALSE;int InsertBST1(BiTree*T,int key)/*当二叉排序树 T 中不存在关键字等于 key 的数据元素时*/*插入 key 并返回 TRUE，否则返回 FALSE*/*调用查找函数 SearchBST，非递归*/BiTree p,s;if(!SearchBST2(*T,key,NULL,&p)s=(BiTree)malloc(sizeof(BiTNode);s-data=key;s-lchild=s-rchild=NULL;if(!p)*T=s;/*插入 s 为根节点，此前树为空树*/else if(key p-data)p-rchild=s;/*插入 s 为右孩子*/else p-lchild=s;/*插入 s 为左孩子*/return TRUE;return FALSE;
