数据结构 - 计算机学院.DOCVIP

《数据结构》 实 验 指 导 书 计算机学院数据结构课程组 2014-3 前言 　　 　　计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。 数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。 实验目录 实验一 线性表的基本操作及其应用 4 实验二 栈和队列的基本操作及其应用 8 实验三 二叉树的基本运算 12 实验四 哈夫曼树与哈夫曼编码 15 实验五 图的基本操作 17 实验六 图的应用 19 实验七 查找、排序的应用 24 实验一 线性表的基本操作及其应用 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。题目一：单链表的基本操作（*） [问题描述] 实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。 [基本要求] （2）输出单链表中的数据元素 [测试数据] 由学生任意指定。 题目二：约瑟夫环（**） [问题描述]　　约瑟夫（Joseph）问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值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,(设n≤30)。然后输入各人的密码。 [选作内容]　　向上述程序中添加在顺序结构上实现的部分。 题目三：多项式的表示及相加（***） [问题描述] 设计一个算法，以实现一元稀疏多项式的加法运算。 [基本要求] ……，cn，en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列； （3）多项式a和b相加，建立多项式a+b。 [测试数据] 由学生任意指定。[实现提示]　　用带表头结点的单链表存储多项式。 [选作内容]　　 题目四：Dr.Kong设计了一件艺术品（****） [问题描述] Dr.Kong设计了一件艺术品，该艺术品由N个构件堆叠而成，N个构件从高到低按层编号依次为1，2，……,N。艺术品展出后，引起了强烈的反映。Dr.Kong观察到，人们尤其对作品的高端部分评价甚多。 狂热的Dr.Kong一激动，对组成该艺术品的N个构件重新组合，比如：把第6层到第12层的构件搬下来，想一想，然后整体放到剩下构件的第7层下面；过一会儿，又把第2层到第9层的构件搬下来，整体放到剩下构件的第1层下面等等。于是，Dr.Kong在进行了连续若干次“搬来搬去”后，还是这N个构件，又诞生了一件新的艺术品。 编程：请输出新的艺术品最高十层构件的编号。 第一行: N K 表示构件的总数和“搬来搬去”的总次数 第2~K+1行：A B C 表示要搬动的构件（即从第A层到第B层）整个放在第C层下面； 如果C等于0，则要搬动的构件将放到最高层。 【标准输出】 由十行组成，分别为组成新艺术品的第一层到第十层构件的编号。 【约束条件】 （1） 10≤N≤20000 1≤k≤1000 （2） 1≤A≤B≤N， 0≤C≤N-(B-A+1) 【 样 例 】 提示：样例中仅是常规的测试数据输入及对应结果，特殊情况需要全面考虑，自己设计测试数据验证算法的健壮性。13 3 6 12 1 2 9 0 10 13 8 标准输出结果： 6 7 8 9 10 11 12 2 3 4 [实现提示]