《数据结构》实验指导书
实验一 线性表
【实验目的】
1、 掌握用Turbo c上机调试线性表的基本方法；
2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结
构和链式存储结构上的运算； 3、 运用线性表解决线性结构问题。 【实验学时】
2 学时 【实验类型】
设计型 【实验内容】
1、 顺序表的插入、删除操作的实现； 2、 单链表的插入、删除操作的实现； 3、 两个线性表合并算法的实现。(选做) 【实验原理】
1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线
性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；
2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定
第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；
3、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素 1、 通过键盘读取元素建立线性表；
2、 指定一个元素，在此元素之前插入一个新元素； 3、 指定一个元素，删除此元素。
二、用C语言编程实现建立一个单链表，并在此表中插入一个元素和删除一个元素 1、 通过键盘读取元素建立单链表；
2、 指定一个元素，在此元素之前插入一个新元素； 3、 指定一个元素，删除此元素。
三、用C语言编程实现两个按递增顺序排列线性表的合并 1、 编程实现合并按递增顺序排列的两个顺序表算法； 2、 编程实现合并按递增顺序排列的两个单链表算法。 【思考问题】
结合实验过程，回答下列问题：
1、 何时采用顺序表处理线性结构的问题为最佳选择； 2、 何时采用链表处理线性结构的问题为最佳选择。 【实验报告要求】
1、 根据对线性表的理解，如何创建顺序表和单链表；
2、 实现顺序表插入和删除操作的程序设计思路； 3、 实现链表插入和删除操作的程序设计思路； 4、 实现两表合并操作的程序设计思路； 5、 调试程序过程中遇到的问题及解决方案； 6、 本次实验的结论与体会。
实验二 栈和队列
【实验目的】
1、 掌握栈和队列的顺序存储结构和链式存储结构，以便在实际背景下灵活运用； 2、 掌握栈和队列的特点，即后进先出与先进先出的原则； 3、 掌握栈和队列的基本操作，如入栈与出栈、入队与出队等； 4、 运用栈和队列解决问题。 【实验学时】
2 学时 【实验类型】
设计型 【实验内容】
1、 编程实现建栈、入栈、出栈操作； 2、 编程实现数制转换程序；
3、 编程实现队列的建立，在队列中插入元素和删除元素。 【实验原理】
1、 栈是限定仅在表尾进行插入或删除操作的线性表，具有后进先出的特点。栈的顺
序存储结构是利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素； 2、 队列是一种先进先出的线性表，在队尾进行插入操作，在队头进行删除操作； 3、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现建立一个顺序栈，并在此顺序栈中实现入栈和出栈操作 1、 通过键盘读取元素建立顺序栈；
2、 给定一个元素，在此元素压入此栈中； 3、 将栈顶一个元素弹出此栈。 二、用C语言编程实现将一个十进制数转换成二进制数（或八进制数、或十六进制数） 1、 通过键盘输入一个十进制数；
2、 将此数转换成对应的非十进制数（如二进制数、八进制数或十六进制数）。 三、用C语言编程实现建立一个链式队列，并在此链队列中实现入队和出队操作 1、通过键盘读取元素建立链队列；
2、给定一个元素，在此元素插入此队列中； 3、 将队头一个元素出队。 【思考问题】
结合实验过程，回答下列问题：
1、 入栈、出栈操作，如何移动栈顶指针TOP； 2、 如何判断队列是否已满
【实验报告要求】
1、 根据对栈和队列的理解，如何创建顺序栈和链队列； 2、 调试程序过程中遇到的问题及解决方案； 3、 本次实验的结论与体会。
实验三 数组
【实验目的】
1、 了解数组的两种存储表示方法，掌握数组在作为运行的存储结构中的地址计算方
法；
2、 了解稀疏矩阵的两种压缩方法的特点和适用范围，领会稀疏矩阵运算采用的处理
方法。
【实验学时】
2学时 【实验类型】
设计型 【实验内容】
编程实现稀疏矩阵转置和两稀疏矩阵乘积。 【实验原理】
1、 压缩存储是只存储稀疏矩阵的非零元，除了存储非零元的值之外，还必须同时记
下它所在行和列的位置；
2、 采用三元组顺序表存储稀疏矩阵，一个稀疏矩阵的转置矩阵仍是稀疏矩阵； 3、 采用行逻辑链接的顺序表存储稀疏矩阵，方便于两个稀疏矩阵相乖； 4、 详细原理请参考教材。 【实验步骤】
一、用C语言编程实现稀疏矩阵的转置 1、采用三元组顺序表创建一个稀疏矩阵； 2、将矩阵的行列值相互交换；
3、将每个三元组中的i和j相互调换； 4、重排三元组之间的次序实现矩阵转置。 二、用C语言编程实现两稀疏矩阵的乘积
1、 采用行逻辑链接的顺序表建立两个稀疏矩阵； 2、 求两稀疏矩阵的乘积 【思考问题】
结合实验过程，回答下列问题：
1、两稀疏矩阵相乘，其乘积是否一定为稀疏矩阵 【实验报告要求】
1、 根据对稀疏矩阵的理解，如何创建一个稀疏矩阵； 2、 实现稀疏矩阵转置的程序设计思路； 3、 实现两稀疏矩阵相乘的程序设计思路； 4、 调试程序过程中遇到的问题及解决方案； 5、 本次实验的结论与体会。
实验四 树和二叉树
【实验目的】
1、 掌握二叉树的结构特性，以及各种存储结构的特点及适用范围； 2、 掌握二叉树遍历算法。 3、 掌握线索二叉树算法。 4、 掌握赫夫曼编码算法。 【实验学时】
4 学时 【实验类型】
设计型 【实验内容】
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的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后