第二章部分习题参考答案
1.证明下列结论:
1)在一个无向图中,如果每个顶点的度大于等于2,则该该图一定含有圈; 2)在一个有向图D 中,如果每个顶点的出度都大于等于1,则该图一定含有一个有向圈。
1)证明:设无向图最长的迹,10k V V V P =每个顶点度大于等于2,故存在与1V 相异的点'V 与0V 相邻,若,'P V ?则得到比P 更长的迹,与P 的取法矛盾。因此,P V ∈',是闭迹,从而存在圈.0'10V V V V
(定义:迹是指边不重复的途径,而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径,起点和终点重合的迹称为闭迹,顶点不重复的闭迹称为圈。)
2)证明:设有向图最长的有向迹,10k V V V P =每个顶点出度大于等于1,故存在'V 为k V 的出度连接到点,'V V k 成为一条有向边,若,'P V ?则得到比P 更长的有向迹,与P 矛盾,因此必有P V ∈',从而该图一定含有有向圈。
2.设D 是至少有三个顶点的连通有向图。如果D 中包含有向的Euler 环游(即是通过D 中每条有向边恰好一次的闭迹),则D 中每一顶点的出度和入度相等。反之,如果D 中每一顶点的出度与入度都相等,则D 一定包含有向的Euler 环游。这两个结论是正确的吗?请说明理由。如果G 是至少有三个顶点的无向图,则G 包含Euler 环游的条件是什么?
证明:1)若图D 中包含有向Euler 环游,下证明每个顶点的入度和出度相等。
如果该有向图含有Euler 环游,那么该环游必经过每个顶点至少一次,每经过一次,必为“进”一次接着“出”一次,从而入度等于出度。从而,对于任意顶点,不管该环游经过该顶点多少次,必有入度等于出度。
2)若图D 中每个顶点的入度和出度相等,则该图D 包含Euler 环游。证明如下。
对顶点个数进行归纳。
当顶点数|v(D)|=2时,因为每个点的入度和出度相等,易得构成有向Euler 环游。
假设顶点数|v(D)|=k 时结论成立,则
当顶点数|v(D)|=k + 1时,任取v ∈v(D).设S={以v 为终点的边},K={以v 为始点的边},因为v 的入度和出度相等,故S 和K 中边数相等。记G=D-v.对G 做如下操作:
任取S 和K 中各一条边21e e 、,设在D 中v v e 11=,22vv e =,则对G 和S 做如下操作 21v v G G +=, }{2e S S -=,重复此步骤直到S 为空。这个过程最终得到的G 有k 个顶点,且每个顶点的度与在G 中完全一样。由归纳假设,G 中存在有向Euler 环游,设为C 。在G 中从任一点出发沿C 的对应边前行,每当遇到上述添加边v1v2时,都用对应的两条边e1,e2代替,这样可以获得有向Euler 环游。
3)G 是至少有三个顶点的无向图,则G 包含Euler 环游等价于G 中无奇度顶点。(即任意顶点的度为偶数)。
3.设G 是具有n 个顶点和m 条边的无向图,如果G 是连通的,而且满足m = n-1,证明G 是树。
证明:思路一:
只需证明G 中无圈。
若G 中有圈,则删去圈上任一条边G 仍连通。而每个连通图边数e>=n(顶点数) – 1,但删去一条边后G 中只有n-2条边,此时不连通,从而矛盾,故G 中无圈,所以G 为树。
思路二:
当2=n 时,112=-=m ,两个顶点一条边且连通无环路,显然是树。 设当)2,(1≥∈-=k N k k n 时,命题成立,则
当k n =时,因为G 连通且无环路,所以至少存在一个顶点1V ,他的度数为1,设
该顶点所关联的边为).,(211V V e =那么去掉顶点1V 和1e ,便得到了一个有k-1个顶点的连通无向无环路的子图'G ,且'G 的边数1'-=m m ,顶点数1'-=n n 。由于m=n-1,所以11)1(1''-=--=-=n n m m ,由归纳假设知,'G 是树。
由于G 相当于在'G 中为2V 添加了一个子节点,所以G 也是树。 由(1),(2)原命题得证。
4. 假设用一个n n ?的数组来描述一个有向图的n n ?邻接矩阵,完成下面工作:
1)编写一个函数以确定顶点的出度,函数的复杂性应为);(n Θ: 2)编写一个函数以确定图中边的数目,函数的复杂性应为);(2n Θ 3)编写一个函数删除边),(j i ,并确定代码的复杂性。
解答:(1)邻接矩阵表示为n n a ?,待确定的顶点为第m 个顶点m v
int CountV out(int *a,int n,int m){ int out = 0; for(int i=0;i (2)确定图中边的数目的函数如下: int EdgeNumber(int*a,int n){ int num =0; for(int i=0;i (3)删除边(i , j )的函数如下: void deleteEdge(int *a ,int i ,int j){ if(a[i-1][j-1]==0) return; a[i-1][j-1] = 0; return; } 代码的时间复杂性为Θ(1) 5.实现图的D-搜索算法,要求用SPARKS语言写出算法的伪代码,或者用一种计算机高级语言写出程序。 解:D搜索算法的基本思想是,用栈代替BFS中的队列,先将起始顶点存入栈中,搜索时,取出栈顶的元素,遍历搜索其相邻接点,若其邻接点还未搜索,则存入栈中并标记,遍历所有邻接点后,取出此时栈顶的元素转入下一轮遍历搜索,直至栈变为空栈。 Proc DBFS (v) //从顶点v开始,数组visited标示顶点被访问的顺序; PushS(v , S); //首先访问v,将S初始化为只含有一个元素v的栈 count :=count +1; visited[v] := count; While S 非空do u :=PullHead(S); //区别于队列count :=count +1; visited[w] := count; for 邻接于u的所有顶点w do if s[w] = 0 then PushS(w,S); //将w存入栈S s[w]:= 1; count :=count +1; visited[w] := count; end{if} end{for} end{while} end{DBFS} 注:PushS(w,S)将w存入栈S; PullHead(S)为取出栈最上面的元素,并从栈中删除 Proc DBFT(G,m) //m为不连通分支数 count:=0 ;计数器,标示已经被访问的顶点个数 for i to n do s[i]:=0; //数组s用来标示各顶点是否曾被搜索,是则标记为1,否则标记为0; end{for} for i to m do //遍历不连通分支的情况 if s[i]=0 then DBFS (i); end{if} end{for} end{DBFT} 6.下面的无向图以邻接链表存储,而且在关于每个顶点的链表中与该顶点相邻的顶点是按照字母顺序排列的。试以此图为例描述讲义中算法DFNL 的执行过程。 邻接链表 A->B->E|0 B->A->C|0 C->B->D->E|0 D->C|0 E->A->C->F->G|0 F->E->G|0 G->E->F|0 解:初始化 数组DFN:=0, num=1; A 为树的根节点,对A 计算DFNL(A,null), DFN(A):=num=1; L(A):=num=1; num:=1+1=2。 从邻接链表查到A 的邻接点B , 因为DFN(B)=0,对B 计算DFNL(B,A) DFN(B):= num=2; L(B):=num=2; num :=2+1=3。 查邻接链表得到B 的邻接点A ,因为DFN(A)=1≠0, 但A=A,即是B 的父节点,无操作。 接着查找邻接链表得到B 的邻接点C , 因为DFN(C)=0,对C 计算DFNL(C,B) DFN(C):= num=3; L(C):=num=3; num:=3+1=4。 查找C 的邻接点B ,因为DFN(B)=1≠0, 但B=B,即是C 的父节点,无操作。 接着查找邻接链表得到C 的邻接点D , 因为DFN(D)=0,对D 计算 DFNL(D,C), DFN(D):= num=4; L(D):=num=4; num:=4+1=5。 查找得D 邻接点C ,而DFN(C)=3≠0,但C=C ,为D 的父节点, L(D)保持不变。 D 的邻接链表结束,DFNL(D,C)的计算结束。 返回到D 的父节点C ,查找邻接链表得到C 的邻接点E , 5 5 因为DFN(E)=0,对E计算DFNL(E,C), DFN(E):=num=5; L(E):=num=5; num:5+1=6; 查找得E邻接点A,因DFN(A)=1≠0,又A≠C,变换L(E)=min(L(E),DFN(A))=1。 查找得E邻接点C,因DFN(C)=3≠0,但C=C,无操作。 查找得E邻接点F,因DFN(F)=0, 对F计算DFNL(F,E), DFN(F):=num=6; L(F):=num=6; num:=6+1=7; 查找得F邻接点E,因DFN(E)=5≠0,但E=E,无操作。 查找得F邻接点G,因DFN(G)=0, 对G计算DFNL(G,F), DFN(G):=num=7; L(G):=num=7; num=7+1=8; 查找G邻接点E,因DFN(E)=5≠0,又E≠F,L(G)=min(L(G),DFN(E))=5 查找得G邻接点F,因DFN(F)=6≠0,但F=F,无操作。 G的邻接链表结束,DFNL(G,F)的计算结束。 L(F):=min(L(F),L(G))=min(6,5)=5 F的邻接链表结束,DFNL(F,E)的计算结束。 L(E):=min(L(E),L(F))=min(1,5)=1 E邻接链表结束,DFNL(E,C)计算结束。 L(C):=min(L(C),L(E))=min(3,1)=1 C的邻接链表结束,DFNL(C,B)计算结束。 L(B):=min(L(B),L(C))=min(2,1)=1 查找B的邻接链表结束,DFNL(B,A)计算结束。 L(A):=min(L(A),L(B))=1 查找得A的邻接点E,因DFN(E)=0,又E≠null,则L(A)=min(L(A),DFN(E))=1 查找A的邻接链表结束,DFNL(A,null)计算结束。 最终结果为:深索数DFN,与最低深索数L如下 DFN(A)=1,DFN(B)=2,DFN(C)=3,DFN(D)=4,DFN(E)=5,DFN(F)=6,DFN(G)=7 L(A)=1; L(B)=1; L(C)=1; L(D)=4; L(E)=1; L(F)=5;L(G)=5. 程序2-3-1对图2-3-5的执行过程 开始 DFNL (A,*) DFN(A):=1; L(A):=1; num:=2; ∵ DFN(B)=0, ∴ DFNL (B,A) DFN(B):=2; L(B):=2; num:=3; ∵ DFN(A)=1≠0, 但A=A, ∴不做任何事情 ∵ DFN(C)=0, ∴ DFNL (C,B) DFN(C):=3; L(C):=3; num:=4; ∵ DFN(B)=2≠0, 但B=B, ∴不做任何事情 ∵ DFN(D)=0, ∴ DFNL (D,C) DFN(D):=4; L(D):=4 > DFN( C); num:=5; ∵ DFN(C)=3≠0, 但C=C, ∴不做任何事情 ∵ DFN(E)=0, ∴ DFNL (E,C) DFN(E):=5; L(E):=5 > DFN( C); num:=6; 弹出(C,E )边 ∵ DFN(C)=3≠0, 但C=C, ∵ DFN(F)=0, ∴ DFNL (F,C) DFN(F):=6; L(F):=6; num:=7; ∵ DFN(A)=1≠0, A ≠C, ∴ L(F):=min{6,1}=1; ∵ DFN(C)=3≠0, 但C=C, ∵ DFN(G)=0, ∴ DFNL (G,F) DFN(G):=7; L(G):=7; num:=8; ∵ DFN(F)=6≠0, 但F=F, ∵DFN(H)=0, ∴DFNL(H,G) DFN(H):=8; L(H):=8 > DFN(G); num:=9; 弹出(G,H)边 ∵DFN(G)=7≠0, 但G=G, ∵DFN(I)=0, ∴DFNL(I,G) DFN(I):=9; L(I):=9; num:=10; ∵DFN(F)=6≠0, F≠G, ∴L(I):=min{9,6}=6; ∵DFN(G)=7≠0, 但G=G, ∵DFN(J)=0, ∴DFNL(J,I) DFN(J):=10; L(J):=10; num:=11; ∵DFN(F)=6≠0, F≠I, ∴L(J):=min{10,6}=6; ∵DFN(G)=7≠0, G≠I, ∴L(J):=min{6,7}=6; ∵DFN(I)=9≠0, 但I=I, L(I):=min{6,6}=6; L(G):=min{7,6}=6 ≥DFN(F)弹出(J,G), (J,F), (I,J), (I,F), (G,I), (F,G) 边 L(F):=min{1,6}=1; L(C ):=min{3,1}=1; L(B):=min{2,1}=1≥DFN(A)弹出(F,A), (C,F), (B,C), (A,B) 边 #include 实验报告 课程名称数据结构 实验项目实验三--创建一个二叉树并输出三种遍历结果 系别■计算机学院 _________________ 专业_______________ 班级/学号_____________ 学生姓名___________ 实验日期— 成绩______________________________ 指导 教师 实验题目:实验三创建一个二叉树并输出三种遍历结果 实验目的 1)掌握二叉树存储结构; 2)掌握并实现二叉树遍历的递归算法和非递归算法; 3)理解树及森林对二叉树的转换; 4)理解二叉树的应用一哈夫曼编码及WPL计算。 实验内容 1)以广义表或遍历序列形式创建一个二叉树,存储结构自选; 2)输出先序、中序、后序遍历序列; 3)二选一应用题:1)树和森林向二叉树转换;2)哈夫曼编码的应用问题。 题目可替换上述前两项实验内容) 设计与编码 1)程序结构基本设计框架 (提示:请根据所选定题目,描述程序的基本框架,可以用流程图、界面描述图、 框图等来表示) 2)本实验用到的理论知识遍历二叉树,递归和非递归的方法 (应用型 (提示:总结本实验用到的理论知识,实现理论与实践相结合。总结尽量简明扼要,并与本次实验密切相关,要求结合自己的题目并阐述自己的理解和想法) 3) 具体算法设计 1) 首先,定义二叉树的存储结构为二叉链表存储,每个元素的数 据类型Elemtype,定义一棵二叉树,只需定义其根指针。 2) 然后以递归的先序遍历方法创建二叉树,函数为CreateTree(),在输 入字符时要注意,当节点的左孩子或者右孩子为空的时候,应当输入一 个特殊的字符(本算法为“ #”),表示左孩子或者右孩子为空。 3) 下一步,创建利用递归方法先序遍历二叉树的函数,函数为 PreOrderTreeQ,创建非递归方法中序遍历二叉树的函数,函数为 InOrderTree(),中序遍历过程是:从二叉树的根节点开始,沿左子树 向下搜索,在搜索过程将所遇到的节点进栈;左子树遍历完毕后,从 栈顶退出栈中的节点并访问;然后再用上述过程遍历右子树,依次类 推,指导整棵二叉树全部访问完毕。创建递归方法后序遍历二叉树的 函数,函数为LaOrderTree()。 (提示:该部分主要是利用C、C++ 等完成数据结构定义、设计算法实现各种操作,可以用列表分步形式的自然语言描述,也可以利用流程图等描述) 4) 编码 #include 《临床科研设计》模拟试题 —省住院医师培训必修课统一考试 试题1: 一、单项选择题(10分) 1、在下列研究设计方法中,按临床科研设计论证强度排列,一般认为最强的是:C A、前瞻性队列研究 B、病例对照研究 C、随机对照研究 D、横断面调查 2、在科研选题、立题时,不必考虑下列哪项因素:C A、可行性 B、价值和水平 C、临床阳性结果 D、临床意义 3、在选研究方法时应当考虑的因素中,最重要的是:A A、科研目的 B、可行性 C、样本量 D、创新性 4、研究设计中要估计样本量,主要是因为:B A、样本量过小容易犯第二类错误 B、样本量过小容易犯第一类错误 C、样本量过大会影响结果的准确性 D、样本越大,可行性越差 5、研究对象分组方法设计最重要的指导思想是:A A、两组研究前的基线状况一致 B、两组研究条件要一致 C、两组分组方法要一致 D、两组研究对象年龄、性别要一致 6、分层分析可控制 C A、选择偏倚 B、信息偏倚 C、混杂偏倚 D、信息偏倚和混杂偏倚 7、用住院病人作研究对象容易发生:A A、选择偏倚 B、信息偏倚 C、混杂偏倚 D、选择偏倚和混杂偏倚 8、采用拉丁方设计具有如下要求,但不包括:D B A、三个研究因素 B、水平数可以不等 C、利用标准方 D、不考虑交互作用 9、三个因素各两水平,若采用析因分析设计时,至少要设的组数:B C A、5 B、6 C、8 D、9 10、被认为是论文核心部分的是:B A、材料与方法 B、结果 C、讨论 D、摘要 二、填空题(10分) 1、临床科研选题原则有:创新性原则、科学性原则、可行性原则、需要性原则、效益性原则。 2、临床科研设计的原则有:随机化原则、盲法原则、对照原则、重复原则。 3、临床科研设计的要素是:处理因素、受试对象、试验效应。 三、简答题(28分) 1、简述临床科研的基本步骤。五步骤:科研选题,科研设计,实施方法,设计分析和总结归纳。 2、为什么说偏倚是系统误差,它具有哪些基本属性?系统误差是在调查或测量时,由于某种确定的原因,如实验方法不当、仪器不准等原因造成的,使调查结果偏大或偏小。偏倚是指医学研究中的系统误差以及结果解释、推论中的片面性,使得研究结果与真实性值出现偏倚性的差异。按偏倚的性质分三大类:选择偏倚、信息偏倚、混杂偏倚 3、简述随机化抽样的常用类型以及实施随机化的意义。常用类型有单纯随机抽样、系统随机抽样、分层抽样和整群抽样方法。意义:随机化抽样的最大优点是在根据样本资料推论总体时,可用概率的方式客观地测量推论值的可靠程度,从而使这种推论建立在科学的基础上。 4、常用的诊断试验真实性的评价指标有哪些,各评价的是诊断试验的哪方面?一灵敏度。灵敏度表示试验方法对疾病的检出能力。二特异度。特异度表示试验方法对无病的检出能 树与图的简单遍历算法 发表时间:2019-01-14T09:56:22.797Z 来源:《科技新时代》2018年11期作者:闵俊齐 [导读] 树与图是两种重要的数据结构,而树可以说是一种特殊的图,它的两两结点之间存在唯一简单路径。 重庆第二外国语学校重庆 400065 摘要:树与图是两种重要的数据结构,而树可以说是一种特殊的图,它的两两结点之间存在唯一简单路径。利用其特殊性质,人们创造了许多算法来处理数据结构问题和程序调用问题。而树与图的遍历算法也是数据结构中重要的算法之一。本文从树与图的概念出发,简单的介绍了树与图的主要存储方式,并重点对二叉树的简单遍历算法、哈夫曼树的生成和图的深度优先遍历及广度优先遍历做出了介绍。 关键词:数据结构;二叉树;图;遍历算法 1.树与图的概念 树是一种数据结构,是由n(n≥0)个结点构成的具有明显层次关系的有限集合。一棵树一般由一个根节点和若干个子结点构成。结点与结点之间具有明显的并列或层次关系,这种层次关系称为父子关系。在一棵树中,没有父结点的结点被称为根结点。树有几个重要的概念,以下做出简单的介绍——树的度:某个结点拥有的子树的数量称为这个结点的度,度为零的结点也叫做叶结点,而度不为零的结点叫做分支结点。树的深度:一棵树的根结点的层次为1,其他结点的层次是其父结点的层次加1。一棵树里最大的层次的值被称为这棵树的深度。树有无序树,有序树,二叉树等。其中二叉树是每个结点最多有两个子结点的树,每个结点的子树通常被称为“左子树”和“右子树”,故二叉树中每个结点的度的最大值为2,而又有左右之分,二叉树中结点的次序不能任意颠倒。除最后一层的叶结点没有子结点外,其余每一层的每个结点都具有两个子结点的二叉树称为满二叉树。如果存在一个深度为h的二叉树,它的除h层外其余各层(1~h-1)的结点数都达到了最大值,并且它的第h层的结点全部集中在树的左边,这种二叉树就被称为完全二叉树。完全二叉树是由满二叉树引申出来的,它是一种效率很高的数据结构。本文后部分将会介绍二叉树的简单遍历算法。 图由若干个顶点组成的有限非空集合和各个顶点的边构成,通常表示为G(V,E),其中G表示一个图,V是图G中顶点的集合,E是图G中边的集合。图数据结构主要研究形状和图形数据元素之间的关系。它必须反映数据所对应的元素之间的几何关系和拓扑关系。图依照边的方向可分为有向图和无向图。有向图由顶点和弧构成。弧有弧尾和弧头,带箭头的一边称为弧头。图结构与树结构相比较,图中的任意两个元素都有可能相关。而对某个结点而言,树下层可能有多个元素,上层只有能一个元素,复杂度比树大[1]。 2二叉树与图的储存方式 2.1二叉树的储存方式 二叉树有两种储存方式:顺序存储和链式存储。 顺序储存就是按照完全二叉树的结点层次顺序存储的一种只适用于完全二叉树的储存方式,且在最坏的情况下,k个结点的单支数却只需要长度的 -1的一维数据。这种储存需要一个完全连续地址,所以会占用许多的储存空间。 在二叉树中,每个结点信息一般都由一下几个部分构成:该结点的数据元素(Data)、指向左子树的指针(L child)和指向右子树的指针(R child)。利用指针,我们可以很好的存储二叉树。若使用二叉链表,每个结点的结构如图1(a)所示。一般可以(L,D,R)来表示。在三叉链表中,可表示每个结点的父结点,结构如图1(b)所示。一般可以(L,D,P,R)来表示[5]。链式储存不需要完全连续地址,节约储存空间[2]。 图2 3.二叉树的遍历算法及哈夫曼树的生成 3.1二叉树的遍历算法 遍历,是指用某种方法沿着某条路对每一个元素做一且仅一次访问,它是二叉树的重要运算之一。二叉树的主要有三种访问方式:先序遍历、中序遍历、后序遍历。具体实现过程如下: 二叉树的先序遍历: 递归算法: void PreorderTraverse(BTNode *T) { if (T!=NULL) { visit(T->data) ; /* 访问根结点*/ PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; } } 非递归遍历: 设T是指向二叉树根结点的指针变量,非递归算法是: 若二叉树为空,则返回;否则,令p=T; ⑴访问p所指向的结点; ⑵q=p->Rchild ,若q不为空,则q进栈; ⑶p=p->Lchild ,若p不为空,转(1),否则转(4); ⑷退栈到p ,转(1),直到栈空为止。 ---------------------------------------------------------------------------------------------------------------------- #define MAX_NODE 50 void PreorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ; if (T==NULL) printf(“Binary Tree is Empty!\n”) ; else { do { visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ; if (p==NULL) { p=stack[top] ; top-- ; } } while (p!=NULL) ; } } 合肥学院 计算机科学与技术系 课程设计报告 2013~2014学年第二学期 课程数据结构与算法 课程设计名称图的深度优先遍历算法的实现 学生姓名陈琳 学号1204091022 专业班级软件工程 指导教师何立新 2014 年9 月 一:问题分析和任务定义 涉及到数据结构遍会涉及到对应存储方法的遍历问题。本次程序采用邻接表的存储方法,并且以深度优先实现遍历的过程得到其遍历序列。 深度优先遍历图的方法是,从图中某顶点v 出发: (1)访问顶点v ; (2)依次从v 的未被访问的邻接点出发,对图进行深度优先遍历;直至图中和v 有路径相通的顶点都被访问; (3)若此时图中尚有顶点未被访问,则从一个未被访问的顶点出发,重新进行深度优先遍历,直到图中所有顶点均被访问过为止。 二:数据结构的选择和概要设计 设计流程如图: 图1 设计流程 利用一维数组创建邻接表,同时还需要一个一维数组来存储顶点信息。之后利用创建的邻接表来创建图,最后用深度优先的方法来实现遍历。 图 2 原始图 1.从0开始,首先找到0的关联顶点3 2.由3出发,找到1;由1出发,没有关联的顶点。 3.回到3,从3出发,找到2;由2出发,没有关联的顶点。 4.回到4,出4出发,找到1,因为1已经被访问过了,所以不访问。 所以最后顺序是0,3,1,2,4 三:详细设计和编码 1.创建邻接表和图 void CreateALGraph (ALGraph* G) //建立邻接表函数. { int i,j,k,s; char y; EdgeNode* p; //工作指针. printf("请输入图的顶点数n与边数e(以逗号做分隔符):\n"); scanf("%d,%d",&(G->n),&(G->e)); scanf("%c",&y); //用y来接收回车符. for(s=0;s 数据结构B实验报告 一、实验内容 图的生成、图的遍历 二、实验目的 掌握图的基本存储结构 掌握图的相关算法 掌握图的两种遍历方法 三、功能 本实验要求实现以下功能: 1.以邻接矩阵或者邻接表作为存储结构建立一个无向图。 2.深度优先搜索该无向图,输出遍历序列。 3.广度优先搜索该无向图,输出遍历序列。 四、主要代码 #include 实验课题一:将下图中得二叉树用二叉链表表示: 1用三种遍历算法遍历该二叉树,给出对应得输出结果; 2写一个函数对二叉树搜索,若给出一个结点,根据其就是否属于该树,输出true或者f alse。 3写函数完成习题4、31(C++版)或4、28(C版教科书)。 #include "stdio、h" #include”malloc、h" typedefstruct BiTNode { char data; structBiTNode *lchild,*rchild; }BiTNode,*BiTree; BiTree Create(BiTreeT) { char ch; ch=getchar(); if(ch=='#’) T=NULL; else { T=(BiTNode *)malloc(sizeof(BiTNode)); T-〉data=ch; T->lchild=Create(T—〉lchild); T—〉rchild=Create(T-〉rchild); } return T; } int node(BiTree T) { int sum1=0,a,b; ?if(T) { if(T!=NULL) ??sum1++; ?a=node(T->lchild); sum1+=a; b=node(T—>rchild); sum1+=b; ?} return sum1; } int mnode(BiTree T) { ?int sum2=0,e,f; if(T) { ?if((T->lchild!=NULL)&&(T-〉rchild!=NULL))?sum2++; ?e=mnode(T-〉lchild); sum2+=e; f=mnode(T-〉rchild); sum2+=f; ?} return sum2; } void Preorder(BiTree T) { if(T) { printf("%c”,T->data); Preorder(T—>lchild); Preorder(T-〉rchild); } } int Sumleaf(BiTree T) { int sum=0,m,n; if(T) { if((!T-〉lchild)&&(!T-〉rchild)) sum++; m=Sumleaf(T->lchild); sum+=m; n=Sumleaf(T—>rchild); sum+=n; } return sum; } 武汉东湖学院 实验报告 学院:计算机科学学院—专业计算机科学与技术2016年11月18日 1.实验目的 (1)了解邻接矩阵存储法和邻接表存储法的实现过程。 (2)了解图的深度优先遍历和广度优先遍历的实现过程。 2.实验内容 1.采用图的邻接矩阵存储方法,实现下图的邻接矩阵存储,并输出该矩阵 2.设计一个将第1小题中的邻接矩阵转换为邻接表的算法,并设计一个在屏幕上显示邻接表的算法 3.实现基于第2小题中邻接表的深度优先遍历算法,并输出遍历序列 4.实现基于第2小题中邻接表的广度优先遍历算法,并输出遍历序列 3.实验环境Visual C++ 6.0 4 .实验方法和步骤(含设计) 我们通过二维数组中的值来表示图中节点与节点的关系。通过上图可 知, 其邻接矩阵示意图为如下: V0 v1 v2 v3 v4 v5 V0 1 0 1 0 1 V1 1 0 1 1 1 0 V2 0 1 0 0 1 0 V3 1 1 0 0 1 1 V4 0 1 1 1 0 0 V5 1 1 此时的 “1 ” 表示这两个节点有关系,“ 0”表示这两个节点无关系 我们通过邻接表来在计算机中存储图时,其邻接表存储图如下: 5.程序及测试结果 #include 二叉树三种遍历算法的源码 二叉树三种遍历算法的源码背诵版 本文给出二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准算法,直接用于考研答题。 1.先序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void PreOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历 { p=pop(s); p=p->rchild; }//endif }//endwhile }//PreOrderUnrec 2.中序遍历非递归算法 #define maxsize 100 typedef struct { Bitree Elem[maxsize]; int top; }SqStack; void InOrderUnrec(Bitree t) { SqStack s; StackInit(s); p=t; while (p!=null || !StackEmpty(s)) { while (p!=null) //遍历左子树 { push(s,p); p=p->lchild; }//endwhile if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历}//endif }//endwhile }//InOrderUnrec 3.后序遍历非递归算法 #define maxsize 100 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]; int top; }SqStack; void PostOrderUnrec(Bitree t) 实验四:图的遍历 题目:图及其应用——图的遍历 班级:姓名:学号:完成日期: 一.需求分析 1.问题描述:很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示在连通的无向图上访问全部结点的操作。 2.基本要求:以邻接表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集。 3.测试数据:教科书图7.33。暂时忽略里程,起点为北京。 4.实现提示:设图的结点不超过30个,每个结点用一个编号表示(如果一个图有n个结点,则它们的编号分别为1,2,…,n)。通过输入图的全部边输入一个图,每个边为一个数对,可以对边的输入顺序作出某种限制,注意,生成树的边是有向边,端点顺序不能颠倒。 5.选作内容: (1).借助于栈类型(自己定义和实现),用非递归算法实现深度优先遍历。 (2).以邻接表为存储结构,建立深度优先生成树和广度优先生成树,再按凹入表或树形打印生成树。 二.概要设计 1.为实现上述功能,需要有一个图的抽象数据类型。该抽象数据类型的定义为: ADT Graph { 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集。 数据关系R: R={VR} VR={ ○A ○C ○D ○B ○E○F G 《数据结构与算法》实验报告三 ——二叉树的操作与应用 一.实验目的 熟悉二叉链表存储结构的特征,掌握二叉树遍历操作及其应用 二. 实验要求(题目) 说明:以下题目中(一)为全体必做,(二)(三)任选其一完成 (一)从键盘输入二叉树的扩展先序遍历序列,建立二叉树的二叉链表存储结构;(二)分别用递归和非递归算法实现二叉树的三种遍历; (三)模拟WindowsXP资源管理器中的目录管理方式,模拟实际创建目录结构,并以二叉链表形式存储,按照凹入表形式打印目录结构(以扩展先序遍历序列输入建立二叉链表结构),如下图所示: (基本要求:限定目录名为单字符;扩展:允许目录名是多字符组合) 三. 分工说明 一起编写、探讨流程图,根据流程图分工编写算法,共同讨论修改,最后上机调试修改。 四. 概要设计 实现算法,需要链表的抽象数据类型: ADT Binarytree { 数据对象:D是具有相同特性的数据元素的集合 数据关系R: 若D为空集,则R为空集,称binarytree为空二叉树; 若D不为空集,则R为{H},H是如下二元关系; (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)若D-{root}不为空,则存在D-{root}={D1,Dr},且D1∩Dr为空集; (3)若D1不为空,则D1中存在唯一的元素x1, *问题描述: 建立图的存储结构(图的类型可以是有向图、无向图、有向网、无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵。 1、邻接矩阵表示法: 设G=(V,E)是一个图,其中V={V1,V2,V3…,Vn}。G的邻接矩阵是一个他有下述性质的n阶方阵: 1,若(Vi,Vj)∈E 或 若图中每个顶点只含一个编号i(1≤i≤vnum),则只需一个二维数组表示图的邻接矩阵。此时存储结构可简单说明如下: type adjmatrix=array[1..vnum,1..vnum]of adj; 利用邻接矩阵很容易判定任意两个顶点之间是否有边(或弧)相联,并容易求得各个顶点的度。 对于无向图,顶点Vi的度是邻接矩阵中第i行元素之和,即 n n D(Vi)=∑A[i,j](或∑A[i,j]) j=1 i=1 对于有向图,顶点Vi的出度OD(Vi)为邻接矩阵第i行元素之和,顶点Vi 的入度ID(Vi)为第i列元素之和。即 n n OD(Vi)=∑A[i,j],OD(Vi)=∑A[j,i]) j=1j=1 用邻接矩阵也可以表示带权图,只要令 Wij, 若 实验三、图的遍历操作 一、目的 掌握有向图和无向图的概念;掌握邻接矩阵和邻接链表建立图的存储结构;掌握DFS及BFS对图的遍历操作;了解图结构在人工智能、工程等领域的广泛应用。 二、要求 采用邻接矩阵和邻接链表作为图的存储结构,完成有向图和无向图的DFS 和BFS操作。 三、DFS和BFS 的基本思想 深度优先搜索法DFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后选择一个与Vo相邻且没被访问过的顶点Vi访问,再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问,……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问,则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W,从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。 广度优先算法BFS的基本思想:从图G中某个顶点Vo出发,首先访问Vo,然后访问与Vo相邻的所有未被访问过的顶点V1,V2,……,Vt;再依次访问与V1,V2,……,Vt相邻的起且未被访问过的的所有顶点。如此继续,直到访问完图中的所有顶点。 四、示例程序 1.邻接矩阵作为存储结构的程序示例 #include"" #include"" ertex); irstedge; irstedge; } } }//endwhile } //==========主函数=========== void main() { ALGraph *G; G=(ALGraph *)malloc(sizeof(ALGraph)); CreatALGraph(G); printf("Print Graph DFS: "); DFS(G); printf("\n"); printf("Print Graph BFS: "); BFS(G,3); printf("\n"); } 五、实验内容 1调试程序。设计一个有向图和一个无向图,任选一种存储结构,完成有向图和无向图的DFS(深度优先遍历)和BFS(广度优先遍历)的操作。 邻接矩阵作为存储结构的运行结果: 邻接链表作为存储结构的运行结果: 六、实验报告要求 画出你所设计的图,写出两种方法的遍历序列。 标准程序流程图的符号及使用约定 一,引言 程序流程图(Progran flowchart)作为一种算法表达工具,早已为工国计算机工作者和广大计算机用户十分熟悉和普通使用.然而它的一个明显缺点在于缺乏统一的规范化符号表示和严格的使用规则.最近,国家标准局批准的国家标准(GB1525-89)<<信息处理--数据流程图,程序流程图,系统流程图,程序网络图和系统资源图的文件编制符号及约定>>为我们推荐了一套标准化符号和使用约定.由于该标准是与国际标准化组织公布的标准ISO5807--85 Information processing--Documentation symbols and comventions for data,program and system flowcharts,program network charts and system resources charts是一致的,这里将其中程序流程图部分摘录出来,并做了一些解释,供读者参考. 根据这一标准画出的程序流程图我们称为标准流程图. 二,符号 程序流程图表示了程序的操作顺序.它应包括: (1)指明实际处理操作的处理符号,包括根据逻辑条件确定要执行的路径的符号. (2)指明控制流的流线符号. (3)便于读写程序流程图的特殊符号. 以下给出标准流程图所用的符号及其简要说明,请参看图1. 图1 标准程序流程图符号 1.数据---- 平行四边形表示数据,其中可注明数据名,来源,用途或其它的文字说明.此符号并不限定数据的媒体. 2.处理---- 矩形表示各种处理功能.例如,执行一个或一组特定的操作,从而使信息的值,信息形世或所在位置发生变化,或是确定对某一流向的选择.矩形内可注明处理名或其简工功能. 3.特定处理---- 带有双纵边线的矩形表示已命名的特定处理.该处理为在另外地方已得到详细说明的一个操作或一组操作,便如子例行程序,模块.矩形内可注明特定处理名或其简要功能. 4.准备---- 六边形符号表示准备.它表示修改一条指令或一组指令以影响随后的活动.例如,设置开关,修改变址寄存器,初始化例行程序. 5.判断----- 菱形表示判断或开关.菱形内可注明判断的条件.它只有一个入口,但可以有若干个可供选择的出口,在对符号内定义折条件求值后,有一个且仅有一个出口被激活.求值结果可在表示出口路径的流线附近写出. 6.循环界限---- 循环界限为去上角矩形表示年界限和去下角矩形的下界限构成,分别表示循环的开始和循环的结束. 实验报告 课程名称算法与数据结构 姓名何劼 专业计算机科学与技术 部别 指导教员 日期年月日 实验项目列表 实验报告 姓名:何劼学号:专业:计算机科学与技术部别: 实验地点:实验时间: 2012、4、17 设备编号: 同组人员:指导教员签字:成绩:教员评语: 一、实验名称 遍历算法及应用 二、实验目的 1 .掌握二叉树的递归构造方法 2 .掌握二叉树的递归遍历方法 3 .掌握二叉树的递归遍历的简单应用 三、实验内容和要求 编写完成如下功能的程序。 1 .构造二叉树(中序加后序序列造树选做) 2 .删除树中原来所有1 度的结点 3 .求给定的任意结点的父亲 4 .从根到叶的一条最长路经 5 .计算树中叶结点数(选) 6 .判定一棵树是否是正则树(选) 7 .按层遍历树,并输出树宽(选) 要求: 1 .先构造出二叉树,然后输出原树的三种遍历序列。 2 .在删除原来所有1 度的结点后,再输出新二叉树的三种遍历序列。 3 .直接输出给定结点的父结点的值。 4 .输出这条最长的路径。 5 .输出树中叶结点的数目。 6 .输出一棵树是否是正则树的判定结论。 7 .按层遍历树,并输出树宽 四、实验环境 1.硬件环境:PC机 2.软件环境:Windows操作系统,VC++集成开发环境 五、算法设计思想 题目一—构造二叉树。 为了使得程序能够更加具有通用性,设计者在构造二叉树时编写了三种造树方式,分别是先序扩充序列造树,先序加中序序列造树以及中序加后序造树。其中前两个程序已经在课上得到了实现。中序加后序造树,主要问题就是左右子树上下标界的确定,运用图示法能够较为形象准确的解决此问题。三种序列的输出这里不加赘述。 题目二——删除树中1度结点。 采用先序遍历递归。首先判断下一结点是否为1度结点,若为1度结点并且有右儿子,返回1;若为1度结点并且有左儿子,返回2;不为1度结点返回0。再根据返回值的情况进行勾连和结点的删除。 题目三——求结点的父亲。 采用后续遍历递归。设计者配合使用了类似于“红绿灯”的found 标记值。若为0则还未发现结点;若为1则找到该结点返回上一层输出其父亲,并置found为2。 题目四——输出从根到叶的一条最长路径。 首先找到最长路径对应的叶子(先序),再求取叶子的祖先(后序)。运用order数组存储其祖先,最后从后到前输出。这样得到的路径是符 二叉树的算法: 用扩展先序遍历序列创建二叉树; 递归遍历算法 中序非递归遍历层次遍历 二叉树深度的算法 实现代码如下: #include //以下为递归遍历算法 void PreOrder(BitTree root) /*先序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { Visit(root ->data); /*访问根结点*/ PreOrder(root ->LChild); /*先序遍历左子树*/ PreOrder(root ->RChild); /*先序遍历右子树*/ } } void InOrder(BitTree root) /*中序遍历二叉树, root为指向二叉树(或某一子树)根结点的指针*/ { if (root!=NULL) { InOrder(root ->LChild); /*中序遍历左子树*/ Visit(root ->data); /*访问根结点*/ InOrder(root ->RChild); /*中序遍历右子树*/ } } void PostOrder(BitTree root) /* 后序遍历二叉树,root为指向二叉树(或某一子树)根结点的指针*/ { if(root!=NULL) { PostOrder(root ->LChild); /*后序遍历左子树*/ PostOrder(root ->RChild); /*后序遍历右子树*/ Visit(root ->data); /*访问根结点*/ } } //中序非递归遍历 void InOrder1(struct Node *head) { struct Node *p; struct Node *stack[20]; int top=0; p=head; while(p||top!=0) { while (p)图的优先遍历算法(C语言版)
创建一个二叉树并输出三种遍历结果
临床科研设计模拟试题_附答案
树与图的简单遍历算法
树的遍历算法(完美C语言)
图的深度优先遍历算法课程设计报告
图的生成、图的遍历
数据结构C语言实现二叉树三种遍历
实验报告:图的存储结构和遍历
二叉树三种遍历算法代码_
图的遍历实验报告
用递归和非递归算法实现二叉树的三种遍历
邻接矩阵表示图,深度,广度优先遍历
图的遍历操作实验报告
非常实用的流程图符号及说明.doc
遍历算法及应用
二叉树的各种遍历算法及其深度算法