数据结构实验指导书
适用专业： 计算机科学与技术
计算机与信息工程学院
2016年3月
1
前 言
数据结构是计算机专业的必修、主干课程之一，它旨在使学生学会分析、研究计算机加工的数据对象的特性，学会把数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算（操作），把现实世界中的问题转化为计算机内部的表示和处理，这是一个良好的环节。为了指导和帮助学生更好地学习、实践数据结构这门课程，我编写了这本实验指导书。
《数据结构实验指导书》列举了数据结构课程设计实例，通过综合训练，能够培养学生实际分析问题、解决问题、编程和动手操作等多方面的能力，最终目的是帮助学生系统地掌握该门课程的基本内容，并运用所学的数据结构知识去解决实际问题。指导书中共有十个实验，内容包括数据结构课程设计概述、线性表、栈、队列、树状结构、图状结构、查找和排序等问题的应用。
《数据结构实验指导书》是一本独立于具体的数据结构教材的辅导书，通过针对每种数据结构的具体实例，循序渐进地启发学生完成设计。书中给出的实例都是完整可运行的，同时给出了测试样例、总结与思考等，辅助学生学习的教学辅导参考书。
2
目 录
实验一：一元二次方程的求解 ....................................................................................................... 1 实验二：线性表—顺序表 ............................................................................................................... 2 实验三：线性表—单链表 ............................................................................................................... 3 实验四： 栈和队列—数制转换 ..................................................................................................... 5 实验五：栈和队列—模拟病人到医院排队看病 ........................................................................... 6 实验六：树—二叉树的建立与遍历 ............................................................................................... 7 实验七：树—二叉树遍历的应用 ................................................................................................... 8 实验八：图—图的建立与遍历 ....................................................................................................... 9 实验九：查找算法设计与实现 ..................................................................................................... 11 实验十：排序算法设计与实现 ..................................................................................................... 12
3
实验一：一元二次方程的求解
一、实验目的：
1、熟悉C语言的上机环境，掌握C语言的基本语法和结构 2、熟悉定义函数和函数声明的方法 3、熟悉函数实参和形参的对应关系 4、学习对文件程序的编译和运行 二、实验内容与步骤：
1、求方程ax2+bx+c=0的解，用3个调用函数实现b2-4ac=0,>0,<0的情况 2、定义三个函数用作主函数的调用 3、编写主函数
三、实验平台与课时安排：
Visual C++ 6.0集成环境；2课时 四、实验设计方案： 1、a=0 不是二次方程
2、b2-4ac>0，有两个不等实根 3、b2-4ac<0，有两个共轭复根 【运行结果】
程序运行结果如图1所示。
图1 程序运行结果
在本算法中，注意三个系数abc的关系，a=0 不是二次方程，b2-4ac>0，有两个不等实根b2-4ac<0，有两个共轭复根。
1
实验二：线性表—顺序表
一、实验目的：
1、会定义线性表的顺序存储结构 2、熟练掌握数组的一些基本操作
3、掌握如何建立一张顺序表，并实现查找操作 4、实现顺序表的插入和删除操作 二、实验内容与步骤：
1、建立一个顺序表，利用一位数组来存储，含有n个数据元素。
2、输出顺序表
3、找到顺序表中第i个元素并输出
4、完成在第ｉ个元素之前插入数据的操作 5、删除顺序表中的第i个元素 三、实验平台与课时安排：
Visual C++ 6.0集成环境；4课时 四、实验设计方案：
1、定义顺序表的数据类型即定义程序工作需要用到的数组和相关变量
2、建立含有n个数据元素的顺序表，数组中的多个元素要多次分别输入，善用循环语句
3、对建立的顺序表设计查找、插入和删除基本操作的算法。
4、查找操作即找到对应位置的元素并输出，插入操作是找到合适位置后则该位置以及该位置后的所有元素均要后移一位，如何实现后移？挪开位置后，把元素放入数组，赋值语句即可。删除操作是找到合适位置后则该位置以及该位置后的所有元素均要前移一位，如何实现前移？ 【运行结果】
程序运行结果如图2和图3所示。
本实验中，建立一个顺序表，利用一维数组来存储和计算相关值并实现插入和删除
2
实验三：线性表—单链表
一、实验目的：
1、熟悉并了解线性表的链式存储结构特性 2、掌握定义单链表的结点类型
3、熟悉对单链表创建，查找，插入，删除等一些基本操作 二、实验内容与步骤：
1、初始化单链表，建立长度为n的单链表并输出
2、完成单链表的插入，查询，删除操作，最后输出链表 三、实验平台与课时安排：
Visual C++ 6.0集成环境；4课时 四、实验设计方案：
1、单链表结点结构如何定义？
eg:
typedef struct Book{
char BName[MAX_BOOK_NAME]; /*book name*/ char AName[MAX_AUTHOR_NAME] ; /*author name*/ int BCode; /*book code*/ float BPrice; /*book price*/ int BNum; /*book num*/ Borrower *next;
}Book,BookList[MAX_BOOK_KIND_NUM];
2、在建立链表前要进行链表的初始化，即创建一个空的单链表，如何创建？提示：空单链表就是只有一个头结点head，头结点指针域为空的单链表。
3、n个结点的单链表要做n次的结点申请、赋值、插入链表。
4、如每次都是把新结点插入到链表最后，要记下链表最后一个结点地址，如何记录？提示：刚刚插入的新结点就是最新的表尾结点。
5、查找给定值的过程就是链表从头到尾一个个结点值依次与给定值比较的过程，循环语句结束条件是什么？一是找到了给定值结点，一是直到链表末尾了也没找到给定值结点。
6、删除指定的p结点，会影响到的是其前驱的指针域，如何记录p的前驱？提示：在一边查找p的过程中就可以一边记录p的前驱。 【运行结果】
程序运行结果如图4所示。
3
图4 程序运行结果
在本算法中，p指针指向a链表的第一个结点（非头结点），即p=a->next，q指针指向链表b的第一个结点，即q=b->next。c指向新链表的头结点。r指针首先指向c的头结点，每次加入两个结点到链表c中，随着新结点的加入，r始终指向链表c的最后一个结点，直到全部结点都加入为止。
4
实验四： 栈和队列—数制转换
一、实验目的：
1、 加深对栈特性的理解，以便在解决实际问题中灵活运用它们。 2、 加深对栈操作实现算法的理解。 3、 熟悉程序调试的方法。
二、实验内容与步骤：
1、绘制程序流程图，编写实验程序，经编译、链接无误后运行； 2、待转换数据存放于数据段，根据自己要求输入； 3、运行程序，然后停止程序； 4、查看转换结果；
5、反复试几组数据，验证程序的正确性。
三、实验平台与课时安排：
Windows xp 操作系统，Visual C++ 6.0集成环境 四、实验设计方案：
1、采用栈的顺序存储结构来实现
2、用stack类来存储数据,实现栈逻辑上的特点”先进后出”. 3、程序中加入对违规操作的预防语句
【运行结果】
程序运行结果如图5所示。
图5 程序运行结果
先进行入栈操作，让低位数先进栈，输出时，高位数先出，这样符合人们的习惯。
5
实验五：栈和队列—模拟病人到医院排队看病
一、实验目的：
1、熟悉并能实现队列的定义和基本操作。 2、了解和掌握队列的应用。 二、实验内容与步骤：
1、编写程序，构造一个链式队列；
2、模拟病人的排队看病，先到先看，使用队列来实现排队过程； 3、运行程序，查看结果；
4、反复试几次，验证程序的正确性。 三、实验平台与课时安排：
Visual C++ 6.0集成环境；2课时 四、实验设计方案：
1、定义链式队列
2、模拟病人的排队看病主要完成以下几个操作： （1）病人把病历本交到护士手中，相当于进队。
（2）排在最前面的病人先看，同时取走病历，这一步相当于出队。 （3）查看排队，从队头到队尾依次显示队列中所有的病历号。 （4）停止排队，退出程序。 【运行结果】
程序运行结果如图6所示。
图6 运行结果
此处判断空队的条件是 front= =NULL，而入队操作的判断条件是 rear= =NULL，两者的区别是前者是针对队列因元素全部出队而为空的情况，后者是针对初始队列为空的情况。
6
实验六：树—二叉树的建立与遍历
一、实验目的：
1.掌握二叉树的逻辑结构；
2.熟练掌握二叉链表存储二叉树的结点定义； 3.学会利用递归方法建立二叉树； 4.学会先、中、后序遍历二叉树。 二、实验内容与步骤：
编写程序，用先序递归的方法建立二叉树。 三、实验平台与课时安排：
Visual C++ 6.0集成环境；2课时 四、实验设计方案：
1.二叉树采用二叉链表存储，用C语言定义二叉链表的结构类型如下：
struct node
{DataType data; /* 定义数据域，DataType代表实际需要的类型 */ struct node *lch; /* 定义左孩子域，指向左孩子地址 */ struct node *rch; /* 定义右孩子域，指向右孩子地址 */ };
typedef struct node bitree; /* 定义二叉树结点类型为bitree */ 2.建立二叉树的先序递归方法
输入扩展先序遍历序列并建立对应的二叉树，输入#表示输入的二叉树元素为空。输入回车键表示输入结束。
3、先序、中序、后序输出当前二叉树。
4、将建立二叉树和遍历二叉树写成子程序，在主程序中调用即可。 【运行结果】
程序运行结果如图7所示。
图7 运行结果
7
实验七：树—二叉树遍历的应用
一、实验目的：
1、掌握二叉树前序、中序、后序遍历的基本方法及应用； 2、会在遍历二叉树基础上对二叉树进行一些运算。 二、实验内容与步骤：
1、建立一棵二叉树、统计二叉树叶子结点个数的程序，输出叶子结点个数。 2、求二叉树的深度。 三、实验平台与课时安排：
Visual C++ 6.0集成环境；4课时 四、实验设计方案：
1、做此实验题目，需要掌握如下知识：二叉树结点定义；建立二叉树；二叉树的遍历，这些在前面一个实验中已经学习。
2、统计叶子结点的个数，或如统计结点个数，查找二叉树中是否存在某个值得结点，交换二叉树所有结点的左右子树，求二叉树的深度等之类的题目，必须建立在遍历的基础上。区别在于访问二叉树时做的不同操作。
3、注意不同的遍历方法访问结点应该处于不同的位置。 4、此实验内容没有要求用何种遍历方法， 【运行结果】
程序运行结果如图8所示。
图8 运行结果
8
实验八：图—图的建立与遍历
一、实验目的：
1、熟练掌握图的邻接表存储结构 2、掌握图邻接表建立和输出算法
3、注意区分邻接表顶点结点以及边结点的表示意义
4、了解在进行边的输入时，输入顺序不一样时，会得到不一样的结果 二、实验内容与步骤：
1、结构体定义邻接表和队列
2、输入顶点和边的信息，构造邻接表并输出 3、采用广度和深度优先遍历算法来遍历图 三、实验平台与课时安排：
Visual C++ 6.0集成环境；6课时 四、实验设计方案：
1、程序中需要定义顶点结点和边结点。注意区分顶点结点和边结点数据域和指针域的代表意义。边结点定义如下：
struct enode /* 定义边结点结构 */ {
int adjvex; /* 边的终点顶点所在位置 */ struct enode *next; /* 指向下一个边结点 */ };
顶点结点定义如下：
struct vnode /* 定义顶点结点结构 */ {
int vertex; /* vertex域存储顶点信息，假设为整型*/ struct enode *first; /* 指向第一个边结点 */ };
2、利用栈（先进后出）队列（先进先出）的特性，分别实现图的深度和广度优先遍历算法。
【运行结果】
程序运行结果如图9所示。
9
图9 运行结果
这里采用顺序队列的形式。
10
实验九：查找算法设计与实现
一、实验目的：
1、掌握折半查找的流程 2、理解折半查找的适应场合
3、给定数列和待查找关键字，知道该关键字应该依次与哪些元素比较 4、掌握折半查找算法 二、实验内容与步骤：
1、输入一有序数列，并采用顺序查找法查找元素，输出找到或者找不到的信息 2、输入一有序数列，并采用折半查找法查找元素，输出找到或者找不到的信息 3、比较两种查找方法的性能 三、实验平台与课时安排：
Visual C++ 6.0集成环境；2课时 四、实验设计方案：
1、定义一维数组存储顺序表；
2、i nput()和output()实现输入输出；
3、BiSearc(int *A, int key, int n)函数来实现折半查找。 4、Search_Seq(int *A, int key ) 函数来实现顺序查找。 【运行结果】
程序运行结果如图10所示。
图10 折半查找运行结果
折半查找算法的平均查找长度是log2(n+1)，时间复杂度是O(log2n)。折半查找法比顺序查找法快得多，但折半查找只能用于有序表，不能用于链表，在必须频繁地向线性表中添加或删除结点的动态应用环境中，这是一个严重的缺点。
11
实验十：排序算法设计与实现
一、实验目的：
1、掌握希尔排序和快速排序流程与原理 2、熟练掌握一趟希尔排序和快速排序算法 3、能理解快速排序递归算法 二、实验内容与步骤：
1、以希尔排序和快速排序为例，实现排序算法并比较性能 2、键盘输入杂乱数列，编写程序进行希尔排序，并输出结果 3、键盘输入杂乱数列，编写程序进行快速排序，并输出结果 三、实验平台与课时安排：
Visual C++ 6.0集成环境；4课时 四、实验设计方案：
1、在希尔排序中将长度为n的待排序表分成若干组，所有相隔为某个“增量”的记录为一组，在各组内进行直接插入排序。
2、希尔提出的增量d1=n/2初始时增量d1较大，分组较多，以后增量逐渐减少，分组减少（每组记录数增多），直到最后增量为1，所有记录为一组，再进行一次整体直接插入排序。
3、在快速排序中，假设待排序序列中，以i指向最小下标，j指向最高下标。以数列第一个元素为控制关键字，即以初始的a[0]为控制关键字。 【运行结果】
程序运行结果如图11所示。
图11 希尔排序运行结果
希尔排序的最后一趟一定是d=1的情况。
12
因篇幅问题不能全部显示，请点此查看更多更全内容