数据结构复习资料(亲自整理)

1、索引存储结构、简答题1、链表：链表就是一串存储数据的链式结构。链式的优点在于，每个数据之间都是相 关联的。2、线性结构：线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双 队列，数组，串。3、树与二叉树二叉树是每个结点最多有两个子树的有序树；树是由n (n>=1)个有限节点组成一个具有层次关系的集合。树和二叉树的2个主要差别：1 .树中结点的最大度数没有限制，而二叉树结点的最大度数为2;2 .树的结点无左、右之分，而二叉树的结点有左、右之分。4、堆堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一

2、棵完全二叉树。5、二叉排序树二叉排序数的(递归)定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。、应用题1、树与二叉树前中后序遍历序列一、已知前序、中序遍历，求后序遍历例：前序遍历：GDAFEMHZ中序遍历：ADEFGHMZ画树求法：第一步，根据前序遍历的特点，我们知道根结点为G第二步，观察中序遍历 ADEFGHMZ其中root节点G左侧的ADEF必然是 root的左子树，G右侧的HMZ必然是root的右子树。第三步，观察左子树 ADEF,左子树的中的根节点必然是大树的root的leftch

3、ild。在前序遍历中，大树的 root的leftchild位于root之后，所以左子树 的根节点为D。第四步，同样的道理，root的右子树节点 HMZ中的根节点也可以通过前 序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。 同理，遍历的右子树的第一个节点就是右子树的根节点。树与二叉树的转换 树转换为二叉树：步辑2：去线二叉树线索化扑鼻和层次调曼多竦；2金除长子外的孩子去线二叉树转换为树:步舞h加线步1给兄第那线步骤3;层秋调整（b；中用我索链表中序线索二叉树及其存储能构汪思：图中的实线表示指针，虚线

4、表示线索。结点C的左线索为空，表示 C是中序序列的开始结点，无前趋；结点E的右线索为空，表示 E是中序序列的终端结点，无后继。线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1。2、图邻接表一、邻接表邻接表是图的一种链式存储结构。邻接表中，对图中每个顶点建立一个 单链表，第i个单链表中的结点表示依附于顶点Vi的边（对有向图是以顶点 Vi为尾的弧）。邻接表中的表结点和头结点结构：表结点adj vexn ex t a r cinfo头结点dataf i r s t arc、无向图的邻接表4、图 7-5三、有向图的邻接表和逆邻接表（一）在有向图的邻接表中，第i个单链表链接的边都是顶点 i发

5、出的边。（二）为了求第i个顶点的入度，需要遍历整个邻接表。因此可以建立逆邻接表。（三）在有向图的逆邻接表中，第i个单链表链接的边都是进入顶点i的边。出边表人边表四、邻接表小结 设图中有n个顶点，e条边，则用邻接表表示无向图时， 需要n个顶点结点，2e 个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n个顶点结点，e个 边结点。 在无向图的邻接表中，顶点 vi的度恰为第i个链表中的结点数。 在有向图中，第i个链表中的结点个数只是顶点vi的出度。在逆邻接表中的第 i个链表中的结点个数为 Vi的入度。邻接矩阵（有向、无向）1 .图的邻接矩阵表示法在图的邻接矩阵表示法中:用邻接矩阵表示顶点间的

6、相邻关系用一个顺序表来存储顶点信息2 .图的邻接矩阵(Adacency Matrix)设G=(V , E)是具有n个顶点的图，则 G的邻接矩阵是具有如下性质的n阶方阵:1若1卬u J或=是宜中的边0若OjuJ或)不是百中的边WIV【例】下图中无向图 G 5和有向图G 6的邻接矩阵分别为 A l和A 2广度优先遍历广度优先遍历是连通图的一种遍历策略。其基本思想如下:1、从图中某个顶点 V0出发，并访问此顶点；2、从V0出发，访问V0的各个未曾访问的邻接点W1, W2,，Wk;然后，依次从W1,W2,Wk出发访问各自未被访问的邻接点；3、重复步骤2,直到全部顶点都被访问为止。例如下图中：1 .从0

