第一篇：数据结构实验指导书

数据结构实验指导书

信息工程学院计算机系

实验一 线性表实验

实验目的

熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点熟悉链表的各种操作。时间要求：4学时 问题描述：

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求: 利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号。

实现提示：

程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码(小于30)。

选作内容：

在顺序存储结构上实现上述问题的操作。

Input 输入包括两行，第一行包括报数上限值m和人数n，第二行为n个人的密码，所有数据之间由空格分隔。Output 输出一行，共n个整数，表示各编号人的出列顺序。各数之间由空格分隔。Sample Input 20 7 3 1 7 2 4 8 4 Sample Output 6 1 4 7 2 3 5 2

实验二 栈和队列实验

实验目的

熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。时间要求：4+4学时 问题描述：

设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，当便道上汽车要离开时，排在它前面的汽车要先开走让路，然后再依次排到队尾，并且在便道上停车不收费。试为停车场编制按上述要求进行管理的模拟程序。

基本要求：

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列管理，每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时间，对每一组输入数据进行操作后的输出数据为： 若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便递上停留的时间不收费），栈以顺序结构实现，队列以链表结构实现。实现提示：

需另设一栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含有两个数据项：汽车牌照号码和进入停车场的时间。选作内容：

（1）两个栈共享空间，思考应开辟数组的空间是多少 ?（2）汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如 1 辆客车和 1.5 辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。（3）停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这神要求。Input 输入第一行，包括两个数据，第一个整数为停车场最多可停放车辆数，第二个浮点数表示单位时间的停车费用。接下来有多行数据，每行有三个整数，第一个为0或1，0表示进 入车场，1表示离开车场；第二个整数为车号；第三个整数为进入或离开的时间。当一行中三个数均为0时表示输入结束，所有数据之间由空格分隔。Output 输出为三部分，第一部分为按离开停车场顺序打印出的各车费用，每车一行，包括车号和费用(保留小数点后两位)。第二部分占一行为当前停车场中的所有车辆，从北到南顺序输出各车车号。第三部分占一行为当前便道上的所有车辆，从前向后顺序输出各车车号。各车号之间由一个空格分隔。Sample Input 2 1.5 0 1 5 0 2 10 1 1 15 0 3 20 0 4 25 0 5 30 0 6 35 1 2 40 0 7 45 1 6 50 0 0 0 Sample Output 1 15.00 2 45.00 3 4 7 5 4

实验三 哈夫曼树实验

实验目的

熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。时间要求：4+4学时 问题描述：

利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。

基本要求：

一个完整的系统应具有以下功能：

（1）I： 初始化。从终端读入字符集大小 n，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。

（2）C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

（3）D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。

（4）P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。

（5）T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。

实现提示：

（1）用户界面可以设计为“菜单”方式：显示上述功能号，再加上“E”表示结束运性行结束，用户键入一个选择功能字符，则执行相应的功能，此功能执行完毕后再显示此菜单，直至用户选择了“E”为止。

（1）在程序的一次执行过程中，第一次执行了I、D 或 C 命令之后，哈夫曼树已经在内存中存在了，不必再读入。每次执行中不一定执行 I 命令，因为文件 hfmtree 可能早已建好。

选作内容：

（1）修改你的系统，使系统实现对自身源程序的编码和译码（注意特殊符号的编/译码问题）。

（2）实现各个转换操作的源/目的文件均由用户自己指定。

实验四 图的搜索实验

实验目的

熟悉图的相关操作，掌握图的搜索算法及其应用，同时进一步练习栈与队列在实际问题中的应用。时间要求：4+4学时 问题描述：

一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。问题是让你帮助老鼠找出从入口到出口的一条最短路径。

00001000 11001010 00010000 00001010 10100000 00111011 10001000 基本要求：

为老鼠找出一条从入口到出口的最短路径。实现提示：

1、迷宫用数组表示，1代表是墙走不通，0表示可以通行。边界可以扩充为墙，即M×N迷宫用(M+2)×(N+2)数组表示。

2、向4个方向前进时的位移量可以用以下数组表示，处理时方便。

int move[4][2]={ {0,1},{1,0},{0,-1},{-1,0} };

3、采用图的广度优先搜索算法。选作内容：

对给定的迷宫，统计出共有多少条不同的路径。

实验五 排序实验

实验目的

熟练掌握各种排序算法的实现方法，以及不同算法的特点，掌握各种排序方法的时间效率。

