动态查找表-课程设计报告.doc

动态查找表 摘 要 数据结构是研究与数据之间的关系，我们称这一关系为数据的逻辑结构，简称数据结构。当数据的逻辑结构确定以后，数据在物理空间中的存储方式，称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构，因而有不同的算法。 本次课程设计，程序中采用树形结构作为其数据结构。具体采用的是二叉排序树作为其存储结构。中序遍历删除二排序树中某个结点摘 要 1 1 Abstract 3 2 抽象数据类型动态查找表定义 4 3 系统总体分析 5 3.1系统模块划分 5 3.2 二叉树的生成过程 5 3.3 主要功能模块设计 5 3.4 系统详细设计 7 3.4.1 主函数菜单模块 7 3.4.2 查找模块 11 3.4.3 删除模块 12 3.4.4 插入模块 13 3.4.5 中序输出模块 15 参考文献 17 心 得 体 会 18 教 师 评 语 19 附 录 20 1 Abstract Data structure is the relationship between research and data, we call this relationship as a logical data structure, referred to as data structures. When the data logical structure is determined, the data stored in the physical space, is known as the data storage structure. The same logical structure can have different storage structure, which has a different algorithm. The curriculum design, program data is tree as its data structure. Specific uses binary sort tree and use binary list as its storage structure. The course is designed to achieve a binary sort tree creation, in-order traversal, insert, find and delete a binary sort tree nodes. This course is mainly the function of dynamic look-up table, through the binary search tree algorithm and binary list of storage structures. This course is designed to highlight the system design concept, overall design, each functional module design and implementation. Keywords: C Language， Data Structure， Dynamic， Binary Search Tree, Binary List 2 抽象数据类型动态查找表定义 ADT DynamicSearchTable{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素含有类型相同，可唯一标识数据元素的关键字。 数据关系R:数据元素同属一个集合。 基本操作P： InitDSTable(DT); 操作结果：构造一个空的动态查找表DT。 DestroyDSTable（DT）; 初始条件：动态查找表DT存在。 操作结果：销毁动态查找表DT。 SearchDSTable（DT，key）; 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空” 。 InsertDSTable（DT，e）; 初始条件：动态查找表DT存在，e为待插入的数据元素。 操作结果：若DT中不存在其关键字等于e的数据元素，则插入e到DT。 DeleteDSTable（DT，key）; 初始条件：动态查找表DT存在，key为和关键字类型相同的给定值。 操作结果：若DT中存在其关键字等于key的数据元素，则删除之。 InOrderTraverse(DT); 初始条件：动态查找表DT存在