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