《数据结构与算法》
实验指导书
实验及学时数分配
序号
实验名称
学时数（小时）
1
实验一 线性表
4
2
实验二 树和二叉树
2
3
实验三 图
2
4
实验四 查
2
5
实验五 内部排序
2
合计
12
几点要求：
一、上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。
三、下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一    线性表
【实验目的】
1、掌握用Turbo c上机调试线性表的基本方法；
2、掌握线性表的基本操作，插入、删除、查以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；
3、运用线性表解决线性结构问题。
【实验学时】
4 学时
【实验类型】
设计型
【实验内容】
1、顺序表的插入、删除操作的实现；
2、单链表的插入、删除操作的实现；
3、两个线性表合并算法的实现。(选做)
【实验原理】
1、当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；
2、当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元
素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；
3、详细原理请参考教材。
【实验步骤】
一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）
2、指定一个元素，在此元素之前插入一个新元素；（从键盘接受插入位置i， 和要插入的元素值；实现插入；显示插入后的线性表）
3、指定一个元素，删除此元素。（从键盘接受删除元素位置i，实现删除；显示删除后的线性表）
二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素。
1、通过键盘读取元素建立单链表；
2、指定一个元素，在此元素之前插入一个新元素；
3、指定一个元素，删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并。
1、编程实现合并按递增顺序排列的两个顺序表算法；
2、编程实现合并按递增顺序排列的两个单链表算法。
【思考问题】
结合实验过程，回答下列问题：
1、何时采用顺序表处理线性结构的问题为最佳选择；
2、何时采用链表处理线性结构的问题为最佳选择。
【实验报告要求】
1、根据对线性表的理解，如何创建顺序表和单链表；
2、实现顺序表插入和删除操作的程序设计思路；
3、实现链表插入和删除操作的程序设计思路；
4、实现两表合并操作的程序设计思路；
5、调试程序过程中遇到的问题及解决方案；
6、本次实验的结论与体会。
实验二    树和二叉树
【实验目的】
1、掌握二叉树的结构特性，以及各种存储结构的特点及适用范围；
2、掌握二叉树遍历算法。
3、掌握线索二叉树算法。
4、掌握赫夫曼编码算法。
【实验学时】
2 学时
【实验类型】
设计型
汇编语言指导书
【实验内容】
1、编程实现二叉树的遍历算法（可采用先序、中序和后序遍历算法之一）；
2、编制线索二叉树建立、遍历程序（采用中序遍历算法）；
3、通过给定字符a,b,c,d,e,f,g的使用频率，编程求出它们的赫夫曼编码。
【实验原理】
1、在二叉树的一些些应用中，常常要求在树中查具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是遍历二叉树的问题，二叉树是由三个基本单元组成：根结点、左子树和右子树，若限定先左子树后右子树，则根据根的顺序可有三种遍历方法，即：先序遍历、中序遍历和后序遍历。
2、在二叉链表存储结构中加上前驱或后继的线索，则构成线索二叉树，在线索二叉树中进行遍历可以很方便地得到访问二叉树的线性序列。
3、赫夫曼树是一类带权路径长度最短的树，利用赫夫曼树进行编码可以得到最优的二进制前缀编码。
4、详细原理请参考教材。
【实验步骤】
一、用C语言编程实现二叉树的中序遍历算法
1、采用二叉链存储结构创建一个二叉树；
2、用非递归方法实现二叉树的中序遍历算法；
3、输出二叉树中每个结点的值；
4、给定具体数据调试程序。
二、用C语言编程实现在线索二叉树上进行遍历
1、先进行二叉树的线索化，即建立线索二叉树；
2、在线索二叉树中遍历每个结点并输出每个结点的信息；
4、给定具体数据调试程序。
三、用C语言编程实现赫夫曼编码
假定用于通信的电文由8个字母A、B、C、D、E、F、G、H组成，各字母在电文中出现的概率为5%，25%，4%，7%，9%，12%，30%，8%，试编程为这8个字母设计赫夫曼编码。
1、分析问题
2、编程创建此问题的赫夫曼树；
3、编程求出此8个字母赫夫曼编码并输出；
4、调试程序。
【思考问题】
结合实验过程，回答下列问题：
1、采用非递归方法实现二叉树遍历与采用递归方法实现二叉树的遍历，哪个方法执行效率高；
2、为什么在线索二叉树上进行遍历，要比在二叉树上进行遍历快捷方便？
3、针对同一问题，构成的赫夫曼树是否是唯一的，构成的赫夫曼编码是否唯一？
【实验报告要求】
1、根据对二叉树的理解，如何创建一个二叉树；
2、实现二叉树遍历的程序设计思路；
3、如何对二叉树进行线索化；
4、创建赫夫曼树及其编码的程序设计思路；
5、本次实验的结论与体会。
实验三    图
【实验目的】
1、掌握图的基本存储方法；
2、掌握图的两种搜索路径的遍历算法；
3、掌握拓扑排序算法；(选做)
【实验学时】
2学时
【实验类型】
设计型
【实验内容】
1、编程实现图的遍历图算法（按图的深度优先搜索算法或广度优先搜索算法遍历）；
2、应用拓朴排序算法编制程序解决问题。
【实验原理】
1、图的结构比较复杂，任意两顶点之间都可能有联系，图无顺序存储映象的存储结构，可以借助数组的数据类型表示元素之间的关系，存储图常用的存储结构有数组表示法、邻接表、邻接多重表和十字链表等；
2、从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅访问一次，这就是图的遍历，
图的遍历算法是求解图的连通性问题、拓朴排序和求关键路径等算法的基础，通常有两种遍历图的方法：深度优先搜索和广度优先搜索，其中深度优先搜索就是从图中某个顶点V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止；广度优先搜索就是从图中某个顶点V出发，在访问了V之后依次访问V的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止；

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。