数据结构复习资料(亲自整理)(共25页).docx

精选优质文档-倾情为你奉上一、 简答题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为尾的弧）。邻接表中的表结点和头结点结构：表 结 点adjvexnextarcinfo头结点datafirstarc二、无向图的邻接表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,42.由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的关联顶点32.由3出发，找到1；由1出发，没有关联的顶点。3.回到3，从3出发，找到2；由2出发，没有关联的顶点。4.回到4，出4出发，找到1，因为1已经被访问过了，所以不访问。所以最后顺序是0,3,1,2,4Prim算法 基本思想：假设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->125、 检索 二叉排序建立typedef struct node int data; struct node * lchild; 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->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.key<Ri-d.key) R0=Ri;j=i-d； /R0只是暂存单元，不是哨兵 do /查找Ri的插入位置 Rj+d；=Rj； /后移记录 j=j-d； /查找前一记录 while(j>0&&R0.key<Rj.key)； Rj+d=R0； /插入Ri到正确的位置上 /endif /ShellPass void ShellSort(SeqList R) int increment=n； /增量初值，不妨设n>0 do increment=increment/3+1； /求下一增量 ShellPass(R，increment)； /一趟增量为increment的Shell插入排序 while(increment>1) /ShellSort 直接插入排序void lnsertSort(SeqList R) /对顺序表R中的记录R1.n按递增序进行插入排序 int i，j； for(i=2;i<=n；i+) /依次插入R2，Rn if(Ri.key<Ri-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.key<Rj.key)； /当Ri.keyRj.key时终止 Rj+1=R0； /Ri插入到正确的位置上 /endif /InsertSort 选择排序void SelectSort(SeqList R) int i，j，k； for(i=1;i<n;i+)/做第i趟排序(1in-1) k=i； for(j=i+1;j<=n;j+) /在当前无序区Ri.n中选key最小的记录Rk if(Rj.key<Rk.key) k=j; /k记下目前找到的最小关键字所在的位置 if(k!=i) /交换Ri和Rk R0=Ri；Ri=Rk；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>=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<high)/仅当区间长度大于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行，共8×6=48个元素；所以A18, 9与A10, 5相差4+48=52个元素，共52×4=208个存储单元；A18, 9的地址应该是1208。 b.更一般的算法：基地址+（行标之差×每行元素个数+列标之差）×元素所占存储单元3、n个顶点的连通图最多多少边、最少多少条边？答：最多n（n-1）/2,最少n-14、设一个无向图有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 <stdio.h>#define ElemType char/节点声明，数据域、左孩子指针、右孩子指针typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/先序建立二叉树BiTree CreateBiTree() char ch; 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;/返回根节点/先序遍历二叉树void PreOrderTraverse(BiTree T) if(T) printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(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 main() BiTree T; T = CreateBiTree();/建立 PreOrderTraverse(T);/输出 getch(); 在二叉树中插入结点x，找中序首点（顺着左支一直走）、尾点（顺右）/首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。注意：新插入的结点总是叶子结点。/一typedef struct 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 < t->data) t->lchild = Insert(t->lchild, key); else t->rchild = Insert(t->rchild, key); return t; /important!二typedef struct 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 < ( *L ) -> data )/若n比当前节点的值小，则往当前节点的左子树插 insert( &( *L ) -> 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->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->Right!=NULL) preOrder(tree->Right); main() count=0; preOrder(tree); / 显示count 2、 检索： 二分法搜索（递归与非递归）必背！递归：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,5; Search(p,0,4,4); return 0; 非递归int BinarySearch(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 < x) low = mid + 1; else high = mid - 1; return -1; 二叉排序树（插入与查找）/* 二叉排序树的节点结构定义 */ typedef struct BiTNode int data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; int SearchBST( BiTree T, int key, BiTree f, BiTree *p ) /*非递归*/ /* 指针f指向T的双亲，其初始调用值为NULL */ /* 若查找成功，则指针p指向该数据元素节点，并返回TRUE */ /* 否则指针p指向查找路径上访问的最后一个节点并返回FALSE */ BiTree s; if( !T ) *p = f; return FALSE; else while( T ) if( key = T->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; 专心-专注-专业