单链表的初始化插入和删除实验报告

数据结构实验报告

3. 后序遍历

4. 结点数 叶子数 高度

5..层次遍历

自己设计的：

abdhl##m##i##e#jn###cf#ko###g## 1.预计先序遍历结果：abdhlmiejncfkog 2.预计中序遍历结果：lhmdibenjafokcg 3.预计后序遍历结果：lmhidnjebokfgca 4.结点数 15 高度5 叶子数 6

17

数据结构实验报告

实际结果：

实验心得：这次实验主要是要让我们熟练树及其相关知识 熟练掌握先序中序后序遍历，层次遍历 然后我们自己画一个图 会实现以上功能 以及叶子数 结点数还有高度的计算 程序里面大量运用了递归以及队的应用，

18

数据结构实验报告

实验三、图的遍历操作

一、 目的

掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握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相邻的起且未被

19

数据结构实验报告

访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。 四、 程序源代码 1．

邻接矩阵作为存储结构的程序示例

#include\#include\

#define MaxVertexNum 100 //定义最大顶点数 typedef struct{

char vexs[MaxVertexNum]; //顶点表

int edges[MaxVertexNum][MaxVertexNum]; //邻接矩阵，可看作边表

int n,e; //图中的顶点数n和边数e }MGraph; //用邻接矩阵表示的图的类型 //=========建立邻接矩阵======= void CreatMGraph(MGraph *G) {

int i,j,k; char a;

printf(\ scanf(\输入顶点数和边数 scanf(\ printf(\ for(i=0;in;i++)

20