数据结构课程设计题目

数据结构课程设计

一、设计目的

　　数据结构是计算机专业的核心课程，是计算机科学的算法理论基础和软件设计的技术基础。它主要研究信息的逻辑结构及其基本操作在计算机中的表示和实现。

　　数据结构是实践性很强的课程。课程设计是加强学生实践能力的一个强有力手段。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。

二、设计要求

　　1、课程设计题目共20题，每人一题；

2、课程设计时间为1周；

3、设计语言不限；

同学在处理每一个题目的时候，要从分析题目的需求入手，按设计抽象数据类型、构思算法、实现抽象数据类型、编制上机程序代码并调试的步骤完成题目，最终写出完整的分析报告。

见到题目，案头工作准备不足，忙于上机敲程序不是优秀程序员的工作风格。注意设计与实现过程的经验积累，编码应尽量利用学习阶段的成熟数据结构包（即头文件），加大代码的重用率。

三、提交相关内容要求

1． 源程序：

按照课程设计的具体要求所开发的源程序，源程序的名字务必与所做题目相关；

2．课程设计报告（具体格式见后面所附示例）：

（保存在word 文档中，文件名要求 按照"姓名-学号-课程设计报告"起名，如文件名为“张三-082054101-课程设计报告.doc”）。

四、成绩评定

通过程序实现、总结报告和学习态度综合考评，并结合学生的动手能力，独立分析解决问题的能力和创新精神。成绩分优、良、中、及格和不及格五等。考核标准包括：

算法思想的正确性，包括是否采用了合适的数据存储结构等。 （30%）

程序实现的正确性，包括程序整体结构是否合理、编程风格是否规范等。 （20%）

学生的工作态度、独立工作能力。 （30%）

课程设计报告（含课程设计心得）。 （20%）

发现课程设计基本雷同，一律不及格。

五、设计题目

1、农夫过河问题

【问题描述】

一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫能撑船。因为狼吃羊，羊吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请问农夫该采取什么方案才能将所有的东西运过河呢？

2、医院选址问题

【问题描述】

有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总体来说较短，设计较合理。

3、图书管理系统

【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【基本要求】

1)每种书的登记内容包括书号、书名、著作者、现存量和库存量；

2)对书号建立索引表（线性表）以提高查找效率；

3)系统主要功能如下：

*采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
*借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
*归还：注销对借阅者的登记，改变该书的现存量。

4、商品货架管理

[问题描述]

商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的生产日期最近。　上货时，需要倒货架，以保证生产日期较近的商品在较下的位置。

5、停车场管理

[问题描述]

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

6、学生成绩管理

[问题描述]

给出n个学生的m门考试的成绩表，每个学生的信息由学号、姓名以及各科成绩组成。对学生的考试成绩进行有关统计：按总数高低次序，打印出名次表，分数相同的为同一名次；按名次打印出每个学生的学号、姓名、总分以及各科成绩，并打印统计表。

7、校园导游程序

[问题描述]

用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。

[要求]

（1） 查询各景点的相关信息；

（2） 查询图中任意两个景点间的最短路径。

（3） 查询图中任意两个景点间的所有路径。

（4） 增加、删除、更新有关景点和道路的信息。

8、员工管理系统

[问题描述]

每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统能够完成员工信息的查询、更新、插入、删除、排序等功能。

[要求]

（1） 排序：按不同关键字，对所有员工的信息进行排序。

（2） 查询：按特定条件查找员工。

（3） 更新：按编号对某个员工的某项信息进行修改。

（4） 插入：加入新员工的信息。

（5） 删除：按编号删除已离职的员工的信息。

9、模拟全国交通咨询

[问题描述]

为旅客提供三种最优决策的交通咨询。此程序规定：

（1） 在程序中输入城市名称时，需输入10个字母以内的字母串；输入列车或飞机编号时需输入一个整型数据；输入列车或飞机的费用时需输入一个实型数据；输入列车或飞机开始时间和到达时间时均需输入两个整型数据（以hh：mm的形式）；在选择功能时，应输入与所选功能对应的一个整型数据。

（2） 程序的输出信息主要是：最快需要多少时间才能到达，或最少需要多少旅费才能到达，或最少需要多少次中转到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。

[要求]

提供对城市信息的编辑，提供列车时刻表和飞机航班表的编辑。

提供三种最优决策：最快到达、最省钱到达、最少中转次数到达。

10、 迷宫求解

[问题描述]

走迷宫是实验心理学中一个古典问题。用计算机解迷宫路径的程序，就是仿照人走迷宫而设计的，也是对盲人走路的一个机械模仿. 计算机解迷宫时，通常用的是"穷举求解"的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。

11、狐狸逮兔子

[问题描述]

围绕着山顶有10个圆形排列的洞，狐狸要吃兔子，兔子说：“可以，但必须找到我，我就藏身于这十个洞中，你先到１号洞找，第二次隔１个洞（即3号洞）找，第三次隔２个洞（即6号洞）找，以后如此类推，次数不限。”但狐狸从早到晚进进出出了1000次，仍没有找到兔子。问兔子究竟藏在哪个洞里？

12、根据上车和下车站的地点查询换乘公交车的可行方案

[问题描述]

