数据结构2016课程设计题及要求

1、项目项目一：一：停车场管理系统的设计与实现停车场管理系统的设计与实现（8学时学时）停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在停车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。问

2、题描述：问题描述： 1.基本要求 （1）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。 （2）每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。 （3）栈以顺序结构实现，队列以链表实现。 2.重点、难点 重点：针对停车场问题的特点，利用栈的后进先出特点，选择栈这种数据结构来模拟停车场，利用队列先进先出的特点，选择队列这种数据结构来模拟车场外的

3、便道。 难点：离散事件问题的模拟算法设计与求解。 3.作业及课外学习要求： 按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。项目项目二：二： 旅游景点咨询系统的设计与实现旅游景点咨询系统的设计与实现（12学时学时） 问题描述：问题描述：创建一个至少有15个点的有向网表示的某个旅游景点的导游图。顶点代表景点,类型为字符串（例如，泰山导游图：“天地广场门”，“十八盘”，“冯玉祥墓”，“桃花峪门”，“中天门”，“南天门”，“玉皇顶”等），弧表示两个景点之间可以直达，弧上的权值表示两个景点之间的路程（公里数），弧上还有到达方法的信息（有步行和索道两种）。建立一个游客咨询系统。1.基本要求

4、（1）创建图的存储结构。（2）输入两个景点名，就可以得到从一个景点到达另一个景点的所有简单路径、相应路径的路程公里数、行走的方法（每一段是步行，还是坐索道）；（3）输入两个景点名，就可以得到其最短路径，即：路程最短的行进方法；如果两者无路径可通，就得出“两景点不可达的信息”。2.重点、难点重点：（1）通过实验掌握图状结构数据的存储与表式； （2）通过实验掌握对图的存储、遍历、运算等各种操作；（3）深入理解图的特征及应用；难点：（1）任意两个景点所有路径的计算；（2）最短路径的计算与算法设计。3.作业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。项目项目三：三：

5、通讯录查询系统的设计与实现通讯录查询系统的设计与实现( 8学时学时) 问题描述：问题描述：为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的电话与地址。设计散列表存储，设计并实现通讯录查找系统。1.基本要求（1）每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码为关键字建立散列表；（3）采用二次探测再散列法解决冲突；（4）查找并显示给定电话号码的记录；（5）通讯录信息文件保存。2.重点、难点重点：（1）通过实验深入理解哈希表既是一种存储形式，又是一种查找方法；（2）哈希表的构造；（3）哈希冲突方案的设计。难点：哈希表的构造与哈希冲突方案的设计3.作

6、业及课外学习要求：按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。项目项目四：四： 哈夫曼编哈夫曼编/译码系统的设计与实现译码系统的设计与实现( 8-12学时学时) 问题描述问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编译码系统。1.基本要求（1）初始化（Initialzation）。从数据文件DataFile.data中读入字符及每个

7、字符的权值，建立哈夫曼树HuffTree；（2）编码（EnCoding）。用已建好的哈夫曼树，对文件ToBeTran.data中的文本进行编码形成报文，将报文写在文件Code.txt中；（3）译码（Decoding）。利用已建好的哈夫曼树，对文件CodeFile.data中的代码进行解码形成原文，结果存入文件Textfile.txt中；（4）输出（Output）。输出DataFile.data中出现的字符以及各字符出现的频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt； 2.重点、难点 重点： （1）通过实验

8、理解哈夫曼树的特征及其应用； （2）哈夫曼树的构造算法设计； （3）利用构造的哈夫曼树进行编码和译码。 难点： （1）字符的哈夫曼树编码及存储； （2）字符的译码与串的匹配算法。 3.作业及课外学习要求： 按照题意要求独立进行设计，设计结束后要按要求写出课程设计报告。课程设计报告规范 实验报告的开头应给出实验报告的开头应给出题目题目、班级班级、姓名姓名、学号学号以及以及完成日期完成日期等，等，请为自己设计请为自己设计一个封面一个封面。正文一般包括以下。正文一般包括以下6方面内容：方面内容：1 .需求分析需求分析在该部分中根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求

9、做什么？限制条件是什么？ 1.1问题描述 1.2基本要求 (1) 输入的形式和输入值的范围； (2) 输出的形式； (3) 程序所能达到的功能。2. 概要设计概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1) 数据结构 (2)程序模块(3) 各模块之间的调用关系以及算法设计 课程设计报告规范3. 详细设计详细设计 实现概要设计中定义的所有数据类型,对每个操作写出C/C+语言算法;对主程序和其他模块也都需要写出C/C+语言算法；写出函数和过程的调用关系。 4. 测试与分析测试与分析 测试数据，输出测试的结果。这里的测试数据应该完整和严格，

10、包括正确的输入及其输出结果和含有错误的输入及其输出结果。并对结果进行分析（主要包括：调试过程中遇到的问题是如何解决的；算法的时空分析和改进设想；经验与体会等）。 5. 附录附录 源程序清单（带详细注释的源程序）。如果提交源程序代码，可以只列出程序文件名的清单。6. 用户使用手册 用户使用手册告诉用户如何使用你编写的程序，详细列出每一步的操作步骤和使用规则等。 每个设计项目需要提交的材料每个设计项目需要提交的材料 1.电子档：电子档：由以下三个部分组成，缺一不可 源程序：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）； 上交程序的说明文件：（保存在.txt中）在说明文档中应该写明上交程序所在的目录，上交程序的主程序文件名，如果需要安装，要有程序的安装使