《数据结构课程设计》题目与要求。
一、 实验学时:两周。
二、 要求:
1、 题目从以下题目中选择,完成程序设计及设计文档。
2、 程序的要求:实现的功能要求尽量完善。完善基本功能的基础上,再扩充其它功能。
3、 课程设计说明书的格式要求:a4纸打印,格式设置统。
一、规范、美观。
三、题目。1. 运动会分数统计(限1 人完成)
任务:参加运动会有n个学校,学校编号为1……n。比赛分成m个男子项目,和w个女子项目。
项目编号为男子1……m,女子m+1……m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为,前三名的积分分别为;哪些取前五名或前三名由学生自己设定。(m<=20,n<=20)
功能要求:1) 可以输入各个项目的前三名或前五名的成绩;
2) 能统计各学校总分,3) 可以按学校编号或名称、学校总分、男女团体总分排序输出;
4) 可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校。
5) 数据存入文件并能随时查询
6) 规定:输入数据形式和范围:可以输入学校的名称,运动项目的名称。
输出形式:有中文提示,各学校分数为整形。
界面要求:有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要求。
存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构;
测试数据:要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明;
2. 文章编辑(限1 人完成)
功能:输入一页文字,程序可以统计出文字、数字、空格的个数。
静态存储一页文章,每行最多不超过80个字符,共n行;要求(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章**现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移。
存储结构使用线性表,分别用几个子函数实现相应的功能;
输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出"全部字母数"、"数字个数"、"空格个数"、"文章总字数"(3)输出删除某一字符串后的文章;
3. 图的遍历和生成树求解实现(限1 人完成)
要求:( 可选择部分完成)
1) 自选存储结构,先任意创建一个图,求图中每个顶点的度,输出结果;
2) 图的dfs,bfs的递归和非递归算法的实现;
3) 最小生成树(两个算法)的实现;
4) 求连通分量的实现(可选做);
5) 要求用邻接矩阵、邻接表、十字链表多种结构存储实现。
4. 哈希表的设计与实现 (限1 人完成)
问题描述:设计哈希表实现**号码查询系统。
基本要求:
1、设每个记录有下列数据项:**号码、用户名、地址;
2、从键盘输入各记录,分别以**号码和用户名为关键字建立哈希表;
3、采用再哈希法解决冲突;
4、查找并显示给定**号码的记录;
5、查找并显示给定用户名的记录。
6、在哈希函数确定的前提下,尝试各种不同类型处理冲突的方法(至少两种),考察平均查找长度的变化。
5. 顺序结构、链表结构下的一元多项式的加法、减法、乘法的实现。(限1 人完成)
设有一元多项式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) 结果m(x)中无重复阶项和无零系数项;
3) 要求输出结果的升幂和降幂两种排列情况。
6. 利用栈求表达式的值,可供小学生作业,并能给出分数。(限1 人完成)
要求:建立试题库文件,随机产生n个题目;题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价。
7. 排序综合(限1 人完成)
利用随机函数产生n个随机整数(30000以上),对这些数进行多种方法进行排序。
要求:1) 至少采用五种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等)。并把排序后的结果保存在不同的文件中。
2) 统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),在实验报告中要求找出其中两种较快的方法,分析原因。
8. 稀疏矩阵应用(限1 人完成)
要求:实现三元组,十字链表下的稀疏矩阵的加法、转置、乘法的实现。
9. 敢死队问题(限1 人完成)
有m个敢死队员要炸掉敌人的一碉堡,谁都不想去,排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务,则要再派一个战士上去。现给每个战士编一个号,大家围坐成一圈,随便从某一个战士开始计数,当数到5时,对应的战士就去执行任务,且此战士不再参加下一轮计数。
如果此战士没完成任务,再从下一个战士开始数数,被数到第5时,此战士接着去执行任务。以此类推,直到任务完成为止。
排长是不愿意去的,假设排长为1号,请你设计一程序,求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。
要求:至少采用两种不同的数据结构的方法实现。
10. 迷宫问题。
问题描述:以一个m*n的长方阵表示迷宫,0和1表示迷宫的通路和障碍。设计一个程序,对任意设定的迷宫,求一条从入口到出口的通路,或得出没有通路的结论。
实现方法参考课本。
11. 教学计划编制问题。
问题描述:大学中每个专业都有固定的教学计划,任何专业的学习年限是固定的,每年两个学期,每个专业开设的课程是确定的,而课程之间的开设时间是必须满足先修关系的。每们课可以有多门先修课,也可以没有。
以本科四年为准,要求设计一个教学计划。
要求:输入学期总数,一学期的学分上限,每门课的课程号、学分和直接先修课的课程号。使学生在各学期中的学习负担尽量均匀;输出教学计划到用户指定的文件中,计划**格式自行设计,若无结果可报告适当的信息。
12. 交通咨询模拟。
问题描述:处于不同情况的旅客对交通工具有不同的要求:省钱、省时间等,编辑一个城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询。
要求:提供城市信息的编辑;城市之间只有火车和飞机两种交通工具。提供对列车时刻表和飞机航班的简单编辑;提供两种最优决策:最快和最省钱到达。全程只考虑一种交通工具。
四、考核标准:
此题目所列要求为基本要求,同学们可以在此基础上,增加相关功能。
根据提交的设计文档(包括程序主要完成的功能、设计思路和框图、主要**,程序中有何创新,有何收获和所存在的不足以及需要改进的地方。),程序功能的实现(要求演示)进行考核:
无任何文档,无程序,得 0 分;
文档混乱,没有思路,程序不能运行,不及格;
文档描述清晰,程序实现了基本功能,但运行时有错误,回答问题需提示,及格;
文档描述清晰,程序实现了基本功能且运行正确,回答问题基本正确,中等;
文档描述清晰准确,思路清晰,程序实现了要求的所有功能,回答问题正确,良好;
文档完备,文档描述清晰准确,思路清晰,深入分析了程序功能和实现方案,程序实现了全部功能,设计合理有创新,功能完善,或有其它的创新实现,回答问题完整准确,优秀。
数据结构课程设计题目
题目1实现两个链表的合并。要求 编一程序将a表和b表归并成一个新的递增有序的单链表c 值相同的元素均保留在c表中 并要求利用原表的空间存放c。测试数据 1 a表 30,41,15,12,56,80 b表 23,56,78,23,12,33,79,90,55 2 a表 30,41,15,12,56,8...
数据结构课程设计题目
题目1 图的遍历。功能 实现图的深度优先,广度优先遍历算法,并输出原图结构及遍历结果。分步实施 1 初步完成总体设计,搭好框架 2 完成最低要求 两种必须都要实现,写出画图的思路 3 进一步要求 画出图的结构,有兴趣的同学可以进一步改进图的效果。要求 1 界面友好,函数功能要划分好。2 总体设计应画...
数据结构课程设计题目
51 航班信息查询与检索。问题描述 根据旅客提出的终点站名输出下列信息 航班号 飞机号 星期几飞行 最近一天航班的日期和余票额。设计要求 1 对飞机航班信息进行排序和查找。可按航班的航班号 起点站 到达站 起飞时间以及到达时间等信息进行查询 2 采用基数排序法对一组具有结构特点的飞机航班号进行排序 ...