7、开始，首先找到0的关联顶点3,42 .由3出发，找到1, 2;由4出发，找到1,但是1已经遍历过，所以忽略。3 .由1出发，没有关联顶点；由 2出发，没有关联顶点。所以最后顺序是0,3,4,1,2深度优先遍历深度优先遍历是连通图的一种遍历策略。其基本思想如下：设x是当前被访问顶点，在对 x做过访问标记后，选择一条从x出发的未检测过的边（x, y）。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边（x, y）到达未曾访问过的 v,对y访问并将其标记为已访问过；然后从 y开始搜索，直到搜索完从 y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回到顶点 x,并且再选择一

8、条从 x出发的未检测过的边。上述过程直至 从x出发的所有边都已检测过为止。例如下图中：1 .从0开始，首先找到0的关联顶点32 .由3出发，找到1;由1出发，没有关联的顶点。3 .回到3,从3出发，找到2;由2出发，没有关联的顶点。4 .回至IJ 4,出4出发，找到1,因为1已经被访问过了，所以不访问。所以最后顺序是0,3,1,2,4Prim算法基本思想：假设 G=(V, E)是连通的，TE是G上最小生成树中边的集合。算法从 U=u0 (u0CV)、TE=开始。重复执行下列操作：在所有uCU, vCVU的边(u, v)C E中找一条权值最小的边(u0,v0)并入集合TE中，同 时v0并入U,直

