《算法与数据结构》实验报告(20130909).doc

内蒙古大学 计算机学院&软件学院 算法与数据结构实验报告算法与数据结构实验报告班级_ 姓名_ 学号_实验1：线性表的建立及操作（6学时）问题描述 定义一个图书类和一个书库类。图书类包括图书编号、书名、作者（只考虑第一作者）、定价等属性；书库类包括一个指向图书链表的头指针以及操作链表的相关函数。这两个类的定义如下：class Book int BookNumber; /图书编号 char BookName50; /书名 char AuthorName30; /第一作者姓名 double Price; /定价 Book *next; /指向下一个图书对象的指针public: void print(); /输出图书的所有属性 ;class BookStoreBook *book_head; /图书链表的头指针 public:BookStore(); /创建书库对象，图书链表的头指针为空Book* createBook(); /创建一个图书对象void insertBook(Book *b); /按定价从高到低将图书对象插入到图书链表void deleteBook(int booknumber); /从链表中删除图书编号为booknumber的图书double getTotalPrice(); /获得该书库中图书的定价之和int getBookCount(); /获得该书库中图书的数目Book* findBook(int booknumber); /按照图书编号查找图书，并输出图书信息Book* findBook(char *str); /按照书名或者作者查找图书，并输出图书信息void print(); /输出该书库中所有图书信息BookStore(); /释放书库对象 . /根据需要设置其它方法;实验目的（1） 熟悉面向对象程序设计中链表结点的定义以及链表的建立过程；（2） 掌握链表的基本操作，包括：遍历链表、插入结点、删除结点等。实验内容及要求（1） 在Visual C+ 6.0环境下，编写程序实现图书类和书库类；（2） 在主函数中建立一个图书链表，并测试图书类和书库类中的相关方法。第15页，共15页算法与数据结构实验报告班级_ 姓名_ 学号_实验2：线性表的应用（6学时）问题描述 通过单链表实现整数集合的交（）、并（）、异或（XOR）运算。其中：两个集合A和B的异或运算的结果是属于A且不属于B的元素和属于B且不属于A的元素。实验目的（1） 熟练掌握链表的基本操作；（2） 运用链表解决实际问题。实验内容及要求（1） 编写程序，设计结点类，通过链表描述整数集合；（2） 在主函数中建立两个递增排序的整数链表，对这两个链表依次执行交、并、异或运算，并输出相应结果；如果运算结果为“空”，则输出“NULL”；（3） 由于同一个集合中不能同时存在两个相同的元素，因此在一个链表中不应存在数值相同的两个结点；（4） 当执行集合的异或运算时，不开辟新空间，只在原有的两个链表上进行操作。示例输入/输出示例输入：105 15 7 9 100 -43 18 9 -100 66156 5 200 -9 88 7654 0 16 22 -12 -100 365 1 8 123示例输出：第一个集合共有9个元素，分别是：-100 -43 5 7 9 15 18 66 100第二个集合共有15个元素，分别是：-100 -12 -9 0 1 5 6 8 16 22 88 123 200 365 7654两个集合的交共有2个元素，分别是：-100 5两个集合的并共有22个元素，分别是：-100 -43 -12 -9 0 1 5 6 7 89 15 16 18 22 66 88 100 123 200365 7654两个集合的异或共有20个元素，分别是：-43 -12 -9 0 1 6 7 8 9 1516 18 22 66 88 100 123 200 365 7654算法与数据结构实验报告班级_ 姓名_ 学号_实验3：栈和队列的应用（12学时）问题描述 设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入停车场；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场；每辆停放在车场的车在它离开停车场时，必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。实验目的（1） 理解栈（先进后出）和队列（先进先出）的工作特点；（2） 掌握栈结构的构造方法以及栈的基本操作（出栈、入栈）；（3） 掌握队列的构造方法以及队列的基本操作（出队列、入队列）；（4） 运用栈和队列解决实际问题。实验内容及要求（1） 以栈模拟停车场，以队列模拟停车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：(i) 汽车“到达”或“离去”信息，(ii) 汽车牌照号码，（iii) 到达或离去的时刻。（2） 对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间（单位是小时）和应交纳的费用（在便道上停留的时间不收费），假设停车费为每小时m元。（3） 栈和队列均采用链表结构实现。（4） 提示：需另设一个栈（也用链表结构实现），临时停放为给要离去的汽车让路而从停车场退出来的汽车。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。示例输入/输出设n=2，m=5，则输入数据为：2 5A 1 10A 2 15D 1 20A 3 23A 4 28A 5 31A 6 33D 2 45D 4 70E其中：A表示到达（Arrival）；D表示离去（Departure）；E表示程序结束（End）。输出数据为：汽车1停靠在停车场1号位置汽车2停靠在停车场2号位置汽车1停车13小时，缴纳停车费65元汽车3停靠在停车场2号位置汽车4停靠在便道的1号位置汽车5停靠在便道的2号位置汽车6停靠在便道的3号位置汽车2停车30小时，缴纳停车费150元汽车4停靠在停车场2号位置 （说明：汽车4进入停车场的时间为汽车2离开的时间）汽车4停车25小时，缴纳停车费125元其中：停车场从北至南的序号依次为1（栈底）n（栈顶）；便道上的停车序号从1（队列头）开始，往后依次增一。选作内容（1） 等候在便道上的汽车可以直接从便道上开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾，并使得原来排在前面的汽车仍然排在前面。（2） 汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如：1辆7座客车和1.5辆小汽车的占地面积相同，收费为每小时3元；1辆卡车占地面积相当于2辆小汽车的占地面积，收费为每小时4元；一辆公共汽车占地面积相当于3量小汽车的占地面积，收费为每小时6元等等；因此，等候在便道上的汽车无法可能无法进入停车场（假设停车场总面积为M，当前停车场的空余面积小于汽车所需占地面积）。算法与数据结构实验报告班级_ 姓名_ 学号_实验4：面向数字图像的Huffman编/译码器的设计与实现（1215学时）问题描述 “Huffman-树”不仅能对文本数据进行编码、译码，提高文本数据的传输效率，同时它也能对多媒体数据（如：数字图像、视频等）进行编码、译码，从而实现多媒体数据的压缩存储。目前，在Web互联网上广泛使用的JPEG图像格式就采用了Huffman编码，与其他图像格式（如：BMP、TIF等）相比，同一副图像采用JPEG格式时所需的存储空间是最少的。在这个实验中，请设计一个Huffman编/译码器，并模拟数字图像的压缩存储（编码）和解码显示（译码）的过程。实验目的（1） 掌握“Huffman-树”的构造过程；（2） 通过该实验，深入理解Huffman编码的原理及作用；（3） 运用Huffman编码解决实际问题。实验内容及要求（1） 构造“Huffman-树”：. 读入一个大小为N*M（N为图像的高度，M为图像的宽度）的灰度图像块，该图像中的每个像素（元素）的取值范围是0255，取值为0表示该像素是“黑色”，取值为255表示该像素是“白色”，其他取值表示介于“黑色”和“白色”之间的灰度值。. 统计读入图像块中每种灰度值出现的次数，并去除出现次数为零的灰度值，以此作为构造“Huffman-树”所需的权值。. 说明：在构造“Huffman-树”的过程中，当有多个待合并元素的权值相同时，每次选择灰度值较小的两个元素进行合并。（2） Huffman编码（压缩存储）：读入新的灰度图像块，利用已建立好的“Huffman-树”对其进行编码，将图像的宽度、高度信息和编码结果保存到文件（如：compress_image.txt）中，同时计算Huffman编码的压缩比并输出。压缩比的计算公式如下：压缩比=原始图像所需比特数/压缩后图像所需比特数。（3） Huffman译码（解码显示）：读入压缩存储的灰度图像，利用已建立好的“Huffman-树”对其进行译码，将译码结果按照原有宽度、高度还原图像，并将还原之后的图像保存到文件（如：decoding_image.txt）中。示例输入/输出设N=8，M=8，则输入数据为：8 8162162162161162157163161162162162161162157163161162162162161162157163161162162162161162157163161162162162161162157163161164164158155161159159160160160163158160162159156159159155157158159156157输出数据为：Huffman编码的压缩比为2.38:1 （512比特/215比特）算法与数据结构实验报告班级_ 姓名_ 学号_实验5：小型文本搜索引擎的实现（1215学时）问题描述 随着互联网技术的飞速发展，如何从海量数据中查找所需内容，不仅是科研人员关注的热点问题，许多IT公司也先后推出了各自的搜索引擎，如：Google、百度、Bing等。搜索引擎的核心是如何对Web网页构建有效的索引，以便能够快速查找和匹配查询关键词，并及时地将搜索结果返回给用户。在这个实验中，请实现一个英文单词的二叉查找树，并可根据输入的英文单词进行搜索，同时可给出单词在文档中的位置信息。实验目的（1） 掌握二叉查找树的构造过程；（2） 掌握二叉查找树中结点的插入、删除等操作；（3） 掌握二叉树的前序、中序遍历；（4） 运用二叉查找树解决实际问题。实验内容及要求（1） 构造二叉查找树：. 从文件中读入内容，过滤掉阿拉伯数字和标点符号，并将英文字母的大写形式全部转换成小写形式。. 按照英文字母表的顺序构造英文单词的二叉查找树。当两个英文单词的首字母相同时，按第二个字母进行排序，依次类推。. 为每个英文单词建立一个单链表，用于存放该单词在文档中的位置信息（即：该单词是文档的第几个单词，序号从1开始）。如果一个单词在文档中出现多次，则该链表中将包含多个结点，并按照单词在文档中出现的次序（位置信息）递增排序。（2） 遍历二叉查找树：. 实现二叉查找树的先序遍历，以便能够找出出现次数最多的单词；. 搜索：输入一个待检索单词，以先序遍历的方式从二叉查找树中查找单词，如果能找到该单词，则输出该单词在原始文档中出现的位置信息，否则提示文档中不包含该检索词；. 实现二叉查找树的中序遍历，并将遍历结果保存到文件中（words.txt）。（要求：每个单词占一行，每行依次记录单词、该单词出现的次数、以及该单词在文档中的位置信息。）（3） 删除结点：. 给定一个停用词列表（停用词是指对搜索没有作用的词，如：of, and, a, an, the等等），将二叉查找树中的属于停用词表中的单词依次删除（不仅删除结点，还需清空记录该单词位置信息的单链表）；. 在搜索时，当输入的检索词是停用词时，则不进行查询。选作内容（1） 允许一次输入两个或者更多个单词进行查询，即：先获得这些单词各自在文档中出现的位置信息，然后再分析这些单词的位置信息，判断这些单词在原始文档中是否存在连续出现的情况。（2） 尝试实现从多个文档中读入内容，构建二叉查找树，并实现多个文档的搜索。算法与数据结构实验报告班级_ 姓名_ 学号_实验6：道路选择问题（6学时）问题描述 某省自从实行了畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。现在，已知起点和终点，请你设计程序计算出要从起点到终点的最短距离。实验目的（1） 掌握图的邻接矩阵表示法和邻接表表示法；（2） 掌握无向图的最小生成树算法（Prim和Kruskal）；（3） 运用最小生成树算法解决实际问题。实验内容及要求（1） 本题目包含多组输入数据。（2） 每组数据的第一行包含两个正整数N和M（0N200，0M1000），分别代表现有的城镇数目和已修建的道路数目。城镇分别以0N-1编号。（3） 接下来是M行道路信息。每一行有三个整数A，B，X（0=A, BN；A!=B；0X10000），分别表示城镇A、城镇B，以及城镇A和城镇B之间有一条长度为X的双向道路。（4） 再接下一行有两个整数S，T（0=S,TN），分别代表起点和终点。（5） 对于每组输入数据，利用Prim算法或者Kruskal算法构建相应的最小生成树，并输出最短需要行走的距离。如果不存在从S到T的路线，则输出-1。示例输入/输出输入数据为：3 30 1 10 2 31 2 10 23 10 1 11 2输出数据为：2-1算法与数据结构实验报告班级_ 姓名_ 学号_实验7：内部排序算法比较（9学时）问题描述 排序是计算机程序设计中一种重要操作，它的功能是将一个数据元素（或记录）的任意序列重新排列成一个按关键字有序的序列。本实验熟悉几种典型的排序方法，并对各种算法的特点、使用范围和效率进行进一步的了解。实验目的 （1） 深刻理解排序的定义和各类排序的算法思想，并能灵活应用。（2） 掌握各类排序的时间复杂度的分析方法，能从“关键字间的比较次数”分析算法的平均情况、最好情况和最坏情况。（3） 理解排序方法“稳定”和“不稳定”的含义。实验内容及要求（1） 数据由输入或随机函数产生。（2） 实现简单插入排序、简单选择排序、快速排序、堆排序和归并排序算法等。（3） 至少要用5组不同的输入数据做比较（每组数据不小于100，应考虑正序、逆序和随机序列），统计关键字的比较次数和移动次数（需在算法的适当位置插入对关键字的比较次数和移动次数的计数）、稳定性、最好情况、最坏情况、平均情况等。（4） 对结果做出简单的分析。算法与数据结构实验报告班级_ 姓名_ 学号_实验8：数列极差问题（9学时）(附加)问题描述 随机生成n个正整数排成一个数列，进行如下操作：每次去掉其中两个数a和b，然后在数列中的加入一个数ab+1，如此下去，直至剩下一个数为止。在所有按这种操作方式最后得到的数中，最大的数记做max