以无向图的形式可以描述城市公交车的线路换乘情况，其中的每一条公交车线路用一个无向图的顶点表示，彼此间可倒车的线路可用顶点之间的边表示，边还应包含换乘的车站等信息。一小型的线路图与数据结构无向图的对应情况，如下图所示。

每一条公交线路的所有路经车站可用一个线性表表示，一般根据上车站和下车站的询问请求都可以查到各自对应的线性表，也就确定了线路所对应的图顶点。换车的可行方案就是在两个顶点之间求出一条路径，并转换成实际的换乘线路和车站。

[要求]

线路交叉的换乘站和重合的线路车站使用同一的站名，当输入合法的上、下车站名时，将输出换乘线路，乘车方向、路经车站和换乘的车站。

[实现提示]

该题目的主要数据结构包括图和一组线性表，以及准备输出数据用的辅助数据结构。路径搜索可以考虑用DFS或BFS 遍历算法，搜索到的每一条路径需要使用临时空间缓存。乘车方向能够从乘车站与换乘站的位置关系来设法确定。

13．航空订票系统

[问题描述]

为航空管理员提供方便，为旅客提供航空定票录入. 查询.咨询. 订票. 退票. 修改航班信息等功能。

[要求]

（1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）。

（2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，抵达城市，航班票价，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；

（3）订票：（订票情况可以存在一个数据文件中，结构自己设定）

可以订票，如果该航班已经无票，可以提供相关可选择航班；

（4）退票： 可退票，退票后修改相关数据文件；

客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。

（5）修改航班信息：

当航班信息改变可以修改航班数据

14．通讯录管理系统

[问题描述]

设计一个通讯录管理系统。通讯录内容包括：姓名、家庭住址、出生日期、电话号码。采用链表来做。

[要求]

实现创建、输出、排序（电话号码）、插入、删除、查找等功能。

15．管道铺设施工的最佳方案选择

[问题描述]

N(N>10)个居民区之间需铺设煤气管道。假设任意两个居民区之间都可铺设，但代价不同。事先将任意居民区之间铺设管道的代价存入文件。设计一个最佳方案，使得这N个居民区间铺设管道的代价最小，希望能以图形形式在屏幕上输出结果。

16 散列表的设计与实现

【问题描述】
设计散列表实现电话号码查找系统。
【要求】
1) 设每个记录有下列数据项：电话号码、用户名、地址；
2) 从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；
3) 采用一定的方法解决冲突；
4) 查找并显示给定电话号码的记录；
5) 查找并显示给定用户名的记录。
【选做内容】
1) 系统功能的完善；
2) 设计不同的散列函数，比较冲突率；
3) 在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。

17 一元多项式的加法、减法、乘法的实现。

【问题描述】

设有一元多项式Am(x)和Bn(x).
  Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm
  Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn
 请实现求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。

【要求】
1) 首先判定多项式是否稀疏
2) 分别采用顺序和动态存储结构实现；
3) 结果M(x)中无重复阶项和无零系数项；
4) 要求输出结果的升幂和降幂两种排列情况

18最少换车次数问题

【问题描述】

设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车都是单向的，这n个车站被顺序编号为0-n-1。编号程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。

【要求】

求得从站0出发乘公交车至站n一1的最少换车次数。

【设计思路】

利用输入信息构建一张有向图G(用邻接短阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边＜i,j)。这样，从站x至站y的最少上车次数便对应于图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

19 火车售票系统

【问题描述】

通过此系统可以实现售票、退票、车票剩余情况查询等功能。每张车票包含车次、座位信息。
【要求】

在售票、退票、查询剩余票等环节中，都必须显示出车票的信息，即车次、座位情况。为简单起见，在此假设所有出售的车票均为同一车次的车票。退票时，必须是车站售出的车票才能退，否则视为无效票，不能退票。

系统能实现的功能如下：

a.  查询：根据旅客提出的终点站名输出下列信息：车次、日期、乘员定额、余票额、票价和折扣信息；

b . 订票：根据客户提出的要求（车次号、订票数）查询该车次票额情况，若有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。

c. 退票：根据客户提供的情况（日期、车次），为客户办理退票手续；

【提示】

所涉及的信息有：

终点站信息（终点站名、车次号、乘车日期、乘客定额、余票量、票价、折扣信息等）

已订票的客户名单（包括姓名、车次、证件编号、订票量）

20 实时监控报警系统

【问题描述】

建立一个报警和出警管理的系统。

【要求】

1. 采用一定的存储结构存储报警信息，要求有内容、时间；

2. 有一次的出警就应该在待处理的信息中删除这条信息；

3. 记录出警信息；

4. 待处理信息过多时会发出警告；

《数据结构》课程设计报告示例

一、课程设计题目: 给定

二、需求分析

说明程序设计的任务，强调的是程序要做什么，明确规定：

1、输入的形式和输入值的范围；

2、输出的形式；

3、程序所能达到的功能；

4、测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。

三、概要设计

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次（调用）关系。

四、详细设计

各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）
　　源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。

五、程序使用说明、测试分析及结果

1、说明如何使用你编写的程序；

2、测试结果与分析；

3、每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。

4、运行界面。

六、课程设计总结

总结可以包括 : 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容。

本文来源：https://www.2haoxitong.net/k/doc/bc67f732a32d7375a417804f.html