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

《本科生《算法与数据结构》实验报告2012》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《算法与数据结构》实验报告学院专业姓名学号《算法与数据结构》实验报告学院专业姓名学号实验1：ADTList（线性表）（6学时）[问题描述]线性表是典型的线性结构，实现ADTList，并在此基础上实现两个集合的交运算和并运算。[实验目的]（1）掌握线性表的链表存储结构。（2）掌握在单链表上基本操作的实现。（3）在掌握单链表的基本操作上进行综合题的实现。[实验内容及要求]（1）要求用带头结点的单链表存储两个集合中的元素和最终的结果。（2）集合的元素限定为十进制数，程序应对出现重复的数据进行过滤，即链表中没有重复数据。（3）显示两个集合的内容及其交集和并集

2、的内容。（4）要求不改变原来的集合，交集和并集分别另外存放。[测试数据]（1）set1={3,8,5,8,11}，set2={22,6,8,3,15,11,20}set1∪set2＝set1∩set2＝第13页（1）其中一个集合为空集（2）两个集合都是空集（3）创建集合时有重复数据的情况第13页《算法与数据结构》实验报告学院专业姓名学号实验2：利用栈将中缀表达式转换为后缀表达式并进行计算（6学时）[问题描述]中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。[实

3、验目的]（1）深入理解栈的特性。（2）掌握栈结构的构造方法。[实验内容及要求]（1）中缀表达式中只包含＋、－、×、/运算及（和）。（2）可以输入任意中缀表达式,数据为一位整数。（3）显示中缀表达式及转换后的后缀表达式(为清楚起见，要求每输出一个数据用逗号隔开)。（4）对转换后的后缀表达式进行计算。[测试数据]（1）6＋3*(9-7)-8/2转换后的后缀表达式为：计算结果为：（2）(8-2)/(3-1)*(9-6)转换后的后缀表达式为：第13页《算法与数据结构》实验报告学院专业姓名学号实验3：队列的应用（6学时）[问题描述]实现一个简单银行叫号模拟系统

4、。银行有三个窗口可以同时办理业务，当有用户到达银行时，首先选择自己要办理的业务，可以选择一种或多种。系统计算办理此业务所需的时间并显示给用户，然后系统查看有无空闲的窗口，如果有，通知用户到一个空闲窗口办理，如果没有空闲窗口，则需安排用户到某个窗口等候，系统先计算每个队列中用户办理业务的总时间，将用户安排到时间最短的队列等候。模拟输出多个用户办理业务的过程。输入举例如下：用户1在时间1到达银行，在1号窗口办理业务，需要1分钟用户1在时间2结束，离开用户2在时间3达到。在1号窗口开始办理，办理业务需要4分钟用户3在时间3到达，在2号窗口开始办理，办理业务

5、需要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．建立业务类，描述业务种类，业务所需时间第13页3．建立用户类，描述用户办理的业务，用户的状态等4．可以随机产生用户进入银行

6、的时间，让用户输入所需办理的业务。第13页《算法与数据结构》实验报告学院专业姓名学号实验4：实现二叉树的基本操作(9学时)[问题描述]树和二叉树是最常用的非线性结构(树型结构)，其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。[实验目的]（1）熟练掌握二叉树的结构特性。（2）掌握二叉树的各种存储结构的特点及实用范围。（3）通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。（4）熟练掌握各种遍历二叉树的递归和非递归算法。[实验内容及要求]（1）用二叉链表表示一个大家族的家

7、谱。根为祖先结点，每个结点的左子树是其第一个孩子，右子树是其下一个兄弟。（2）创建时可以根据前序遍历序列进行创建，也可以以其他方式创建。创建好之后写入文件。（3）创建好二叉链表之后实现以下功能a)从文件读出，在屏幕上以树的形式或层次的形式显示，如下图所示：b)输入一个结点值，输出其双亲及其所有子女，以及所有兄弟结点值c)输入一个结点值，插入一个结点作为其子女第13页《算法与数据结构》实验报告学院专业姓名学号实验5：哈夫曼树的编/译码器系统的设计(9学时)[问题描述]利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这

8、要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进行解码（复原）。对于可以双向传输的