数据结构复习整理.doc
《数据结构复习整理.doc》由会员分享,可在线阅读,更多相关《数据结构复习整理.doc(57页珍藏版)》请在咨信网上搜索。
1、数据结构复习整理完整版1. 复杂性分析对各种操作的时间复杂性的分析。 主要是链表,树,排序等简单一些的分析。分析的时候,从简单的入手,学会方法。后续的各种豆可能让你分析时间复杂度。 线性链表(顺序表和单链表) 链表 循环链表
2、 双向链表2. 线性结构 队列(循环队列) 栈链表主要操作:找某一个元素,插入一个(在哪个位置增加),删除一个(在哪个位置删除)。栈:查找,插入(位置固定),删除(位置固定)队列:查找,插入(位置固定),删除(位置固定)顺序表(可以视为一个数组)单链表:(删除)(插入)
3、倒置:(查找)循环链表双向链表栈:(插入删除查找)队列(插入删除查找)循环队列的实现,并不是像上面的图那样,实现了一个循环的样子。3. 二叉树基本概念二叉树是每个节点最多有两个子树的有序树。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是,二叉树不是树的特殊情形。二叉树是每个结点最多有两个子树的有序树。通常根的子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。二叉树的每个结点至多只有二棵子树(不存在出度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树不是树的一种特殊情形,尽管其与树有许多相似
4、之处,但树和二叉树有两个主要差别: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) 对于任意一棵
5、二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;(4) 具有n个结点的完全二叉树的深度为(5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:若I为结点编号则 如果I>1,则其父结点的编号为I/2;如果2*I<=n,则其左儿子(即左子树的根结点)的编号为2*i;若2*i>N,则无左儿子;如果2*I+1<=n,则其右儿子的结点编号为2*i+1;若2*i+1>N,则无右儿子。(6)给定N个节点,能构成h(N)种不同的二叉树。h(N)为卡特兰数的第N项。h(n)=C(2*n,n)/(n+1)。(7)设有i个枝点,I为所有
6、枝点的道路长度总和,J为叶的道路长度总和J=I+2i 存储结构顺序存储表示二叉树可以用数组或线性表来存储,而且如果这是满二叉树,这种方法不会浪费空间。用这种紧凑排列,如果一个结点的索引为i,它的子结点能在索引2i+1和2i+2找到,并且它的父节点(如果有)能在索引floor(i-1)/2)找到(假设根节点的索引为0)。这种方法更有利于紧凑存储和更好的访问的局部性,特别是在前序遍历中。然而
7、,它需要连续的存储空间,这样在存储高度为h的n个结点组成的一般普通树时将会浪费很多空间。一种最极坏的情况下如果深度为h的二叉树每个节点只有右孩子需要占用2的h次幂减1,而实际却只有h个结点,空间的浪费太大,这是顺序存储结构的一大缺点。 /* 二叉树的顺序存储表示 */ #define MAX_TREE_SIZE 100 /* 二叉树的最大节点数 */ typedef TElemType SqBiTreeMAX_TREE_SIZE; /* 0号单元存储根节点 */ typedef struct int level,order; /* 节点的层,本层序号(按满二叉树计算) */ po
8、sition;二叉链表存储表示/* 二叉樹的二叉鏈表存儲表示 */ typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /* 左右孩子指針 */ BiTNode,*BiTree;遍历算法 二叉树的遍历三种方式,如下:(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树。简记根-左-右。(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树。简记左-根-右。 (3)后序遍历(LRD),首先遍历左子树,然后遍历右子树,最后访问根结点。
9、简记左-右-根。 例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没有左子树,其有右子树D
10、,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 深度优先遍历在深度优先中,我们希望从根结点访问最远的结点。和图的深度优先搜索不同的是,不需记住访问过的每一个结点,因为树中不会有环。
11、广度优先遍历和深度优先遍历不同,广度优先遍历会先访问离根节点最近的节点。完全二叉树,满二叉树1. 满二叉树:一棵深度为k,且有个节点称之为满二叉树2. 完全二叉树:深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为完全二叉树4. 树基本概念树(tree)是包含n(n>0)个结点的有穷集,其中:(1)每个元素称为结点(node);(2)有一个特定的结点被称为根结点或树根(root)。(3)除根结点之外的其余数据元素被分为m(m0)个互不相交的集合T1,T2,Tm-1,其中每一个集合Ti(1<=i<=m)本身也是一棵树,被
12、称作原树的子树(subtree)。 :="" 1.="" 2.="" 3.="" 4.="" 5.="" 6.="" 7.="" 8.="" 9.="" 10.="" 11.="" 12.="" 13.="" m="">=0)棵互不相交的树的集合称为森林;存储父节点表示法/* 树节点的定义 *
13、/#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 &nb
14、sp;ElemType data; / 节点的数据元素 ChildPtr firstchild; / 孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 节点数和根节点的位置 CTree;5.森林6.森林、树与二叉树的转换将树转换为二叉树 树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树:在所有兄弟结点之间加一连线;对每个结点,除了保留与其长子的连线外,去掉该结点与其它孩子的连线。注
15、意: 由于树根没有兄弟,故树转化为二叉树后,二叉树的根结点的右子树必为空。2)将一个森林转换为二叉树 具体方法是: 将森林中的每棵树变为二叉树 因为转换所得的二叉树的根结点的右子树均为空,故可将各二叉树的根结点视为兄弟从左至右连在一起,就形成了一棵二叉树。二叉树到树、森林的转换 把二叉树转换到树和森林自然的方式是:若结点x是双亲y的左孩子,则把x的右孩子,右孩子的右孩子,都与y用连线连起来,最后去掉所有双亲到右孩子的连线。图二元组的定义图G是一个有序二元组(V,E),其中V称为顶集(Vertices Set),E称为边集(Edges se
16、t),E与V不相交。它们亦可写成V(G)和E(G)。E的元素都是二元组,用(x,y)表示,其中x,yV。三元组的定义图G是指一个三元组(V,E,I),其中V称为顶集,E称为边集,E与V不相交;I称为关联函数,I将E中的每一个元素映射到。如果e被映射到(u,v),那么称边e连接顶点u,v,而u,v则称作e的端点,u,v此时关于e相邻。同时,若两条边i,j有一个公共顶点u,则称i,j关于u相邻。有/无向图如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,与一个节点相关联的边有出边和入边之分。相反,边没有方向的图称为无向图。简单图一个图如果1. 没有两条边,它们所关联的两个点都相同(
17、在有向图中,没有两条边的起点终点都分别相同);2. 每条边所关联的是两个不同的顶点则称为简单图(Simple graph)。简单的有向图和无向图都可以使用以上的“二元组的定义”,但形如的序对不能属于E。而无向图的边集必须是对称的,即如果,那么。基本术语阶(Order):图G中顶集V的大小称作图G的阶。子图(Sub-Graph):当图G'=(V',E')其中V包含于V,E包含于E,则G'称作图G=(V,E)的子图。每个图都是本身的子图。生成子图(Spanning Sub-Graph):指满足条件V(G') = V(G)的G的子图G。导出子图(Induced
18、 Subgraph):以图G的顶点集V的非空子集V1为顶点集,以两端点均在V1中的全体边为边集的G的子图,称为V1导出的导出子图;以图G的边集E的 非空子集E1为边集,以E1中边关联的顶点的全体为顶点集的G的子图,称为E1导出的导出子图。度(Degree):一个顶点的度是指与该顶点相关联的边的条数,顶点v的度记作d(v)。入度(In-degree)和出度(Out-degree):对于有向图来说,一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中,以其为终点的边数;出度则是相对的概念,指以该顶点为起点的边数。自环(Loop):若一条边的两个顶点为同一顶点,则此边称作自环。路径(
19、Path):从u到v的一条路径是指一个序列v0,e1,v1,e2,v2,.ek,vk,其中ei的顶点为vi及vi - 1,k称作路径的长度。如果它的起止顶点相同,该路径是“闭”的,反之,则称为“开”的。一条路径称为一简单路径(simple path),如果路径中除起始与终止顶点可以重合外,所有顶点两两不等。行迹(Trace):如果路径P(u,v)中的边各不相同,则该路径称为u到v的一条行迹。轨道(Track):如果路径P(u,v)中的顶点各不相同,则该路径称为u到v的一条轨道。闭的行迹称作回路(Circuit),闭的轨称作圈(Cycle)。(另一种定义是:walk对应上述的path,path对
20、应上述的track。Trail对应trace。)桥(Bridge):若去掉一条边,便会使得整个图不连通,该边称为桥。图的存储表示1. 数组(邻接矩阵)存储表示(有向或无向)2. 邻接表存储表示邻接表是图的一种链式存储结构。邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点Vi的边(对有向图是以顶点Vi为尾的弧)。邻接表中的表结点和头结点结构:有向图的邻接表和逆邻接表(一)在有向图的邻接表中,第i个单链表链接的边都是顶点i发出的边。(二)为了求第i个顶点的入度,需要遍历整个邻接表。因此可以建立逆邻接表。(三)在有向图的逆邻接表中,第i个单链表链接的边都是进入顶点i的边。邻
21、接表小结 设图中有n个顶点,e条边,则用邻接表表示无向图时,需要n个顶点结点,2e个表结点;用邻接表表示有向图时,若不考虑逆邻接表,只需n个顶点结点,e个边结点。 在无向图的邻接表中,顶点vi的度恰为第i个链表中的结点数。 在有向图中,第i个链表中的结点个数只是顶点vi的出度。在逆邻接表中的第i个链表中的结点个数为vi的入度。 建立邻接表的时间复杂度为O(n+e)。3. 有向图的十字链表存储表示十字链表表示特点 1.针对弧结点,增加入弧链表结构和出弧链表结构; 2.容易求得任意顶点的出度和入度,专用于有向图的操作; 3.结构
22、实现比较复杂。4.无向图的邻接多重表存储表示邻接多重表(Adjacency Multilist)主要用于存储无向图。因为,如果用邻接表存储无向图,每条边的两个边结点分别在以该边所依附的两个顶点为头结点的链表中,这给图的某 些操作带来不便。例如,对已访问过的边做标记,或者要删除图中某一条边等,都需要找到表示同一条边的两个结点。因此,在进行这一类操作的无向图的问题中采 用邻接多重表作存储结构更为适宜。邻接多重表的存储结构和十字链表类似,也是由顶点表和边表组成,每一条边用一个结点表示,其顶点表结点结构和边表结点结构如图其中,顶点表由两个域组成,vertex 域存储和该顶点相关的信息firstedge
23、 域指示第一条依附于该顶点的边;边表结点由六个域组成,mark 为标记域,可用以标记该条边是否被搜索过;ivex 和jvex 为该边依附的两个顶点在图中的位置;ilink 指向下一条依附于顶点ivex的边;jlink 指向下一条依附于顶点jvex 的边,info 为指向和边相关的各种信息的指针域。一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。在邻接表中,对图中每个顶点建立一个单链表(并按建立的次序编号),第i个单链表中 的结点表示依附于顶点vi的边(对于有向图是以顶点vi为尾的弧)。每个结点由两个域组成:邻接点
24、域(adjvex),用以指示与vi邻接的点在图中的位 置,链域(nextarc)用以指向依附于顶点vi的下一条边所对应的结点。如果用邻接表存放网(带权图)的信息,则还需要在结点中增加一个存放权值的域 (info)。每个顶点的单链表中结点的个数即为该顶点的出度(与该顶点连接的边的总数)。无论是存储图或网,都需要在每个单链表前设一表头结点,这些表 头结点的第一个域data用于存放结点vi的编号i,第二个域firstarc用于指向链表中第一个结点。在上面两个图结构中,一个是有向图,即每条边都有方向,另一个是无向图,即每条边都没有方向。在有向图中,通常将边称作弧,含箭头的一端称为弧头,另一端称为弧尾,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 严蔚敏 数据结构 复习 整理
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。