《数据结构》实验指导书--v1.0.doc

数据结构
－实验指导书

信息与电子工程学院
浙江工商大学

2009/4/7 周二 9:04:00

目录
目录 2
1. 链表结构（设计性） 1
1.1 实验目的 1
1.2 实验要求 1
1.3 实验内容 1
1.4实验步骤 2
1.5实验报告内容 2
1.6 评分 2
1.7 思考题 3
2. 队列结构（设计性） 4
2.1 实验目的 4
2.2 实验要求 4
2.3 实验内容 4
2.4 实验步骤 5
2.5 实验报告内容 5
2.6 评分 5
2.7 思考题 6
3. 二叉树结构（设计性） 7
3.1 实验目的 7
3.2 实验要求 7
3.3 实验内容 7
3.4 实验步骤(参考) 8
3.5 实验报告内容 8
3.6 评分 9
3.7 思考题 9
4. 图结构（设计性） 11
4.1 实验目的 11
4.2 实验要求 11
4.3 实验内容 11
4.4 实验步骤（参考） 12
4.5 实验报告内容 12
4.6 评分 13
4.7 思考题 13
5. 查找算法（设计性） 15
5.1 实验目的 15
5.2 实验要求 15
5.3 实验内容 15
5.4 实验步骤 15
5.5实验报告内容 16
5.6 评分 16
5.7 思考题 17

数据结构实验 Last updated: 2025/2/3 周一
1. 链表结构（设计性）
姓名： 学号： 班级： 得分：
习题：
1.1 实验目的
1．熟悉C语言的上机环境，进一步掌握C语言的结构特点。
2．掌握线性表的链式存储结构——单链表的定义及C语言实现。
3．掌握线性表在链式存储结构——单链表中的各种基本操作。

1.2 实验要求
1．预习C语言中结构体的定义与基本操作方法。
2．对单链表的每个基本操作用单独的函数实现。
3．编写完整程序完成下面的实验内容并上机运行。
4．整理并上交实验报告。

1.3 实验内容
在VC++环境下编写调试单链表初始化，删除结点，查找结点，插入结点的算法和函数。或者
把已布置作业中的算法改成程序，进行运行。
问题描述：
利用线性表的链式存储结构,设计学生成绩表，能够对单链表进行如下操作：
1．初始化一个带表头结点的空链表；
2．创建一个单链表是从无到有地建立起一个链表，即一个一个地输入各结点数据，并建立起前后相互链接的关系。又分为逆位序(插在表头)输入n 个元素的值和正位序(插在表尾)输入n 个元素的值；
3．插入结点可以根据给定位置进行插入（位置插入），也可以根据结点的值插入到已知的链表中（值插入），且保持结点的数据按原来的递增次序排列，形成有序链表。
4．删除结点可以根据给定位置进行删除（位置删除），也可以把链表中查找结点的值为搜索对象的结点全部删除（值删除）；
5．输出单链表的内容是将链表中各结点的数据依次显示，直到链表尾结点；
6．编写主程序，实现对各不同的算法调用。

1.4实验步骤
1．利用尾插法建立学生成绩单链表，并遍历。
2．插入节点，且保持节点的数据按原来的递增次序排列。
3．删除节点。

1.5实验报告内容
1、实验目的。
2、实验内容和具体要求。
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法。
4、程序清单。
5、所输入的数据及相应的运行结果。
6、实验心得。

1.6 评分
上交实验报告前，请同学先打分。
大类
明细
打分
1.程序功能（30％）
（1）正确定义链表的数据结构（10％）

（2）完成题目要求功能（20％）

2.程序质量（30%）
（1）用大括号和缩进来清楚地显示程序结构。（提示：按一次"tab"键产生一个缩进)（5％）

（2）各函数有功能说明和参数说明（5％）

（3）每个源程序文件都有说明（比如本程序功能，作者，包含哪些函数）（5％）

（4）每个函数长度不超过100行（5％）

（5）函数、变量取名前后一致并容易理解（5％）

（6）对不容易理解的常量、变量和语句有注释（比如全局常量、变量、if语句）（5％）

3.实验报告（20%）（请附在后面）
（1）有经验总结（10％）

（3）有程序代码（包括主函数）（10％）

4．程序调试（20%）
（1）会单步运行到任何一个语句（10％）

（2）单步运行时能查看变量值（10％）

1.7 思考题
1．如果上面实验内容用头插法如何建立单链表。
2．如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb，Lc，使得Lb中只含La表中奇数结点，Lc中含有La表的偶数结点。

