数据结构课程设计一、教学目的和要求课程设计是加强学生实践能力的一个强有力手段。

综合课设 1主要针对数据结构和 C/C++语言开展 的实践性课程。

要求学生掌握数据结构的应用、算法的编写、类 C 语言的算法转换成 C （ C++）程序并 上机调试的基本方法。

课程设计要求学生在完成程序设计的同时能够写出比较规范的课程设计报告。

培 养学生综合运用所学理论知识解决复杂实际问题的实践能力、研究性学习能力和团队合作能力。

、课程设计要求1、 选好题目： 每题一人， 每班每个题目只允许一人选做 ，学习委员将选题情况在课设第一天统计上交。

2、 课设报告 独立思考，独立完成： 课设报告出现雷同超过 60% ，不论什么原因，一律不及格。

班和班之间，相同题目的同学，可以组成小组，相互讨论，共同完成课程设计中各任务的设计和调试 要求。

小组成员间， 算法思路可以相同， 程序可以类似， 但不能完全一样。

课设报告不能雷同超过 60% 。

3、 做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置 方法，准备好有关的文件。

4、 设计要点：⑴需求分析： 在该部分中叙述总共几个模块，每个模块的功能要求。

⑵系统设计 总体设计：定义某个数据结构的抽象数据类型及其他算法的功能说明。

详细设计：在此定义存储结构，每个部分的算法设计说明（建议描述算法采用流程图） 。

⑶编码实现 各个算法实现的源程序，对每个题目要有相应的源程序（每个功能模块采用不同的函数实现） 。

源程序要按照程序的规则来编写， 要结构清晰， 重点函数的重点变量， 重点功能部分要加上清晰的程序注释。

程序能够运行，要有基本的容错功能，尽量避免出现操作失误时出现死循环。

⑷调试分析 给出实现功能的一组或多组测试数据， 程序调试后， 将按照此测试数据进行测试的结果列出来。

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

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

5、 实现的结果必须进行检查和演示； 程序源代码和程序的说明文件必须上交， 作为考核内容的一部分； （上交时文件夹的取名规则为： “课设题目（ *** 设计完成） ”，如“资源管理系统的设计与实现（张三设计完成） ”。

该文件夹下包括三个目录： “源代码 ”、 “可执行文件 ”、 “张三 _课程设计报告 ”。

由学习委员 按规定时间统一上交） 。

6、报告提交形式：纸介质（要求B5纸张打印，加封皮）和电子文档。

三、考核方法和内容根据课程设计过程中学生的学生态度、 题目完成情况、 课程设计报告书的质量和回答问题的情况等 按照 10%、 40%、 30%、 20% 加权综合打分。

成绩评定实行优秀、良好、中等、及格和不及格五个等级。

评分标准：任务书（ 签名，把题目要求贴在相应位置，注意下划线 ） ---------- 目录（注意目录的格式，页码） -------- 1、设 计任务（ 题目要求 ） ---- 2 、需求分析（ 准备选用什么数据逻辑结构？数据元素包含哪些属性？需要哪 些函数？为什么要这样设计？最后列出抽象数据类型定义 ） ----------- 3 、系统设计（ 设计实现抽象数据类型， 包含选择什么物理存储方式？数据元素的结构体或类定义，以及各函数的设计思路，算法，程序流程 图等 ） 4 、编码实现（ 重要函数的实现代码 ） --------------------------- 5 、调试分析（ 选择多组测试数据、运行截图、结果分析 ） ---- 6、课设总结（ 心得体会 ） ----- 7 、谢辞 8 、参考文献；课设报告打印要求：B5纸张打印，报告总页数控制在 10—15页内，报告中不能全是代码， 报告中代码总量控制在150行内。

版式：无页眉，有页码，页码居中优秀： 答辩所有问题都能答出 良好： 答辩所有问题都能答出 中等： 答辩大部分问题能答出 及格： 答辩大部分问题能答出 不及格：答辩几乎答不出问题 课设报告的装订顺序如下：+ 报告良好 +报告一般 + 报告良好 +报告一般或者 报告几乎都是代码或者 雷同部分达到 60%字号：小四，单倍行距字体：宋体+Times new Romar 截图：截图要配图的编号和图的题目，如：“图1 Insert 函数流程图”四、课程设计的题目1、运动会分数统计2、集合的并、交和差运算的程序3、长整数的加法运算4、一元多项式计算器5、车厢调度问题6、文章编辑7、识别广义表的头或尾的演示8、哈夫曼树及其编码9、校园导游咨询10、地图着色问题11、内部排序算法比较12、哈希表的设计与实现——线性探测再散列13、哈希表的设计与实现——二次探测再散列14、哈希表的设计与实现——链地址法15、火车售票系统16、图书管理系统17、客户消费积分管理系统18、产品进销存管理系统19、学生成绩管理系统的设计与实现20、通讯录管理系统的设计与实现——线性表21、通讯录管理系统的设计与实现——哈希表22、简单目录管理系统的设计与实现23、最短旅程的求解24、迷宫求解25、家谱管理系统的设计与实现26、宿舍管理查询软件27、语言中平衡符号的问题28 、算术表达式求解29、表达式求值，可供小学生作业，并能给出分数30、数制转换问题31、病人就医管理32、九宫格问题33、银行业务模拟34、停车场管理35、关键路径问题36、地铁站建设问题37、服装销售系统38、歌星大奖赛39、机房机位预约模拟系统40、歌曲信息管理系统41、简单的试题库管理系统42、学生点名系统43、猜数游戏五、数据结构课程设计的具体内容要求：全部采用数据结构课程中的内容实现，采用C或C++实现，逻辑结构只能选线性结构、树型结构、图型结构、集合结构中的一种，不能用数据库。

