数据结构课程设计指导

1、数据结构课程设计指导课程设计名称：数据结构课程设计 指导老师：欧阳勇课程设计周（时）数：1周指导方式：集体辅导与个别辅导相结合课程设计适用专业：计算机科学与技术课程设计教材及主要参考资料：1、数据结构，严蔚敏编著，清华大学出版社一、课程设计教学目的及基本要求1、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5、设计的题目要求达到一定工作量（

2、200行以上代码），并具有一定的深度和难度。6、编写出课程设计说明书，说明书不少于15页（不包括代码）。二、课程设计内容及安排1、问题定义与需求分析：根据设计题目的要求，充分地分析和理解问题，确定功能需求和限制条件。2、数据结构设计：对问题描述中涉及的操作对象定义相应的数据类型和各抽象数据类型，写出每个抽象数据类型的定义(包括数据结构的描述和每个基本操作的功能说明)，3、总体设计：采用结构化设计方法，按照以数据结构为中心的原则划分模块，设计软件层次结构和模块间的调用关系，定义主程序，画出模块之间的调用关系图。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，4、详细设计

3、：定义数据存储结构，各个主要模块的算法定义。详细设计的结果是对数据结构和基本操作作出进一步的求精，写出数据存储结构的类型定义，用伪码写出函数的算法。5、程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解，使程序中逻辑概念清楚。要求用C语言编写。6、程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果。7、设计结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析

4、。8、编写课程设计报告。题目：学生成绩管理系统(1) 问题描述设计数据结构完成一个学院学生相关信息的存储，并在此基础上编写算法实现学生成绩管理。(2) 课程设计目的应用线性数据结构存储信息，并能够合理的应用排序及查找算法，学会应用散列法。(3) 基本要求 一个学院由若干个班组成；所有学生修相同的考试课和考查课。 管理系统能够实现：学生加入，学生毕业，学生成绩统计，学生查询，学生排名等管理操作。（要考虑考试课和考查课的比重关系） 为方便查找，要求针对学生姓名进行散列法查找。 管理系统应有完整地界面（最好是图形化界面）。(4) 实现提示主要集中在散列函数的构造和冲突的解决上。迷宫的生成与路由(1)

5、 问题描述设计算法生成一个N×M(N行M列)的迷宫，并完成迷宫的组织和存储。实现两种不同的迷宫路由算法：广度优先，深度优先算法。并比较(包括理论和实验)三种方法的时空复杂性。(2) 课程设计目的理解栈的应用，理解深(广)度优先思想，理解问题的理论和实验分析。(3) 基本要求 N和M是用户可配置的，缺省值为50和50。 迷宫的入口和出口分别在第0行和第N-1行上，随机选择。 生成的迷宫要求是连通的。 实现图形化界面(可用VC+，也可用C语言的图形库)。 三种方法的试验比较应该在多个迷宫实例上(尤其可以选一些特定的迷宫)。(4) 实现提示多考虑栈上的运算。“随机漫步”问题(1) 问题描述

6、有一类问题总称为“随机漫步”（random walk）问题，这类问题长久以来吸引着数学界的兴趣。所有这些问题即使是最简单的解决起来也是极其困难的。而且它们在很大程度上还远没有得到解决。一个这样的问题可以描述为：在矩形的房间里，铺有n×m块瓷砖，现将一只（醉酒的）蟑螂放在地板中间一个指定方格里。蟑螂随机地从一块瓷砖“漫步”到另一块瓷砖（可能是在找一片阿司匹林）。假设它可能从其所在的瓷砖移动到其周围八块瓷砖中的任何一个（除非碰到墙壁），那么它把每一块瓷砖都至少接触一次将花费多长时间？虽然这个问题可能很难用纯粹的概率技术来解决，但是使用计算机的话却十分容易。使用计算机解决此问题的技术称为“

7、模拟”。这种技术广泛应用于工业中，用来预测运输流量，存货控制等等。该问题可采用如下方法进行模拟：用一个n×m数组作为计数器来表示蟑螂到达每一块瓷砖的次数，每个数组单元的初始值均置为零。蟑螂在地板上的位置用坐标（ibug，jbug）表示。蟑螂的八种可能移动用在位置(ibug + imovek，jbug + jmovek)的瓷砖表示，其中0k7，并且 imove0 = -1 jmove0 = 1imove1 = 0 jmove1 = 1imove2 = 1 jmove2 = 1imove3 = 1 jmove3 = 0imove4 = 1 jmove4 = -1imove5 = 0 jm

