数据结构(C语言版) 查找表 详细举例介绍

1、 查找表是由同一类型的数据元查找表是由同一类型的数据元素素(或记录或记录)构成的集合。构成的集合。 由于由于“集合集合”中的数据元素之间中的数据元素之间存在着松散的关系，因此查找表是一存在着松散的关系，因此查找表是一种应用灵便的结构。种应用灵便的结构。何谓查找表 ？对查找表经常进行的对查找表经常进行的操作操作: :1. 查询查询某个某个“特定的特定的”数据元素是否数据元素是否在查找表中；在查找表中；2. 检索检索某个某个“特定的特定的”数据元素的各数据元素的各种属性；种属性；3. 在查找表中在查找表中插入插入一个数据元素；一个数据元素；4. 从查找表中从查找表中删去删去某个数据元素。某个数据元

2、素。仅作仅作查询查询和和检索检索操作的查找表。操作的查找表。有时在查询之后，还需要将有时在查询之后，还需要将“查询查询”结结果为果为“不在查找表中不在查找表中”的数据元素的数据元素插入插入到到查找表中；或者，从查找表中查找表中；或者，从查找表中删除删除其其“查询查询”结果为结果为“在查找表中在查找表中”的数据的数据元素。元素。查找表可分为两类查找表可分为两类:是数据元素（或记录）中某个是数据元素（或记录）中某个数据项数据项的值，用以的值，用以标识标识（识别）一个数据元（识别）一个数据元素（或记录）。素（或记录）。 若此关键字可以识别若此关键字可以识别唯一的唯一的一个记一个记录，则称之谓录，则称

3、之谓 若此关键字能识别若此关键字能识别若干若干记录，则称记录，则称之谓之谓 根据给定的某个值，在查找表中根据给定的某个值，在查找表中确定一确定一个其关键字等于给定值的数据元素或（记个其关键字等于给定值的数据元素或（记录）录） 查找查找 若查找表中存在这样一个记录，则称若查找表中存在这样一个记录，则称“查找成功查找成功”，查找结果：，查找结果：给出整个记录给出整个记录的信息，或指示该记录在查找表中的位置的信息，或指示该记录在查找表中的位置； 否则称否则称“查找不成功查找不成功”，查找结果：，查找结果：给给出出“空记录空记录”或或“空指针空指针”。 由于查找表中的数据元素之间不存由于查找表中的数据

4、元素之间不存在明显的组织规律，因此不便于查找。在明显的组织规律，因此不便于查找。 为了提高查找的效率，为了提高查找的效率， 需要在查找需要在查找表中的元素之间人为地表中的元素之间人为地 附加某种确定的附加某种确定的关系，换句话说，关系，换句话说， 用另外一种结构来表用另外一种结构来表示查找表示查找表。查找的方法取决于查找表的结构。查找的方法取决于查找表的结构。如何进行查找？如何进行查找？9.1 静态查找表静态查找表9.2 动态查找树表动态查找树表9.3 哈希表哈希表数据对象数据对象D：数据关系数据关系R：D是具有相同特性的数是具有相同特性的数据元素的集合。据元素的集合。每个数每个数据元素含有类

5、型相同的据元素含有类型相同的关键字，可唯一标识数关键字，可唯一标识数据元素。据元素。 数据元素同属一个集合。数据元素同属一个集合。ADT StaticSearchTable Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作基本操作 P：next ADT StaticSearchTable构造一个含构造一个含n个数据元素个数据元素的静态查找表的静态查找表ST。 Create(&ST, n);操作结果：操作结果：销毁表销毁表ST。Destroy(&ST);初始条件：初始条件：操作结果：操作结果：静态查找表静态

6、查找表ST存在；存在；若若 ST 中存在其关键字等于中存在其关键字等于 key 的数据元素，则函数值的数据元素，则函数值为该元素的值或在表中的位为该元素的值或在表中的位置，否则为置，否则为“空空”。 Search(ST, key);初始条件：初始条件：操作结果：操作结果：静态查找表静态查找表ST存在，存在，key 为为和查找表中元素的关键字类和查找表中元素的关键字类型相同的给定值；型相同的给定值；按某种次序对按某种次序对ST的每个元的每个元素调用函数素调用函数Visit()一次且一次且仅一次，一旦仅一次，一旦Visit()失败，失败，则操作失败。则操作失败。Traverse(ST, Visit

7、();初始条件：初始条件：操作结果：操作结果：静态查找表静态查找表ST存在，存在，Visit是对元素操作的应用函数；是对元素操作的应用函数；typedef struct / 数据元素存储空间基址，建表时数据元素存储空间基址，建表时 / 按实际长度分配，按实际长度分配，0号单元留空号单元留空 int length; / 表的长度表的长度 SSTable;假设静态查找表的假设静态查找表的顺序存储结构顺序存储结构为为ElemType *elem;数据元素类型的定义为数据元素类型的定义为:typedef struct keyType key; / 关键字域关键字域 / 其它属性域其它属性域 ElemT

8、ype ; , TElemType ; 以顺序表或线性链表以顺序表或线性链表表示静态查找表表示静态查找表一、顺序查找表一、顺序查找表21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elem回顾顺序表的查找过程：回顾顺序表的查找过程：假设给定值假设给定值 e=64,要求要求 ST.elemk = e, 问问: k = ?kkint Location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType) k = 1; p = L.ele

