专题九数据结构知识.docx

《专题九数据结构知识.docx》由会员分享，可在线阅读，更多相关《专题九数据结构知识.docx（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品名师归纳总结封面可编辑资料 - - - 欢迎下载精品名师归纳总结作者： PanHongliang仅供个人学习专题九：数据结构学问数据结构是运算机软件的一门基础课程 , 运算机科学各个领域及有关的应用软件都要用到各种数据结构 语言编译要使用栈、散列表及语法树。 操作系统中用队列、储备治理表及目录可编辑资料 - - - 欢迎下载精品名师归纳总结树等。数据库系统运用线性表、 多链表及索引树等进行数据治理。 而在人工智能领域， 依求解问题性质的差异将涉及到各种不同的数据结构，如广义表、集合、搜寻树及各种有向图等等 . 学习数据结构目的是要熟识一些最常用的数据结构， 明确数据结构内在的规律关系， 知

2、道它们在运算机中的储备表示，并结合各种典型应用说明它们在进行各种操作时的动态性质及实际的执行算法，进一步提高软件计和编程水平 . 通过对不同储备结构和相应算法的对比，增强我们依据求解问题的性质挑选合理的数据结构， 并将问题求解算法的空间、 时间及复杂性掌握在肯定范畴的才能.软件设计师考试大纲对数据结构部分的要求是娴熟把握常用数据结构和常用算法，因此， 本专题从数据结构的概述动身， 对基本的概念引出常用的数据结构类型的介绍和讲解， 同时在讲解各种数据结构中间采纳算法与数据结构相结合的方式， 在算法步骤中使用数据结构， 对数据结构的重点、难点进行了分析， 最终讲解了与数据结构紧密相关的排序和查找算

3、法， 以及一些以往考试卷的分析.1. 数据结构概述数据结构 争论了运算机需要处理的数据对象和对象之间的关系。刻画了应用中涉及到的数据的规律组织。也描述了数据在运算机中如何储备、传送、转换.学习数据结构留意的问题：系统把握基本数据结构的特点及其不同实现.明白并把握各种数据结构上主要操作的实现及其性能（时间、空间）的分析.把握各种数据结构的使用特性，在算法设计中能够进行挑选.把握常用的递归、回溯、迭代、递推等方法的设计把握自顶向下、逐步求精的程序设计方法.把握自顶向下、逐步求精的程序设计方法.在学习数据结构的学问之前，我们要明白一下数据结构中的基本概念.数据 ：对客观事物的符号表示，在运算机中就是

4、指全部能输入到运算机中并被运算机程序所处理的符号的总称 .数据项：是数据的不行分割的最小单位。数据元素： 是数据的基本单位，在运算机程序中通常作为一个整体进行处理。一个数据元素可由如干个数据项组成 .数据对象： 是性质相同的数据元素的集合，是数据的一个子集.数据结构上的基本操作：插入操作删除操作更新操作查找操作排序操作可编辑资料 - - - 欢迎下载精品名师归纳总结数据结构是指数据对象及相互关系和构造方法， 一个数据结构 B 形式上可以用一个二元组表示为 B=（ A，R）. 其中， A 是数据结构中的数据（称为结点） 的非空有限集合， R是定义在 A 上的关系的非空有限集合 .依据数据元素之间

5、的关系的不同特性，通常有以下 4 类基本结构 .集合结构中的数据元素除了“同属于一个集合”的关系外，别无其他关系.线性结构结构中的数据元素之间存在一个对一个的关系.树形结构结构中的元素之间存在一个对多个的关系.图状结构或网状结构结构中的元素之间存在多个对多个的关系.数据结构中， 结点与结点间的相互关系是数据的规律结构. 数据结构在运算机中的表示（又称为映象）称为数据的物理结构，也称储备结构.数据元素之间的关系在运算机中有两种不同的表示方式：次序映象和非次序映象， 并由此得到两种不同的储备结构：次序储备结构和链式储备结构.任何一个算法的设计取决于选定的数据（规律）结构，而算法的实现依靠于采纳的储

