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

《数据结构—课程设计报告.docx》由会员分享，可在线阅读，更多相关《数据结构—课程设计报告.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造课程设计指导书课程设计名称：数据构造课程设计指导教师：丁群课程设计周数：2 周课程设计授课单位：信息工程系指导方式：集体辅导与个别辅导相结合课程设计适用专业：计算机科学与技术课程设计教材及主要参考资料：数据构造，陈越编著，高教出版社数据构造，严蔚敏编著，清华大学出版社一、课程设计教学目的及根本要求1. 了解并把握数据构造与算法的设计方法，具备初步的独立分析和设计力量；2. 初步把握软件开发过程的问题分析、系统设计、程序编码、测试等根本方法和技能；3. 提高综合运用所学的理论学问和方法独立分析和解决问题的力量；4. 训练用系统的观点和软件开发一般标准进展软件开发，培育软件工作者所应具备的

2、科学的工作方法和作风；5. 设计的题目要求到达肯定工作量200 行以上代码，并具有肯定的深度和难度；6. 编写出课程设计说明书，说明书不少于10 页代码不算。二、课程设计内容及安排1. 问题分析和任务定义：依据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？而不是怎么做？限制条件是什么？2. 规律设计：对问题描述中涉及的操作对象定义相应的数据类型，并依据以数据构造为中心的原则划分模块，定义主程序模块和各抽象数据类型。规律设计的结果应写出每个抽象 数据类型的定义(包括数据构造的描述和每个根本操作的功能说明)，各个主要模块的算法， 并画出模块之间的调用关系图；3. 具体设计：定义相应的存

3、储构造并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统构造清楚、合理、简洁和易于调试，抽象数据类型的实现尽可能做到 数据封装，根本操作的规格说明尽可能明确具体。具体设计的结果是对数据构造和根本操作 作出进一步的求精，写出数据存储构造的类型定义，写出函数形式的算法框架；4. 程序编码：把具体设计的结果进一步求精为程序设计语言程序。同时参加一些注解和断言，使程序中规律概念清楚；5. 程序调试与测试：承受自底向上，分模块进展，即先调试低层函数。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6. 结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的

4、输入及其输出结果。算法的时间、空间简单性分析；7. 编写课程设计报告；三、设计报告的内容格式见附件：课程设计格式标准设计完毕后要写出课程设计报告，以作为整个课程设计评分的书面依据和存档材料。设计报告以规定格式的电子文档书写、打印并装订，排版及图、表要清楚、工整。内容及要求如下：封面：题目、班级、学号、姓名、指导教师和完成日期。正文包括以下 7 个内容：1需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1) 输入的形式和输入值的范围；(2) 输出的形式；(3) 程序所能到达的功能；(4) 测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。2概要设计说

5、明本程序中用到的全部抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。3. 具体设计实现概要设计中定义的全部数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法到达的具体程度建议为：依据伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可承受流程图 N S 图或PAD 图进展描述，画出函数和过程的调用关系图。4. 调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回忆争论和分析； b算法的时空分析(包括根本操作和其他算法的时间简单度和空间简单度的分析)和改进设想；c阅历和体会等。5用户使用说明说明如何使用你编写的

6、程序，具体列出每一步的操作步骤。6. 测试结果列出你的测试结果，包括输入和输出。这里的测试数据应当完整和严格，最好多于需求分析中所列。7. 参考文献列出参考的相关资料和书籍。四、课程设计考核方法及成绩评定课程设计完毕时，要求学生写出课程设计报告不附源程序，不得少于10 页，可运行的软件系统包括源程序。课程设计成绩分两局部，设计报告占50，设计作品占 50。五、局部参考课题1. 排序功能要求：（1） 能进展各种排序算法运算，排序包括直接插入希尔排序、改进冒泡排序、快速排序 、堆排序、基数排序。（2） 能对各种算法进展比较.（3） 人机界面自定义，要友好。将排序的结果包括排序后的序列、算法关键字比

