《数据结构课程设计题目列表(12页).doc》由会员分享,可在线阅读,更多相关《数据结构课程设计题目列表(12页).doc(12页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、-数据结构课程设计题目列表-第 12 页数据结构A课程设计题目1、题目一 集合的并、交和差运算【问题描述】编制一个能演示执行集合的并、交和差运算的程序。【基本要求】(1) 集合的元素限自行定义。(2) 演示程序以用户和计算机的对话方式执行。【测试数据】自行建立。【实现提示】无。【选做内容】(1) 集合的元素判定和子集判定运算。(2) 求集合的补集。(3) 集合的混合运算表达式求解。(4) 集合的元素类型推广到其他类型,甚至任一类型。2、 题目二 算术表达式计算【问题描述】表达式计算是实现程序设计语言的基本问题之一,也是栈的应用的一个典型例子。设计一个程序,演示用算符优先法对算术表达式求值的过程
2、。【基本要求】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用运算符优先关系,实现对算术四则混合运算表达式的求值。【测试数据】(1)能够判断表达式中的括号是否匹配,测试的表达式中括号不匹配,可以重新输入。(2)能够处理多位整数以及浮点数。(3)具体测试数据自定义。【实现提示】设置运算符栈和运算数栈辅助分析算符优先关系;在读入表达式的字符序列的同时,完成运算符和运算数(整数)的识别处理,以及相应的运算;在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作等内容。【选做内容】扩充运算符集,如增加乘方、单目减、赋值等运算。3、题目三 贪吃蛇游戏开发【问题描述】贪吃蛇游戏是一个深
3、受人们喜欢的游戏,编程实现该游戏。【基本要求】一条蛇在密闭的围墙内,在围墙内随机出现一个食物,通过键盘上的四个光标键控制蛇向上下左右四个方向移动,蛇头撞到食物,则表示食物被吃掉,这时蛇的身体长一节,同时计1分;接着又出现食物,等待被蛇吃掉,如果蛇在移动过程中,撞到墙壁或身体交叉(蛇头撞到自己的身体)游戏结束。【测试数据】 自定义。【实现提示】(1)围墙区域可以用二维数组实现;(2)食物随机产生;(3)蛇的身体使用链表;(4)蛇的游动采用插入头结点,删除尾结点的方法实现。【选做内容】可以根据情况,自行添加完善。4、题目四 航空订票模拟 【问题描述】航空客运订票的业务活动包括:查询航线、客票预定和
4、办理退票等。设计一个航空订票模拟程序,以使上述业务可以借助计算机来完成。(难度系数:0.73)【基本要求】每条航线所涉及的信息有:终点站名、航班号、飞机号、飞行周日(星期几)、乘员定额、余票量、订票的客户名单(包括姓名、订票量、舱位等级1,2或3)以及等候替补的客户名单(包括姓名、所需数量)。系统能实现的操作和功能如下:(1) 查询航线:根据旅客提供的终点站名输出下列信息:航班号、飞机号、星期几飞行,最近一天航班的日期和余票额。(2) 承办订票业务:根据客户提出的要求(航班号、订票数额)查询该航班票额情况,若尚有余票,则为客户办理订票手续,输出座位号;若为满员或余票额少于订票额,则须重新询问客
5、户要求。若需要,可登记排队候补。(3) 承办退票业务:根据客户提供的要求(日期、航班),为客户办理退票手续,然后查询该航班是否排队候补,首先询问排在第一的客户,若所退票额能满足他的要求,则为他办理订票手续,否则依次询问其他排队候补的客户。【测试数据】自行建立。【实现提示】两个客户名单可分别由线性表和队列实现。为查找方便,已订票客户的线性表应按客户姓名有序,并且,为插入和删除方便,应以链表作存储结构。由于预约人数无法预计,队列也应以链表作存储结构。整个系统需汇总各条航线的情况登陆在一张线性表上,由于航线基本不变,可采用顺序存储结构,并按航班有序或按终点站名有序。每条航线是这张表上的一个记录,包含
6、上述8个域、其中乘员名单域为指向乘员名单链表的头指针,等候替补的客户名单域为分别指向队头和队尾的指针。【选做内容】当客户订票要求不能满足时,系统可向客户提供到达同一目的的其他航线情况。读者还可充分发挥自己的想象力,增加系统的功能和其他服务项目。5、题目五 哈希查找 【问题描述】若要在n个城市间建设通信网路,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题。(难度系数:0.78)【基本要求】(1) 利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。(2) 以文本形式输出生成树中各条边以及他们的权值。【测试数据】自行建立。【实现提示】通信线路一旦建立,必然是双
7、向的。因此,构造最小生产树的网一定是无向网。设图的顶点数不超过30个,并为简单起见,网中边的权值设成小于100的整数,可利用随机数函数产生。【选做内容】利用堆排序选择实现权值最小的边。6、题目六 哈夫曼编/译码器设计 【问题描述】利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼的编/译码系统。(难度系数:0.82)【基本要求】一个完整的系统应该具有以下功能:(1)
8、I:初始化(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hfmTree中;(2) E:编码(Encoding)。利用已建立好的哈夫曼树(如不在内存,则从文件hfmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中;(3) D:译码(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码。结果存入文件TectFile中。【测试数据】自行建立。【实现提示】编码结果以文本方式存储在文件CodeFile中;用户界面可以设计为“菜单”方式。【选做内容】 文本压缩解压。7、题
9、目七 校园导游系统模拟【问题描述】设计一个校园导游程序,为来访的客人提供各种信息查询服务。【基本要求】(1) 设计学校的校园平面图,所含景点不少于6个。以图中顶点表示校内各景点,存放景点名称、代号、间介等信息;以边表示路径,存放路径长度等相关信息。(2) 为来访客人提供图中任意景点相关信息的查询。(3) 提供途中任意景点问路查询,即求任意两个景点间的一条最短的简单路径。【测试数据】自行建立。【实现提示】无【选做内容】(1) 提供途中任意景点问路查询,即求任意两个景点间的所有路径。(2) 提供校园图中多个景点的最佳访问路线查询,即求途经这多个景点的最佳 (短)路径。8、题目八 教学计划编制问题【
10、问题描述】大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。【基本要求】(1)输入参数包括:学期总数,一学期的学分上限,每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。(2)允许用户指定下列两种编排策略之一:一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前几个学期中。(3)若根据给定的条件问题无解,
11、则报告适当的信息;否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。【测试数据】学期总数:6;学分上限:10;该专业共开设12门课,课程号从C01到C12,学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系见图1。【实现提示】可设学期总数不超过12,课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中,则作为错误处理。应建立内部课程号与课程号之间的对应关系。图1 课程先修关系9、题目九 成绩分析问题【问题描述】录入、保存一个班级学生多门课程的成绩,并对成绩进行分析。【基本要求】(1)通过键盘输入各学生的多门课程的成绩,建立相应的文件input.dat
12、。(2)对文件input.dat中的数据进行处理,要求具有如下功能:1) 按各门课程成绩排序,并生成相应的文件输出。2) 计算每人的平均成绩,按平均成绩排序,并生成文件。3) 求出各门课程的平均成绩、最高分、最低分、不及格人数、6069分人数、7079分人数、8089分人数、90分以上人数。4) 根据姓名或学号查询某人的各门课成绩,重名情况也能处理。 【测试数据】测试数据自定义,参考格式如表2所示。表2 成绩表学号姓名数学英语计算机001王放787790002张强896788003李浩566678004黄鹂兵898685005李浩678876006陈利风455467007尚晓78767010、
13、题目十 迷宫问题【问题描述】以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。【基本要求】(1)编程求出迷宫的一个解。(2)编写递归形式的算法,求得迷宫中所有可能的通路(选作)。【测试数据】 自定义。【实现提示】计算机解迷宫通常用的是“穷举求解”方法,即从入口出发,顺着某一个方向进行探索,若能走通,则继续往前进;否则沿着原路退回,换一个方向继续探索,直至出口位置,求得一条通路。假如所有可能的通路都探索到而未能到达出口,则所设定的迷宫没有通路。可以二维数组存储迷宫数据,通常设定入口点的下标为(1,1)
14、,出口点的下标为(m,n)。为处理方便起见,可在迷宫的四周加一圈障碍。对于迷宫中任一位置,均可约定有东、南、西、北四个方向可通。11、题目十一 小型书店的图书信息管理模拟 【问题描述】小型书店的图书信息管理的功能包括图书信息的增加、删除、更新和查询等。设计一个小型书店的图书信息管理模拟程序,以使上述业务可以借助计算机来完成。【基本要求】每一类图书所涉及的信息有:图书的ISBN号、图书名称、作者、出版社、价格、库存数量。系统能实现的操作和功能如下:(1)查询图书信息:根据输入的图书信息(ISBN号或名称)输出下列信息:图书的ISBN号、图书名称、作者、出版社、价格、库存数量。(2)图书信息增加或
15、更新:根据每次采购图书的信息要求实现对相应图书信息的增加或更新。(3)图书信息删除:对于部分图书的信息需要进行删除操作。 【测试数据】自行建立。【实现提示】图书信息建议以文件方式存放,便于数据操作。数据查询时建议使用顺序或折半查找。Southwest university of science and technology数据结构课程设计课题名称专业名称学生姓名学号+电话指导教师评分项(30分)具体评分项得分【1】设计过程学习态度(3分)设计能力(4分)设计效果(4分)【2】报告格式规范(3分)内容充实(4分)测试数据合理(4分)【3】答辩叙述清楚与否(3分)课题演示效果(4分)能否正确回答提
16、问(4分) 总分评阅教师蔡茂蓉曾立胜李学俊何 刚评分细则目 录一、课题描述编制一个演示单链表插入、删除、查找等操作的程序。二、需求分析本设计程序用C编写,完成单链表的生成,任意位置的插入、删除,以及确定某一元素在单链表中的位置。 输入的形式和输入值的范围:插入元素时需要输入插入的位置和元素的值;删除元素时输入删除元素的位置;查找操作时需要输入元素的值。在所有输入中,元素的值都是整数。 输出的形式:在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值,查找操作后显示要查找元素的位置。 程序所能达到的功能:完成单链表的生成(通过插入操作)、插入、删除、查找操作
17、。三、概要设计1)数据逻辑结构、存储结构分析:(补充完成.)2)本程序包含6个函数:(1)显示操作菜单函数menu()(2)初始化单链表函数InitLinkList(.) 补充:参数描述、功能描述(3)显示单链表内容函数dispLinkList(.) 补充:参数描述、功能描述(4)插入元素函数InsLinkList(.) 补充:参数描述、功能描述(5)删除元素函数DelLinkList(.) 补充:参数描述、功能描述(6)查找元素函数LocLinkList(.) 补充:参数描述、功能描述各函数间关系如下:Menu()InitLinkList()dispLinkList ()InsLinkList ()DelLinkList ()LocLinkList ()四、详细设计 重点算法的实现,关键代码处要有注释。五、测试数据及结果(1)建立单链表:输入(0,11),(0,12),(0,13),(0,14)(0,15)。得到单链表(15,14,13,12,11)。 屏幕截图:(2)删除:输入1。得到单链表(15,14,13,12,11,2)。屏幕截图:六、调试分析及总结(1)调试过程中遇到的问题以及解决的方法描述。(2)收获体会。
限制150内