2022东北大学软件学院数据结构实验报告（线性表+栈和队列+二叉树+图）

2022东北大学软件学院数据结构实验报告，这门课最终得分92。

1.实验目的

实验1目的：

（1） 掌握线性表的实现。

（2） 掌握线性表的应用。

实验2目的：

（1） 掌握栈和队列的实现。

（2） 掌握栈和队列的应用。

实验3目的：

（1） 掌握二叉树的实现。

（2） 掌握二叉树的应用。

实验4目的：

（1） 掌握图结构的实现。

（2） 掌握图结构的应用。

2. 实验内容与实验步骤

2.1线性表的应用

2.1.1 实验内容

用线性表存储学生的各科成绩，并可以统计某门课的最高分、最低分、平均分情况，实现统计成绩的功能。

2.1.2 实验步骤

i . 首先进行实验的需求分析，实验的要求是完成一个能够统计学生成绩的最高分、最低分和平均分的程序，要求使用C语言中的链表实现，阅读实验要求，定义存储结构为学生类型的结构体、基本操作有创建链表，输出最高分、最低分和平均分。

ii .在c语言环境下编写代码，并进行调试。

iii .设计测试用例，运行程序，测试用例。

2.2 栈和队列的应用

2.2.1 实验内容

算术表达式求值：利用栈实现一个中缀表达式的求值。

2.2.2 实验步骤

i .首先进行实验的需求分析，要求利用栈来实现一个中缀表达式求值。基本的存储结构为栈结构，但是在C语言中并不存在栈结构，所以需要通过数组来实现。需要实现的操作有入栈和出栈操作，可以通过一个指向数组第一个元素的指针来实现（或者用一个索引指向栈顶元素）。最终实现表达式求值。

基本数据结构：

typedef float Num;

typedef struct

{

​ Num data[MAX];

​ int top;

}StackNum;//运算数栈

typedef struct

{

​ char data[MAX];

​ int top;

}StackChar;//运算符栈

ii .在C语言环境下编写代码，并进行调试。

iii .设计测试用例，运行测试程序，记录测试结果。

2.3二叉树的基本应用

2.3.1 实验内容

完成二叉树的基本操作，使用树结构存储医院楼房结构。

2.3.2 实验步骤

i .首先分析使用什么样的存储结构来实现树的存储，通过对医院楼房结构的分析，发现这并不是一棵二叉树，这个树形结构中并不都是简单的一对二的关系，所以不宜采用二叉树中的二叉链表存储；如果用三叉树来表示的话，因为只有一个节点是一对三的关系，所以使用三叉树表示会浪费空间，空间的利用率不高。最后决定采用左儿子右兄弟表示法。

ii .使用左儿子右兄弟表示法，那么基本的数据结构是链表。我自定义了一个结构体的类型，用于存储医院楼房结构中每一个节点的名称和该节点的父亲节点的边的权值。

基本的数据结构：

struct node{

char partname[35];

int countofpart;

struct node* leftson;

struct node* rightsibling;

};

其中的字符数组partname用于存储医院楼房设施的名字，countofpart用于存储医院楼房树形结构图中父亲节点到儿子节点的边上的权值，leftson是指向左儿子的指针，rightsibling是指向右兄弟的指针。

iii .使用孩子兄弟表示法表示医院的树形结构，根据我们定义的基本数据类型和医院楼房树形图，分析得到如下的表示。

图 1 医院楼房树形图

图 2 基本数据结构

图 3 左儿子右兄弟表示法存储结构图

2.4 图的用应结构

2.4.1 实验内容

完成图基本操作；并将下图中图数据存储;计算该图的最小生成树。

图 4 A mock European rail system

2.4.2 实验步骤

（1）首先分析题目要求：实验题目中所给的图是一个无向图，要求我们将图的数据存储。图的两种常见的存储方式有邻接矩阵和邻接表。并且要把图的边上的权值存储，图的边的权值有路费和距离。

（2）抽象数据类型（ADT）：

struct Graph{

int vexnum ;

int arcweight[20][20];

struct{ char vexname[20]; }Vex[20];

};

定义了结构体来存储图的信息。因为在求最小生成树的操作中并不涉及到增加和删除顶点，所以我使用了邻接矩阵的方式存储图的结构。结构体中的二维数组用来存储邻接矩阵的值，其中的vexnum表示的是图中的顶点数，再定义了一个结构体数组用来存储每一个顶点的名字，也就是用来存储每一个城市的名字。

（3）求图的最小生成树的算法有普里姆算法和克鲁斯卡尔算法。在实验中我选择了使用普里姆算法，普里姆算法的算法思想是选择点。

（4）理解普里姆算法。在求最小生成树的过程中，我们运用到了MST性质，即：

