数据结构实验

1、数据结构实验指导书计算机学院数据结构课程组2014-3前言计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方

2、法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。实验目录实验一 线性表的基本操作及其应用4实验二 栈和队列的基本操作及其应用8实验三 二叉树的基本运算12实验四 哈夫曼树与哈夫曼编码15实验五 图的基本操作17实验六 图的应用19实验七 查找、排序的应用24实验一 线性表的基本操作及其应用一、实验目的1、帮助读者复习C+语言程序设计中的知识。2、熟悉线性表的逻辑结构。3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重

3、点。二、实验内容本次实验提供3个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做！题目一：单链表的基本操作（*）问题描述实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。基本要求（1）依次从键盘读入数据，建立带头结点的单链表； （2）输出单链表中的数据元素（3）求单链表的长度；（4）根据指定条件能够取元素和修改元素；（5）实现在指定位置插入和删除元素的功能。 测试数据由学生任意指定。题目二：约瑟夫环（*） 问题描述约瑟夫（Joseph）问题的一种描述是：编号为1,2,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选

4、一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。基本要求利用单向循环链表存储结构模拟此过程，按照出列的顺序印出各人的编号。测试数据由学生任意指定。如：m的初值为20；n的值为7；密码：3，1，7，2，4，8，4；（正确的输出结果应为6，1，4，7，2，3，5）。 (报告上要求写出多批数据测试结果)实现提示程序运行后首先要求用户输入初始报数上限值m，人数n,(设n30)。然后输入各人的密码。选作内容向上述程序中

5、添加在顺序结构上实现的部分。题目三：多项式的表示及相加（*）问题描述设计一个算法，以实现一元稀疏多项式的加法运算。基本要求（1）输入并建立多项式；（2）输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；（3）多项式a和b相加，建立多项式a+b。测试数据由学生任意指定。实现提示用带表头结点的单链表存储多项式。选作内容多项式a和b相减，建立多项式a-b。 三、实验前的准备工作1、掌握线性表的逻辑结构。2、掌握线性表的链式存储结构。3、熟练掌握线性表的插入、删除等操作。四、实验报告要求1、实验报告要按

6、照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验二 栈和队列的基本操作及其应用一、实验目的1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。2、掌握栈和队列的特点，即后进先出和先进先出的原则。3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。二、实验内容本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，学生可以根据自己的情况选做！题目一：回文判断（*）问题描述对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回

7、文。基本要求（1）数据从键盘读入；（2）输出要判断的字符串； （3）利用栈和队列对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。测试数据由学生任意指定。题目二：商品货架管理（*）问题描述商店货架以栈的方式摆放商品。生产日期越近的越靠近栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样就需要倒货架，使生产日期越近的越靠近栈底。基本要求设计一个算法，保证每一次上货后始终保持生产日期越近的商品越靠近栈底。实现提示可以用一个队列和一个临时栈作为周转。测试数据由学生任意指定。题目三：舞伴问题（*）假设

8、在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题。【实验提示】先入队的男士或女士亦先出队配成舞伴。因此该问题具体有典型的先进先出特性，可用队列作为算法的数据结构。在算法中，假设男士和女士的记录存放在一个数组中作为输入，然后依次扫描该数组的各元素，并根据性别来决定是进入男队还是女队。当这两个队列构造完成之后，依次将两队当前的队头元素出队来配成舞伴，直至某队列变空为止。此时，若某队仍有等待配对者，算法输出此队列中等待者的人数及排在队头的等待者的

9、名字，他（或她）将是下一轮舞曲开始时第一个可获得舞伴的人。【实验要求】 利用队列实现，存储结构采用顺序或链式均可三、实验前的准备工作1、掌握栈的逻辑结构和存储结构。2、熟练掌握栈的出栈、入栈等操作。3、掌握队列的逻辑结构和存储结构。4、熟练掌握队列的出队、入队等操作四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验三 二叉树的基本运算一、实验目的1、使学生熟练掌握二叉树的逻辑结构和存储结构。2、熟练掌握二叉树的各种遍历算法。二、实验内容题目一：二叉树的基本操作实现 （*）问题描述建立一棵二叉树，试编程实现二叉树

