数据结构与算法课件

数据结构与算法DataStructureandAlgorithm数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。1968DonaldE.Knuth“TheArtofComputerProgramming”/~uno/计算机排版系统TEX程序设计=数据结构+算法数据：描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据元素：组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也被称为记录。数据项：一个数据元素可以由若干数据项组成。数据对象：性质相同的数据元素的集合，是数据的子集。数据数据对象数据元素数据项数据项数据项数据项数据元素不同数据元素之间不是独立的，而是存在特定的关系，将这些关系称为结构。数据结构：相互之间存在一种或多种特定关系的数据元素的集合逻辑结构：数据对象中数据元素之间的相互关系物理结构：是指数据的逻辑结构在计算机中的存储形式。示意图表示数据逻辑结构：将每一个数据元素看作一个结点，用圆圈表示。元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示。集合结构：集合结构中的数据元素，除了同属于一个集合外，它们之间没有其他关系。线性结构：线性结构中的数据元素之间是一对一的关系。树形结构：树形结构中的数据元素之间存在一对多的层次关系。图形结构：图形结构的数据元素是多对多的关系物理结构顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。逻辑结构是面向问题的，物理结构是面向计算机的。物理结构的基本目的就是将数据及其逻辑关系存储到计算机的内存中。逻辑结构物理结构集合结构线性结构树形结构图形结构顺序存储结构链接存储结构算法：解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。算法的特性输入：具有零个或多个输入输出：至少有一个或多个输出有穷性：算法在执行有限的步骤之后，自动结束而不会出现无线循环。确定性：算法的每一步都具有确定的含义，不会出现二义性。可行性：算法的每一步都是可行的，即每一步都能通过执行有限次数完成。ThomasH.Cormen,ChalesE.Leiserson(2009)<算法导论>第三版“直白的说，算法就是任何明确定义的计算过程，它接收一些值或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程”简而言之，我们可以说算法就是用来解决一个特定任务的一系列步骤。一个有效的算法应该含有三个重要特性：1

它必须是有限的：如果你设计的算法永无休止的尝试解决问题，那么它是无用的。2它必须具备明确定义的指令：算法的每一步都必须准确定义，在任何场景下指令都应当没有歧义。3它必须是有效的：一个算法被设计用以解决某个问题，那么它就应当能解决这个问题，并且应该是收敛的。算法设计的要求正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能够正确反映问题的需求、能够得到问题的正确答案1算法程序没有语法错误2算法程序对于合法的输入数据能够产生满足要求的输出结果3算法程序对于非法的输入能够得出满足规格说明的结果4算法程序对于精心选择的，甚至刁难的测试数据都能够有满足要求的输出结果。可读性：算法设计的另一目的是为了便于阅读、理解和交流。健壮性：当输入数据不合法时，算法也能做出相关处理，而不是产生异常或莫名其妙的结果。时间效率与空间效率算法效率的度量方法事后统计方法：主要是通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。事前分析估计方法：在计算机程序编制前，依据统计方法进行估算高级程序语言程序运行消耗时间取决于：1算法的策略，方法。2编译产生的代码质量3问题的输入规模4机器执行指令的速度可以忽略加法常数与最高项相乘的常数并不重要判断一个算法的效率时，函数中的常数和其他次要项常常可以忽略，而更应该关注最高阶项的阶数时间复杂度在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间度量，记作：T(n)=O(f(n))它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的监禁时间复杂度，简称为时间复杂度。其中，f(n)是问题规模n的某个函数。推导大O阶：用常数1取代运行时间中的所有加法常数。在修改后的运行次数函数中，只保留最高阶项。如果最高阶项存在且不是1，则去除与这个项相乘的常数。得到的结果就是大O阶。30

线性表的类型定义（a1,a2,…ai-1，ai,ai＋1

，…,an）1.线性表的定义：是n个数据元素的有限序列n=0时称为数据元素线性起点ai的直接前趋ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表线性终点31

线性表的顺序表示和实现线性表的顺序表示又称为顺序存储结构或顺序映像逻辑上相邻，物理上也相邻用一组地址连续的存储单元依次存储线性表的元素，可通过数组来实现若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）32

线性表(a1,a1,a2,...an)顺序存储结构的一般形式

