数据结构试验指导书修订版

1、数据结构实验指导书郑州轻工业学院实验01顺序表的基本操作实验02单链表的基本操作 19实验03栈的基本操作32实验04队列的基本操作35实验树的基圭操隹3840实验06哈夫曼编码实验07图的两种存储和遍历42实验08最小生成树、拓扑排序和最短路径.46实验09二叉排序树的基本操作48的生成50实验11常用的内部排序算法5254附：实验报告模板前言数据结构是计算机相关专业的一门核心基础课程，是编译原理、操作系统、数拯库系统及其 它系统程序和大型应用程序开发的重要基础，也是很多高校考研专业课之一。它主要介绍线性结构、 树型结构、图状结构三种逻借结构的特点和在计算机内的存储方法，并在此基础上介绍一些

2、典型算 法及英时、空效率分析。这门课程的主要任务是研究数据的逻辑关系以及这种逻辑关系在讣算机中 的表示、存储和运算，培养学生能够设计有效表达和简化算法的数据结构,从而提高其程序设计能力。 通过学习，要求学生能够掌握各种数据结构的特点、存储表示和典型算法的设汁思想及程序实现，能 够根据实际问题选取合适的数据表达和存储方案，设il岀简洁、髙效、实用的算法，为后续课程的 学习及软件开发打下良好的基础。另外本课程的学习过程也是进行复杂程序设计的训练过程,通过算 法设计和上机实践的训练，能够培养学生的数据抽象能力和程序设汁能力。学习这门课程，习题和实 验是两个关键环节。学生理解算法，上机实验是最佳的途径

3、之一。因此，实验环节的好坏是学生能 否学好数据结构的关键。为了更好地配合学生实验，特编写实验指导书。、实验目的本课程实验主要是为了原理和应用的结合，通过实验一方而使学生更好的理解数拯结构的概念 和常用的几种数据结构在计算机中的存储和实现的方法，加强学生动手能力：另一方而培养学生从 实际问题中抽象岀对应的抽象数搦类型，进而找到合适的计算机存储方法和算法，为以后课程的学 习、大型软件的开发、实际工程问题打下良好的软件开发基础。二、实验要求1、每次实验前学生必须根据实验内容认真准备实验程序及调试时所需的输入数据。2、在指导教师的帮助下能够完成实验内容，得岀正确的实验结果。3、实验结朿后总结实验内容、

4、书写实验报告。4、遵守实验室规章制度、不缺席、按时上、下机。5、实验学时内必须做数据结构的有关内容，不允许上网聊天或玩游戏，如发现上述现象，取 消本次上机资格，平时成绩扣10分。6、实验报告有一次不合格，扣5分，两次以上不合格者，平时成绩以零分记。三、实验环境VC+或其他C+相关的编译环境。四、说明1、本实验的所有算法中元素类型应根据实际需要合理选择。2、实验题目中带次者为较高要求，学生可自选：其余部分为基本内容，应尽量完成（至少完成 70%,否则实验不合格）。3、数拯结构是很多髙校的硕士研究生入学考试的专业课之一，希望有志于考研的学生能够在 学习过程中注意各种算法的理解，以便为考研做一左的准

5、备。4、好的算法决左了好的程序，要有效地实现算法，就需要设计能够有效表达和简化算法的数据 结构，因此数据结构是有效进行程序设计的基础，是每个程序员的必修课。五、实验报告的书写要求1、明确实验的目的及要求。2、记录实验的输入数据和输出结果。3、说明实验中岀现的问题和解决过程。4、写出实验的体会和实验过程中没能解决的问题。5、实验程序请构建为多文件程序，每一个算法对应的函数原型声明存放在头文件*.h中，对应 的函数实现存放在源文件*.c中；main。函数存放在另一个源文件中，该文件包含头文件*.h即 可。六、成绩考评办法1、期末考试占70分，闭卷。2、平时考评占30分。其中实验环肖占20分（实验准

6、备、上机、报告、验收等）：平时占10分 （出勒、作业、测验等）。七、参考书目1、数据结构（C语言版）严蔚敏等淸华大学岀版社。2、数据结构题集（C语言版）严蔚敏等淸华大学出版社。3、数据结构与算法分析一语言描述，Mark Allen Weiss著，机械工业出版社，2012。实验01顺序表的基本操作实验学时：2学时实验类型：上机背景知识：顺序表的插入、删除及应用。目的要求：1. 掌握顺序存储结构的特点。2. 掌握顺序存储结构的常见算法。实验内容：编写一个完整的程序，实现顺序表的生成、插入、删除、输岀等基本运算。（1）建立一个顺序表，含有n个数据元素。（2）输岀顺序表。（3）在顺序表中删除值为x的结

