《算法与数据结构》

1、算法与数据结构实验报告学院专业姓名学号实验1线性表的操作(12学时)问题描述假设一个班级内有n个学生，定义一个学生类和一个班级类。学生类中包括学号、姓名、性别、年龄、专业等属性；班级类包括一个学生对象链表。定义如下：class Stude nt int id;/ 学号char name20; /姓名int age; / 年龄/请设置学生类中相应的操作class MyClassStude nt *stu_head; / 链表表头指针int total;/学生总数char man ager20; 班主任姓名/ public:MyClass()创建新班，学生数为0void insertStu(Stu

2、dent s); /在班内中插入学生 s,插入后保持学号没有重复并且按学号递增void deleteStu(int i) ; /删除学号为i的学生void display(); /显示班内所有学生的信息和其它信息void search(int i);按照学号i查找学生，并输出其信息void search( char *s); /按照姓名查找学生，如果有重名的学生，则输出所有学生void join(MyClass &class2 ); II将class2班合并到本班，合并后保证学号没有重复并且按学号递增void seperate(MyClass &c1,MyClass &

3、c2);II 按照性别分成两个班cl 和 c2II其它方法实验目的（1）掌握链表的基本操作。（2）熟练类的定义以及类之间的关系实验内容及要求（1）实现MyClass类中所列出的方法；（2）编写主函数测试类中的方法。算法与数据结构实验报告学院专业姓名学号实验2:利用栈将中缀表达式转换为后缀表达式并进行计算（3学时）问题描述中缀表达式是最普通的一种书写表达式的方式，而后缀表达式不需要用括号来表示，计算 机可简化对后缀表达式的计算过程，而该过程又是栈的一个典型应用。实验目的（1）深入理解栈的特性。（2）掌握栈结构的构造方法。实验内容及要求（1） 中缀表达式中只包含+、一、x、/运算及（和）。（2）可

4、以输入任意中缀表达式，数据为一位整数。（3）显示中缀表达式及转换后的后缀表达式 （为清楚起见，要求每输出一个数据用逗 号隔开）。（4）对转换后的后缀表达式进行计算。例如输入：中缀表达式：6 + 3*（9-7）-8/2输出：转换后的后缀表达式为：6,3,9,7,-,*,+,8,2,-计算结果为：8算法与数据结构实验报告学院专业姓名学号实验3:行编辑程序问题（3学时）问题描述一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端 上进行输入时，不能保证不出差错，因此，若在编辑程序中，“每接受一个字符即存入用户数据区”的做法显然不是最恰当的。较好的做法是，设

5、立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。允许用 户输入出差错，并在发现有误时可以及时更正。例如，当用户发现刚刚键入的一个字符是错的时，可补进一个退格符"#"，以表示前一个字符无效；如果发现当前键入的行内差错较多或难以补救，则可以键入一个退行符”"，以表示当前行中的字符均无效。 如果已经在行首继续输入 #符号无效。实验目的（1）深入理解栈的特性。（2）掌握使用递归实现某些问题。（3）设计出应用栈解决在实际问题背景下对较复杂问题的递归算法。实验内容及要求（1）实现简单行编辑器，可以输入一个多行的字符序列。但行字符总数（包含退格符和退行 符

6、）不大于250。（2） 利用顺序栈保存从终端接收的字符，每行回车时显示经过编辑的本行字符，例如：用户输入为:voL#id mia#ai n() churchar ch;输出为：void mai n() char ch;算法与数据结构实验报告学院专业姓名学号实验4:队列的应用（6学时）问题描述实现一个简单银行叫号模拟系统。银行有三个窗口可以同时办理业务，当有用 户到达银行时，首先选择自己要办理的业务，可以选择一种或多种。系统计算办理 此业务所需的时间并显示给用户，然后系统查看有无空闲的窗口，如果有，通知用 户到一个空闲窗口办理，如果没有空闲窗口，则需安排用户到某个窗口等候，系统 先计算每个队列中

7、用户办理业务的总时间，将用户安排到时间最短的队列等候。模 拟输出多个用户办理业务的过程。输入举例如下：用户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分钟实验目的

8、（1）深入理解队列的特性。（2）掌握使用队列实现某些问题。实验内容及要求1 建立3个队列存储在三个窗口等待的用户2建立业务类，描述业务种类，业务所需时间3. 建立用户类，描述用户办理的业务，用户的状态等4可以随机产生用户进入银行的时间，让用户输入所需办理的业务算法与数据结构实验报告学院专业姓名学号实验5:实现二叉树的基本操作（12学时）问题描述树和二叉树是最常用的非线性结构 （树型结构），其中以二叉树最为常见，本实验题要求实现二叉树的最基本操作，其中遍历二叉树是二叉树各种操作的基础，它分为先序、中序和后序。实验目的（1）熟练掌握二叉树的结构特性。（2）掌握二叉树的各种存储结构的特点及实用范围。

