1、数据结构与算法Data Structure and Algorithm数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。1968 Donald E.Knuth“The Art of Computer Programming”http:/www-cs-faculty.stanford.edu/uno/计算机排版系统TEX程序设计 =数据结构+算法数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据元素：组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。数据项：一个数据元素
2、可以由若干数据项组成。数据对象：性质相同的数据元素的集合，是数据的子集。数据数据对象数据元素数据项数据项数据项数据项数据元素不同数据元素之间不是独立的，而是存在特定的关系，将这些关系称为结构。数据结构：相互之间存在一种或多种特定关系的数据元素的集合逻辑结构：数据对象中数据元素之间的相互关系物理结构：是指数据的逻辑结构在计算机中的存储形式。示意图表示数据逻辑结构：将每一个数据元素看作一个结点，用圆圈表示。元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示。集合结构：集合结构中的数据元素，除了同属于一个集合外，它们之间没有其他关系。线性结构：线性结构中的数据元素
3、之间是一对一的关系。树形结构：树形结构中的数据元素之间存在一对多的层次关系。图形结构：图形结构的数据元素是多对多的关系物理结构顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。逻辑结构是面向问题的，物理结构是面向计算机的。物理结构的基本目的就是将数据及其逻辑关系存储到计算机的内存中。逻辑结构逻辑结构物理结构物理结构 集合结构集合结构 线性结构线性结构 树形结构树形结构 图形结构图形结构 顺序存储结构顺序存储结构 链接存储结构链接存储结构算法：解决特定问题求解步
4、骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法的特性输入：具有零个或多个输入输出：至少有一个或多个输出有穷性：算法在执行有限的步骤之后，自动结束而不会出现无线循环。确定性：算法的每一步都具有确定的含义，不会出现二义性。可行性：算法的每一步都是可行的，即每一步都能通过执行有限次数完成。Thomas H.Cormen,Chales E.Leiserson(2009)第三版“直白的说，算法就是任何明确定义的计算过程，它接收一些值或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程”简而言之，我们可以说算法就是用来解决一个特定任务的
5、一系列步骤。一个有效的算法应该含有三个重要特性：1 它必须是有限的：如果你设计的算法永无休止的尝试解决问题，那么它是无用的。2 它必须具备明确定义的指令：算法的每一步都必须准确定义，在任何场景下指令都应当没有歧义。3 它必须是有效的：一个算法被设计用以解决某个问题，那么它就应当能解决这个问题，并且应该是收敛的。算法设计的要求正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能够正确反映问题的需求、能够得到问题的正确答案1 算法程序没有语法错误2 算法程序对于合法的输入数据能够产生满足要求的输出结果3 算法程序对于非法的输入能够得出满足规格说明的结果4 算法程序对于精心选择的
6、，甚至刁难的测试数据都能够有满足要求的输出结果。可读性：算法设计的另一目的是为了便于阅读、理解和交流。健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。时间效率与空间效率算法效率的度量方法事后统计方法：主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。事前分析估计方法：在计算机程序编制前，依据统计方法进行估算高级程序语言程序运行消耗时间取决于：1 算法的策略，方法。2 编译产生的代码质量3 问题的输入规模4 机器执行指令的速度可以忽略加法常数与最高项相乘的常数并不重要判断一个算法的效率时，函数中的常
7、数和其他次要项常常可以忽略，而更应该关注最高阶项的阶数时间复杂度在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n)它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的监禁时间复杂度，简称为时间复杂度。其中，f(n)是问题规模n的某个函数。推导大推导大O阶：阶：1.用用常数常数1取代运行时间中的所有加法常数。取代运行时间中的所有加法常数。2.在修改后在修改后的运行次数函数中，只保留最高阶项。的运行次数函数中，只保留最高阶项。3.如果
8、最高阶项存在且不是如果最高阶项存在且不是1，则去除与这个项相乘，则去除与这个项相乘的常数。的常数。得到得到的结果就是大的结果就是大O阶。阶。2(log(n)xnO22(n 1)(n 1)(n 2)1222()nnnnOn 30 线性表的类型定义（a1,a2,ai-1，ai,ai1，,an）1.线性表的定义：是n个数据元素的有限序列n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点31 线性表的顺序表示和实现 线性表的顺序表示又称为顺序存储结构或顺序映像 逻辑上相邻，物理上也相邻 用一组地址连续的存储单元依次存储线性
9、表的元素，可通过数组来实现 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）32 线性表线性表(a1,a1,a2,.an)(a1,a1,a2,.an)顺序存储结构的一般形式顺序存储结构的一般形式 序号序号 存储状态存储状态 存储地址存储地址 1 b 1 b 2 b+p 2 b+p i b+(i-1)i b+(i-1)*p p n b+(n-1)n b+(n-1)*p p 自由区自由区 maxleng b+(maxleng-1)maxleng b+(maxleng-1)*p p其中其中:b-:b-表的首地址表的首地址/基地址基地址/元素元素a1a1的地址。的地址。p-
10、1 p-1个数据元素所占存储单元的数目。个数据元素所占存储单元的数目。maxleng-maxleng-最大长度最大长度,为某个常数。为某个常数。a1a1 a2a2 .aiai .anan /33 线性表顺序结构在C语言中的定义 其中：SqList-结构类型名 La-结构类型变量名 La.length-表长 La.elem0-a1 La.elemLa.length-1-an#define maxleng 100 struct SqList ElemType elemmaxleng;/下标:0,1,.,maxleng-1 int length;/表长;SqList La;34 线性表的顺序存储结构
11、定义（动态）#define List_Init_size 100#define Listincrement 10struct SqList ElemType*elem;int length;int listsize;35 顺序存储结构的顺序存储结构的寻址公式寻址公式 i=1 2 i ni=1 2 i n 地址地址=b b+1 b+(i-1)p b+(n-1)p=b b+1 b+(i-1)p b+(n-1)p 假设假设:线性表的首地址为线性表的首地址为b,b,每个数据元素占每个数据元素占p p个存储个存储 单元单元,则表中任意元素则表中任意元素ai(1in)ai(1in)的存储地址是的存储地址是
12、:LOC(i)=LOC(1)+(i-1)LOC(i)=LOC(1)+(i-1)*p p =b+(i-1)=b+(i-1)*p (1in)p (1in)例例:假设假设 b=1024,p=4,i=35 b=1024,p=4,i=35 LOC(i)=b+(i-1)LOC(i)=b+(i-1)*p p =1024+(35-1)=1024+(35-1)*4 4 =1024+34 =1024+34*4 4 =1160 =1160 a1a1a2a2.aiai.anan/36 插入算法实现举例设 L.elem0.maxleng-1中有legth个元素，在 L.elemi-1之插入新元素e，1=inext =f
13、irst;first=newnode;newnodenewnodefirst firstdatanextqdatanextdatanextdatanull firstdatanextdatanextdatanull firstdatanextq48 在链表中间插入newnode-next=current-next;current-next=newnode；newnodecurrentnewnodecurrent49datanextdatanextdatanull datanextqpdatanextdatanextdatanull datanextq50 在链表末尾插入newnode-next
14、 =current-next;current-next =newnode；newnodenewnodecurrentcurrent51 在链表中设置头结点 在链表的首元结点之前附设的一个头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便 无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表52 循环链表(Circular List)循环链表是单链表的变形。循环链表最后一个结点的 next 指针不 为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链
15、表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址53循环链表的示例 带表头结点的循环链表a1a2a3anfirstanfirsta2a1first(空表)(非空表)54 循环链表的运算与单链表类似，只是在涉及到链头与链尾的处理时稍有不同 表尾插入树的基本概念树的基本概念二叉树二叉树二叉树的存储表示二叉树的存储表示二叉树的遍历二叉树的遍历1.1 树的定义和术语树的定义和术语树：树：n（n0）个个结点结点的有限的有限集合集合。当。当n0时，称为时，称为空树；任意一棵非空树满足以下条件：空树；任意一棵非空树满足以下条件：有且仅有一个特定的称为有且仅有一个特定的称为根根的结点；的结
16、点；当当n1时，除根结点之外的其余结点被分成时，除根结点之外的其余结点被分成m（m0）个个互不相交互不相交的有限集合的有限集合T1,T2,Tm，其中其中每个集合又是一棵树，并称为这个根结点的每个集合又是一棵树，并称为这个根结点的子树子树。1 树的基本概念树的基本概念树的定义是采用递归方法树的定义是采用递归方法(a)一棵树结构一棵树结构 (b)一个非树结构一个非树结构 (c)一个非树结构一个非树结构 ACBGFEDHIACBGFDACBGFDE以下哪一棵是树？哪一棵不是？理由？结点的度：结点的度：结点所拥有的子树的个数。结点所拥有的子树的个数。树的度：树的度：树中各结点度的最大值。树中各结点度的
17、最大值。CGBDEFKLHMIJA叶子结点：叶子结点：度为度为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点：分支结点：度不为度不为0的结点，也称为非终端结点。的结点，也称为非终端结点。CGBDEFKLHMIJA孩子、双亲：孩子、双亲：树中某结点子树的根结点称为这个结点树中某结点子树的根结点称为这个结点的的孩子结点孩子结点，这个结点称为它孩子结点的，这个结点称为它孩子结点的双亲结点双亲结点；兄弟：兄弟：具有同一个双亲的孩子结点互称为兄弟。具有同一个双亲的孩子结点互称为兄弟。CGBDEFKLHMIJA路径：路径：如果树的结点序列如果树的结点序列n1,n2,nk有如下关系：有如下关系：
18、结点结点ni是是ni+1的双亲（的双亲（1=ik），则把，则把n1,n2,nk称称为一条由为一条由n1至至nk的路径；路径上经过的边的个数称为的路径；路径上经过的边的个数称为路径长度路径长度。CGBDEFKLHMIJA祖先、子孙：祖先、子孙：在树中，如果有一条路径从结点在树中，如果有一条路径从结点x到到结点结点y，那么那么x就称为就称为y的祖先，而的祖先，而y称为称为x的子孙。的子孙。CGBDEFKLHMIJA结点所在层数：结点所在层数：根结点的层数为根结点的层数为1 1；对其余任何结点，；对其余任何结点，若某结点在第若某结点在第k k层，则其孩子结点在第层，则其孩子结点在第k+1k+1层。层
19、。树的深度：树的深度：树中所有结点的最大层数，也称树中所有结点的最大层数，也称高度高度。1 1层层2层层4 4层层3层层高度高度4CGBDEFKLHMIJCCBDEFKLHJA71234568910层序编号：层序编号：将树中结点按照从上层到下层、同层从左将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从到右的次序依次给他们编以从1 1开始的连续自然数。开始的连续自然数。有序树、无序树：有序树、无序树：如果一棵树中结点的各子树从左如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为到右是有次序的，称这棵树为有序树；反之，称为无序树。无序树。数据结构中讨论的一般都是
20、有序树数据结构中讨论的一般都是有序树 ACBGFEDACBGFED树结构和线性结构的比较树结构和线性结构的比较线性结构线性结构树结构树结构第第一一个数据元素个数据元素根结点（只有根结点（只有一一个）个）无前驱无前驱无双亲无双亲最后最后一一个数据元素个数据元素叶子结点叶子结点(可以有可以有多多个个)无后继无后继无孩子无孩子其它数据元素其它数据元素其它结点其它结点一个前驱一个前驱,一个后继一个后继一个双亲一个双亲,多个孩子多个孩子一对一一对一 一对多一对多二叉树的定义二叉树的定义 二叉树是二叉树是n（n0）个结点的有限集合，该集合或个结点的有限集合，该集合或者为空集（称为空二叉树），者为空集（称为
21、空二叉树），或者由一个根结点或者由一个根结点和两棵和两棵互不相交互不相交的、分别称为根结点的的、分别称为根结点的左子树左子树和和右子树右子树的二叉树组成。的二叉树组成。2 二叉树二叉树问题转化：将树转换为二叉树，从而利用二叉树解问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。决树的有关问题。研究二叉树的意义？研究二叉树的意义？2.1 2.1 二叉树的定义二叉树的定义 二叉树的特点：二叉树的特点：每个结点最多有两棵子树；每个结点最多有两棵子树；二叉树是有序的，其次序不二叉树是有序的，其次序不能任意颠倒能任意颠倒。注意：二叉树和树是两种树结构。注意：二叉树和树是两种树结构。ABCDEF
22、GABAB二叉树的基本形态二叉树的基本形态空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树具有具有3 3个结点的树和具有个结点的树和具有3 3个结点的二叉树的形态个结点的二叉树的形态v二叉树和树是两种树结构。二叉树和树是两种树结构。2.2 2.2 二叉树的性质二叉树的性质 性质性质1 二叉树的第二叉树的第i层上最多有层上最多有2i-1个结点（个结点（i1）。）。证明：证明：当当i=1时时，第，第1层只有一个根结点，而层只有一个根结点，而 2i-1=
23、20=1，结论显然成立。结论显然成立。假定假定i=k（1ki）时结论成立，即第）时结论成立，即第k层上至多有层上至多有2k-1个结点，个结点，则则 i=k+1时时，因为第，因为第k+1层上的结点是层上的结点是第第k层上结点的孩子，而二叉树中每个结点最多有层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第个孩子，故在第k+1层上最大结点个数为第层上最大结点个数为第k层上的层上的最大结点个数的二倍，即最大结点个数的二倍，即22k-12k。结论成立。结论成立。性质性质2 深度为深度为k（k0）的二叉树，最多有的二叉树，最多有2k-1个结点个结点，最少有，最少有k个结点。个结点。证明：由性质证明
24、：由性质1可知，深度为可知，深度为k的二叉树中结点个数最多的二叉树中结点个数最多=2k-1；每一层至少要有一个结点，因此深度为每一层至少要有一个结点，因此深度为k的二叉树，的二叉树，至少有至少有k个结点。个结点。kii1)(层上结点的最大个数第深度为深度为k且具有且具有2k-1个结点的二叉树个结点的二叉树一定是一定是满二叉树，满二叉树，性质性质3 对任何一棵非空二叉树对任何一棵非空二叉树，如果如果叶子结点叶子结点数为数为n0，度为度为2的结点数为的结点数为n2，则有则有:n0n21。证明：证明：设度为设度为1的结点数为的结点数为n1，二叉树总的结点数二叉树总的结点数为为n，则有则有:n=n0
25、n1 n2。再设分支条数为再设分支条数为e，有有e=n-1=n0 n1 n2 1，同时有同时有 e=n1 2n2 因此得因此得 n0 n1 n2 1=n1 2n2，于是得证。于是得证。性质性质4 具有具有n个结点的完全二叉树的最小深度为个结点的完全二叉树的最小深度为 log2(n+1)。证明：假设具有证明：假设具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，根据完全二叉树的定义和性质根据完全二叉树的定义和性质2，有下式成立，有下式成立 2k-1 1 n 2k-1 2k-1-12k-12k-1第第k-1层层第第k层层最少结点数最少结点数最多结点数最多结点数完全二叉树是指除最后一层外
26、，每一层上的结点数均完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。达到最大值，在最后一层上只缺少右边的若干结点。对不等式取对数，有：对不等式取对数，有：k-1 log2(n+1)k即：即：log2(n+1)k log2(n+1)+1由于由于k是整数，故必有是整数，故必有k log2(n+1)。log2(n+1)+1log2n+1log2(n+1)log2(n+1)k所在区间所在区间性质性质5 对一棵具有对一棵具有n个结点的完全二叉树中从个结点的完全二叉树中从1开始按层序编开始按层序编号，则对于任意的序号为号，则对于任意的序号为i（1in）的结点（简
27、称为结点的结点（简称为结点i），），有：有：(1)如果如果i1，则结点则结点i的双亲结点的序号为的双亲结点的序号为 i/2 ；如果如果i1，则结点则结点i是根结点，无双亲结点。是根结点，无双亲结点。(2)如果如果2in，则结点则结点i的左孩子的序号为的左孩子的序号为2i；(3)如果如果2i1n，则结点则结点i的右孩子的序号为的右孩子的序号为2i1；(4)若结点编号若结点编号i为奇数，且为奇数，且i1，它处于右兄弟位置，则它的左兄弟它处于右兄弟位置，则它的左兄弟为结点为结点i-1。(5)若结点编号若结点编号i为偶数，且为偶数，且in，它处于左兄弟位置，则它的右兄弟它处于左兄弟位置，则它的右兄弟为
28、结点为结点i+1。(6)结点结点i所在层次为所在层次为 log2i +1。18910456723对一棵具有对一棵具有n个结点的完全个结点的完全二叉树中从二叉树中从1开始按层序编开始按层序编号，则号，则l 结点结点i的双亲结点为的双亲结点为 i/2；l 结点结点i的左孩子为的左孩子为2i；l 结点结点i的右孩子为的右孩子为2i1。性质性质5表明，在完全二叉树中，结点的层序编号反映表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。了结点之间的逻辑关系。二叉树的遍历操作二叉树的遍历操作 二叉树的遍历是指从根结点出发，按照某种二叉树的遍历是指从根结点出发，按照某种次序次序访问二叉树中的所有
29、结点，使得每个结点被访问一访问二叉树中的所有结点，使得每个结点被访问一次且仅被次且仅被访问访问一次。一次。二叉树遍历操作的结果？二叉树遍历操作的结果？将非线性结构线性化将非线性结构线性化抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。前序遍历前序遍历中序遍历中序遍历后序遍历后序遍历层序遍历层序遍历 二叉树的遍历二叉树的遍历二叉树的遍历方式：二叉树的遍历方式：VLR、LVR、LRV、VRL、RVL、RLV 如果限定先左后右，则二叉树遍历方式有三种：如果限定先左后右，则二叉树遍历方式有三种：前序前序：VLR中序中序：L
30、VR后序后序：LRV层序遍历层序遍历：按二叉树的层序编号的次序访问各结点。：按二叉树的层序编号的次序访问各结点。考虑二叉树的组成：考虑二叉树的组成：V遍历左子树遍历左子树L遍历右子树遍历右子树R二叉树二叉树二叉树遍历的递归算法二叉树遍历的递归算法前序（根）遍历前序（根）遍历若二叉树为空，则空操作返回若二叉树为空，则空操作返回；否则：；否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序遍历遍历根根结点的右子树。结点的右子树。前序遍历序列：前序遍历序列：-+a*b-c d/e f二叉树的遍历操作二叉树的遍历操作 中序（根）遍历中序（根）遍历若二叉树为空，则空操作
31、返回；若二叉树为空，则空操作返回；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。中序遍历序列：中序遍历序列：a+b*c-d-e/f二叉树的遍历操作二叉树的遍历操作 后序（根）遍历后序（根）遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；后序遍历序列：后序遍历序列：a b c d-*+e f/-二叉树的遍历操作二叉树的遍历操作 层序遍历层序遍历二叉树的层次遍历是指从二二
32、叉树的层次遍历是指从二叉树的第一层（即根结点）叉树的第一层（即根结点）开始，开始，从上至下从上至下逐层遍历，逐层遍历，在同一层中，则按在同一层中，则按从左到右从左到右的顺序对结点逐个访问。的顺序对结点逐个访问。层序遍历序列：层序遍历序列：-+/a*e f b c d二叉树的遍历操作二叉树的遍历操作 二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：ABDGCEF中序遍历结果：中序遍历结果：DGBAECF后序遍历结果：后序遍历结果：GDBEFCA层序遍历结果：层序遍历结果：ABCDEFGABCDEFG已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果序列是EB
33、CDAFHIGJ,试画出这棵二叉树，并求出后序遍历序列和层序遍历序列。1 图的基本概念图的定义图的定义图是由顶点的图是由顶点的有穷有穷非空非空集合和顶点之间边的集合组集合和顶点之间边的集合组成，通常表示为：成，通常表示为：G=(V，E)其中：其中：G表示一个图，表示一个图，V是图是图G中顶点的集合，中顶点的集合，E是是图图G中顶点之间边的集合。中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。在图中，顶点个数不能为零，但可以没有边。如
34、果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是有向边，则称该图为有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4图的基本术语图的基本术语 简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其
35、自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简单图。数据结构中讨论的都是简单图。图的基本术语图的基本术语 邻接、依附邻接、依附无向图中，对于任意两个顶点无向图中，对于任意两个顶点vi和顶点和顶点vj，若存在边若存在边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为邻接点，同时称边互为邻接点，同时称边(vi，vj)依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点：V2、V4V2的邻接点：的邻接点：V1、V3、V5图的
36、基本术语图的基本术语 邻接、依附邻接、依附有向图中，对于任意两个顶点有向图中，对于任意两个顶点vi和顶点和顶点vj，若存在弧若存在弧，则称顶点则称顶点vi邻接到顶点邻接到顶点vj，顶点顶点vj邻接自顶邻接自顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V1的邻接点：的邻接点：V2、V3V3的邻接点：的邻接点：V4在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。在图结构中，任意两个顶点之间都可能有关系。FECBA
37、D线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱前驱和和后继后继；在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲双亲和和孩子孩子；在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间都存在边，都存在边，则称该图为无
38、向完全图。则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，都存在方向相反的两条弧，则称该图为有向完全图则称该图为有向完全图。图的基本术语图的基本术语 V1V2V3V1V2V3V4含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。V1V2V3V1V2V3V4稀疏图：稀疏图：
39、称边数很少的图为稀疏图；称边数很少的图为稀疏图；稠密图：稠密图：称边数很多的图为稠密图。称边数很多的图为稠密图。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，通常记为点的边数，通常记为TD(v)。图的基本术语图的基本术语 顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID(v)；顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD(v)。权：权：是指对边赋予的有
40、意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图。边上带权的图，也称网图。图的基本术语图的基本术语 V1V2V3V42785路径：路径：在无向图在无向图G=(V,E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，其中，(vij-1,vij)E（1jm）。）。若若G是有向图，则路径也是有是有向图，则路径也是有方向的，顶点序列满足方向的，顶点序列满足E。图的基本术语图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。一般情况下，图中的路径不惟一。V1 到到V4的路
41、径：的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4路径长度：路径长度：图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1 V4：长度为：长度为1V1 V2 V3 V4：长度为：长度为3V1 V2 V5V3 V4：长度为：长度为4回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点除了第一个顶点和
42、最后一个顶点外，其余顶点不重复出现的回路。外，其余顶点不重复出现的回路。图的基本术语图的基本术语 V1V2V3V4V5V1V2V3V4邻接矩阵（数组表示法）邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中基本思想：用一个一维数组存储图中顶点顶点的信息，的信息，用一个二维数组（用一个二维数组（称为邻接矩阵称为邻接矩阵）存储图中各顶点）存储图中各顶点之间的之间的邻接邻接关系。关系。假设图假设图G(V，E)有有n个顶点，则邻接矩阵是一个个顶点，则邻接矩阵是一个nn的方阵，定义为：的方阵，定义为：G.Edgeij1 若若(vi,vj)E（或（或E）0 其它其它无向图的邻接矩阵的特点？无向图的邻接
43、矩阵的特点？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 G.Edge=V1 V2 V3 V4V1V2V3V4主对角线为主对角线为 0 且一定是对称矩阵。且一定是对称矩阵。如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素的个数。0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 G.Edge=V1 V2 V3 V4V1V2V3V4如何判断
44、顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素G.Edgeij是否为是否为1。0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 G.Edge=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩阵V1V3V4V2V1 V2 V3 V4vertex=将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若G.Edgeij为为1，则顶点，则顶点 j 为顶
45、点为顶点 i 的邻接点。的邻接点。0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 G.Edge=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G.Edge=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。不一定，例如有向完全图。有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点
46、 i 的出度？的出度？邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G.Edge=有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G.Edge=有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=V1 V2 V3 V4V1V2V3V4如何判断从顶点如何判断从顶点
47、 i 到顶点到顶点 j 是否存在边？是否存在边？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素G.Edgeij是否为是否为1。0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 G.Edge=邻接表邻接表邻接表存储的基本思想：对于图的每个顶点邻接表存储的基本思想：对于图的每个顶点vi，将所将所有邻接于有邻接于vi的顶点链成一个单链表，称为顶点的顶点链成一个单链表，称为顶点vi的的边边表表（对于有向图则称为出边表），所有边表的头指（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维针和存储顶点信息的一维数组构成了数组构成了顶点表顶点表。图的邻接矩阵存储结构的空间
48、复杂度？图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？如果为稀疏图则会出现什么现象？假设图假设图G有有n个顶点个顶点e条边，则存储该图需要条边，则存储该图需要O(n2)。邻接表有两种结点结构：顶点表结点和边表结点邻接表有两种结点结构：顶点表结点和边表结点。dataadjdestlink 顶点表顶点表 边边 表表 data：数据域，存放顶点信息。数据域，存放顶点信息。adj：指针域，指向边表中第一个结点。指针域，指向边表中第一个结点。dest：邻接点域，边的终点在顶点表中的下标。邻接点域，边的终点在顶点表中的下标。link：指针域，指向边表中的下一个结点。指针域，指向边表中的下
49、一个结点。template struct Edge int dest;E cost;Edge*link;template struct Vertex T data;Edge*adj;定义邻接表的结点定义邻接表的结点 dataadj destlink图的存储结构的比较图的存储结构的比较邻接矩阵和邻接表邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能空间性能 时间性能时间性能 适用范围适用范围 唯一性唯一性邻邻接接矩矩阵阵邻邻接接表表稠密图稠密图稀疏图稀疏图唯一唯一不唯一不唯一3 图的遍历图的遍历操作图的遍历操作图的遍历图的遍历是在从图中是在从图中某某一顶点出发，对图中所一顶点
50、出发，对图中所有顶点有顶点访问一次且仅访问一次且仅访问访问一次。一次。抽象操作，抽象操作，可以是对结点进行的各种可以是对结点进行的各种处理，这里处理，这里简化为输出结点的数据。简化为输出结点的数据。图的遍历操作要解决的关键问题图的遍历操作要解决的关键问题 在图中，如何选取遍历的起始顶点？在图中，如何选取遍历的起始顶点？n在在线性表线性表中，数据元素在表中的编号就是元素在序列中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；中的位置，因而其编号是唯一的；n在在树树中，将结点按层序编号，由于树具有层次性，因中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；而其层序