6、备结构 .数据的规律结构分为两类：线性结构：线性表、栈、队列和串非线性结构：树、图数据的储备方法有四类：次序储备方法链接储备方法索引储备方法散列储备方法2. 常用数据结构2.1 线性表在数据结构中，线性结构常称为线性表，是最简洁、最常用的一种数据结构，它是由 n 个相同数据类型的结点组成的有限序列.其特点是：在数据元素的非空有限集合中，存在唯独的一个被称做“第一个”的数据元素存在唯独的一个被称做“最终一个”的元素数据元素除第一个之外，集合中的每个数据元素均只有一个前驱除最终一个之外，集合中每个数据元素均只有一个后继4 / 47可编辑资料 - - - 欢迎下载精品名师归纳总结一个由 n 个结点

7、e0，e1， en-1 组成的线性表记为：（ e0， e1， en-1 ） . 线性表的结点个数称为线性表的长度，长度为0 的线性表称为空的线性表，简称空表. 对于非空线性表， e0 是线性表的第一个结点， en-1 是线性表的最终一个结点 . 线性表的结点构成了一个序列，对序列中两个相邻结点ei 和 ei-1 ，称前者是后者的前驱结点，后者是 前者的后继结点 .线性表最重要的性质是线性表中结点和相对位置是确定的.线性表的结点也称为表元，或称为记录，要求线性表的结点肯定是同一类型的数据 . 线性表的结点可由如干个成分组成，其中唯独标识表元的成分成为关键字，简称键 .线性表是一个相当敏捷的数据结

8、构，它的长度可以依据需要增长或缩短. 对线性表的基本运算如下：INITIATE （ L）初始化操作LENGTH（L）求长度函数 GET（ L，i ）取元素函数PRIOR（ L， elm）求前驱函数NEXT（L， elm） 求后继函数LOCATE（L，x ） 定位函数 INSERT（L，i ，b）插入操作DELETE（L，i ）删除操作有多种储备方式能将线性表储备在运算机内，其中最常用的是次序储备和链接储备.依据储备方式的不同，其上述的运算实现也不一样. 次序储备：是最简洁的储备方式，其特点是规律关系上相邻的两个元素在物理位置上也相邻 . 通常使用一个足够大的数组，从数组的第一个元素开头，将线性

9、表的结点依次储备在数组中 .次序储备方式优点：能直接拜访线性表中的任意结点.线性表的第 i 个元素 ai的储备位置可以使用以下公式求得： LO（C ai ）=LO（C a1）+（ i-1 ）*l式中 LOC（a1）是线性表的第一个数据元素a1 的储备位置， 通常称做线性表的起始位置或基的址 .次序储备的缺点：1线性表的大小固定，铺张大量的储备空间，不利于节点的增加和削减。 执行线性表的插入和删除操作要移动其他元素，不够便利。可编辑资料 - - - 欢迎下载精品名师归纳总结链式储备线性表链接储备是用链表来储备线性表.单链表（线性链表）：从链表的第一个表元开头， 将线性表的结点依次储备在链表的各表

10、元中. 链表的每个表元除要储备线性表结点的信息以外，仍要有一个成分来储备其后继结点的指针.线性链表的特点是： 每个链表都有一个头指针， 整个链表的存取必需从头指针开头，头指针指向第一个数据元素的位置，最终的节点指针为空. 当链表为空时，头指针为空值。链表非空时，头指针指向第一个节点.链式储备的缺点：1由于要储备的址指针，所以铺张空间。 直接拜访节点不便利。循环链表：循环链表是另一种形式的链式储备结构，是单链表的变形 . 它的特点就是表中最终一个结点的指针域指向头结点，整个链表形成一个环. 因此，从表中任意一个结点动身都可以找到表中的其他结点 .循环链表和单向链表基本一样，差别仅在于算法中循环的

