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

《数据结构实验指导书(C版)》由会员分享，可在线阅读，更多相关《数据结构实验指导书(C版)（12页珍藏版）》请在装配图网上搜索。

1、数据结构实验指导书（C 语言版）2017年9月目录1、顺序表的实现 12、链栈的实现 33、前序遍历二叉树 54、图的深度优先遍历算法 75、散列查找 91、顺序表的实现1. 实验目的掌握线性表的顺序存储结构；验证顺序表及其基本操作的实现；理解算法与程序的关系，能够将顺序表算法转换为对应的程序。2. 实验内容建立含有若干个元素的顺序表；对已建立的顺序表实现插入、删除、查找等基本操作。3. 实现提示定义顺序表的数据类型顺序表结构体SeqList,在SeqList基础上实现题目要求的插 入、删除、查找等基本操作，为便于查看操作结果，设计一个输出函数依次输出顺序表的元 素。简单起见，本实验假定线性表

2、的数据元素为int型，要求学生：（1）将实验程序调试通过后，用模板类改写；（2）加入求线性表的长度等基本操作；（3）重新给定测试数据，验证抛出异常机制。4. 实验程序在编程环境下新建一个工程“顺序表验证实验”，并新建相应文件，文件包括顺序表结构/*假设顺序表最多存放100 个元素*/*定义线性表的数据类型，假设为int型*/*存放数据元素的数组*/*线性表的长度*/体 SeqList 的定义，范例程序如下#define MaxSize 100typedef int DataType;typedef structDataType dataMaxSize; int length; SeqList;

3、文件包括建立顺序表、遍历顺序表、按值查找、插入操作、删除操作成员函数的定义范例程序如下：int CreatList（SeqList *L, DataType a , int n）if （n MaxSize） printf（”顺序表的空间不够，无法建立顺序表5）; return 0;for （int i = 0; i datai = ai;L-length = n;return 1;void PrintList(SeqList *L)for (int i = 0; i length; i+)printf(”d ”, L-datai);/*输出线性表的元素值，假设为int型*/int Locate

4、(SeqList *L, DataType x)for (int i = 0; i length; i+)if (L-datai = x) return i+1;/*返回序号*/return 0;/*退出循环，说明查找失败*/int Insert(SeqList *L, int i, DataType x)if (L-length = MaxSize) printf( 上溢错误，插入失败5); return 0;if (i L-length + 1) printf( 位置错误，插入失败5); return 0;for (int j = L-length; j = i; j-)/*j 表示元素序

5、号*/L-dataj = L-dataj - 1;L-datai - 1 = x;L-length+;return 1;int Delete(SeqList *L, int i, DataType *ptr)if (L-length = 0) printf(” 下溢错误，删除失败n); return 0;if (i L-length) printf(位置错误，删除失败n); return 0;*ptr = L-datai - 1;/*取出位置 i 的元素*/for (int j = i; j length; j+)/* j 表示元素所在数组下标*/L-dataj - 1 = L-dataj;L

6、-length-;return 1;在定义了顺序表的存储结构 SeqList 并实现了基本操作后，程序中就可以使用 SeqList类型来定义变量，可以调用实现基本操作的函数来完成相应的功能。范例程序如下：#include #include /*将顺序表的存储结构定义和各个函数定义放到这里*/int main( )int r5 = 1, 2, 3, 4, 5, i, x;SeqList L;/*定义变量 L 为顺序表类型*/Creat(&L, r, 5);/*建立具有 5 个元素的顺序表*/printf(”当前线性表的数据为：)；PrintList(&L);/*输出当前线性表1 2 3 4 5*