时间要求：4+4学时 问题描述：

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。对一组给定的数据，设计出各不同排序算法对其进行排序，给出各算法在排序中的关键字比较次数和关键字移动次数，以取得直观感受。基本要求：

（1）对以下各排序算法进行比较：直接插入排序、冒泡排序、快速排序、简单选择排序、归并排序。

（2）待排序表的表长为100；一共有n组不同的数据，对每组数据用以上各排序方法进行排序，比较的指标为有关键字参加的比较次数和关键字的移动次数。实现提示：

在算法的适当地方加入计数操作，计算关键字的比较次数和移动次数。选作内容：

对算法的稳定性作验证。

Input 输入部分第一行为待排关键字的组数n，接下来为n行待排关键字，第行有100个整数所有数据之间由空格分隔。Output 输出共n行，每行共有10个整数，表示5种排序方法排序的关键字比较次数和移动次数，即为：直接插入排序比较次数 直接插入排序移动次数 冒泡排序比较次数 冒泡排序移动次数 快速排序比较次数、快速排序移动次数 简单选择排序比较次数、简单选择排序移动次数 归并排序比较次数 归并排序移动次数（下例待排关键字为5，实际提交测试数据为100）Sample Input 3 1 2 3 4 5 5 4 3 2 1 4 2 5 1 3 Sample Output 4 0 4 0 10 16 10 0 7 12 14 18 10 30 12 16 10 6 5 12 10 12 10 18 11 14 10 6 7 12

数据结构实验报告

实验一 线性表实验

班级：____________ 姓名：____________ 学号：____________

实验目的：

熟悉线性表的基本运算在顺序存储结构和链式存储结构上的实现，其中重点掌握线性表的链式表示时各种操作的实现。问题描述：

约瑟夫（Joseph）问题的一种描述是：编号为1，2，3，„，n的n个人按顺时针方向围坐一圈，每人持有一个密码〈正整数〉，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）

数据结构实验报告

实验二 栈和队列实验

班级：____________ 姓名：____________ 学号：____________

实验目的：

熟悉栈和队列的基本特性，掌握栈和队列基本运算的实现过程。重点掌握栈和队列各种操作的实现。问题描述：

设停车场内只有一个可停放 n 辆汽车的狭长通道，且只有一个大门可供汽车进出，汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满 n 辆汽车，则后来的汽车只能在门外的便道上等候, 一旦有车开走，则排在便道上的第一辆车即可开入，当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）

数据结构实验报告

实验三 哈夫曼树实验

班级：____________ 姓名：____________ 学号：____________

实验目的：

熟悉非线性结构的特点 , 掌握非线性结构的存储方式及各种操作的实现方法，同时对自顶向下的程序设计方法、应用程序界面的设计、非线性结构的文件存储方法等方面的辑程技术进行训练。问题描述：

利用哈夫曼编码进行信息通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码；在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统，试为这样的信息收发站写一个哈夫曼编译码系统。基本要求：

一个完整的系统应具有以下功能：

（1）I： 初始化。从终端读入字符集大小 n，及 n 个字符和 n 个权值，建立哈夫曼树，并将其存于文件hfmtree中。

（2）C： 编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree中读入），对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中。

（3）D： 译码。利用已建好的哈夫曼树将文件codefile中的代码进行译码，结果存入文件textfile中。

（4）P： 打印代码文件。将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。

（5）T：打印哈夫曼树。将已在内存中的哈夫曼树以直观的方式（树或凹凸表形式）显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）(后面可加页)

数据结构实验报告

实验四 图搜索实验

班级：____________ 姓名：____________ 学号：____________

实验目的：

熟悉图的相关操作，掌握图的搜索算法及其应用，同时进一步练习栈与队列在实际问题中的应用。问题描述：

一只老鼠走进了一个迷宫，这个迷宫是由M行N列（如:10行8列）的方格构成的，相邻方格之间可能是相通的，也可能有墙相隔，各方格位置由其对应坐标确定，如图所示。迷宫在（1，1）处有一个入口，在（M,N）处有一个出口，在入口和出口之间有通路相通。问题是让你帮助老鼠找出从入口到出口的一条最短路径。基本要求：

为老鼠找出一条从入口到出口的最短路径。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）(后面可加页)

数据结构实验报告

实验五 排序实验

班级：____________ 姓名：____________ 学号：____________

实验目的

熟练掌握各种排序算法的实现方法，以及不同算法的特点，掌握各种排序方法的时间效率。