11、条件不是结点的指针是否为空，而是他们的指针是否等于头指针，循环链表最终一个结点的link指针不为 0 NULL ，而是指向了表的前端 .为简化操作，在循环链表中往往加入表头结点.循环链表的特点是：只要知道表中某一结点的的址，就可搜寻到全部其他结点的的址.循环链表的示例：带表头结点的循环链表：双向链表：双向链表是另一种形式的链式结构，双向链表的结点中有两个指针域，其一指向直接后继，另一指向直接前趋. 双向链表克服了单链表的单向性的缺点.前驱方向后继方向可编辑资料 - - - 欢迎下载精品名师归纳总结双向链表也可以有循环表， 链表中存在两个环 . 一个结点的前趋的后继和该结点的后继的前趋都是指向该

12、结点的.p =p lLink rLink = p rLink lLink2.2 栈栈（ Stack ）是限定仅在表尾进行插入或删除操作的线性表. 表尾端称栈顶（ top ）， 表头端称栈底（ bottom ） .如有栈S=（ s0， s1， s n-1 ）就 s0 为栈底结点， s n-1 为栈顶结点 . 通常称栈的结点插入为进栈，栈的结点删除为出栈. 由于最终进栈的结点必定最先出栈，所以栈具有后进先出的特点 . 可以用一下一个图形来形象的表示：栈有两种储备结构：次序栈和链栈次序栈即栈的次序储备结构是，利用一组的址连续的储备单元依次存放自栈底到栈顶的数据元素，同时设指针top 指示栈顶元素的当

13、前位置 .栈也可以用链表实现， 链式储备结构的栈简称链栈 . 如同时需两个以上的栈， 就最好采纳这种结构 . 对于栈上的操作，总结如下，大家可以认真看一下这些程序，一个大的程序都是由一些对数据结构的小的操作组成的.次序储备的栈的基本操作如下： 判定栈满：int stackfullseqstack *sreturn s-top= =stacksize-1。进栈：可编辑资料 - - - 欢迎下载精品名师归纳总结voidpushseqstack *s,datatypexif stackfullserror“ stack verflow” 。s-data+s-top=x。判定栈空：int stacke

14、mptyseqstack *sreturn s-top= = -1出栈：datatype popseqstack *sif stackemptyserror“stack underflow” 。x=s-datatop。s-top-。 return x。链接储备栈：用链表实现的栈，链表第一个元素是栈顶元素，链表的末尾是栈底节点，链表的头指针就是栈顶指针，栈顶指针为空就是空栈. 如同时需要两个以上的栈，最好采纳链表作储备结构链接储备的栈的操作如下： 进栈：Void pushlinkstack *p,datatype xstacknode *q q=stacknode*mallocsizeofsta

15、cknode。q data=x 。可编辑资料 - - - 欢迎下载精品名师归纳总结出栈：q next=p top 。p top=q 。可编辑资料 - - - 欢迎下载精品名师归纳总结Datatypepoplinkstack*pdatatypex 。stacknode*q=p top 。ifstackemptyperror“ stack underflow.” 。x=q data 。p top=q next 。freeq。return x。多栈处理栈浮动技术：n 个栈共享一个数组空间V mn 设立栈顶指针数组t n+1和 栈底指针数组 b n+1，t i 和 b i 分别指示第 i个栈的栈顶与栈

16、底， b n 作为掌握量，指到数组最高下标各栈初始安排空间s = m/n指针初始值t 0 =b0 = -1b n =m-1t i =b i =b i -1 +s,i = 1, 2,n-12.3 队列队列是只答应在一端进行插入， 另一端进行删除运算的线性表 . 答应删除的那一端称为队首（ front ），答应插入运算的另一端称为队尾（ rear ）. 通常称队列的结点插入为进队，队列的结点删除为出队 . 如有队列Q=（q0，q1， qn-1 ）就 q0 为队首结点， qn-1 为队尾结点 . 因最先进入队列的结点将最先出队，所以队列具有先进先出的特性 .可编辑资料 - - - 欢迎下载精品名师归