7、较和移动的次数等。显示的形式可为图形或文本。（4） 数据的输入有两种方式：手工输入和随机生成。要留意输入数据的个数。随机个数10000。手工输入个数10。2. 家谱治理系统家谱用于记录某家族历代家族成员的状况与关系。本课程设计要求设计并实现一个计算机软件，支持对家谱的存储、更、查询、统计等操作。根本要求内部要求：要求将家谱信息看作树形构造处理，数据可一次读入内存； 外部要求：这一级要求系统具备以下根本功能：(1家庭成员信息存储：将每个家庭成员的根本信息存储在计算机中。家庭成员的根本信息至少应包括：姓名，诞生地，诞生日期，死亡日期，性别，身高，学历，职业，最高职务/职称，；(2) 家族关系存储：

8、将各家庭成员之间的关系，存储在计算机中可永久保存；(3) 更：家谱数据的更修改、删除、参加；输出：将家谱以较友好的格式输出显示；(4查询：按根本信息查询成员，按亲戚关系查询； 增加要求A)统计：统计并打印显示结果，统计的工程有：平均寿命、平均身高、男女比例、家庭平均人口、平均最高/低学历、 3. 文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章， 每行最多不超过 80 个字符，共N 行；要求:（1） 分别统计出其中英文字母数和空格数及整篇文章总字数；（2） 统计某一字符串在文章中消灭的次数，并输出该次数；（3） 删除某一子串，并将后面的字符前移。存储构造使用线

9、性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1） 分行输出用户输入的各行字符；（2） 分 4 行输出“全部字母数“、“数字个数“、“空格个数“、“文章总字数“（3） 输出删除某一字符串后的文章。4. 订票系统任务：通过此系统可以实现如下功能：录入： 可以录入航班状况数据可以存储在一个数据文件中，数据构造、具体数据自定;查询： 可以查询某个航线的状况如，输入航班号，查询起降时间，起飞抵达城市， 航班票价，票价折扣，确定航班是否满仓；可以输入起飞抵达城市，查询飞机航班状况；订票：订票状况可以存在一个数据文件中，构造自己设

10、定可以订票，假设该航班已经无票，可以供给相关可选择航班；退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班状况，订单要有编号;修改航班信息：当航班信息转变可以修改航班数据文件;要求：依据以上功能说明，设计航班信息，订票信息的存储构造，设计程序完成功能；5. 运动会分数统计任务：参与运动会有 n 个学校，学校编号为 1n。竞赛分成m 个男子工程，和w 个女子工程。工程编号为男子1m，女子m+1m+w。不同的工程取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。m=20,n=20功能要求：（

11、1） 可以输入各个工程的前三名或前五名的成绩；（2） 能统计各学校总分；（3） 可以按学校编号、学校总分、男女团体总分排序输出；（4） 可以按学校编号查询学校某个工程的状况；可以按工程编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20 以内的整数假设做得更好可以输入学校的名称，运开工程的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，依据提示，可以完成相关的功能要求。存储构造：学生自己依据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。数据文件的数据读写方法等相关内容在c 语言程序设计的书上，请自学解决请在最终的上交资料中指

12、明你用到的存储构造；测试数据：要求使用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， 求和

13、结果： f(x)+g(x)=8x6+12x5-20x3+22x2+10。挨次表数据类型定义如下： #define MAXLEN 100 typedef structint dataMAXLEN; int last; SeqList;（2） 多项式求和链式存储构造的实现。例如，：f(x)= 100x100+5x50-30x10+10，g(x)=150x90-5x50+40x20+20x10+3x ， 求和结果： f(x)+g(x)=100x100+150x 90+40x20-10x10+3x+10。8. 后缀表达式求值功能要求：（1） 用键盘输入一个整数后缀表达式操作数的范围只有0 到 9，运算

14、符只含+、-、*、/ ，而且中间不行以有空格，使用循环程序从左向右读入表达式。（2） 假设读入的是操作数，直接进入操作数栈。（3） 假设读入的是运算符，马上从操作数栈取出所需的操作数，计算操作数运算的值， 并将计算结果存回操作数栈。9. 循环队列的实现和运算功能要求：（1） 在挨次存储构造上实现输出受限的双端循环队列的入队和出队只允许头出输出 算法。（2） 设每个元素表示一个待处理的作业，元素值表示作业的估量时间。入队列实行简化的短作业化先原则，假设一个提交的作业的估量执行时间小于队头和队尾作业的平均时 间，则插入在队头，否则插入在队尾。（3） 循环队列数据类型： #define MAXLEN

15、 10 typedef struct int dataMAXLEN;/ 定义数据的类型及数据的存储区int front,rear;/定义队头、队尾指针csequeue;（4） 入队作业处理的估量执行时间可以用随机数函数rand产生，也可以用键盘输入。10. 标识符树与表达式求值功能要求：（1） 定义二叉树的构造如下：struct tree/ 定义构造体 int data;/ 定义一个整型数据域struct tree *left;/ 定义左子树指针struct tree *right;/ 定义右子树指针;typedef struct tree btnode;/ 树的构造类型typedef btn

16、ode *bt;/ 定义树结点的指针类型（2） 把算术表达式 2*3+6/3 的标识树如以下图存入一维数组。（3） 求标识符树的前序遍历、中序遍历和后序遍历的序列。（4） 以后序计算标识符树的值。11. 进位制数换算功能要求：（1） 编写选择式菜单程序，实现从十进制数到二进制、八进制、十六进制数的转换。（2） 二进制到十进制数、八进制、十六进制数的转换。（3） 八进制到十进制数、二进制、十六进制数的转换。（4） 十六进制数到十进制数、二进制、八进制数的转换。12. 哈夫曼编译码器功能要求：（1） 生成哈夫曼树。（2） 哈夫曼树承受静态链表存储，其数据类型为：typedef struct/ 定义

17、构造体 int weight;/ 定义一个整型权值变量int lchild,rchild,parent;/ 定义左、右孩子及双亲指针HTNode;typedef HTNode HFMT MAXLEN;/ 是向量类型的（3） 求哈夫曼树对应的哈夫曼编码。（4） 给出哈夫曼编码译出字符13. 约瑟夫生死者玩耍约瑟夫问题的一种描述是：编号为 1，2，.,N 的 N 个人按顺时针方向围坐一圈,每人持有一个密码(正整数).一开头任选一个正整数作为报数上限值 M,从第一个人开头按顺时针方向自 1 开头挨次报数,报到 M 时停顿报数.报 M 的人出列,将他的密码作为的M 值,从他在顺时针方向上的下一个人开头

18、重从1 报数,如此下去,直至全部人全部出列为止.试设计一个程序求出出列挨次根本要求:利用单向循环链表存储构造模拟此过程,依据出列的挨次印出各人的编号.14. 八皇后问题编写程序对八皇后问题进展求解：在 8 行 8 列的棋盘上放置 8 个皇后，使任一个皇后都不能吃掉其他的 7 个皇后注：皇后可吃掉与她处于同行或同列或同一对角线上的其他棋子，并将结果以某种方式显示出来。根本要求：（1） 程序源代码及测试结果（2） 程序功能说明15. 迷宫问题可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；要求： 在上交资料中请写明：存储构造、根本算法可以使用程序流程图、源程序、测试数据和结果、算法的时间简单度、另外可以提出算法的改进方法； 16自己可以自选题目，但需指导教师同意.