还剩10页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》课程设计任务书学期14-15-1班级计科、网络、软件13级
一、设计目的《数据结构》是一门实践性较强的软件基础课程,为了学好这门课程,必须在掌握理论知识的同时加强上机实践本课程设计的目的就是要达到理论与实际应用相结合,使同学们能够根据数据对象的特性,学会数据组织的方法,能把现实世界中的实际问题在计算机内部表示出来,并培养基本的、良好的程序设计技能.
二、设计要求
1、通过这次设计,要求在数据结构的逻辑特性和物理表示、数据结构的选择应用、算法的设计及其实现等方面加深对课程基本内容的理解.同时,在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练.
2、学生必须仔细研读《数据结构》课程设计(实习)要求,以学生自学为主、指导教师指导为辅,认真、独立地完成课程设计的任务,有问题及时主动与指导教师沟通
3、本次课程设计按照教学要求需要在三周时间内独立完成,学生要发挥自主学习的能力,充分利用时间,安排好课设的时间计划,并在课设过程中不断检测自己的计划完成情况,及时地向指导教师汇报
4、编程语言任选.
三、设计选题选题说明本次课设共提供若干个不同难易程度的题目,其中前面5个为必做题,满分80分(系统功能完善、人机交互界面简单、直观、便捷,否则逐项减分);后面为选做题,共20分题目难易程度不等,题目*越多难度越大根据实际选做题目的难度和数量以及实现程序的完善侬以适当加减分1同学们在选题时,要结合个人实际情况,确保及格,力争多做
1、单位员工通讯录管理系统(线性表的应用)[问题描述]为某个单位建立一个员工通讯录管理系统,可以方便查询每一个员工的办公室电话、手机号、及电子邮箱其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除、以及整个通讯录表的输出出北京至天津天津至徐州及徐州至上海各段的出发时间,到达时间及票价等信息2以邻接表作交通图的存储结构,表示边的结构内除含有邻接点的信息外还包括交通工具,路途中耗费的时间和花费以及出发和到达时间等多种属性【选做内容】增加旅途中中转次数最少的最优决策.
19.英语单词学习助手***【问题描述】掌握线性表、串、查找表等数据结构的物理存储结构与基本算法,通过解决较复杂的实际问题,提高学生对数据结构知识综合运用的技能与实践能力.设计内容以大学英语相关英语文章为语料素材,设计有效的数据结构及其存储结构表示英语单词表,并建立相应的倒排索引,帮助英语学习者在遇到生词时能方便找到生词的相应例句,熟悉其应用语境号地道的用法设计有效的算法对语料进行清理与分句处理,实现基于索引的快速例句搜索程序【基本要求】1输入某一个或若干个英语单词,要求返回相应的英语例句2根据单词与语句建立倒排索引,并且索引要求物化到外存,以文件形式保存,每次启动程序时不必重新建立索引,只需将索引文件导入内存3采用图形界面,便于输入单词,例句展现直观,界面布局合理【设计提示】按三步进行1准备英语语料.寻找英语文章,可下载英语新闻,托福、文章,或大学英语课文等2处理语料.对语料进行清理、分句、索引、生成字典需要进行取词干的操作分句可以直接根据标点符号处理3根据索引进行查询.支持一个或多个查询,基于对词干的处理,当查、等时也能够行返回由于查询的结果是语句,如果直接按照词与文章的关系建立索引,这样需要从文章中找句子,太多的串匹配操作可能导致查询较慢,所以要设计好索引的粒度大学校区*【题目描述】当前,中原工学院共有四个校区北校区、南校区、西校区和东校区信商新区,每一个校区都有若干个建筑物,如公园、广场、科研院所、实验中心、礼堂等,每个建筑物之间都有一定的距离,因此,在平时的教学和生活中,教师和学生都会经常面临这样的问题在同一个校区或不同校区之间,从一个地点到另一个地点往来的需要现在,他们需要找到从出发点S到目的地T的一条最短路径,以便节省时间,你能帮助他们吗?假设任两个建筑物之间至多存在一条直接相连的道路,并且都有具体的长度【输入】输入的第一行是一个正整数C表示下面测试案例数目在每一种测试例中,第一行的正整数N(0〈NW100)表示道路的数目,其后的N行第i行表示第i(1WiWN)条道路的起点和终点及其之间的距离(0WW100)第1行表示教师或学生的出发地S与目的地T你必须帮找出他们从出发地S到目的地T之间的最短路径每个校区分别使用、、和每一个建筑物名称用长度不超出100个小写字符()串表示【输出】输出应包括C行每行对应一个测试例,输出从起点到目的地的最短距离如果两地点间无路径则输出-
1.系统没有多余的内存空间可利用【输入样例】2100【输出样例】2
四、学生自选课题学生原则上可以结合个人爱好自选课题要求自选课题必须覆盖数据结构的主要内容,有一定的深度与难度,有一定的算法复杂性,能明确体现数据抽象与组织、算法设计与性能分析以及编码实现等过程学生自选课题需提前报课程设计指导教师批准方可生效.
五、指导教师苗凤君、高艳霞、吴志刚、田继鹏
六、时间安排第17—19每天上午8:30—12:00下午1300—1630
七、完成课程设计报告课程设计报告书封面用学校的统一封面课程设计报告的内容设计题目、需求分析、算法设计(包含算法思想、算法设计分析、流程图等)、调试分析、测试结果、课设总结(收获及体会)、附录(源代码)
八、成绩考核根据完成任务的情况(必须进行系统验收+答辩)、课程设计报告书的质量和课程设计过程中的工作态度等按照50%、30%、20%加权综合打分上机程序检查未通过者、无设计报告者以及严重抄袭他人设计者,成绩为不及其它情况根据界面设计、实现方法、功能效果、设计报告来评定主要从以下几个方面考察
九、上交报告及相关源代码上交课程设计报告和相关光盘其中设计报告要以打印文稿的形式上交光盘内容包括程序源码和课程设计报告的电子文档整个班级的设计均刻在一张光盘上.(上交时每人交一份,文件夹的取名规则为“班级一学号一姓名”,如计科131一学号一张三该文件夹下至少包括“源代码〃、“课程设计报告由以班为单位收集刻盘按规定时间统一上交)数据结构课程组2014-12-10[实现提示]可以采用单链表的存储结构,如可定义如下的存储结构:{/*员工通讯信息的结构类型定义*/[5];/*员工编号*/;/*员工姓名*/[15];/*办公室电话号码火/[15]:/*手机号码*/[25]/*邮箱*/};/*通讯录单链表的结点类型*/{;/*结点的数据域*/*;/火结点的指针域*/}*;
2、停车场管理(栈和队列的应用)[问题描述]设停车场是一个可以停放n辆汽车的狭长通道,且只有一个大门可供汽车进出汽车在停车场内按车辆到达时间的先后顺序,依次有北向南排列(大门在最南端,最先到达的第一车停放在车场的最北端),若车场内已停满n辆车,那么后来的车只能在门外的便道上等候,一旦有车开走则排在便道上的第一辆车即可开入;当停车场内某辆车要离开时在它之后进入的车辆必须先退出车场为它让路,待该辆车开出大门外,其他车辆再按原次序进入车场,每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用试为停车场编制按上述要求进行管理的模拟程序[实现提示]以栈模拟停车场,以队列模拟车场外的便道每一组输入数据包括三个数据项汽车“到达”或“离去〃信息、汽车牌照号码以及到达或离去的时刻对每一组输入数据进行操作后的输出信息为:若是车辆到达,则输出汽车在停车场内或便道上的停车位置;若是车辆离去,则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停车不收费)栈以顺序存储结构实现,队列以链表结构实现
3、哈夫曼编码/译码系统(树应用)[问题描述]利用哈夫曼编码进行通信,可以压缩通信的数据量提高传输效率,缩短信息的传输时间还有一定的保密性现在要求编写一程序模拟传输过程,实现在发送前将要发送的字符信息进行编码,然后进行发送,接收后将传来的数据进行译码,即将信息还原成发送前的字符信息[实现提示]在本例中设置发送者和接受者两个功能,发送者的功能包括
①输入待传送的字符信息;
②统计字符信息中出现的字符种类数和各字符出现的次数频率;
②根据字符的种类数和各自出现的次数建立哈夫曼树;
③利用以上哈夫曼树求出各字符的哈夫曼编码;
④将字符信息转换成对应的编码信息进行传送接受者的功能包括
①接收发送者传送来的编码信息;
②利用上述哈夫曼树对编码信息进行翻译,即将编码信息还原成发送前的字符信息从以上分析可发现,在本例中的主要算法有三个1哈夫曼树的建立;2哈夫曼编码的生成;3对编码信息的翻译
4、校园导游咨询图的应用[问题描述]设计一个校园导游程序为来访的客人提供各种信息查询服务.1设计学校的校园平面图,所含景点不少于10个,以图中顶点表示校内各景点,存放景点名称、代号、简介等信息;以边表示路径,存放路径长度等相关信息;2提供基本信息的修改功能;3为来访客人提供图中任意景点相关信息的查询;4为来访客人提供景点的问路查询,即已知一个景点,查询到某景点之间的一条最短路径及长度.
5、药店的药品销售统计系统排序应用[问题描述]设计一系统,实现医药公司定期对销售各药品的记录进行统计,可按药品的编号、单价、销售量或销售额做出排名[实现提示]在本设计中,首先从数据文件中读出各药品的信息记录,存储在顺序表中各药品的信息包括药品编号、药名、药品单价、销出数量、销售额.药品编号共4位,采用字母和数字混合编号,如:A125前一位为大写字母,后三位为数字,按药品编号进行排序时可采用基数排序法对各药品的单价、销售量或销售额进行排序时,可采用多种排序方法,如直接插入排序、冒泡排序、快速排序,直接选择排序等方法.在本设计中,对单价的排序采用冒泡排序法,对销售量的排序采用快速排序法,对销售额的排序采用堆排序法药品信息的元素类型定义{
[4];/*药品编号*/
[10];/*药品名称*/;/*药品单价/;/*销售数量*/;/*本药品销售额*/};存储药品信息的顺序表的定义{r[];
6、散列表的设计与实现C任务设计散列表实现电话号码查找系统要求1设每个记录有下列数据项用户名、电话号码、地址;a2从键盘输入各记录,以用户名汉语拼音形式为关键字建立散列表;3采用线性探测再散列法解决冲突;A4查找并显示给定电话号码的记录;5通讯录信息文件保存;6要求人机界面友好,使用图形化界面;选作内容⑴系统功能的完善;2a设计不同的散列函数,比较冲突率;Q3在散列函数确定的前提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化
7、一元稀疏多项式的计算*任务能够按照指数降序排列建立并输出多项式;能够完成两个多项式的相加、相减,并将结果输出;要求:以链式存储结构实现多项式
8、迷宫求解(*)任务以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.要求首先实现一个栈类型,然后编写一个求解迷宫的非递归程序求得的通路以三元组0的形式输出,其中指示迷宫中的一个坐标,d表示走到下一坐标的方向
9、排序综合(**)利用随机函数产生N个随机整数(20000以上),对这些数进行多种方法进行排序.要求
(1)至少采用三种方法(希尔排序、快速排序、堆排序)实现上述问题求解;
(2)统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比),找出其中两种较快的方法;
(3)统计每种算法所用的比较次数和交换次数,最后列表显示;
(4)如果采用4种或4种以上的方法者可适当加分
10、教学计划编制问题(**)[问题描述]大学的每个专业都要制定教学计划假设任何专业都有固定的学习年限,每学年含两学期,每学期的时间长度和学分上限值均相等每个专业开设的课程都是确定的,而且课程在开设时间的安排必须满足先修关系.每门课程有哪些先修课程是确定的,可以有任意多门,也可以没有每门课恰好占一个学期试在这样的前提下设计一个教学计划编制程序[实现提示]
1、输入参数应包括:学期总数,一学期的学分上限,每门课的课程号(可以是固定占3位的字母数字串)、学分和直接先修课的课程号.
2、应允许用户指定下列两种编排策略之一一是使学生在各学期中的学习负担尽量均匀;二是使课程尽可能地集中在前儿个学期中
3、若根据给定的条件问题无解,则报告适当的信息;否则将教学计划输出到用户指定的文件中计划的表格格式可以自己设计
4、可设学期总数不超过12课程总数不超过100o如果输入的先修课程号不在该专业开设的课程序列中,则作为错误处理
11、二叉排序树的基本操作(**)任务编写算法实现对依次输入的关键字序列建立二叉排序树.,并能实现二叉排序树的查找、插入和删除运算.
12、运动会分数统计(**)任务:参加运动会有n个学校,学校编号为1……no比赛分成m个男子项目和w个女子项目.项目编号为男子1……m女子1……不同的项目取前五名或前三名积分;取前五名的积分分别为
7、
5、
3、
2、1前三名的积分分别为:
5、
3、2;哪些项目取前五名或前三名由学生自己设定(m=20=20)功能要求
(1)可以输入各个项a的前三名或前五名的成绩;
(2)能统计各学校总分,
(3)可以按学校编号、男女团体总分排序输出;
(4)可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校规定输入数据形式和范围20以内的整数(如果做得更好可以输入学校的名称,运动项目的名称)输出形式有中文提示,各学校分数为整形界面要求有合理的提示每个功能可以设立菜单根据提示可以完成相关的功能要求存储结构学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构;相关数据结构(参考)项目名次及分值用二位数组口
[5];单项获奖情况登记表(项目编号,获奖名次、获奖学校,得分(自动得分))学校获奖名次表(学校编号,团体总分,名次)测试数据要求使用
1、全部合法数据;
2、整体非法数据;
3、局部非法数据进行程序测试,以保证程序的稳定.测试数据及测试结果请在上交的资料中写明;
13、宿舍管理查询软件(**)任务为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求1采用交互工作方式2可以增加、删除、修改信息3建立数据文件,数据文件按关键字姓名、学号、房号进行排序选择、快速排序、堆排序等任选一种4查询a按姓名查询.按学号查询按房号查询5打印任一查询结果可以连续操作
14、最小生成树问题**【问题描述】若要在n个城市之间建设通信网络,只需要假设1条线路即可如何以最低的经济代价建设这个通信网,是一个网的最小生成树问题【系统要求】.利用克鲁斯卡尔算法求网的最小生成树.利用普里姆算法求网的最小生成树.要求输出各条边及它们的权值【测试数据】由学生任意指定,但报告上要求写出多批数据测试结果【实现提示】通信线路一旦建成,必然是双向的因此,构造最小生成树的网一定是无向网设图的顶点数不超过30个并为简单起见,网中边的权值设成小于100的整数,可利用C语言提供的随机函数产生.图的存储结构的选取应和所作操作相适应为了便于选择权值最小的边,此题的存储结构既不选用邻接矩阵的数组表示法,也不选用邻接表而是以存储边带权的数组表示图.【选作内容】利用堆排序实现选择权值最小的边
15、平衡二叉排序树的实现**【系统要求】1用二叉链表作存储结构,以回车\n为输入结束标志,输入数列L生成一棵平衡的二叉排序树T并以直观的方式显示在终端上;2对二叉排序树T作中序遍历,输出结果;⑶输入元素x查找二叉排序树T若存在含x的结点,则删除该结点,并作中序遍历执行操作2;否则输出信息“无x”,并将x插入该二叉排序树中注意插入、删除应保证二叉排序树的平衡性.
16、商店存货管理系统(**)功能:建立一商店存货管理系统,要求每次出货时取进货时间最早且最接近保质期中止时间的货物分步实施
1.初步完成总体设计,搭好框架,确定人机对话的界面,确定函数个数;2完成最低要求:建立一个文件,包括5个种类的货物情况,能对商品信息进行扩充(追加),修改和删除以及简单的排序;
3.进一步要求:扩充商品数量,以及完成系统查询功能有兴趣的同学可以自己扩充系统功能
17、售票处的服务系统(***)【问题描述】航空客运订票的业务活动包括查询航线、客票预订和办理退票等试设计一个航空客运订票系统,以使上述业务可以借助计算机来完成【系统要求】设民航售票处的计算机系统可以为客户提供下列各项服务.查询航线:根据旅客提出的终点站名输出下列信息航班号、飞机号、星期儿飞行,最近一天航班的日期和余票额;.承办订票业务:根据客户提出的要求(日期、航班号、订票数额)查询该航班票额情况,若尚有余额,则为客户办理订票手续,输出座位号;若已满员或余票额少于订票额,则需要重新询问客户要求若需要,可预约登记排队等候.承办退票业务根据客户提供的情况(日期、航班、退票数额),为客户办理退票手续,然后查询该航班是否有人预约登记,首先询问排在第一的客户,若所退票额能满足他的要求,则为他办理订票手续,否则依次询问其他排队预约的客户【测试数据】由学生任意指定,但报告上要求写出多批数据测试结果【实现提示】每条航线应包含的信息有终点站名、航班号、飞机号、飞行日期(星期几)、乘员定额、余票额、已订票的客户名单(包括姓名、订票额、座位号)和预约登记的客户名单(包括日期、姓名、所需票额)这最后两项显然是一个线性表和一个队列.为查找方便、己订票客户的线性表应按客户姓名有序,并且,为插入和删除方便,应以链表作存储结构由于预约人数无法预料,队列也应以链表作存储结构整个系统需汇总各条航线的情况登录在一张线性表上,由于航线基本不变,可采用顺序存储结构,并按航班有序或按终点站名有序.每条航线是这张表上的一个记录,包含上述八个域,其中乘员名单域为指向乘员名单链表的头指针,预约登记客户名单域为分别指向队头和队尾的指针【选做内容】当客户订票要求不能满足时,系统可向客户提供到达同一目的地的其它航线情况大家还可以充分发挥自己的想象力,增加你的系统的功能和其它服务项目.
18、中国道路交通网络信息查询系统(****)【问题描述】出于不同的目的的旅客对交通工具有不同的要求例如,因公出差的旅客希望在旅途中的时间尽可能短,出门旅游的游客则期望旅费尽可能省,而老年旅客则要求中转次数最少编制一个全国城市间的交通咨询程序,为旅客提供两种或三种最优决策的交通咨询.【基本要求】
(1)提供对城市信息进行编辑(如添加或删除)的功能
(2)城市之间有两种交通工具火车和飞机.提供对列车时刻表和飞机航班进行编辑(增设或删除)的功能
(3)提供两种最优决策:最快到达或最省钱到达.全程只考虑一种交通工具;
(4)旅途中耗费的总时间应该包括中转站的等候时间;
(5)咨询以用户和计算机的对话方式进行.由用户输入起始站、终点站、最优决策原则和交通工具输出信息最快需要多长时间才能到达或者最少需要多少旅费才能到达,并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地.【测试数据】参考《数据结构》清华版
7.6节图
7.33的全国交通图,自行设计列车时刻表和飞机航班【实现提示】
(1)对时刻表和飞机航班进行编辑,应提供文件输入和键盘输入两种形式飞机航班信息包括起始站的出发时间,终点站的到达时间和票价;列车时刻表则需根据交通图给出各个路段的详细信息,如:对从北京到上海的火车,给项目得分备注程序运行情况25分程序的结构合理与否15分算法说明的清晰程度20分总结的深刻程度10分独立完成情况20分加分因素10分。