内蒙古大学 计算机学院&软件学院 《算法与数据结构》实验报告
《算法与数据结构》实验报告
班级____________ 姓名___________ 学号_____________
实验1：线性表的应用（6学时）
[问题描述]
通过单链表实现整数集合的交（∩）、并（∪）、差（－）运算。其中：集合A与集合B差运算的结果是属于集合A但不属于集合B的元素。
[实验目的]
（1） 熟练掌握链表的基本操作； （2） 运用链表解决实际问题。
[实验内容及要求]
（1） 编写程序，设计结点类，通过链表描述整数集合；
（2） 在主函数中建立两个递增排序的整数链表，对这两个链表依次执行交、并、异
或运算，并输出相应结果；如果运算结果为“空”，则输出“NULL”；
（3） 由于同一个集合中不能同时存在两个相同的元素，因此在一个链表中不应存在
数值相同的两个结点。
[示例输入/输出]
示例输入： 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
两个集合的差共有7个元素，分别是： -43 7 9 15 18 66 100
第1页，共7页
内蒙古大学 计算机学院&软件学院 《算法与数据结构》实验报告
《算法与数据结构》实验报告
班级____________ 姓名___________ 学号_____________
实验2：栈和队列的应用（9学时）
[问题描述]
设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入停车场；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场；每辆停放在车场的车在它离开停车场时，必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。
[实验目的]
（1） （2） （3） （4）
理解栈（先进后出）和队列（先进先出）的工作特点； 掌握栈结构的构造方法以及栈的基本操作（出栈、入栈）； 掌握队列的构造方法以及队列的基本操作（出队列、入队列）； 运用栈和队列解决实际问题。
[实验内容及要求]
（1） 以栈模拟停车场，以队列模拟停车场外的便道，按照从终端读入的输入数据序
列进行模拟管理。每一组输入数据包括三个数据项：(i) 汽车“到达”或“离去”信息，(ii) 汽车牌照号码，（iii) 到达或离去的时刻。
（2） 对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停
车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间（单位是小时）和应交纳的费用（在便道上停留的时间不收费），假设停车费为每小时m元。
（3） 等候在便道上的汽车可以直接从便道上开走，但此时排在它前面的汽车要先开
走让路，然后再依次排到队尾。
（4） 栈和队列均采用链表结构实现。
（5） 提示：需另设一个栈（也用链表结构实现），临时停放为给要离去的汽车让路
而从停车场退出来的汽车。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
[示例输入/输出]
设n=2，m=5，则输入数据为： 2 5
A 1 10
第2页，共7页
内蒙古大学 计算机学院&软件学院 《算法与数据结构》实验报告
A 2 15 D 1 20 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停车10小时，缴纳停车费50元 汽车3停靠在停车场2号位置 汽车4停靠在便道的1号位置 汽车5停靠在便道的2号位置 汽车6停靠在便道的3号位置
汽车2停车30小时，缴纳停车费150元
汽车4停靠在停车场2号位置 （说明：汽车4进入停车场的时间为汽车2离开的时间） 汽车4停车25小时，缴纳停车费125元
其中：停车场从北至南的序号依次为1（栈底）~n（栈顶）；便道上的停车序号从1（队列头）开始，往后依次增一。
[选作内容]
（1） 汽车可有不同种类，则他们的占地面积不同，收费标准也不同，如：1辆7座
客车和1.5辆小汽车的占地面积相同，收费为每小时3元；1辆卡车占地面积相当于2辆小汽车的占地面积，收费为每小时4元；一辆公共汽车占地面积相当于3量小汽车的占地面积，收费为每小时6元等等；因此，等候在便道上的汽车无法可能无法进入停车场（假设停车场总面积为M，当前停车场的空余面积小于汽车所需占地面积）。
第3页，共7页
内蒙古大学 计算机学院&软件学院 《算法与数据结构》实验报告
《算法与数据结构》实验报告
班级____________ 姓名___________ 学号_____________
实验3：小型文本搜索引擎的实现（12~15学时）
[问题描述]
随着互联网技术的飞速发展，如何从海量数据中查找所需内容，不仅是科研人员关注的热点问题，许多IT公司也先后推出了各自的搜索引擎，如：Google、百度、Bing等。搜索引擎的核心是如何对Web网页构建有效的索引，以便能够快速查找和匹配查询关键词，并及时地将搜索结果返回给用户。在这个实验中，请实现一个英文单词的二叉查找树，并可根据输入的英文单词进行搜索，同时可给出单词在文档中的位置信息。
[实验目的]
（1） （2） （3） （4）
掌握二叉查找树的构造过程；
掌握二叉查找树中结点的插入、删除等操作； 掌握二叉树的前序、中序遍历； 运用二叉查找树解决实际问题。
[实验内容及要求]
（1） 构造二叉查找树：
①. 从文件中读入内容，过滤掉阿拉伯数字和标点符号，并将英文字母的大写
形式全部转换成小写形式。
②. 按照英文字母表的顺序构造英文单词的二叉查找树。当两个英文单词的首
字母相同时，按第二个字母进行排序，依次类推。
③. 为每个英文单词建立一个单链表，用于存放该单词在文档中的位置信息（即：该单词是文档的第几个单词，序号从1开始）。如果一个单词在文档中出现多次，则该链表中将包含多个结点，并按照单词在文档中出现的次序（位置信息）递增排序。
（2） 遍历二叉查找树：
①. 实现二叉查找树的先序遍历，以便能够找出出现次数最多的单词；
②. 搜索：输入一个待检索单词，从二叉查找树中查找单词，如果能找到该单
词，则输出该单词在原始文档中出现的位置信息，否则提示文档中不包含该检索词；
③. 实现二叉查找树的中序遍历。（要求：每个单词占一行，每行依次记录单
词、该单词出现的次数、以及该单词在文档中的位置信息。）
（3） 删除结点：
①. 给定一个停用词列表（停用词是指对搜索没有作用的词，如：of, and, a, an,
the等等），将二叉查找树中的属于停用词表中的单词依次删除（不仅删除结点，还需清空记录该单词位置信息的单链表）；
第4页，共7页
内蒙古大学 计算机学院&软件学院 《算法与数据结构》实验报告
②. 在搜索时，当输入的检索词是停用词时，则不进行查询。
[选作内容]
（1） 允许一次输入两个或者更多个单词进行查询，即：先获得这些单词各自在文档
中出现的位置信息，然后再分析这些单词的位置信息，判断这些单词在原始文档中是否存在连续出现的情况。
（2） 尝试实现从多个文档中读入内容，构建二叉查找树，并实现多个文档的搜索。
第5页，共7页
《算法与数据结构》实验报告(20140301)
