软件算法综合设计任务书

1、软件算法综合设计任务书一、软件算法综合设计基本信息1、课程设计编号:2、课程设计名称:软件算法综合设计3、课程设计周数(学时:1周(40学时4、课程设计授课单位:计算机科学与技术系5、指导方式:集体辅导和个别辅导相结合6、适用专业:计算机科学与技术7、课程设计教材及主要参考资料:1 严蔚敏,吴伟民编著.数据结构(C语言版.清华大学出版社, 1997.42 严蔚敏,吴伟民编著.数据结构习题集 . 清华大学出版社,1997.4二、教学目的和基本要求1、了解并掌握数据结构和算法设计的方法,具备初步的独立分析和设计能力。2、初步掌握软件开发过程的问题分析分析、系统设计、程序编码和测试等基本方法和技能。

2、3、提高综合运用所学的理论只是和方法,独立分析和解决问题的能力。4、训练用系统的观点和软件开发一般规范进行软件的开发,培养软件工作着所具备的科学工作方法和作风。三、软件算法综合设计的内容和安排1、问题分和任务定义:根据设计题目的要求,充分地分析和理解问题,明确问题要求做什么,限制的条件是什么。2、逻辑设计:对问题中涉及到的操作对象定义相应的数据类型,并按照以数据结构为中心的原则划分模块,定义主程序和各抽象数据类型,逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明,各个主要模块的算法,并画出模块之间的调用关系图。3、物理设计:定义相应的存储结构并写出个函数的

3、伪码算法。在这个过程中,要综合考虑系统功能,使得系统结构清晰、合理、简单和易于调试,抽象数据类型的实现尽可能做到数据封装,基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精,写出数据结构存储结构的类型定义,写出函数形式的算法框架。4、程序编码:把详细设计的结果进一步求精为程序设计语言。同时加入一些注解和断言,使程序中逻辑概;念清晰。5、程序调试和测试:采用自底向上,分模块进行,即先调试低层函数。能够熟练掌握调试工具的各种功能,设计测试数据确定疑点,通过修改程序来证实它或绕过它。调试正确后,认真整理源程序和注释,形成格式和风格良好的源程序清单和结果。6、结果分

4、析:程序运行结果包括正确的输入及其输出结果、含有错误的输入和输出结果、算法时间复杂度和空间复杂度分析。7、撰写课程设计报告:总结和提升上述过程和步骤,写出结构严谨、表述清楚、符合设计规范的报告。四、软件算法综合设计的题目本课程设计题目共34个,每个同学可以根据自身实际情况进行选择。最后需要对所做系统书写实验报告一份,格式见附页。五、考核的方法和成绩的评定考核成绩分为两个部分:(1验收程序部分:占50%。按照以下几个指标进行验收:程序的正确性;程序的运行和存储效率;程序代码编写规范程度,代码的可读性高;界面是否友好;程序设计的创新性;(2实验报告(50%实验报告结构是否清晰,问题叙述是否具有逻辑

5、性;关键代码设计是否正确无误;程序设计的时间、空间复杂性分析是否正确。六、时间的安排共1周,5天。题目共10个,每个同学可以根据自身实际情况掌握进度,最后一天验收程序,也可以分部分验收。七、软件算法综合设计报告的格式(1问题的概述、分析和研究意义;(2数据结构的逻辑设计和物理存储设计;(3重要算法的设计、流程描述和代码描述;(4数据结构的时间、空间复杂性分析和重要算法的复杂度分析;(5程序的最终实现结果(包括重点界面的抓取,能说明问题的重要实验结果数据的打印或其可视化结果;(6参考文献;(7附录:关键数据结构的定义及关键算法的源代码。八、软件算法综合设计结果的提交(1课程设计报告(一份、A4纸

6、打印,同时包括一份电子文档。(2完整的程序系统(电子方式提交,能够对输入产生相应的输出,同时尽量完成可视化演示。(3源程序文档(电子方式提交,源程序代码要求适当缩进编排、结构清晰、可读性好,对源程序的类说明(如采用面向对象方法设计、函数说明、接口说明、关键变量说明等要进行注释。(4答辩报告(制作PPT报告,电子方式提交,要求重点突出,思路清晰,同时就此报告准备答辩。所有电子方式提交的文件全部存放在一个目录中,并对其进行压缩,压缩后的文件按规定格式进行命名,命名格式为:班级号+学号+姓名。九、软件算法综合设计题目说明1.运动会分数统计(限3人完成任务:参加运动会有n个学校,学校编号为1n。比赛分

7、成m个男子项目,和w个女子项目。项目编号为男子1m,女子m+1m+w。不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1,前三名的积分分别为:5、3、2;哪些取前五名或前三名由学生自己设定。(m=20,n=20功能要求:1可以输入各个项目的前三名或前五名的成绩;2能统计各学校总分;3可以按学校编号或名称、学校总分、男女团体总分排序输出;4可以按学校编号查询学校某个项目的情况;可以按项目编号查询取得前三或前五名的学校;5数据存入文件并能随时查询;6规定:输入数据形式和范围:可以输入学校的名称,运动项目的名称。输出形式:有合理的提示,各学校分数为整形。界面要求:有合理的提示,

8、每个功能可以设立菜单,根据提示,可以完成相关的功能要求。存储结构:学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决请在最后的上交资料中指明你用到的存储结构;测试数据:要求使用1、全部合法数据;2、整体非法数据;3、局部非法数据。进行程序测试,以保证程序的稳定。测试数据及测试结果请在上交的资料中写明。2.飞机订票系统(限3人完成通过此系统可以实现如下功能:录入:可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定;查询:可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达

9、城市,航班票价,票价折扣,确定航班是否满仓;可以输入起飞抵达城市,查询飞机航班情况;订票:(订票情况可以存在一个数据文件中,结构自己设定可以订票,如果该航班已经无票,可以提供相关可选择航班;退票:可退票,退票后修改相关数据文件;客户资料有姓名,证件号,订票数量及航班情况,订单要有编号;修改航班信息:当航班信息改变可以修改航班数据文件。要求:根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能。3.文章编辑(限3人完成功能:输入一页文字,程序可以统计出文字、数字、空格的个数;静态存储一页文章,每行最多不超过80个字符,共N行。要求:(1分别统计出其中英文字母数和空格数及整篇文章总

10、字数;(2统计某一字符串在文章中出现的次数,并输出该次数;(3删除某一子串,并将后面的字符前移。存储结构使用线性表,分别用几个子函数实现相应的功能。输入数据的形式和范围:可以输入大写、小写的英文字母、任何数字及标点符号。输出形式:(1分行输出用户输入的各行字符;(2分4行输出全部字母数、数字个数、空格个数、文章总字数(3输出删除某一字符串后的文章。4.宿舍管理查询软件(限3人完成为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求:A.采用交互工作方式;B.建立数据文件,数据文件按关键字(姓名、学号、房号进行排序(冒泡、选择、插入排序等任选一种。查询菜单:(用二分查找实现以下操作A.按姓名查

11、询;B.按学号查询;C.按房号查询。打印任一查询结果(可以连续操作5.校园导航问题(限3人完成设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径。6.教学计划编制问题(限3人完成设计要求:针对计算机系本科课程,根据课程之间的依赖关系(如离散数学应在数据结构之前开设制定课程安排计划,并满足各学期课程数目大致相同。7.散列法的实验研究(限3人完成散列法中,散列函数构造方法多种多样,同时对于同一散列函数解决冲突的方法也可以不同。两者是影响查询算法性能的关键因素。对于几种典型的散列函数构造方法,做实验观

12、察,不同的解决冲突方法对查询性能的影响。8.图书借阅管理系统(限3人完成主要分为两大功能:1图书管理(增加图书、查询图书、删除图书、图书借阅、还书;2会员管理(增加会员、查询会员、删除会员、借书信息。9.学生成绩管理(限3人完成实现功能:输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出。10.二叉排序树的实现(限3人完成用顺序和二叉链表作存储结构1以回车(n为输入结束标志,输入数列L,生成一棵二叉排序树T;2对二叉排序树T作中序遍历,输出结果;3输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2;否则输出信息“无x”。1

13、1.最小生成树问题(限3人完成设计要求:在n个城市之间建设网络,只需保证连通即可,求最经济的架设方法。存储结构采用多种。求解算法多种。12.通讯录的制作(限3人完成设计目的:用数据结构中的双向链表作数据结构,结合C语言基本知识。编写一个通讯录管理系统。以把所学数据结构知识应用到实际软件开发中去。设计内容:本系统应完成一下几方面的功能:1输入信息enter(;2显示信息display( ;3查找以姓名作为关键字search( ;4删除信息delete( ;5存盘save ( ;6装入load( 。设计要求:1每条信息至包含:姓名(NAME 街道(STREET城市(CITY邮编(EIP国家(STA

14、TE几项;2作为一个完整的系统,应具有友好的界面和较强的容错能力;3上机能正常运行,并写出课程设计报告。13.哈夫曼编码/译码器(限3 人完成【问题描述】设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。【基本要求】1将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目录中 ;2分别采用动态和静态存储结构;3初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;4编码:利用建好的哈夫曼树生成哈夫曼编码;5输出编码;6设字符集及频度如下表:字符空格 A B C D E F G H I J K L M频度 186 64 13 22 3

15、2 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z频度 57 63 15 1 48 51 80 23 8 18 1 16 1【进一步完成内容】1译码功能;2显示哈夫曼树;3界面设计的优化。14.图书管理系统(限3人完成【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1每种书的登记内容包括书号、书名、著作者、现存量和库存量;2对书号建立索引表(线性表以提高查找效率;3系统主要功能如下:采编入库:新购一种书,确定书号后,登记到图书帐目表中,如果表中已有,则只将库存量增加;借阅:如果一种书的现存量大于0,则借出一本,登记

16、借阅者的书证号和归还期限,改变现存量;归还:注销对借阅者的登记,改变该书的现存量。【进一步完成内容】1系统功能的进一步完善;2索引表采用树表;3设计内容;4程序流程图;5源程序;6软件测试报告(包括所用到的数据及结果。15.散列表的设计与实现(限3人完成【问题描述】设计散列表实现电话号码查找系统。【基本要求】1设每个记录有下列数据项:电话号码、用户名、地址;2从键盘输入各记录,分别以电话号码和用户名为关键字建立散列表;3采用一定的方法解决冲突;4查找并显示给定电话号码的记录;5查找并显示给定用户名的记录。【进一步完成内容】1系统功能的完善;2设计不同的散列函数,比较冲突率;3在散列函数确定的前

17、提下,尝试各种不同类型处理冲突的方法,考察平均查找长度的变化。16.顺序结构、动态链表结构下的一元多项式的加法、减法、乘法的实现。(限3人完成设有一元多项式A m(x和B n(x.A m(x=A0+A1x1+A2x2+A3x3+ +A m x mB n(x=B0+B1x1+B2x2+B3x3+ +B n x n请实现求M(x= A m(x+B n(x、M(x= A m(x-B n(x和M(x= A m(xB n(x。要求:1首先判定多项式是否稀疏;2分别采用顺序和动态存储结构实现;3结果M(x中无重复阶项和无零系数项;4要求输出结果的升幂和降幂两种排列情况。17.利用栈求表达式的值,可供小学生

18、作业,并能给出分数。(限3人完成要求:建立试题库文件,随机产生n个题目;题目涉及加减乘除,带括弧的混合运算;随时可以退出;保留历史分数,能回顾历史,给出与历史分数比较后的评价。18.二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。(限3人完成要求:遍历的内容应是千姿百态的。树与二叉树的转换的实现。以及树的前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。要求:遍历的内容应是千姿百态的。19.学生搭配问题(限3人完成一班有m个女生,有n个男生(m不等于n,现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开

19、始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴。请设计一系统模拟动态地显示出上述过程,要求如下:1输出每曲配对情况;2计算出任何一个男生(编号为X和任意女生(编号为Y,在第K曲配对跳舞的情况.至少求出K的两个值;3尽量设计出多种算法及程序,可视情况适当加分。提示:用队列来解决比较方便。20.猴子吃桃子问题(限3人完成有一群猴子摘了一堆桃子,他们每天都吃当前桃子的一半且再多吃一个,到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求:1采用数组数据结构实现上述求解;2采用链数据结构实现上述求解;3采用递归实现上述求解。21.数制转换

20、问题(限3人完成任意给定一个M进制的数x ,请实现如下要求1求出此数x的10进制值(用MD表示;2实现对x向任意的一个非M进制的数的转换;3至少用两种或两种以上的方法实现上述要求(用栈解决,用数组解决,其它方法解决。22.排序综合(限3人完成利用随机函数产生N个随机整数(20000以上,对这些数进行多种方法进行排序。要求:1至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序,并把排序后的结果保存在不同的文件中;2统计每一种排序方法的性能(以上机运行程序所花费的时间为准进行对比,找出其中两种较快的方法;3如果采用4种或4种以上

21、的方法者,可适当加分。23.学生成绩管理系统(限3人完成现有学生成绩信息文件1(1.txt,内容如下姓名学号语文数学英语张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47. . . . 学生成绩信息文件2(2.txt,内容如下:姓名学号语文数学英语陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77. . . . 试编写一管理系统,要求如下:1实现对两个文件数据进行合并,生成新文件3.txt;2抽取出三

22、科成绩中有补考的学生并保存在一个新文件4.txt;3合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现;4输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现;5要求使用结构体,链或数组等实现上述要求;6采用多种方法且算法正确者,可适当加分。 24.图的遍历的实现（ 人完成） 24.图的遍历的实现（限 3 人完成） 图的遍历的实现 要求： 1先任意创建一个图； 2图的 DFS,BFS 的递归和非递归算法的实现； 3要求用有向图和无向图分别实现； 4要求用邻接矩阵、邻接表多种结构存储实现。 25.线索二叉树的应用（ 人完成） 25.线索二叉树的应用（限

23、 3 人完成） 线索二叉树的应用 要求：实现线索树建立、插入、删除、恢复线索的实现。 26.稀疏矩阵应用（限 3 人完成） 26.稀疏矩阵应用（ 人完成） 稀疏矩阵应用 要求：实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现。 （1）稀疏矩阵的存储； （2）稀疏矩阵加法； （3）矩阵乘法； （4）矩阵转置。 27.树的应用（限 3 人完成） 27.树的应用（ 人完成） 树的应用 要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归 算法，层次序的非递归算法的实现，应包含建树的实现。 28.任意长的整数加法（限 3 人完成） 8.任意长的整数加法（ 人完成） 任意长的整数加法 问

24、题描述：设计一个程序实现两个任意长的整数的求和运算。 基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演 示程序。要求输入和输出每四位一组，组间用逗号隔开。 如：1，0000，0000，0000，0000。 29.二叉平衡排序树（限 3 人完成） 29.二叉平衡排序树（ 人完成） 二叉平衡排序树 问题描述：从一棵空树开始创建，在创建过程中，保证树的有序性，同时还要 针对树的平衡性做些调整。最终要把创建好的二叉排序树转换为二叉平衡排序 树。 基本要求：1.创建（插入、调整、改组） 2.输出 30.串的查找和替换 （限 3 人完成） 30.串的查找和替换 人完成） 问题描述：打开

25、一篇英文文章，在该文章中找出所有给定的单词，然后对所 有给定的单词替换为另外一个单词，再存盘。 31.约瑟夫环 （限 3 人完成） 31.约瑟夫环 人完成） 问题描述：编号为 1，2 n 的 n 个人按顺时针方向围坐一圈，每人持有一 个密码（正整数）。一开始任选一个正整数作为报数的上限值 m，从第一个人开 始按顺时针方向自 1 开始顺序报数，报到 m 时停止报数，报 m 的人出列，将他的 密码作为新的 m 值， 从他的顺时针方向上的下一个开始重新从 1 报数， 如此下去， 直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求： 1利用单循环链表作为存储结构模拟此过程； 2键盘输入总人数、初始报数上限值 m 及各人密码； 3按照出列顺序输出各人的编号。 32.构造可以使 n 个城市连接的最小生成树 （限 3 人完成） 32.构造可以使 个城市连接的最小生成树 人完成） 问题描述：给定一个地区的 n 个城市间的距离网，用 Prim 算法或 Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价。 基本要求： 1、城市间的距离