本科生《算法与数据结构》实验报告3

第1页《算法与数据结构》实验报告学院专业姓名学号实验1：ADTList（线性表）（3学时）[问题描述]线性表是典型的线性结构，实现ADTList，并在此基础上实现两个集合的交运算或并运算。[实验目的]（1）掌握线性表链表存储结构。（2）掌握在单链表上基本操作的实现。（3）在掌握单链表的基本操作上进行综合题的实现。[实验内容及要求]（1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。（2）集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。（3）显示两个集合的内容及其运算结果。[测试数据]（1）set1={3,8,5,8,11}，set2={22,6,8,3,15,11,20}set1∪set2＝set1∩set2＝（2）set1={1,3,5,7}，set2={2,3,7,14,25,38}set1∪set2＝set1∩set2＝第2页[思考]（1）分析你所设计的算法的时间复杂度？(2)若输入两个集合内的元素是递增的，见测试数据(2)，请你提出一种时间复杂度更少的算法思想，并分析时间复杂度是多少？第3页《算法与数据结构》实验报告学院专业姓名学号实验2：利用栈将中缀表达式转换为后缀表达式并进行计算（3学时）[问题描述]中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。[实验目的]（1）深入理解栈的特性。（2）掌握栈结构的构造方法。[实验内容及要求]（1）中缀表达式中只包含＋、－、×、/运算及（和）。（2）可以输入任意中缀表达式,数据为一位整数。（3）显示中缀表达式及转换后的后缀表达式(为清楚起见，要求每输出一个数据用逗号隔开)。（4）对转换后的后缀表达式进行计算。栈的类定义如下：#includeiostream.hconstintStackSize=50;classStack{char*StackList;inttop;public:Stack(){StackList=newchar[StackSize];top=-1;}第4页boolIsEmpty();boolIsFull();voidPush(charx);charPop();charGetTop();voidpostexpression();};//Stack[测试数据]（1）6＋3*(9-7)-8/2转换后的后缀表达式为：计算结果为：（2）(8-2)/(3-1)*(9-6)转换后的后缀表达式为：计算结果为：[思考]（1）把中缀表达式转化为后缀表达式的好处？第5页（2）考虑当表达式中数据的位数超过一位时，如何修改你的程序？困难在哪？第6页《算法与数据结构》实验报告学院专业姓名学号实验3：n皇后问题（6学时）[问题描述]在一个n×n的国际象棋棋盘上按照每行顺序摆放棋子，在棋盘上的每一个格中都可以摆放棋子，但任何两个棋子不得在棋盘上的同一行、同一列、同一斜线上出现，利用递归算法解决该问题，并给出该问题的n个棋子的一个合理布局。[实验目的]（1）深入理解栈的特性。（2）掌握使用递归实现某些问题。（3）设计出应用栈解决在实际问题背景下对较复杂问题的递归算法。[实验内容及要求]（1）从棋盘的第一行开始放起。（2）输出最后每个棋子的在棋盘上的坐标(最好以矩阵形式输出)。[测试数据]自定n值。[思考]（1）设计一个递归算法的三要素是什么？第7页（2）考虑用非递归实现该问题，并从中总结递归算法和非递归算法的优、缺点各是什么？（3）通过对递归算法的理解，总结把一个递归算法转换为非递归算法的方法(可查参考书)，并把求n的阶乘的递归算法转换为非递归算法。第8页《算法与数据结构》实验报告学院专业姓名学号实验4：打印二项展开式(a+b)n的系数（3学时）[问题描述]将二项式(a+b)n展开，系数构成著名的杨辉三角形，这是典型的对队列的应用。[实验目的]（1）深入理解队列的特性。（2）掌握使用队列实现某些问题。[实验内容及要求]要求打印形式为11121133114641……………[测试数据]自定n值。[思考]（1）杨辉三角形中系数之间的关系是什么？（2）栈和队列各应用于什么范围？第9页《算法与数据结构》实验报告学院专业姓名学号实验5：实现二叉树的基本操作(6学时)[问题描述]树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。[实验目的]（1）熟练掌握二叉树的结构特性。（2）掌握二叉树的各种存储结构的特点及实用范围。（3）通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。（4）熟练掌握各种遍历二叉树的递归和非递归算法。[实验内容及要求]（1）创建二叉树：createBTree(…)所谓创建二叉树是指按照某一种或某两种遍历序列建立起来的二叉树的存储结构。（2）求叶结点的数目：getLeavesNum()（3）画二叉树：drawBTree()（4）输出二叉树的中序遍历序列。[测试数据]（1）以下图所示1或2的形状画出二叉树(不需画线)，从中体会画这两种形状的图的难易程度。第10页图2FCHEDBAAHFEDCB图1中序遍历序列结果为：（2）自己设定几组序列来验证程序的正确性。[思考]（1）若二叉树采用顺序存储，有什么缺点？（2）根据任意两种遍历序列重建二叉树，然后给出另外一种遍历序列。（3）在遍历二叉树的算法中，你用的是递归算法？还是非递归算法？若你用的是递归算法，请考虑用非递归算法实现对二叉树的遍历；反之考虑用递归算法实现对二叉树的遍历。第11页《算法与数据结构》实验报告学院专业姓名学号实验6：哈夫曼树的编/译码器系统的设计(6学时)[问题描述]利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）。对于可以双向传输的信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。[实验目的]（1）通过哈夫曼树的定义，掌握构造哈夫曼树的意义。（2）掌握构造哈夫曼树的算法思想。（3）通过具体构造哈夫曼树，进一步理解构造哈夫曼树编码的意义。[实验内容及要求](1)从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件hfmtree中。并将建立好的哈夫曼树以树或凹入法形式输出;对每个字符进行编码并且输出。(2)利用已建好的哈夫曼编码文件hfmtree，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。[测试数据]用下表给出的字符集和频度的实际统计数据建立哈夫曼树：字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：THISPROGRAMISMYFAVORITE第12页[思考](1)利用哈夫曼编码，为什么能使报文中的电文总长度减少?(2)为什么利用哈夫曼算法求出的一个字符的编码都不是其它字符编码的前缀？第13页《算法与数据结构》实验报告学院专业姓名学号实验7：图的遍历（6学时）[问题描述]给定一个无向图或有向图，利用深度优先遍历和广度优先遍历对给定图进行遍历。[实验目的]（1）熟悉图的两种常用的存储结构。（2）掌握对图的两种遍历方法，即深度优先遍历和广度优先遍历。（3）进一步掌握利用递归或队列结构进行算法设计方法。[实验内容及要求]（1）构造一个具有n个顶点的无向图或有向图。（2）输出以深度优先遍历和广度优先遍历后的顶点序列。[测试数据]以下图作为测试数据：ahgfedcb输出结果：第14页[思考]（1）在你所设计的算法中，使用了什么数据结构？（2）考虑如何把书上给出的递归实现的深度优先遍历算法改为非递归算法？第15页《算法与数据结构》实验报告学院专业姓名学号实验8：利用Kruskal算法求无向网的最小生成树（6学时）[问题描述]如要在n个城市之间建设通信网络，只需架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是求一个无向网的最小生成树问题。[实验目的]（1）掌握图的各种存储结构和基本操作。（2）对于实际问题的求解会选用合适的存储结构。（3）通过Kruskal算法理解如何求无向网的最小生成树。[实验内容及要求]（1）构造具有n个顶点的无向网，并利用Kruskal算法求网的最小生成树。（2）以文本形式输出所求得的最小生成树中各条边以及它们的权值。[测试数据]以下图作为测试数据：36595567345254ahgfedcb输出结果：第16页[思考]（1）如何判断输入的无向网存在最小生成树?若不存在，请分析是何缘故?（2）在输入数据过程中，你如何处理一条边(权值不同)输入1次以上的情况?（3）在设计该算法时，你遇到的最大困难是什么?你是如何解决的?第17页《算法与数据结构》实验报告学院专业姓名学号综合设计实验题目以下综合题目可根据实际情况选做。题目1：内部排序算法比较（6学时）[问题描述]排序是计算机程序设计中一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。本实验熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率进行进一步的了解。[实验目的]（1）深刻理解排序的定义和各类排序的算法思想，并能灵活应用。（2）掌握各类排序的时间复杂度的分析方法，能从“关键字间的比较次数”分析算法的平均情况、最好情况和最坏情况。（3）理解排序方法“稳定”和“不稳定”的含义。[实验内容及要求]①数据由输入或随机函数产生。②实现快速排序、堆排序和归并排序算法。③至少要用5组不同的输入数据做比较（每组数据不小于100），统计测试数据的准确的关键字的比较次数和移动次数（需在算法的适当位置插入对关键字的比较次数和移动次数的计数）④对结果作出简单的分析。[测试数据]由随机函数产生（还应考虑正序、逆序和随机序列）。第18页[思考]（1）对于快速排序，就平均时间而言，它被认为是目前最好的一种内部排序方法，但它对应某些特殊序列（例如正序和逆序），时间复杂度是最差的，你认为这种原因是如何造成的？对算法如何做改进可以避免这一情况？（2）为什么利用堆排序比用简单选择排序能降低时间复杂度？（3）归并排序适用于元素个数少的还是多的？空间利用率怎么样？（4）分析快速排序、堆排序和归并排序的时间复杂度在平均情况下和最坏情况下各为多少？第19页《算法与数据结构》实验报告学院专业姓名学号题目2：伙伴系统（6学时）[问题描述]伙伴系统属于动态存储管理系统中的一种，系统通过响应用户提出的“请求”和“释放”内存的大小而对内存进行管理，在用户提出“请求”时，分配一块大小“恰当”的内存区给用户；在用户释放内存区时及时回收。与其它动态存储管理方法不同的是：无论是占用块还是空闲块，其大小均为2的k次幂（k为某个正整数）。[实验目的]（1）掌握数组的应用；（2）掌握静态链表的应用；（3）掌握内存管理的分配与回收；[实验内容及要求]（1）最小内存块是4字节，最大是64K。（2）API有：initiate(intk):初始化,k是空间的大小，即2的k次方。new(intk):分配大小为2的k次方的块。free(intad):释放首地址为ad的块。getMap():按地址顺序显示内存块的情况，如：0-15:04//0–15表示内存块的首尾地址，0表示该块空闲16-31:1432-95:15……每行的格式为：a–b:tka–b:表示内存块的首尾地址；t:0表示该块空闲，1表示占用；k:表示内存块的大小为2的k次方；（3）构造2个分配回收序列进行测试，其中至少有5次分配，3次回收。第20页[测试数据]（1）你的测试序列1是：按测试序列执行分配回收后内存情况是：（2）你的测试序列2是：按测试序列执行分配回收