时间要求：4+4学时 问题描述：

各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。对一组给定的数据，设计出各不同排序算法对其进行排序，给出各算法在排序中的关键字比较次数和关键字移动次数，以取得直观感受。

需求分析：（包括对问题的理解，解决问题的策略、方法描述）

系统设计：（包括数据结构定义、抽象出基本操作描述、主程序模块处理过程描述）

调试分析：（包括调试过程中对原设计的修改，以及遇到的问题和解决的方法）

测试结果：（输入的测试数据及运行结果、正确性、在线测试情况）

基本操作的实现：（对各基本操作实现的描述）

第二篇：数据结构实验指导书

目 录

实验规则················································2 实验环境················································2 实验报告要求············································3 实验一 单链表

（一）······································4 实验二 单链表

（二）······································5 实验三 栈···············································6 实验四 二叉树···········································7 实验五 最短路径·········································8 实验六 内部排序·········································9

实 验 规 则

为了顺利完成实验教学任务，确保人身、设备的安全，培养严谨、踏实、实事求是的科学作风和爱护国家财产的优良品质，特制定以下实验规则：

1、实验前必须充分预习，完成指定的预习任务。预习要求如下：

（1）认真阅读指导书，进行必要的设计与计算。（2）熟悉实验内容。

（3）预先复习，并按要求编写程序。（4）未完成预习任务者不得进入实验室。

2、遵守以下纪律：

（1）在实验室不得做和实验无关的事情。

（2）进行任课老师指定内容以外的实验，必须经指导教师同意。（3）遵守纪律，不迟到。

（4）保持实验室内安静、整洁，爱护公物，不许乱写乱画。

实 验 环 境

本实验在386以上的微机上进行，运行环境为VC6.0。

实验报告要求

1、实验题目 2．实验目的 3．实验环境

4．实验内容与完成情况（可以附上自主设计的源程序）5．出现的问题及对问题的解决方案 6．实验思考：（学生对本次实验的收获的总结）

实验一 单链表

（一）一、实验目的

掌握线性表的链式存储结构及其基本操作。

二、预习要求

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容

实现一个简单的学生信息管理系统，该系统的功能有：

1、利用单链表建立学生基本信息表

2、浏览每个学生的信息

3、根据学号查询某个学生的基本信息

4、添加学生信息到单链表中

5、删除一个学生的信息

四、实现提示

设计结点的结构体类型，包括学生的学号、姓名、年龄、性别；要求设计一个简单的菜单界面，根据需要选择所要进行的操作；构造函数，每一个函数实现上述的一个功能。

实验二 单链表

（二）一、实验目的

掌握线性表的链式存储结构及其基本操作。

二、预习要求

1、看懂书上的算法，深入理解链表的物理存储模式和逻辑模式。

2、根据要求，编写程序准备上机调试。

三、实验内容

1、实现单链表的就地逆置。

2、建立两个非递减有序单链表，然后合并成一个非递减链表。

3、建立两个非递减有序单链表，然后合并成一个非递增链表。

4、编写一个主函数,调试上述算法。

四、选做题、思考题

1、如何用带表头结点的单链表作为多项式的存储表示，实现两个多项式的相加。

2、约毖夫环的实现。

3、如何利用文件实现学生信息的存取。

实验三 栈

一、实验目的

深入了解并掌握栈的特性及其在实际中的应用；熟练掌握栈的算法实现；运用栈操作求解实际问题。

二、预习要求

1、看懂书上的算法，深入理解栈的特性和存储结构，以便在实际问题背景下灵活运用。

2、根据要求，编写程序准备上机调试。

三、实验内容

利用栈实现数据的分类，要求当输入为偶数时进栈1，当输入为奇数时进栈2，最后分别从栈1和栈2输出偶数和奇数序列。

四、实现提示

1、开辟一个连续的存储空间，实现两个栈顺序存储空间的共享；分别在两端设置栈顶指针，并按要求实现栈操作。

2、采用顺序存储实现栈的初始化、入栈、出栈操作。

五、选做题、思考题

1、两栈空间共享时，栈满的条件是什么？

2、为停车场编制进行管理的模拟程序（习题集P96，2.1）。

3、编写程序，利用栈实现表达式求值。

实验四 二叉树

一、实验目的

通过实践掌握二叉树的存储结构和遍历思想；掌握二叉树的常见算法的程序实现。