17、纳总结可以用次序储备线性表来表示队列，也可以用链表实现， 用链表实现的队列称为链队列.队列操作：int pushPNODE *top， int e是进栈函数，形参 top 是栈顶指针的指针，形参e是入栈元素 .int popPNODE *top，int oe是出栈函数，形参 top 是栈顶指针的指针，形参e作为返回出栈元素使用 .int enQueuePNODE *tail，int e是入队函数，形参tail是队尾指针的指针， 形参 e 是入队元素 .int deQueuePNODE *tail，int *e是出队函数，形参tail是队尾指针的指针， 形参 e 作为返回出队元素使用 .定义结点

18、的结构如下： typedef struct node int value。struct node *next。NODE， *PNODE。 函数 int pushPNODE *top， int ePNODE p = PNODEmallocsizeofNODE。if.preturn 1。p-value = e。p-next = *top。 /指向栈顶指针*top = p。return 0。 函数 int popPNODE *top， int *e可编辑资料 - - - 欢迎下载精品名师归纳总结PNODE p = *top 。ifp = NULL return*e = p-value。*top =

19、p-next。 1。/栈顶指向取出的数的指针freep。return 0。 函数 int enQueuePNODE *tail， int ePNODE p，t 。t = *tail。p = PNODEmallocsizeofNODE。if.p return l 。p value = e。 p next = t next 。t-next = p。/将元素加在尾指针后*tail = p。return 0。 函数 int deQueuePNODE *tail， int ePNODE p，q。if*tail-next = *tail return 1。/ 队列已经空p = *tail-next。/p获

20、得尾指针q = p-next。e = q-value。p-next = q-next。if*tail = q*tail = p。/尾指针指向最终节点freeq。return 0。可编辑资料 - - - 欢迎下载精品名师归纳总结循环队列 Circular Queue:储备队列的数组被当作首尾相接的表处理 .队头、队尾指针加 1 时从 maxSize -1 直接进到 0，可用语言的取模 余数 运算实现 .队头指针进 1:front= front+ 1 %maxSize。队尾指针进 1:rear = rear+ 1 %maxSize。队列初始化： front=rear = 0 。队空条件： fron

21、t=rear 。队满条件： rear + 1 %maxSize = front循环队列的进队和出队 :优先级队列：是不同于先进先出队列的另一种队列. 每次从队列中取出的是具有最高优先权的元素2.4 串字符串是非数值处理应用中重要的处理对象. 字符串是由某字符集上的字符所组成的任何有限字符序列 .当一个字符串不包含任何字符时， 称它为空字符串 . 一个字符串所包含的有效字符个数称为这个字符串的长度. 一个字符串中任一连续的子序列称为该字符串的子串. 包含子串的字符串相应称为主串. 通常称该字符在序列中的序号为该字符在串中的位置.字符串的串值必需用单引号括 , c1c 2c3 cn 起来，但单引号

22、本身不属于串，它的作用是为了防止于变量名和数的常量混淆 . 在 C 语言中，字符串常量是用一对双引号括住如干字符来表示，如“ I am a student ”字符串通常存于字符数组中，每个字符串最终一个有效字符后跟一个字符串终止符“0 ”. 系统供应的库函数形成的字符串会自动加终止符号，而用户的应用程序中形成的字符串必需由程序自行负责添加字符串终止符号 .两个串相等当且仅当两个串的值相等，长度相等并且各个对应位置的字符都相等 .常用的字符串的基本操作有 7 种.可编辑资料 - - - 欢迎下载精品名师归纳总结ASSING（s ，t ）和 CREA（T EQUAL（ s， t ）判等函数LENG