1、运动会分数统计问题描述：参加运动会的n个学校编号为1〜n。

比赛分成 m个男子项目和 w个女子项目，项目编号分别为1〜m和m+1〜m + w。

由于各项目参加人数差别较大，有些项目取前五名，得分顺序为11, 7, 4, 2, 1;还有些项目只取前三名，得分顺序为5， 3， 2。

哪些项目取前五名或前三名由学生自己设定。

写一个统计程序产生各种成绩单和得分报表。

基本要求：(1 )各项目结束时，输入前三名或前五名的项目编号、运动员姓名、校名和名次(成绩) ;(2)产生各学校的成绩单，内容包括每个学校所取得的每项成绩的项目号、名次(成绩) 、姓名和得分，并统计各学校总分;(3)可以按学校编号、男女团体总分排序输出;(4)可以按学校编号查询学校某个项目的情况;(5)可以按项目编号查询取得前三或前五名的学校;(6)演示程序以用户和计算机的对话方式执行。

2、集合的并、交和差运算的程序问题描述：编制一个能演示执行集合的并、交和差运算的程序。

基本要求：⑴集合的元素限定为大小写字母符['a'….'z '',A集合的大小’]<53。

⑵集合输入的形式为一个以 "回车符 "为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序应能自动滤去。

⑶输出的运算结果字符串中将不含重复字符或非法字符。

⑷演示程序以用户和计算机的对话方式执行。

3、长整数的加法运算问题描述：设计一个实现任意长的整数进行加法、减法运算的演示程序。

基本要求：⑴利用链表实现长整数的存储，每个结点含一个整型变量。

提醒：任何整型变量int的范围是-(2人15-1)~(2人15-1)。

⑵输入和输出形式按照中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。

女口： -2345，6789，3211 ;⑶演示程序以用户和计算机的对话方式执行。

4、一元多项式计算器问题描述：设有一元多项式 A m(x) 和 B n(x).A m(x) = A 0+A 1X1+A2X2+A3X3+- +A m x m1 2 3 nB n(x) = B 0+B1X +B2X +B3X + …+B n X试求 M(x)= A m(x)+B n(x)、M(X)= A m(x)-B n(x)和 M(X)= A m(x) B n(x)。

基本要求：⑴首先判定多项式是否稀疏;⑵分别采用顺序和链式结构实现;⑶结果 M(x) 中无重复阶项和无零系数项;⑷要求输出结果的升幂和降幂两种排列情况。

⑸演示程序以用户和计算机的对话方式执行。

5、车厢调度问题问题描述：假设停在铁路调度站(如教科书中图3.1(b)所示)入口处的车厢系列的编号依次为1，2, 3，…n。

设计一个程序，求出所有可能由此输出的长度为 n 的车厢系列。

基本要求：⑴设计一个程序，求出由一个编号依次为 1 , 2,、、、，n的车厢序列可能产生的所有出栈系列。

⑵利用双向栈存储结构实现调度站和输出序列这两个栈的空间共享。

⑶对于每个输出序列演示出所有操作序列的变化过程。

6、文章编辑问题描述：输入一页文字，可以统计出文字、数字、空格的个数。

基本要求：⑴静态存储一页文章，每行最多不超过80个字符，共N行。

⑵分别统计出其中英文字母和空格数及整篇文章总字数。

⑶统计某一字符串在文章中出现的次数，并输出该次数。

⑶删除某一子串，并将后面的字符前移。

⑷存储结构使用线性表，分别用几个子函数实现相应的功能。

7、广义表的应用要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度等。

本设计用一个主控菜单程序控制，共分为 6 个子系统。

（1）建立广义表（2）输出广义表（3）结点的查找（4）求广义表表头（5）求广义表表尾（ 6）求广义表的深度演示程序以用户和计算机的对话方式执行。

8、哈夫曼树及其编码问题描述：设计一个利用哈夫曼算法的编码系统，重复地显示并处理以下项目，直到选择退出为止。

基本要求：⑴初始化：键盘输入或文件输入字符集大小n、n个字符和n个权值，建立哈夫曼树；⑵编码：禾ij用建好的哈夫曼树生成哈夫曼编码；⑶输出树形的哈夫曼树及哈夫曼编码；⑷设字符集及频度如下表：字符空格 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 19、校园导游咨询问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。

基本要求：⑴设计华东交通大学南区的校园平面图，所含景点不少于10个。

以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。