9、m; while ( k=L.length & compare(*p+,e) k+; if ( k= L.length) return k; else return 0;21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.LengthST.elemi60ikey=64key=60i64int Search_Seq(SSTable ST, KeyType key) / 在顺序

10、表在顺序表ST中顺序查找其关键字等于中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找从后往前找 return i; / 找不到时，找不到时，i为为0 定义：定义： 查找算法的查找算法的平均查找长度平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值为确定记录在查找表中的位置，需和给定值

11、 进行比较的关键字个数的期望值进行比较的关键字个数的期望值 其中其中: n 为表长，为表长，Pi 为查找表中第为查找表中第i个记录的概率，个记录的概率， 且且 Ci为找到该记录时，曾为找到该记录时，曾和给定值和给定值 比较过的关键字的个数。比较过的关键字的个数。分析顺序查找的时间性能。分析顺序查找的时间性能。niiiCPASL111niiP在在等概率等概率查找的情况下，查找的情况下， 顺序表查找的平均查找长度顺序表查找的平均查找长度为：为：对对顺序表顺序表而言，而言，Ci = n-i+1nPi121111n)i(nnASLnissASL = nP1 +(n-1)P2 + +2Pn-1+Pn 若

12、查找概率无法事先测定，则查若查找概率无法事先测定，则查找过程采取的改进办法是，找过程采取的改进办法是，在每次查找在每次查找之后，将刚刚查找到的记录直接移至表之后，将刚刚查找到的记录直接移至表尾的位置上尾的位置上。在在不等概率查找不等概率查找的情况下，的情况下，ASLss 在在 PnPn-1P2P1时时取极小值取极小值 上述顺序查找表的查找算法简上述顺序查找表的查找算法简单，单， 但平均查找长度较大，特别不但平均查找长度较大，特别不适用于表长较大的查找表。适用于表长较大的查找表。 若以若以有序表有序表表示静态查找表，则表示静态查找表，则查找过程可以基于查找过程可以基于“折半折半”进行。进行。二、

13、有序查找表二、有序查找表05 13 19 21 37 56 64 75 80 88 92 0 1 2 3 4 5 6 7 8 9 10 11 ST.elemST.length例如例如: key=64 的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值置区间初值 while (low 50时，可得近似结果时，可得近似结果 一般情况下，

14、表长为一般情况下，表长为 n 的折半查找的折半查找的判定树的深度和含有的判定树的深度和含有 n 个结点的完全个结点的完全二叉树的深度相同。二叉树的深度相同。1) 1(log12112111nnnjnCnASLhjjniibs1) 1(log2nASLbs关键字关键字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3 在不等概率查找在不等概率查找的情况下，折半查找的情况下，折半查找不是不是有序表最好的查找方法有序表最好的查找方法例如例如:此时此时 ASL=2 0.2+3 0.3+1 0.05+2 0.3+3 0.15=2.4若改变若改变Ci的值

15、的值 2 1 3 2 3则则 ASL=2 0.2+1 0.3+3 0.05+2 0.3+3 0.15=1.9三、静态查找树表三、静态查找树表 使使 达最小的判定树称为达最小的判定树称为最优二叉树最优二叉树，其中其中: 111niiCiqniiCipASL1111niiniiqp定义定义:为计算方便，令为计算方便，令 wi = pi选择二叉树的根结点，选择二叉树的根结点，使使 达最小达最小 111ijjhijjiwwP11)(iilhiswswswswP介绍一种介绍一种次优二叉树次优二叉树的构造方法的构造方法:为便于计算，引入累计权值和为便于计算，引入累计权值和 并设并设 wl-1 = 0 和和

16、 swl-1 = 0，则推导可得则推导可得ijjiwsw1j01234567wj02153435swjpjkeyA B C D E F G023811 15 18 23例如例如:lh21 18 124310 18h9608EC21Ah53lhG3013ECGABDF所得次优二叉树如下所示所得次优二叉树如下所示: 查找比较查找比较“总次数总次数” = 3 2+4 1+2 5+3 3 +1 4+3 3+2 5 = 52 查找比较查找比较“总次数总次数” = 3 2+2 1+3 5+1 3 +3 4+2 3+3 5 = 59和折半查找相比较和折半查找相比较DBACFEGStatus SecondOp

17、timal(BiTree &T, ElemType R, float sw, int low, int high) / 由有序表由有序表Rlow.high及其累计权值表及其累计权值表sw / 递归构造次优查找树递归构造次优查找树T。 选择最小的选择最小的Pi值值 if (!(T = (BiTree)malloc(sizeof(BiTNode) return ERROR; T-data = Ri; / 生成结点生成结点if (i=low) T-lchild = NULL; / 左子树空左子树空else SecondOptimal(T-lchild, R, sw, low, i-1); / 构造左

18、子树构造左子树 if (i=high) T-rchild = NULL; / 右子树空右子树空 else SecondOptimal(T-rchild, R, sw, i+1, high); / 构造右子树构造右子树 return OK; / SecondOptimal次优查找树采用二叉链表的存储结构次优查找树采用二叉链表的存储结构Status CreateSOSTre(SOSTree &T, SSTable ST) / 由有序表由有序表 ST 构造一棵次优查找树构造一棵次优查找树 T。 / ST 的数据元素含有权域的数据元素含有权域 weight if (ST.length = 0) T =

19、 NULL; else FindSW(sw, ST); / 按照有序表按照有序表 ST 中各数据元素中各数据元素 / 的的 weight 值求累计权值表值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); return OK; / CreatSOSTree四、索引顺序表四、索引顺序表以索引顺序表表示静态查找表，以索引顺序表表示静态查找表，searchsearch操作可用分块查找来实现。操作可用分块查找来实现。分块查找又称索引顺序查找，这是分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查顺序查找的一种改进方法。在此查找方法中，除表本

20、身以外，尚需建找方法中，除表本身以外，尚需建立一个立一个“索引表索引表”。例如例如 表中含有表中含有18个元素，可分成三个子表。个元素，可分成三个子表。对每个子表（或称块）建立一个索引项，对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该其中包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表内的最大关键字）和项指针（指示该子表的第一个元素在表中位置）。子表的第一个元素在表中位置）。索引表索引表最大关键字最大关键字起始地址起始地址 22 48 8617 13221213 8 9 20334244382448605874498653 索引表按关键字有序，

21、故表或索引表按关键字有序，故表或者有序，或者分块有序。所谓者有序，或者分块有序。所谓“分分块有序块有序” 是指一个子表中所有元素是指一个子表中所有元素的关键字均大于前一个子表的最大的关键字均大于前一个子表的最大关键字。关键字。 1）由索引确定记录所在区间；）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。注意：索引可以根据查找表的特点来构造。可见，可见， 索引顺序查找索引顺序查找的过程也是一个的过程也是一个“缩小区间缩小区间”的查找过程。的查找过程。索引顺序查找的平均查找长度索引顺序查找的平均查找长度 = 查找查找

22、“索引索引”的平均查找长度的平均查找长度 + 查找查找“顺序表顺序表”的平均查找长度的平均查找长度 (n) (1) (n) (1) (nlogn)综合上一节讨论的几种查找表的特性：综合上一节讨论的几种查找表的特性：查找查找 插入插入 删除删除无序顺序表无序顺序表 无序线性链表无序线性链表有序顺序表有序顺序表 有序线性链表有序线性链表 静态查找树表静态查找树表 (n) (n) (logn) (n) (logn) (1) (1) (n) (1) (nlogn)1）从）从查找查找性能看，最好情况能达性能看，最好情况能达 (logn)，此时要求表，此时要求表有序有序；2）从）从插入插入和和删除删除的性

23、能看，最好的性能看，最好 情况能达情况能达 (1)，此时要求存储，此时要求存储 结构是结构是链表链表。ADT DynamicSearchTable 抽象数据类型抽象数据类型动态查找表动态查找表的定义如下：的定义如下：数据对象数据对象D：数据关系数据关系R： 数据元素同属一个集合。数据元素同属一个集合。D是具有相同特性的数据是具有相同特性的数据元素的集合。元素的集合。每个数据元素含有类型相每个数据元素含有类型相同的关键字，同的关键字， 可唯一标可唯一标识数据元素。识数据元素。InitDSTable(&DT)基本操作基本操作P：DestroyDSTable(&DT)SearchDSTable(DT

24、, key);InsertDSTable(&DT, e);DeleteDSTable(&T, key);TraverseDSTable(DT, Visit();nextADT DynamicSearchTable操作结果：操作结果：构造一个空的动态查找表构造一个空的动态查找表DT。InitDSTable(&DT);销毁动态查找表销毁动态查找表DT。DestroyDSTable(&DT);初始条件：初始条件： 操作结果：操作结果：动态查找表动态查找表DT存在；存在；若若DT中存在其关键字等于中存在其关键字等于 key的数据元素，则函数值的数据元素，则函数值为该元素的值或在表中的位为该元素的值或在

25、表中的位置，否则为置，否则为“空空”。SearchDSTable(DT, key);初始条件：初始条件：操作结果：操作结果：动态查找表动态查找表DT存在，存在，key为和关键字类型相同的给为和关键字类型相同的给定值；定值；动态查找表动态查找表DT存在，存在， e 为待插入的数据元素；为待插入的数据元素；InsertDSTable(&DT, e);初始条件：初始条件：操作结果：操作结果：若若DT中不存在其关键字中不存在其关键字等于等于 e.key 的的 数据元素，数据元素，则插入则插入 e 到到DT。动态查找表动态查找表DT存在，存在，key为和关键字类型相同的给为和关键字类型相同的给定值；定值

26、；DeleteDSTable(&T, key);初始条件：初始条件：操作结果：操作结果：若若DT中存在其关键字等中存在其关键字等于于key的数据元素，则删的数据元素，则删除之。除之。动态查找表动态查找表DT存在，存在，Visit是对结点操作的应用函数；是对结点操作的应用函数；TraverseDSTable(DT, Visit();初始条件：初始条件：操作结果：操作结果：按某种次序对按某种次序对DT的每个结的每个结点调用函数点调用函数 Visit() 一次且至一次且至多一次。一旦多一次。一旦 Visit() 失败，失败，则操作失败。则操作失败。一、二叉排序树（二叉查找树）一、二叉排序树（二叉查找

27、树）二、二叉平衡树二、二叉平衡树三、三、B - 树树四、四、B+树树五、键五、键 树树1定义定义2查找算法查找算法3插入算法插入算法4删除算法删除算法5查找性能的分析查找性能的分析一、二叉排序树（二叉查找树）（1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上 所有所有结点的值结点的值均小于均小于根结点的值；根结点的值； 二叉排序树二叉排序树或者是一棵空树；或者或者是一棵空树；或者是具有如下特性的二叉树：是具有如下特性的二叉树：（3）它的左、右子树）它的左、右子树也都也都分别分别是二叉是二叉 排序树排序树。（2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上 所有所有结

28、点的值结点的值均大于均大于根结点的值；根结点的值；1 1定义：定义：503080209010854035252388例如例如:是二叉排序树是二叉排序树66不不 通常，取二叉链表作为通常，取二叉链表作为二叉排序树的存储结构二叉排序树的存储结构typedef struct BiTNode / 结点结构结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;TElemType data; 1）若给定值）若给定值等于等于根结点的关键字，根结点的关键字，则查找成功；则查找成功； 2）若给定值）若给定值小于小于根结点的关键

29、字，根结点的关键字，则继续在左子树上进行查找；则继续在左子树上进行查找； 3）若给定值）若给定值大于大于根结点的关键字，根结点的关键字，则继续在右子树上进行查找。则继续在右子树上进行查找。否则否则若二叉排序树若二叉排序树为空为空，则查找不成功；，则查找不成功；50308020908540358832例如例如:二叉排序树二叉排序树查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 从上述查找过程可见，从上述查找过程可见，在查找过程中，生成了一条在查找过程中，生成了一条查找路径查找路径: 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层

30、向下直至关键字等于给定值的结点逐层向下直至关键字等于给定值的结点;或者或者 从根结点出发，沿着左分支或右分支从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。逐层向下直至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功算法描述如下：算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指针在根指针 T 所指二叉排序树中递归地查找其所指二叉排序树中递归地查找其 / 关键字等于关键字等于 key 的数据元素，若的数据元素，若查找成功查找成功， / 则返回指针则返回指针 p 指向该数据

31、元素的结点，并返回指向该数据元素的结点，并返回 / 函数值为函数值为 TRUE; / SearchBST 否则表明否则表明查找不成功查找不成功，返回，返回 / 指针指针 p 指向查找路径上访问的最后一个结点，指向查找路径上访问的最后一个结点， / 并返回函数值为并返回函数值为FALSE, 指针指针 f 指向当前访问指向当前访问 / 的结点的双亲，其初始调用值为的结点的双亲，其初始调用值为NULLif (!T)else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else p = f; return FALSE; / 查找

32、不成功查找不成功 p = T; return TRUE; / 查找成功查找成功SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找在左子树中继续查找SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找在右子树中继续查找30201040352523fT设设 key = 48fTfT22pfTfTTTTfffp 根据动态查找表的定义，根据动态查找表的定义，“插入插入”操作在操作在查找不成功查找不成功时才进行时才进行; 若二叉排序树为空树，则新插入的若二叉排序树为空树，则新插入的结点为结点为新的根结点新的根结点；否则，新插入

33、；否则，新插入的结点必为一个的结点必为一个新的叶子结点新的叶子结点，其，其插入位置由查找过程得到。插入位置由查找过程得到。Status Insert BST(BiTree &T, ElemType e) / 当二叉排序树中不存在关键字等于当二叉排序树中不存在关键字等于 e.key 的的 / 数据元素时，插入元素值为数据元素时，插入元素值为 e 的结点，并返的结点，并返 / 回回 TRUE; 否则，不进行插入并返回否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p ) else return FALSE; / Insert BST s = (B

34、iTree) malloc (sizeof (BiTNode); / 为新结点分配空间为新结点分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p ) T = s; / 插入插入 s 为新的根结点为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入插入 *s 为为 *p 的左孩子的左孩子else p-rchild = s; / 插入插入 *s 为为 *p 的右孩子的右孩子return TRUE; / 插入成功插入成功（1）被删除的结点）被删除的结点是叶子是叶子；（2）被删除的结点）

35、被删除的结点只有左子树只有左子树或者或者只有右子树只有右子树；（3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树。可分可分三种情况三种情况讨论：讨论： 和插入相反，删除在和插入相反，删除在查找成功查找成功之后进行，并之后进行，并且要求在删除二叉排序树上某个结点之后，且要求在删除二叉排序树上某个结点之后，仍仍然保持二叉排序树的特性然保持二叉排序树的特性。50308020908540358832（1）被删除的结点是）被删除的结点是叶子结点叶子结点例如例如:被删关键字被删关键字 = 2088其双亲结点中相应指针域的值改为其双亲结点中相应指针域的值改为“空空”50308020

36、908540358832（2）被删的结点）被删的结点只有左子树只有左子树或或只有右子树只有右子树 其双亲结点的相应指针域的值改为其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树指向被删除结点的左子树或右子树”。被删关键字被删关键字 = 408050308020908540358832（3）被删除的结点）被删除的结点既有左子树，也有右子树既有左子树，也有右子树4040以其前驱替代之，然以其前驱替代之，然后再删除该前驱结点后再删除该前驱结点被删结点被删结点前驱结点前驱结点被删关键字被删关键字 = 50以中序遍历排好，20-30-32-35-40-50-80-85-88-90Stat

37、us DeleteBST (BiTree &T, KeyType key ) / 若二叉排序树若二叉排序树 T 中存在其关键字等于中存在其关键字等于 key 的的 / 数据元素，则删除该数据元素结点，并返回数据元素，则删除该数据元素结点，并返回 / 函数值函数值 TRUE，否则返回函数值，否则返回函数值 FALSE if (!T) return FALSE; / 不存在关键字等于key的数据元素 else / DeleteBST算法描述如下：算法描述如下： if ( EQ (key, T-data.key) ) / 找到关键字等于找到关键字等于key的数据元素的数据元素else if ( LT

38、 (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找继续在左子树中进行查找DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找继续在右子树中进行查找void Delete ( BiTree &p ) / 从从二叉排序树中删除结点二叉排序树中删除结点 p， / 并重接它的左子树或右子树并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete其中其中删除操作删除操作过程

39、如下所描述：过程如下所描述： / 右子树为空树则只需重接它的左子树右子树为空树则只需重接它的左子树q = p; p = p-lchild; free(q);pp此处p应该换为f的左孩子或右，根据p为f左还是右而定/ 左子树为空树只需重接它的右子树左子树为空树只需重接它的右子树q = p; p = p-rchild; free(q);ppq = p; s = p-lchild;while (!s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱指向被删结点的前驱/ 左右子树均不空左右子树均不空p-data = s-data;if (q != p ) q-rch

40、ild = s-lchild; else q-lchild = s-lchild; / 重接重接*q的左子树的左子树free(s);pqs 对于每一棵特定的二叉排序树，对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它均可按照平均查找长度的定义来求它的的 ASL 值，显然，由值相同的值，显然，由值相同的 n 个关个关键字，构造所得的不同形态的各棵二键字，构造所得的不同形态的各棵二叉排序树的平均查找长叉排序树的平均查找长 度的值不同，度的值不同，甚至可能差别很大。甚至可能差别很大。由关键字序列由关键字序列 3，1，2，5，4构造而得的二叉排序树构造而得的二叉排序树由关键字序列由关键字序

41、列 1，2，3，4，5构造而得的二叉排序树，构造而得的二叉排序树，2134535412ASL =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 下面讨论平均情况下面讨论平均情况: 不失一般性，假设长度为不失一般性，假设长度为 n 的序列中有的序列中有 k 个关键字个关键字小于小于第一个关键字，则必有第一个关键字，则必有 n-k-1 个关键字个关键字大于大于第一个关键字第一个关键字,由它构造的二由它构造的二叉排序树叉排序树n-k-1k的平均查找长度是的平均查找长度是 n 和和 k 的函数的函数P(n, k) ( 0 k n-1 ) 假设假设 n 个关键字可

42、能出现的个关键字可能出现的 n! 种排列种排列的可能性相同，则含的可能性相同，则含 n 个关键字的二叉排个关键字的二叉排序树的平均查找长度序树的平均查找长度10),(1)(nkknPnnPASLniiniiiCnCpknP111),(在在等概率查找等概率查找的情况下，的情况下，RiLirootniiCCCnCnknP11),(1)1)1()(1()1)(11knPknkPkn)1()1()(11knPknkPkn由此可类似于解差分方程，此递归方程有解：可类似于解差分方程，此递归方程有解：CnnnnPlog12)(10) 1() 1()(111)(nkknPknkPknnnP112)(21nkk

43、Pkn 何谓何谓“二叉平衡树二叉平衡树”？ 二叉平衡树的查找性能分析二叉平衡树的查找性能分析 如何构造如何构造“二叉平衡树二叉平衡树”二、二叉平衡树二、二叉平衡树 二叉平衡树二叉平衡树是二叉查找树的另一种形式，是二叉查找树的另一种形式，其特点为：其特点为： 树中每个结点的树中每个结点的左、右子树深度左、右子树深度之差的绝对值不大于之差的绝对值不大于1 。例如例如:1RLhh548254821是平衡树是平衡树不是平衡树不是平衡树 构造二叉平衡（查找）树的方法是：构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。例如例如:依次插入的关键字为依次插入的关

44、键字为5, 4, 2, 8, 6, 95424258665842向右旋转向右旋转一次一次先向右旋转先向右旋转再向左旋转再向左旋转426589642895向左旋转一次继续插入关键字继续插入关键字 9 在平衡树上进行查找的过程和二叉在平衡树上进行查找的过程和二叉排序树相同，因此，排序树相同，因此，查找过程中和给定查找过程中和给定值进行比较的关键字的个数不超过平衡值进行比较的关键字的个数不超过平衡 树的深度。树的深度。平衡树的查找性能分析：平衡树的查找性能分析： 问：含 n 个关键字的二叉平衡树可能达到的最大深度最大深度是多少？n = 0空树空树最大深度为最大深度为 0n = 1最大深度为最大深度为

45、 1n = 2最大深度为最大深度为 2n = 4最大深度为最大深度为 3n = 7最大深度为最大深度为 4先看几个具体情况:反过来问，反过来问，深度为深度为 h 的二叉平衡树中的二叉平衡树中所所含结点的最小值含结点的最小值 Nh 是多少？是多少？h = 0N0 = 0h = 1h = 2h = 3一般情况下，一般情况下，N1 = 1N2 = 2N3 = 4Nh = Nh-1 + Nh-2 + 1利用归纳法可证得，利用归纳法可证得， Nh = Fh+2 - 1 因此，在二叉平衡树上进行查找时，因此，在二叉平衡树上进行查找时，查找过程中和给定值进行比较的关键字查找过程中和给定值进行比较的关键字的个

46、数和的个数和 log(n) 相当相当。 由此推得，深度为由此推得，深度为 h 的二叉平衡树的二叉平衡树中所含结点的最小值中所含结点的最小值 Nh = h+2/5 - 1 反之，含有反之，含有 n 个结点的二叉平衡树能个结点的二叉平衡树能达到的最大深度达到的最大深度 hn = log ( 5 (n+1) - 2 1定义定义2查找过程查找过程3插入操作插入操作4删除操作删除操作5查找性能的分析查找性能的分析三、三、 B - 树树1B-树的定义树的定义B-树是一种树是一种 平衡平衡 的的 多路多路 查找查找 树：树： root 50 15 71 84 3 8 20 26 43 56 62 78 89

47、 96 在在 m 阶的阶的B-树上，每个非终端结点可能树上，每个非终端结点可能含有：含有： n 个个关键字关键字 Ki（1 in） nm n 个个指向记录的指针指向记录的指针 Di（1in） n+1 个个指向子树的指针指向子树的指针 Ai（0in）;多叉树的特性多叉树的特性typedef struct BTNode int keynum; / 结点中结点中关键字个数关键字个数，结点大小，结点大小 struct BTNode *parent; / 指向指向双亲双亲结点的指针结点的指针 KeyType keym+1; / 关键字（关键字（0号单元不用）号单元不用） struct BTNode *p

48、trm+1; / 子树子树指针向量指针向量 Record *recptrm+1; / 记录记录指针向量指针向量 BTNode, *BTree; / B树结点和树结点和B树的类型树的类型B-树结构的树结构的C语言描述如下语言描述如下: : 非叶结点中的非叶结点中的多个关键字多个关键字均均自小至大自小至大有有序排列，即：序排列，即：K1 K2 keynum; i=Search(p, K); / 在在p-key1.keynum中查找中查找 i ， / p-keyi=Kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p

49、的双亲 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功在查找不成功之后，需进行插入。显然，关键字插入插入的位置位置必定在最下最下层的非叶结点层的非叶结点，有下列几种情况：3插入插入1）插入后，该结点的关键字个数nsymbol 其中其中: p 指向双链树中某个结点，指向双链树中某个结点， 0 i K.num-1初始状态初始状态: p=T-first; i = 0;若若 ( p & p-symbol = K.chi & ifirst; i+;若若 ( p & p-symbol != K.chi )则继续在键树的同一层上进

50、行查找则继续在键树的同一层上进行查找 p=p-next;若若 ( p & p-symbol=K.chi & i=K.num-1)则则 查找成功，查找成功，返回指向相应记录的指针返回指向相应记录的指针 p-infoptr 若若 ( p = NULL)则表明查找不成功，返回则表明查找不成功，返回“空指针空指针”;3. Trie树树 以多重链表作存储结构实现的键树结点结构结点结构:分支结点分支结点叶子结点叶子结点指向记录指向记录的指针的指针0 1 2 3 4 5 24 25 26关键字关键字指向下层结点的指针指向下层结点的指针每个域对应一个每个域对应一个“字母字母”0 1(A) 3 4 5(E) 9

51、(I) 268(H)4(D) 19(S) 22(V) 0 18(R) 7(G) 190 5(E)THADHAS HAVE HEHERHEREHIGHHIS叶子结点叶子结点分支结点分支结点指向记录指向记录的指针的指针typedef struct TrieNode NodeKind kind; / 结点类型结点类型 union struct KeyType K; Record *infoptr lf; / 叶子结点叶子结点(关键字和指向记录的指针关键字和指向记录的指针) struct TrieNode *ptr27; int num bh; / 分支结点分支结点(27个指向下一层结点的指针个指向下

52、一层结点的指针) TrieNode, *TrieTree; / 键树类型键树类型结点结构的结点结构的 C 语言描述语言描述:在在 Trie 树中查找记录的过程树中查找记录的过程:假设假设: T 为指向为指向 Trie 树根结点的指针，树根结点的指针， K.ch0.K.num-1 为待查关键字为待查关键字(给定值给定值)。则查找过程中的基本操作为：则查找过程中的基本操作为： 搜索和对应字母相应的指针搜索和对应字母相应的指针:若若 p 不空，且不空，且 p 所指为分支结点，所指为分支结点，则则 p = p-bh.Ptrord(K.Chi) ; ( 其中其中: 0 i K.num-1 )初始状态初始

53、状态: p=T; i = 0;若若 ( p & p-kind = BRANCH & ibh.ptrord(K.chi); i+;其中，其中，ord 为求字符在字母表中序号的函数为求字符在字母表中序号的函数若若 ( p & p-kind=LEAF & p-lf.K=K)则则查找成功查找成功，返回指向相应记录的指针返回指向相应记录的指针 ptr 反之，即反之，即 ( !p | p-kind=LEAF & p-lf.K!=K )则表明则表明查找不成功查找不成功，返回，返回“空指针空指针”; 一、哈希表是什么？一、哈希表是什么？二、哈希函数的构造方法二、哈希函数的构造方法 三、处理冲

54、突的方法处理冲突的方法 四、哈希表的查找四、哈希表的查找 五、哈希表的删除操作五、哈希表的删除操作 六、对静态查找表，。六、对静态查找表，。9.3 哈哈 希希 表表 以上两节讨论的表示查找表的各种以上两节讨论的表示查找表的各种结结构构的共同的共同特点特点：记录在表中的位置和它的记录在表中的位置和它的关键字之间不存在一个确定的关系，关键字之间不存在一个确定的关系， 查找的过程查找的过程为给定值依次和关键字集为给定值依次和关键字集合中各个关键字进行合中各个关键字进行比较比较， 查找的效率查找的效率取决于和给定值取决于和给定值进行比较进行比较的关键字个数。的关键字个数。 用这类方法表示的查找表，用这

55、类方法表示的查找表，其其平均查找长度都不为零平均查找长度都不为零 不同的表示方法，其差别仅在于：不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。关键字和给定值进行比较的顺序不同。 只有一个办法：预先知道所查关键只有一个办法：预先知道所查关键字在表中的位置，字在表中的位置， 对于频繁使用的查找表，对于频繁使用的查找表，希望希望 ASL = 0。 即，要求：即，要求：记录在表中位置和其关记录在表中位置和其关键字之间存在一种确定的关系键字之间存在一种确定的关系。若若以下标为以下标为000 999 的顺序表的顺序表表示之。表示之。例如：例如：为每年招收的为每年招收的 1000 名新生建

56、立名新生建立一张查找表，其关键字为学号，其值的一张查找表，其关键字为学号，其值的范围为范围为 xx000 xx999 (前两位为年份前两位为年份)。则查找过程可以简单进行：取给定值则查找过程可以简单进行：取给定值（学号）的后三位，（学号）的后三位，不需要经过比较便不需要经过比较便可直接从顺序表中找到待查关键字。可直接从顺序表中找到待查关键字。但是，对于但是，对于动态查找表动态查找表而言，而言，因此在一般情况下，需在关键字与记录因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关在表中的存储位置之间建立一个函数关系，系，以以 f(key) 作为关键字为作为关键字为 key 的记录

57、的记录在表中的位置在表中的位置，通常通常称称这个函数这个函数 f(key) 为哈希函数。为哈希函数。1) 表长不确定；表长不确定；2) 在设计查找表时，只知道关键字所在设计查找表时，只知道关键字所 属范围，而不知道确切的关键字。属范围，而不知道确切的关键字。Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Du 例如：例如：对于如下对于如下 9 个关键字个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 0 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3ChenZhaoQianSunLi

58、WuHanYeDu问题问题: 若添加关键字 Zhou , 怎么办？怎么办？能否找到能否找到另一个哈希函数？1) 哈希函数是一个哈希函数是一个映象映象，即：，即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可大小不超出允许范围即可;从这个例子可见，从这个例子可见，2) 由于哈希函数是一个由于哈希函数是一个压缩映象压缩映象，因此，因此，在一般情况下，很容易产生在一般情况下，很容易产生“冲突冲突”现象，现象，即：即： key1 key2，而，而 f(key1) = f(key2)

59、。3) 很难很难找到一个不产生冲突的哈希函数。找到一个不产生冲突的哈希函数。一般情况下，一般情况下，只能选择恰当的哈希函数，只能选择恰当的哈希函数，使冲突尽可能少地产生。使冲突尽可能少地产生。 因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除了需要选择一个时，除了需要选择一个“好好”( (尽可能尽可能少产生冲少产生冲突突) )的哈希函数之外的哈希函数之外;还需要找还需要找到到一种一种“处理冲突处理冲突” 的方法的方法。哈希表的定义: 根据设定的根据设定的哈希函数哈希函数 H(key) 和所选和所选中的中的处理冲突的方法处理冲突的方法，将一组关键字，将一组关键字映象映象到到一

60、个有限的、地址连续的地址集一个有限的、地址连续的地址集 (区间区间) 上，并以关键字在地址集中的上，并以关键字在地址集中的“象象”作为作为相应记录在表中的相应记录在表中的存储位置存储位置，如此构造所，如此构造所得的查找表称之为得的查找表称之为“哈希表哈希表”。 对数字的关键字可有下列构造方法对数字的关键字可有下列构造方法: 若是非数字关键字，则需先对其进行若是非数字关键字，则需先对其进行数字化处理。数字化处理。1. 直接定址法直接定址法3. 平方取中法平方取中法5. 除留余数法除留余数法4. 折叠法折叠法6. 随机数法随机数法2. 数字分析法数字分析法二、构造哈希函数的方法构造哈希函数的方法哈