数据结构实验指导书
（C语言版）
2017年9月
目录
1、顺序表的实现 ......................................................................................................... 1 2、链栈的实现 ............................................................................................................. 3 3、前序遍历二叉树 ..................................................................................................... 5 4、图的深度优先遍历算法 ......................................................................................... 7 5、散列查找 ................................................................................................................. 9
1
1、顺序表的实现
1. 实验目的
⑴掌握线性表的顺序存储结构； ⑵验证顺序表及其基本操作的实现；
⑶理解算法与程序的关系，能够将顺序表算法转换为对应的程序。 2. 实验内容
⑴建立含有若干个元素的顺序表；
⑵对已建立的顺序表实现插入、删除、查找等基本操作。 3. 实现提示
定义顺序表的数据类型——顺序表结构体SeqList，在SeqList基础上实现题目要求的插入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元素。简单起见，本实验假定线性表的数据元素为int型，要求学生：
（1）将实验程序调试通过后，用模板类改写； （2）加入求线性表的长度等基本操作； （3）重新给定测试数据，验证抛出异常机制。 4. 实验程序
在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构体SeqList的定义，范例程序如下：
#define MaxSize 100 /*假设顺序表最多存放100个元素*/
typedef int DataType; /*定义线性表的数据类型，假设为int型*/ typedef struct {
DataType data[MaxSize]; /*存放数据元素的数组*/ int length; /*线性表的长度*/ } SeqList;
文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义，范例程序如下：
int CreatList(SeqList *L, DataType a[ ], int n) {
if (n > MaxSize) {printf(\顺序表的空间不够，无法建立顺序表\\n\ for (int i = 0; i < n; i++)
L->data[i] = a[i]; L->length = n; return 1; }
1