23、TH（s ）求长度函数s ，ss ）赋值操作可编辑资料 - - - 欢迎下载精品名师归纳总结CONCA（T s ，t ）联接函数12 / 47可编辑资料 - - - 欢迎下载精品名师归纳总结SUBSTR（s ，start，len ）求子串函数 INDEX（ s， t ）定位函数REPLACE（ s，t ，v）置换函数 INSERT（s ，pos， t ）插入函数DELETE（s ，pos， t ）删除函数1 求字符串长 ,int strlenchar s（2）串复制 copychar *strcpychar to,char from。该函数将串 from 复制到串 to 中，并且返回一个指向串

24、to 的开头处的指针 .(3) 联接 concatenationcharstrcatchar to,char from该函数将串 from 复制到串 to 的末尾，并且返回一个指向串to 的开头处的指针 .(4) 串比较（ compareint strcmpchars1,char s2。该函数比较串s1 和串 s2 的大小，当返回值小于0，等于 0 或大于 0 时分别表示s1s2例如： result=strcmp“baker ”, ” Baker ”result0result=strcmp“12”, ”12” 。result=0 result=strcmp“ Joe”, ”Joseph” 。r

25、esult1 时，元素 ai,j=0.可编辑资料 - - - 欢迎下载精品名师归纳总结LOCi,j=LOC0,0+3*i-1+j-i+1 =LOC0,0+2i+j4.稀疏矩阵简洁说，设矩阵A 中有 s 个非零元素，如s 远远小于矩阵元素的总数（即sm n）， 并且分布没有肯定规律 . 用次序储备结构的三元组对稀疏矩阵进行储备，分别记录行、列和值十字链表：由于非零元的位置和个数变化，所以用链表储备更恰当。在这种情形下采纳十字链表来表示，每个非零元用一个节点表示，节点中有行、列仍有向下的域和线右的域。此外仍需要一个指向列链表的表头节点和指向行链表的表头节点. 仍可以设置一个指向整个十字链表的表头节

26、点 . 仍可以把列表头和行表头节点组成数组，便于操作。各种广义表示意图2.6 树2.6.1 概述树型结构是一类重要的非线性数据结构. 其中以树和二叉树最为常用，直观看来，树是以分支关系定义的层次结构.树是由一个或多个结点组成的有限集T，它满意以下两个条件：I. 有一个特定的结点，成为根结点可编辑资料 - - - 欢迎下载精品名师归纳总结II. 其余的结点分成 m（m=0）个互不相交的有限集T0，T1， Tm-1. 其中每个集合又都是一棵树，称 T0， T1， Tm-1 为根结点的子树 .这里可以看出树的定义是递归的，即一棵树由子树构成，子树又由更小的子树构成. 一个结点的子树数目， 称为结点的

27、度 . 树中各结点的度的最大值就称为树的度. 树中结点的最大层次称为树的深度 .假如将树中结点的各子树看成从左到右是有次序的（即不能交换） ，就称该树为有序树， 否就为无序树 . 森林是 m（m=0）棵互不相交的树的集合 .储备结构树是非线性的结构，不能简洁的用结点的线性表来表示. 树有多种形式的储备结构，最常用的是标准储备形式和带逆储备形式. 在树的标准储备结构中，树中的结点可分成两部分：结点的数据和指向子结点的指针. 当程序需从结点返回到其父结点时，需要在树的结点中储备其父结点的位置信息，这种储备形式就是带逆储备结构.详细使用的链表结构有：双亲表示法： 利用每个节点只有一个双亲的特点。求节

