《数据结构》课程设计指导书

数据结构课程设计指导书目录数据结构课程设计指导书1目录1一、课程设计目的及基本要求2二、课程设计内容2三、课程设计步骤2四 课程设计时间安排2五、课程设计考核方法及上交材料3课程设计题目41 Set 工具设计(1) 42 List 工具设计(1) 43 LinkedList 工具设计 (1) 54 Stack 和 Queue 工具设计(1) 65 HashTable 工具设计(1) 66 Tree 工具设计(1) 77 BinarySortTree 工具设计(1)98 BTree 工具设计(2)99 简明汉语词典(2)1010基于顺序索引的通讯录(2)1011基于顺序索引的员工管理(2)1012基于二叉排序树的文件索引(2)1113 一元稀疏多项式计算器(1)1114 文章编辑器(1) 1115停车场管理(1) 1116赫夫曼编/译码器(2)1217 校园导游(2)1218 算术表达式求值(1)1219算术表达式形式转换(3)1320 迷宫求解(1)1321 n 皇后问题(1)1322 Hanoi 塔递归过程演示(1)1323 基于堆的最大元输出(1)13一、课程设计目的及基本要求数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同 时，加强上机实践。本课程设计的目标就是要达到理论与实际应用相结合，提高学生组织数 据及编写大型程序的能力，并培养基本的、良好的程序设计技能以及合作能力。设计中要求综合运用所学知识，上机解决一些与实际应用结合紧密的、规模较大的问题， 通过分析、设计、编码、调试、编写文档等各环节的训练，使学生深刻理解、牢固掌握数据 结构和算法设计技术，掌握分析、解决实际问题的能力。同时，在程序设计方法、上机操作、 文档编制等技能受到比较系统和严格的训练。二、课程设计内容每个学生从候选题目中选择一个题目，根据题目的要求设计相应的程序。一般每班中的 每个同学尽可能选择不同的题目，并独立完成。候选题目中各题的难易程序以及实现的复杂 度都不尽相同，这些因素在最后考核时都予以考虑。三、课程设计步骤1. 问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求 做什么？（而不是怎么做？）限制条件是什么？2. 逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为 中心的原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象 数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法， 并画出模块之间的调用关系图；3. 详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考 虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到 数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作 作出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4. 程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和 断言，使程序中逻辑概念清楚；5. 程序调试与测试：采用自底向上，分模块进行，即先调试低层函数。能够熟练掌握调 试工具的各种功能，设计测试数据确定疑点，通过修改程序来证实它或绕过它。调试正确后， 认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6. 结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结 果。7. 编写课程设计报告；四 课程设计时间安排待定五、课程设计考核方法及上交材料课程设计结束时，要求学生写出课程设计报告（附源程序），并提交可运行的软件系统。学生课程设计的成绩主要根据学生的设计过程和报告综合评定得出。具体的成绩评定标准如下：1 设计过程成绩，占课程总成绩的 70%；2 设计报告成绩，占课程总成绩的 30%。另外，在验收程序时，若发现存在抄袭现象，课程设计成绩为0 分。课程设计题目1 Set 工具设计(1)设计并实现一个集合数据结构Set。一个集合中没有重复元素，支持下列运算:booleanadd(E o)如果set中尚未存在指定的元素o,则添加此元素。booleanaddAll (Set c)如果set中没有指定集合c中的所有元素，则将其添加到此set中。voidclear ()移除set中的所有元素。booleancontains(E o)如果set包含指定的元素o,则返回true。booleancontainsAll (Set c)如果此set包含指定集合c中的所有元素，则返回true。booleanisEmpty ()如果set不包含元素，则返回true。booleanremove(E o)如果set中存在指定的元素o,则将其移除。booleanremoveAll(Set c)移除set中那些包含在指定集合c中的元素。booleanretainAll(Set c)仅保留set中那些包含在集合c中的元素。intsize ()返回set中的元素数(其容量)。EtoArray ()返回包含此set中所有元素的数组要求：1用类或函数实现集合数据结构的存储和运算，实现的类或函数放在一个头文件“Set.h”中， 可以被别的函数使用；2设计另外的函数，利用已实现的“Set.h”中集合的相关功能，实现任意两个集合的并、交、 差和补运算。2 List 工具设计(1)一个列表(List)是一个元素的序列，元素可以重复。用户可以根据元素的整数索引(在列 表中的位置)访问元素，并搜索列表中的元素。List支持下列运算：booleanadd(E o)向列表的尾部追加指定的兀素。voidadd(int index, e element) 在列表的指定位直插入指定兀素。voidclear ()从列表中移除所有元素(可选操作)。booleancontains(E o)如果列表包含指定的元素，则返回true。Eget (int index)返回列表中指定位置的元素。intindexOf(E o)返回列表中首次出现指定元素的索引，如果列表不包含此元素，则返回-1。booleanisEmpty()如果列表不包含元素，则返回true。intlastIndexOf(E o)返回列表中最后出现指定元素的索引，如果列表不包含此元素，则返回-1。Eremove (int index)移除列表中指定位置的元素。booleanremove (e o)移除列表中出现的首个指定元素。booleanremoveAll(List c)从列表中移除指定List c中包含的所有元素(可选操作)。Eset(int index, e element)用指定元素替换列表中指定位置的元素。intsize ()返回列表中的元素数。要求：1用类或函数实现List数据结构的存储和运算，实现的类或函数放在一个头文件“List.h” 中，可以被别的函数使用；2设计另外的函数，利用已实现的“List.h”中的相关功能，实现任意两个列表的合并运算。3 LinkedList 工具设计(1)LinkedList是List的链式实现，其具体的功能和实现要求同List。4 Stack 和 Queue 工具设计(1)St ack是后进先出(LIF O)的堆栈。它支持以下运算:booleanempty ()测试堆栈是否为空。Epeek ()查看栈顶兀素而不移除匕。Epop()移除栈顶元素并作为此函数的值返回该元素。Epush(E it em)把项压入栈顶。Queue是先进先出(FIFO)的队列。它支持以下运算:booleanempty()测试队列是否为空。Epeek ()查看队头元素而不移除匕。EDeQueue ()移除队头元素并作为此函数的值返回该元素。EDeQueue(E it em)把元素插入队尾。要求:1 用类或函数实现 Stack 和 Queue 数据结构的存储和运算，实现的类或函数分别放在头文件 “Stack.h”和“Queue.h”中，可以被别的函数使用；2设计一个函数，利用已经实现的“Stack.h”中Stack的相关功能，实现一个任意序列的逆 置操作；设计另外的一个函数，利用已经实现的Queue.h”中Queue的相关功能，实现任 意两个队列的合并运算。5 HashTable 工具设计(1)实现一个哈希表HashTable将键映射到相应的值。它支持以下运算:voidclear ()将此哈希表清空，使其不包含任何键。Eget (Object key)返回此哈希表中指定键所映射到的值。booleanisEmpty ()测试此哈希表是否为空。Kkeys ()返回此哈希表中的所有的键的集合。Eput(K key, V value)将指定key映射到此哈希表中的指定value。Eremove (Object key)从哈希表中移除该键及其相应的值。intsize()返回此哈希表中的键的数量。StringtoString()返回此Hash table元素的字符串表示形式，其形式为 ASCII字符,(逗号加空格)分隔开的、括在括号中的一组 条目。Evalues ()返回此Hashtable中所包含值的集合。要求：1 用类或函数实现 HashTable 数据结构的存储和运算，实现的类或函数放在头文件 “HashTable.h ”中，可以被别的函数使用；2设计一个函数，利用已经实现的“HashTable.h”中的相关功能，实现一个集体中人名的 哈希表。6 Tree 工具设计(1)实现一个二叉树BinaryTree，它支持以下运算:BiTreeInitBiTreeO构造空二叉树。VoidDestroyBiTree ()销毁二叉树。BiTreeCreateBiTree ()创建一棵非空二叉树。BooleanIsEmpty ()判断二叉树是否为空。BiTreeRoot ()返回此二叉树的根节点。EValue(BiTree p)返回此二叉树中节点p的值。VoidAssign(BiTree p, E e)将此二叉树中节点p的值赋为e。BiTreeParent (BiTree p)返回此二叉树中节点p的双亲。BiTreeLeftChild (BiTree p)返回此二叉树中节点p的左孩子。BiTreeRightChild (BiTree p)返回此二叉树中节点p的右孩子。VoidInsertLChild (BiTree p, BiTree C (可选操作)向此二叉树插入一棵子树c (c的右子树为空)作为p的左孩 子，p原来的左子树变为c的右子树。VoidInsertRChild (BiTree p, BiTree C (可选操作)向此二叉树插入一棵子树c(c的右子树为空)作为p的右孩 子，p原来的右子树变为c的右子树。VoidDeleteLChild (BiTree p)(可选操作)删除此二叉树中p节点的左子树。VoidDeleteRChild (BiTree p)(可选操作)删除此二叉树中p节点的左子树。intDepth ()返回此二叉树的深度。StringPreOrderTraverse ()返回二叉树的先序遍历序列。StringInOrderTraverse ()返回二叉树的中序遍历序列。StringPostOrderTraverse ()返回二叉树的后序遍历序列。StringLevelOrderTraverse ()返回二叉树的层次遍历序列。要求：1 用类或函数实现 BinaryTree 数据结构的存储和运算，实现的类或函数放在头文件 “BinaryTree.h ”中，可以被别的函数使用；2设计一个函数，利用已经实现的“BinaryTree.h”中的相关功能，输出一棵二叉树的所有叶 子节点。7 BinarySortTree 工具设计(1)实现一个二叉排序树BinarySortTree，它支持以下运算:BiTreeInitBSTreeO构造空二叉排序树。VoidDestroyBSTree （）销毁二叉排序树。BiTreeSearchBSTree （key）查找二叉排序树中关键字等于key的元素，若找到，返回该 元素在树中的位置，否则返回空。VoidInsertBSTree（E e）若此二叉排序树中不存在关键字等于e.key的元素，则插入e。VoidDeleteBSTree（E e）若此二叉排序树中存在关键字等于e.key的元素，则删除之。StringTraverseBSTreeO返回此二叉树的中序遍历序列。要求：1 用类或函数实现 BinarySortTree 数据结构的存储和运算，实现的类或函数放在头文件 “BinarySortTree.h ”中，可以被别的函数使用；2利用已经实现的“BinaryTree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为 关键字生成对应的二叉排序树索引文件，并利用该文件实现相应的查找操作。8 BTree 工具设计 (2)实现一个B-树BTree，它支持以下运算:BTreeInitBTreeO构造空B-树。VoidDestroyBTree () 销毁B-树。BTreeSearchBTree（key）查找B-树中关键字等于key的元素，若找到，返回该元素在 树中的位置，否则返回空。VoidInsertBTree（E e）右此B-树中不存在关键字等于e.key的元素，则插入e。VoidDeleteBTree（E e）若此B-树中存在关键字等于e.key的元素，则删除之。StringTraverseBTreeO返回此B-树的中序遍历序列。要求：1用类或函数实现BTree数据结构的存储和运算，实现的类或函数放在头文件“BTree.h”中， 可以被别的函数使用；2利用已经实现的“BTree.h”中的相关功能，对一个已知的学生成绩表文件按照学号为关键 字生成对应的B-树索引文件，并利用该文件实现相应的查找操作。9 简明汉语词典（2）编制一个简单的词典系统，该系统要求实现词典的建立、词条的追加、维护、查询功能。 要求：（1）词典用一个独立的文件存放，词条信息包括：词名、读音、词性、词义等；（2）词典建立索引，该索引用分块索引或建树实现，索引也作为独立的文件放在外 存；（3）系统要求有简单的界面实现在词条追加、更改和查询时的人机交互。10 基于顺序索引的通讯录（2）编写一个简单的通讯录管理, 要求实现查询、排序、修改等功能。 要求 通讯录用一个独立的文件存放； 建立索引，索引也作为独立的文件放在外存； 录入或修改：录入或修改通讯信息 查询/统计: 按关键字查询或统计。11 基于顺序索引的员工管理（2）每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。实 现对员工信息的查询、更新、插入、删除等功能。要求（1）录入：录入员工的信息，并存放于文件中（2）建立索引，索引也作为独立的文件放在外存；（3）查询：按特定条件查找员工。（4）更新：按编号对某个员工的某项信息进行修改。（5）插入：加入新员工的信息。（6）删除：按编号删除已离职的员工的信息。12 基于二叉排序树的文件索引(2)建立一个学生档案文件，利用二叉排序树建立文件的索引，并实现如下操作 要求(1) 录入：录入学生的档案信息，并存放于文件中(2) 建立索引：用二叉排序树建立索引，索引也作为独立的文件放在外存(3) 查询：按特定条件查找学生。(4) 更新：按编号对某个学生的某项信息进行修改。(5) 插入：加入新学生的信息。(6) 删除：按编号删除学生的信息。13 一元稀疏多项式计算器(1)设计一个一元稀疏多项式简单计算器。要求一元稀疏多项式计算器的基本功能是：1 .输入并建立多项式2 .输出多项式，多项式的输出形式为类数学表达式。例如，xi5+(-8)x7-14的输出形式为x15-8x 7-14。序列按指数降序排列；3.多项式a和b相加，建立多项式a + b4 .多项式a和b相减，建立多项式a b5.计算多项式在x处的值。14 文章编辑器(1)实现一个简单的文章编辑器，使其能够录入、统计、插入、删除、查找/替换等功能。要求(1) 能够录入或载入一页文字，设每页文字共N行，每行最多不超过80个字符;2) 能够对录入或修改后的文字存盘；3) 实现简单的统计功能：统计出其中英文字母数和空格数及整篇文章总字数；4) 插入某一字符串：并将后面的字符后移；5) 删除某一字符串：并将后面的字符后移；6) 查找/替换：查找某一子串在文章中的位置，并能替换为其它内容。15 停车场管理(1)设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车 在停车场内按车辆到达时间的先后顺序，依次由北向南排列(大门在最南端，最先到达的第 一辆车停放在车场的最北端)，若车场内已停满n辆汽车，则后来的汽车只能在门外的便道 上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时， 在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序 进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为 停车场编制按上述要求进行管理的模拟程序。要求1 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模 拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及 到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽 车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交 纳的费用(在便道上停留的时间不收费)。16 赫夫曼编/译码器(2)利用赫夫曼编码进行通信可大大提高信道利用率，缩短信息传输时间。试编写一个赫夫 曼编/译码系统。要求(1) I：初始化(Ini tializa tion)。从终端读入字符集大小n,以及n个字符和n个权 值，建立赫夫曼树。(2) E:编码(Encoding)。利用已建好的赫夫曼树对文件ToBeTran中的正文进行编码, 然后将结果存入CodeFile文件中。(3) D:译码(Decoding)。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码, 结果存入TextFile中。(4) P:打印(Print)。打印 CodeFile 和 TextFile 中的内容。17 校园导游(2)用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息,图中的边表示景点间的道路,存放路径长度等信息。要求( 1 ) 查询各景点的相关信息；(2) 查询图中任意两个景点间的最短路径。(3) 查询图中任意两个景点间的所有路径。(4) 增加、删除、更新有关景点和道路的信息。18 算术表达式求值(1)一个算术表达式是由操作数(operand)、运算符(opera tor)和界限符(delim it er)组成 的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式 起始、结束符“#”，如：#(7+15)*(23-28/4)#。引入表达式起始、结束符是为了方便 编程利用“算符优先法”求算术表达式的值。19 算术表达式形式转换(3)一个算术表达式是由操作数(operand)、运算符(opera tor)和界限符(delim it er)组成 的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式 起始、结束符“#”，如：#(7+15)*(23-28/4)#。引入表达式起始、结束符是为了方便 编程实现将一个中缀表达式转换为相应的前缀或后缀表达式形式。20 迷宫求解(1)以一个mxn的方阵表示迷宫，0和1分别表示迷宫中的通路和障碍。设计一个程序，对任 意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。21 n 皇后问题(1)在nxn格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击之处 在同一行或同一列或同一斜线上的棋子。n后问题等价于在nxn格的棋盘上放置n个皇后， 任何2个皇后不放在同一行或同一列或同一斜线上。设计一个程序，求出n后问题中的所有 解。22 Hanoi 塔递归过程演示(1)演示 Hanoi 塔的递归执行过程，要求：1 对 Hanoi 塔递归过程中的栈的变化情况以及塔的变化情况都进行演示；2可以编程实现，或采用powerpoint的内置动画功能以及其它动画工具进行演示。23 基于堆的最大元输出(1)已知一组随机产生的数值序列，其元素个数不断增加。用堆实现：1 输出初始的数值序列中的最大元；2 在元素增加后，重新筛选，输出最大元。