2. 队列结构（设计性）
姓名： 学号： 班级： 得分：
习题：
2.1 实验目的
1．熟练掌握栈和队列的特点。
2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。
3．掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队
等基本操作。
4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。

2.2 实验要求
1．认真阅读和掌握本实验的算法。
2．上机将本算法实现。
3．保存程序的运行结果，并结合程序进行分析。
4．上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序。
5．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。

2.3 实验内容
1．在VC++环境下编写调试队列初始化，删除结点，查找结点，插入结点的算法和函数。
2．把已布置作业中的算法改成程序，进行运行。
问题描述：
用顺序栈把输入的1个字符串反序输出，能够对顺序栈进行如下操作：
1．初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底；
2．完成一个元素的入栈操作，修改栈顶指针；
3．完成一个元素的出栈操作，修改栈顶指针；
4．读取栈顶指针所指向的元素的值；

2.4 实验步骤
1. 初始化顺序栈
2. 插入元素
3. 删除栈顶元素
4. 取栈顶元素
5. 遍历顺序栈

2.5 实验报告内容
1、实验目的。
2、实验内容和具体要求。
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法。
4、程序清单。
5、所输入的数据及相应的运行结果。
6、实验心得。

2.6 评分
上交实验报告前，请同学先打分。
大类
明细
打分
1.程序功能（30％）
（1）正确定义队列的数据结构（10％）

（2）完成题目要求功能（20％）

2.程序质量（30%）
（1）用大括号和缩进来清楚地显示程序结构。（提示：按一次"tab"键产生一个缩进)（5％）

（2）各函数有功能说明和参数说明（5％）

（3）每个源程序文件都有说明（比如本程序功能，作者，包含哪些函数）（5％）

（4）每个函数长度不超过100行（5％）

（5）函数、变量取名前后一致并容易理解（5％）

（6）对不容易理解的常量、变量和语句有注释（比如全局常量、变量、if语句）（5％）

3.实验报告（20%）（请附在后面）
（1）有经验总结（10％）

（3）有程序代码（包括主函数）（10％）

4．程序调试（20%）
（1）会单步运行到任何一个语句（10％）

（2）单步运行时能查看变量值（10％）

2.7 思考题
1．读栈顶元素的算法与退栈顶元素的算法有何区别？
2．如何用队列的链式存储来实现输入一个字符串，按序输出。
3．编写程序实现表达式求值，即验证某算术表达式的正确性，若正确，则计算该算术表达式的值。
主要功能描述如下：
a、从键盘上输入表达式。
b、分析该表达式是否合法：
（1）是数字，则判断该数字的合法性。若合法，则压入数据到堆栈中。
（2）是规定的运算符，则根据规则进行处理。在处理过程中，将计算该表达式的值
（3）若是其它字符，则返回错误信息。
c、若上述处理过程中没有发现错误，则认为该表达式合法，并打印处理结果。

3. 二叉树结构（设计性）
姓名： 学号： 班级： 得分：
习题：
3.1 实验目的
1．熟练掌握二叉树的二叉链表存储结构。
2．掌握二叉树的非线性和递归性特点。
3．熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现。
4．掌握线索二叉树的定义和基本操作。
5．加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力。

3.2 实验要求
1．认真阅读和掌握本实验的算法。
2．上机将本算法实现。
3．保存程序的运行结果，并结合程序进行分析。
4．上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序。
5．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。

3.3 实验内容
在VC++环境下编写调试二叉链表遍历的算法和函数，或者把已布置作业中的算法改成程序，进行运行。
问题描述：
用输入的n个整数建立n个结点的完全二叉树，其操作如下：
1．创建一棵空二叉树；
2．对一棵存在的二叉树进行销毁；
3．根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树；
4．判断某棵二叉树是否为空；
5．求二叉树的深度；
6．求二叉树的根结点，若为空二叉树，则返回一特殊值；
7．二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次；
8．编写主程序，实现对各不同的算法调用。
3.4 实验步骤(参考)
A．编写代码
1．首先将二叉树的链式存储结构定义放在一个头文件：如取名为BinTreeDef.h。
2．将二叉树的基本操作算法也集中放在一个文件之中，如取名为BinTreeAlgo.h。包含关于二叉树的链式结构操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。
3．将函数的测试和主函数组合成一个文件，如取名为BinTreeUse.cpp。
B．建立工程和调试
1．启动VC++;
2．新建工程/Win32 Console Application，选择输入位置：如“d:\”，输入工程的名称：如“BinTreeDemo”；按“确定”按钮，选择“An Empty Project”，再按“完成”按钮；
3．加载实验一中的pubuse.h 选中菜单的”project”— >“add to project”— > “files”选择已存在文件，确定，然后一定将文件pubuse.h 拷贝到所建的工程目录下；
4．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“BinTreeDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
5．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“BinTreeAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
6．新建文件/C Source File，选中“添加到工程的复选按钮”，输入文件名“BinTreeUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
7．构件、调试。可以采用单步调试F10/F11等。