10、的如下基本操作：1. 按先序序列构造一棵二叉链表表示的二叉树T；2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列；3. 求二叉树的深度/结点数目/叶结点数目；(选做)4. 将二叉树每个结点的左右子树交换位置。（选做） 基本要求从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立），测试数据如输入：ABCDEGF（其中表示空格字符）则输出结果为 先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA层序：ABCDEFG选作内容采用非递归算法实现二叉树遍历。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握二叉树的逻辑结构和存储结构。3、掌

11、握二叉树的各种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验四 哈夫曼树与哈夫曼编码一、实验目的1、使学生熟练掌握哈夫曼树的生成算法。2、熟练掌握哈夫曼编码的方法。二、实验内容本次实验提供2个题目，难度相当，学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一、哈夫曼树和哈夫曼编码问题描述一电文，有若干个不同字符，要求从终端输入这些不同字符及其出现的频率，然后对这些字符进行哈夫曼编码，并输出。测试数据利用教材P.148 例62中的数据调试程序 (可自己设定测试数据)。 选作内容1

12、、打印出该哈夫曼树2、若从终端输入任意一段电文（假设仅为26个大小写英文字母）,试编程高效地求出该段电文的哈夫曼编码。提示：如何快速统计不同字符的出现频率3、译码：将上述1的编码结果还原成电文。三、实验前的准备工作1、掌握树的逻辑结构。2、掌握哈夫曼树的定义及生成算法。3、掌握哈夫曼编码的方法。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验五 图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。2、熟练掌握图的存储结构。3、熟练掌握图的两种遍历算法。二、实验内容本次实验提供4个题目，难度相当，

13、学生可以根据自己的情况选做，其中题目一是必做题，其它选作！题目一： 图的遍历（*）问题描述对给定图，实现图的深度优先遍历和广度优先遍历。基本要求以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。【测试数据】由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的两种遍历算法的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验六 图的应用一、实验目的1、使学生可以巩固所学的

14、有关图的基本知识。2、熟练掌握图的存储结构。3、掌握如何应用图解决各种实际问题。二、实验内容本次实验提供若干个题目，难易程度不等，学生可以根据自己的情况选做至少一题。题目一：最小生成树问题问题描述若要在n个城市之间建设通信网络，只需要假设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。基本要求1 利用克鲁斯卡尔算法求网的最小生成树。2 要求输出各条边及它们的权值。实现提示通信线路一旦建成，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数。图的存储结构的选取应和所作操作相适应。为了便于选择

15、权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组表示图。 测试数据由学生依据软件工程的测试技术自己确定。题目二：拓扑排序的应用 试编程，为某校软件专业的四年全部课程做一个排课方案。测试数据自行设计题目三：最短路径问题问题描述给定一个无向网，可以求得任意一对顶点之间的最短路径。基本要求 以邻接矩阵为存储结构，实现弗洛伊德算法求解每一对顶点之间的最短路径及最短路径长度。测试数据由学生依据软件工程的测试技术自己确定。三、实验前的准备工作1、掌握图的相关概念。2、掌握图的逻辑结构和存储结构。3、掌握图的各种应用的实现。四、实验报告要求1、实验报告要按照实验报告格式规范书写。2、实验上要写出多批测试数据的运行结果。3、结合运行结果，对程序进行分析。实验七 查找、排序的应用一、实验目的1、本实验可以使学生更进一步巩固各种查找和排序的基本知识。2、学会比较各种排序与查找算法的优劣。3、学会针对所给问题选用最适合的算法。4、掌握利用常用的排序与选择算法的思想来解决一般问题的方法和技巧。二、实验内容问题描述学生信息管理系统基本要求设计一个学生信息管理系统，学生对象至少要包含：学号、姓名、性别、成绩1、成绩2、总成绩等信息。要求实现以下功能：1.试选择一种方式实现：基于数组、链表或文件方式2总成绩要求自动