数据结构课程设计要求

1、数据结构课程设计指导书 一、 课程设计的性质、任务和目的课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。数据结构是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范，能够为今后从事计算机开发与应用打下基础。需要学生具有丰富科学知识、独立解决实际问题、有创造能力，这

2、也是该课程设计的最终目的。二、课程设计的方式与基本要求方式：整个课程设计要求分为四个阶段来完成。第一阶段为准备阶段，此阶段要求将学生自主进行问题分析和相关资料查询，并对课程设计内容作初步设计；第二阶段为编程及程序调试阶段，此阶段会安排一定数量的集中上机时间；第三阶段为程序测试及检查阶段，此阶段由指导老师对每位学生的设计结果作测试和检查，并根据测试及检查结果评定学生成绩，此成绩占课程设计总成绩的70%；第四阶段为学生编写课程设计实验报告阶段，每位学生按照课程设计实验报告的内容和要求编写详细的课程设计实验报告并打印上交给指导老师，由指导老师根据每位学生的完成情况评定成绩，此成绩占课程设计总成绩的3

3、0%。三、课程设计的基本要求数据结构课程设计要求学生在规定的时间内（三周内）完成所选题目，并根据所选问题分析设计思路、选择数据结构描述、确立算法过程、用一种计算机语言（用C语言）编写出详细的实现程序，然后通过上机反复调试与修改，直到获得满意的结果为止。对于要解决的同一问题，由于所采用的数据结构可能不同、所选择的算法可能不同、编写的程序也不尽相同，但只要结果正确且有效（具有较好的时间复杂度和空间复杂度）即可，即不要求编写的算法和程序完全一致，但力求编写的算法和程序更优秀、综合指标更好。通过本课程的课程设计，应使学生达到以下的基本要求 : 1. 能根据加工数据对象的特征，选择适当的数据结构、存储结

4、构及相应算法，基本掌握各种算法在时间和空间的分析技巧。 2. 能够进行算法设计和程序设计，并且使所设计的程序结构清楚，正确易读，并上机调试通过。 3初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5. 设计的题目要求达到一定工作量，并具有一定的深度和难度。6. 较强的实习、实践能力；较强的分析问题、解决问题的能力。设计要求： 1. 有明确的设计思路； 2. 有完整的界面； 3. 能够完整实现算法； 4. 有图形辅助说明； 5. 有适当的帮助功能； 6

5、. 设计完成后写出设计报告，对整个设计过程做出总结。 课程设计报告要求 : 1. 每一项设计要求都要用函数实现，； 2. 有程序流程图； 3. 有程序清单； 5. 课程设计中遇到的难点及解决方法； 6. 收获总结。 7. 做好设计期间的记录。 四、课程设计的主要任务 1. 问题分析和任务定义 根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？2. 逻辑设计 对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的

6、功能说明)，各个主要模块的算法，并给出模块之间的调用关系。3. 详细设计 定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架。4. 程序编码 把详细设计的结果进一步求精为程序设计语言程序。程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释，使程序中逻辑概念清楚。5. 调试与测试 采用自底向上，分模块进行，即先调试低

7、层函数。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6.编写课程设计报告五、课程设计报告内容与要求课程设计报告要求：(1) 不少于2500字（12-15页），先交电子稿，由学委在12月5日前收齐，老师检查通过后可打印(A4纸)交上来。 (2) 正文部分可以包括：需求分析、概要设计、详细设计、测试与分析、总结、源程序清单。 (3) 设计报告一人一题，严禁抄袭，否则按不及格处理。课程设计报告内容 数据结构课程设计实验报告要求完成的内容包括：1、 引言给出问题分析过程，充分分析和理解问题的设计要求，写出本课程设计的研究内容和研究意