8、ove5 = -1imove6 = -1 jmove6 = -1imove7 = -1 jmove7 = 0蟑螂向其相邻的八个方格的随机漫步通过产生一个随机数值k(0k7)来模拟。当然，蟑螂不能爬出屋外，所以应该去掉通往墙壁的坐标值并形成一个新的随机组合。蟑螂每次进入一个方格，该方格的计数器就增加一，从而计数器的一个非零元素就表示蟑螂到达对应方格的次数。当每一个方格被至少进入一次时，试验就完成了。试编写程序进行上述规定的模拟试验。（2）设计目的利用二维数组解决复杂的实际问题；了解实际问题到计算机问题的转化；了解算法设计中边界条件的重要性(3) 基本要求你的程序必须：（a）能够处理所有的n和m值

9、, n和m满足：2<n40，2m20；（b）能够对“n = 15，m = 15，起始点为（10，10）”和“n = 39，m = 19，起始点为（1，1）”进行实验。（c）具有迭代限制，即实验过程中蟑螂进入方块的最大次数为EM =50000时，程序能够终止。对于每次试验，打印：（d）蟑螂进行的合法移动的总次数。（e）最终的计数器数组，显示出漫步的“密度”，即在实验中每一块瓷砖被接经过的次数。（4）实现提示 无骑士巡游问题(1) 问题描述国际象棋为许多令人着迷的娱乐提供了固定的框架，这些框架独立于游戏本身。其中很多都是基于奇异的骑士“L型”（L-shaped）移动。一个经典的例子就是骑士巡

10、游（knight's tour）问题，自从十八世纪初以来，这个问题吸引了数学家们的兴趣，也使热心者们感到困惑。简而言之，这个问题要求从棋盘上任意给定的方格开始移动骑士，相继地到达所有的64个方格，进入每个方格一次且仅进入一次。通常情况下，我们用如下方法表示一个解：即把数字0，1，63放入棋盘中的方格来表示到达这些方格的顺序。解决骑士巡游问题更具创意的方法之一是由J. C. Warnsdorff在1823年提出的。其规则是：骑士总是移向具有最少出口且没有到达过的方格之一。（2）设计目的利用（二维）数组解决复杂的实际问题；了解实际问题到计算机问题的转化；了解算法设计中边界条件的重要性(3)

11、 基本要求a)使用Warnsdorff规则，设计并实现解决骑士巡游问题的算法；b) 打印棋盘，并显示骑士巡游问题的解，然后终止算法。（4）实现提示a) 用一个二维数组表示国际象棋棋盘；b) 骑士的八种可能移动表示：如果骑士当前位于方格（i，j），则骑士可能移到的方格有（i 2，j + 1），（i - 1，j + 2），（i + 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）处于接近棋盘的边缘方格，在这些可能的移动中，有些移动就会使骑士移出棋盘，这当然是不允

12、许的。我们可以很容易地使用两个数组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某个值，且假定新方块仍然位于棋盘上。稀疏矩阵的完全链表表示及其运算(1) 问题描述稀疏矩阵的每个结点包含down，right，row，col和value五个域。用单独一个结点表示一个非零项，并将所有结点连接在一起，形成两个循环链表。使得第一个表即行表，把所有结点按照行序（同一行内按列

13、序）用right域链接起来。使得第二个表即列表，把所有结点按照列序（同一列内按行序）用down链接起来。这两个表共用一个头结点。另外，增加一个包含矩阵维数的结点。稀疏矩阵的这种存储表示称为完全链表表式。实现一个完全链表系统进行稀疏矩阵运算，并分析下列操作函数的计算时间和额外存储空间的开销。（2）设计目的认识和掌握稀疏矩阵的完全链表表示；能够建立并运用这种存储结构(3) 基本要求建立一个用户友好、菜单式系统进行下列操作，并使用合当的测试数据测试该系统。（a） 读取一个稀疏矩阵建立其完全链表表示（b） 输出一个稀疏矩阵的内容（c） 删除一个稀疏矩阵（d） 两个稀疏矩阵相加（e） 两个稀疏矩阵相减（

