下载文档原格式
数据结构严蔚敏版第十章答案第十章：图一、概述图是一种非常重要的数据结构，它由节点（顶点）和边组成，用于描述事物之间的关系。
在本章中，我们将学习图的基本概念、表示方法和常用算法。
二、基本概念1. 顶点（节点）：图中的一个元素，用于表示一个实体，如人、地点等。
2. 边：连接两个顶点的关系，可以是有向的（箭头指向一个方向）或无向的（没有箭头）。
3. 路径：由一系列顶点和边组成的序列，表示从一个顶点到另一个顶点的通路。
4. 无环图：不存在回路（从一个顶点出发，经过若干边又回到该顶点）的图。
5. 有环图：存在回路的图。
三、表示方法1. 邻接矩阵：使用二维数组来表示图的连接关系，数组的行和列分别对应图中的顶点，数组元素表示边的权重或连接状态。
2. 邻接表：使用链表来表示图的连接关系，每个顶点对应一个链表，链表中存储与该顶点相连的其他顶点。
四、图的遍历1. 深度优先搜索（DFS）：从一个顶点开始，沿着一条路径尽可能深入地访问顶点，直到无法继续为止，然后回溯到上一个顶点，继续访问其他路径。
使用栈来实现。
2. 广度优先搜索（BFS）：从一个顶点开始，先访问其所有相邻顶点，然后再访问相邻顶点的相邻顶点，以此类推，直到所有顶点都被访问到。
使用队列来实现。
五、最小生成树最小生成树是指在一个连通图中，选择其中的一些边，使得这些边构成一棵树，并且树上所有边的权重之和最小。
常用的算法有Prim算法和Kruskal算法。
六、最短路径最短路径是指从一个顶点到另一个顶点的路径中，路径上所有边的权重之和最小。
常用的算法有Dijkstra算法和Floyd算法。
七、拓扑排序拓扑排序是对有向无环图进行排序的一种算法。
它将图中的顶点按照一定的顺序排列，使得所有的有向边都从前面的顶点指向后面的顶点。
八、关键路径关键路径是指在一个有向无环图中，从开始顶点到结束顶点的最长路径。
关键路径上的活动不能延误，否则将影响整个工程的进度。
九、其他图算法除了上述提到的算法，还有许多其他的图算法，如最大流问题、二分图匹配等。
数 据 结 构 第10章 内部排序10.1 概述•什么是排序？–排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。
–若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
10.1 概述•待排序的数据类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型10.1 概述•内部排序的类别–插入类：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。
–交换类：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。
–选择类：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。
–归并类：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。