9、到V=U为止。此时，TE中必有n-1条边，T=(V, TE)为G的最小生成树。Prim算法的核心：始终保持TE中的边集构成一棵生成树。注意：prim算法适合稠密图，其时间复杂度为O(n"),其时间复杂度与边得数目无关，而kruskal算法的时间复杂度为 O(eloge)跟边的数目有关，适合稀疏图。(b>(e)(d) © © ©irK用电造地小土“山用'Krusal算法图中先将每个顶点看作独立的子图，然后查找最小权值边，这条边是有限制条件的，边得两个顶点必须不在同一个图中，如上图，第一个图中找到最小权值边为（ v1, v3）,且满 足限制条件

10、，继续查找到边（v4, v6）, （v2, v5）, （v3, v6）,当查找到最后一条边时，仅 仅只有（v2, v3）满足限制条件，其他的如（v3, v4）, （v1, v4）都在一个子图里面，不满足条件，至此已经找到最小生成树的所有边。a(b)(C)(d)(c)用笄法构造最小生成对的逑器www.WuTianQixom拓扑排序由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。对上图进行拓扑排序的结果:2->8->0->3->7->1->5->6->9->4->11 ->10->125、检索二叉排序建立

11、typedef struct node int data;struct node * Ichild;struct node * rchild;node;void Init(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->lchil

12、d; /r 指向其左子树； btree *prer = p->lchild; /prer 指向其左子树 ;while(r ->rchild != NULL)/搜索左子树的最右边的叶子结点rprer = r; r = r->rchild; p->data = r->data;if(prer != r)/若r不是p的左孩子，把r的左孩子作为r的父亲的 右孩子prer->rchild = r->lchild; elsep->lchild = r->lchild; /否则结点 p的左子树指向 r的左子树free(r); return p; else

13、 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 ER各字符的哈夫曼码。(1) 统计：字符A频度1DEFT1223(2) 构造 Huffman 树：r ； I 2 1 23 i 37 I"W65合并1和2合并2和3© 一® ® <®©合并3和3排序，色排序2上 排序一®3住序合并7和11(3) 在左分枝标0,右分枝标1:luff man

14、W(4) 确定Huffman编码:字符1ADEFTR频度712233骗码010101011100110111(5)译码: ill)N产一f 1 (2 JD EHuffman树例.给定代码序列：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、内排序希尔排序I初始关醺字L49 38 6576 13 27 49 56 04一精楮序结果：二例排序结果：三总排序结果:d为当前增量void ShellPass(SeqList R int d)希尔排序中的一趟排序，for(i=d+1;i<=n ; i+) 将Rd+

15、1. n分别插入各组当前的有序区 if(Ri.key<Ri-d.key)R0=Ri;j=i-d;/R只是暂存单元，不是哨兵 do 查找Ri的插入位置Rj+d; =Rj;后移记录j=j-d;查找前一记录while(j>0&&R0.key<Rj.key);Rj+d=R0; 插入Ri到正确的位置上 /endif /ShellPassvoid ShellSort(SeqList R) int increment=n ; 增量初值，不妨设 n>0do increment=increment/3+1 ; 求下一增量ShellPass(R increment) ; /

16、 一趟增量为 increment 的 Shell 插 入排序while(increment>1) /ShellSort直接插入排序void lnsertSort(SeqList R) 对顺序表R中的记录R1.n按递增序进行插入排序 int i, j;for(i=2;i<=n ; i+) 依次才f入 R2,，Rn if(Ri.key<Ri-1.key)/若Ri.key大于等于有序区中所有的keys,则Ri/应在原有位置上R0=Ri;j=i-1; R0是哨兵，且是 Ri的副本do 从右向左在有序区R1. . i-1中查找Ri的插入位置Rj+1=Rj; /将关键字大于 Ri.key

17、的记录后移 j- while(R0.key<Rj.key) ; / 当 Ri.key> Rj.key 时终止Rj+1=R0; /Ri插入到正确的位置上/endif/InsertSort选择排序初始值：2 1 5 7 2 4 9tI IIII - Fl I/ H = 一 I 3!II ， |- TH *KJF 123 4 5678 第弟第弟第第第第void SelectSort(SeqList R)int i, j, k;for(i=1;i<n;i+)/ 做第 i 趟排序(1 & i< n-1)k=i；for(j=i+1;j<=n;j+) /在当前无序区 R

18、i.n中选key最小的记录 Rk if(Rj.key<Rk.key)k寸k记下目前找到的最小关键字所在的位置if(k!=i) / 交换 Ri和 RkR0=Ri； k； Rk=R0; /R0作暂存单元 /endif /endfor /SeleetSort交换排序void BubbleSort(SeqList R) /R (l.n)是待排序的文件，采用自下向上扫描，对R做冒泡排序int i, j;Boolean exchange; 交换标志for(i=1;i<n;i+) / 最多做 n-1 趟排序exchange=FALSE； / 本趟排序开始前，交换标志应为假for(j=n -1;j

19、>=i； j-) / 对当前无序区Ri.n 自下向上扫描if(Rj+1.key<Rj.key)/ 交换记录R0=Rj+1 ； /R0 不是哨兵，仅做暂存单元Rj+1=Rj；Rj=R0；exchange=TRUE； / 发生了交换，故将交换标志置为真if(!exchange) / 本趟排序未发生交换，提前终止算法return ； /endfor( 外循环 ) /BubbleSortvoid QuickSort(SeqList R， int low ， int high) / 对 Rlow.high 快速排序int pivotpos ； / 划分后的基准记录的位置if(low<h

20、igh)/ 仅当区间长度大于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.highint i=low ， j=m+1 ， p=0 ；

21、/ 置初始值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+

22、 ；while(j<=high) / 若第 2 个子文件非空，则复制剩余记录到 R1 中R1p+=Rj+；for(p=0 ， i=low ； i<=high ； p+ ， i+)Ri=R1p ； / 归并完成后将结果复制回Rlow.high /Merge、选择题1、二叉树的第i层至多有2A(i - 1)个结点；深度为k的二叉树至多有2” - 1个结点 (根结点的深度为1)2、二维数组A 1020, 5.10采用行序为主存方式存储，每个元素占4个存储单元，且A 10, 5的存储地址为1000,则A 18, 9的存储地址？a.不管按行还是按列，都是顺序存储。按行存储，每行 10-5+1

23、共6个元素。A10, 9 距离A10, 5之间相差4个元素；A18, 9与A10, 9相差8行，共8X 6=48个元素；所 以A18, 9与A10, 5相差4+48=52个元素，共 52 X 4=208个存储单元；A18, 9的地址 应该是1208。b.更一般的算法：基地址 +(行标之差X每行元素个数 +列标之差)X元素所占存储单3、n个顶点的连通图最多多少边、最少多少条边？答：最多 n (n-1) /2,最少n-14、设一个无向图有5顶点，度数分别是4,3,3,2,2,求该图边数？答：每条边与两个顶点相 连接，所以所有顶点上的度数之和就是图中边的两倍，本题中共有4+3+3+2+2=14个边的

24、端点，因而共有14/2=7条边。6、建立最小堆int A0=氏12,17,30,50,20,60,65,4.49 卜建堆过程6、huffman 编码回回四店回回四火a亘下 心 £ 1. I r| |T| r7iT TT|A.j I J %7、直接排序法过程用直接排序法将无序列49, 38, 65, 97, 76, 13, 27按照从大到小的顺序排 为有序列时，每一趟将把当前最大的放到第一位，然后例举出前五趟就是每一趟将把当前最大的放到第一位.即第一趟 97, 49, 38, 65, 76, 13,27第二趟97, 76, 49, 38, 65, 13, 27,第三趟97, 76, 6

25、5, 49, 38, 13, 27,第四趟97, 76, 65, 49, 38, 13, 27,第五趟97, 76, 65, 49, 38, 13, 278、四、编程题1、二叉树：二叉树的建立：#include <stdio.h>#define ElemType char节点声明，数据域、左孩子指针、右孩子指针typedef struct BiTNodechar data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/ 先序建立二叉树BiTree CreateBiTree()char ch;BiTree T;scanf("

26、%c",&ch);if(ch='#')T=NULL;elseT = (BiTree)malloc(sizeof(BiTNode);T->data = ch;T->lchild = CreateBiTree();T->rchild = CreateBiTree();return T;/ 返回根节点/ 先序遍历二叉树void PreOrderTraverse(BiTree T)if(T)printf("%c",T ->data);PreOrderTraverse(T->lchild);PreOrderTravers

27、e(T->rchild);/ 中序遍历void InOrderTraverse(BiTree T)if(T)PreOrderTraverse(T->lchild);printf("%c",T ->data);PreOrderTraverse(T->rchild);/ 后序遍历void PostOrderTraverse(BiTree T)if(T)PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild); printf("%c",T ->data);void

28、main()BiTree T;T = CreateBiTree();/ 建立PreOrderTraverse(T);/ 输出 getch(); 在二叉树中插入结点x ，找中序首点(顺着左支一直走)、尾点(顺右)/ 首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、 右儿子。 将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。 /typedef struct nodeint data;struct node * lchild;struct node * rchild;node;node * Insert(node *t , in

29、t key)if(t = NULL)node * p;p = (node *)malloc(sizeof(node);p->data = key;p->lchild = NULL;p->rchild = NULL;t = p;elseif(key < t->data)t->lchild = Insert(t ->lchild, key);elset->rchild = Insert(t->rchild, key);return t; /important!typedef struct Nodeint data;struct Node *lc

30、,*rc;node,*Link;void insert( Link *L,int n )if( *L = NULL )( *L ) = new node;/ 若找到插入位置，则新申请节点( *L ) -> lc = ( *L ) -> rc = NULL;( *L ) -> data = n;elseif( n = ( *L ) -> data )/若 n 与当前节点的值相等，则不需插入了 return ;else if( n < ( *L ) -> data )/ 若 n 比当前节点的值小，则往当前节点的左子树插insert( &( *L ) -&

31、gt; lc,n );else/ 若 n 比当前节点的值大，则往当前节点的右子树插insert( &( *L ) -> rc,n );中序遍历：typedef struct BiTNode/* 结点结构 */int data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;void Inorder(BiTree T) /* 中序遍历二叉树*/if (T) Inorder(T ->lchild); /* 遍历左子树*/ printf("%d ",T ->data);/* 访问结点 */ Inorder(T

32、 ->rchild);/* 遍历右子树*/当调用该子函数时：加入传的就是根节点，他将不断的递归一直到最左的一个叶子节点，就是不断重复T 位最左叶子节点是那么第一句再递归式就失败了，所有退回上一层输出，紧接着就执行开始递归以此类推在递归第三句时候也是严格按着1,2,3 这个顺序执行。 求一度结点，叶子结点int count=0; void preOrder(TTree:tree) if (tree!=NULL) count+;/ 先根访问，且计数/ 这里显示 tree 的数据 if (tree->Left!=NULL) preOrder(tree ->Left);if(tree

33、 ->Right!=NULL) preOrder(tree ->Right); main() count=0;preOrder(tree);/ 显示 count2、 检索： 二分法搜索(递归与非递归)必背！ ！ ！ 递归：void Search(int p,int low,int height,int key) int middle=(low+height)/2; if(low>height) printf(" 没有该数！ "); return; if(pmiddle=key)printf("%dn",middle); return;else if(pmiddle>key) Search(p,low,middle -1,key); else if(pmiddle<key)Search(p,middle+1,height,key); int main()int p5=1,2,3,4,