在生成树的构造过程中，图中的n个顶点分别属于两个集合：

已经落在生成树上的顶点集：U

尚未落在生成树上的顶点集：V-U

接下来则应该在所有连通U中顶点和V-U中顶点的边中选择权值最小的边

图 5 MST性质

3. 实验环境

实验的操作系统是Windows操作系统，调试软件是codeblocks，版本号是20.03，上机地点是信息楼B523，机器使用个人笔记本电脑。

4. 实验过程与分析

4.1线性表的应用

4.1.1定义学生结构体类型

首先定义一个学生结构体类型，学生结构体中包含学生的姓名、数学成绩、物理成绩、英语成绩和化学成绩。其中的姓名需要定义一个长度为20的字符串数组。考虑到学生的成绩可能是小数，所以把学生成绩定义的类型为double类型。结构体中还需要有一个学生类型的结构体指针。

图 6 学生结构体

4.1.2声明结构体指针

在创建链表和遍历链表时需要用到指针，所以声明了作用范围是全局的结构体指针。

图 7 结构体指针

4.1.3创建头结点

在创建链表时需要创建一个头结点，方便后续链表元素的增加和遍历。创建头结点时需要用到malloc函数。

图 8 创建头结点

4.1.4尾插法创建单链表

定义了creatlinklist函数来创建链表，使用尾插法创建链表。在前面声明了头指针和尾指针，通过传递的参数对节点的数据域赋值。然后，尾指针tail指向链表的最后一个节点。

图 9 定义函数创建链表

4.1.5输入学生成绩

通过键盘输入每一个学生的各科成绩，在主函数中调用创建链表的creatlinklist函数。

图 10 输入学生成绩

4.1.6定义查询最高分、最低分、平均分的函数

学生的成绩有4门，所以为了提高代码的重用性，定义了一个查询成绩的函数，判断其中的参数i来确定需要查询的是哪一科成绩，使用 switch case 语句进行条件判断。While循环遍历（循环条件是指针所指向的节点不为空），得到最低分、最高分和所有学生分数之和。

图 11 定义变量，head指向头结点后的第一个结点

图 12 while循环遍历链表和switch case语句

4.2 栈和队列的应用

4.2.1对中缀表达式的特点分析

中缀表达式就是我们在平常数学中所见到的表达式形式。它与后缀表达式不同，在中缀表达式中，遇到一个操作符不能够直接的计算，是否能够进行计算取决该运算符之后的运算符，需要比较这两个运算符的运算优先级。

和计算后缀表达式一样，我们引入一个操作数栈。由于后缀表达式不用缓存，加减乘除（ ±*/） 这些操作符，所以一个操作数栈就够了。但是，中缀表达式的计算是要用到操作符的缓存的，所以，还要再引入一个操作符栈，专门存储各个操作符。

以a + b * c+d为例，一个一个字符从左往右读取，当读到a时，a被压到操作数栈中，下一个读到+，由于运算符栈为空，所以+被压到操作符栈中，再下一个b被压到操作数栈中。

然后下一个读*，*压入操作符栈中，下一个读c，c压入操作数栈中。再往下，读取+，这时候就需要判断操作符栈顶元素和+的运算优先级，显然，乘法的运算优先级要高于加法。这时候就要从操作符栈顶中取出一个操作符，从操作数栈中自顶向下取出两个操作数进行运算。然后读取+，由于加减法的优先级低于乘除法，所以无论操作符栈顶的元素是什么，都可以进行运算，所以从操作符中弹出+，再从操作数栈中自顶向下弹出两个操作数进行运算。

然后就读取d，到达表达式的末尾，这时候弹出操作符栈的元素和操作数栈中的元素进行运算。运算的结果压入操作数栈中。

从上述例子的分析，我们可以发现：一个操作符究竟什么时候进行运算，并不取决于它前面的那个操作符是什么，而是取决于它后面的那个操作符是什么。即：如果后面的操作符的运算优化级比前面的操作符高，那么前面的操作符就必须延迟计算；如果后面的操作符优化级比前面的低或者相等，那么前面的操作符就可以进行计算。

图 13 中缀表达式算法流程图

4.2.2通过数组模拟实现栈

由于我使用的是C语言编码，在C语言中并没有栈的结构，这就需要我们模拟实现栈的结构。分别定义浮点数类型的数组作为操作数栈，定义了字符类型的数组作为操作符栈。

图 14 定义数组

4.2.3实现入栈、出栈操作

在数组中用top1、top2来表示数组的索引值。top1、top2的初始值都为-1，因为最开始时栈为空，而数组的第一个索引值是0。

在操作符的入栈操作中，需要先将top2加1，然后再把读到的操作符赋值给数组元素Operator[top2]。

