北航数据结构课件 (8)
- 格式：pdf
- 大小：957.46 KB
- 文档页数：99
文档推荐
-
北航数据结构页数:6
-
北航10秋学期《算法与数据结构》模拟题一页数:5
-
北航数据结构课件 (8)页数:99
-
数据结构北航软件技术基础课程ppt页数:50
下载文档原格式
合集下载
数据结构北航软件技术基础课程ppt
eMail:gaoliansheng@
2020/9/23
liansheng_gao@
软件技术基础
• 第零章 编程的一些问题 • 第五章 二叉树和树
• 第一章 绪 论
• 第六章 图和广义表
• 第二章 线 性 表
• 第七章 排 序
• 第三章 栈和队列
• 第八章 查 找
试，通过测试用例保证每条源代码至少执行一次
2020/9/23
第零章 程序设计的一些问题
• 需求分析-Requ综 结i述 果re： ：m由 测e专 试n门 报t的 告A测n试a人ly员s对is软件进行测试
• 概要设计-Prim12ary测 测试 试D计e划sign
• 详细设计-Detaile条 wda件lDkt：her编osu译gihg、n链接成功，完成单元测试，
2020/9/23
第零章 程序设计的一些问题
• 软件和属性
– 计算机运行中不可缺少的 – 预先编好，能为他人使用 – 商品
• 盘和软件
– 盘是软件的载体
• 软件的分类
– 应用软件 – 系统软件
2020/9/23
第零章 程序设计的一些问题
• 程序设计的几个阶段(软件工程简介)
– 六、七十年代出现了软件危机
2020/9/23
数据元素
• 数据元素是数据的基本单位。 • 它也可以再由不可分割的数据项组成
2020/9/23
数据对象 性质相同的数据元素的集合 。
例：一个班级的成绩表可以看作一个数据对象。 一个图片、声音…..
数据对象是性质相同的数据元素集合。
2020/9/23
数据结构
• 数据元素集合（也可称数据对象） • 各元素之间的关系，即结构。
北航数据结构课件 (10)
（ 1，4，6 ， 12 8，8 12 ， 6，11，… ）
例
49
temp
temp＞K[j] j=0 38 97 76 65 13 27 50
… (若干趟后)
K[j+1]=K[ j ]； j=j−1；
65
38
49
76 65
76 97
65 97
13
27
50
K[j+1]=temp;
38
49
65
76
97
核心思想
首先确定一个元素的间隔数gap。 将参加排序的元素按照gap分隔成若干个子序列 ( 即分别把那些位置相隔为gap的元素看作一个子序 列),然后对各个子序列采用 某一种排序方法 进行排 序；此后减小gap值，重复上述过程，直到gap<1。
一种减小gap的方法：
gap1 = n/2 gapi = gapi-1/2
1.时间性能 —— 排序过程中元素之间的比较次数与元素的
移动次数。 本章讨论各种排序方法的时间复杂度 时主要按照最差情况下所需要的比较次数 来进行。
2.空间性能 —— 除了存放参加排序的元素之外，排序过程
中所需要的其他辅助空间。
3.排序稳定性 —— 对于值相同的两个元素，排序前后的先后
次序不变，则称该方法为稳定性排序方法， 否则，称为非稳定性排序方法。
算 法
泡排序法的排序趟数与原始序列中数 据元素的排列有关，因此，排序的趟数为 一个范围，即[1..n-1]。
什么情况下至少排序一趟 什么情况下要排序n-1趟
O(n
2)
结论
泡排序方法比较适合于 参加排序的序列的原始状态 基本有序的情况
泡排序法是 稳定性排序方法。
北航数据结构-栈
实验报告：栈实现逻辑关键词求值17374347周京成一、问题描述逻辑关键词求值是程序设计语言中的一个基本问题，简单说就是让计算机理解并且接受高级语言描述的概念，这里的处理对象是“”，代表和；“v”代表并；，“~”代表非；“_”代表蕴含；“-”代表当且仅当；“（”，“）”左右括号；以及代表Ture 的数字1和代表False的0按照一定规则构成的合法式子，由于各种运算之间有优先级关系，所以用括号来隔开，所以使用栈来求逻辑表达式的值，这里我们最好输出的是True和False，为了方便，输入的数字只有1和0.二、数据结构：栈由于使用的是python语言，可以不用直接构造一个栈结构，直接使用列表，就可以实现栈的各类操作，比如进栈，出栈等等。
三、算法的设计和实现：1.首先建立两个列表，分别存储读入的数字和字符2.读入数字和字符，当读入右括号“）”，则要计算这个括号里面的运算结果，存储在数字列表中。
3.最后只剩下最多一个字符和两个数字，再进行讨论既可。
四、预期结果与问题预期结果和我们自己运算应该是一致的，例如（~（1_0））^((1v0)-1)=True一般可能的问题：1．在表达式最外面加括号，例如（1^0）,则需要判断字符列表是不是为空，来判断这种情况。
2.只数字列表只剩一个数字，这时候也要判断字符列表是不是空，最好再输出。
附：python代码：str1=input()list1=[]//字符列表list2=[]//数字列表for i in str1:if i.isdigit()==True:list2.append(int(i))//判断是不是数字else:if i!=")":list1.append(i)//不是右括号存储else:last=list1.pop()//右括号进行计算，各种栈操作while(last!="("):if last=="^":list2.append(list2.pop() and list2.pop())if last=="v":list2.append(list2.pop() or list2.pop())if last=="~":list2.append(not list2.pop())if last=="_":if (not list2.pop()) and (list2.pop())==True: list2.append(0)else:list2.append(1)if last=="-":if (list2.pop()+list2.pop()) in [0,2]:list2.append(1)else:list2.append(0)last=list1.pop()if list1==[]:print (bool (list2.pop()))//判断字符列表是否为空 else : //输出if list1[0]=="^":print (bool (list2.pop() and list2.pop())) if list1[0]=="v":print (bool (list2.pop() or list2.pop())) if list1[0]=="~":print (bool (not list2[0]))if list1[0]=="_":if (not list2.pop()) and list2.pop()==True : print (False )else :print (True )if list1[0]=="-":if (list2.pop()+list2.pop()) in [0,2]: print (True ) else :print (False )输出样例：中国剩余定理（简单写下）：我们只做对于有限多个质数的同余方程组。
北航--数据结构课件第1章
例
procedure MATRIX( A, B, C, n )
for i←1 to n do
------------------------- n+1
for j←1 to n do
------------------ n(n+1)
C[i, j]←0
--------------------------------- n2
课程名称：算法与数据结构
数据结构
教材名称：
《数据结构》
唐发根 编著 科学出版社
《数据结构习题与解析》
科学出版社 2002
为什么要开设 数据结构课程
目的
通过本课程的学习，运用本 课程讨论的知识更好地进行算法 设计与算法分析，掌握计算机进 行数据处理的基本原理、基本方 法和技巧，进一步提高程序设计 的水平和能力。
和最小值。 4. m MOD n 表示m对n取模。 5. 算术运算符有+、-、、/、↑(幂)。 6. 关系运算符有= 、≠、< 、> 、≤、≥ 。
7. 逻辑运算符有and、or、n因子。
用自然语言表达的算法
(1) M除以N，将余数送中间变量R； (2) 测试余数R是否等于零？
loop 语句串
forever
4. 分情况语句
5. 算法调用语句
case
：条件1： 语句串1
：条件2： 语句串2
...
...
...
...
：条件n： 语句串n
：else ： 语句串n+1
end
相当于Pascal语言 的case语句或C语言中 的switch语句
call 算法名(参数表) 变量名←算法名(参数表)
最新-数据结构7-8-9树-PPT文档资料
本章重点：二叉树的 表示和实现
15
16 物料管理
数据结构
2、二叉树
为何要重点研究每结点最多只有两个 “叉” 的树？
二叉树的结构最简单，规律性最强； 所有树都能转为唯一对应的二叉树（可以预习6.4节）。
（1）. 二叉树的定义 （2）. 二叉树的性质 （3）. 二叉树的存储结构
2019/4/22
2019/4/22 11
12 物料管理
数据结构
结点A的度：3 结点B的度：2 结点M的度：0
结点A的孩子：B，C，D 结点B的孩子：E，F 树的度：3 E K L A
叶子：K，L，F，G，M，I，J
结点I的双亲：D 结点L的双亲：E 结点B，C，D为兄弟 结点K，L为兄弟 J 树的深度：4
B
F
C
G H M
16
17 物料管理
数据结构
2、二叉树
（1）、二叉树的定义
是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的分别称 为左子树和右子树的二叉树组成。(即:空或有一个根，根有左子树、右子 树；而左右子树本身又是二叉树。）
逻辑结构： 一对二（1:2） 基本特征:① 每个结点最多只有两棵子树 （不存在度大于2的结点）； ② 左子树和右子树次序不能颠倒。
3. 深度为9的二叉树中至少有
Ａ)２9 Ｂ)２8 Ｃ)９
C 个结点。
Ｄ)２9－1
2019/4/22
20
21 物料管理
数据结构
2、二叉树
•满二叉树: 一棵深度为k 且有2k -1个结 点的二叉树。 特点：每层都 “充满”了结 点
B
A C
L
•完全二叉树: 深度为k 的、有n个 结点的二叉树，当且 仅当其每一个结点都 与深度为k 的满二叉 树中编号从1至n的结 L 点一一对应。
北航数据结构
四、结果
代码： def qsort(slist,l,r):
if l>r: return -1
t=slist[l] i=l j=r while i!=j:
while slist[j]>=t and i<j: j-=1
while slist[i]<=t and i<j: i+=1
if i<j: slist[i],slist[j]=slist[j],slist[i]
实验报告-快速排序与希尔排序
一、问题描述
快速排序实现中采用了发现逆序和交换记录位置的方法，算法最基本的思想还是划分， 即按某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一 个排序的序列。
希尔排序方法又称为缩小增量的插入排序。基本思想：先将整个待排记录序列分割成为 若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。
三算法的设计与实现
快速排序
1.设两个指针 low 和 high，初值分别为 low 和 high 2.设第一个元素关键字为 pivotkey 3.从 high 所指位置向前搜索找到第一个小于 pivotkey 的记录互相交换，然后从 low 所指位 置起向后搜索，找到第一个大于 pivotkey 的记录互相交换 4.重复 3，直至 low=high 为止。 希尔排序 （1）先取增量 d>1,把全部记录分成 d 个组 （2）对每组进行直接插入排序 （3）逐渐减少增量 d，直到为 1，所有记录在同一组，直接插入排序为止。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法 因 D.L.Shell 于 1959 年提出而得名。
代码： def qsort(slist,l,r):
if l>r: return -1
t=slist[l] i=l j=r while i!=j:
while slist[j]>=t and i<j: j-=1
while slist[i]<=t and i<j: i+=1
if i<j: slist[i],slist[j]=slist[j],slist[i]
实验报告-快速排序与希尔排序
一、问题描述
快速排序实现中采用了发现逆序和交换记录位置的方法，算法最基本的思想还是划分， 即按某种标准把考虑的记录划分为“小记录”和“大记录”，并通过递归不断划分，最终得到一 个排序的序列。
希尔排序方法又称为缩小增量的插入排序。基本思想：先将整个待排记录序列分割成为 若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行 一次直接插入排序。
三算法的设计与实现
快速排序
1.设两个指针 low 和 high，初值分别为 low 和 high 2.设第一个元素关键字为 pivotkey 3.从 high 所指位置向前搜索找到第一个小于 pivotkey 的记录互相交换，然后从 low 所指位 置起向后搜索，找到第一个大于 pivotkey 的记录互相交换 4.重复 3，直至 low=high 为止。 希尔排序 （1）先取增量 d>1,把全部记录分成 d 个组 （2）对每组进行直接插入排序 （3）逐渐减少增量 d，直到为 1，所有记录在同一组，直接插入排序为止。
希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法 因 D.L.Shell 于 1959 年提出而得名。
《数据结构的第八讲》PPT课件
13
图的定义
路径长度： 非带权图的路径长度是指此路径上边的条数。 带权图的路径长度是指路径上各边的权之和。
A
从A到F长度为 3 的路径
B
E {A,B,C,F}
CF
精选ppt
14
图的定义
连通图与连通分量：
在无向图中, 若从顶点v1到顶点v2有路径, 则称顶 点v1与v2是连通的。
如果图中任意一对顶点都是连通的, 则称此图是连 通图。
构造器方法重新构建了顶点数组和在常量 NUMVERTICES中指定数值的邻接矩阵。
既然数组是基于零的，所以数据成员 numVerts存储着 顶点列表内当前的数量以便于把列表初始设置为 0。
AddVertex方法会为顶点标签取走一个字符串参数，实 例化一个新的 Vertex对象，并且把它添加到顶点数组 内。
精选ppt
22
8.2 图的存储表示
精选ppt
23
邻接矩阵(Adjacency Matrix)
在图的邻接矩阵表示中，有一个记录各个顶点 信息的顶点表，还有一个表示各个顶点之间关 系的邻接矩阵。
设图 A = (V, E)是一个有 n 个顶点的图, 图的邻 接矩阵是一个二维数组 A.edge[n][n]，
(vi, vp1)、(vp1, vp2)、...、(vpm, vj) 应是属于E的边。
精选ppt
8
图的定义
路径的长度：
从路径中第一个顶点到最后一个顶点的边 的数量。
讨论的图对象的限制 : (1) 自身环 不讨论.
0
1
(2) 与两个特定顶点相关联的边不
能多于一条，多重图也不讨论。
1
0 2
精选ppt
9
图中，边必须是不同的。
北航多源信息融合2017课件8证据理论基础(2)
2017/3/16
多源测试信息融合
14
证据合成规则—多证据的合成
定理2：设m1,m2,…,mn是同一识别框架上的基本置信度指派， 对应的焦元分别为A1,A2,…,An，则这n条证据的组合公式
m( A) (m1 m2 mn )( A) (1 K ) 1
A 1 A2 An A
2017/3/16 多源测试信息融合 7
证据合成规则—两条证据的合成
(1) mass函数的几何表示
假设m1,m2分别是同一识别框架Θ上两条证据基本臵信度指 派，对应的焦元分别为A1, A2, …, AN 和 B1, B2, …, BM，由基 本 臵 信 度 指 派 值 m1(A1), m1(A2), …,m1(AN) 和 m2(B1), m2(B2), …,m2(BM)所确定的mass函数可用图2来表示。 将证据联合作用下产生的信任度函数称为原来信任度函数 的直和(正交和)：m1⊕m2。
求合成以后的mass值。
2017/3/16 多源测试信息融合
16
证据合成规则
解法1：根据证据合成公式，首先计算证据1和2合成后的结 果。
K1,2 m1 ( A) [m2 ( B) m2 (C )] m1 ( B) [m2 ( A) m2 (C )] m1 (C ) [m2 ( A) m2 ( B)] 0.8 (0.2 0.2) 0.1 (0.6 0.2) 0.1 (0.6 0.2) 0.48 m1 ( A)m2 ( A) 0.8 0.6 m1,2 ( A) 0.923 1 K1,2 1 0.48 m1 ( B)m2 ( B) 0.1 0.2 m1,2 ( B) 0.0385 1 K1,2 1 0.48 m (C )m2 (C ) 0.1 0.2 m1,2 (C ) 1 0.0385 1 K1,2 1 0.48
北航数据库课件
3
数据库设计概述
• 数据库设计的方法（2）
– 规范设计法：运用软件工程的思想和方法，把 整个设计过程划分为若干阶段，把复杂的大问 题分为若干相对简单的小问题，每个阶段只解 决整个设计中的部分问题。 – 规范设计法是迭代和逐步求精的过程，每一过 程完成时要进行设计分析，产生各种设计文 档，并组织评审和用户交流，如不满足要求则 进行修改。
• E-R图的组成：实体、联系、属性
– 实体：用长方形表示实体型，在框内写上实体名。 – 属性：用椭圆形表示实体的属性，并用无向边把实体 与其属性连接起来。 – 联系：用菱形表示实体间的联系，菱形框内写上联系 名。用无向边把菱形分别与有关实体相连，在无向边 旁标上联系的类型。若联系也具有属性，则属性和菱 形也用无向边连接上。
解决——同一实体的属性通常取分E-R图中属性的并，再适当调整次序。
– 实体之间的联系在不同分E-R图中呈现不同类型。
解决——根据语义加以综合或调整。
例：
A
A
A
n
l1 l2
n m
B
n p
C
l1
n
l2
p C
m
B
m
B
m
34
产品
m
组装
n
零件
编号
产品名
性能
零件数
零件号 零件名 材料号 耗用量
第四章 数据库设计
• • • • • 数据库设计概述 需求分析 概念结构设计 逻辑结构设计 物理结构设计
1
数据库设计概述
• 什么是数据库设计
– 是指对于一个给定的应用环境，设计优化的数据 库逻辑和物理结构，建立数据库及其应用系统， 使之能够有效地存储数据，满足用户的应用需求。
数据库设计概述
• 数据库设计的方法（2）
– 规范设计法：运用软件工程的思想和方法，把 整个设计过程划分为若干阶段，把复杂的大问 题分为若干相对简单的小问题，每个阶段只解 决整个设计中的部分问题。 – 规范设计法是迭代和逐步求精的过程，每一过 程完成时要进行设计分析，产生各种设计文 档，并组织评审和用户交流，如不满足要求则 进行修改。
• E-R图的组成：实体、联系、属性
– 实体：用长方形表示实体型，在框内写上实体名。 – 属性：用椭圆形表示实体的属性，并用无向边把实体 与其属性连接起来。 – 联系：用菱形表示实体间的联系，菱形框内写上联系 名。用无向边把菱形分别与有关实体相连，在无向边 旁标上联系的类型。若联系也具有属性，则属性和菱 形也用无向边连接上。
解决——同一实体的属性通常取分E-R图中属性的并，再适当调整次序。
– 实体之间的联系在不同分E-R图中呈现不同类型。
解决——根据语义加以综合或调整。
例：
A
A
A
n
l1 l2
n m
B
n p
C
l1
n
l2
p C
m
B
m
B
m
34
产品
m
组装
n
零件
编号
产品名
性能
零件数
零件号 零件名 材料号 耗用量
第四章 数据库设计
• • • • • 数据库设计概述 需求分析 概念结构设计 逻辑结构设计 物理结构设计
1
数据库设计概述
• 什么是数据库设计
– 是指对于一个给定的应用环境，设计优化的数据 库逻辑和物理结构，建立数据库及其应用系统， 使之能够有效地存储数据，满足用户的应用需求。
8 北航本科编译原理课件 张莉
1概述28.2 错误分类34错误的诊察和报告5678错误处理技术910(2) 错误局部化处理的实现（递归下降分析法） cx: 全局变量，存放错误信息。
•用递归下降分析时，如果发现错误，便将有 关错误信息（字符串或者编号）送CX，然后转出 错误处理程序； •出错程序先打印或显示出错位置以及出错信息， 然后跳出一段源程序, 直到跳到语句的右界符 (如：end）或正在分析的语法成分的合法后继符号 为止, 然后再往下分析。
北京航空航天大学计算机学院11例:条件语句分析: 有如下分析程序:if<B> then <stmt>[else< stmt >];procedure if_stmt; begin nextsym; B; if not class=‘then’ then begin cx :=‘缺then’ error; end; else begin nextsym; statement end; if class=‘else’then begin nextsym; statement; end end if_stmt; 北京航空航天大学计算机学院/*读下个单词符号*/ /*调用布尔表达式处理程序*//*错误性质送cx*/ /*调用出错处理程序*/12局部化处理的出错程序为: procedure error; begin write(源程序行号, 序号, cx) repeat nextsym; until class = ‘;’ or class = ‘end’ or class = ‘else’ end error; 跳过太多real x, 3a, a, bcd, 2fg;北京航空航天大学计算机学院 13(3) 提高错误局部化程度的方法 设 S1: 合法后继符号集 (某语法成分的后继符号) S2: 停止符号集 (跳读必须停止的符号集)进入某语法成分的分析程序时: S1:= 合法后继符号 S2:= 停止符号北京航空航天大学计算机学院14当发现错误时: error(S1,S2) procedure error(S1,S2) begin write(line_no, char_no, cx); repeat nextsym until(class in S1 or class in S2 ); end if<B> then <stmt>[else< stmt >] 若<B>有错,则可跳到then, 若<stmt>有错,则可跳到else。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
第八章图8.1 图的基本概念8.2 图的存储方法本章讨论的主要内容8.1图的基本概念一.图的定义(1) 用图形(2) 用符号(3)用语言顶点v i 与v j 是这条边的两个邻接点。
关于一条边或弧的表示(vi , v j ) 或<v i , v j >v i v j v iv j顶点偶对其中V 2 = { v 1, v 2, v 3, v 4 }E 2 = { <v 1,v 2>, <v 2,v 1>,<v 2,v 3>, <v 4,v 3> }G 1=(V 1, E 1)对于（vi ,v j)∈E,必有（vj,vi)∈E，并且偶对中顶点的前后顺序无关。
若<vi ,v j>∈E是顶点的有序偶对。
无向图有向图网(络)与边有关的数据称为,边上带权的图称为。
权网络v1v2v3v4无向图有向图网(络)二.图的分类1.顶点的度对于有向图而言, 有:顶点的:以顶点v i 为出发点的边的数目,记为OD(v i )。
顶点的:以顶点v i 为终止点的边的数目,记为ID(v i )。
TD(v i ) = OD(v i ) + ID(v i )出度入度v 1v 2v 3v4具有n 个顶点的有向图最多有n(n -1)条边。
具有n 个顶点的无向图最多有n(n -1)/2条边。
对于具有n 个顶点,e 条边的图,有e = ∑TD(v i )ni=112边的数目达到最大的图称为。
边的数目达到或接近最大的图称为，否则,称为。
完全图稠密图稀疏图DCEBAA, C, D, E (第2条路径)A, B, E (第1条路径)P(A, E):出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。
不带权的图的路径长度是指路径上所经过的边的数目，带权图的路径长度是指路径上经过的边上的权值之和。
子图3.对于图G=(V,E) 与G´=(V´,E´), 若有V´⊆V,E´⊆E,则称G´为G的一个子图。
G(1)无向图的连通4.图的连通连通分量——无向图中的极大连通子图。
v 9v 1v 2v 4v 3v 5v 6v 7v 1v 2v 4v 3v 1v 2v 4v 3v 5v 6v 9v 72个连通分量连通图非连通图无向图中顶点v i 到v j 有路径,则称顶点v i 与v j 是连通的。
若无向图中任意两个顶点都连通, 则称该无向图是连通的。
若有向图中顶点v i 到v j 有路径,并且顶点v j到v i 也有路径，则称顶点v i 与v j 是连通的。
若有向图中任意两个顶点都连通，则称该有向图是强连通的。
(强)连通图非连通图强连通分量——有向图中的极大强连通子图。
强连通分量(2)有向图的连通包含具有n个顶点的连通图G的全部n个顶点,仅包含其n-1条边的极小连通子图称为G的一个生成树。
5.生成树v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4v1v2v3v4…v1v2v3v4GG的生成树1. 带自身环的图2. 多重图8.2图的存储方法1. 定义一个一维数组VERTEX[0..n -1]存放图中所有顶点的数据信息(若顶点信息为1,2,3,…,此数组可略)。
1当顶点v i 到顶点v j 有边时A[i][j]=0当顶点v i 到顶点v j 无边时{对于带权的图, 有w ij 当顶点v i 到v j 有边,且边的权为w ijA[i][j]=当顶点v i 到顶点v j 无边时{∞2. 定义一个二维数组A[0..n -1,0..n -1]存放图中所有顶点之间关系的信息(该数组被称为),有邻接矩阵0 1 1 11 0 1 11 1 0 11 1 1 0A 1 =∝4 ∝∝6 ∝7 ∝∝∝∝∝∝∝8∝A 2 =v 1v 2v 3v 4VERTEX1[0..3]0123v 1v 2v 3v 4VERTEX2[0..3]0123(1) 无向图的邻接矩阵一定是一个对称矩阵。
(2) 不带权的有向图的邻接矩阵一般是稀疏矩阵。
(3) 无向图的邻接矩阵的第i 行(或第i 列)非0 或非∝元素的个数为第i 个顶点的度数。
(4) 有向图的邻接矩阵的第i 行非0或非∝元素的个数为第i 个顶点的出度;第i 列非0或非∝元素的个数为第i 个顶点的入度。
v 1v4v 2v 30 1 1 11 0 1 11 1 0 11 1 1 0v 1v 2v 3v 4（无向图）0 1 0 01 0 1 00 0 0 00 0 1 0v 1v 2v 3v 4（有向图）特点其中,vertex 域存放某个顶点的数据信息;link 域存放某个链表中第一个结点的地址。
其中,next 域为指针域;weight 域为权值域(若图不带权,则无此域);adjvex 域存放以第i 个顶点为出发点的一条边的另一端点在头结点数组中的位置。
n 个头结点之间为一数组结构。
二.邻接表存储方法1. 每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为。
其构造为顶点结点建立n 个线性链表存储该图。
核心思想:2. 第i 个链表中的每一个链结点(称之为)表示以第i 个顶点为的一条边;边结点的构造为边结点出发点0 1 2 3v1v2v3v40123v 1v 2v 3v 46特点(((123123终止点第i个链表中的每一个链结点(称之为边结点)表示以第i个顶点为的一条边;出发点对于邻接表…三.有向图的十字链表存储方法( 略)四.无向图的多重邻接表存储方法( 略)以无向图为例8.3图的遍历从图中某个指定的顶点出发, 按照某一原则对图中所有顶点都访问一次, 得到一个由图中所有顶点组成的序列, 这一过程称为。
图的遍历出发点v 1v 2v 4v 7v 9v 5v 3v 6v 8012345678遍历序列列队采用邻接表存储该图：O(n+e)。
采用邻接矩阵存储该图：O(n２)。
一.什么是最小生成树v1v 2v3v48.4最小生成树v 1v 2v 3v 4…295带权连通图中，总的权值之和最小的带权生成树为。
最小生成树也称最小代价生成树,或最小花费生成树。
最小生成树二.求最小生成树依次在G 中选择一条一个顶点仅在V 中,另一个顶点在U 中,并且权值最小的边加入集合TE ,同时将该边仅在V 中的那个顶点加入集合U .重复上述过程n –1次,使得U=V ,此时T 为G 的最小生成树。
普里姆(Prim)方法克鲁斯卡尔(Kruskal)方法设G=(V, GE)为具有n 个顶点的带权连通图;T=(U, TE)为生成的最小生成树, 初始时,TE=空, U={v}, v∈V 。
普里姆(Prim )算法v 4v 2v 6v5v 3v 116115691814192220G :{ v 1, v 2, v 3, v 4, v 5, v 6 }V =(v 1, v 2)16,(v 1, v 3)20GE=(v 1, v 4)19 ,(v 2, v 3)11(v 2, v 5)6 ,(v 2, v 6)5(v 3, v 4)22 ,(v 3, v 5)14(v 4, v 5)18 ,(v 5, v 6)9T :U = { v 1}TE = { }(v 1, v 2)16,v 2(v 2, v 6)5,v 6(v 2, v 5)6,v 5(v 2, v 3)11,v 3,v 4(v 4, v 5)18克鲁斯卡尔(Kruskal )方法从G 中选择一条当前未选择过的、且边上的权值最小的边加入TE ，若加入TE 后使得T 未产生回路,则本次选择有效，如使得T 产生回路,则本次选择无效,放弃本次选择的边。
重复上述选择过程直到TE 中包含了G 的n -1条边，此时的T 为G 的最小生成树。
基本思想T=(U, TE)G=(V, GE)初始时,TE=空U=VG T (连通图)(生成树)v 4v 2v 6v 5v 3v 1569放弃111416放弃18克鲁斯卡尔(Kruskal)方法以1~n 分别代表n 个顶点,采用邻接矩阵存储该图,有W ij 当顶点v i 到顶点v j 有边,且权为W ijA[i][j]= ∞当顶点v i 到顶点v j 无边时0当v i =v j 时{设出发顶点为v (通常称为源点)。
1. 图的存储三.解决问题所需要确定的数据结构3. 设置数组dist[0..n -1] 分别记录源点v 到图中各顶点的最短路径的路径长度，其中，dist[i]记录源点到顶点i 的最短路径的长度。
初始时，dist 数组的值为邻接矩阵第v 行的n 个元素值。
（i =0,1, 2, …, n -1 ）4. 设置数组path[0..n -1] 分别记录源点v 到图中各顶点的最短路径所经过的顶点序列，其中,path[i]记录源点到顶点i 的路径。
初始时，path[i]={v }, i =0,1, 2, …, n -1）2. 设置一个标志数组s[0..n -1]记录源点v 到图中哪些顶点的最短路径已经找到。
有：1表示源点到顶点i 的最短路径已经找到s[i] =0表示源点到顶点i 的最短路径尚未找到初始时，s[v]=1, s[i]=0 （i =0,1, 2, …, n -1 i ≠v ）{1. 确定dist 、s 、path 三个数组的初值。
2.利用s 数组与dist 数组在那些尚未找到最短路径的顶点中确定一个与源点v 最近的顶点u ,并置s[u]为1,同时将顶点u 加入path[u]。
3. 根据顶点u 修改源点到所有尚未找到最短路径的顶点的路径长度。
即1) 将源点v 到顶点u 的(最短)路径长度分别加到源点v 通过顶点u 可以直接到达、且尚未找到最短路径那些的顶点的路径长度上。
若加后的长度小于原来v 到某顶点r 的路径长度，则用加后的长度替换原来的长度，否则，不作替换。
2)若替换，将源点v 到顶点u 的路径(最短路径)上经过的所有顶点替换path[r]。
4. 重复上述过程的第2至第3步n –1次。
s[i]=0；s[v]=1；path[i]={ v }；四.算法(用自然语言表达)for(i=0;i<n;i++){dist[i]=A[v][i]；}dist数组0 10 2 ∝∝∝∝s数组10 0 0 0 0 011111110 10 2 ∝∝∝∝10 0 ∝∝ 1 ∝∝2 ∝0 2 ∝11 ∝∝∝ 2 0 4 6 ∝∝ 1 ∝ 4 0 ∝7∝∝11 6 ∝0 3∝∝∝∝7 3 0邻接矩阵path数组132456710221147631最小代价生成树源点思考3 26251与源点有关相同不v 4v 2v 6v 5v3v 116115691814192220最小生成树结论•••一.什么是AOV 网一个建筑工程的施工流程…8.6 AOV 网与拓扑排序。