7、点或者删除给左位置i的结点。（4）实现把该表中所有奇数排在偶数之前，即表的前面为奇数，后而为偶数。（5）输入整型元素序列，利用有序表插入算法建立一个有序表。（6）*利用算法5建立两个非递减有序表A和B,并把它们合并成一个非递减有序表Co（7）在主函数中设计一个简单的菜单，分别测试上述算法。（8）*综合训练：利用顺序表实现一个班级学生信息管理（数据录入、插入、删除、排序、查找等）。实验说明：1请构建多文件程序，算法1至算法6对应的函数原型声明存放在头文件中，对应的函数实现 存放在源文件中：mainO函数存放在另一个源文件中，该文件包含头文件即可。2.类型定义define MAXSIZE 100

8、立顺序表n）;printf （/zttt2.遍历顺序表n）;printf （，zttt3.删除第 i 个元素n）;printf （/zttt4.删除值为 x 的元素n）;printf （，zttt5.奇数排在偶数之前n）;printf （/zttt6.插入法生成递增有序表n）;printf （z/ttt7.两个非递减有序表La和Lb合并成非递减有序表Lcn）;printf （/ztttO.退岀nn）;/*初始化顺序表*/Status InitList_Sq(SqList &L, int n)=(ElemType*)malloc(n*sizeof(ElemType); if(! exit(OVE

9、RFLOW):二0；=n;return OK;/*建立顺序表*/Status CreateList_Sq(SqList &L)int n, i;printfCin输入顺序表长度：”)；scanf f &n);if(InitList_Sq(L, n)printfC请输入%d个元素：，n);for(i = 0; i n; i卄)scanf (，y%dz，, & i);+；return OK;elsereturn ERROR;/*输出顺序表*/void PrintList_Sq(SqList L)int i;printff顺序表中元素为：n);for(i 二 0; i ; i卄)printf (%d

10、 ”，i);printf(n);/*删除第i个元素*/Status D亡leteList_Sq(SqList &L, int i, ElemType &e)ElemType *p, *q;if( (i ) return ERROR;p = &1-lD ；e = *P；q 二 +；for(+p; p = q; +p) *(p-1)二 *p;Treturn OK;/*删除值为X的元素，删除成功返回OK,删除失败返回ERROR*/Status DeleteListX_Sq(SqList &L, ElemType x)El亡mType*q;/*奇数排在偶数之前*/Status AdjustList_S

11、q(SqList &L)ElemType *p, *q;int temp;return OK;/*插入法生成递增有序表，有序表生成成功返回OK,失败返回ERROR*/Status OrderList_sq(SqList &L, int n)int i, j, x; /*x表示每次待插入的元素*/*两个非递减有序表A和B,并把它们合并成一个非递减有序表C*/void MergeList_Sq(SqList La, SqList Lb, SqList &Lc )ElemType *pa, *pb, *pc, *pa_last, *pb_last;pa 二；pb 二；二二 +；pc = = (Ele

12、mType *)malloc * sizeof(ElemType);辻(! exit (OVERFLOW);pa_last = + - 1;pb_last = + - 1;while (pa = pa_last & pb = pb_last)if (*pa = *pb) *pc+ = *pa+;else *pc+ = *pb+;while (pa = pa_last) *pc+ = *pa+；while(pb = pb_last) *pc+ = *pb+;includeint mainOint choice, n, i, x;SqList L, La, Lb, Lc;while (1)menu

13、O ;printf(*选择你的操作：”)；scanf(“%d, &choice);switch(choice)case 1:if(CreateList_Sq(L)printf C顺序表创建成功n);elseprintf C顺序表创建失败n); break;case 2：PrintList_Sq(L);break;case 3:printf(请输入删除元素的位置：”)； scanf (/z%dz &i);if(DeleteList_Sq(L, i, x)printf r被删除元素值为：%dn， x); elseprintf C删除失败n)；break;case 4:printff请输入删除元素值

14、：)； scanf (/z%dz &x);if(DeleteListX_Sq(L, x)printf (/z删除成功n);else printf C删除失败n);PrintList_Sq (L);break;case 5:AdjustLi st_Sq(L);printf (，z新链表为:n);PrintList_Sq (L);break;case 6:printfCIh输入顺序表长度：”)；scanf&n);if(OrderList_sq(L, n)printf r值有序顺序表为:n*);PrintList_Sq(L);elseprintf C顺序表创建失败n);break;case 7:pr