二、预习要求

二叉树的三种遍历方法。

三、实验内容

1、输入字符序列，建立二叉链表。

2、利用栈，编写非递归算法，编程实现二叉树的中序遍历。

3、求二叉树的叶子结点个数。

4、在主函数中设计一个简单的菜单，分别调试上述算法。

四、选做题、思考题

1、如何实现二叉树的后序遍历（非递归）。

2、如何求二叉树的高度。

实验五 最短路径（旅游景点导游咨询模拟）

一、实验目的

利用图的最短路径原理为用户提供路径咨询，掌握求最短路径的算法并编程实现。

二、预习要求

学习了解图的存储结构，掌握求最短路径的两种算法。

三、实验内容

设计一个旅游景点导游模拟程序，为来访的客人提供景点最短路径的信息查询服务，任意选取n城市，构成一个有向带权图，图中顶点表示城市，边上的权值表示两点间的距离，根据用户指定的始点和终点输出相应的最短路径。

四、实现提示

咨询以用户和计算机的对话方式进行，由用户输入起始点和终点，输出信息：最短路径是多少？并指出所经过的城市。存储结构可选用邻接矩阵。

五、选做题、思考题

1．如何实现对城市信息进行编辑（如：添加或删除）的功能。

2．用邻接表作存储结构，求一指定景点出发，到其余各景点的最短路径。

实验六 内部排序

一、实验目的

直观感受算法的关键字比较次数和关键字移动次数。

二、预习要求

1、常见的排序算法(插入排序、交换排序、选择排序、归并排序、基数排序等)的思想、特点及其适用条件。

2、根据要求，编写程序准备上机调试。

三、实验内容

1、对直接插入排序和简单选择排序算法进行关键字比较次数和关键字移动次数的比较。

2、利用链式存储结构，编写程序，实现直接插入排序和冒泡排序。

四、实现提示

测试数据可以为几组典型的数据：正序、逆序、乱序。

五、选做题、思考题

1、快速排序算法的非递归实现。

2、结合实验，理解针对不同待排元素的特点而选择不同排序方法的重要性。

3、如何对本实验进行时间、空间的复杂度分析。

第三篇：数据结构 实验指导书

数 据 结 构 实 验 指 导 书

数据结构实验指导书

目录

数据结构实验指导书.......................................................................................................................1

目录...........................................................................................................................................1 实验指导书概述...............................................................................................................................2 上机实验题目...................................................................................................................................3

实验一 C语言相关知识复习................................................................................................3

一、实验目的...................................................................................................................3

二、实验内容...................................................................................................................3 实验二 单链表的插入、删除...............................................................................................3

一、实验目的...................................................................................................................3

二、实验内容...................................................................................................................3

三、实现提示...................................................................................................................4 实验三 栈及其应用.................................................................................................................5

一、实验目的...................................................................................................................5

二、实验内容...................................................................................................................5 实验四 二叉树的递归算法.....................................................................................................6

一、实验目的...................................................................................................................6

二、实验内容...................................................................................................................6 实验五 图的遍历.....................................................................................................................7

一、实验目的...................................................................................................................7

二、实验内容...................................................................................................................7 实验六 有序表的查找.............................................................................................................7

一、实验目的...................................................................................................................7

二、实验内容...................................................................................................................7 实验七 哈希表.........................................................................................................................7

一、实验目的...................................................................................................................7

二、实验内容...................................................................................................................7 实验八 内部排序算法的应用.................................................................................................8

一、实验目的...................................................................................................................8

二、实验内容...................................................................................................................8

实验指导书概述

“数据结构”是计算机专业一门重要的专业技术基础课程，是一门关键性核心课程。本课程系统地介绍了软件设计中常用的数据结构以及相应的存储结构和实现算法，介绍了多种常用的查找和排序技术，并对其进行了性能分析和比较，内容非常丰富。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。

由于以下原因，使得掌握这门课程具有较大难度：  内容多，时间短，给学习带来困难；

 贯穿全书的动态链表存储结构和递归技术是学习中的重点和难点；  隐含在各部分的技术和方法丰富，也是学习的重点和难点；  先修课程中所介绍的专业性知识不多，加大了学习难度。

由于数据结构课程的技术性与实践性，《数据结构课程实验》的设置十分必要。为了帮助学生更好地学习本课程，理解和掌握算法设计所需的技术，为整个专业学习打好基础，要求运用所学知识，上机解决一些典型问题，通过分析、设计、编码、调试等各环节的训练，使学生深刻理解、牢固掌握所用到的一些技术。

