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

数据结构课程设计

一、教学目标和要求
为了配合《数据结构》课程教学，使学生能更深刻地领会《数据结构》这门课程关键性，特开设此课程设计；编写部分在特定数据结构上算法，经过上机调试，愈加好掌握多种数据结构及其特点，同时提升处理计算机应用实际问题能力。
二、课程设计要求
1、选好题目：每题一人，每班每个题目最多许可三人选做，必需确保每题有两人选做，学习委员将选题情况先统计上交。

2、独立思索，独立完成：课程设计中各任务设计和调试要求独立完成，碰到问题能够讨论，但不能够拷贝。相同题目标同学，算法思绪能够相同，不过程序和课设汇报不能相同。
3、做好上机准备：每次上机前，要事先编制好准备调试程序，认真想好调试步骤和相关环境设置方法，准备好相关文件。
4、设计关键点：
　⑴需求分析：
　在该部分中叙述总共多个模块，每个模块功效要求。
　⑵系统设计
总体设计：定义某个数据结构抽象数据类型及其它算法功效说明。
具体设计：在此定义存放结构，每个部分算法设计说明（提议描述算法采取步骤图）。
⑶编码实现
各个算法实现源程序，对每个题目要有对应源程序（每个功效模块采取不一样函数实现）。源程序要根据程序规则来编写，要结构清楚，关键函数关键变量，关键功效部分要加上清楚程序注释。
程序能够运行，要有基础容错功效，尽可能避免出现操作失误时出现死循环。
⑷调试分析
给出实现功效一组或多组测试数据，程序调试后，将根据此测试数据进行测试结果列出来。时间复杂度分析，每个模块设计和调试时存在问题思索（问题是哪些？问题怎样处理？），算法改善设想。
⑸课设总结：课程设计过程收获、碰到问题、碰到问题处理问题过程思索、程序调试能力思索、对数据结构这门课程思索、在课程设计过程中对《数据结构》课程认识等内容。
5、实现结果必需进行检验和演示；程序源代码和程序说明文件必需上交，作为考评内容一部分；（上交时文件夹取名规则为：“课设题目（***设计完成）”，如“资源管理系统设计和实现（张三设计完成）”。该文件夹下包含三个目录：“源代码”、“可实施文件”、“张三_课程设计汇报”。由学习委员按要求时间统一上交）。
6、汇报提交
时间: 待定。
形式: 纸介质(要求B5纸张打印，加封皮)和电子文档。
三、考评方法和内容
依据课程设计过程中学生学生态度、题目完成情况、课程设计汇报书质量和回复问题情况等根据10%、40%、30%、20%加权综合打分。成绩评定实施优异、良好、中等、及格和不及格五个等级。
评分标准：
优异：答辩+汇报优异
良好：答辩+汇报通常 或 汇报优异+没答辩
中等：答辩+汇报稍差 或 汇报通常+没答辩
及格：汇报稍差+没答辩 或 答辩但被发觉不是自己编写实现
不及格：汇报几乎全部是代码 或 类同部分达成70%
课设汇报装订次序以下：
封面-----任务书-----目录-----设计任务-----需求分析-----系统设计-----编码实现-----调试分析-----课设总结-----谢辞-----参考文件-----附录（可选）等；
汇报总页数控制在10±2页内，汇报中不能全是代码，汇报中代码控制在150行内。
四、课程设计题目
1、运动会分数统计
2、集合并、交和差运算程序
3、长整数加法运算
4、一元多项式计算器
5、车厢调度问题
6、文章编辑
7、识别广义表头或尾演示
8、哈夫曼树及其编码
9、校园导游咨询　
10、地图着色问题
11、内部排序算法比较
12、哈希表设计和实现
13、火车售票系统
14、图书管理系统
15、用户消费积分管理系统
16、产品进销存管理系统
五、数据结构课程设计具体内容
要求：全部采取数据结构课程中线性结构、树型结构、图型结构、集合结构中一个，不能用数据库。
1、运动会分数统计
问题描述：
参与运动会n个学校编号为1～n。比赛分成m个男子项目和w个女子项目，项目编号分别为1～m和m+1～m＋w。因为各项目参与人数差异较大，有些项目取前五名，得分次序为7，5，3，2，1；还有些项目只取前三名，得分次序为5，3，2。写一个统计程序产生多种成绩单和得分报表。
基础要求：
⑴每个项目结束时，输入前三名或前五名项目编号、运动员姓名、校名和名次（成绩）；
⑵产生各学校成绩单，内容包含各学校所取得每项成绩项目号、名次（成绩）、姓名和得分，并统计各学校总分；
⑶产生团体总分报表，内容包含校号、男子团体总分、女子团体总分和团体总分。
2、集合并、交和差运算程序
问题描述：
编制一个能演示实施集合并、交和差运算程序。
基础要求：
⑴集合元素限定为小写字母符[′a′….′z ′]，集合大小n<27。
⑵集合输入形式为一个以"回车符"为结束标志字符串，串中字符次序不限，且许可出现反复字符或非法字符，程序应能自动滤去。
⑶输出运算结果字符串中将不含反复字符或非法字符。
⑷演示程序以用户和计算机对话方法实施。
3、长整数加法运算
问题描述：
设计一个实现任意长整数进行加法运算演示程序。
基础要求：
1利用链表实现长整数存放，每个结点含一个整型变量。
2任何整型变量范围是-(2^15-1)~(2^15-1)。
3输入和输出形式根据中国对于长整数表示习惯，每四位一组,组间用逗号隔开。 如：-2345，6789，3211；
4、一元多项式计算器
问题描述：
设有一元多项式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)中无反复阶项和无零系数项；
⑷要求输出结果升幂和降幂两种排列情况。
5、车厢调度问题
问题描述：
假设停在铁路调度站(如教科书中图3.1(b)所表示)入口处车厢系列编号依次为1，2，3，…n。设计一个程序,求出全部可能由此输出长度为n 车厢系列。
基础要求：
⑴设计一个程序，求出由一个编号依次为1，2，、、、，n车厢序列可能产生全部出栈系列。
⑵利用双向栈存放结构实现调度站和输出序列这两个栈空间共享。
⑶对于每个输出序列演示出全部操作序列改变过程 。
6、文章编辑
问题描述：
输入一页文字，能够统计出文字、数字、空格个数。
基础要求：
⑴静态存放一页文章，每行最多不超出80个字符，共N行。
⑵分别统计出其中英文字母和空格数及整篇文章总字数。
⑶统计某一字符串在文章中出现次数，并输出该次数。
⑶删除某一子串，并将后面字符前移。
⑷存放结构使用线性表，分别用多个子函数实现对应功效。
7、识别广义表头或尾演示
问题描述：
写一个程序，建立广义表存放结构，演示在此存放结构上定义广义表求头、求尾操作序列结果。
基础要求：
⑴组成广义表正当字符：小写或大写字母、空白字符、圆括号和逗号，且设广义表原子为单个字母。
⑵以用户和计算机对话方法实施，广义表建立方法为边输入边建立；分解操作进行方法为，输入整个命令串，然后分步显示每一个操作结果。
⑶输入过程中自动滤去正当字符以外其它字符，并能在输入步当初输入对应提醒信息。
8、哈夫曼树及其编码
问题描述：
设计一个利用哈夫曼算法编码系统，反复地显示并处理以下项目，直到选择退出为止。
基础要求：
⑴初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
⑵编码：利用建好哈夫曼树生成哈夫曼编码；
⑶输出其哈夫曼树及哈夫曼编码；
⑷设字符集及频度以下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
9、校园导游咨询　　
问题描述：
设计一个校园导游程序，为来访客人提供多种信息查询服务。
基础要求：
⑴设计华东交通大学校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，⑵存放景点名称、代号、介绍等信息；以边表示路径，存放路径长度等相关信息。
⑶为来访客人提供图中任意景点相关信息查询。
⑷为来访客人提供图中任意景点问路查询，即查询任意两个景点之间一条最短简单路径。
10、地图着色问题
问题描述：
已知江西地图，请设计地图着色软件，对11个地级市进行着色，要求相邻地级市所使用颜色不一样，并确保使用颜色最少。
基础要求：
⑴地图采取图型数据结构，每个地级市为一个节点，边表示对应两个地级市相邻。
⑵设计着色算法，确保邻接点不是同一个颜色。
⑶演示程序以用户和计算机对话方法进行。
11、内部排序算法比较
问题描述：
试经过随机数据比较各算法关键字比较次数和关键字移动次数，以取得直观感受。
基础要求：
⑴最少采取三种方法实现上述问题求解（提醒，可采取方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。
⑵待排序表表长大于100，其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据作比较；比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）。
⑶最终对结果作出简单分析，包含对各组数据得出结果波动大小解释。
12、哈希表设计和实现
问题描述：
设计哈希表实现电话号码查找系统。
基础要求：
⑴设每个统计有下列数据项：电话号码、用户名、地址；
⑵从键盘输入各统计，分别以电话号码和用户名为关键字建立哈希表；
⑶采取一定方法处理冲突；
⑷查找并显示给定电话号码统计；
⑸查找并显示给定用户名统计。
13、火车售票系统
问题描述：
经过此系统能够实现售票、退票、车票剩下情况查询等功效。每张车票包含车次、座位信息。
基础要求：
⑴在售票、退票、查询剩下票等步骤中，全部必需显示出车票信息，即车次、座位情况。
⑵为简单起见，在此假设全部出售车票均为同一车次车票。
⑶退票时，必需是车站售出车票才能退，不然视为无效票，不能退票。
14、图书管理系统
问题描述：
设计一个计算机管理系统完成图书管理基础业务。
基础要求：
⑴每种书登记内容包含书号、书名、著作者、现存量和库存量；
⑵对书号建立索引表（线性表）以提升查找效率；
⑶系统关键功效以下：
①采编入库：新购一个书，确定书号后，登记到图书帐目表中，假如表中已经有，则只将库存量增加；
②借阅：假如一个书现存量大于0，则借出一本，登记借阅者书证号和归还期限，改变现存量；
③归还：注销对借阅者登记，改变该书现存量。
15、用户消费积分管理系统
问题描述：
针对用户消费情况，进行用户管理，依据用户消费积分对用户实施不一样程度打折优惠。
基础要求：
⑴采取一定存放结构进行用户信息存放；
⑵对用户信息能够进行修改、删除、添加；
⑶能够依据消费情况进行用户积分计算；
⑷依据积分情况实施不一样程度打折优惠；
16、产品进销存管理系统
问题描述：
针对某一个行业库房产品进销存情况进行管理。
基础要求：
⑴采取一定存放结构对库房货物及其数量进行分类管理；
⑵能够进行产品类添加、产品添加、产品数量添加；
⑶能够查询库房每种产品总量、进货日期、销出数量、销售时间等。