14、f） 两个稀疏矩阵相乘（g） 稀疏矩阵的转置（4）实现提示 链表上的操作。仓库管理系统（线性表应用）问题描述建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物以及建立新的仓库存储系统。实现提示可以采用双向链表的存储结构，如可定义如下的存储结构：typedef struct dnode /*定义双向链表结构体*/ int number; /*货物编号*/ char namemax; /*货物名称*/ int counter; /*货物数量*/ struct dnode *prior,*next; /*定义两指针，分别指向其前驱和后继*/ dlnode;哈夫曼编码/译

15、码系统（树应用）问题描述利用哈夫曼编码进行通信，可以压缩通信的数据量，提高传输效率，缩短信息的传输时间，还有一定的保密性。现在要求编写一程序模拟传输过程，实现在发送前将要发送的字符信息进行编码，然后进行发送，接收后将传来的数据进行译码，即将信息还原成发送前的字符信息。实现提示在本例中设置发送者和接受者两个功能，发送者的功能包括：输入待传送的字符信息；统计字符信息中出现的字符种类数和各字符出现的次数（频率）；根据字符的种类数和各自出现的次数建立哈夫曼树；利用以上哈夫曼树求出各字符的哈夫曼编码；将字符信息转换成对应的编码信息进行传送。接受者的功能包括：接收发送者传送来的编码信息；利用上述哈夫曼树对

16、编码信息进行翻译，即将编码信息还原成发送前的字符信息。从以上分析可发现，在本例中的主要算法有三个：（1）哈夫曼树的建立；（2）哈夫曼编码的生成；（3）对编码信息的翻译。教学计划编制问题（图的应用）问题描述大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。实现提示1、 输入参数应包括：学期总数，一学期的学分上限，每门课的课程号（可以是固定

17、占3位的字母数字串）、学分和直接先修课的课程号。2、 应允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。3、 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式可以自己设计。4、 可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。图书管理系统（查找应用）问题描述图书管理基本业务活动包括：对一本书的采编入库、清除库存、借阅和归还等等。试设计一个图书管理系统，将上述业务活动借助于计算机系统完成。实现提示1、 每种书的登记内容至少包

18、括书号、书名、著者、现存量和总库存量等五项。2、 由于图书管理的基本业务活动都是通过书号（即关键字）进行的，所以要用对书号 索引，以获得高效率。3、 系统应实现的基本功能有：l 采编入库：新购入一种书，经分类和确定书号之后登记到图书帐目中去。如果这两种书在帐中已有，则只将总库存量增加。l 清除库存：某种书已无保留价值，将它从图书帐目中注销。l 借阅：如果一种书的现存量大于零，则借出一本，登记借阅者的图书证号和归还期限。l 归还：注销对借阅者的登记，改变该书的现存量。l 显示：以凹入表的形式显示B树。这个操作是为了调试和维护的目的而设置的。通信录查询系统（查找应用）【问题描述】设计散列表实现通讯

19、录查找系统。(1) 设每个记录有下列数据项：电话号码、用户名、地址；(2) 从键盘输入各记录，分别以电话号码为关键字建立散列表；(3) 采用二次探测再散列法解决冲突；(4) 查找并显示给定电话号码的记录；(5) 通讯录信息文件保存；(6) 要求人机界面友好，使用图形化界面；【实现提示】主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人

20、的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。Save()的功能：保存通讯录中的所有记录到指定文件中。Load()的功能：从指定文件中读取通讯录中的记录。药店的药品销售统计系统（排序应用）【问题描述】设计一系统，实现医药公司定期对销售各药品的记录进行统计，可按药品的编号、单价、销售量或销售额做出排名。【实现提示】在本设计中，首先从数据文件中读出各药品的信息记录，存储在顺序表中。各药品的信息包括：药品编号、药名、药品单价、销出数量、销售额。药品编号共4位，采用字母和数字混合编号，如：A125，前一位为大写字母，后三位为数字，按药品编号进行排序时，可采用基数排序法。对各药品的单价、销售量或销售额进行排序时，可采用多种排序方法，如直接插入排序、冒泡排序、快速排序，直接选择排序等方法。在本设计中，对单价的排序