9、（3）通过二叉树的基本操作的实现，从而思考一般树的基本操作的实现。（4）熟练掌握各种遍历二叉树的递归和非递归算法。实验内容及要求（1） 用树表示一个大家族的家谱。家谱树中的结点表示家谱中的成员，包括编号，姓名,性别等信息。家谱树的存储结构为二叉链表。根为祖先结点，每个结点的左子树是其第一个孩子，右子树是其下一个兄弟。（2）创建家谱树：可以根据前序遍历序列进行创建，也可以以其他方式创建。创建好之 后写入文件保存。（3）显示家谱：在屏幕上以树的形式或层次的形式显示家谱。（4）查询：a.输入一个结点值（编号或姓名），输出其双亲及其所有子女，以及所有兄弟 结点信息。b.输入一个结点值（编号或姓名），查

10、询他是祖先（根节点）的第几代子孙。（5） 插入：输入一个结点值（编号姓名），插入一个结点作为其子女。6）考虑家谱中是否允许有重名的情况。算法与数据结构实验报告学院专业姓名学号实验6:查找算法（6学时）问题描述利用顺序表实现顺序查找、二分查找算法。实验目的1、掌握顺序表的查找2、掌握折半查找算法3、对实际查找问题学会选用一种合适的查找算法求解4、比较不同查找算法的效率实验内容及要求（1）将实验1的学生类Student中添加一个手机号码属性,在班级类Class中增 加一个生成通讯录的方法，该方法将全班同学的姓名（假设无重名）和手机号码取出，存入一个顺序结构中，生成通讯录，并写入文件（以后可以直接从

11、文件中读取 通讯录）。（2）利用顺序查找算法查找某学生的手机号码。（3）按姓名排序，利用折半查找算法查找某学生的手机号码。（4）统计并比较两种算法中关键字的比较次数。（5）建议定义一个通讯录类，将有关属性和方法进行圭寸装。算法与数据结构实验报告学院专业姓名学号实验7:哈夫曼树的编/译码器系统的设计（9学时）问题描述利用哈夫曼编码进行通讯可以大大提高信道利用率，缩短信息传输时间，降低传输成本。 但是，这要求在发送端通过一个编码系统对待传数据进行预先编码；在接受端将传来的数据进 行解码（复原）。对于可以双向传输的信道，每端都要有一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统。

12、实验目的（1）通过哈夫曼树的定义，掌握构造哈夫曼树的意义。（2）掌握构造哈夫曼树的算法思想。（3）通过具体构造哈夫曼树，进一步理解构造哈夫曼树编码的意义。实验内容及要求(1) 建立哈夫曼树：从终端读入字符集大小为 n (即字符的个数)，逐一输入 n个字符和相应的n个权值(即字符出现的频度)如表 1所示，建立哈夫曼树，将它存于文件 hfmtree中。 并将建立好的哈夫曼树以树或凹入法形式输出；对每个字符进行编码并且输出。(2) 编码：利用已建好的哈夫曼编码树，对键盘输入的正文进行译码。输出字符正文，再输出该文的二进制码。(3) 译码：输入一串二进制编码，利用你建立的哈夫曼树，将其进行译码，输出字

13、符正文。表1：字符集和及其频度：字符ABCDEFGHIJKLMN频度641322321032115475715322057字符OPQRSTUVWXYZ空格频度63151485180238181161168并实现以下报文的译码和输出：THIS PROGRAM IS MY FA VORITE算法与数据结构实验报告学院专业姓名学号实验8：校园导游(12学时)问题描述设计校园景点图，包含校园各景点以及景点之间的路径， 所含景点不少于8个 以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息，以边表示景点 之间的路径，边的权值表示路径长度。设计一个校园导游程序，提供校园导游信息。实验目的(1) 熟

14、悉图的两种常用的存储结构（2）掌握对图的两种遍历方法，即深度优先遍历和广度优先遍历。进一步掌握利用递归或队列结构进行算法设计方法。（3）掌握prime算法和最短路径算法实验内容及要求（1）景点查询：输入景点名称或编号，提供景点相关信息的查询。（2）分别按照深度优先和广度优先算法，将校园每个景点的信息输出且仅输出一次。（3）利用Priml算法求图的最小生成树，设计使各个景点之间连通代价最小的一种（4）提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短路径。算法与数据结构实验报告学院专业姓名学号实 验9:内部排序算法比较（9学时）问题描述排序是计算机程序设计中一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。本实验熟悉几种典型的排序方法，并对各种算法的特 点、使用范围和效率进行进一步的了解。实验目的（1）深刻理解排序的定义和各类排序的算法思想，并能灵活应用。（2）掌握各类排序的时间复杂度的分析方法，能从“关键字间的比较次