在操作数的出栈操作中，需要先把当前的栈顶元素（也就是当前的Figure[top1]）赋值给c，然后top1减1，top1就成为了下一个元素的索引下标。

图 15 实现入栈、出栈

4.2.4对于多位运算的处理

在进行中缀表达式运算时，运算的操作数可能有1位，也可能有多位。例如53+7*3中的53就是有两位的运算数。如果还是按照一位一位字符读取的话，遇到多位运算的情况就会出现错误。

为了解决这个问题，在编码中，我增加了对于多位运算数的判断。若当前字符是操作数，那么就判断下一位字符是否也是操作数。若是，则对它们转换为多位的运算数，然后再压入栈。

图 16 多位运算数处理

4.3 二叉树的基本应用

4.3.1左孩子右兄弟存储树递归算法

定义函数create使用左孩子右兄弟法创建树，在主函数中先构建了树的根节点和树根的左儿子节点，然后再调用create函数构造数的其余节点，其算法流程图如下图所示：

图 17 构造树的根结点和左儿子结点

图 18 左孩子右兄弟递归算法

图 19 左儿子右兄弟递归算法流程图

4.3.2 遍历查找操作

把医院的树形结果存储之后，还要对queries文件中给出的查询操作对树进行查询。给出的有两种查询操作，一种是查询子部件操作，另一种是查询特定的子部件操作。要实现查询的操作，那就必须实现遍历的操作。我所编写的遍历算法的思路是从头结点开始遍历，如果头结点的名字不匹配，那么查找他的左儿子结点，如果还是不匹配，遍历他的左儿子的右兄弟，采用了递归的思想。

在查找中需要注意的是查找内容的有效性。譬如，在查找子部件操作中，如果从文件中读取的查找内容不存在，需要给出相应的提示；如果查找的内容刚好是位于叶子结点，那么它就没有孩子结点，它也就没有子部件。

图 20 遍历查找子部件

4.3.3 判断是哪一种查找操作

从queries文件中读取查找的内容时，会有两种查找操作，分别是查找子部件操作和查找特定子部件操作。读取文件我使用的是fscanf，与scanf不同，fscanf能够按行读取，并且还能够读取到每一行中分隔的字符串。所以，用fscanf读取到每一行的第一个字符串，如果这个字符串是“what”，那么就是查找子部件操作；如果这个字符串是“how”，那么就是查找特定的子部件的操作。

图 21 判断是哪一种查找操作

4.4 图结构的应用

4.4.1 邻接矩阵存储图结构

我们首先从结构体graph中得到图的顶点数，然后对邻接矩阵初始化，让每一个权值初始化为最大值maxInt，然后再从services文件中读取数据，构造邻接矩阵的权值。需要注意的是，当权值为maxInt的时候，表示这两个顶点不存在边。

为了更方便，直接地理解邻接矩阵的存储结构，我在Excel中通过表格的形式模拟了邻接矩阵，并初始化了邻接矩阵，若两个顶点之间不存在边，我就没有在单元格中写权值。

图 22 Excel中模拟实现邻接矩阵

为了方便实现操作，我首先在文件cities.txt中存储了城市的名称。然后文件读取，结构体数组Vex[20]中的顶点名称被赋值为城市的名称。然后再读取services.txt文件中的数据，为顶点之间的边赋权值。

图 23 构建图的操作

4.4.2 返回顶点编号的操作

在后续的对于求图的最小生成树的操作中，为了能够由顶点的名称获取顶点的编号，我定义了一个函数locate，它的作用是通过遍历顶点数组，通过顶点的名称来求出顶点的编号。

图 24 返回顶点的编号

4.4.3 普里姆算法的具体实现过程

在最开始时，需要随机地定义一个起始顶点，这个顶点我通过键盘输入，这个顶点加入生成树的集合中，然后寻找由这个顶点出发的到达边的权值最小的顶点，这就是第一步找点。

找到点之后，把这个点加入生成树的集合中，然后就需要更新生成树集合中顶点到不在生成树集合顶点边的最小权值。在这里，我定义了结构体数组closeedge[]来存放生成树顶点集合中的顶点到非生成树顶点集合的顶点。

struct

{ int adjvex;

int arcweight;

} closeedge[10];

图 25 数组表示

需要注意的是，一旦某个顶点加入了生成树，那么closeedge[i].arcweight就会被赋值为0，表示该顶点已经加入生成树顶点集合。adjvex表示的是到i顶点的最短距离的顶点编号，且该顶点是生成树集合中的顶点。

图 26 对数组元素的值初始化

当有顶点加入生成树顶点集合后，需要对closeedge[]数组中的值进行更新。更新的方法是：遍历新加入的顶点到其余各顶点的边权值，如果权值小于closeedge[]中到各顶点的最小权值，则需要把closeedge[]中的arcweight更新为最小的权值，adjvex更新为到达该顶点边的出发顶点。