上机实践是对学生的一种全面综合训练，是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通过上机实践，使学生在可能短的时间内对数据结构知识的实践和应用有一个比较全面和系统的认识，达到理论与实践相结合的目的。

为了达到上述目的，本指导书安排了8个实验题目，它们与教科书的各章有紧密的关系，使学生在实验后能加深对课程内容的理解，增强动手能力。

每个实验题目采取了统一的格式，由问题描述、基本要求、测试数据、实现提示等部分组成。

问题描述旨在为读者建立问题提出的背景环境，指明问题“是什么”；

要求则对问题进一步求精，划出问题的边界，指出具体的参量或前提条件，并规定该题的最低限度要求；

测试部分旨在为检查学生上机作业提供方便，在完成实习题时应自己设计完整和 严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据；

实现提示对实现中的难点及其解法思路等问题作了简要提示，个别问题给出了参考实现。

下面带*的题目为选做题目。

上机实验题目

实验一 C语言相关知识复习

一、实验目的

复习C语言中函数、数组、结构体、文件等概念，掌握它们的描述与操作方法；熟悉掌握C++中typedef、引用参数调用（&）的概念及使用方法，为理解数据结构课程的后续内容以及算法书写奠定基础。

二、实验内容 问题描述：编写一个函数，求一个整数数组中的最大、最小值。

要求：在函数声明中采用引用参数传递方式实现最大、最小值的返回。测试：在主函数中输入10个数，调用此函数，打印输出最大和最小值。2 关于指针的使用：

用malloc方式分别申请两个指针，并实现两个指针内容的比较大小操作。要求：此功能在一个函数内实现，该函数接受两个整数值，存储到两个指针内容中，输出两者中的最大值。

测试：从主函数中输入两个数，调用该函数，打印输出交换后的值。

实验二 单链表的插入、删除

一、实验目的

1、熟悉某种数据结构在计算机上实现的方法。

2、掌握单链表的定义、创建、插入、删除、遍历等基本操作的实现。

3、体会单链表操作、有序表插入、删除的一般方法。

二、实验内容

问题描述：已知递增有序的单链表A，编写算法实现向A中插入或删除一个元素，并保持A的有序性。

实验要求：

1、结点的数据均为整型。

2、若表中已经存在此元素，则不插入

三、实现提示

1.在已知的线性表中插入或删除，需要下面的辅助函数：线性表的创建、线性表的遍历

2.在单链表表中插入或删除，需依次实现：

a)单链表结构的定义

b)单链表的创建（头插法或尾插法建表）c)单链表的遍历

d)单链表的插入、删除（采用顺序查找方法，顺头指针往后，查找插入或删除位置，再修改指针）

//头文件

#include “stdlib.h” //预定义常量 #define NULL 0

//单链表的定义

typedef struct LNode{ int data;struct LNode *next;}LNode,*LinkList;//单链表的创建

void Create_List(LinkList &L){ int data;LinkList p,q;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;

q=L;

scanf(“%d”,&data);while(data!=0){

p=(LinkList)malloc(sizeof(LNode));

p->data=data;

p->next=q->next;

q->next=p;

q=p;

scanf(“%d”,&data);} }

//单链表的遍历

void TranverseList(LinkList L){

LinkList p;

p=L->next;

if(p==NULL)

{

printf(“niln”);

return;

}

while(p!=NULL)

{

printf(“%d ”,p->data);

p=p->next;

}

printf(“n”);}

实验三 栈及其应用

一、实验目的

1、熟悉栈的顺序表示与实现。

2、熟悉栈的应用。

3、理解并掌握递归函数的设计与实现。

二、实验内容 问题描述：利用栈实现十进制数n转化为d进制数 要求：

1)输入一个n和d，打印输出d进制数序列。

2)利用顺序栈来实现十进制数n转化为其他d进制数。此时，需要同时实现初始化空栈、入栈、出栈、判栈空等辅助功能。测试数据：

（1）输入n:1348

d:8 输出：2504（2）输入n:9

d:8 输出：11（3）输入n:0

d:8 输出：0 2 问题描述：利用栈实现算术表达式求值。要求：

1)参与运算的操作数为10以内的数值。测试数据：

自拟。

实验四 二叉树的递归算法

一、实验目的

1、掌握二叉树的表示与实现。