28、点的孩子时要遍历整个向量孩子表示法：把每个节点的孩子都排列起来，一单链表储备，就n 个节点有 n个孩子链表，而n 个头指针又组成了一个线性表.孩子兄弟表示法（又称二叉树表示法，或二叉链表表示法）：节点两个指针分别指向该节点的第一个孩子和下一个兄弟节点.树的遍历在应用树结构时，常要求按某种次序获得树中全部结点的信息，这可通过树的遍历操作来实现 . 常用的树的遍历方法有：树的前序遍历：第一拜访根结点，然后从左到右遍历根结点的各棵子树.树的后序遍历： 第一从左到右按后序遍历根结点的各棵子树，然后拜访根结点.树的层次遍历： 第一拜访处于 0 层上的根结点，然后从左到右依次拜访处于1 层、 2 层上的结

29、点，即自上而下从左到右逐层拜访树各层上的结点 .2.6.2 二叉树概述与一般的树的结构比较，二叉树在结构上更规范和更有确定性，应用也比树更为广泛.16 / 47可编辑资料 - - - 欢迎下载精品名师归纳总结二叉树的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2 的结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒. 二叉树与树不同的的方在于，第一二叉树可以为空，空的二叉树没有结点。另外，在二叉树中，结点的子树是有序的，分左右两棵子二叉树 .二叉树采纳类似树的标准储备形式来储备.二叉树的性质 :二叉树具有以下重要特性 .i 层至多有个结点（ i=1 ） .k 的二叉树至多有 -

30、1 个结点（ k=1）.对任何一棵二叉树T，假如其终端结点数为 n0，度为 2 的结点数为 n2，就 n0=n2+1. n 个结点的完全二叉树的深度为.二叉树的遍历树的全部遍历方法都适用于二叉树，常用的二叉树遍历方法有3 种. #include#include #define NULL 0 Typedef struct nodechar data。struct node *lchild,*rchild。TREENODE。TREENODE *root。前序遍历 :拜访根结点，按前序遍历根结点的左子树， 按前序遍历根结点的右子树.中序遍历 :按中序遍历根结点的左子树， 拜访根结点，按中序遍历根结点

31、的右子树.中序遍历算法 :可编辑资料 - - - 欢迎下载精品名师归纳总结Void inorderTREENODE *p ifp.=NULL inorderp lchild。printf“ %c” ,p data inorderprchild。后序遍历 :按后序遍历根结点的左子树， 按后序遍历根结点的右子树， 拜访根结点 .以上 3 种遍历方法都是递归定义的 .哈夫曼及其应用 ：又称为最优树，是一类带权路径长度最短的树路径长度： 从树中一个节点到另一个节点之间的分支构成的这两个节点之间的路径，路径上的分支树木就称为路径长度。树的路径长度：从树根到每一节点的路径长度之和。树的带权路径长度：树中全

32、部叶子节点的带权路径长度之和。哈夫曼树就是一棵 n 个叶子节点的二叉树，全部叶子节点的带权之和最小.算法描述：给定 n 个节点的集合，每个节点都带权值。选两个权值最小的节点构造一棵新的二叉树，新二叉树的根节点的权值就是两个子节点权值之和。从 n 个节点中删除刚才使用的两个节点， 同时将新产生的二叉树根节点放在节点集合中.重复 2， 3 步，知道只有一棵树为止 .例题：已知节点的前序序列和中序序列分别为： 前序序列： A B C D E F G中序序列： C B E D A F G求出整个二叉树，以及构造过程2.7 图可编辑资料 - - - 欢迎下载精品名师归纳总结基本概念 :图是一种较线性表和

33、树更为复杂的数据结构. 在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关.一个图 G由非空有限的顶点集合V 和有限的边的集合 E 组成，记为 G=（ V， E）. 图一般分为两种类型 .无向图的边是顶点的无序偶，用（i ， j ）来表示顶点 i 和 j 之间的边 .有向图的边是顶点的有序偶，有向图的边也成为弧，用 来表示顶点 i 和 j 之间的弧.其中，有条边的无向图称为完全图，而具有nn-1条弧的有向图成为有向完全图.有时图的边或弧具有与它相关的树，这种与图的边或弧相关的数称作权. 带权图也简称为网 .假如同为无向图或同为有向图的两个图G1=（ V1，E1）和 G

