《数据结构》实验书

1、数据结构实验指导书潘向辉/吴学毅编写印包学院数字媒体技术专业2011年3月实验说明【实验环境】操作系统：Microsoft Windows XP/2000?编程语言:C语言【实验要求】1. 实验前，了解实验目的？实验内容及相关的基本理论知识，并按照实验内容要求设计程序流程 ，书写预习报告；2. 本课程实验均为单人单组，独立完成；3. 实验所用计算机固定，以便实现实验之间的延续性；4. 按要求完成实验内容，在实验结束后按照格式和规范撰写实验报告？【实验项目及学时分配】本课程实验环节共计16学时，实验项目及学时分配如下序号实验项目学时实验类型要求1线性表（顺序表 及单链表）4验证掌握线性表的基本操

2、作，熟悉指针 操作，完成实验内容要求2栈和队列2验证掌握顺序栈？顺序循环队列以及链式堆栈和队列基本操作并应用3二叉树的构建?基本操作和遍历4设计掌握二叉树的基本操作，实现二叉树的三种遍历？掌握哈夫曼树的构造以及编码4图的建立？基本操作以及遍历4设计掌握图的两种存储结构，并实现某一存储结构下图的操作的实现5排序与查找算法实现2设计掌握几种排序和查找算法的思想，实现任意排序和查找算法【实验报告及考核】1. 实验报告撰写符合格式及规范要求，详见实验报告撰写格式及规范2. 本课程实验占课程总成绩的15%?实验（一）线性表一 ？实验项目名称：线性表课时:4学时?实验要求1、掌握顺序表的定义与实现，包括查

3、找？插入？删除算法的实现,能在实际应2、掌握在各种链表结构中实现线性表操作的基本方法 用中选用适当的链表结构；三？实验环境Widows操作系统？C语言四？实验内容（1） 顺序表建立一如下表所示的学生信息表学号姓名性别年龄20001张三男2020002李四男22使用结构体， 下内容：1. 初始化2. 依次输 键盘输入）用顺序表完成以线性表为空； 入数据元素；（由3. 完成数据元素的插入？删除操作4. 取第i个数据元素5. 依次显示当前线性表中的数据元素（2）单链表建立一个单链表，依次输入数据元素09?使用结构体，用单链表完成以下内容：1. 初始化单链表；2.在单链表指定位置插入一个数据元素3.

4、删除指定位置的一个数据元素；4.取第i个数据元素5. 查找数据元素 x是否在单链表中；6.销毁单链表； 五？思考题：在什么情况下使用顺序表比链表好？实验(二)栈和队列一 ？实验项目名称：栈和队列课时:2学时二？实验要求1、 掌握栈的顺序表示？链表表示以及相应操作的实现？特别注意栈空和栈满的条件；2、 掌握队列的顺序表示？链表表示以及相应操作的实现？特别是循环队列中队头与队尾指针的变化情况；三？实验环境Widows操作系统？VC6.0四？实验内容分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文？回文是指一个字符序列以中间字符为基准，两边字符完全相同 ？如：“ABC

5、DEDCBA ?字符串长度小于等于 80,用 于判断回文的字符串不包括字符串的结束标记符？基本要求：(1) 字符序列可由用户从键盘随意输入；(2) 可以连续测试多个字符序列，由用户决定退出测试程序；算法思想：判断回文的算法思想是：把字符串中的字符逐个分别存入队列和 堆栈中，然后逐个出队列和退栈并比较出队列的数据元素和退栈的 数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文？基本操作：回文判断操作主要包括入栈和入队列？退栈和出队列操作 ？在对堆栈以及队列进行操作之前 ，必须对队列以及堆栈进行初始化？若使用链式堆栈和链式队列，操作结束后必须销毁链表 ？五？思考题：1 ?栈有哪些特点及

6、与一般线性表有哪些区别？2 ?队列有哪些特点及于一般线性表有哪些区别？实验(三)二叉树的构建？基本操作和遍历一 ?实验项目名称：二叉树的构建？基本操作和遍历课时:4学时二?实验要求1?熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范 围；2?熟练掌握二叉树的遍历方法及遍历算法；3?掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算？三？实验环境Widows操作系统？VC6.0四？实验内容(1)二叉树建立如下图所示的二叉树：要求:1?建立带头结点的二叉树，将?依次将二叉树的所有?用户可由键盘输入数?打印二叉树；?对二叉树实现前入乞树初始化为空;7上图所示的二叉树；现对二叉树各

