数结构实验指导书

《数结构实验指导书》由会员分享，可在线阅读，更多相关《数结构实验指导书（11页珍藏版）》请在金锄头文库上搜索。

1、数据结构与算法数据结构与算法实验指导书实验指导书实验及学时数分配实验及学时数分配序号序号实验名称实验名称学时数（小时）学时数（小时）1实验一 线性表线性表42实验二 树和二叉树树和二叉树23实验三 图图24实验四 查找查找25实验五 内部排序内部排序2合计合计12几点要求：几点要求：一、上机前：认真预习认真预习相关实验内容，提前编写提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数） 。二、上机中：在 Turbo C 或 VC6.0 环境中，认真调试程序认真调试程序，记录记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。三、下机后：按要求按要求完成

2、实验报告实验报告，并及时提交（实验后 1 周内周内） 。实验一实验一 线性表线性表【实验目的】 1、 掌握用 Turbo c 上机调试线性表的基本方法； 2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结 构和链式存储结构上的运算； 3、 运用线性表解决线性结构问题。 【实验学时】 4 学时学时 【实验类型】 设计型 【实验内容】 1、 顺序表的插入、删除操作的实现； 2、 单链表的插入、删除操作的实现； 3、 两个线性表合并算法的实现。 【实验原理】 1、 当我们在线性表的顺序存储结构上的第 i 个位置上插入一个元素时，必须先将线 性表中第 i 个元素之后的所有元素

3、依次后移一个位置，以便腾出一个位置，再把 新元素插入到该位置。若是欲删除第 i 个元素时，也必须把第 i 个元素之后的所 有元素前移一个位置； 2、 当我们在线性表的链式存储结构上的第 i 个位置上插入一个元素时，只需先确定 第 i 个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除 第 i 个元素时，也必须先确定第 i 个元素前一个元素位置，然后修改相应指针将 该元素删除即可； 3、 详细原理请参考教材。 【实验步骤】 一、用 C 语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。1、 通过键盘读取元素建立线性表； 2、 指定一个元素，在此元素之前插入一个新元

4、素； 3、 指定一个元素，删除此元素。 二、用 C 语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。1、 通过键盘读取元素建立单链表； 2、 指定一个元素，在此元素之前插入一个新元素； 3、 指定一个元素，删除此元素。 三、用 C 语言编程实现两个按递增顺序排列线性表的合并。 1、 编程实现合并按递增顺序排列的两个顺序表算法； 2、 编程实现合并按递增顺序排列的两个单链表算法。 【思考问题】 结合实验过程，回答下列问题： 1、 何时采用顺序表处理线性结构的问题为最佳选择？ 2、 何时采用链表处理线性结构的问题为最佳选择？ 【实验报告要求】1、 根据对线性表的理解，如何创建顺序

5、表和单链表； 2、 实现顺序表插入和删除操作的程序设计思路； 3、 实现链表插入和删除操作的程序设计思路； 4、 实现两表合并操作的程序设计思路； 5、 调试程序过程中遇到的问题及解决方案； 6、 本次实验的结论与体会。实验二实验二 树和二叉树树和二叉树【实验目的】 1、 掌握二叉树的结构特性，以及各种存储结构的特点及适用范围； 2、 掌握二叉树遍历算法。 3、 掌握线索二叉树算法。 4、 掌握赫夫曼编码算法。 【实验学时】 2 学时学时 【实验类型】 设计型 【实验内容】 1、 编程实现二叉树的遍历算法（可采用先序、中序和后序遍历算法之一） ； 2、 编制线索二叉树建立、遍历程序（采用中序遍

6、历算法） ； 3、 通过给定字符 a,b,c,d,e,f,g 的使用频率，编程求出它们的赫夫曼编码。 【实验原理】 1、 在二叉树的一些些应用中，常常要求在树中查找具有某种特征的结点，或者对树 中全部结点逐一进行某种处理，这就是遍历二叉树的问题，二叉树是由三个基本 单元组成：根结点、左子树和右子树，若限定先左子树后右子树，则根据根的顺 序可有三种遍历方法，即：先序遍历、中序遍历和后序遍历。 2、 在二叉链表存储结构中加上前驱或后继的线索，则构成线索二叉树，在线索二叉 树中进行遍历可以很方便地得到访问二叉树的线性序列。 3、 赫夫曼树是一类带权路径长度最短的树，利用赫夫曼树进行编码可以得到最优的

7、 二进制前缀编码。 4、 详细原理请参考教材。 【实验步骤】 一、用 C 语言编程实现二叉树的中序遍历算法。 1、采用二叉链存储结构创建一个二叉树； 2、用非递归方法实现二叉树的中序遍历算法； 3、输出二叉树中每个结点的值； 4、给定具体数据调试程序。 二、用 C 语言编程实现在线索二叉树上进行遍历。 1、先进行二叉树的线索化，即建立线索二叉树； 2、在线索二叉树中遍历每个结点并输出每个结点的信息； 3、给定具体数据调试程序。 三、用 C 语言编程实现赫夫曼编码。 假定用于通信的电文由 8 个字母 A、B、C、D、E、F、G、H 组成，各字母在电 文中出现的概率为 5%，25%，4%，7%，9

8、%，12%，30%，8%，试编程为这 8 个字 母设计赫夫曼编码。 1、 分析问题； 2、 编程创建此问题的赫夫曼树； 3、 编程求出此 8 个字母赫夫曼编码并输出； 4、 调试程序。 【思考问题】结合实验过程，回答下列问题： 1、 采用非递归方法实现二叉树遍历与采用递归方法实现二叉树的遍历，哪个方法执 行效率高； 2、 为什么在线索二叉树上进行遍历，要比在二叉树上进行遍历快捷方便？ 3、 针对同一问题，构成的赫夫曼树是否是唯一的，构成的赫夫曼编码是否唯一？ 【实验报告要求】 1、 根据对二叉树的理解，如何创建一个二叉树； 2、 实现二叉树遍历的程序设计思路； 3、 如何对二叉树进行线索化；