15、intf (请输入顺序表La的长度：*);scanf (/z%dz &n);OrderList_sq(La, n);printf (请输入顺序表Lb的长度：*);scanf (，z%dz &n);OrderList_sq(Lb, n);MergeList_Sq(La, Lb, Lc);printf (w合并后的顺序表为：n);PrintList_Sq(Lc);break;case 0：return 0;default:printf （，z输入错误，请重新输入n）;实验02单链表的基本操作实验学时：2学时实验类型：上机背景知识：单链表的插入、删除及应用。目的要求：1. 掌握单链表的存储特点及其实

16、现。2. 掌握单链表的插入、删除算法及苴应用算法的程序实现。实验内容：编写一个完整的程序，实现单链表的生成、插入、删除、输出等基本操作。（1）随机产生或键盘输入一组元素，建立一个带头结点的单向链表（无序）。（2）计算单链表的长度，颯历单链表。（3）把单链表中的元素逆置（不允许申请新的结点空间）。（4）在单链表中删除所有值为偶数的元素结点。（5）编写在非递减有序单链表中插入一个元素使链表元素仍有序的函数，并利用该函数建 立一个非递减有序单链表。（6）*利用算法5建立两个非递减有序单链表，然后合并成一个非递增有序链表。next=NULL;return OK;/*尾插法建立单链表*/Status C

17、reat_Linklist(LinkList &L)int x;LinkList p, rear;Init_Linklist (L);rear = L;printf C输入T表示输入结朿n);while(scanf (，z%d/z, &x), x != T)p = (LinkList)malloc(sizeof(Lnode);if(!p) return ERROR;p-data = x;rear-next = p;rear = p;rear-next = NULL;return OK;/*单链表遍历*/void DispLinklist(LinkList L)LinkList p;p = L-

18、next;while (p)printf (z/%d 、p-data);p = p-next;printf(n);/*计算单链表长度*/int length_Linklist(LinkList L)int count二0;/*count表示单链表长度*/LinkList p;return count;/*单链表逆宜*/void Reverse Linklist (LinkList L)LinkList p, q/*删除值为偶数的结点*/void DelEven_Linklist(LinkList L)LinkList p, q;/*在有序单链表中插入元素，链表仍然有序，插入成功返回0K,插入失

19、败返回ERROR*/Status Insert_Linklist(LinkList L, int x)9/*创建非递减有序单链表，创建成功返回OK,创建失败返回ERROR*/Status CreatOrder_Linklist(LinkList &L)/*两个非递减有序单链表La和Lb合并成一个非递增有序链表Lc*/void MergeDescend_Linklist(LinkList La, LinkList Lb, LinkList &Lc)/*两个非递减有序单链表La和Lb合并成一个非递减有序链表Lc*/void MergeAscend_Linklist(LinkList La, Lin

20、kList Lb, LinkList &Lc)LinkList pa, pb, pc;pa = La-next;pb = Lb-next;pc = Lc = La;while(pa & pb)if(pa-data data)pc-next = pa; pc = pa; pa = pa-next:elsepc-next = pb; pc = pb; pb = pb-next:pc-next = pa pa ： pb;free (Lb);/*链表La按值分解成两个链表，La全部为奇数，Lb全部为偶数*/void Split_Linklist(LinkList La, LinkList &Lb)in

21、clude int mainOint choice, length;LinkList L, La, Lb, Lc;while (1)menu 0 ;printf(*选择你的操作：”)；scanf&choice);switch(choice)case 1:if(Creat_Linklist(L)printf C单链表创建成功n);elseprintf r单链表创建失败n);break;case 2：Disp_Linklist(L);break;case 3:length = length_Linklist(L);printf (w单链表长度为：dn, length);break;case 4:R

22、everse_Linklist(L);printff逆置后的链表为：)；Disp_Linklist(L);break;case 5:DelEven_Linklist(L);printf (w新链表为:n);Disp_Linklist(L);break;case 6:if(CreatOrder_Linklist(L)printf r值有序链表为：n);Disp_Linklist(L);elseprintf (z/单链表创建失败n);break;case 7:CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeDescend_Linklist(

23、La, Lb, Lc);printf (合并后的新链表为：n) ;Disp_Linklist (Lc); break;case 8：CreatOrder_Linklist(La);CreatOrder_Linklist(Lb);MergeAscend_Linklist(La, Lb, Lc);printf (合并后的新链表为：n) ;Disp_Linklist (Lc); break;case 9：Creat_Linklist(L);Split_Linklist(L, Lb);printfC分裂后的新链表为：n);Disp_Linklist(L);Disp_Linklist(Lb);break