7、结点的插入 ？删除等操作;?中序？后序遍历；算法思想：建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右子树操作 依次将上图中的结点插入二叉树中，利用二叉树的特殊中序遍历方法将该树以凹 入表示法打印显示？最后,调用二叉树的前序？中序？后序遍历函数对二叉树进行 遍历,并显示遍历结果？ ？哈夫曼树设计各设有字符集A?B?C?D,各字符在电文中出现的次数集为1,3,5,7, 字符的哈夫曼编码？要求：1?构造字符集的哈夫曼树,其结点数据结构如下：weightflagpare ntleftChildrightChild哈夫构造哈夫曼编码，输出权值及其对应的编码？算法思想：首先，由给定的n个权值构造

8、有2n-1个结点的哈夫曼树？在哈夫曼树中，其叶 结点的权值为相应的给定权值，非叶结点的权值为其孩子结点的权值之和？哈夫曼树构造过程如下：1. 根据给定的n个权值w 1 ,w2,wn,构成的n棵二叉树的森林F =T1,T2,斤,其中每棵二叉树Ti中只有一个权值为wj的结点，其左 ?右子树均为空；2. 在F中选取根结点的权值最小和次小的两棵树作为左？右子树构造一棵 新的二叉树,且置新二叉树的根结点的权值为其左？右子树上根结点的权值 之和；3. 在F中删除这两棵二叉树,并将新二叉树加入到F中；4. 重复2和3,直到F中只含一棵树为止？这棵树就是哈夫曼树?其次,对n个结点的哈夫曼树进行不等长编码？保证

9、任何一个字符的哈夫曼编码 不为另一字符的哈夫曼编码的前缀？五？思考题：已知一棵二叉树的层序序列是ABCDEFGH中序序列是DBGEHJACI试画出 此二叉树?实验（四）图的建立？基本操作以及遍历一 ?实验项目名称:图的建立？基本操作以及遍历课时:4学时二?实验要求1?熟练掌握图的结构特性，熟悉图的各种存储结构的特点及适用范围；2?熟练掌握几种常见图的遍历方法及遍历算法；三？实验环境Widows 操作系统？VC6.0四？实验内容选用任一种图的存储结构，建立如下图所示的带权有向图：要求:1 ?建立边的条数为零的图2 ? 依次将图的边以及相应的权值插入,建立如上图所示的图，并将结点集合和权值集合输出

10、；3 ?对所建立的图进行深度优先搜索或广度优先搜索，输出图的遍历序列； 算法思想：首先,选定所使用的图的存储结构（邻接矩阵存储或邻接表存储），建立图的结构体定 义?根据所选用的结构建立边条数为零的图，依次插入图的结点和图的各有向边以及权 值weight再次将图的结点集合以及权值集合输出，以验证所建立图的正确性最后调用 图的遍历函数，实现图的深度优先遍历或广度优先遍历，并输出遍历序列？ 五？思考题：1 ?采用邻接表存储的图的深度优先遍历算法类似于二叉树的哪种遍历？2?采用邻接表存储的图的广度优先遍历算法类似于二叉树的哪种遍历？实验（五）排序与查找算法实现一?实验项目名称:排序与查找算法实现课时：

11、2学时二?实验要求1 ?熟练掌握几种常见的排序方法及优缺点；2?熟练掌握几种常见的查找方法及其性能的评价；3?上机完成常见排序与查找功能的程序？三？实验环境Widows操作系统？VC6.0四？实验内容编写程序实现任一排序和查找功能？要求：1、数据元素个数n可由用户随意确定且有0<*80;2、可连续测试多组数据元素；3、数据元素由键盘输入；4、 将输入的数据元素进行排序后，实现任意查找功能；若查找成功，则 返回数据元素在数组中的下标和数据元素本身，若查找不成功，则输 出查找失败信息；5、最后，将经过排序的数据元素输出用以验证？ 五？思考题：在待排序的兀素序列基本有序的前提下，哪种排序方法效率最高？附录A西安理工大学实验报告课程实验名称第页共页系另U实 验日期年月日专业班级组别实验报告日期年月日姓 名号实验报告内容验证性