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

算法与数据结构实验报告学院 专业 姓名 学号 算法与数据结构实验报告学院 专业 姓名 学号 实验1： ADT List（线性表） （6学时）问题描述线性表是典型的线性结构，实现ADT List，并在此基础上实现两个集合的交运算和并运算。实验目的（1）掌握线性表的链表存储结构。（2）掌握在单链表上基本操作的实现。（3）在掌握单链表的基本操作上进行综合题的实现。实验内容及要求（1） 要求用带头结点的单链表存储两个集合中的元素和最终的结果。（2） 集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。（3） 显示两个集合的内容及其交集和并集的内容。（4） 要求不改变原来的集合，交集和并集分别另外存放。 测试数据（1） set1=3, 8, 5, 8,11，set2=22, 6, 8, 3, 15,11,20 set1set2set1set2（2） 其中一个集合为空集（3） 两个集合都是空集（4） 创建集合时有重复数据的情况算法与数据结构实验报告学院 专业 姓名 学号 实验2：利用栈将中缀表达式转换为后缀表达式并进行计算（6学时）问题描述 中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。实验目的 （1） 深入理解栈的特性。（2） 掌握栈结构的构造方法。实验内容及要求（1） 中缀表达式中只包含、/ 运算及（ 和 ）。 （2） 可以输入任意中缀表达式,数据为一位整数。（3） 显示中缀表达式及转换后的后缀表达式(为清楚起见，要求每输出一个数据用逗号隔开)。（4） 对转换后的后缀表达式进行计算。 测试数据（1） 63*(9-7)-8/2 转换后的后缀表达式为： 计算结果为：（2） (8-2)/(3-1)*(9-6) 转换后的后缀表达式为：算法与数据结构实验报告学院 专业 姓名 学号 实验3：队列的应用（6学时）问题描述实现一个简单银行叫号模拟系统。银行有三个窗口可以同时办理业务，当有用户到达银行时，首先选择自己要办理的业务，可以选择一种或多种。系统计算办理此业务所需的时间并显示给用户，然后系统查看有无空闲的窗口，如果有，通知用户到一个空闲窗口办理，如果没有空闲窗口，则需安排用户到某个窗口等候，系统先计算每个队列中用户办理业务的总时间，将用户安排到时间最短的队列等候。模拟输出多个用户办理业务的过程。输入举例如下：用户1在时间1到达银行，在1号窗口办理业务，需要1分钟用户1在时间2结束，离开用户2在时间3达到。在1号窗口开始办理，办理业务需要4分钟 用户3在时间3到达，在2号窗口开始办理，办理业务需要5分钟用户4在时间5到达，在3号窗口开始办理，办理需要8分钟用户5在时间6到达，在1号窗口等待，办理业务需要4分钟用户2在时间8办理完业务，离开用户5在时间8在1号窗口，办理业务需要4分钟用户6在时间8到达，在1号窗口等待，办理业务需要6分钟用户7在时间8到达，在2号窗口等待，办理业务需要10分钟 实验目的（1）深入理解队列的特性。（2）掌握使用队列实现某些问题。实验内容及要求1建立3个队列存储在三个窗口等待的用户2建立业务类，描述业务种类，业务所需时间3建立用户类，描述用户办理的业务，用户的状态等4可以随机产生用户进入银行的时间，让用户输入所需办理的业务。算法与数据结构实验报告学院 专业 姓名 学号 实验4： 实现二叉树的基本操作 (9学时)问题描述 树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。实验目的（1） 熟练掌握二叉树的结构特性。（2） 掌握二叉树的各种存储结构的特点及实用范围。（3） 通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。（4） 熟练掌握各种遍历二叉树的递归和非递归算法。实验内容及要求（1）用二叉链表表示一个大家族的家谱。根为祖先结点，每个结点的左子树是其第一个孩子，右子树是其下一个兄弟。（2）创建时可以根据前序遍历序列进行创建，也可以以其他方式创建。创建好之后写入文件。（3）创建好二叉链表之后实现以下功能 a)从文件读出，在屏幕上以树的形式或层次的形式显示，如下图所示： b)输入一个结点值，输出其双亲及其所有子女，以及所有兄弟结点值 c)输入一个结点值，插入一个结点作为其子女算法与数据结构实验报告学院 专业 姓名 学号 实验5：哈夫曼树的编/译码器系统的设计(9学时)问题描述利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）。对于可以双向传输的信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。 实验目的 （1） 通过哈夫曼树的定义，掌握构造哈夫曼树的意义。（2） 掌握构造哈夫曼树的算法思想。（3） 通过具体构造哈夫曼树，进一步理解构造哈夫曼树编码的意义。实验内容及要求(1) 从终端读入字符集大小为n（即字符的个数），逐一输入n个字符和相应的n个权值（即字符出现的频度），建立哈夫曼树，将它存于文件 hfmtree 中。并将建立好的哈夫曼树以树或凹入法形式输出;对每个字符进行编码并且输出。(2) 利用已建好的哈夫曼编码文件 hfmtree ，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。 测试数据 用下表给出的字符集和频度的实际统计数据建立哈夫曼树：字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：THIS PROGRAM IS MY FAVORITE改进 将文本输入文件，先统计文本中的每个字符出现的频率，然后再建立哈夫曼树。 算法与数据结构实验报告学院 专业 姓名 学号 实 验6：图的遍历（9学时）问题描述 给定一个无向图或有向图，利用深度优先遍历和广度优先遍历对给定图进行遍历。实验目的 （1） 熟悉图的两种常用的存储结构。（2） 掌握对图的两种遍历方法，即深度优先遍历和广度优先遍历。（3） 进一步掌握利用递归或队列结构进行算法设计方法。实验内容及要求（1）构造一个具有n个顶点的无向图或有向图。（2）输出以深度优先遍历和广度优先遍历后的顶点序列。测试数据 以下图作为测试数据： 思考（1） 考虑如何把递归实现的深度优先遍历算法改为非递归算法？算法与数据结构实验报告学院 专业 姓名 学号 实 验7：利用Prim算法求无向网的最小生成树（9学时）问题描述 如要在n个城市之间建设通信网络，只需架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是求一个无向网的最小生成树问题。实验目的 （1） 掌握图的各种存储结构和基本操作。（2） 对于实际问题的求解会选用合适的存储结构。（3） 通过Priml算法理解如何求无向网的最小生成树。实验内容及要求 （1）构造具有n个顶点的无向网，并利用Priml算法求网的最小生成树。 （2）以文本形式输出所求得的最小生成树中各条边以及它们的权值。测试数据 以下图作为测试数据： 思考（1） 如何判断输入的无向网存在最小生成树? 若不存在，请分析是何缘故?（2） 在设计该算法时，你遇到的最大困难是什么? 你是如何解决的?算法与数据结构实验报告学院 专业 姓名 学号 实 验8：内部排序算法比较 （9学时）问题描述排序是计算机程序设计中一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。本实验熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率进行进一步的了解。实验目的 （1） 深刻理解排序的定义和各类排序的算法思想，并能灵活应用。（2） 掌握各类排序的时间复杂度的分析方法，能从“关键字间的比较次数”分析算法的平均情况、最好情况和最坏情况。（3） 理解排序方法“稳定”和“不稳定”的含义。实验内容及要求 数据由输入或随机函数产生。 实现快速排序、堆排序和归并排序算法（任选二）。 至少要用5组不同的输入数据做比较（每组数据不小于100），统计测试数据的准确的关键字的比较次数和移动次数（需在算法的适当位置插入对关键字的比较次数和移动次数的计数） 对结果做出简单的分析。 测试数据 由随机函数产生（还应考虑正序、逆序和随机序列）。思考（1） 对于快速排序，就平均时间而言，它