24、;case 0：return 0;default:printf (z，输入错误，请重新输入n);实验03栈的基本操作实验学时：2学时实验类型：上机背景知识：顺序栈、链栈，入栈、出栈。目的要求:1. 掌握栈的思想及其存储实现。2. 掌握栈的常见算法的程序实现。实验内容：（1）采用顺序存储实现栈的初始化、入栈、出栈操作。（2）采用链式存储实现栈的初始化、入栈、岀栈操作。（3）在主函数中设计一个简单的菜单，分别测试上述算法。（4）*综合训练：1）堆栈操作合法性：假设以S和X分别表示入栈和岀栈操作。如果根据一个仅由S和X构成 的序列，对一个空堆栈进行操作，相应操作均可行（如没有岀现删除时栈空）且最后状

25、态 也是栈空，则称该序列是合法的堆栈操作序列。请编写程序，输入S和X序列，判断该序 列是否合法。2）括号匹配检验：假设表达式中允许包括两种括号：圆括号和方括号，其嵌套的顺序随意， 即（ 0）或（）等为正确的格式，（）或（）等均为不正确格式。输入一个表达 式，判断其中的括号是否能正确匹配。3）表达式转换：算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。日常使用的算 术表达式是采用中缀表示法，即二元运算符位于两个运算数中间。请设计程序将中缀表达 式转换为后缀表达式。输入在一行中给出不含空格的中缀表达式，可包含+、-、*、以及 左右括号（），表达式不超过20个字符。在一行中输岀转换后的后缀表达

26、式，要求不同对象（运算数、运算符号）之间以空格分隔，但结尾不得有多余空格。实验说明：1. 类型泄义顺序栈示例#define MAX 100 xt格式存储，统计该文件中各种字符的频率，对各字符进行Huffman编码， 将该文件翻译成Huffman编码文件，再将Huffman编码文件翻译成源文件。实验说明：1. 参考类型泄义 双亲孩子表示法typedef struct unsigned int weight;unsigned int parent, lchild, rchild; HTNode, *HuffmanTree;/动态分配数组存储哈夫曼树typedef char * * HuffmanC

27、ode; /动态分配数组存储哈夫曼编码表注意问题：1 递归算法的灵活应用。2. 多级指针的使用。实验07图的两种存储和遍历实验学时：2学时实验类型：上机背景知识：图的存储、遍历及英应用。目的要求：1. 掌握图的存储思想及其存储实现。2. 掌握图的深度、广度优先颯历算法思想及其程序实现。实验内容：（1）键盘输入数拯，分别建立一个有向图和一个无向图的邻接表。（2）输出该邻接表。（3）在有向图的邻接表的基础上计算各顶点的度，并输出。（4）采用邻接表存储实现无向图的深度优先遍历。（5）采用邻接表存储实现无向图的广度优先遍历。（6）在主函数中设计一个简单的菜单，分别调试上述算法。（7）*综合训练地下迷宫

28、探索：假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道 的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到 起点输入格式:输入第一行给岀三个正整数，分别表示地下迷宫的廿点数N （KNIOOO,表示通道所有交 叉点和端点）、边数M（M3000,表示通道数）和探索起始肖点编号S （ *ij点从1到N编号）。 随后的H行对应M条边（通道），每行给出一对正整数，分別是该条边直接连通的两个节点的 编号。输出格式:若可以点亮所有节点的灯，则输岀从S开始并以S结束的包含所有节点的序列，序列中相邻的节点一赵有边（通道）；否则虽然不能点亮所有节点的灯，但还是输

29、出点亮部分灯的怜点序列，最后输岀0,此时表示迷宫不是连通图。由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约左以肖 点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。 输入样例：6 8 11 22 33 44 55 66 43 61 5输出样例：12345654321实验说明：1. 类型左义（邻接表存储）define MAX.VERTEX.NUM 20 /顶点最大个数typedef struct ArcNodeintadjvex:struct ArcNode *nextarc;intweight; /边的权值 ArcNode; /表结点

30、define VertexType int /顶点元素类型typedef struct VNodeVertexType data;ArcNode *firstarc;VNode, AdjListMAX_VERTEX_NUM; /typedef struct!AdjList vertices;int vexnum, arc num; /顶点的实际数，边的实际数int kind;ALGraph;2. 上述类型怎义可以根据实际情况适当涮整。3算法4、5分别利用栈、队列实现非递归算法。 注意问题：1. 注意理解各算法实现时所采用的存储结构。2. 注意区别正.逆邻接。实验08最小生成树、拓扑排序和最短路