34、2=（V2 ，E2）满意V 2V1E 2E1就称图 G2 是图 G1 的子图 .顶点的度就是指和顶点相关联的边的数目. 在有向图中，以顶点 v 为头的弧的数据成为 v的入度。以 v 为尾的弧成为 v 的出度 . 这里有一个重要的公式反映了顶点和边的关系.其中， e 表示边的数目， n 表示顶点个数， TDVi 表示顶点 Vi 的度.在图 G=（ V， E）中，假如存在顶点序列（ v0 ，v1， vk ），其中 v0 =p ，vk =q ， 且（ v0 ， v1），（ v1 ， v2），（ vk-1 ， vk ）都在 E 中，就称顶点 p 到顶点 q 有一条路径，并用（ v0 ，v 1， vk

35、）表示这条路径，路径的长度就是路径上的边或弧的数目，这条路径的长度为 k.假如第一个顶点和最终一个顶点相同的路径称为回路或环. 序列中顶点不重复显现的路径称为简洁路径 .对无向图而言，假如从任意两个不同顶点 i 和 j 之间都有路径，就该无向图是连通的. 无向图中的极大连通子图为该图的连通重量.对有向图而言，假如任意两个不同顶点i 到 j 有路径，同时 j 到 i 也有路径，就该有向图是强连通的 . 同样，无向图中的极大连通强子图为该图的强连通重量.储备结构 : 最常用的储备结构是有两种 .邻接矩阵 :这是反映顶点间邻接关系的矩阵 . 定义如下：可编辑资料 - - - 欢迎下载精品名师归纳总结

36、设 G=（V， E）是具有 n（ n 1）个顶点的图， G的邻接矩阵 M是一个 n 行 n 列的矩阵， 如（ i ，j ）或 E，就 Mij=1。否就 Mij=0.邻接表 : 这是图的链式储备结构 .图的每个顶点都建立了一个链表，且第i 个链表中的结点代表与顶点i 相关联的一条边或由顶点 i 动身的一条弧 . 而这些链表的头指针就构成一个次序线性表.另外，仍有其他的一些储备结构，如十字链表和邻接多重表，分别用来储备有向图和无向图 .图的遍历 :图的遍历是指从图中的某个顶点动身，沿着图中的边或弧拜访图中的每个顶点，并 且每个顶点只被拜访一次 . 图的遍历算法是求解图的连通性问题、拓扑排序和求关键

37、路径等算法的基础 .通常有两种方法，它们对无向图和有向图都适用.深度优先搜寻 :类似于树的先根遍历 .广度优先搜寻 :类似于树的层次遍历 .这两种算法的时间复杂度相同，不同之处仅仅在于对顶点拜访的次序不同.图的有关算法涉及到图的有关算法比较多，这里只简洁归纳介绍一下，详细算法期望大家参考有关资料 .求最小代价生成树设 G=（V ，E）是一个连通的无向图， 如 G1 是包含 G 中全部顶点的一个无回路的连通子图，就称 G1 为 G 的一棵生成树 . 其中代价最小（各条边的权值之和最小）的生成树就称为最小代价生成树（简称最小生成树） .这里供应两种算法来求解这一问题：普里姆（Prim）算法和克鲁斯卡尔（ Kruskal）算法 . 分别适用于求边稠密的网的最小生成树和边稀疏的网的最小生成树，其时间复杂度分别是 On2和 Oeloge（ e 为网中边的数目） .其中 prim 算法基本思想 ：任选一个顶点 v 0 开头，连接与 v0 最近的顶点 v1，得子树T1，再连接与 T1 最近的顶点 v2，得子树 T2，如此进行下去，直到全部顶点都用到为止 . Lv:v 到子树 T0 的直接距离 .E 是边集合 .输入加权连通图的带权邻接矩阵C=（ Cij ） n*n . 1T0- 空