《数据结构课程设计指导2010》由会员分享，可在线阅读，更多相关《数据结构课程设计指导2010（8页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程设计指导课程设计名称：数据结构课程设计 指导老师： 课程设计周（时）数：1周指导方式：集体辅导与个别辅导相结合课程设计适用专业：计算机科学与技术课程设计教材及主要参考资料：1、数据结构，严蔚敏编著，清华大学出版社一、课程设计教学目的及基本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求达到一定工作量（20
2、0行以上代码），并具有一定的深度和难度。6、编写出课程设计说明书，说明书不少于15页（不包括代码）。二、课程设计内容及安排1、问题定义与需求分析：根据设计题目的要求，充分地分析和理解问题，确定功能需求和限制条件。2、数据结构设计：对问题描述中涉及的操作对象定义相应的数据类型和各抽象数据类型，写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，3、总体设计：采用结构化设计方法，按照以数据结构为中心的原则划分模块，设计软件层次结构和模块间的调用关系，定义主程序，画出模块之间的调用关系图。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，4、详细设计：定
3、义数据存储结构，各个主要模块的算法定义。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，用伪码写出函数的算法。5、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚。要求用C语言编写。6、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。7、设计结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析。8
4、、编写课程设计报告。题目：学生成绩管理系统(1) 问题描述设计数据结构完成一个学院学生相关信息的存储，并在此基础上编写算法实现学生成绩管理。(2) 课程设计目的应用线性数据结构存储信息，并能够合理的应用排序及查找算法，学会应用散列法。(3) 基本要求 一个学院由若干个班组成；所有学生修相同的考试课和考查课。 管理系统能够实现：学生加入，学生毕业，学生成绩统计，学生查询，学生排名等管理操作。（要考虑考试课和考查课的比重关系） 为方便查找，要求针对学生姓名进行散列法查找。 管理系统应有完整地界面（最好是图形化界面）。(4) 实现提示主要集中在散列函数的构造和冲突的解决上。迷宫的生成与路由(1) 问
5、题描述设计算法生成一个NM(N行M列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。(2) 课程设计目的理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。(3) 基本要求 N和M是用户可配置的，缺省值为50和50。 迷宫的入口和出口分别在第0行和第N-1行上，随机选择。 生成的迷宫要求是连通的。 实现图形化界面(可用VC+，也可用C语言的图形库)。 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。(4) 实现提示多考虑栈上的运算。算法：所有的格子均为黑点（表示此路不通），然后随
6、机生成白点，每生成5个白点就走一次迷宫直到能够走通迷宫为止，并记载出口的位置（如有n个出口，则将封闭n-1个出口）。“随机漫步”问题(1) 问题描述有一类问题总称为“随机漫步”（random walk）问题，这类问题长久以来吸引着数学界的兴趣。所有这些问题即使是最简单的解决起来也是极其困难的。而且它们在很大程度上还远没有得到解决。一个这样的问题可以描述为：在矩形的房间里，铺有nm块瓷砖，现将一只（醉酒的）蟑螂放在地板中间一个指定方格里。蟑螂随机地从一块瓷砖“漫步”到另一块瓷砖（可能是在找一片阿司匹林）。假设它可能从其所在的瓷砖移动到其周围八块瓷砖中的任何一个（除非碰到墙壁），那么它把每一块瓷砖
7、都至少接触一次将花费多长时间？虽然这个问题可能很难用纯粹的概率技术来解决，但是使用计算机的话却十分容易。使用计算机解决此问题的技术称为“模拟”。这种技术广泛应用于工业中，用来预测运输流量，存货控制等等。该问题可采用如下方法进行模拟：用一个nm数组作为计数器来表示蟑螂到达每一块瓷砖的次数，每个数组单元的初始值均置为零。蟑螂在地板上的位置用坐标（ibug，jbug）表示。蟑螂的八种可能移动用在位置(ibug + imovek，jbug + jmovek)的瓷砖表示，其中0k7，并且 imove0 = -1 jmove0 = 1imove1 = 0 jmove1 = 1imove2 = 1 jmov
8、e2 = 1imove3 = 1 jmove3 = 0imove4 = 1 jmove4 = -1imove5 = 0 jmove5 = -1imove6 = -1 jmove6 = -1imove7 = -1 jmove7 = 0蟑螂向其相邻的八个方格的随机漫步通过产生一个随机数值k(0k7)来模拟。当然，蟑螂不能爬出屋外，所以应该去掉通往墙壁的坐标值并形成一个新的随机组合。蟑螂每次进入一个方格，该方格的计数器就增加一，从而计数器的一个非零元素就表示蟑螂到达对应方格的次数。当每一个方格被至少进入一次时，试验就完成了。试编写程序进行上述规定的模拟试验。（2）设计目的利用二维数组解决复杂的实际问
9、题；了解实际问题到计算机问题的转化；了解算法设计中边界条件的重要性(3) 基本要求你的程序必须：（a）能够处理所有的n和m值, n和m满足：2n40，2m20；（b）能够对“n = 15，m = 15，起始点为（10，10）”和“n = 39，m = 19，起始点为（1，1）”进行实验。（c）具有迭代限制，即实验过程中蟑螂进入方块的最大次数为EM =50000时，程序能够终止。对于每次试验，打印：（d）蟑螂进行的合法移动的总次数。（e）最终的计数器数组，显示出漫步的“密度”，即在实验中每一块瓷砖被接经过的次数。（4）实现提示 无算法：将蟑螂所在格标记为0，其周围的格子分别标记为1、2、3、4、
10、5、6、7、8，然后从18随机生成数，生成哪个数就走哪一步（除开撞墙）。每个格子只走一遍的算法：图的遍历骑士巡游问题(1) 问题描述国际象棋为许多令人着迷的娱乐提供了固定的框架，这些框架独立于游戏本身。其中很多都是基于奇异的骑士“L型”（L-shaped）移动。一个经典的例子就是骑士巡游（knights tour）问题，自从十八世纪初以来，这个问题吸引了数学家们的兴趣，也使热心者们感到困惑。简而言之，这个问题要求从棋盘上任意给定的方格开始移动骑士，相继地到达所有的64个方格，进入每个方格一次且仅进入一次。通常情况下，我们用如下方法表示一个解：即把数字0，1，63放入棋盘中的方格来表示到达这些方
11、格的顺序。解决骑士巡游问题更具创意的方法之一是由J. C. Warnsdorff在1823年提出的。其规则是：骑士总是移向具有最少出口且没有到达过的方格之一。（2）设计目的利用（二维）数组解决复杂的实际问题；了解实际问题到计算机问题的转化；了解算法设计中边界条件的重要性(3) 基本要求a)使用Warnsdorff规则，设计并实现解决骑士巡游问题的算法；b) 打印棋盘，并显示骑士巡游问题的解，然后终止算法。（4）实现提示a) 用一个二维数组表示国际象棋棋盘；b) 骑士的八种可能移动表示：如果骑士当前位于方格（i，j），则骑士可能移到的方格有（i 2，j + 1），（i - 1，j + 2），（i
12、 + 1，j + 2），（i + 2，j + 1），（i + 2，j - 1）（i + 1，j -2），（i - 1，j - 2），（i - 2，j - 1）。然而，我们注意到，如果（i，j）处于接近棋盘的边缘方格，在这些可能的移动中，有些移动就会使骑士移出棋盘，这当然是不允许的。我们可以很容易地使用两个数组ktmove1和ktmove2把骑士的八种可能移动表示为： ktmove1 ktmove2 -2 1 -1 21 22 12 -1 1 -2 -1 -2 -2 -1于是，位于（i，j）的骑士就可能移到（i + ktmove1k，j + ktmove2k），其中k是介于0和7之间de某个值，
13、且假定新方块仍然位于棋盘上。稀疏矩阵的完全链表表示及其运算(1) 问题描述稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。（2）设计目的认识和掌握稀疏矩阵的
14、完全链表表示；能够建立并运用这种存储结构(3) 基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。（a） 读取一个稀疏矩阵建立其完全链表表示（b） 输出一个稀疏矩阵的内容（c） 删除一个稀疏矩阵（d） 两个稀疏矩阵相加（e） 两个稀疏矩阵相减（f） 两个稀疏矩阵相乘（g） 稀疏矩阵的转置（4）实现提示 链表上的操作。仓库管理系统（线性表应用）问题描述建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物以及建立新的仓库存储系统。实现提示可以采用双向链表的存储结构，如可定义如下的存储结构：typedef struct dnode /*定义双向链表结构体*/ int number; /*货物编号*/ char namemax; /*货物名称*/ int counter; /*货物数量*/ struct dnode *prior,*next; /*定义两指针，分别指向其前
