周数据结构课程设计任务书.docx
《周数据结构课程设计任务书.docx》由会员分享，可在线阅读，更多相关《周数据结构课程设计任务书.docx（32页珍藏版）》请在冰点文库上搜索。
周数据结构课程设计任务书
数据结构课程设计任务书
1课程设计的目的
《数据结构课程设计》是信息与计算科学专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。
其目的是：
<1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。
<2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。
2课程设计的基本要求
<1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；
<2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；
<3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；
<4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
<5）设计的题目要求达到一定工作量，并具有一定的深度和难度。
<6）编写课程设计说明书。
3课程设计内容及安排
<1）问题分析和任务定义：
根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？
<而不是怎么做？
）限制条件是什么？
<2）逻辑设计：
对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。
逻辑设计的结果应写出每个抽象数据类型的定义<包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；
<3）详细设计：
定义相应的存储结构并写出各函数的伪代码算法。
在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。
详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；
<4）程序编码：
把详细设计的结果进一步求精为程序设计语言程序。
同时加入一些注解和断言，使程序中逻辑概念清楚；
<5）程序调试与测试：
采用自底向上，分模块进行，即先调试低层函数。
能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。
调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；
<6）结果分析：
程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。
算法的时间、空间复杂性分析；
<7）撰写课程设计报告；
4课程设计报告的内容
设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。
设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整，内容及要求详见“课程设计报告规范”，其中“课程设计报告内容”中一般应包括以下内容：
4.1需求分析
以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？
并明确规定：
（1>输入的形式和输入值的范围；
（2>输出的形式；
（3>程序所能达到的功能；
（4>测试数据：
包括正确的输入及其输出结果和含有错误的输入及其输出结果。
4.2概要设计
说明本程序中用到的所有类的定义、主程序的流程以及各程序模块之间的层次<调用）关系。
4.3详细设计
实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法<伪代码算法达到的详细程度建议为：
按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）>；可采用流程图、活动图进行描述，画出函数和过程的调用关系图。
4.4调试分析
内容包括：
调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；
4.5测试结果
列出你的测试结果，包括输入和输出。
这里的测试数据应该完整和严格，最好多于需求分析中所列。
4.6用户手册
说明如何使用你编写的程序，详细列出每一步的操作步骤。
5课程设计考核方法及成绩评定
课程设计结束时，要求学生写出课程设计报告<可不附源程序），可运行的软件系统<包括源程序，在数字大学城提交电子版，同时提交纸质版）。
学委在2018.12.31前按照实验的格式收齐电子版及打印的报告、交实验室肖老师处。
课程设计成绩分4部分，
（1）设计报告35%；
（2）程序质量占30％；
（3）集中上机考勤20％；
（4）提问及团队合作15%
6进度安排
演示软件和答辩另行安排
7课程设计题目
以下题目供参考，最多三人一组，各班学委相互协调好不要重复。
学生可以根据自己的实际，可以自己另行选择课程设计题目，选好题后必须经指导老师同意。
7.1集合的并、交和差运算
【间题描述】
编制一个能演示执行集合的并、交和差运算的程序。
【基本要求】
（1>集合的元素限定为小写字母字符[’a’，…’z’]
（2>演示程序以用户和计算机的对话方式执行。
【测试数据】
【实现提示】
以有序链表表示集合。
【选作内容】
（1>集合的元素判定和子集判定运算。
（2>求集合的补集。
（3>集合的混合运算表达式求值。
（4>集合的元素类型推广到其他类墩，甚至任意类型。
7.2任意长的整数加法运算
【问题描述】
设计一个程序实现两个任意长的整数的求和运算。
【基本要求】
设计一个实现任意长的整数进行加法运算的演示程序。
要求输入和输出每四位一组，组间用逗号隔开。
如：
1，0000，0000，0000，0000。
【实现说明】
可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中每个元素可以是字符、1位整数或分组的整数<4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈，进行输出。
【测试数据】
7.3任意长的整数乘法运算
【问题描述】
设计一个程序实现两个任意长的整数的乘法运算。
【基本要求】
设计一个实现任意长的整数进行乘法运算的演示程序。
要求输入和输出每四位一组，组间用逗号隔开。
如：
1，0000，0000，0000，0000。
【实现说明】
可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中每个元素可以是字符、1位整数或分组的整数<4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。
7.4任意长的整数除法运算
【问题描述】
设计一个程序实现两个任意长的整数的除法运算。
【基本要求】
设计一个实现任意长的整数进行除法运算的演示程序。
要求输入和输出每四位一组，组间用逗号隔开。
如：
1，0000，0000，0000，0000。
【实现说明】
可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中每个元素可以是字符、1位整数或分组的整数<4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。
7.5停车场管理
【问题描述】
设停车场是一个可停放，辆汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端>，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入。
当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。
【基本要求1
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输人数据序列进行模拟管理。
每一组输入数据包括三个数据项:
汽车‘“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。
对每一组输入数据进行操作后的输出信息为:
若是车辆到达，则输出汽车在停车场内或便道上的停车位置。
若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费>。
栈以顺序结构实现，队列以链表结构实现。
【测试数据】
【实现提示】
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序
存储结构实现。
输入数据按到达或离去的时刻有序。
栈中每个元素表示一辆汽车，包含两个数据项:
汽车的牌照号码和进入停车场的时刻。
7.6代码分析器
【问题描述】
读入一个JAVA源文件，统计文件中的代码、注释和空行的行数以及函数的个数和平均行数，并利用统计信息分析评价该程序的风格.
【基本要求】
（1>把e程序文件按字符顺序读入源程序。
<2）边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。
（3>程序的风格评价分为代码、注释和空行三个方面。
每个方面分为A，B，C:
和D四个等级。
等级的划分标准如下：
【测试数据】
先对较小的程序进行分析。
当你的程序能正确运行时，对你的程序本身进行分析。
【实现提示】
为了实现的方便，可作以下约定:
<1）头两个字符是‘//’的行称为注释行（该行不含语句>。
除了空行和注释行外，其余均为代码行（包括类型定义、变量定义和函数头>。
<2）每个函数代码行数（除去空行和注释行>称为该函数的长度。
<3>每行最多只有一个"{"、”}",“switch”，“class”<便于识别函数的结束行）。
7.7哈夫曼编码译码器
【问题描述】
设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件<压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件（.txt>。
【基本要求】
1.输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；
2.将文本文件利用哈夫曼树进行编码，生成压缩文件<后缀名cod）
3.输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；
【实现说明】
1.在构造哈夫曼树时，可以利用不同的线性表存放二叉树：
用顺序表、单链表、循环单链表、双向链表、循环双链表；
2.在构造哈夫曼树时，可以利用优先队列存放二叉树：
顺序队列、链队列<可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；
3.二叉树本身也可以用静态数组模拟；
7.8一元稀硫多项式计算器
【问题描述】
设计一个一元稀疏多项式简单计算器。
【基本要求】
一元稀疏多项式简单计算器的基本功能是:
（1>输入并建立多项式。
（2>输出多项式，输出形式为整数序列:
n,c1,e1,c2,e2,...，cn,en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列。
（3>多项式a和b相加，建立多项式a+b
（4>多项式a和b相减，建立多项式a-b
【测试数据】
【实现提示】
用链表存储多项式。
7.9约瑟夫环
【问题描述】
编号为1，2…n的n个人按顺时针方向围坐一圈，每人持有一个密码<正整数）。
一开始任选一个正整数作为报数的上限值m，从某一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。
【基本要求】
由键盘输入总人数，再依次输入每个人的姓名和密码建立人员表，再输入开始报数人的位置及初始报数上限，按照出列顺序输出各人的姓名。
【实现说明】
可以利用顺序表、单循环链表、双循环链表<其中链表可以带或不带附加表头结点，还可用静态结构实现链表）作为存储结构模拟此过程。
【测试数据】
M的初值为20，n=7，7个人的密码依次为3，1，7，2，4，8，4。
首先m值为6<正确的出列顺序应为6，1，4，7，2，3，5）。
【实现提示】
程序运行后.首先要求用户指定初始报数上限值，然后读取各人的密码。
可设n<=30。
7.10哈希表的设计与实现（需要查阅教材chapter11hashtable的内容>
【问题描述】
设计哈希表实现电话号码查询系统。
【基本要求】
1、设每个记录有下列数据项：
电话号码、用户名、地址；
2、从键盘输入各记录，以电话号码为关键字建立哈希表；
3、查找并显示给定电话号码的记录；
4、查找并显示给定用户名的记录。
【实现说明】
可以用不同的哈希函数、不同的解决冲突的策略。
7.11表达式求值问题
【问题描述】
设计一个程序，求解算术表达式的值。
【基本要求】
以字符序列的形式从键盘输入语法正确的、不含变量的整数<或实数）表达式，实现对算术四则混合运算表达式的求值。
【实现说明】
可以用不同生长方向的顺序栈、链栈
【测试数据】
7.12学生成绩管理系统
【问题描述】
设计一个计算机管理系统对学生成绩进行管理
【基本要求】
一个学生包括：
学号、姓名、数据结构、操作系统、数值计算和总成绩。
要求能够：
录入班级的学生成绩<按学号），保存到文件<或者从文件中调出），修改记录，删除记录，按学号输出、按单科成绩从高到低输出、按总成绩从高到低输出。
对成绩，可能通过建立索引表来提高数据的可访问性。
【实现说明】
可以用不同的排序方式：
<插入、希尔排序、冒泡排序、选择、快速排序等）
7.13班级通讯录
【问题描述】
设计一个计算机管理系统对班组通讯录进行管理
【基本要求】
一个学生的数据包括：
学号、姓名、电话号码、手机、QQ号。
要求能够：
录入、修改、删除、查找和输出所有记录。
为提高数据的可访问性，电话号码、手机、QQ号建立索引表，索引表可以在维护数据时动态维护，也可能最后一次建立。
【实现说明】
建立索引表时采用不同的排序方式：
直接插入、希尔排序、冒泡排序、直接选择、堆排序；查找数据时可采用不同的查找方式：
顺序查找、二分查找、黄金分割查找。
7.14数制转换问题
【问题描述】
实现不同数制数据间的转换，包括整数和小数。
【基本要求】
输入一种数的数据及数制，输出这个数的其他数制表示，要求包括二、八、十和十六进制。
要求程序要有一个可供用户选择的简单操作界面。
操作前要有简单的提示。
【实现说明】
可以用不同生长方向的顺序栈及链栈
7.15图书管理系统
【问题描述】
设计一个计算机管理系统完成图书管理基本业务。
【基本要求】
1.每种书的登记内容包括书号、书名、著作者、现存量和库存量；
2.对书号建立索引表<线性表）以提高查找效率，对新增的书，采用不同的排序算法建立索引表，再把2个索引表合并；
3.系统主要功能如下：
采编入库：
新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；
查找：
根据书号快速度查找书；
借阅：
如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；
归还：
注销对借阅者的登记，改变该书的现存量。
【实现说明】
可以采用不同的排序算法建立索引表，采用不同的查找算法根据书号快速度查找书目
7.16运动会分数统计
【问题描述】
参加运动会有n个学校，学校编号为1……n。
比赛分成m个男子工程，和w个女子工程。
工程编号为男子1……m，女子m+1……m+w。
每个的工程取前3名积分<或者前5名），积分分别为：
5、3、2<或者7、5、3、2、1）；【基本要求】
1.可以输入各个工程的前3名<或者前5名）的成绩；
2.能统计各学校总分，
3.可以按学校编号、学校总分、男女团体总分排序输出；
4.可以按学校编号查询学校某个工程的情况；可以按工程编号查询取得前3<或者前5）的学校。
【实现说明】
可以用不同的排序算法进行排序输出
7.17航空客运订票系统
【间题描述】
航空客运订票的业务活动包括:
查询航线、客票预订和办理退票等。
试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。
【基本要求】
（1>每条航线所涉及的信息有:
终点站名、航班号、飞机号、飞行周日（星期几>、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位等级1,2或3>以及等候替补的客户名单（包括姓名、所需票量>。
（2>作为示意系统，全部数据可以只放在内存中。
（3>系统能实现的操作和功能如下:
①查询航线。
根据旅客提出的终点站名输出下列信息:
航班号、飞机号、星期几飞行.最近一天航班的日期和余票额。
②承办订票业务:
根据客户提出的要求（航班号、订票数额>查询该航班票额情况.若尚有余票，则为客户办理订票手续，输出座位号，若已满员或余票额少于订票额.则需重新询间客户要求。
若需要，可登记排队候补。
③承办退票业务:
根据客户提供的情况（日期、航班>，为客户办理退票手续.然后查询该航班是否有人排队候补，首先询间排在第一的客户，若所退票额能满足他的要求，则为他办理订票手续，否则依次询间其他排队候补的客户。
【测试数据】
由读者指定。
【实现提示】
两个客户名单可分别由线性表和队列实现。
为查找方便，已订票客户的线性表应按客户姓名有序，并且，为插入和删除方便，应以链表作存储结构。
由于预约人数无法预计。
队列也应以链表作存储结构。
整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。
每条航线是这张表上的一个记录，包含上述8个fields、其中乘员名单域为指向乘员名单链表的头引用，等候替补的客户名单域为分别指向队头和队尾的引用。
【选作内容】
当客户订票要求不能满足时。
系统可向客户提供到达同一目的地的其他航线情况。
读
者还可充分发挥自己的想象力，增加你的系统的功能和其他服务工程。
7.18校园导游咨询
【间题描述】
设计一个校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】
（1>设计你的学校的校园平面图，所含景点不少于10个。
以图中顶点表示校内各景点，存放景点名称、代号、简介等信息。
以边表示路径，存放路径长度等相关信息。
（2>为来访客人提供图中任意景点相关信息的查询。
（3>为来访客人提供图中任意景点的问路查询.即查询任意两个景点之间的一条最短的简单路径。
【测试数据】
由读者根据实际情况指定。
【实现提示】
一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网。
顶点和边均含有相关信息。
【选作内容】
（1>求校园图的关节点。
（2>提供图中任意景点间路查询，即求任意两个景点之间的所有路径。
（3>提供校园图中多个景点的最佳访间路线查询。
即求途经这多个景点的最佳（短>
路径。
（4>校园导游图的景点和道路的修改扩充功能。
7.19论文管理系统
【间题描述】
系里的老师们每年都在国内外刊物上发表论文。
系办教务员、和各类工程的申报经常要对全系老师科研论文进行管理。
请设计一个程序对这些信息进行管理。
【基本要求】
实现以下功能：
（1）能添加论文信息；
（2）能按作者、年份或期刊等条件进行查询或统计，并显示查询结果<或输出到文本文件）；
（3）能对论文信息进行修改；
（4）能对论文记录进行删除；
根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。
操作前要有简单的提示。
【测试数据】
由读者根据实际情况指定。
【实现提示】
论文的信息包括有
（1）篇名
（2）作者
（3）刊物名称
（4）期卷号
（5）页码
（6）刊物档次<一般刊物、核心刊物、国外刊物）
（7）是否EI收录
（8）是否SCI收录
【选作内容】
考虑多用户登录的情况，对程序进行权限管理<例如管理员可以进行信息的修改、添加或删除，一般用户只能做查询）。
7.20校园收发室管理系统
【间题描述】
学校收发室每天都收到寄给全校师生的信件、包裹和汇款单<统称为邮件），目前的管理手段是人工进行，费时而且容易出错。
请设计一个程序对这些信息进行管理。
【基本要求】
实现以下功能：
（1）能添加新邮件信息；
（2）能按姓名、日期间隔或单位进行查询，并显示查询结果<或输出到文本文件）；
（3）能对邮件信息进行修改；
（4）能对邮件记录进行删除；
根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。
操作前要有简单的提示。
【测试数据】
根据实际情况指定。
【实现提示】
论文的信息包括有
（1）收件人姓名
（2）发件人
（3）邮件类型<普通/特快/汇款/包裹/…）
（4）收件日期
（5）是否已经签收
（6）备注
【选作内容】
考虑多用户登录的情况，对程序进行权限管理<例如管理员可以进行信息的修改、添加或删除，一般用户只能做查询）。
多条件进行联合查询，例如根据院系和日期进行查询。
7.21实验室预约管理系统
【间题描述】
某校多个实验室对全体学生开放。
实验室共提供三种实验工程，分别在上午、下午和晚上进行。
同一时间段只进行一种实验工程，每次接待的人数也有限制<例如最多30人）。
现在要求设计一个预约管理系统对实验室的使用进行管理。
【基本要求】
实现以下功能：
（1）根据学生的申请查找最早的可用的时间和实验室；并返回给申请者。
（2）能取消预约的申请，再次提供给预约使用；
（3）能对指定时间段实验室预约情况进行查询；
根据以上功能说明，设计具体的存储结构，要求程序要有一个可供用户选择的简单操作界面。
操作前要有简单的提示。
【测试数据】
根据实际情况指定。
【实现提示】
可运用队列方式管理申请者。
【选作内容】
考虑多用户登录的情况，对程序进行权限管理<例如管理员可以进行开放实验室的添加、删除的修改，一般用户只能做查询，）。
多条件进行联合查询，例如根据院系和日期进行查询。
7.22排序算法演示系统
【间题描述】
设计一个测试程序比较几种排序算法的关键字比较次数和移动次数以取得直观感受。
【基本要求】
<1）对冒泡排序、直接插入排序、简单选择排序、归并排序、快速排序、希尔排序算法进行比较；
<2）待排序的元素的关键字为整数。
其中的数据要用伪随机产生程序产生<如10000个），至少用5组不同的输入数据做比较，再使用各种算法对其进行排序，记录其排序时间，再汇总比较；
<3）演示程序以人机对话的形式进行。
每次测试完毕显示各种比较指标值的列表，用条形图<星号表示）进行表示，以便比较各种排序的优劣。
<4）每次测试结果设计为一个类，包括有算法名称，数据个数，时间等信息。
并且要记录要存储到文件中，
【测试数据】
由随机数产生器生成。
【实现提示】
主要工作是设法在已知算法中的适当位置插入对关键字的比较次数和移动次数的计数操作。
程序还可以考虑几组数据的典型性，如：
正序、逆序和不同程度的乱序。
注意采用分块调试的方法。
【选作内容】
<1）对不同表长进行比较；
<2）验证各算法的稳定性。
7.23个人理财管理系统
【间题描述】
该系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。
进入系统后可以输入、和删除修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况。
【基本要求】
1）界面友好，类的职责要划分好；
2）总体设计应画流程图；
3）程序要加必要的注释；
4）提供程序测试方案。
【测试数据】
至少提供3个月、每月不少于10笔开支的模拟数据。
【实现提示】
升级会员 