数据结构作业系统_第七章答案
- 格式：docx
- 大小：23.08 KB
- 文档页数：14
下载文档原格式
合集下载
《数据结构》填空作业题(答案)
《数据结构》填空作业题答案第 1 章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2．程序包括两个内容：数据结构和算法。
3.数据结构的形式定义为：数据结构是一个二元组：Data Structure =（ D， S）。
4.数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5.数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6.在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7.在树形结构中，数据元素之间存在一对多的关系。
8.数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9.数据的逻辑结构包括线性结构、树形结构和图形结构 3 种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12.数据的存储结构可用 4 种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。
14.数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16.数据元素可由若干个数据项组成。
17.算法分析的两个主要方面是时间复杂度和空间复杂度。
18.一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19.算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
数据结构作业及答案
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
数据结构》作业题答案
参考答案第一章、绪论一、选择题1 B；2 A； 3 B；4 C ；5 C； 6 B；7 C；8 C；9 D；10 B。
二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。
三、问答题与算法题1、3 ；2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;T4 ( n ) = 1.5 n 2 + O ( n ) 。
T4 ( n ) 较优，T3 ( n )较劣。
3、见课本。
第二章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。
三、问答题与算法题1、头指针：结点或头结点的指针变量。
其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。
头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。
其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。
首结点：是链表的第一个结点。
2、(1)基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
(2)基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
《数据结构(C语言版 第2版)》(严蔚敏 著)第七章练习题答案
《数据结构（C语言版第2版）》（严蔚敏著）第七章练习题答案第7章查找1．选择题（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。
A．(n-1)/2B．n/2C．(n+1)/2D．n答案：C解释：总查找次数N=1+2+3+…+n=n(n+1)/2，则平均查找长度为N/n=(n+1)/2。
（2）适用于折半查找的表的存储方式及元素排列要求为（）。
A．链接方式存储，元素无序B．链接方式存储，元素有序C．顺序方式存储，元素无序D．顺序方式存储，元素有序答案：D解释：折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
（3）如果要求一个线性表既能较快的查找，又能适应动态变化的要求，最好采用()查找法。
A．顺序查找B．折半查找C．分块查找D．哈希查找答案：C解释：分块查找的优点是：在表中插入和删除数据元素时，只要找到该元素对应的块，就可以在该块内进行插入和删除运算。
由于块内是无序的，故插入和删除比较容易，无需进行大量移动。
如果线性表既要快速查找又经常动态变化，则可采用分块查找。
（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。
A．20，70，30，50B．30，88，70，50C．20，50D．30，88，50答案：A解释：表中共10个元素，第一次取⎣(1+10)/2⎦=5，与第五个元素20比较，58大于20，再取⎣(6+10)/2⎦=8，与第八个元素70比较，依次类推再与30、50比较，最终查找失败。
（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A．3B．4C．5D．6答案：B解释：22个记录的有序表，其折半查找的判定树深度为⎣log222⎦+1=5，且该判定树不是满二叉树，即查找失败时至多比较5次，至少比较4次。
（6）折半搜索与二叉排序树的时间性能（）。
北大15春《数据结构》作业答案答案
d
A. A. {d,e,c,f,a,g,b}
B. B. {f,e,g,d,a,c,b}
C. C. {e,f,d,g,b,c,a}
D. D. {c,d,b,e,f,a,g }
6.栈和队列都是____a__。【第三章_栈和队列的基本概念P44，需要理解】
A. A.限制存取位置的线性结构
B. B.顺序存储的线性结构
c
A. A.快速排序<归并排序<直接插入排序=冒泡排序
B. B.快速排序=归并排序
C. C. Shell排序<快速排序=归并排序<直接插入排序=冒泡排序
D. D.直接插入排序=冒泡排序< Shell排序<快速排序=归并排序
15.
在冒泡排序、快速排序、堆排序、归并排序中，______d___排序是稳定的。【第十章】
作业ID：82376
1.
以下哪个算法的时间复杂度表示是最慢的？___b____【第一章】
A. A. O(1)
B. B. O(log2n)
C. C. O(n)
D. D. O(n^2 )
2.在一个线性表中，假设第一个元素a1的存储地址是20，每个元素占用四个存储单元，则第8个数据元素a8的地址是_c___：【第二章】
B. B. {25, 36, 48, 72, 16, 23, 40, 79, 82, 35}
C. C. {25, 36, 48, 72, 16, 23, 35, 40, 79, 82}
D. D. {16, 23, 25, 35, 36, 40, 48, 72, 79, 82}
14.
直接插入排序、快速排序、冒泡排序、归并排序、Shell排序，当元素数量很大时，时间复杂度按从小到大的顺序是如何排列的？【第十章】
A. A. {d,e,c,f,a,g,b}
B. B. {f,e,g,d,a,c,b}
C. C. {e,f,d,g,b,c,a}
D. D. {c,d,b,e,f,a,g }
6.栈和队列都是____a__。【第三章_栈和队列的基本概念P44，需要理解】
A. A.限制存取位置的线性结构
B. B.顺序存储的线性结构
c
A. A.快速排序<归并排序<直接插入排序=冒泡排序
B. B.快速排序=归并排序
C. C. Shell排序<快速排序=归并排序<直接插入排序=冒泡排序
D. D.直接插入排序=冒泡排序< Shell排序<快速排序=归并排序
15.
在冒泡排序、快速排序、堆排序、归并排序中，______d___排序是稳定的。【第十章】
作业ID：82376
1.
以下哪个算法的时间复杂度表示是最慢的？___b____【第一章】
A. A. O(1)
B. B. O(log2n)
C. C. O(n)
D. D. O(n^2 )
2.在一个线性表中，假设第一个元素a1的存储地址是20，每个元素占用四个存储单元，则第8个数据元素a8的地址是_c___：【第二章】
B. B. {25, 36, 48, 72, 16, 23, 40, 79, 82, 35}
C. C. {25, 36, 48, 72, 16, 23, 35, 40, 79, 82}
D. D. {16, 23, 25, 35, 36, 40, 48, 72, 79, 82}
14.
直接插入排序、快速排序、冒泡排序、归并排序、Shell排序，当元素数量很大时，时间复杂度按从小到大的顺序是如何排列的？【第十章】
数据结构第七章：图
例
a c G1
b d
vexdata firstarc adjvex next 1 4 ^ a 2 3 4 b c d 1 1 3 ^ ^ ^
19
7.3 图的遍历
深度优先遍历(DFS) 深度优先遍历
方法：从图的某一顶点 出发，访问此顶点； 方法：从图的某一顶点V0出发，访问此顶点；然后依 次从V 的未被访问的邻接点出发，深度优先遍历图， 次从 0的未被访问的邻接点出发，深度优先遍历图， 直至图中所有和V 相通的顶点都被访问到； 直至图中所有和 0相通的顶点都被访问到；若此时图 中尚有顶点未被访问， 中尚有顶点未被访问，则另选图中一个未被访问的顶 点作起点，重复上述过程， 点作起点，重复上述过程，直至图中所有顶点都被访 问为止。 问为止。
ω ij , 若(v i , v j )或 < v i , v j >∈ E(G) A[i, j ] = 0，其它
11
例
1 3
5
2
8 4 7 5 1 6 3 4 2
0 5 7 0 3
5 0 0 4 8
7 0 0 2 1
0 4 2 0 6
3 8 1 6 0
12
关联矩阵——表示顶点与边的关联关系的矩阵 表示顶点与边的关联关系的矩阵 关联矩阵
1
7.1 图的定义和术语
是由两个集合V(G)和E(G)组成的 组成的, 图(Graph)——图G是由两个集合 图 是由两个集合 和 组成的 记为G=(V,E) 记为
其中： 其中：V(G)是顶点的非空有限集 是顶点的非空有限集 E(G)是边的有限集合，边是顶点的无序对或有序对 是边的有限集合， 是边的有限集合
有向图——有向图 是由两个集合 有向图G是由两个集合 有向图 有向图 是由两个集合V(G)和E(G)组成的 和 组成的
数据结构作业系统第七章复习资料
7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。
注意：算法中涉及的图的基本操作必须在此存储结构上实现。
实现下列函数：Status DfsReachable(ALGraph g, int i, int j);/* Judge if it exists a path from vertex 'i' to *//* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM];typedef char VertexType;typedef struct ArcNode {int adjvex;struct ArcNode *nextarc;} ArcNode;typedef struct VNode {V ertexType data;ArcNode *firstarc;} VNode, AdjList[MAX_VERTEX_NUM];typedef struct {AdjList vertices;int vexnum, arcnum;} ALGraph;Status DfsReachable(ALGraph g, int i, int j)/* Judge if it exists a path from vertex 'i' to *//* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/{int k;ArcNode *p;visited[i]=1;for(p=g.vertices[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex;if(k==j)return 1;if(visited[k]!=1)if(DfsReachable(g,k,j))return 1;}}return 0;}7.23③同7.22题要求。
《数据结构》填空作业题（答案）
《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。
2．程序包括两个内容：数据结构和算法。
3. 数据结构的形式定义为：数据结构是一个二元组：Data Structure =（D，S）。
4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。
5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。
6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。
7. 在树形结构中，数据元素之间存在一对多的关系。
8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。
9. 数据的逻辑结构包括线性结构、树形结构和图形结构3种类型，树型结构和有向图结构合称为非线性结构。
10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。
11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。
12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。
13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。
14. 数据结构在物理上可分为顺序存储结构和链式存储结构。
15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。
16. 数据元素可由若干个数据项组成。
17. 算法分析的两个主要方面是时间复杂度和空间复杂度。
18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。
19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。
20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。
数据库课后习题作业答案
数据库课后习题作业答案《数据库系统概论》课程习题及参考答案第⼀章绪论（教材37页）１.试述数据、数据库、数据库系统、数据库管理系统的概念。
答：数据：描述事物的符号记录称为数据。
数据的种类有⽂字、图形、图像、声⾳、正⽂等等。
数据与其语义是不可分的。
数据库：数据库是长期储存在计算机内、有组织的、可共享的数据集合。
数据库中的数据按⼀定的数据模型组织、描述和储存，具有较⼩的冗余度、较⾼的数据独⽴性和易扩展性，并可为各种⽤户共享。
数据库系统：数据库系统(DBS)是指在计算机系统中引⼊数据库后的系统构成。
数据库系统由数据库、数据库管理系统(及其开发⼯具)、应⽤系统、数据库管理员构成。
数据库管理系统：数据库管理系统(DBMS)是位于⽤户与操作系统之间的⼀层数据管理软件。
⽤于科学地组织和存储数据、⾼效地获取和维护数据。
DBMS 主要功能包括数据定义功能、数据操纵功能、数据库的运⾏管理功能、数据库的建⽴和维护功能。
２.使⽤数据库系统有什么好处？答：使⽤数据库系统的好处是由数据库管理系统的特点或优点决定的。
使⽤数据库系统的好处很多，例如可以⼤⼤提⾼应⽤开发的效率，⽅便⽤户的使⽤，减轻数据库系统管理⼈员维护的负担等。
为什么有这些好处，可以结合第 5题来回答。
使⽤数据库系统可以⼤⼤提⾼应⽤开发的效率。
因为在数据库系统中应⽤程序不必考虑数据的定义、存储和数据存取的具体路径，这些⼯作都由 DBMS来完成。
此外，当应⽤逻辑改变，数据的逻辑结构需要改变时，由于数据库系统提供了数据与程序之间的独⽴性。
数据逻辑结构的改变是 DBA的责任，开发⼈员不必修改应⽤程序，或者只需要修改很少的应⽤程序。
从⽽既简化了应⽤程序的编制，⼜⼤⼤减少了应⽤程序的维护和修改。
使⽤数据库系统可以减轻数据库系统管理⼈员维护系统的负担。
因为 DBMS 在数据库建⽴、运⽤和维护时对数据库进⾏统⼀的管理和控制，包括数据的完整性、安全性，多⽤户并发控制，故障恢复等等都由DBMS执⾏。
数据库系统第七章习题答案
数据库系统第七章习题答案数据库系统第七章习题答案数据库系统是计算机科学中的一个重要分支，它研究如何存储、管理和检索大量结构化数据的方法和技术。
在数据库系统的学习过程中，习题是检验学生对知识掌握程度的重要方式之一。
本文将为读者提供数据库系统第七章习题的详细答案。
第一题：假设有一个名为"Students"的关系模式，包含学生的学号（Sid）、姓名（Name）和年龄（Age）三个属性。
请写出一个SQL语句，查询年龄大于20岁的学生的学号和姓名。
答案：SELECT Sid, Name FROM Students WHERE Age > 20;第二题：在上题的基础上，假设还有一个名为"Courses"的关系模式，包含课程的课程号（Cid）、课程名称（Cname）和学分（Credit）三个属性。
请写出一个SQL语句，查询选修了学号为"1001"的学生所选的所有课程的课程号和课程名称。
答案：SELECT Cid, Cname FROM Courses WHERE Cid IN (SELECT Cid FROM Selection WHERE Sid = '1001');第三题：在上题的基础上，假设还有一个名为"Selection"的关系模式，包含学生的学号（Sid）和所选课程的课程号（Cid）两个属性。
请写出一个SQL语句，查询选修了课程号为"C001"的课程的学生的学号和姓名。
答案：SELECT Sid, Name FROM Students WHERE Sid IN (SELECT Sid FROM Selection WHERE Cid = 'C001');第四题：在上题的基础上，假设还有一个名为"Scores"的关系模式，包含学生的学号（Sid）和课程的课程号（Cid）两个属性，以及学生在该课程中的成绩（Score）属性。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
1 / 14 7.22③试基于图的深度优先搜索策略写一算法， 判别以邻接表方式存储的有向图中是否存在由顶 点vi到顶点vj的路径(i≠j)。注意： 算法中涉及 的图的基本操作必须在此存储结构上实现。 实现下列函数： Status DfsReachable(ALGraph g, int i, int j); /* Judge if it exists a path from vertex 'i' to*/ /* vertex 'j' in digraph 'g'.*/ /* Array 'visited[]' has been initialed to 'false'.*/ 图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode*firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; 2 / 14
typedef struct { AdjList vertices; } ALGraph; Status DfsReachable(ALGraph g, int i, int j) /* Judge if it exists a path from vertex 'i' to*/ /* vertex 'j' in digraph 'g'.*/ /* Array 'visited[]' has been initialed to 'false'.*/{int k; ArcNode *p; visited[i]=1; for(p=g.vertices[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex; if(k==j)return 1; if(visited[k]!=1) if(DfsReachable(g,k,j))return 1;}} return 0;} 7.23③同 7.22题要求。试基于图的广度优先搜索策略写一算法。 实现下列函数： Status BfsReachable(ALGraph g, int i, int j); /* Determine whether it exists path from vertex i to */ /* vertex j in digraph g with Breadth_First Search.*/ /* Array 'visited' has been initialed to 'false'.*/ 3 / 14
图的邻接表以及相关类型和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode*firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; } ALGraph; Status InitQue(Que &q); Status EnQue(Que &q, int e); Status DeQue(Que &q, int &e); Status QueEmpty(Que q); Status GetFront(Que q, int &e); Status BfsReachable(ALGraph g, int i, int j) /* Determine whether it exists path from vertex i to */ 4 / 14
/* vertex j in digraph g with Breadth_First Search.*/ /* Array 'visited' has been initialed to 'false'.*/{Que q; int k,n; ArcNode *p; InitQue(q); EnQue(q,i); while(!QueEmpty(q)){DeQue(q,k); visited[k]=1; for(p=g.vertices[k].firstarc;p;p=p->nextarc){n=p->adjvex; if(n==j)return 1; if(visited[n]!=1)EnQue(q,n);}} return 0;} 7.24③试利用栈的基本操作编写，按深度优先搜索策略 遍历一个强连通图的非递归形式的算法。算法中不规定具 体的存储结构，而将图Graph看成是一种抽象的数据类型。 实现下列函数： void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType)); /* Travel the digraph 'dig' with Depth_First Search. */ 图以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; int LocateVex(Graph g, VertexType v); 5 / 14
VertexType GetVex(Graph g, int i); int FirstAdjVex(Graph g, int v); int NextAdjVex(Graph g, int v, int w); void visit(char v); Status InitStack(SStack &s); Status Push(SStack &s, SElemType x); Status Pop(SStack &s, SElemType &x); Status StackEmpty(SStack s); Status GetTop(SStack s, SElemType &e); void Traverse(Graph dig,VertexType v0, void (*visit)(VertexType)){inti,v,flag;SStack s;VertexType p;//flag来记录某点还有没有邻接点InitStack(s);
{i=LocateVex(dig,v0);visited[i]=TRUE;visit(v0);Push(s,v0); while(!StackEmpty(s)) {GetTop(s,p);v=LocateVex(dig,p);flag=0; for(i=FirstAdjVex(dig,v);i>=0;i=NextAdjVex(dig,v,i)) { if(!visited[i]) {p=GetVex(dig,i); flag=1; break;}} if(flag) {visit(p);visited[i]=TRUE; Push(s,p);}else{Pop(s,p); }}}} 7.27④采用邻接表存储结构，编写一个判别无向图中任意给定的 两个顶点之间是否存在一条长度为k的简单路径的算法。 6 / 14
实现下列函数： Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp); /* Judge whether it exists a path from sv to tv with length k */ /* in graph g, return path using string sp ifexists.*/ 图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM]; typedef charStrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex; struct ArcNode *nextarc; } ArcNode; typedef struct VNode { VertexType data; ArcNode*firstarc; } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; } ALGraph; int LocateVex(Graph g, VertexType v); 7 / 14
void inpath(char *&path, VertexType v); /* Add vertex 'v' to 'path' */ void depath(char *&path, VertexType v); /* Remove vertex 'v' from 'path' */ Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp) /* Judge whether it exists a path from sv to tv with length k */ /* in graph g, return path using string sp ifexists.*/ {int i,j,l; ArcNode *p; if(sv==tv && k==0) { inpath(sp,tv); return OK; } else{i=LocateVex(g,sv); visited[i]=1; inpath(sp,sv); for(p=g.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex; if(!visited[l]){if(SinglePath(g,g.vertices[l].data,tv,k-1,sp)) return OK; else depath(sp,g.vertices[l].data);}} visited[i]=0;}}