图 27 对数组元素的值进行更新

当然，在最外层还设置了一层循环，因为最小生成树必须包括所有的顶点，所以循环的条件是当j小于或等于顶点的最大编号。当超过最大编号，就意味着已经找到了所有的顶点，结束循环。

minarc函数的作用是找出非生成树顶点集合中的顶点，要求找到的顶点到生成树集合顶点边的权值最小。

图 28 minarc函数

5. 实验结果总结

5.1线性表的应用实验结果

5.1.1用例设计

用例1：

输入节点个数： 4

输入学生成绩：

陈龙 95 96 98 85

张三 85 94 78 82

李四 75 81 95 88

王五 86 94 93 71

用例2：

输入节点个数： 3

输入学生成绩：

刘明 75 46 36 55

李琦 74 85 63 76

赵强 41 55 63 70

5.1.2 测试结果

图 29 用例1输入（部分）

图 30 用例1测试结果

图 31 用例2输入（部分）

图 32 用例2输出结果

两次用例的测试都达到了预期的测试结果，输出数据正常。

5.2 栈和队列的应用实验结果

5.2.1 用例设计

用例1：15*2+7-6

用例2：100/10+8*3-31+14

用例3：2*（31+69）

5.2.2 测试结果

为了方便输入，测试结果从operation.text文件中输入。

图 33 用例1测试结果

图 34 用例2测试结果

图 35 用例3测试结果

5.3 二叉树的基本应用实验结果

5.3.1 用例设计

用例1：how many wing floor

how many floor hospital

what is hospital

用例2：what is outlet

how many bed patient_room

用例3：how many lager_rubber_washer sink

5.3.2 测试结果

图 36 用例1测试结果

图 37 用例2测试结果

图 38 用例3测试结果

三个用例的测试结果完全正确，实验结果准确。

5.4 图结构的应用实验结果

5.4.1 用例设计

用例1：输入的开始节点为：London

用例2：输入的开始节点为：Berlin

用例3：输入的开始节点为：Sarajevo

5.4.2 实验结果

图 39 用例1输出结果

​

图 40 用例2输出结果

图 41 用例3输出结果

经过检验，3个用例输出的结果均为最小生成树，权值之和都是10600, 符合实验预期结果。

5.5 实验总结

通过这次实验，我进一步地理解了线性表中链表的使用方法。编写代码过程中也是遇到了一些小Bug，通过对代码的不断调试，修改，最终代码能够成功运行，程序也满足了实验的要求。其中一个小问题就是在创建链表的时候，最开始创建节点需要把头结点的next指向新的节点，还有就是遍历链表的时候需要再定义一个指针指向头结点，这样才能够实现链表的多次遍历。

在实验3二叉树的应用中，通过对医院楼房结果这样一个生活中的例子，我巩固了数据结构中对于树的存储，树的遍历、查找的内容的知识。在实验过程中，我更理解了“纸上得来终觉浅，绝知此事要躬行”的道理。数据结构的一些知识在课堂上看似听懂了，但是一到实际操作的过程中就会出现各种小问题。比如在写左儿子右兄弟的递归算法时，在代码调试中，没有报任何的问题，但是测试的结果却是没有输出。这个问题就很考验人了，我反复的检查自己写的代码，但是始终没有发现问题在哪。这时候我请教了我的同学，他看了一遍我的代码后，发现了问题所在。原来在写条件判断if语句中，写了（partnode->leftson=NULL）,

正确的应该是（partnode->leftson==NULL），这也说明了当我学习了多种语言的时候，当使用其中一种语言写代码时，就可能会和其他语言混淆。这也给了我一个很好的启示：编写代码不仅仅是需要掌握算法逻辑，还必须熟悉语言的语法规则。

在实验4图结构的应用中，通过求无向图的最小生成树，我对于普里姆算法有了更深刻的认识。在最开始分析实验的时候，因为自己在课堂上就了解过了普里姆算法的思想，觉得并不是很难。但是到了实际操作的时候，就会遇到一些自己没有想过的问题。比如如何表示出到达生成树顶点的权值最小边的顶点？如何表示该顶点已经在生成树顶点集合中？这些问题在编写代码过程中给了我很好的引导。在编写代码的过程中，同样会遇到一些小bug，但是在仔细检查代码后，进行了改正，最后程序也成功地运行。

总之，在这四次实验过程中，通过对链表、树、图等应用操作，我对于C语言中如何建立链表、查找链表，创建树、图以及相应的操作有了更清晰的认识，对于我理解数据结构这门课程是有很大帮助的，了解掌握了数据结构的一些算法原理，不仅仅能够锻炼我的逻辑思维，对于学习本专业的其他课程也奠定了很好的基础。