数据结构实验指导书(C版)

数据结构实验指导书

（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

void PrintList(SeqList *L) {

for (int i = 0; i < L->length; i++)

printf(\ /*输出线性表的元素值，假设为int型*/ }

int Locate(SeqList *L, DataType x) {

for (int i = 0; i < L->length; i++)

if (L->data[i] == x) return i+1; /*返回序号*/

return 0; /*退出循环，说明查找失败*/ }

int Insert(SeqList *L, int i, DataType x) {

if (L->length >= MaxSize) {printf(\上溢错误，插入失败\\n\if (i < 1 || i > L->length + 1) {printf(\位置错误，插入失败\\n\for (int j = L->length; j >= i; j--) /*j表示元素序号*/ L->data[j] = L->data[j - 1]; L->data[i - 1] = x; L->length++; return 1; }

int Delete(SeqList *L, int i, DataType *ptr) {

if (L->length == 0) {printf(\下溢错误，删除失败\\n\ if (i < 1 || i > L->length) {printf(\位置错误，删除失败\\n\ *ptr = L->data[i - 1]; /*取出位置i的元素*/

for (int j = i; j < L->length; j++) /* j表示元素所在数组下标*/ L->data[j - 1] = L->data[j]; L->length--; return 1; }

在定义了顺序表的存储结构SeqList并实现了基本操作后，程序中就可以使用SeqList类型来定义变量，可以调用实现基本操作的函数来完成相应的功能。范例程序如下：

#include #include

/*将顺序表的存储结构定义和各个函数定义放到这里*/ int main( ) {

int r[5] = {1, 2, 3, 4, 5}, i, x;

2