09级《数据结构》实验指导书

《09级《数据结构》实验指导书》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、型要求1线性表（顺序表及单链表）4验证掌握线性表的棊本操作，熟悉指针操作，完成实验内容要求2栈和队列2验证学握顺序栈、顺序循坏队列以及链式堆栈和队列基本操作并应用3二叉树的构建、基本操作和遍历4设计掌握二叉树的棊本操作，实现二艾树的三种遍历。学握哈夫曼树的构造以及编码4图的建立、基本操作以及遍历4设计拿握图的两种存储结构，并实现某一存储结构下图的操作的实现5排序9查找算法实现2设计学握几种排序和查找算法的思想，实现任遺排序和查找算法【实验报告及考核】1.实验报告撰写符合格式及规范要求，详见实验报告撰写格式及规范;2.木课程实验占

3、课程总成绩的15%。实验（一）线性表一、实验项目名称：线性表课时：4学时二、实验要求1、掌握顺序表的定义与实现，包扭杳找、插入、删除算法的实现；2.掌握在各种链表结构中实现线性表操作的基本方法，能在实际应川中选用适当的链表结构；三、实验环境Widows操作系统、C语言四、实验内容（1）顺序表建立一•如F表所示的学生信息表学号姓名性别年龄20001张三男2020002李四男22••••••••••••使用结构体，川顺序表完成以下内容：1.初始化线性表为空；2.依次输入数据元素；（rti键盘输入）3.完成数据元素的插入、删除操作；化

4、取第i个数据元索；1.依次显示当前线性表中的数据元索。（2）单链表建立一个单链表，依次输入数据元索0〜9。使用结构体，用单链表完成以下内容：1.初始化单链表；2.在单链表指定位置插入一个数据元素；3.删除指定位置的一个数据元素；4.取笫i个数据元素；5.查找数据元索x是否在单链表中；6.销毁单链表；五、思考题：在什么情况下使用顺序表比链表好？实验（二）栈和队列一、实验项目名称：栈和队列课时：2学时二、实验要求1、掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；2、掌握队列的顺序表示、链表表示以及相应操作的

5、实现。特别是循环队列中队头与队尾指针的变化情况；三、实验环境Widows操作系统、VC6.0四、实验内容分别使用顺序循环队列和堆栈以及链式队列和堆栈编写程序：判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准,两边字符完全相同。如:“ABCDEDCBA”。字符串长度小于等于80,用于判断回文的字符串不包扌&字符串的结束标记符。基本要求：（1）字符序列可rh用户从键盘随意输入；（2）可以连续测试多个字符序列，由川八决定退出测试程序；算法思想：判断回文的算法思想是：把字符串中的字符逐个分别存入队列和堆栈中，然后逐个出队

6、列和追栈并比钱出队列的数据元素和退栈的数据元素是否相等，若全部相等则该字符序列为回文，否则就不是回文。基本操作：回文判断操作主要包括入栈和入队列、退栈和岀队列操作。在对堆栈以及队列进行操作之前，必须对队列以及堆栈进行初始化。若使用链式堆栈和链式队列，操作结束后必须销毁链表。五、思考题：1、栈有哪些特点及与一般线性表有哪些区别？2、队列有哪些特点及于一般线性表有哪些区别？一、实验项目名称：二叉树的构建、基本操作和遍历课时：4学时二、实验要求1、熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；2、熟练掌握二叉树的

7、遍历方法及遍历算法；3、掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。三、实验环境Widows操作系统、VC6.0四、实验内容（1）二叉树建立如卜-图所示的二叉树：要求：1、建立带头结点的二叉树，将二义树初始化为空；2、依次将二叉树的所有结点插入，建立上图所示的二叉树；3、川户可由键盘输入数据实现对二叉树各结点的插入、删除等操作;4、打印二叉树;5、对二叉树实现前序、中序、后序遍历；算法思想：建立一棵只有头结点的二叉树，并通过调用插入左子树和插入右子树操作，依次将上图中的结点插入二叉树中，利用二叉树的特殊中序遍历方法将

8、该树以凹入表示法打印显示。最后，调用二义树的前序、中序、后序遍历函数对二叉树进行遍历，并显示遍历结果。(2)、哈夫曼树设有字符集AB、C、D},各字符在电文中出现的次数集为{1,3,5,7},设计各字符的哈夫曼编码。耍求：1、构造字符集的哈夫曼树，其结点数据结构