




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、实用文档 文案大全 数据结构(C语言版)复习重点 重点在二、三、六、七、九、十章,考试内容两大类:概念,算法 第1章、绪论 1. 数据:是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 2. 数据元素:是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 3. 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。 其4类基本结构:集合、线性结构、树形结构、图状结构或网状结构 4. 逻辑结构:是数据元素之间的逻辑关系的描述。 5. 物理结构(存储结构):是数据结构在计算机中的表示(又称映像)。 其4种存储结构:顺序存数结构、链式存
2、数结构、索引存数结构、散列存数结构 6. 算法:是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个操作。 其5个重要特性:有穷性、确定性、可行性、输入、输出 7. 时间复杂度:算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记作,T(n)=O(f(n) ;他表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称做算法的渐进时间复杂度,简称时间复杂度。 例如: (a) +x;s=0; (b) for(i=1;i=n;+i)+x;s += x; (c) for(j=1;j=n;+j) for(k=1;knext为第一个结点地址
3、,L-next=NULL为空表。 生成结点:p=(LinkList)malloc(sizeof(LNode) 回收结点: free(q) 实用文档 文案大全 2) 循环链表特点:表中最后一个结点的指针域指向头结点,整个链表形成一个环。 循环链表的操作与线性链表基本一致,差别仅在于算法中的循环条件不是P或P-next是否为空,而是它们是否等于头指针。 3) 双向链表特点:有2个指针域,其一指向直接后继,另一指向直接前趋。 实用文档 文案大全 第3章、栈和队列 1. 栈:是限定仅在表尾进行插入或删除操作的线性表。表尾端称为栈顶,表头端称为栈底,不含有元素的空表称为空栈;栈又称为后进先出的线性表。
4、2. 队列:是一种先进先出的线性表,它只允许在表的一端进行插入,而另一端删除元素。允许插入的一端叫做队尾,允许删除的一端则称为队头。 1) 链队列:用链表示的队列。一个队列需要两个分别指示队头和队尾的指针(分别成为头指针和尾指针)才能确定唯一。和单链表一样,也给链队列添加一个头结点,并令头指针指向头结点。 2) 循环队列:与顺序栈类似,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。初始化建空队列时,令front = rear = 0,每当插入新的队列尾元素时,“尾指针增1”;每当删除队列头元素时,“头指
5、针增1”。 实用文档 文案大全 第4章、串 1. 串:是由零个或多个字符组成的有限序列。 第5章、数组和广义表 实用文档 文案大全 1. 数组特点:与线性表一样,所有数据元素都必须属于同一数据类型。 2. 数组的顺序存储结构:由于数组一般不作插入或删除操作,一旦建立了数组,则结构中的数据元素个数和元素之间的关系就不会发生变动,因此采用顺序存储结构表示数组。 存储位置计算:假设每个数据元素需占用L个存储单元,则二维数组A中任一元素aij的存储位置可由下式确定 以行序为主序的存储结构:LOC(i,j)=LOC(0,0)+(b2*i+j)*L 以列序为主序的存储结构:LOC(i,j)=LOC(0,0
6、)+(b2*j+i)*L 式中LOC(i,j)是aij的存储位置;LOC(0,0)是a00的存储位置,即二维数组A的起始存储位置,也称基地址或基址;b2在以行序为主序的存储结构时为每行存储元素的个数(列数),在以列序为主序的存储结构时为每列存储元素的个数(行数)。 3. 广义表:是线性表的推广,也有人称其为列表(lists,用复数形式以示与统称的表list的区别)。记作LS=(a1,a2,an) ,其中LS是广义表(a1,a2,an)的名称,n是它的长度。在线性表的定义中,ai(1in)只限于是单个元素。而在广义表的定义中,ai可以是单个元素,也可以是广义表,分别称为广义表LS的原子和子表。
7、例如: 第6章、树和二叉树 1. 二叉树:是一种树型的结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。 2. 二叉树的性质: 1) 性质1:在二叉树的第i层上至多有2的i减1次方个结点(i1)。 2) 性质2:深度为k的二叉树至多有2的k次方减1个结点(k1)。 深度为k的二叉树至少有k个结点(k1)。 深度为k的完全二叉树至少有2的k次方减2的k减1次方个结点(k1)。 3) 性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。 4) 性质4:具有n个结点的完全二叉树的深度为
8、log2n+1。 5) 性质5:如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层,每层从左到右),则对任一结点i(1实用文档 文案大全 ABCDEHIFGJKin)有: a) 如果i=1,则结点i是二叉树的根,无双亲;如果i1,则其双亲PARENT(i)是结点i/2。 b) 如果2in,则结点i无左孩子(结点i为叶子结点);否则其左孩子LCHILD(i)是结点2i。 c) 如果2i+1n,则结点i无右孩子;否则其右孩子RCHILD(i)是结点2i+1。 3. 满二叉树:一颗深度为k且有 2的k次方减1个结点的二叉树。 4. 完全二叉树:深
9、度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。 5. 遍历二叉树: 1) 根据二叉树写遍历结果 : a) 先序遍历(先根遍历) : DLR - + a * b - c d / e f b) 中序遍历(中根遍历): LDR a + b * c - d - e / f c) 后序遍历(后根遍历):LRD a b c d - * + e f / - 2) 根据遍历结果画二叉树: 一棵二叉树的先序、中序和后序序列分别如下,其中有部分未给出,试求出空格处的结点字符,并画出该二叉树。 先序:_B_EHI_FG_K 中序:D_HEIA_CJG_ 后序:
10、_H_EBF_KG_A 解题思路: a) 由先序或后序确定根结点;如本题后序最后一个为A,根结点为A,所以先序第一个空就为A。 b) 在中序找出根结点,根结点左侧为左子树,右侧为右子树;如本题D_HEI为左子树,_CJG_为右子树。 c) 由先序确定紧跟在根结点后的左子树根;如本题紧跟在A后的是B,B为左子树根,中序根结点的左子树只有一个空,所以为B。 d) 继续由中序确定左子树根的左右子树,左侧为左子树,右侧为右子树;如本题B的左子树为D,右子树为HEI,所以先序第二个空为D。 e) 重复c)、d)步骤确定整棵左子树;如本题先序中紧跟在D后的是E,E为B的右子树,由中序中看出E左子树为H,右
11、子树为I,补充后序填空,前两空分别为D和I。 f) 由后序确定右子树根的左子树,再由中序确定右子树根;如本题紧跟在B后的是F,F为右子树根的左子树,已知中序_CJG_为右子树,F只可能第一个空,fcd实用文档 文案大全 那第二个空为K,补全先序、中序、后序填空并可画出二叉树。 6. 森林与二叉树的转换: 1) 树转换成二叉树:连兄弟,留长子,删孩子。 a) 连线,连接所有兄弟结点。 b) 删线,仅保留双亲与长子结点的连线,删除与其他孩子结点之间的连线。 c) 整理,原有的长子结点为左子树,从兄弟转换为孩子的结点为右子树。 d) 注意,由于树根没有兄弟结点,固树转换为二叉树后,二叉树根结点的右子
12、树必为空。 2) 森林转换成二叉树:连树根及兄弟,留长子,删孩子。 a) 连线,连接每棵树的根结点及所有兄弟结点。 b) 删线,仅保留双亲与长子结点的连线,删除与其他孩子结点之间的连线。 c) 整理,第一棵树根结点为二叉树根结点,原有的长子结点为左子树,从兄弟转换为孩子的结点为右子树。 3) 二叉树转换成树:连左孩子的右孩子及其右孩子,删原树右孩子。 a) 连线,若某结点X存在左孩子XL,则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR都与X结点连线。 b) 删线,删除原二叉树的所有双亲与右孩子结点的连线。 c) 整理,原二叉树
13、根结点为树根结点。 实用文档 文案大全 4) 二叉树转换成森林:连左孩子的右孩子及其右孩子,删原树右孩子。 a) 连线,若某结点X存在左孩子XL,则将这个左孩子的右孩子结点XLR、左孩子的右孩子的右孩子结点XLRR、左孩子的右孩子的右孩子的右孩子结点XLRRR都与X结点连线。 b) 删线,删除原二叉树的所有双亲与右孩子结点的连线。 c) 整理,调整为多棵树的森林。 实用文档 文案大全 7. 赫夫曼树:又称最优树,是一类带权路径长度最短的树。 a) 两个最小数值组成一对,小的在前,大的在后;如上图中2与4最小,2在前,4在后。 b) 将两个最小数值的和算作一个数,再与其他数重复a)步骤;如上图中
14、2与4的和为6,5与6最小,5在前,6在后。 c) 最后计算WPL,它等于每个数值乘以从根结点到这个数值的连线个数的积之和;如上图中WPL=2*3+4*3+5*2+7*1=35。 8. 赫夫曼编码: a) 在赫夫曼树上,左分支代表0,右分支代表1。 b) 由根结点到指定结点的路径(从上到下把0、1连起来),就是该结点的赫夫曼编码;如上图(d)中a为0,b为10,c为110,d为111。 第7章、图 1. 图:多个结点,结点之间的关系可以是任意的,图中任意两个数据元素之间都有可能相关。 2. 无向完全图:有n(n-1)/2条边的无向图。 3. 有向完全图:有n(n-1)条边的有向图。 4. 入度
15、:以顶点V为头的弧的数目称为V的入度。 5. 出度:以V为尾的弧的数目称为V的出度。 6. 连通图:在无向图中,任意两个顶点之间都有路径。 7. 连通分量:在无向图中的极大连通子图。 实用文档 文案大全 8. 邻接矩阵:无向图的邻接矩阵关于主对角线对称,在整个矩阵中非零元素的个数等于边个数的2倍,第i行和第i列中非零元素的个数等于该结点的度。 9. 邻接表:无向图的邻接矩阵关于主对角线对称,在整个矩阵中非零元素的个数等于边个数的2倍,第i行和第i列中非零元素的个数等于该结点的度。 实用文档 文案大全 10. 深度优先遍历:从图中某个顶点出发,搜索与之相关联的顶点,选择一个访问(从左到右,从上到
16、下);再从该顶点出发,搜索与之相关联且未访问过的顶点,选择一个访问;重复上步骤,直到没有相关联且未访问过的顶点;后退一个顶点继续搜索访问,直到所有顶点都被访问过。 V0V1V2V3V4 a) 从V0出发,先找到V0的关联顶点V3。 b) 由V3出发,找到V1;由V1出发,没有关联的顶点。 c) 回到V3,从V3出发,找到V2;由V2出发,没有关联的顶点。 d) 回到V3,再回到V0,由V0出发,找到V4。 e) 从V4出发,找到V1,因为V1已经被访问过了,所以不访问。 所以最后顺序是V0, V3, V1, V2, V4。 实用文档 文案大全 11. 广度优先遍历:从图中某个顶点出发,搜索与之
17、相关联的顶点,逐个访问(从左到右,从上到下);再从这些顶点出发,搜索与之相关联且未访问过的顶点,逐个访问;重复上步骤,直到所有顶点都被访问过。 V0V1VVV a) 从V0出发,先找到V0的关联顶点V3、V4。 b) 由V3出发,找到V1、V2;由V4出发,找到V1,因为V1已经被访问过了, 所以不访问。 c) 由V1出发,没有关联的顶点;由V2出发,没有关联的顶点。 所以最后顺序是V0, V3, V4, V1, V2。 12. 最小生成树: 1) 普里姆算法:连相邻权值最小的。 2) 克鲁斯卡尔算法:先连权值最小的,再依次连。 实用文档 文案大全 13. 拓扑排序:由某个集合上的一个偏序得到
18、该集合上的一个全序的操作。 14. 关键路径:路径长度最长的路径。 实用文档 文案大全 1) 如图,先求各事件的最早发生时间(顺序为V1V9) V1的最早发生时间为0,V2的最早发生时间为6,V3的最早发生时间为4,V4的最早发生时间为5。对于V5,需要V2,V3均发生,V2发生且完成的时间为6+1=7;V3发生且完成的时间为4+1=5,因而V5的最早发生时间为7。同理可求出各顶点的最早发生时间: V1 V2 V3 V4 V5 V6 V7 V8 V9 e(i) 0 6 4 5 7 7 16 14 18 2) 求各事件的最晚发生时间(顺序为V9V1) V9的最晚时间为18,V8的最晚时间为18-
19、a11=14,V7的最晚时间为18-a10=16,V6的最晚时间为14-a9=10,V5的最晚时间为V7的最晚时间减去a7和V8的最晚时间减去a8两者较小的,则V5的最晚时间为7,同理可得其他顶点的最晚发生时间: V1 V2 V3 V4 V5 V6 V7 V8 V9 l(i) 0 6 6 8 7 10 16 14 18 则li与ei相等的事件即为关键事件 即:V1,V2,V5,V7,V8,V9 可得关键路径:V1,V2,V5,V7,V9或V1,V2,V5,V8,V9 3) 求各活动的最早发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e(i) 0 0 0 6 4
20、 5 7 7 7 16 14 4) 求各活动的最晚发生时间 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 l(i) 6-6=0 6-4=2 8-5=3 7-1=6 7-1=6 10-2=8 16-9=7 14-7=7 14-4=10 18-2=16 18-4=14 则li与ei相等的活动即为关键活动 即:a1,a4,a7,a8,a10,a11 可得关键路径:V1,V2,V5,V7,V9或V1,V2,V5,V8,V9 15. 最短路径:从某顶点出发,沿图的边到达另一顶点所经过的路径中,各边上权值之和最小的一条路径。 1) 迪杰斯特拉算法: 实用文档 文案大全 2) 弗洛伊
21、德算法: 实用文档 文案大全 方法:两条线,从左上角开始计算一直到右下角 如下所示: 给出矩阵,其中矩阵A是邻接矩阵,而矩阵Path记录u,v两点之间最短路径所必须经过的点。 实用文档 文案大全 最后A3即为所求结果。 实用文档 文案大全 第9章、查找 1. 查找表:是由同一类型的数据元素(或记录)构成的集合。 2. 关键字:是数据元素(或记录)中某个数据项的值,用它可以标识(识别)一个数据元素(或记录)。 3. 静态查找表:查询某个特定的数据元素是否在查找表中,检索某个特定的数据元素的各种属性。 1) 顺序查找法:从表中最后一个记录开始,逐个进行记录的关键字和给定值比较,若某个记录的关键字和
22、给定值比较相等,则查找成功,找到所查记录;反之若直至第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查记录,查找不成功。 其存储结构要求:以顺序表或线性链表表示的静态查找表。 其平均查找长度:假设每个记录的查找概率相等,即Pi=1/n,则在等概率情况下顺序查找的平均查找长度为,ASL=(n+1)/2。 2) 折半查找法(二分查找法):先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。 其存储结构要求:以有序表表示的静态查找表。 其平均查找长度:假设表中每个记录的查找概率相等(Pi=1/n),则查找成功时折半查找的平均查找长度为,ASL=(n+1)/n*lo
23、g2(n+1)-1。 3) 索引顺序表查找法(分块查找法):先确定待查记录所在的块(子表),然后在块中顺序查找。 其存储结构要求:以索引顺序表表示的静态查找表。 其平均查找长度:将长度为n的表均匀地分成b块,每块含有s个记录,即b=n/s;又假设表中每个记录的查找概率相等,则每块查找概率为1/b,块中每个记录的查找概率为1/s,若用顺序查找确定所在块,则分块查找的平均查找长度为,ASL=(n/s+s)/2+1;若用折半查找确定所在块,则分块查找的平均查找长度为,ASLlog2(n/s+1)+s/2。 4. 动态查找表:在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已存在的某个
24、数据元素。 1) 二叉排序树:或者是一棵空树;或者是具有下列性质的二叉树:1、若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;2、若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;3、它的左、右子树也分别为二叉排序树。 2) 平衡二叉树(AVL树):它或者是一棵空树;或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是 -1、0和1。只要二叉树上有一个结点的平衡因子的绝对值大于1,则该二叉树就是不平
25、衡的。 实用文档 文案大全 下面即四种情况分别为:左左、右右、左右、右左,每种情况又有两个图、,是该情况的最简单的图形,是该情况的一般的图形。 设x为最小不平衡子树的根结点,y为刚插入的点 左左:即在x的左孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图),即y可以是c,也可以是c的左孩子(如图),也可以是c的右孩子(不在画出)。 图就不用说了,结点x和结点a变换,则树平衡了;那么图就是树中的一般情况了a结点有右孩子d,那要进行x和a变换,那么a的右孩子放哪啊?很简单,如图放在x的左孩子上;分析:xd,da,所以d可作为x的左孩子,且可作为a的右孩子中的孩子。下边这样的类似情况不再一一
26、分析,自己分析分析 实现:找到根结点x,与它的左孩子a进行交换即可使二叉树树再次平衡; 实用文档 文案大全 右右:即在x的右孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图),即y可以是c,也可以是c的右孩子(如图),也可以是c的左孩子(不在画出)。 实现:找到根结点x,与它的右孩子a进行交换即可使二叉树树再次平衡; 左右:即在x的左孩子a的右孩子c上插入一个结点y(该结点也可以是c,如图),即y可以是c,也可以是c的右孩子(如图),也可以是c的左孩子(不在画出)。 这个左右和下边的右左,稍微复杂了点,需要进行两次交换,才能达到平衡,注意这时y是c的右孩子,最终y作为x的左孩子;若y是
27、c的左孩子,最终y作为a的右孩子,画图分析一下下边类似,不再敖述。 实现:找到根结点x,让x的左孩子a与x的左孩子a的右孩子c进行交换,然后再让x与x此时的左孩子c进行交换,最终达到平衡; 右左:即在x的右孩子a的左孩子c上插入一个结点y(该结点也可以是c,如图),即y可以是c,也可以是c的右孩子(如图),也可以是c的左孩子(不在画出)。 实现:找到根结点x,让x的右孩子a与x的右孩子a的左孩子c进行交换,然后再让x与x此时的右孩子c进行交换,最终达到平衡; 上边的四种情况包含了所有插入时导致不平衡的情况,上面给出的仅仅是一棵大实用文档 文案大全 树中的最小不平衡子树,一定要想清楚,别迷了!另外一定要注意这个交换操作,比如a与b交换(a在上,b在下),b一定要占据a的位置!什么意思?就是b要放在(覆盖)储存a的那块内存上,再通俗点说,若a是x的左孩子,则交换后b要做x的左孩子;这就是所谓的b占据a的位置! 5. 哈希表: 1) 构造方法: a) 直接定址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = akey + b,其中a和b为常数(这种散列函数叫做自身函数)。若其中H(key)中已经有值了,就往下一个找,直到H(key)中没有值了,就放进去。 b) 数字分析法:分析一组数据
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2025至2030年中国大豆专用腐植酸复合肥数据监测研究报告
- 2025至2030年中国圣诞灯串数据监测研究报告
- 2025至2030年中国内花纹牵伸胶圈数据监测研究报告
- 2025至2030年中国二轴电脑弹簧机数据监测研究报告
- 2025年中国超声波粉位测量仪市场调查研究报告
- 2025年中国网上客户关系管理系统市场调查研究报告
- 2025年中国水润滑艉轴密封装置市场调查研究报告
- 2025年中国有色金属球市场调查研究报告
- 2025年中国平头无帽沿发光二极管市场调查研究报告
- 2025年中国圣诞老人提手四方篮市场调查研究报告
- 中山大学抬头信纸中山大学横式便笺纸推荐信模板a
- 无形资产评估完整版课件
- 义务教育学科作业设计与管理指南
- 《汽车发展史》PPT课件(PPT 75页)
- 常暗之厢(7规则-简体修正)
- 反诈骗防诈骗主题教育宣传图文PPT教学课件
- 制冷系统方案的设计pptx课件
- 修心七要原文
- 纳期管理流程图
- 中国TBHQ行业市场调研报告
- 1资产负债表变动情况的分析评价
评论
0/150
提交评论