序号存储状态存储地址1b2b+p

ib+(i-1)*p

nb+(n-1)*p

自由区maxlengb+(maxleng-1)*p其中:b----表的首地址/基地址/元素a1的地址。p----1个数据元素所占存储单元的数目。maxleng----最大长度,为某个常数。

a1

a2

...

ai

...

an

//

//

//33线性表顺序结构在C语言中的定义

其中：SqList----结构类型名

La----结构类型变量名

La.length---表长

La.elem[0]----a1La.elem[La.length-1]---an#definemaxleng100structSqList{ElemTypeelem[maxleng];//下标:0,1,...,maxleng-1intlength;//表长

};SqListLa;34线性表的顺序存储结构定义（动态）#defineList_Init_size100#defineListincrement10structSqList{ElemType*elem;intlength;intlistsize;};35 顺序存储结构的寻址公式

i=12in

地址=bb+1b+(i-1)pb+(n-1)p

假设:线性表的首地址为b,每个数据元素占p个存储单元,则表中任意元素ai(1≤i≤n)的存储地址是:

LOC(i)=LOC(1)+(i-1)*p=b+(i-1)*p(1≤i≤n)

例:假设b=1024,p=4,i=35LOC(i)=b+(i-1)*p=1024+(35-1)*4=1024+34*4=1160

a1a2...ai...an//////36插入算法实现举例 设L.elem[0..maxleng-1]中有legth个元素，在

L.elem[i-1]之插入新元素e，1<=i<=length

例.i=3,e=6,length=6

插入6之前：→→→→

258203035//////01234567835,30,20,8依次后移一个位置插入6之后：

2568203035////012345678

37顺序存储结构的评价优点：

(1)是一种随机存取结构，存取任何元素的时间是一个常数，速度快；

(2)结构简单，逻辑上相邻的元素在物理上也是相邻的；

(3)不使用指针，节省存储空间。缺点：

(1)插入和删除元素要移动大量元素，消耗大量时间；

(2)需要一个连续的存储空间；

(3)插入元素可能发生“溢出”；

(4)自由区中的存储空间不能被其它数据共享38线性表的链式存储结构顺序表：随机存取链表：逻辑相邻，物理不一定相邻特点每个元素(表项)由结点(Node)构成。线性结构

结点可以不连续存储表可扩充适用于存储空间需求不定、插入或删除频繁的情形datanexta1a2a3a4a5first39free(a)可利用存储空间a0a2a1a3freefirst(b)经过一段运行后的单链表结构单链表的存储映像40线性链表用一组任意的存储单元存储线性表的数据元素，可以是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的地址（或位置）信息，这个信息称为指针(pointer)或链(link)结点 数据域：元素本身信息指针域：指示直接后继的存储位置4131ZHAOQIANSUNLIZHOUWUZHENGWANG^H例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43131NULL3771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331H头指针42结点：数据元素的存储映像。由数据域和指针域两部分组成；链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。43头指针、头结点和首元结点头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。 单链表可由一个头指针唯一确定。头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息;首元结点是指链表中存储线性表第一个数据元素a1的结点44一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25例：答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31∴头指针的值是3145单链表的C定义 或typedefstructnode*LPointer;structnode{intdata;LPointernext;};typedefstructnode{intdata;node*next;}*LinkList;46单链表的插入在第一个结点前插入newnode->next=first;first=newnode;（插入前）（插入后）newnodenewnodefirst

firstdatanextqdatanextdatanextdatanull……firstdatanextdatanextdatanull……firstdatanextq48在链表中间插入newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodecurrentnewnodecurrent49datanextdatanextdatanull……datanextq…pdatanextdatanextdatanull……datanextq…50在链表末尾插入newnode->next=current->next; current->next=newnode；(插入前)(插入后)newnodenewnodecurrentcurrent51在链表中设置头结点在链表的首元结点之前附设的一个头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便无头结点时，当头指针的值为空时表示空表；有头结点时，当头结点的指针域为空时表示空表52

循环链表(CircularList)循环链表是单链表的变形。循环链表最后一个结点的next