7、/Insert(&L, 2, 8);/*在第 2 个位置插入值为 8 的元素*/printf(“执行插入操作后数据为：)；PrintList(&L);/*输出插入后的线性表1 8 2 3 4 5*/printf(当前线性表的长度为：%dn, Length(&L);/*输出线性表的长度6*/printf(请输入查找的元素值：)；scanf(%d, &x);i = Locate(&L, x);if (0 = i) printf(查找失败n);else printf(元素d 的位置为：%dn, x, i);printf(请输入查找第几个元素值：, &i);scanf(%d, &i);if (Get(

8、&L, i, &x) = 1) printf(第小个元素值是%dn, i, x);else printf(”线性表中没有第小个元素n, i); printf(“请输入要删除第几个元素：); scanf(%d, &i);if (Delete(&L, i, &x) = 1) /*删除第 i 个元素*/printf(”删除第小个元素是%d，删除后数据为：,i, x);PrintList(&L);/*输出删除后的线性表*/else printf(删除操作失败5); return 0;2、链栈的实现1. 实验目的掌握栈的链接存储结构； 验证链栈及其基本操作的实现；验证栈的操作特性。2. 实验内容建立一个

9、空栈；对已建立的栈进行插入、删除、取栈顶元素等基本操作。3. 实现提示定义链栈中的结点结构(链栈中结点结构基于单链表相同)，定义链栈的数据类型链栈结构体，包括入栈、出栈、取栈顶元素等基本操作。本节的实验采用模板实现，要求学 生：（1）假设栈元素为字符型，修改主函数； （2）重新设计测试数据，考查栈的上溢、下溢等情况，修改主函数。4. 实验程序在编程环境下新建一个工程“链栈验证实验”，并新建相应文件，文件包括链栈结构体的 定义，范例程序如下：typedef int DataType;/*栈兀素的数据类型，假设为int型*/typedef struct Node DataType data;str

10、uct Node*next; Node;/*存放栈元素的数据域*/*存放下一个结点的地址*/Node *top;/*栈顶指针*/文件包括链栈初始化、入栈、出栈、获取栈顶元素、判空操作成员函数的定义，范例程序如下：void InitStack（Node *top）top = NULL;void Push(Node *top, DataType x)Node *s = (Node *)malloc(sizeof(Node);/*申请一个结点 s*/s-data = x;s-next = top; top = s;/*将结点 s 插在栈顶*/int Pop(Node *top, DataType *

11、ptr)Node *p = top;if (top = NULL) printf(下溢错误，删除失败n); return 0; *ptr = top-data;/*存储栈顶元素*/top = top-next;/*将栈顶结点摘链*/free(p);return 1;int GetTop(Node *top, DataType *ptr)if (top = NULL) printf(下溢错误，取栈顶失败n); return 0; *ptr = top-data; return 1;int Empty(Node *top)if (top = NULL) return 1;/*栈空则返回 1*/el

12、se return 0; 在定义了链栈的存储结构并实现了基本操作后，可以调用实现基本操作的函数来完成相 应的功能。范例程序如下：#include #include #include /*将单链表的结点结构定义和链栈的各个函数定义放到这里*/int main( )DataType x;Node *top = NULL;/*定义链栈的栈顶指针并初始化*/InitStack(top);/*初始化链栈*/printf(对15和10执行入栈操作，)；Push(top, 15);Push(top, 10);if (GetTop(top, &x) = 1)printf(当前栈顶元素为：%dn, x);/*输

13、出当前栈顶元素10*/if (Pop(top, &x) = 1)printf(”执行一次出栈操作，删除元素：%dn , x);/*输出出栈元素10*/if (GetTop(top, &x) = 1)printf(当前栈顶元素为：dn, x);/*输出当前栈顶元素15*/printf(请输入待插入元素：)；scanf(%d, &x);Push(&S, x);if (Empty(top) = 1)printf(栈为空 n);elseprintf(”栈非空n);/*栈有2个元素，输出栈非空*/DestroyStack(top);return 0;3、前序遍历二叉树1. 实验目的掌握二叉树的逻辑结构；

14、掌握二叉树的二叉链表存储结构；验证二叉树的二叉链表存储及遍历操作。2. 实验内容建立一棵含有n个结点的二叉树，采用二叉链表存储；输出前序遍历该二叉树的遍历结果。3. 实现提示定义二叉树的数据类型二叉树结点结构体BiNode，在BiNode基础上实现题目要求的建立二叉链表、前序遍历等基本操作。建立二叉链表可以采用扩展二叉树的一个遍历序列例如前序序列，将扩展二叉树的前序序列由键盘输入，建立该二叉树的二叉链表存储。简单起见，本实验假定二叉树的数据元素为char型，要求学生：(1) 将实验程序调试通过后，用模板类改写；(2) 加入层序遍历二叉树等基本操作。4. 实验程序在编程环境下新建一个工程“二叉链

15、表验证实验”，并新建相应文件，文件包括二叉树结构体的定义，范例程序如下：typedef char DataType;typedef struct BiNodeDataType data;struct BiNode *lchild, *rchild; BiNode;BiNode *root;文件包括建立二叉链表、前序遍历操作成员函数的定义，范例程序如下：BiNode* CreatBiTree(BiNode*root)char ch;cin ch;/*输入结点的数据信息*if (ch = # ) root = NULL;/*递归结束，建立一棵空树*/else root = (BiNode *)ma

16、lloc(sizeof(BiNode);/*生成新结点*/root-data = ch;/*新结点的数据域为 ch*/root-lchild = Creat(root-lchild);/*递归建立左子树*/root-rchild = Creat(root-rchild);/*递归建立右子树*/return root;void PreOrder(BiNode*root)/*递归调用的结束条件*/*访问根结点的数据域，为 char 型*/ /*前序递归遍历 root 的左子树*/ /*前序递归遍历 root 的右子树*/if (root = NULL) return;else printf(%c

17、, root-data);PreOrder(root-lchild);PreOrder(root-rchild);在定义了二叉树的存储结构并实现了基本操作后，可以调用实现基本操作的函数来完成 相应的功能。范例程序如下：#include #include #include /*将二叉链表的结点结构定义和各个函数定义放到这里*/ int main( )BiNode *root = NULL;/*定义二叉树的根指针变量*/root = CreatBiTree(root);/*建立一棵二叉树*/printf(”该二叉树的根结点是：%cn, root-data);printf(n该二叉树的前序遍历序列是

18、：);PreOrder(root);return 0;4、图的深度优先遍历算法1. 实验目的掌握图的逻辑结构；掌握图的邻接矩阵存储结构； 验证图的邻接矩阵存储及其深度优先遍历操作的实现。2. 实验内容建立无向图的邻接矩阵存储；对建立的无向图，进行深度优先遍历3. 实现提示定义邻接矩阵存储的无向图结构体MGraph,在其基础上实现题目要求的图建立、深度 优先遍历等基本操作。4. 实验程序在编程环境下新建一个工程“图的深度优先遍历验证实验”，并新建相应文件，文件包括/*假设图中最多顶点个数*/*图中顶点的数据类型，假设为char型*/*定义邻接矩阵存储结构*/*存放顶点的一维数组*/*存放边的二维

19、数组*/*图的顶点数和边数*/图的邻接矩阵结构体MGraph的定义，范例程序如下:#define MaxSize 10 typedef char DataType;typedef structDataType vertexMaxSize; int edgeMaxSizeMaxSize; int vertexNum, edgeNum; MGraph;文件包括建立图、图的深度优先遍历操作成员函数的定义，范例程序如下:void CreatGraph(MGraph *G, DataType a , int n, int e) int i, j, k;/*存储顶点信息*/*初始化邻接矩阵*/*依次输入每

20、一条边*/*输入边依附的顶点编号*/*置有边标志*/G-vertexNum = n; G-edgeNum = e; for (i = 0; i vertexNum; i+)G-vertexi = ai;for (i = 0; i vertexNum; i+)for (j = 0; j vertexNum; j+)G-edgeij = 0;for (k = 0; k edgeNum; k+)scanf(%d%d, &i, &j);G-edgeij = 1; G-edgeji = 1; void DFraverse(MGraph *G, int v) /*全局数组变量 visitedn已初始化为

21、0*/printf(%c , G-vertexv); visitedv = 1;for (int j = 0; j vertexNum; j+)if (G-edgevj = 1 & visitedj = 0) DFSTraverse(G, j);在定义了图的邻接矩阵存储结构并实现了基本操作后，可以调用实现基本操作的函数来完成相应的功能。范例程序如下:#include #include int visitedMaxSize=0;/*全局数组变量 visited 初始化*/*把邻接矩阵的存储结构定义和各个函数定义放到这里*/int main( )int i;char ch =A,B,C,D,E;M

22、Graph MG;CreatGraph(&MG, ch, 5, 6);/*建立具有 5 个顶点 6 条边的无向图*/for (i = 0; i MaxSize; i+)visitedi = 0;printf(深度优先遍历序列是：”)；DFTraverse(&MG, 0);/*从顶点 0出发进行深度优先遍历*/return 0；5、散列查找1. 实验目的掌握散列查找的基本思想； 掌握闭散列表的构造方法；掌握线性探测处理冲突的方法； 验证散列技术的查找性能。2. 实验内容对于给定的一组整数和散列函数，采用线性探测法处理冲突构造散列表； 设计查找算法，验证查找性能。3. 实现提示首先将待查找集合存储

23、到闭散列表 ht 中，然后随机生成待查元素的下标，考查在查找成功 情况下的比较次数。4. 实验程序 由于程序比较简单，使用单文件结构即可。新建文件“散列查找”，注意从下标 0 开始存 放待查找元素，范例程序如下：int HashSearch1(int ht , int m, int k, int *p) /*形参 p 传指针，返回位置*/int i, j, flag = 0；/*flag=0 表示散列表未满*/j = H(k);i = j;while (hti != 0 & flag = 0)if (hti = k) *p = i; return 1;else i = (i + 1) % m;if (i = j) flag = 1;if (flag = 1) printf(溢出 ”)；exit(-l);else hti = k; *p = i; return 0;/*计算散列地址*/*记载比较的起始位置*/*比较若干次查找成功*/*向后探测一个位置*/*表已满*/*表满，产生溢出*/*比较若干次查找不成功，插入*/