数据结构课设题目.doc

数据结构课程设计题目（适用于软件0803整个班和软件0802后14为同学）注意：对每个课程设计题目，可以选择C、C+和Java这3中语言中的任意一种语言实现，同一班级若两位同学选择的题目相同，但实现语言不同，是允许的。若两位同学的题目和实现语言都相同，是绝对不可以的。1. 个人帐簿管理系统设计功能： 个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。（1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；（2）完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；（3） 进一步要求：完成对每月的开支排序，以及完成系统查询功能。2. 课程设计题目: 商店存货管理系统 功能: 建立一商店存货管理系统,对完成对至少五种商品的管理,包括:增加,删除和修改以及简单 的排序,要求每次出货时取进货时间最早且最接近保质期中止时间的货物。项目基本要求: (1)要求利用面向过程的方法以及 C 语言的编程思想来完成系统的设计; (2)要求在设计的过程中,设计独立的功能模块;创新要求: 在基本要求达到后,可进行创新设计,如增加商品数据,完成系统的多种查询和排序等3.一元多项式计算任务:能够按照指数降序排列建立并输出多项式;能够完成两个多项式的相加,相减,并将结果输入;在上交资料中请写明:存储结构,多项式相加的基本过程的算法(可以使用程序流程图) ,源程序,测试数据和结果,算法的时间复杂度,另外可以提出算法的改进方法。4.*信息管理系统任务:通过此系统可以实现如下功能:（1）录入:可以录入*情况(数据可以存储在一个数据文件中,数据结构,具体数据自定)（2）查询:可以查询某个*的情况(如,输入*号,查询*时间,*数量);（3）修改（4）删除要求：根据以上功能说明,设计具体的存储结构,要求程序要有一个可供用户选择的简单操作界面.操作前要有简单的提示,设计程序完成功能。5 表达式求值的完整程序（计算器）就是给定任意一个算术表达式如(4+5)*3-8/2要能够得出它的结果6 文章编辑*功能:输入一页文字,程序可以统计出文字,数字,空格的个数.静态存储一页文章,每行最多不超过80个字符,共N行;要求(1)分别统计出其中英文字母数和空格数及整篇文章总字数;(2)统计某一字符串在文章中出现的次数,并输出该次数;(3)删除某一子串,并将后面的字符前移.存储结构使用线性表,分别用几个子函数实现相应的功能;输入数据的形式和范围:可以输入大写,小写的英文字母,任何数字及标点符号.输出形式:(1)分行输出用户输入的各行字符;(2)分4行输出全部字母数,数字个数,空格个数,文章总字数(3)输出删除某一字符串后的文章;7. joseph环任务:编号是1,2,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数).一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数.报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止.设计一个程序来求出出列顺序.要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序输出各个人的编号.测试数据:m的初值为20,n=7 ,7个人的密码依次为3,1,7,2,4,7,4,首先m=6,则正确的输出是什么要求:输入数据:建立输入处理输入数据,输入m的初值,n ,输入每个人的密码,建立单循环链表.输出形式:建立一个输出函数,将正确的输出序列8. 猴子选大王*任务:一堆猴子都有编号,编号是1,2,3 .m ,这群猴子(m个)按照1-m的顺序围坐一圈,从第1开始数,每数到第N个,该猴子就要离开此圈,这样依次下来,直到圈中只剩下最后一只猴子,则该猴子为大王.要求:输入数据:输入m,n m,n 为整数,nm输出形式:中文提示按照m个猴子,数n 个数的方法,输出为大王的猴子是几号 ,建立一个函数来实现此功能9. 建立二叉树,层序遍历(用队列的方法实现)和 中序遍历( 用递归和非递归的方法一起都要)10. 建立二叉树,先序遍历( 用递归和非递归的方法一起都要)11. 建立二叉树,后序遍历( 用递归和非递归的方法一起都要)任务:要求能够输入树的各个结点,并能够输出遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数,遍历序列的函数12, 赫夫曼树的建立任务 :建立建立最优二叉树函数要求:可以建立函数输入二叉树,并输出其赫夫曼树在上交资料中请写明:存储结构, 基本算法(可以使用程序流程图) ,输入输出,源程序,测试数据和结果,算法的时间复杂度,另外可以提出算法的改进方法;13, 纸牌游戏*任务:编号为1-52张牌,正面向上,从第2张开始,以2为基数,是2的倍数的牌翻一次,直到最后一张牌;然后,从第3张开始,以3为基数,是3的倍数的牌翻一次,直到最后一张牌;然后从第4张开始,以4为基数,是4的倍数的牌翻一次, 直到最后一张牌;.再依次5的倍数的牌翻一次,6的,7的 直到 以52为基数的 翻过,输出:这时正面向上的牌有哪些14,图的建立及输出任务:建立图的存储结构(图的类型可以是有向图,无向图,有向网,无向网,学生可以任选两种类型),能够输入图的顶点和边的信息,并存储到相应存储结构中,而后输出图的邻接矩阵.要求:15, 各种排序任务:用程序实现插入法排序,起泡法改进算法排序;利用插入排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好.输入的数据形式为任何一个正整数,大小不限.输出的形式:数字大小逐个递增的数列/m16. 用无序的顺序表实现一个城市数据库. 每条数据库记录包括城市名(任意长 的字符串)和城市的坐标(用整数 x 和 y 表示) .你的数据库应该允许插入记录, 按照名字或者坐标删除或检索记录, 还应该支持在指定点给定距离内所有记录的 打印.17. 用无序的链表实现一个城市数据库. 每条数据库记录包括城市名(任意长的 字符串)和城市的坐标(用整数 x 和 y 表示) .你的数据库应该允许插入记录, 按照名字或者坐标删除或检索记录, 还应该支持在指定点给定距离内所有记录的 打印.18. 无向图应用问题任务：如果以五向网表示n个城市之间通信网络的建设计划，顶点表示城市，边上的权表示该线路的造价，设计一个方案，使这个通讯网的总造价最低。提示：这是一个求最小生成树的问题。n个城市名和各边的权值由用户输入，建立图的邻接矩阵，然后以Prim算法来求最小生成树，然后输出方案。19. 统计成绩任务：给出n个学生的考试成绩表，每条信息有姓名与分数组成，(1)分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；(2)按名次列出每个学生的姓名与分数。要求：学生的考试成绩表必须通过键盘输入数据而建立，同时要对输出进行格式控制。（3）统计一个班级中每一个学生多门课程的成绩及排名(按各门课程及总分排名)。20. 停车场管理设有一个可以停放n辆汽车的狭长停车场，它只有一个大门可以供车辆进出。车辆按到达停车时间的早晚依次从停车场最里面向大门口停放(最先到达的第一辆车放在停车场的最里面)。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后近来的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车未进停车场就要离去，允许其离去，不收停车费，并且仍然保持在便道上等待的车辆的次序。编制一程序模拟停车场管理。实现提示：汽车的模拟输入信息格式可以是：(到达/离去，汽车牌照号码，到达/离去的时刻)。例如：(A,1,5)表示一号牌照车爱5这个时刻到达，而(D,5,20)表示5号牌照车在20这个时刻离去，整个程序可以在输入信息为(E,0,0)时结束。基本要求：要求程序输出每辆车到达后的停车位置(停车场或便道上)，以及某辆车离开停车场时应交纳的费用和它在停车场内停留的时间。21. n阶魔阵问题任务：给定一奇数n，构造一个n阶魔阵。n阶魔阵是一个n阶方阵，其元素自由然数1，2，3，n*n组成。魔阵的每行元素之和，每列元素之和以及主,副对角线之和均相等。既对于给定的奇数n以及i=1，2，3，n。魔阵a满足以上条件。要求：要求输出结果的格式要具有n阶方阵的形式。22. 实现图书管理信息系统的设计23. 轮船渡口管理系统24. 救护车调度模拟系统25. 航空客运订票系统已知技术参数和设计要求通过此系统可以实现如下功能:录入: 可以录入航班情况(数据可以存储在一个数据文件中,数据结构,具体数据自定) ;查询: 可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓); 可以输入起飞抵达城市,查询飞机航班情况;订票:(订票情况可以存在一个数据文件中,结构自己设定) 可以订票,如果该航班已经无票,可以提供相关可选择航班;退票: 可退票,退票后修改相关数据文件; 客户资料有姓名,证件号,订票数量及航班情况,订单要有编号.修改航班信息: 当航班信息改变可以修改航班数据文件要求: 根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能26. 迷宫问题已知技术参数和设计要求任务:可以输入一个任意大小的迷宫数据,用非递归的方法求出一条走出迷宫的路径,并将路径输出;要求:在上交资料中请写明:存储结构,基本算法(可以使用程序流程图),源程序,测试数据和结果,算法的时间复杂度,另外可以提出算法的改进方法27. 运动会分数统计已知技术参数和设计要求任务:参加运动会有n个学校,学校编号为1n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1m,女子m+1m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7,5,3,2,1,前三名的积分分别为:5,3,2;哪些取前五名或前三名由学生自己设定.(m=20,n=20)功能要求:可以输入各个项目的前三名或前五名的成绩;能统计各学校总分,可以按学校编号或名称,学校总分,男女团体总分排序输出;可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校.数据存入文件并能随时查询规定:输入数据形式和范围:可以输入学校的名称,运动项目的名称输出形式:有中文提示,各学校分数为整形界面要求:有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要求.存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中.(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构;测试数据:要求使用1,全部合法数据;2,整体非法数据;3,局部非法数据.进行程序测试,以保证程序的稳定.测试数据及测试结果请在上交的资料中写明28. 地图着色问题已知技术参数和设计要求设计要求:已知中国地图,对各省进行着色,要求相邻省所使用的颜色不同,并保证使用的颜色总数最少.29. 校园导航问题已知技术参数和设计要求设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任