2、掌握二叉树的定义、创建、遍历等基本操作的实现。

3、熟悉求二叉树深度等递归算法的设计与实现。

二、实验内容

问题描述：已知二叉树t，分别采用顺序存储结构、二叉链表存储结构实现求二叉树的深度，并对二叉树分别进行中序遍历。要求：

1、二叉树分别采用顺序或二叉链表存储。

2、树中的数据类型约定为整型。测试数据：

1、输入序列：-+aØØ*bØØ-cØØdØØ/eØØfØØ创建二叉树； 输出：深度：5

前序序列：-+a*b-cd/ef

中序序列：a+b*c-d-e/f

后序序列：abcd-*+ef/-T:d / e f

2、t=nil

输入：Ø

输出：深度：0 实验五 图的遍历

一、实验目的

熟悉图的基本操作，掌握图遍历的设计与实现。

二、实验内容

问题描述：已知的描述校园景点的图，实现对该图的深度优先和广度优先遍历。要求：

图采用邻接矩阵存储，顶点信息包括景点的名称和简单描述。

实验六 有序表的查找

一、实验目的

1、理解各种查找方法的基本思想

2、熟悉有序表查找方法的算法实现

二、实验内容 已知一有序的序列{1,3,5,7,9}，采用折半法分别查找3和6。

2已知输入一无序的序列{5,1,3,9,7}，创建一棵二叉排序树，然后对其遍历，输出递增有序的序列。

实验七 哈希表

一、实验目的

理解哈希表的概念和基本操作；熟悉哈希表的创建、查找、插入的算法实现。

二、实验内容

问题描述：已知11位好友的名字各不相同，设计并实现一个哈希表，根据好友的名字，可以取得其生日。要求：

1、好友的信息包含名字和生日两个数据项，其中好友的名字为主键，用汉语拼音形式存放；

2、哈希函数采取：好友名字中所有拼音字母ASCII码值的和 MOD 11(除以1取余)；

3、采取线性探测再散列的方式处理冲突。

实验八 内部排序算法的应用

一、实验目的

理解各种内部排序方法的基本思想；熟悉各种内部排序方法的算法实现

二、实验内容

问题描述：已知一序列{503，087，512，061，908，170，897，275，653，426}，分别采取下列排序方法对其进行排序：

（1）直接插入排序；

（2）简单选择排序；

（3）起泡排序；（4）快速排序；（5）堆排序。

第四篇：数据结构实验指导书（精选）

石 家 庄 铁 道 大 学

实 验 任 务 书

课程名称： 数据结构 实验学时： 8 适用专业： 自动化类专业 开设学院： 电气与电子工程学院

石 家 庄 铁 道 大 学

14学年—15学年第 2学期 数据结构实验任务书

专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 王明明 实验题目：线性表的基本操作

实验环境： Visual C++ 实验目的：

1、掌握线性表的定义；

2、掌握线性表的基本操作，如建立、查找、插入和删除等。

实验内容：

定义一个包含学生信息（学号，姓名，成绩）的的顺序表或链表，使其具有如下功能：(1)根据指定学生个数，逐个输入学生信息；(2)逐个显示学生表中所有学生的相关信息；

(3)根据姓名进行查找，返回此学生的学号和成绩；

(4)根据指定的位置可返回相应的学生信息（学号，姓名，成绩）；(5)给定一个学生信息，插入到表中指定的位置；(6)删除指定位置的学生记录；(7)统计表中学生个数。

实验提示：

