数据结构课程设计题目.doc

数据结构课程设计题目

14
2020年4月19日
文档仅供参考
10月30日下午4点到4点30分之间上交到创新大楼西4楼405
1、选好题目：每人一题。
2、独立思考，独立完成：按照软件工程的流程设计与开发系统。首先写好需求分析。利用模块化的编程思想来完成系统的设计，给出详细地分析过程，画出程序流程图。编写程序，调试各模块。学会从问题入手，分析研究数据结构中数据表示和数据处理的特性，以便为应用所涉及的数据选择适当的逻辑结构、存储结构和相应的操作算法，并初步掌握时间和空间分析技术。要求书写符合软件工程规范的文件。课程设计中各任务的设计和调试要求独立完成。
3、做好上机准备：明确课程设计任务，提高课程设计认识。做好资料搜集，上网查询所需资料，认真独立完成问题分析和设计内容，编写程序，准备好测试数据，要充分利用好时间。
4、上机任务：按照上机之前准备的实验程序及测试数据进行调试，调试过程要规范，认真记录调试结果及调试过程中出现的问题，积极解决问题，最终得到正确的源程序。
5、
6、成果提交
课设报告、程序源代码和程序的说明文件必须上交。按照课设报告模板认真书写课程设计报告。
纸介质课设报告（必须采用B5纸打印）
电子文档包括“源代码（*.cpp）”、“可执行文件(*.exe)”、“课程设计报告(*.doc)”和一个说明文件（如果有的话），放入一个以“课设题目（姓名）”为名字的文件夹中。

注意：1）独立完成，源代码雷同者视为抄袭，双方均以不及格论处；
2）课程设计报告60% 以上雷同视为抄袭，双方均以不及格论处。
3）无课设报告、程序或课设报告抄袭者，成绩为不及格。
注意：一旦发现原封不动的使用网上下载或某个书籍中的源代码和/或课程设计报告的，成绩为不及格。

