数据结构—课程设计报告.doc

数据结构课程设计指导书课程设计名称：数据结构课程设计指导老师：丁群课程设计周数：2周课程设计授课单位：信息工程系指导方式：集体辅导与个别辅导相结合课程设计适用专业：计算机科学与技术课程设计教材及主要参考资料：数据结构，陈越编著，高教出版社数据结构，严蔚敏编著，清华大学出版社一、课程设计教学目的及基本要求1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风；5.设计的题目要求达到一定工作量（200行以上代码），并具有一定的深度和难度；6.编写出课程设计说明书，说明书不少于10页（代码不算）。二、课程设计内容及安排1.问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2.逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，各个主要模块的算法，并画出模块之间的调用关系图；3.详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4.程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5.程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6.结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7.编写课程设计报告；三、设计报告的内容（格式见附件：课程设计格式规范）设计结束后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下：封面：题目、班级、学号、姓名、指导教师和完成日期。正文包括以下7个内容：1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可采用流程图NS图或PAD图进行描述，画出函数和过程的调用关系图。4调试分析内容包括： a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；c经验和体会等。5用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。6测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。7参考文献列出参考的相关资料和书籍。四、课程设计考核方法及成绩评定课程设计结束时，要求学生写出课程设计报告（不附源程序），不得少于10页，可运行的软件系统（包括源程序）。课程设计成绩分两部分，设计报告占50，设计作品占50。五、部分参考课题1.排序功能要求：（1）能进行各种排序算法运算，排序包括直接插入希尔排序、改进冒泡排序、快速排序、堆排序、基数排序。（2）能对各种算法进行比较.（3）人机界面自定义，要友好。将排序的结果包括排序后的序列、算法关键字比较和移动的次数等。显示的形式可为图形或文本。（4）数据的输入有两种方式：手工输入和随机生成。要注意输入数据的个数。随机个数10000。手工输入个数10。2.家谱管理系统家谱用于记录某家族历代家族成员的情况与关系。本课程设计要求设计并实现一个计算机软件，支持对家谱的存储、更新、查询、统计等操作。基本要求内部要求：要求将家谱信息看作树形结构处理，数据可一次读入内存；外部要求：这一级要求系统具备下列基本功能： (1）家庭成员信息存储：将每个家庭成员的基本信息存储在计算机中。家庭成员的基本信息至少应包括：（姓名，出生地，出生日期，死亡日期，性别，身高，学历，职业，最高职务/职称，）；(2)家族关系存储：将各家庭成员之间的关系，存储在计算机中（可永久保存）；(3)更新：家谱数据的更新（修改、删除、加入）；输出：将家谱以较友好的格式输出（显示）；(4）查询：按基本信息查询成员，按亲戚关系查询；增强要求A)统计：统计并打印（显示）结果，统计的项目有：平均寿命、平均身高、男女比例、家庭平均人口、平均（最高/低）学历、 3文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求:（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章。4订票系统任务：通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）;查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号;修改航班信息：当航班信息改变可以修改航班数据文件;要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；5运动会分数统计任务：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：（1）可以输入各个项目的前三名或前五名的成绩；（2）能统计各学校总分；（3）可以按学校编号、学校总分、男女团体总分排序输出；（4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；6个人光盘管理系统任务：开发一个简单实用的个人光盘自助管理系统功能要求：1.自动生成对光盘一级目录（文件）的摘要信息2.人机结合对自动生成的摘要信息明确化后存储3.光盘查询功能，如查询影视、资料、歌曲等光盘，以便使用4.光盘的借出和归还功能7多项式求和功能要求：（1）多项式求和顺序存储结构的实现。例如，已知：f(x)=8x6+5x5-10x4+32x2-x+10，g(x)=7x5+10x4-20x3-10x2+x，求和结果：f(x)+g(x)=8x6+12x5-20x3+22x2+10。顺序表数据类型定义如下：#defineMAXLEN100typedefstructintdataMAXLEN;int last;SeqList;（2）多项式求和链式存储结构的实现。例如，已知：f(x)=100x100+5x50-30x10+10，g(x)=150x90-5x50+40x20+20x10+3x，求和结果：f(x)+g(x)=100x100+150x90+40x20-10x10+3x+10。8后缀表达式求值功能要求：（1）用键盘输入一个整数后缀表达式（操作数的范围只有0到9，运算符只含+、-、*、/，而且中间不可以有空格），使用循环程序从左向右读入表达式。（2）如果读入的是操作数，直接进入操作数栈。（3）如果读入的是运算符，立即从操作数栈取出所需的操作数，计算操作数运算的值，并将计算结果存回操作数栈。9循环队列的实现和运算功能要求：（1）在顺序存储结构上实现输出受限的双端循环队列的入队和出队（只允许头出输出）算法。（2）设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业化先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。（3）循环队列数据类型：#defineMAXLEN10typedefstructintdataMAXLEN; /定义数据的类型及数据的存储区intfront,rear; /定义队头、队尾指针csequeue;（4）入队作业处理的预计执行时间可以用随机数函数rand()产生，也可以用键盘输入。10标识符树与表达式求值功能要求：（1）定义二叉树的结构如下：structtree/定义结构体intdata;/定义一个整型数据域structtree*left;/定义左子树指针structtree*right;/定义右子树指针;typedefstructtreebtnode;/树的结构类型typedefbtnode*bt;/定义树结点的指针类型（2）把算术表达式2*3+6/3的标识树（如下图）存入一维数组。（3）求标识符树的前序遍历、中序遍历和后序遍历的序列。（4）以后序计算标识符树的值。11进位制数换算功能要求：（1）编写选择式菜单程序，实现从十进制数到二进制、八进制、十六进制数的转换。（2）二进制到十进制数、八进制、十六进制数的转换。（3）八进制到十进制数、二进制、十六进制数的转换。（4）十六进制数到十进制数、二进制、八进制数的转换。12哈夫曼编译码器功能要求：（1）生成哈夫曼树。（2）哈夫曼树采用静态链表存储，其数据类型为：typedefstruct/定义结构体intweight;/定义一个整型权值变量intlchild,rchild,parent;/定义左、右孩子及双亲指针HTNode;typedefHTNodeHFMTMAXLEN; /是向量类型的（3）求哈夫曼树对应的哈夫曼编码。（4）给出哈夫曼编码译出字符13.约瑟夫生死者游戏约瑟夫问题的一种描述是：编号为1，2，.,N的N个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开始任选一个正整数作为报数上限值M,从第一个人开始按顺时针方向自1开始顺序报数,报到M时停止报数.报M的人出列,将他的密码作为新的M值,从他在顺时针方向上的下一个人开始重新从1报数,如此下去,直至所有人全部出列为止.试设计一个程序求出出列顺序基本要求:利用单向循环链表存储结构模拟此过程,按照出列的顺序印出各人的编号.14