指针不为NULL，而是指向了表的前端。为简化操作，在循环链表中往往加入表头结点。循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址53循环链表的示例带表头结点的循环链表a1a2a3anfirstanfirsta2a1first(空表)(非空表)54循环链表的运算与单链表类似，只是在涉及到链头与链尾的处理时稍有不同表尾插入树的基本概念二叉树二叉树的存储表示二叉树的遍历1.1树的定义和术语树：n（n≥0）个结点的有限集合。当n＝0时，称为空树；任意一棵非空树满足以下条件：⑴

有且仅有一个特定的称为根的结点；⑵

当n＞1时，除根结点之外的其余结点被分成m（m>0）个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并称为这个根结点的子树。1树的基本概念树的定义是采用递归方法(a)一棵树结构(b)一个非树结构(c)一个非树结构ACBGFEDHIACBGFDACBGFDE以下哪一棵是树？哪一棵不是？理由？结点的度：结点所拥有的子树的个数。树的度：树中各结点度的最大值。CGBDEFKLHMIJA叶子结点：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点。CGBDEFKLHMIJA孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点，这个结点称为它孩子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟。

CGBDEFKLHMIJA路径：如果树的结点序列n1,n2,…,nk有如下关系：结点ni是ni+1的双亲（1<=i<k），则把n1,n2,…,nk称为一条由n1至nk的路径；路径上经过的边的个数称为路径长度。CGBDEFKLHMIJA祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。CGBDEFKLHMIJA结点所在层数：根结点的层数为1；对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。树的深度：树中所有结点的最大层数，也称高度。1层2层4层3层高度＝4CGBDEFKLHMIJCCBDEFKLHJA71234568910层序编号：将树中结点按照从上层到下层、同层从左到右的次序依次给他们编以从1开始的连续自然数。有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树；反之，称为无序树。数据结构中讨论的一般都是有序树

ACBGFEDACBGFED树结构和线性结构的比较线性结构树结构第一个数据元素根结点（只有一个）无前驱无双亲最后一个数据元素叶子结点(可以有多个)无后继无孩子其它数据元素其它结点一个前驱,一个后继一个双亲,多个孩子一对一一对多二叉树的定义

二叉树是n（n≥0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。2二叉树问题转化：将树转换为二叉树，从而利用二叉树解决树的有关问题。研究二叉树的意义？2.1二叉树的定义

二叉树的特点：⑴每个结点最多有两棵子树；⑵二叉树是有序的，其次序不能任意颠倒。

注意：二叉树和树是两种树结构。ABCDEFGABAB二叉树的基本形态Ф空二叉树只有一个根结点左子树根结点只有左子树右子树根结点只有右子树左子树右子树根结点同时有左右子树具有3个结点的树和具有3个结点的二叉树的形态二叉树和树是两种树结构。2.2二叉树的性质

性质1二叉树的第i层上最多有2i-1个结点（i≥1）。

证明：当i=1时，第1层只有一个根结点，而2i-1=20=1，结论显然成立。假定i=k（1≤k＜i）时结论成立，即第k层上至多有2k-1个结点，则

i=k+1时，因为第k+1层上的结点是第k层上结点的孩子，而二叉树中每个结点最多有2个孩子，故在第k+1层上最大结点个数为第k层上的最大结点个数的二倍，即2×2k-1＝2k。结论成立。[证明用数学归纳法]性质2深度为k（k≥0）的二叉树，最多有2k-1个结点，最少有k个结点。

证明：由性质1可知，深度为k的二叉树中结点个数最多==2k-1；每一层至少要有一个结点，因此深度为k的二叉树，至少有k个结点。深度为k且具有2k-1个结点的二叉树一定是满二叉树，！性质3对任何一棵非空二叉树，如果叶子结点数为n0，度为2的结点数为n2，则有:n0＝n2＋1。

证明：设度为1的结点数为n1，二叉树总的结点数为n，则有:n=n0＋

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-1…2k-12k-1———第k-1层———第k层…最少结点数最多结点数完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。对不等式取对数，有：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（1≤i≤n）的结点（简称为结点i），有：