3.5 实验报告内容
1、实验目的。
2、实验内容和具体要求。
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法。
4、程序清单。
5、所输入的数据及相应的运行结果。
6、实验心得。

3.6 评分
上交实验报告前，请同学先打分。
大类
明细
打分
1.程序功能（30％）
（1）正确定义二叉链表的数据结构（15％）

（2）完成题目要求功能（20％）

2.程序质量（30%）
（1）用大括号和缩进来清楚地显示程序结构。（提示：按一次"tab"键产生一个缩进)（5％）

（2）各函数有功能说明和参数说明（5％）

（3）每个源程序文件都有说明（比如本程序功能，作者，包含哪些函数）（5％）

（4）每个函数长度不超过100行（5％）

（5）函数、变量取名前后一致并容易理解（5％）

（6）对不容易理解的常量、变量和语句有注释（比如全局常量、变量、if语句）（5％）

3.实验报告（20%）（请附在后面）
（1）有经验总结（10％）

（3）有程序代码（包括主函数）（10％）

4．程序调试（20%）
（1）会单步运行到任何一个语句（10％）

（2）单步运行时能查看变量值（10％）

3.7 思考题
1．如何计算二叉链表存储的二叉树中度数为1的结点数。
2．已知有—棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结点到p所指结点之间的路径。
3．利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行。
4．按程序要求输入结点的值（一个字符），`0`表示空树，生成赫夫曼树的编码。完成Huffman编码的译码过程，即输入一个码串，翻译成相应的字符串。

4. 图结构（设计性
姓名： 学号： 班级： 得分：
习题：
4.1 实验目的
1．熟练掌握图的两种存储结构(邻接矩阵和邻接表)的表示方法。
2．掌握图的基本运算及应用。
3．加深对图的理解，逐步培养解决实际问题的编程能力。

4.2 实验要求
1．对图的各项操作一定要编写成为C（C++）语言函数，组合成模块化的形式，每个算法的实现要从时间复杂度和空间复杂度上进行评价。
2．将本算法中的各个操作实现。
3．保存程序的运行结果，并结合程序进行分析。
4．上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序。
5．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。

4.3 实验内容
在VC++环境下编写调试图深度优先和广度优先遍历的算法和函数，或者把已布置作业中的算法改成程序，进行运行。
问题描述：输入每条边的顶点u和 v及其权值w，然后建立用邻接矩阵表示的图。其相关操作如下：
1. 创建一个可以随机确定结点数和弧（有向或无向）数的图。
2. 根据图结点的序号，得到该结点的值。
3. 根据图结点的位置的第一个邻接顶点的序号，以及下一个邻接顶点的序号。
4. 实现从第v 个顶点出发对图进行深度优先递归遍历。
5. 实现对图作深度优先遍历。
6. 编写主程序，实现对各不同的算法调用。
4.4 实验步骤（参考）
A．编写代码
1．首先将图的邻居矩阵结构定义放在一个头文件：如取名为ALGraphDef.h。
2．将图的基本操作算法也集中放在一个文件之中，如取名为ALGraphAlgo.h。
3．将函数的测试和主函数组合成一个文件，如取名为ALGraphUse.cpp。
B．建立工程和调试
1．启动VC++;
2．新建工程/Win32 Console Application，选择输入位置：如“d:\”，输入工程的名称：如“BinTreeDemo”；按“确定”按钮，选择“An Empty Project”，再按“完成”按钮；
3．加载实验一中的pubuse.h 选中菜单的”project”— >“add to project”— > “files”选择已存在文件，确定，然后一定将文件pubuse.h 拷贝到所建的工程目录下；
4．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“ALGraphDef.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
5．新建文件/C/C++ Header File，选中“添加到工程的复选按钮”，输入文件名“ALGraphAlgo.h”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
6．新建文件/C++ Source File，选中“添加到工程的复选按钮”，输入文件名“ALGraphUse.cpp”，按“确定”按钮，在显示的代码编辑区内输入如上的参考程序；
7．构件、调试。可以采用单步调试F10/F11等。

4.5 实验报告内容
1、实验目的
2、实验内容和具体要求
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法
4、程序清单
5、所输入的数据及相应的运行结果
6、实验心得

