《15周数据结构课程设计任务书》由会员分享，可在线阅读，更多相关《15周数据结构课程设计任务书（21页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计任务书1 课程设计的目的数据结构课程设计是信息与计算科学专业集中实践性环节之一，是学习完数据结构课程后进行的一次全面的综合练习。其目的是： （1）要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机部表示出来，并培养良好的程序设计技能。 （2）在实践中认识为什么要学习数据结构，掌握数据结构、程序设计语言、程序设计技术之间的关系，是前面所学知识的综合和回顾。2 课程设计的基本要求（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和
2、技能；（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力；（4）训练用系统的观点和软件开发一般规进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（5）设计的题目要求达到一定工作量，并具有一定的深度和难度。（6）编写课程设计说明书。3 课程设计容与安排（1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？ （2）逻辑设计：对问题描述中涉与的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基
3、本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；（3）详细设计：定义相应的存储结构并写出各函数的伪代码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作进行进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；（4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；（5）程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确
4、定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序与其注释，形成格式和风格良好的源程序清单和结果；（6）结果分析：程序运行结果包括正确的输入与其输出结果和含有错误的输入与其输出结果。算法的时间、空间复杂性分析；（7）撰写课程设计报告；4 课程设计报告的容设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版与图、表要清楚、工整，容与要求详见“课程设计报告规”， 其中“课程设计报告容”中一般应包括以下容：4.1 需求分析以无歧义的述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的
5、围；(2) 输出的形式；(3) 程序所能达到的功能；(4) 测试数据：包括正确的输入与其输出结果和含有错误的输入与其输出结果。4.2 概要设计说明本程序中用到的所有类的定义、主程序的流程以与各程序模块之间的层次（调用）关系。4.3 详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪代码算法；对主程序和其他模块也都需要写出伪代码算法（伪代码算法达到的详细程度建议为：按照伪代码算法可以在计算机键盘直接输入高级程序设计语言程序）)；可采用流程图、活动图进行描述，画出函数和过程的调用关系图。4.4 调试分析容包括：调试过程中遇到的问题是如何解决的以与对设计与实现的回顾讨论和分析；4.5
6、测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。4.6 用户手册说明如何使用你编写的程序，详细列出每一步的操作步骤。5 课程设计考核方法与成绩评定课程设计结束时，要求学生写出课程设计报告（可不附源程序），可运行的软件系统（包括源程序，在数字大学城提交电子版，同时提交纸质版）。学委在2012.12.31前按照实验的格式收齐电子版与打印的报告、交实验室肖老师处。课程设计成绩分4部分，（1） 设计报告35%；（2） 程序质量占30；（3） 集中上机考勤20；（4） 提问与团队合作15%6 进度安排演示软件和答辩另行安排7 课程设计题目以下题目供参考，最
7、多三人一组，各班学委相互协调好不要重复。学生可以根据自己的实际，可以自己另行选择课程设计题目，选好题后必须经指导老师同意。7.1 集合的并、交和差运算间题描述 编制一个能演示执行集合的并、交和差运算的程序。基本要求 (1)集合的元素限定为小写字母字符a，z (2)演示程序以用户和计算机的对话方式执行。测试数据实现提示 以有序链表表示集合。选作容 (1)集合的元素判定和子集判定运算。 (2)求集合的补集。 (3)集合的混合运算表达式求值。 (4)集合的元素类型推广到其他类墩，甚至任意类型。7.2 任意长的整数加法运算问题描述设计一个程序实现两个任意长的整数的求和运算。基本要求设计一个实现任意长的
8、整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。实现说明可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈，进行输出。测试数据7.3 任意长的整数乘法运算问题描述设计一个程序实现两个任意长的整数的乘法运算。基本要求设计一个实现任意长的整数进行乘法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。实现说明可以用顺序表、单链表、循环单链表、
9、双向链表、循环双向链表或者各种栈去表示长整数，其中 每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。7.4 任意长的整数除法运算问题描述设计一个程序实现两个任意长的整数的除法运算。基本要求设计一个实现任意长的整数进行除法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。实现说明可以用顺序表、单链表、循环单链表、双向链表、循环双向链表或者各种栈去表示长整数，其中 每个元素可以是字符、1位整数或分组的整数（4位一组），用单向链表表示时，可以采用低位在前，输出时再用栈进行输出。7.
10、5 停车场管理问题描述设停车场是一个可停放，辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第一辆车停放在车场的最北端)，若车场已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入;当停车场某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用，试为停车场编制按上述要求进行管理的模拟程序。基本要求1以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输人数
11、据序列进行模拟管理。每一组输入数据包括三个数据项:汽车“到达”或“离去”信息、汽车牌照以与到达或离去的时刻。对每一组输入数据进行操作后的输出信息为:若是车辆到达，则输出汽车在停车场或便道上的停车位置;若是车辆离去，则输出汽车在停车场停留的时间和应交纳的费用(在便道上停留的时间不收费)。栈以顺序结构实现，队列以链表结构实现。测试数据实现提示需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项:汽车的牌照和进入停车场的时刻。7.6 代码分析器问题描述 读入一个JAVA源文件，统计文件中的代码
12、、注释和空行的行数以与函数的个数和平均行数，并利用统计信息分析评价该程序的风格.基本要求(1)把e程序文件按字符顺序读入源程序;（2）边读入程序，边识别统计代码行、注释行和空行，同时还要识别函数的开始和结束，以便统计其个数和平均行数。(3)程序的风格评价分为代码、注释和空行三个方面。每个方面分为A，B，C:和D四个等级。等级的划分标准如下：测试数据 先对较小的程序进行分析。当你的程序能正确运行时，对你的程序本身进行分析。实现提示为了实现的方便，可作以下约定:（1）头两个字符是/的行称为注释行(该行不含语句)。除了空行和注释行外，其余均为代码行(包括类型定义、变量定义和函数头)。（2）每个函数代
13、码行数(除去空行和注释行)称为该函数的长度。（3)每行最多只有一个 、”,“switch”，“class”（便于识别函数的结束行）。7.7 哈夫曼编码译码器问题描述设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。基本要求1.输入一个待压缩的英文文本文件，统计文本文件中各字符的个数作为权值，生成哈夫曼树；2.将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod） 3.输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；实现说明1.在构造哈夫曼树时，可以利用
14、不同的线性表存放二叉树：用顺序表、单链表、循环单链表、双向链表、循环双链表；2.在构造哈夫曼树时，可以利用优先队列存放二叉树：顺序队列、链队列（可以是单链表、双链表等，还可以用静态结构去实现），可以分别在入队列或出队列时实现优先级；3.二叉树本身也可以用静态数组模拟；7.8 一元稀硫多项式计算器问题描述 设计一个一元稀疏多项式简单计算器。基本要求一元稀疏多项式简单计算器的基本功能是:(1)输入并建立多项式;(2)输出多项式，输出形式为整数序列:n,c1,e1,c2,e2,. . .，cn,en，其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列;(3)多项式a和b相加
15、，建立多项式a +b(4)多项式a和b相减，建立多项式a-b测试数据实现提示用链表存储多项式。7.9 约瑟夫环问题描述编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从某一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求由键盘输入总人数，再依次输入每个人的和密码建立人员表，再输入开始报数人的位置与初始报数上限，按照出列顺序输出各人的。实现说明可以利用顺序表、单循环链表、双循环链表（其中链表可以带或不带附加表头结点，还可用静态结构实现链表）作为存储结构模拟此过程。测试数据M的初值为20，n=7，7个人的