1、运动会分数统计
问题描述：
参加运动会的n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m＋w。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。哪些项目取前五名或前三名由学生自己设定。写一个统计程序产生各种成绩单和得分报表。
基本要求：
(1)各项目结束时，输入前三名或前五名的项目编号、运动员姓名、校名和名次（成绩）；
(2)产生各学校的成绩单，内容包括每个学校所取得的每项成绩的项目号、名次（成绩）、姓名和得分，并统计各学校总分；
(3)能够按学校编号、男女团体总分排序输出；
(4)能够按学校编号查询学校某个项目的情况；
(5)能够按项目编号查询取得前三或前五名的学校。
2、一元多项式计算器
问题描述：
设有一元多项式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)。
基本要求：
⑴首先判定多项式是否稀疏；
⑵分别采用顺序和链式结构实现；
⑶结果M(x)中无重复阶项和无零系数项；
⑷要求输出结果的升幂和降幂两种排列情况。
3、火车售票系统的设计与实现
问题描述：
经过此系统能够实现售票、退票、车票剩余情况查询等功能。每张车票包含车次、车厢、座位信息。
基本要求：
⑴在售票、退票、查询剩余票等环节中，都必须显示出车票的信息，即车次、车厢、座位情况。
⑵为简单起见，在此假设所有出售的车票均为同一车次的车票。
⑶退票时，必须是车站售出的车票才能退，否则视为无效票，不能退票，而且退票能够再次销售。
4、图书管理系统的设计与实现
问题描述：
设计一个计算机管理系统完成图书管理基本业务。
基本要求：
⑴每种书的登记内容包括书号、书名、著作者、现存量、库存量和借阅信息；
⑵对书号建立索引顺序表以提高查找效率；
⑶系统主要功能如下：
①采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
②借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
③归还：注销对借阅者的登记，改变该书的现存量。
5、客户消费积分管理系统的设计与实现
问题描述：
针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠。
基本要求：
⑴采用一定的存储结构进行客户信息的存储；
⑵对客户的信息能够进行修改、删除、添加；
⑶能够根据消费情况进行客户积分的累加；
⑷根据积分情况，对客户实行不同程度的打折优惠；
6、学生成绩管理系统的设计与实现
问题描述：
能够实现对学生成绩的常见管理功能。
基本要求：
⑴采用一定的存储结构对学生成绩进行管理；
⑵能够进行成绩的录入、查询、修改、删除等操作；
⑶能够查询某门课程的平均分，学生的排名，不同分数段的学生人数及学生信息等；
⑷能够查询某学生的各课程分数，总分及学生的班级排名等；
⑸能够按学号排序输出全部学生的成绩信息、总分及班级排名等。
7、车厢调度问题
问题描述：
假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2，3，…n。设计一个程序,求出所有可能由此输出的长度为n 的车厢系列。
基本要求：
⑴设计一个程序，求出由一个编号依次为1，2，、、、，n的车厢序列可能产生的所有出栈系列。
⑵利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。
⑶对于每个输出序列演示出所有操作序列的变化过程 。
8、迷宫求解
任务：以一个m*n的长方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
要求：首先实现一个栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组(i,j,d)的形式输出，其中(i,j)指示迷宫中的一个坐标，d表示走到下一坐标的方向。
9、语言中平衡符号的问题
要求：设C语言程序代码中包含如下符号/* */，()，[]，{}，编写程序检测一段C代码中上述符号是否正确。
10、算术表示式求解
问题描述：给定一个算术表示式，应用算符优先表示式求值算法求解结果。
基本要求：
(1)从键盘输入要求解的算术表示式；
(2)采用栈结构进行算术表示式的求解过程；
(3)能够判断算术表示式正确与否；
(4)对于错误表示式给出提示；
(5)对于正确的表示式给出最后的结果,并能够显示运算的整个过程。
11、表示式求值，可供小学生作业，并能给出分数
要求：建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括号的混合运算；随时能够退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。
12、哈夫曼树及其编码
问题描述：
设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。
基本要求：
⑴初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
⑵编码：利用建好的哈夫曼树生成哈夫曼编码；
⑵ 输出其哈夫曼树及哈夫曼编码；
⑶ 设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 197 64 13 22 32 103 21 15 47 57 5 1 20 32
字符 N O P Q R S T U V W X Y Z
频度 57 63 1 15 48 16 80 23 8 18 1 51 1
13、简单目录管理系统的设计与实现
任务：利用树型结构设计并实现一个简单的目录管理系统，该系统能够对所有目录进行管理，如目录的新建、删除、查询、目录名称修改、按某种顺序输出所有目录（树的遍历操作）、以树型结构输出所有目录等功能。
14、家谱管理系统的设计与实现
任务：设计并实现一个简单的家谱管理系统。 
基本要求： 
（1）建立家族关系并能存储到文件中。 
（2）实现家族成员的添加、删除功能。 
（3）能够查询家族成员的双亲、祖先、兄弟、 孩子和后代等信息。
（4）按某种顺序输出家谱信息（树的遍历操作）、以树型结构输出家谱资料等功能。
15、校园导游咨询系统的设计与实现　　
问题描述：
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
基本要求：
⑴设计华东交通大学南区的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
⑵为来访客人提供图中任意景点相关信息的查询。
⑶为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。
16、地图着色问题
问题描述：
设计地图着色软件，对江西地图中11个地级市进行着色，要求相邻地级市所使用的颜色不同，并保证使用的颜色最少。
基本要求：
⑴地图采用图型数据结构，每个地级市为一个节点，边表示对应的两个地级市相邻。
⑵设计着色算法，保证邻接点不是同一种颜色。
⑶演示程序以用户和计算机的对话方式进行。
17、内部排序算法比较
问题描述：
试经过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：
⑴至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。
⑵待排序表的表长不小于100，其中的数据要用伪随机数产生程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
⑶最后对结果作出简单分析，包括对各组数据得出结果波动大小的解释。
18、哈希表的设计与实现——线性探测再散列
问题描述：
设计哈希表实现电话号码查找系统。
基本要求：
（1）设每个记录有下列数据项：电话号码、用户名、地址；
（2）从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；
（3）采用线性探测再散列的方法解决冲突；
（4）查找并显示给定电话号码的记录；
（5）查找并显示给定用户名的记录。
19、哈希表的设计与实现——二次探测再散列
问题描述：
设计哈希表实现电话号码查找系统。
基本要求：
(1)设每个记录有下列数据项：电话号码、用户名、地址；
(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；
(3)采用二次探测再散列的方法解决冲突；
(4)查找并显示给定电话号码的记录；
(5)查找并显示给定用户名的记录。
20、哈希表的设计与实现——链地址法
问题描述：
设计哈希表实现电话号码查找系统。
基本要求：
(1)设每个记录有下列数据项：电话号码、用户名、地址；
(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立不同的哈希表；
(3)采用链地址法解决冲突；
(4)查找并显示给定电话号码的记录；
(5)查找并显示给定用户名的记录。
21、通讯录管理系统的设计与实现——哈希表
任务：利用哈希表完成通讯录的一般性管理工作：
(1)添加信息；
(2)显示信息：能够按照手机或联系人的姓名拼音排序显示；
(3)查找：可用不同的关键字作为查找的依据，进行查找；
(4)编辑信息；
(5)删除信息；
(6)保存到文件；
要求：
(1)界面友好，可重复操作。
(2)每条记录至少包括姓名、手机、QQ、电子邮箱、城市、邮编等信息。
22、最短旅程的求解
任务：有n个城市（编号从1到n），它们之间经过双向的道路相连。那里只有n－1条道路，可是，它们的连接方式使得从任意城市都能够走到其它的任何城市。 一天，某个游客到了编号为k的城市。她计划从城市k开始，游遍所有的城市m1，m2，m3……，mi，…（不一定要按这个顺序旅游）。每个城市mi都是不同的，而且，也与k不同。她想要以最短的路程旅行完所有的城市（从城市k开始）。请你帮助计算一下，旅游完上述的城市最短需要多少路程。
23、宿舍管理查询软件
任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：
(1)采用交互工作方式；
(2)能够增加、删除、修改信息；
(3)建立数据文件,数据文件按关键字（姓名、学号、房号）进行排序；
(4) 查询: a.按姓名查询 ；b.按学号查询 ；c按房号查询
(5) 输出任一查询结果（能够连续操作）。
24、病人就医管理
编写一个程序实现就医管理。在病人就医过程中，主要发生三件事：
⑴预检，分科室，挂号。
⑵病人到达诊室，将病历本交给护士，排到等待队列中候诊。
⑶护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。
要求程序采用菜单方式，其选项及功能说明如下：
⑴挂号------预检，分科室，生成就诊号。
⑵排队------输入病人的就诊号，加入到病人排队队列中。
⑶就诊-------病人排队队列中最前面的病人就诊，并将其从队列中删除。
⑷查看排队------从队首到队尾列出所有的排队病人的病历号。
⑸下班---------退出运行。
25、地铁站建设问题 
问题描述： 
以南昌为例，假设要在南昌各辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要设计一个程序，合理安排地铁的建设路线，使乘客能够沿地铁到达各个辖区，并使总的建设费用最小。 
基本要求：  
⑴从包含各辖区的地图文件中读入辖区名称和各辖区间的直接距离。（键盘接收数据也能够） 
⑵根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线。 
⑶输出应该建设的地铁路线及所需要建设的总里程信息。
26、教学计划编制问题 
设计要求：针对自己所在专业本科课程，根据课程之间的依赖关系（如C语言应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。
27、活期储蓄帐目管理
 活期储蓄处理中，储户开户、销户、存入、支出活动频繁，系统设计要求： 
能比较迅速地找到储户的帐户，以实现存款、取款记账； 
能比较简单，迅速地实现插入和删除，以实现开户和销户的需要。
28、马踏棋盘 
 问题描述
      将马随机放在国际象棋的8* 8棋盘Bord[8Ⅱ8]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。 
任务要求
      编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入一个8* 8的方阵，输出之。