(1)如果i＞1，则结点i的双亲结点的序号为i/2；如果i＝1，则结点i是根结点，无双亲结点。(2)如果2i≤n，则结点i的左孩子的序号为2i；(3)如果2i＋1≤n，则结点i的右孩子的序号为2i＋1；(4)若结点编号i为奇数，且i≠1，它处于右兄弟位置，则它的左兄弟为结点i-1。(5)若结点编号i为偶数，且i≠n，它处于左兄弟位置，则它的右兄弟为结点i+1。(6)结点i所在层次为log2i+1一棵具有n个结点的完全二叉树中从1开始按层序编号，则结点i的双亲结点为i/2；结点i的左孩子为2i；结点i的右孩子为2i＋1。

性质5表明，在完全二叉树中，结点的层序编号反映了结点之间的逻辑关系。二叉树的遍历操作

二叉树的遍历是指从根结点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。二叉树遍历操作的结果？将非线性结构线性化抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。前序遍历中序遍历后序遍历层序遍历

二叉树的遍历二叉树的遍历方式：VLR、LVR、LRV、VRL、RVL、RLV

如果限定先左后右，则二叉树遍历方式有三种：前序：VLR中序：LVR后序：LRV层序遍历：按二叉树的层序编号的次序访问各结点。

考虑二叉树的组成：访问根结点记作V遍历左子树记作L遍历右子树记作R二叉树二叉树遍历的递归算法前序（根）遍历若二叉树为空，则空操作返回；否则：①访问根结点；②前序遍历根结点的左子树；③前序遍历根结点的右子树。前序遍历序列：-+a*b-cd/ef二叉树的遍历操作

--/+*abcdef中序（根）遍历若二叉树为空，则空操作返回；否则：①中序遍历根结点的左子树；②访问根结点；③中序遍历根结点的右子树。

中序遍历序列：a+b*c-d-e/f二叉树的遍历操作

--/+*abcdef后序（根）遍历若二叉树为空，则空操作返回；否则：①后序遍历根结点的左子树；②后序遍历根结点的右子树。③访问根结点；后序遍历序列：abcd-*+ef/-二叉树的遍历操作

--/+*abcdef层序遍历二叉树的层次遍历是指从二叉树的第一层（即根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

层序遍历序列：-+/a*efb–cd二叉树的遍历操作

--/+*abcdef二叉树遍历操作练习前序遍历结果：ABDGCEF中序遍历结果：DGBAECF后序遍历结果：GDBEFCA层序遍历结果：ABCDEFGABCDEFG已知一棵二叉树的前序遍历的结果序列是ABECDFGHIJ,中序遍历的结果序列是EBCDAFHIGJ,试画出这棵二叉树，并求出后序遍历序列和层序遍历序列。1图的基本概念图的定义图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G=(V，E)其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。在线性表中，元素个数可以为零，称为空表；在树中，结点个数可以为零，称为空树；在图中，顶点个数不能为零，但可以没有边。如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。若顶点vi和vj之间的边没有方向，则称这条边为无向边，表示为(vi,vj)。若从顶点vi到vj的边有方向，则称这条边为有向边，表示为<vi,vj>。

如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。V1V2V3V4V5V1V2V3V4图的基本术语

简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图简单图V1V2V3V4V5

数据结构中讨论的都是简单图。图的基本术语

邻接、依附无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)依附于顶点vi和顶点vj。V1V2V3V4V5V1的邻接点：V2、V4V2的邻接点：V1、V3、V5图的基本术语

邻接、依附有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，同时称弧<vi，vj>依附于顶点vi和顶点vj

。

V1V2V3V4V1的邻接点：V2、V3V3的邻接点：V4在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比在线性结构中，元素之间的关系为前驱和后继；在树结构中，结点之间的关系为双亲和孩子；在图结构中，顶点之间的关系为邻接。FECBAD线性结构ABCDEF树结构V1V2V3V4V5图结构不同结构中逻辑关系的对比无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。

图的基本术语

V1V2V3V1V2V3V4含有n个顶点的无向完全图有多少条边？含有n个顶点的有向完全图有多少条弧？

含有n个顶点的无向完全图有n×(n-1)/2条边。含有n个顶点的有向完全图有n×(n-1)条边。V1V2V3V1V2V3V4稀疏图：称边数很少的图为稀疏图；稠密图：称边数很多的图为稠密图。顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD(v)。图的基本术语

顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID(v)；顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD(v)。权：是指对边赋予的有意义的数值量。网：边上带权的图，也称网图。图的基本术语

V1V2V3V42785路径：在无向图G=(V,E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…,vim=vq)，其中，(vij-1,vij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<vij-1,vij>∈E。图的基本术语

V1V2V3V4V5一般情况下，图中的路径不惟一。V1到V4的路径：V1V4

V1V2V3V4V1V2V5V3V4路径长度：图的基本术语

非带权图——路径上边的个数带权图——路径上各边的权之和V1V2V3V4V5V1V4：长度为1V1V2V3V4：长度为3V1V2V5V3V4：长度为4回路（环）：第一个顶点和最后一个顶点相同的路径。简单路径：序列中顶点不重复出现的路径。简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。图的基本术语

V1V2V3V4V5V1V2V3V4邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中顶点的信息，用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：G.Edge[i][j]＝1若(vi,vj)∈E（或<vi,vj>∈E）0其它无向图的邻接矩阵的特点？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=0101101101001100G.Edge=V1V2V3V4V1V2V3V4主对角线为0且一定是对称矩阵。如何求顶点i的度？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=邻接矩阵的第i行（或第i列）非零元素的个数。0101101101001100G.Edge=V1V2V3V4V1V2V3V4如何判断顶点i和j之间是否存在边？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=测试邻接矩阵中相应位置的元素G.Edge[i][j]是否为1。0101101101001100G.Edge=V1V2V3V4V1V2V3V4如何求顶点i的所有邻接点？无向图的邻接矩阵V1V3V4V2V1V2V3V4vertex=将数组中第i

行元素扫描一遍，若G.Edge[i][j]为1，则顶点j

为顶点i的邻接点。0101101101001100G.Edge=V1V2V3V4V1V2V3V4有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=0110000000011000G.Edge=V1V2V3V4V1V2V3V4有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何求顶点i的出度？邻接矩阵的第i行元素之和。0110000000011000G.Edge=有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何求顶点i的入度？邻接矩阵的第i列元素之和。0110000000011000G.Edge=有向图的邻接矩阵V1V2V3V4V1V2V3V4vertex=V1V2V3V4V1V2V3V4如何判断从顶点i到顶点j是否存在边？测试邻接矩阵中相应位置的元素G.Edge[i][j]是否为1。0110000000011000G.Edge=邻接表邻接表存储的基本思想：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维数组构成了顶点表。

图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？假设图G有n个顶点e条边，则存储该图需要O(n2)。邻接表有两种结点结构：顶点表结点和边表结点。dataadjdestlink

顶点表边表data：数据域，存放顶点信息。

adj：指针域，指向边表中第一个结点。

dest：邻接点域，边的终点在顶点表中的下标。link：指针域，指向边表中的下一个结点。

template<classT,classE>structEdge{intdest;Ecost;Edge<T,E>*link;……};template<classT,classE>structVertex{

Tdata;Edge<T,E>*adj;};定义邻接表的结点

dataadj

destlink图的存储结构的比较——邻接矩阵和邻接表O（n2）O（n+e）O（n2）O（n+e）空间性能时间性能适用范围唯一性邻接矩阵邻接表稠密图稀疏图唯一不唯一3图的遍历图的遍历操作图的遍历是在从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

抽象操作，可以是对结点进行的各种处理，这里简化为输出结点的数据。图的遍历操作要解决的关键问题①在图中，如何选取遍历的起始顶点？在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。解决方案：从编号小的顶点开始。②从某个起点始可能到达不了所有其它顶点，怎么办？图的遍历操作要解决的关键问题解决方案：多次调用从某顶点出发遍历图的算法。下面仅讨论从某顶点出发遍历图的算法。③因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环。④在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

图的遍历操作要解决的关键问题解决方案：附设访问标志数组visited[n]。解决方案：深度优先遍历和广度优先遍历。1.深度优先遍历

基本思想：⑴访问顶点v；⑵从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；⑶

重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。

2.广度优先遍历

基本思想：⑴访问顶点v；⑵依次访问v的各个未被访问的邻接点v1,v2,…,vk；⑶分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。一个有向图包含顶点v=