31、径实验学时：2学时实验类型：上机背景知识：图的存储、遍历及英应用。目的要求：掌握图的常见应用算法的思想及其程序实现。实验内容：（1）键盘输入数据，分别建立一个有向图的邻接表和一个无向图的邻接矩阵。（2）输岀该邻接表和邻接矩阵。（3）以有向图的邻接表为基础输岀它的拓扑排序序列。（4）以无向图的邻接矩阵为基础实现最小生成树的PRIM算法。（5）以有向图的邻接矩阵为基础实现Dijkstra算法输岀单源点到其它顶点的最短路径。（6）在主函数中设计一个简单的菜单，分别调试上述算法。（7）*综合训练：校园导航1）问题描述：在给岀校园各主要建筑的名称信息及有路线连通的建筑之间的距离（或行进时间）的基础上，

32、利用校园导航系统汁算出给泄的起点到终点之间距离最近（或行进时间最短）的行进路线。2）设讣要求：文件读入或键盘方式读入校园主要建筑信息及建筑间的距离（或行进时间）信息。 创建完地图后，以文件形式保存，以免重复创建。计算出给左的起点到终点之间距离最近（或行进 时间最短）的行进路线，并输岀该路线（包括经过哪些建筑）及苴总距离（或总行进时间）。 实验说明：1. 类型定义邻接表存储见实验07邻接矩阵存储示例define MAX_VERTEX_NUM 20 /顶点最大个数typedef enum DG, DN, UDG, UDN GraphKind;typedef struct ArcCellVRType

33、 adj;intweight; /边的权值ArcCell; AdjMatrixMAX.VERTEX.NUM MAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;intvexnum, arcnum; /顶点的实际数，边的实际数GraphKind kind;MGraph;注意问题：注意理解各算法实现时所采用的存储结构。实验09二叉排序树的基本操作实验学时：2学时实验类型：上机背景知识：树表查找。目的要求：掌握二叉排序树、AVL树的查找、插入、删除、建立算法的思想及程序实现。实验内容：（1）随机产生一组

34、关键字，利用二叉排序树的插入算法建立二叉排序树，然后删除某一指泄关键字元素。2）*建立AVL树并实现删除某一指泄关键字元素。（3）*综合训练： 树种统计随着卫星成像技术的应用，自然资源研究机构可以识别每一棵树的种类。请编写程序帮助研究 人员统计每种树的数量，计算每种树占总数的百分比。首先输入正整数N （W105）,随后N行，每 行给出卫星观测到的一棵树的种类名称。种类名称由不超过30个英文字母和空格组成（不区分大小 写）。按字典序递增输出各种树的种类名称及苴所占总数的百分比，英间以空格分隔，每种树的信 息占一行。实验说明：1. 存储定义参见实验05二叉链表的存储。2. 各种关键字数据输入可利用

35、随机函数自动产生，以便丹省上机时间。注意问题：1. 注意建立二叉排序树时相同元素的处理。2. 注意理解动态查找概念。实验10哈希表的生成实验学时：2学时实验类型：上机背景知识：哈希查找。目的要求：掌握哈希存储结构的思想，能选择合适的哈希函数，实现不同冲突处理方法的哈希表的査找、 建立。实验内容：（1）设计哈希函数及处理冲突的方法；（2）键盘输入数据，利用设计的哈希函数及线性探测法生成哈希表：（3）用同样的输入数据和哈希函数，用链地址法处理冲突生成哈希表：（4）在主函数中设计一个简单的菜单，分别调试上述算法：（5）分析两种方法的平均查找长度。（6）*综合训练：QQ帐户的申请与登陆首先输入一个正整

36、数N （W10J ,随后给出N行指令。每行指令的格式为：“命令符（空格） QQ号码（空格）密码”。其中命令符为“N”（代表New）时表示要新申请一个QQ号，后而是新帐 户的号码和密码；命令符为L”（代表Login）时表示是老帐户登陆，后而是登陆信息。QQ号码为 一个不超过10位、但大于1000 （据说QQ老总的号码是1001）的整数。密码为不小于6位、不超过 16位、且不包含空格的字符串。针对每条指令，给出相应的信息：1）若新申请帐户成功,则输出“New: OK” :2）若新申请的号码已经存在,则输出“ERROR: Exist” ；3）若老帐户登陆成功，则输出“Login： OK” ；4）若老