数据结构实验指导书(本科正式).doc

数据结构实验指导书实验一 线性表【实验目的】1、 掌握用Turbo c上机调试线性表的基本方法；2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；3、 运用线性表解决线性结构问题。【实验学时】4 学时【实验类型】设计型【实验内容】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、 掌握赫夫曼编码算法。【实验学时】2 学时【实验类型】设计型【实验内容】1、 编程实现二叉树的遍历算法（可采用先序、中序和后序遍历算法之一）；2、 通过给定字符a,b,c,d,e,f,g的使用频率，编程求出它们的赫夫曼编码。【实验原理】1、 在二叉树的一些些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理，这就是遍历二叉树的问题，二叉树是由三个基本单元组成：根结点、左子树和右子树，若限定先左子树后右子树，则根据根的顺序可有三种遍历方法，即：先序遍历、中序遍历和后序遍历。2、 在二叉链表存储结构中加上前驱或后继的线索，则构成线索二叉树，在线索二叉树中进行遍历可以很方便地得到访问二叉树的线性序列。3、 赫夫曼树是一类带权路径长度最短的树，利用赫夫曼树进行编码可以得到最优的二进制前缀编码。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%，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的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到，若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止；3、 构造最小生成树的算法有：普里姆算法和克鲁卡尔算法；4、 由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓朴排序，拓朴排序的方法是：在有向图中选一个没有前驱的顶点且输出之，从图中删除该顶点和所有以它为尾的弧，重复上述步骤，直至全部顶点均被输出，或当前图中不存在无前驱的顶点为止。5、 详细原理请参考教材。【实验步骤】一、用C语言编程实现图的遍历算法1、采用邻接表存储结构创建一个图；2、编程实现图的深度优先搜索（或广度优先搜索）遍历算法3、输出遍历结果；4、给定具体数据调试程序。二、教学计划编制问题软件专业的学生要学习一系列课程，其中有些课程必须在其先修课程完成后才能学习，具体关系见下表：课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1,C2C4汇编语言C1C5语言的设计与分析C3,C4C6计算机原理C11C7编译原理C3,C5C8操作系统C3,C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C1,C9,C10假设每门课程的学习时间为一学期，试为该专业的学生设计教学计划，使他们能在最短的时间内修完这些课程。1、 分析问题；2、 根据此问题创建一个图表示课程与课程之间的关系；3、 利用拓扑排序算法实现该教学计划；4、输出课程开出的先后顺序5、 调试程序。【思考问题】结合实验过程，回答下列问题：1、 图有哪几种存储结构，哪种适合于存储无向图，哪种适合于存储有向图？；2、 列举出几种需要应用关键路径或最短路径算法解决的实际问题。【实验报告要求】1、 根据对图的理解，如何创建一个图；2、 实现图的遍历的程序设计思路；3、 编制教学计划问题的设计思路；4、本次实验的结论与体会。实验四 查找【实验目的】1、 掌握静态查找表算法（重点掌握折半查找）；2、 掌握动态查找表-二叉排序树查找算法；3、 掌握哈希表查找算法【实验学时】2 学时【实验类型】设计型【实验内容】1、 编程实现有序表的折半查找算法；2、 编程实现按二叉排序树算法进行查找。3、 利用哈希表算法进行查找【实验原理】1、 有序表的折半查找过程是：先确定确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止；2、 二叉排序树查找过程是：首先将给定值和根结点的关键字比较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的大小关系，分别在左子树或右子树上继续进行查找；3、 在查找问题中，理想的情况是希望不经过任何比较，一次存取便能得到所查记录，那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。这需要构造一个哈希函数，常用的构造函数的方法有：直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。构造的哈希表发生冲突是不可避免的，需要适当地处理冲突，处理冲突的方法有：开放定址法、再哈希法、链地址法和建立一个公共溢出区法。4、 详细原理请参考教材。【实验步骤】一、用C语言编程实现有序表的折半查找算法1、 创建一个递增的有序表；2、 给定一个值，用折半查找算法在有序表中进行查找；3、 输出查找结果；4、 给定具体数据调试程序二、用C语言编程实现在二叉排序树中进行查找1、读入一串整数，采用二叉链存储结构创建一棵二叉排序树；2、给定一个值，在二叉排序树中进行查找；3、输出查找结果；4、给定具体数据调试程序。三、哈希表查找针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查找程序。1、 分析问题；2、 创建此问题的哈希表；3、 指定一个人名，在哈希表中进行查找，并输出查找结果；4、调试程序。【思考问题】结合实验过程，回答下列问题：何种情况适合采用折半查找、何种情况适合采用二叉排序树查找、何种情况适合采用哈希表查找？【实验报告要求】1、根据对静态查找算法的理解，实现折半查找的程序设计思路；2、根据对二叉排序树的理解，实现在二叉排序树中进行查找的程序设计思路；3、如何构造哈希函数，如何解决地址冲突；4、 实现在哈希表中进行查找的程序设计思路；5、 本次实验的结论与体会。实验五 内部排序【实验目的】1、 掌握常用的排序方法（如：希尔排序、快速排序、选择排序、归并排序），并掌握用高级语言实现排序算法；2、 深刻理解排序的定义和常用排序方法的特点，并能加以灵活应用；3、 了解常用方法的排序过程及其依据的原理。【实验学时】2 学时【实验类型】设计型【实验内容】(选择其中两个题做)1、 编程实现插入排序算法；2、 编程实现快速排序算法；3、 编程实现选择排序算法；4、 编程实现归并排序算法。【实验原理】1、 插入排序算法有：直接插入排序、2路插入排序和希尔排序；2、 快速排序算法有：起泡排序、快速排序；3、 选择排序算法有：简单选择排序、树形选择排序和堆排序；4、 详细原理请参考教材。【实验步骤】一、用C语言编程实现插入排序算法 给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种插入排序算法编程实现： 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； 按名次列出每个学生的姓名与分数。二、用C语言编程实现快速排序算法给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种快速排序算法编程实现： 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； 按名次列出每个学生的姓名与分数。三、用C语言编程实现选择排序算法给出n个学生的考试成绩表，每条信息由姓名与分数组成，用一种选择排序算法编程实现： 按分数高低次序输出每个学生在考试中获得的名次，分数相同的为同一名次； 按名次列出每个学生的姓名与分数。四、用C语言编程实现归并排序算法给出n个学生的考试成绩表，每条信息由姓名与分数组成，用归并排序算法编程实现： 按分数高低次序输出每个学生在考试中获得的名次，分数相同的