allanchain / dsa Goto Github PK

车辆管理问题

某单位最多100辆车辆，每辆车的基本信息包括：车号、车型、购买日期、购买价格、驾驶员名称、违章记录等。其中，各辆车的违章次数可能差别很大（有的一次没有，有的可能有数十次）。每次违章记录中包括：违章时间、违章地点、违章代码（如闯红灯、违规停车等）、违章处理等。

现思考：

• 数据结构？哪种存储结构能够有效地表达上述车辆管理问题；
• 如何查找某辆车的违章信息？
• 如何统计某一个时间段内所有车的违章记录？
• 如何统计某一个地点的所有违章记录？
• 如何统计某一违章代码的所有违章记录？
• 新买车，车辆报废问题；
• 新违章记录加入，违章处理后的修改？

统计违章记录时，需要给出车号、违章记录数目等。

实现上述车辆管理的程序，包括车辆信息的文件导入/导出和显示等。

要求：

1. 给定一个TXT文本文件（见“附件”文件：CCode.txt），读取TXT文件并对TXT文件中的所有字符进行统计（可采用fgetc读取各个字符，含英文小写字符、标点符号、回车和换行等，不含中文字符），获取字符数和各个字符的出现频次，然后构造Huffman树。
2. 基于Huffman树，获得各个字符的Huffman编码。通过各个字符的Huffman编码，将原来TXT文件的整个字符序列转换为一个对应的0/1码序列，输出到对应的0/1码文件（TXT文件，命名为：Huffman编码.txt）。
3. 读取该0/1码文件，基于Huffman树，实现整个0/1码文件的Huffman译码，再将译码结果输出到一个TXT文件（命名为：Huffman译码.txt），并检查与原来的TXT文件（CCode.txt）是否一致。

实现 KMP 无回溯模式匹配算法。

具体算法见教科书

给定记录序列：{ 79，8，6，93，59，84，55，9，71，33，16 }

实现“堆排序”、“基数排序”和“二路归并排序”的算法。

要求：一个工程（Project)，不同排序方法对应不同源程序（即：一种方法对应一个源程序）。

本作业的目的：理解几种重要排序方法的**、过程和算法。

多叉路口交通信号灯的管理

通过分析所有可能的行驶路线，分成若干组。对分组的要求是：任一个组内各个方向行驶的车辆可以同时安全行驶而不发生碰撞。

实现二叉排序树建立和检索算法

词索引表建立

图书检索中，通常要建立“关键词-书号索引表”

⇓

步骤

1. 输入一本书名，提取关键词（需要与常用词表对比）
2. 在索引表中查找该关键词是否存在。如不存在，则加入该关键词（按照字典有序原则进行，并建立书号索引；如存在，这在该关键词项中加入书号索引。
3. 继续输入下一本书名，重复上述操作。

数据结构

词表

存放书名中的各个关键词，数量有限，采用顺序结构存储，每个词是一个字符串

索引表

虽然动态生成，并且需要频繁插入，但考虑到该表主要用于查询，因此采用顺序存储结构。表中每个索引项包含两方面内容：关键词和书号索引。书号索引由于是动态生成的，且数目不同，宜采用链表结构存储。

农夫带一只狼、一只羊、一棵白菜过河，船小的每次只能带一样东西，由于狼能吃羊、羊能吃白菜，因此留下的两样东西不能任意组合。那么，农夫采用何种方案才能将所有东西不损害地运过河？