动态查找表(二叉排序树).doc

北京理工大学珠海学院计算机学院课程设计 动态查找表 摘 要 数据结构是研究与数据之间的关系我们称这一关系为数据的逻辑结构简称数据结构。当数据的逻辑结构确定以后数据在物理空间中的存储方式称为数据的存储结构。相同的逻辑结构可以具有不同的存储结构因而有不同的算法。 本次课程设计程序中的数据采用“树形结构”作为其数据结构。具体采用的是“二叉排序树”并且使用“二叉链表”来作为其存储结构。本课程设计实现了二叉排序树的创建、中序遍历、插入、查找和删除二叉排序树中某个结点。 本课程主要实现动态查找表的功能通过“二叉排序树”的算法和“二叉链表”的存储结构来实现。本课程设计说明书重点介绍了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词数据结构 C语言 二叉排序树 动态 二叉链表1北京理工大学珠海学院计算机学院课程设计 2目 录 摘 要. 1 1 ABSTRACT. 323 抽象数据类型动态查找表定义 . 4 43 系统总体分析. 53.1系统模块划分 . 5 3.2 二叉树的生成过程 . 5 3.3 主要功能模块设计 . 5 3.4 系统详细设计 . 7 3.4.1 主函数菜单模块 . 7 3.4.2 查找模块 . 10 3.4.3 删除模块 . 11 3.4.4 插入模块 . 13 3.4.5 中序输出模块 . 15 参考文献. 17 心 得 体 会. 18 教 师 评 语. 19 附 录. 202北京理工大学珠海学院计算机学院课程设计 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 3北京理工大学珠海学院计算机学院课程设计 2 抽象数据类型动态查找表定义 ADT DynamicSearchTable 数据对象DD是具有相同特性的数据元素的集合。各个数据元素含有类型相同可唯一标识数据元素的关键字。 数据关系R:数据元素同属一个集合。 基本操作P InitDSTable(&DT); 操作结果构造一个空的动态查找表DT。 DestroyDSTable&DT; 初始条件动态查找表DT存在。 操作结果销毁动态查找表DT。 SearchDSTableDTkey; 初始条件动态查找表DT存在key为和关键字类型相同的给定值。 操作结果若DT中存在其关键字等于key的数据元素则函数值为该元素的值或在表中的位置否则为“空” 。 InsertDSTable&DTe; 初始条件动态查找表DT存在e为待插入的数据元素。 操作结果若DT中不存在其关键字等于e的数据元素则插入e到DT。 DeleteDSTable&DTkey; 初始条件动态查找表DT存在key为和关键字类型相同的给定值。 操作结果若DT中存在其关键字等于key的数据元素则删除之。 InOrderTraverse(DT); 初始条件动态查找表DT存在。 操作结果按中序的次序输出DT中的每个结点数据值。 ADT DynamisSearchTable 4北京理工大学珠海学院计算机学院课程设计 5 3 系统总体分析 3.1系统模块划分 二叉排序树是一种动态树表。 二叉排序树的定义二叉排序树或者是一棵空树 或者是一棵具有如下性质的二叉树 若它的左子树非空则左子树上所有结点的值均小于根结点的值 若它的右子树非空则右子树上所有结点的值均大于根结点的值 左、右子树本身又各是一棵二叉排序树。 3.2 二叉树的生成过程 二叉排序树的生成采用递归方式的边查找边插入的方式。如图 3.3 主要功能模块设计 程序主要设计了五个功能首先是创建二叉排序树完成后出现任务菜单菜单中设计了六个模块查找删除插入中序输出清屏和退出。5北京理工大学珠海学院计算机学院课程设计 创建二叉排序树N查找数据Switch(1) Y N删除数据Switch(2) Y NSwitch(3)插入数据 Y N中序输出Switch(4) YSwitch(5) N清屏 Y NSwitch(6)退出 Y N输出错误default Y N图2.3 主函数流程图北京理工大学珠海学院计算机学院课程设计 3.4 系统详细设计 3.4.1 主函数菜单模块 该模块功能主要是给用户提供清晰的可操作界面易于人机操作并能很好的调用其他各模块使程序更加优化丝路更加清晰结构更加明了提高了程序的实用性。其代码如下 #include BinaryTree.h void main() BiTree T = NULL; int arr100; int n, i, k; int data; InitBiTree(T); printf(请输入结点数); scanf(%d, &n); printf(请输入数据); for(i = 0; i n; i+) /输入要排序的数据 scanf(%d, &arri); for(i = 0; i data) p = T; return TRUE; /查找成功 else if(key data) /在左子树中继续查找 return (SearchBiTree(T-left, key, T, p); else /在右子树中继续查找 return (SearchBiTree(T-right, key, T, p); 图2.4.23.4.3 删除模块 删除结点函数采用边查找边删除的方式。如果没有查找到则不对树做任何的修改；如果查找到结点则分四种情况分别进行讨论 A该结点左右子树均为空可以直接进行删除 B该结点仅左子树为空右子树不为空用右子树的根结点取代被删除结点的位置 C该结点仅右子树为空左子树不为空 D该结点左右子树均不为空找到被删除结点左子树中最大的结点并用该结点取代被删除节点的位置。其代码如下 Status Delete(BiTree &p) /从二叉排序树中删除结点p并重接它的左或右子树 BiTree q, s; /q = (BiTree)malloc(sizeof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p-right) /右子树为空则重接它的左子树 q = p; p = p-left; q-left = NULL; / free(q); 有错误 else if(!p-left) /只需重接它的右子树 q = p; p = p-right; q-right = NULL; / free(q); /有错误 else /左右子树都不空 q = p; s = p-left; while(s-right) q = s; s = s-right; /转右然后向右走到尽头找到被删点的“前驱” p-data = s-data; /s指向被删结点的“前驱” s-data = NULL; if(q != p) q-right = s-left; /重接*q的右子树 else q-left = s-left; /重接*q的左子树任何的修改如果查找到结点则分四种情况分别进行讨论 A该结点左右子树均为空可以直接进行删除 B该结点仅左子树为空右子树不为空用右子树的根结点取代被删除结点的位置 C该结点仅右子树为空左子树不为空 D该结点左右子树均不为空找到被删除结点左子树中最大的结点并用该结点取代被删除节点的位置。其代码如下 Status Delete(BiTree &p) /从二叉排序树中删除结点p并重接它的左或右子树 BiTree q, s; /q = (BiTree)malloc(sizeof(BiTree); /s = (BiTree)malloc(sizeof(BiTree); if(!p-right) /右子树为空则重接它的左子树 q = p; p = p-left; q-left = NULL; / free(q); 有错误 else if(!p-left) /只需重接它的右子树 q = p; p = p-right; q-right = NULL; / free(q); /有错误 else /左右子树都不空 q = p; s = p-left; while(s-right) q = s; s = s-right; /转右然后向右走到尽头找到被删点的“前驱” p-data = s-data; /s指向被删结点的“前驱” s-data = NULL; if(q != p) q-right = s-left; /重接*q的右子树 else q-left = s-left; /重接*q的左子树/ free(s); 有错误 return TRUE; Status DeleteBiTree(BiTree &T, Elem key) /若二叉排序树T中存在关键字等于key的数据元素时 /则删除该数据元素结点并返回TRUE否则返回FALSE if(!T) return FALSE; /不存在关键字等于key的数据元素 else if(key = T-data) return Delete(T); /找到关键字等于key的数据元素 else if(key data) /从左子树继续查找等于key的数据元素 return DeleteBiTree(T-left, key); else /从右子树继续查找等于key的数据元素 return DeleteBiTree(T-right,key); 图2.4.33.4.4 插入模块 在二叉排序树种插入新结点要保证插入后的二叉树仍符合二叉排序树的定义。插入过程若二叉排序树为空则待插入结点*p作为根结点插入到空树中当非空时将待插结点关键字p-item和树根关键字t-item进行比较若p-item=t-item则无须插入若p-itemitem则插入到根的左子树中若p-itemt-item则插入到根的右子树中。而子树种的插入过程和在树中的插入过程相同如此进行下去直到把结点*p作为一个新的树叶插入到二叉排序树中或者直到发现数已有相同关键字的结点为止。其代码如下 Status InsertBiTree(BiTree &T, Elem key) /当二叉排序树T中不存在关键字等于key的数据元素时插入key并返回TRUE /否则返回FALSE BiTree s = NULL; BiTree p = NULL; if(!SearchBiTree(T, key, NULL, p) s = (BiTree)malloc(sizeof(BiTree); if(!s) /内存分配失败时给出提示然后退出操作 printf(内存空间分配失败n); exit(OVERFLOW); s-data = key; s-left = s-right = NULL; if(!p) T = s; else if(key data) p-left = s; else p-right = s; return TRUE; else return FALSE; 图2.4.4 3.4.5 中序输出模块 遍历Traversal是指沿着某条搜索路线依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。二叉树共有三个部分组成即根结点根结点的左子树根结点的右子树。限定以从左至右方式共有三种遍历方式即前序遍历中序遍历后序遍历。中序遍历的原则若被遍历的二叉树为非空则依次执行如下操作 A以中序遍历方式遍历左子树 B访问根结点 C以中序遍历方式遍历右子树。其代码如下 Status InsertBiTree(BiTree &T, Elem key) /当二叉排序树T中不存在关键字等于key的数据元素时插入key并返回TRUE /否则返回FALSE BiTree s = NULL; BiTree p = NULL; if(!SearchBiTree(T, key, NULL, p) s = (BiTree)malloc(sizeof(BiTree); if(!s) /内存分配失败时给出提示然后退出操作printf(内存空间分配失败n); exit(OVERFLOW); s-data = key; s-left = s-right = NULL; if(!p) T = s; else i