8、义；2、 给出数据结构描述根据要解决的问题，考虑各种可能的数据结构类型，从中选择一种较为有效的方法，并写出采用的数据结构描述及其功用。3、 给出相应算法设计根据问题分析的结果，并确立好所选的数据结构描述，然后写出合理的算法设计过程，特别要注意所使用函数间的调用与被调用关系。4、 给出详细程序清单根据算法的内容，用计算机语言（如C语言）编写完整的程序，并将程序在机器上反复调试，直到结果正确为止，最后将程序清单打印出来，要求附上详细注解。特别要注意算法与程序的区别以及上下层模块间的接口处理。5、 给出程序运行结果利用典型的测试用例，将数据输入到程序执行过程中去，记下执行过程中屏幕显示情况与相应结果

9、。6、报告格式见附件六、考核方式与评分办法1、 考核方式：上机测试及编写课程设计实验报告。2、 评分办法：课程设计的上机测试结果占70%，实验报告成绩占30%。七课程设计 按7-9页的排版规范来统一，不符合规范的将不能及格；（请注意看后面的附注部分）八、课程设计的参考资料参考资料：1严蔚敏 吴伟民，.数据结构(C语言版). 清华大学出版社；2严蔚敏 吴伟民，.数据结构题集(C语言版) 清华大学出版社；3 李春葆，数据结构（C语言篇)习题与解析，清华大学出版社 数据结构课程设计题目 （每个同学可按下面列出的题目选题，如果有自己感兴趣的题目可提交给老师，老师审核通过后才能作为课程设计题目）1. 迷

10、宫求解 （1）.设计目的 仅仅认识到栈是一种特殊的线性表是远远不够的，本次实习的目的在于使学生深入了解栈的特征，以便在实际问题背景下灵活运用它，同时还将巩固这种数据结构的构造方法。 （2） 问题描述 迷宫问题是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒子中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口走到出口，而不走错一步。老鼠经过多次试验最终学会走通迷宫的路线。设计一个计算机程序对任意设定的矩形迷宫A，求出一条从入口到出口的通路，或得出没有通

11、路的结论。 （3）设计要求(1) 建立一个大小为m×n的任意迷宫（迷宫数据可由用户输入或由程序自动生成），并在屏幕上显示出来；（2）找出一条通路的二元组（i,j）数据序列，（i,j）表示通路上某一点的坐标。（3）用一种标志（如数字8）在迷宫中标出该条通路；（4）在屏幕上输出迷宫和通路； 2. .赫夫曼编码的应用 1、 设计目的 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 2、 问题描述 赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码

12、。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。 3、 设计要求 本设计要求是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生成的代码串进行译码，输出电文字符串。 4、 相关知识介绍 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为WiLi。若将此对

13、应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵赫夫曼树，此构造过程称为赫夫曼编码。根据设计要求和分析，要实现本设计，必须实现以下几个方面的功能： (1) 赫夫曼树的建立； (2) 赫夫曼编码的生成； (3) 编码文件的译码。 3. .综合排序 （1）设计目的 对于数据处理工作，排序是其最基本的运算之一。在当今的计算机系统中，花费在排序上的时间占系统CPU运行时间的很大比重（约20%60%）。为了提高计算机的工作效率，人们提出了各种各样的排序算法，这些算法充

14、分地展示了算法设计的某些重要原则和高超技巧。本设计旨在对一些常用的内部排序算法作深入地探讨和理解，通过比较，评价各算法的优劣。 （2）问题描述 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。 （3）设计要求 (1) 实现基本排序方法：直接插入排序、希尔排序、冒泡、快速排序、直接选择、堆排序；（要求至少实现四种算法） (2) 利用随机函数产生不少于100个随机整数，利用直接插入排序、希尔排序、冒泡、快速排序、直接选择、堆排序等排序方法进行递增排序，统计各算法的关键字比较次数和关键字移动次数

15、； (3) 可以用菜单的形式组织程序各功能； (4) 至少要用5组不同的输入数据作比较，比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）；(5 ) 观察所有实验结果并汇集成表格加以总结。 4 .学生信息管理 (1) 问题描述 为学生管理人员编写一个学生信息管理的软件；可用顺序存储或链式存储方式实现。 （2）设计要求要求每条学生信息至包含学号(xh)、姓名(xm)、性别(xb)、年龄(nl)、专业(zy)等，完成如下功能：a) 输入学生基本信息记录input( ) b) 增加一名学生记录（可和功能1合并）insert( ) c) 删除指定（按姓名）学生的信息delet