9、4、 创建赫夫曼树及其编码的程序设计思路； 5、本次实验的结论与体会。实验三实验三 图图【实验目的】 1、 掌握图的基本存储方法； 2、 掌握图的两种搜索路径的遍历算法； 3、 掌握拓扑排序算法；(选做) 【实验学时】 2 学时学时 【实验类型】 设计型 【实验内容】 1、 编程实现图的遍历图算法（按图的深度优先搜索算法或广度优先搜索算法遍历） ；2、 应用拓朴排序算法编制程序解决问题。 【实验原理】 1、 图的结构比较复杂，任意两顶点之间都可能有联系，图无顺序存储映象的存储结 构，可以借助数组的数据类型表示元素之间的关系，存储图常用的存储结构有数 组表示法、邻接表、邻接多重表和十字链表等；

10、2、 从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅访问一次，这就是图 的遍历，图的遍历算法是求解图的连通性问题、拓朴排序和求关键路径等算法的 基础，通常有两种遍历图的方法：深度优先搜索和广度优先搜索，其中深度优先 搜索就是从图中某个顶点 V 出发，访问此顶点，然后依次从 V 的未被访问的邻 接点出发深度优先遍历图，直至图中所有和 V 有路径相通的顶点都被访问到，若 此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复 上述过程，直至图中所有顶点都被访问到为止；广度优先搜索就是从图中某个顶 点 V 出发，在访问了 V 之后依次访问 V 的各个未曾访问过的邻接点，然后分别

11、 从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先 于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点 都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点 作起始点，重复上述过程，直至图中所有顶点都被访问到为止； 3、 构造最小生成树的算法有：普里姆算法和克鲁卡尔算法； 4、 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓朴排序， 拓朴排序的方法是：在有向图中选一个没有前驱的顶点且输出之，从图中删除该 顶点和所有以它为尾的弧，重复上述步骤，直至全部顶点均被输出，或当前图中 不存在无前驱的顶点为止。 5、 详细原理请参

12、考教材。 【实验步骤】 一、用 C 语言编程实现图的遍历算法。 1、采用邻接表存储结构创建一个图； 2、编程实现图的深度优先搜索（或广度优先搜索）遍历算法； 3、输出遍历结果； 4、给定具体数据调试程序。 二、教学计划编制问题 软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计与分析C3,C4C6计算机原理C11C7编译原理C3,C5C8操作系统C3,C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10假设每门

13、课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能 在最短的时间内修完这些课程。 1、 分析问题； 2、 根据此问题创建一个图表示课程与课程之间的关系； 3、 利用拓扑排序算法实现该教学计划； 4、输出课程开出的先后顺序； 5、 调试程序。 【思考问题】 结合实验过程，回答下列问题： 1、 图有哪几种存储结构，哪种适合于存储无向图，哪种适合于存储有向图？； 2、 列举出几种需要应用关键路径或最短路径算法解决的实际问题。 【实验报告要求】 1、 根据对图的理解，如何创建一个图； 2、 实现图的遍历的程序设计思路； 3、 编制教学计划问题的设计思路； 4、本次实验的结论与体会。实验四实

14、验四 查找查找【实验目的】 1、 掌握静态查找表算法（重点掌握折半查找） ； 2、 掌握动态查找表-二叉排序树查找算法； 3、 掌握哈希表查找算法 【实验学时】 2 学时学时 【实验类型】 设计型 【实验内容】 1、 编程实现有序表的折半查找算法； 2、 编程实现按二叉排序树算法进行查找。 3、 利用哈希表算法进行查找 【实验原理】 1、 有序表的折半查找过程是：先确定确定待查记录所在的范围（区间） ，然后逐步 缩小范围直到找到或找不到该记录为止； 2、 二叉排序树查找过程是：首先将给定值和根结点的关键字比较，若相等，则查找 成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或

15、右 子树上继续进行查找； 3、 在查找问题中，理想的情况是希望不经过任何比较，一次存取便能得到所查记录， 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个 关键字和结构中一个唯一的存储位置相对应。这需要构造一个哈希函数，常用的 构造函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数 法和随机数法。构造的哈希表发生冲突是不可避免的，需要适当地处理冲突，处 理冲突的方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区法。 4、 详细原理请参考教材。 【实验步骤】 一、用 C 语言编程实现有序表的折半查找算法 1、 创建一个递增的有序表； 2、 给定一个值

16、，用折半查找算法在有序表中进行查找； 3、 输出查找结果； 4、 给定具体数据调试程序 二、用 C 语言编程实现在二叉排序树中进行查找 1、读入一串整数，采用二叉链存储结构创建一棵二叉排序树； 2、给定一个值，在二叉排序树中进行查找； 3、输出查找结果； 4、给定具体数据调试程序。 三、哈希表查找 针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查 找长度不超过 R，完成相应的建表和查找程序。 1、 分析问题； 2、 创建此问题的哈希表； 3、 指定一个人名，在哈希表中进行查找，并输出查找结果；4、调试程序。 【思考问题】 结合实验过程，回答下列问题： 何种情况适合采用折半查找、何种情况适合采用二叉排序树查找、何种情况适 合采用哈希表查找？ 【实验报告要求】 1、根据对静态查找算法的理解，实现折半查找的程序设计思路； 2、根据对二叉排序树的理解，实现在二叉排序树中进行查找的程序设计思路； 3、如何构造哈希函数，如何解决地址冲突； 4、 实现在哈希表中进行查找的程序设计思路； 5、 本