![严蔚敏数据结构复习整理完整版_第1页](http://file4.renrendoc.com/view/34f543af0cf8eed5d09481d49b0d0634/34f543af0cf8eed5d09481d49b0d06341.gif)
![严蔚敏数据结构复习整理完整版_第2页](http://file4.renrendoc.com/view/34f543af0cf8eed5d09481d49b0d0634/34f543af0cf8eed5d09481d49b0d06342.gif)
![严蔚敏数据结构复习整理完整版_第3页](http://file4.renrendoc.com/view/34f543af0cf8eed5d09481d49b0d0634/34f543af0cf8eed5d09481d49b0d06343.gif)
![严蔚敏数据结构复习整理完整版_第4页](http://file4.renrendoc.com/view/34f543af0cf8eed5d09481d49b0d0634/34f543af0cf8eed5d09481d49b0d06344.gif)
![严蔚敏数据结构复习整理完整版_第5页](http://file4.renrendoc.com/view/34f543af0cf8eed5d09481d49b0d0634/34f543af0cf8eed5d09481d49b0d06345.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、本文格式为Word版,下载可任意编辑 严蔚敏数据结构复习整理完整版 1.繁杂性分析 对各种操作的时间繁杂性的分析。 主要是链表,树,排序等简单一些的分析。 分析的时候,从简单的入手,学会方法。 后续的各种豆可能让你分析时间繁杂度。 线性链表(顺序表和单链表) 链表循环链表 双向链表 2.线性结构队列(循环队列) 栈 链表主要操作:找某一个元素,插入一个(在哪个位置增加),删除一个(在哪个位置删除)。栈:查找,插入(位置固定),删除(位置固定) 队列:查找,插入(位置固定),删除(位置固定) 顺序表(可以视为一个数组) 单链表: (删除) (插入) 倒置: (查找) 循环链表 双向链表 栈: (
2、插入删除查找) 队列 (插入删除查找) 循环队列的实现,并不是像上面的图那样,实现了一个循环的样子。 3.二叉树 基本概念 二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特别情形。 二叉树是每个结点最多有两个子树的有序树。寻常根的子树被称作“左子树(left subtree)和“右子树(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。 二叉树不是树的一种特别情形,尽管其与树有大量相像之处,但树和二叉树有两个主
3、要区别: 1. 树中结点的最大度数没有限制,而二叉树结点的最大度数为2; 2. 树的结点无左、右之分,而二叉树的结点有左、右之分。 二叉树是递归定义的,其结点有左右子树之分,规律上二叉树有五种基本形态: (1)空二叉树如图(a); (2)只有一个根结点的二叉树如图(b); (3)只有左子树如图(c); (4)只有右子树如图(d); (5)完全二叉树如图(e) 注意:尽管二叉树与树有大量相像之处,但二叉树不是树的特别情形 性质 (1) 在非空二叉树中,第i层的结点总数不超过 , i=1; (2) 深度为h的二叉树最多有2h-1个结点(h=1),最少有h个结点; (3) 对于任意一棵二叉树,假如其
4、叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; (4) 具有n个结点的完全二叉树的深度为 (5)有N个结点的完全二叉树各结点假如用顺序方式存储,则结点之间有如下关系: 若I为结点编号则假如I1,则其父结点的编号为I/2; 假如2*IN,则无左儿子; 假如2*I+1N,则无右儿子。 (6)给定N个节点,能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。 (7)设有i个枝点,I为所有枝点的道路长度总和,J为叶的道路长度总和J=I+2i 存储结构 顺序存储表示 二叉树可以用数组或线性表来存储,而且假如这是满二叉树,这种方法不会浪费空间。
5、用这种紧凑排列,假如一个结点的索引为i,它的子结点能在索引2i+1和2i+2找到,并且它的父节点(假如有)能在索引floor(i-1)/2)找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。然而,它需要连续的存储空间,这样在存储高度为h的n个结点组成的一般普通树时将会浪费好多空间。一种最极坏的状况下假如深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1,而实际却只有h个结点,空间的浪费太大,这是顺序存储结构的一大缺点。 /* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typ
6、edef TElemType SqBiTreeMAX_TREE_SIZE; /* 0号单元存储根节点 */ typedef struct int level,order; /* 节点的层,本层序号(按满二叉树计算) */ position; 二叉链表存储表示 /* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree; 遍历算法 二叉树的遍历三种方式,如下: (1)前序遍历(DLR),首先访问根结点,然后遍历左子树,结
7、果遍历右子树。简记根-左-右。 (2)中序遍历(LDR),首先遍历左子树,然后访问根结点,结果遍历右子树。简记左-根-右。 (3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,结果访问根结点。简记左-右-根。 例1:如上图所示的二叉树,若按前序遍历,则其输出序列为。若按中序遍历,则其输出序列为。若按后序遍历,则其输出序列为。 前序:根A,A的左子树B,B的左子树没有,看右子树,为D,所以A-B-D。再来看A的右子树,根C,左子树E,E的左子树F,E的右子树G,G的左子树为H,没有了终止。连起来为C-E-F-G-H,结果结果为ABDCEFGH 中序:先访问根的左子树,B没有左子树,其有右子
8、树D,D无左子树,下面访问树的根A,连起来是BDA。 再访问根的右子树,C的左子树的左子树是F,F的根E,E的右子树有左子树是H,再从H出发找到G,到此C的左子树终止,找到根C,无右子树,终止。连起来是FEHGC, 中序结果连起来是BDAFEHGC 后序:B无左子树,有右子树D,再到根B。再看右子树,最下面的左子树是F,其根的右子树的左子树是H,再到H的根G,再到G的根E,E的根C 无右子树了,直接到C,这时再和B找它们其有的根A,所以连起来是DBFHGECA 深度优先遍历 在深度优先中,我们希望从根结点访问最远的结点。和图的深度优先探寻不同的是,不需记住访问过的每一个结点,由于树中不会有环。
9、 广度优先遍历 和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。 完全二叉树,满二叉树 1.满二叉树:一棵深度为k,且有个节 点称之为满二叉树 2.完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k 的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树 4.树 基本概念 树(tree)是包含n(n0)个结点的有穷集,其中: (1)每个元素称为结点(node); (2)有一个特定的结点被称为根结点或树根(root)。 (3)除根结点之外的其余数据元素被分为m(m0)个互不相交的集合T1,T2,Tm-1,其中每一个集合Ti(1=0)棵互不相交的树的集合称为森
10、林; 存储 父节点表示法 /* 树节点的定义 */#define MAX_TREE_SIZE 100typedef struct TElemType data; int parent; /* 父节点位置域 */ PTNode;typedef struct PTNode nodesMAX_TREE_SIZE; int n; /* 节点数 */ PTree; 孩子链表表示法 /*树的孩子链表存储表示*/typedef struct CTNode / 孩子节点 int child; struct CTNode *next; *ChildPtr;typedef struct ElemType data; / 节点的数据元素 ChildPtr firstchild; / 孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 节点数和根节点的位置 CTree; 5.森林 6.森林、树与二叉树的转换 将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。依照这种关系很自然地就能将树转换成相应的二叉树: 在所有兄弟结点之间加一连线; 对每个结点,除了保存与其长子的连线外,去掉该结点与其它孩子的连线。 注意: 由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。 2)将一个
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年《建筑施工技术》7月期末试题及答案
- 2024-2025学年高中化学下学期《乙烯》教学设计
- 4 地球-我们的家园(教学设计)2023-2024学年统编版道德与法治六年级下册
- Unit4 Adversity and Courage Reading and Thinking A Successful Failure教学设计-2023-2024学年高中英语人教版(2019)选择性必修第三册
- 2023年广西投资集团有限公司校园招聘考试题库及答案解析
- 隧洞施工中不稳定围岩的分析及处理措施
- 专题1 两直线的位置关系(知识梳理与考点分类讲解)-2023-2024学年七年级数学下册专项突破讲与练(北师大版)
- 2023年合心人才发展集团幼儿园教师招聘考试真题
- 珠海市委政法委选调公务员笔试真题2023
- 第八章施工质量管理体系及措施
- 材料设备采购供应方案
- 北京版小学数学二年级上册全册教案
- PISA-阅读样题及点评
- 凝聚最大价值戴比尔斯——变卖钻石为卖爱情
- 昆明市小江寻甸县功山镇段治理工程环境影响报告书
- 你有多少种画平行线的方法---课件
- 人教版英语九年级Unit-1-全单元ppt课件(126页)
- 招聘求职简历制作表格模板可编辑下载 精品简历模板 空白标准表格03
- (精心整理)深圳小学英语语法汇总
- 部编二年级语文上册单元教材分析
- 部编版道德与法治四年级下册---全册教案(表格版)
评论
0/150
提交评论