学生信息的定义： typedef struct { char no[8];//8位学号 char name[20];//姓名 int price;//成绩 }Student;

顺序表的定义

typedef struct { Student *elem;//指向数据元素的基地址

int length;//线性表的当前长度 }SqList；

链表的定义：

typedef struct LNode{ Student data;//数据域 struct LNode *next;//指针域 }LNode,*LinkList;

实验要求：

(1)程序要添加适当的注释，程序的书写要采用缩进格式。

(2)程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应，如插入删除时指定的位置不对等等。

(3)程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。(4)根据实验报告模板详细书写实验报告,在实验报告中给出链表根据姓名进行查找的算法和插入算法的流程图。

石 家 庄 铁 道 大 学

14学年—15学年第 2 学期 数据结构实验任务书

专业名称： 实验学时： 2 课程名称：数据结构 任课教师： 李冬梅

实验题目：栈的应用－算术表达式求值

实验环境： Visual C++ 6.0 实验目的：

1．掌握栈的定义及实现；

2．掌握利用栈求解算术表达式的方法。

实验内容：

通过修改完善教材中的算法3.4，利用栈来实现算术表达式求值的算法。对算法3.4中调用的几个函数要给出其实现过程：

(1)函数In(c)：判断c是否为运算符；

(2)函数Precede(t1,t2)：判断运算符t1和t2的优先级；(3)函数Operate(a,theta,b)：对a和b进行二元运算theta。

程序运行时，输入合法的算术表达式（中间值及最终结果要在0～9之间，可以包括加减乘除和括号），便可输出相应的计算结果。如下图：

实验提示：（仅供参考，每个函数的具体实现可以有多种方法，希望有创新）

1.将栈的定义和实现单独保存在头文件“stack.h”中，然后在表达式求值的源程序sy2.cpp中包含此头文件（即#include“stack.h”）。2.表达式求值源程序sy2.cpp的具体实现(1)主函数如下： void main(){ cout<<“请输入算术表达式,并以#结束.”<

(2)函数EvaluateExpression的实现见算法3.10(3)函数In(c)的实现可以采用以下方式：

Status In(SElemType c)// 应在前面有定义typedef char SElemType;{ // 判断c是否为运算符 switch(c){ case'+':return TRUE;„„//补充完整

default:return FALSE;} }(4)函数Precede(t1,t2)的实现可以采用以下形式： SElemType Precede(SElemType t1,SElemType t2){ //根据教材表3.1，判断两个运算符的优先关系 SElemType f;switch(t2){ case '+': case '-':if(t1=='('||t1=='#')f='<';else f='>';break;„„//补充完整 } return f;}(5)函数Operate(a,theta,b)的实现可以采用以下方式：

SElemType Operate(SElemType a,SElemType theta,SElemType b){ SElemType c;a=a-48;b=b-48;switch(theta){ case'+':c=a+b+48;break;„„//补充完整 } return c;}

选做内容1：进一步改进，使表达式的中间值及最终结果不局限于0～9之间的个位数。（如

果完成要在实验报告中注明），如下图：

选做内容2：

将表达式转化成后缀表达式输出，利用后缀表达式求表达式的值并输出。

将中缀表达式转化成后缀表达式存储在队列中，然后利用后缀表达式求表达式的值并输出。

 将中缀表达式转化成后缀的思想：

（1）创建一空队列，用来存放后缀表达式，建立并初始化操作符栈OPTR，将表达式起始符“#”压入OPTR栈。

（2）依次读入表达式中每个字符ch，循环执行（3）至（5），直至求出整个表达式转换完毕。

（3）取出OPTR的栈顶元素，当OPTR的栈顶元素和当前读入的字符ch均为“#”时，整个中缀表达式转换完毕。

（4）若ch不是运算符，则进队，读入下一字符ch。

（5）若ch是运算符，则根据OPTR的栈顶元素和ch的优先权比较结果，做不同的处理。

① 若是小于，则ch压入OPTR栈，读入下一字符ch。② 若是大于，则弹出OPTR栈顶的运算符，进队。③ 若是等于，则OPTR的栈顶元素是“(”且ch是“)”，这时弹出OPTR栈顶的“(”，相当于去掉括号，然后读入下一字符ch。 对后缀表达式进行计算的具体步骤为：

建立一个栈S从左到右读后缀表达式，读到数字就将它转换为数值压入栈S中，读到运算符则从栈中依次弹出两个数分别到Y和X，然后以“X运算符Y”的形式计算出结果，再压进栈S中。如果后缀表达式未读完，重复执行上面过程，最后输出栈顶的数值即可结束。

实验要求：

(1)程序要添加适当的注释，程序的书写要采用缩进格式。

(2)程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。(3)程序要做到界面友好，在程序运行时用户可以根据相应的提示信息进行操作。(4)根据实验报告模板详细书写实验报告,在实验报告中给出表达式求值算法的流程图。

第五篇：数据结构实验指导书

目 录

实验一

线性表、栈和队列的基本操作............................................................1 实验二

二叉树的基本操作................................................................................3 实验三

内部排序的基本操作............................................................................5 附录：《数据结构与算法》实验报告格式..........................................................6

实验一

线性表、栈和队列的基本操作

【实验目的】

1.掌握线性表（顺序表和链表）的顺序和链式存储结构的定义及C语言的实现。

2.掌握线性表（顺序表和链表）的建立、插入、删除、查找等基本操作。3.深入了解栈和队列的基本特性。

4.熟练掌握栈和队列的基本操作在两种存储结构上的实现。5.熟练掌握循环队列的基本操作。

【实验内容】

1.报数问题：编号为1，2，···，n的n个人围坐在一圆桌旁，每人持有一个正整数的编号。从第一个人开始报数，报到一个预先约定的正整数m时，停止报数，报m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。编一程序输出他们退席的编号序列。例如，设m=20，n=7，则退席的人的编号依次为6，1，7，5，3，2，4。

2.设计一个顺序栈的基本操作的程序，包括初始化顺序栈、判断栈空、求顺序栈中的元素个数、取顺序栈栈顶元素、入栈、出栈，并测试十进制转换成16进制的运算。

3.设计一个循环队列的基本操作的程序，包括实现下列6种基本运算：初始化、入队、出队、遍历、求队列的长度，并测试用队列实现杨辉三角的输出显示。

【实验安排】

由于该实验是数据结构的第一个实验，建议适当多安排一些时间进行熟悉。建议课时安排如下：

课外 2学时，课内2学时

【实验提示】

1.报数问题的存储结构可以采用以下两种方式：

(1)以顺序表为存储结构：可以用简单的数组

int p[n];

(2)以循环链表为存储结构：用不带表头结点的循环单链表表示围成圆圈的n个人；建立此循环单链表；某人离席相当于删除一个结点要正确设置程序中循环终止的条件和删除结点时指针的修改变化。

typedef struct LNode{ int data;

实验二

二叉树的基本操作

【实验目的】

1.掌握二叉树的链式存储结构及实现方法。2.掌握二叉树的遍历方法。

3.掌握二叉树中插入结点、删除结点的方法。

4.掌握二叉树的结点个数、叶子结点个数和树的深度的计算方法。5.掌握建立哈夫曼树的方法，实现哈夫曼编码。

【实验内容】

1.要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：(1)基于先序遍历的构造算法：输入是二叉树的先序序列，但必须在其中加入虚结点以示空指针的位置。假设虚结点输入时用空格字符表示。(2)分别利用前序遍历、中序遍历、后序遍历所建二叉树。(3)统计以上二叉树中叶子结点的个数和结点总数。2.熟练掌握哈夫曼树的构建，并实现哈夫曼编码。

【实验安排】

建议课时安排如下：

课外 4学时，课内2学时

【实验提示】

1.采用C语言的定义树的存储结构： //二叉树的链式存储表示 typedef char DataType;//应由用户定义DataType的实际类型 typedef struct node { DataType data;struct node *lchild, *rchild;//左右孩子指针 } BinTNode;

//结点类型

typedef BinTNode *BinTree;

2.可以考虑采用递归的方法先创建根结点，然后分别创建左右子树。在创建二叉树的过程中，要注意结点数是根据输入的字符确定的。如：

void CreateBinTree(BinTree &T){

实验三

内部排序的基本操作

【实验目的】

1.掌握排序的有关概念和特点。

2.熟练掌握直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序、基数排序等算法的基本思想。

3.关键字序列有序与无序，对于不同的排序方法有不同的影响，通过该实验进一步加深理解。

4.了解各种排序方法的优缺点和适用范围。

【实验内容】

1.从键盘输入上述8个整数，存放在数组quick[8]中，并输出值。2.输出各种排序算法每一趟排序的结果，观察关键字次序的变化。

3.如果上述8个整数按照升序输入，即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 }，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。4.如果上述8个整数按照降序输入，即k2={ 68 , 45 , 33 , 30 , 21 , 12 , 12 , 2}，输出各种排序算法每一趟排序的结果，观察关键字次序的变化。5.测试各排序算法的执行时间，比较执行效率。

6.随机产生3万个数，对其进行排序，观察其结果。

【实验安排】

建议课时安排如下：

课外 2学时，课内2学时 【实验提示】

1.采用C语言的定义记录类型的存储结构： typedef int InfoType;#define n 10

typedef int KeyType;typedef struct {

//假设的文件长度，即待排序的记录数目 //假设的关键字类型 //记录类型

//关键字项

//其它数据项，类型InfoType依赖于具体应用而 KeyType key;

InfoType otherinfo;定义

} RecType;typedef RecType SeqList[n+1];作哨兵

2.注意哨兵的作用。

//SeqList为顺序表类型，表中第0个单元一般用