下载文档原格式
数据结构-动态查找表⼀、动态查找的概念：动态查找表：表结构在查找过程中动态⽣成。
要求：对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回（或者删除之）；否则插⼊关键字等于key 的记录。
⼆、动态查找表1. 1. ⼆叉排序树的定义⼆叉排序树的定义（Binary Sort Tree或Binary Search Tree）：⼆叉排序树或者是⼀棵空树，或者是满⾜下列性质的⼆叉树：（1）若左⼦树不为空，则左⼦树上的所有结点的值（关键字）都⼩于根节点的值；（2）若右⼦树不为空，则右⼦树上的所有结点的值（关键字）都⼤于根节点的值；（3）左、右⼦树都分别为⼆叉排序树。
如下图15-1所⽰，该图中的树就是⼀棵⼆叉排序树。
任何⼀个⾮叶⼦结点的左⼦树上的结点值都⼩于根结点，右⼦树上的结点值都⼤于根结点的值。
图1中，⼆叉树的结点值中序遍历的结果为：3,12,24,37,45,53,61,78,90,100。
结论：若按中序遍历⼀棵⼆叉排序树，所得到的结点序列是⼀个递增序列。
1. 1. ⼆叉排序树（BST树）的查找思想BST树的查找思想:（1）⾸先将给定的K值与⼆叉排序树的根节点的关键字进⾏⽐较：若相等，则查找成功；（2）若给定的K值⼩于BST树的根节点的关键字：继续在该节点的左⼦树上进⾏查找；（3）若给定的K值⼤于BST树的根节点的关键字：继续在该节点的右⼦树上进⾏查找。
1. 2. ⼆叉排序树总结（1）查找过程与顺序结构有序表中的折半查找相似，查找效率⾼；（2）中序遍历此⼆叉树，将会得到⼀个关键字的有序序列（即实现了排序运算）；（3）如果查找不成功，能够⽅便地将被查元素插⼊到⼆叉树的叶⼦结点上，⽽且插⼊或删除时只需修改指针⽽不需移动元素。
三、红⿊树1. 1. 红⿊树的定义红⿊树（Red Black Tree）是⼀种⾃平衡⼆叉查找树，是在计算机科学中⽤到的⼀种数据结构，典型的⽤途是实现关联数组。
它是在1972年由Rudolf Bayer发明的，当时被称为平衡⼆叉B树（symmetric binary B-trees）。
查找-动态查找表-⼆叉排序树⽂字描述 ⼆叉排序树的定义 ⼜称⼆叉查找树，英⽂名为Binary Sort Tree, 简称BST。
它是这样⼀棵树：或者是⼀棵空树；或者是具有下列性质的⼆叉树：(1)若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值；(2)若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值；(3)它的左、右⼦树也分别是⼆叉排序树。
⼆叉排序树的查找 其查找过程和次优⼆叉树类似。
即当⼆叉排序树不为空时，⾸先将给定值和根结点的关键字⽐较，若相等，则查找成功，否则将依据给定值和根结点的关键字之间的⼤⼩关系，分别在左⼦树或右⼦树上继续进⾏查找。
⼆叉排序树的插⼊ 和次优查找树相对，次优查找树是⼀种静态查找表。
⽽⼆叉排序树是⼀种动态树表，其特点是，树的结构通常不是⼀次⽣成的，⽽是在查找过程中，当树中不存在关键字等于给定值的结点时再进⾏插⼊。
新插⼊的结点⼀定是⼀个新添加的叶⼦结点，并且是查找不成功时查找路径上访问的最后⼀个结点的左孩⼦或右孩⼦结点。
⼆叉排序树的删除 在⼆叉排序树上删除⼀个结点相当于删除有序序列中的⼀个纪录，只要在删除某个结点之后依旧保持⼆叉排序树的特性即可。
假设被删除结点*p(指向结点的指针为p)，其双亲结点*f(结点类型为f)，且不失⼀般性，可设*p是*f的左孩⼦。
下⾯分3种情况进⾏讨论： (1)若*p结点为叶⼦结点，即PL和PR均为空树。
由于删除叶⼦结点*p不破坏整棵树的结构，则只需修改其双亲结点的指针即可。
(2)若*p结点只有左⼦树PL或只有右⼦树PR，此书只要令PL或PR直接成为其双亲结点*f的左⼦树即可。
(3)若*p结点的左⼦树和右⼦树均不为空。
从下图知，在删除*p之前，中序遍历该⼆叉树的序列为{…C L C…Q L QS L SPP R F…}, 在删除*p 之后，为保持其他元素之间的相对位置不变，可以有两种⽅法：[3.1]令*p的左⼦树为*f的左⼦树，⽽*p的右⼦树为*s的右⼦树。
动态查找表的几种查找方法动态查找表是计算机科学中常用的数据结构，用于在大量数据中高效地查找目标值。
动态查找表的查找方法有多种，包括线性查找、二分查找、哈希查找和二叉查找树等。
本文将对这几种查找方法进行详细介绍。
一、线性查找线性查找是最简单的查找方法之一，它逐个比较待查找元素和数据集中的每个元素，直到找到目标值或遍历完整个数据集。
线性查找的时间复杂度为O(n)，其中n为数据集的大小。
二、二分查找二分查找是一种高效的查找方法，前提是数据集必须是有序的。
它通过将数据集分成两部分，并与目标值进行比较，从而确定目标值在哪一部分中，然后在该部分中继续进行二分查找。
二分查找的时间复杂度为O(log n)，其中n为数据集的大小。
三、哈希查找哈希查找是一种基于哈希表的查找方法，它通过将目标值经过哈希函数转换成一个索引，然后在哈希表中查找该索引对应的值。
哈希查找的时间复杂度为O(1)，即常数时间。
然而，哈希查找的效率受到哈希函数和哈希冲突的影响，如果存在大量的哈希冲突，查找效率会降低。
四、二叉查找树二叉查找树（Binary Search Tree，简称BST）是一种基于二叉树的查找方法。
它具有以下特点：对于二叉查找树中的任意节点，其左子树中的所有节点值都小于它的值，右子树中的所有节点值都大于它的值。
通过比较目标值和当前节点的值，可以确定目标值在左子树还是右子树中，从而实现查找操作。
二叉查找树的平均时间复杂度为O(log n)，其中n为二叉查找树中节点的个数。
以上是动态查找表的几种常见的查找方法，每种方法都有其适用的场景和优劣势。
在选择查找方法时，需要根据具体的需求和数据特点来进行选择。
如果数据集较小且无序，线性查找可能是一种较好的选择；如果数据集有序，二分查找是一种高效的方法；如果对查找速度要求很高，可以考虑使用哈希查找；如果需要频繁进行插入和删除操作，并且希望保持数据有序，可以选择二叉查找树。
除了以上介绍的几种查找方法，还有其他一些常见的动态查找表，如平衡二叉树、红黑树、B树等。
北京理工大学珠海学院计算机学院课程设计动态查找表摘要数据结构是研究与数据之间的关系我们称这一关系为数据的逻辑结构简称数据结构。
当数据的逻辑结构确定以后数据在物理空间中的存储方式称为数据的存储结构。
相同的逻辑结构可以具有不同的存储结构因而有不同的算法。
本次课程设计程序中的数据采用“树形结构”作为其数据结构。
具体采用的是“二叉排序树”并且使用“二叉链表”来作为其存储结构。
本课程设计实现了二叉排序树的创建、中序遍历、插入、查找和删除二叉排序树中某个结点。
本课程主要实现动态查找表的功能通过“二叉排序树”的算法和“二叉链表”的存储结构来实现。
本课程设计说明书重点介绍了系统的设计思路、总体设计、各个功能模块的设计与实现方法。
关键词数据结构 C语言二叉排序树动态二叉链表12目录摘要 (1)1ABSTRACT (3)23抽象数据类型动态查找表定义 (4)43 系统总体分析 (5)3.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)附录 (20)21 Abstract(摘要)Data structure is the relationship between research and data, we callthis relationship as a logical data structure, referred to as datastructures. When the data logical structure is determined, the data storedin the physical space, is known as the data storage structure. The samelogical structure can have different storage structure, which has adifferent algorithm.The curriculum design, program data is "tree" as its data structure.Specific uses "binary sort tree" and use "binary list" as its storagestructure. 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, throughthe "binary search tree" algorithm and "binary list" of storage structures.This course is designed to highlight the system design concept, overalldesign, each functional module design and implementation.Keywords: C Language Data Structure Dynamic Binary Search Tree,Binary List32 抽象数据类型动态查找表定义ADT DynamicSearchTable{数据对象D D是具有相同特性的数据元素的集合。
各个数据元素含有类型相同可唯一标识数据元素的关键字。
数据关系R:数据元素同属一个集合。
基本操作PInitDSTable(&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存在。
操作结果按中序的次序输出DT中的每个结点数据值。
}ADT DynamisSearchTable453 系统总体分析3.1系统模块划分二叉排序树是一种动态树表。
二叉排序树的定义二叉排序树或者是一棵空树或者是一棵具有如下性质的二叉树⑴若它的左子树非空则左子树上所有结点的值均小于根结点的值⑵若它的右子树非空则右子树上所有结点的值均大于根结点的值⑶左、右子树本身又各是一棵二叉排序树。
3.2 二叉树的生成过程二叉排序树的生成采用递归方式的边查找边插入的方式。
如图3.3 主要功能模块设计程序主要设计了五个功能首先是创建二叉排序树完成后出现任务菜单菜单中设计了六个模块查找删除插入中序输出清屏和退出。
5图2.3 主函数流程图3.4 系统详细设计3.4.1 主函数菜单模块该模块功能主要是给用户提供清晰的可操作界面易于人机操作并能很好的调用其他各模块使程序更加优化丝路更加清晰结构更加明了提高了程序的实用性。
其代码如下#include "BinaryTree.h"void main(){BiTree T = NULL;int arr[100];int n, i, k;int data;InitBiTree(T);printf("请输入结点数");scanf("%d", &n);printf("请输入数据");for(i = 0; i < n; i++){//输入要排序的数据scanf("%d", &arr[i]);}for(i = 0; i < n; i++){//构造二叉排序树InsertBiTree(T,arr[i]);}printf("按中序输出");InOrderTraverse(T); //调用中序输出函数将二叉排序树按中序输出printf("\n");Z:{//语句块供用户选择操作7printf("\t\t---------------------------\n");printf("\t\t| 功能菜单|\n");printf("\t\t---------------------------\n");printf("\t\t| 1.查找数据|\n");printf("\t\t---------------------------\n");printf("\t\t| 2.删除数据|\n");printf("\t\t---------------------------\n");printf("\t\t| 3.插入数据|\n");printf("\t\t---------------------------\n");printf("\t\t| 4.输出有序序列|\n");printf("\t\t---------------------------\n");printf("\t\t| 5.清屏|\n");printf("\t\t---------------------------\n");printf("\t\t| 6.退出|\n");printf("\t\t---------------------------\n\n");X:{//该语句块用于循环选择printf("请输入选择功能的序号");V:{//该语句块用于输入序号错误时重新输入scanf("%d", &k);}//end Vswitch(k){case 1:printf("请输入要查找的数据");scanf("%d", &data);if(InsertBiTree(T, data)){printf("不存在数据元素%d\n", data);}else{8printf("存在数据元素%d\n", data);}break;case 2:printf("请输入要删除的数据");scanf("%d", &data);if(!DeleteBiTree(T, data)){printf("不存在要输出的数据%d\n", data);}else{printf("删除操作成功\n");}break;case 3:printf("请输入要插入的数据");scanf("%d", &data);if(!InsertBiTree(T, data)){printf("要插入的数据%d已存在插入失败\n", data);}else{printf("插入操作成功\n");}break;case 4:printf("有序序列为");InOrderTraverse(T);printf("\n");break;case 5:system("cls");910goto Z;break;case 6:DestroyBiTree(T);exit(0);default:printf("输入字符错误请重新输入:");goto V;}//end switchprintf("\n\n");}//end Xgoto X;}//end Z}图2.4.13.4.2 查找模块该模块是给用户提供查找功能。