4.6 评分
上交实验报告前，请同学先打分。
大类
明细
打分
1.程序功能（30％）
（1）正确定义图的数据结构（10％）

（2）完成题目要求功能（20％）

2.程序质量（30%）
（1）用大括号和缩进来清楚地显示程序结构。（提示：按一次"tab"键产生一个缩进)（5％）

（2）各函数有功能说明和参数说明（5％）

（3）每个源程序文件都有说明（比如本程序功能，作者，包含哪些函数）（5％）

（4）每个函数长度不超过100行（5％）

（5）函数、变量取名前后一致并容易理解（5％）

（6）对不容易理解的常量、变量和语句有注释（比如全局常量、变量、if语句）（5％）

3.实验报告（20%）（请附在后面）
（1）有经验总结（10％）

（3）有程序代码（包括主函数）（10％）

4．程序调试（20%）
（1）会单步运行到任何一个语句（10％）

（2）单步运行时能查看变量值（10％）

4.7 思考题
1．采用邻接表方式存储图，实现图的深度遍历和广度遍历；并用广度优先搜索方法找出从一顶点到另一顶点边数最少的路径。
2．校园导游图编程要求：
(1) 设计学校的校园平面图，所含景点不少于10 个。以图中顶点表示校内各景点，存放景点名称、代号、
简介等信息；以边表示路径，存放路径长度等相关信息。
(2)为来访客人提供图中任意景点相关信息的查询。
(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
3．假设以一个带权有向图表示某一区域的公交线路网，图中顶点代表一些区域中的重要场所，弧代表已有的公交线路，弧上的权表示该线路上的票价（或搭乘所需时间），试设计一个交通指南系统，指导前来咨询者以最低的票价或最少的时间从区域中的某一场所到达另一场所。
5. 查找算法（设计性）
姓名： 学号： 班级： 得分：
习题：
5.1 实验目的
1、掌握查找的特点。
2、掌握折半查找的基本思想及其算法。
3、熟悉二叉排序树的特点，掌握二叉排序树的插入、删除操作。

5.2 实验要求
1．认真阅读和掌握本实验的算法。
2．上机将本算法实现。
3．保存程序的运行结果，并结合程序进行分析。
4．上机过程中，能够熟练运用高级语言的程序调试器DEBUG调试程序。
5．上机后，认真整理源程序及其注释，完成实验报告（包括源程序、实验结果、算法分析、心得体会等）。

5.3 实验内容
1、设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 }，查找key=21和key=25的数据元素。
2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树，并完成删除关键字53和24的操作。
3、可以完成作业布置的内容。题目：对输入的n个整数进行折半查找
5.4 实验步骤
1、折半查找
（1）从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35，存放在数组bub[8]中，并输出其值。
（2）从键盘输入21，查找是否存在该数据元素，若存在，则输出该数据元素在表中的位置，否则给出查找失败的信息。
（3）从键盘输入25，查找是否存在该数据元素，若存在，则输出该数据元素在表中位置，否则给出查找失败的信息。
2、二叉排序树
（1）二叉排序树结点定义
typedef struct BiTNode { // 结点结构
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
（2）从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树
（3）输出其中序遍历结果。
（4）删除数据元素24，输出其中序遍历结果。
（5）删除数据元素53，输出其中序遍历结果。

5.5实验报告内容
1、实验目的。
2、实验内容和具体要求。
3、完成情况和实验记录，实验记录为实验过程中遇到的问题及解决方法。
4、程序清单。
5、所输入的数据及相应的运行结果。
6、实验心得。

5.6 评分
上交实验报告前，请同学先打分。
大类
明细
打分
1.程序功能（30％）
（1）正确定义图的数据结构（10％）

（2）完成题目要求功能（20％）

2.程序质量（30%）
（1）用大括号和缩进来清楚地显示程序结构。（提示：按一次"tab"键产生一个缩进)（5％）

（2）各函数有功能说明和参数说明（5％）

（3）每个源程序文件都有说明（比如本程序功能，作者，包含哪些函数）（5％）

（4）每个函数长度不超过100行（5％）

（5）函数、变量取名前后一致并容易理解（5％）

（6）对不容易理解的常量、变量和语句有注释（比如全局常量、变量、if语句）（5％）

3.实验报告（20%）（请附在后面）
（1）有经验总结（10％）

（3）有程序代码（包括主函数）（10％）

4．程序调试（20%）
（1）会单步运行到任何一个语句（10％）

（2）单步运行时能查看变量值（10％）

5.7 思考题
1．用其它的查找方法完成该算法。
2．比较各种算法的时间及空间复杂度。
3．构造hash树，实现hash查找。

17