16、e( ) d) 修改指定（按姓名）学生的信息）modify( ) e) 查询符合条件的学生（按专业）search( ) f) 显示学生管理库中的信息display( )5 集合的并、交和差运算（1）. 问题描述 编制一个能演示执行集合的并、交和差运算的程序。（2） 基本要求 (1) 集合的元素限定为小写字母字符 a.z 。(2) 演示程序以用户和计算机的对话方式执行。（3）测试数据 (1)Set1="magazine"，Set2="paper"，Set1Set2="aegimnprz"，Setl Set2="ae"

17、，Set1-Set2="gimnz"。(2)Set1= " 012oper4a6tion89"，Set2="error data"，Set1Set2="adeinoprt"，Setl Set2="aeort"，Set1-Set2="inp"。（4） 实现提示以有序链表表示集合。（5） 选作内容(1) 集合的元素判定和子集判定运算。(2) 求集合的补集。(3) 集合的混合运算表达式求值。(4) 集合的元素类型推广到其他类型 ， 甚至任意类型。6 . 稀疏矩阵运算器(1) 问题描

18、述稀疏矩阵是指那些多数元素为零的矩阵。利用 " 稀疏 " 特点进行存储和计算可以大大 节省存储空间 , 提高计算效率。实现一个能进行稀疏矩阵基本运算的运算器。（2） 基本要求以三元组顺序表表示稀疏矩阵,实现两个矩阵相加、相减和相乘、及矩阵的转置的运算。稀疏矩阵的输入形式采用三元组表示 , 而运算结果的矩阵则以通常的阵列形式列出。（3） 实现提示 首先应输入矩阵的行数和列数 , 并判别给出的两个矩阵的行、列数对于所要求作的运算是否相匹配。可设矩阵的行数和列数均不超过 20 。 程序可以对三元组的输入顺序加以限制 , 例如 , 按行优先。 在用三元组表示稀疏矩阵时 , 相加或相

19、减所得结果矩阵应该另生成 , 乘积矩阵也可用二维数组存放。7. 算术表达式求值(1) 问题描述一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”， 如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。（2） 基本要求 首先利用用栈 将中缀表达式转换成后缀表达式：用栈对后缀表达式求值；从键盘读入一个合法的算术表达式，输出正确的结果。显示输入序列和栈的变化过程。 （3）实现提示为实现运算符优先，可以使用两个操作栈，操作数栈s

20、t ,用于存放操作数及运算结果；操作符栈op，用于存放操作符。 滨江学院数据结构 课程设计题 目 院 系 计算机系 从此开始横线对齐。年级班级 2012级软工工程（3） 学生姓名 学 号 学 期 2014-2015（一） 任课教师 黄 群 二一四年 十二月 十 日9论坛系统题目1 引言主要写课题的研究背景和研究意义 在现在信息化的时代，网上论坛是最常见的网上交流的载体，是电子布告栏系统。网上论坛相当于一个网上社区，人们在这个虚拟社区中能够进行各种交流活动。本课程就是关于网上论坛的一个系统，在本系统中用户可以自由的发表意见、讨论问题、浏览信息、相互交换信息与帮助等。论文及参考文献全部用1.25倍行距，正文，正文中文一律采用宋体五号宋体字，英文为Times New Roman，中文标点一律采用全角。 系统用户主要有普通用户、论坛管理员、分类讨论区版主。其中普通用户主要有：注册、登录、浏览论坛、查询与修改、发表帖子、回复帖子、删除自己发表的帖子等。论坛管理员具有最高的权限，除了具有可以使用版主的功能外，还具有进行论坛用户管理，并对讨论区的所有帖子进行管理。分类讨论区版主除了使用普通用户的功能