设计网站的步骤,常州辉煌网络网站制作,成都网站建制作,wordpress pdf 下载失败文章目录 一.查找二.线性结构的查找2.1顺序查找2.2折半查找2.3分块查找 三.树型结构的查找3.1二叉排序树1.定义2.二叉排序树的常见操作3.性能分析 3.2平衡二叉树1.定义2.平衡二叉树的常见操作3.性能分析 3.3B树1.定义2.B树的相关操作 3.4B树1.定义2.B树与B树的比较 四.散列表1.… 文章目录 一.查找二.线性结构的查找2.1顺序查找2.2折半查找2.3分块查找 三.树型结构的查找3.1二叉排序树1.定义2.二叉排序树的常见操作3.性能分析 3.2平衡二叉树1.定义2.平衡二叉树的常见操作3.性能分析 3.3B树1.定义2.B树的相关操作 3.4B树1.定义2.B树与B树的比较 四.散列表1.哈希函数的构造1.常用构造方法2.冲突处理 2.哈希表的查找 一.查找 问题在哪里找 ——查找表 查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。由于“集合”中的数据元素之间存在着松散的关系因此查找表是一种应用灵便的结构我们可以根据需要把这些数据存成线性表可以存成树表或者是散列表。 那么到底怎么存呢? ——取决于怎么做会使查找更方便 而查找的方法取决于查找表的结构即表中数据元素是依何种关系组织在一起的。
静态查找表(Static Search Table)只作查找操作的查找表。
主要操作
查询某个“特定的”数据元素是否在查找表中。检索某个“特定的”数据元素和各种属性。
动态查找表(Dynamic Search Table) 在查找过程中同时插入查找表中不存在的数据元素或者从查找表中删除已经存在的某个数据元素。
主要操作
查找时插入不存在的数据元素。查找时删除已存在的数据元素。
关键字(Key)数据元素中唯一标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。例如在由一个学生元素构成的数据集合中学生元素中“学号”这一数据项的值唯一地标识一名学生。
主关键字可以唯一地标识一个记录的关键字是主关键字次关键字反之用以识别若干记录的关键字好死次关键字 问题查找成功否 查找(Searching)就是根据给定的某个值在查找表中确定一个其关键字等于给定值的数据元素( 或记录)。
若查找表中存在这样一个记录则称“查找成功”。查找结果给出整个记录的信息或指示该记录在查找表中的位置。否则称“查找不成功”。查找结果给出“空记录”或“空指针”。 平均查找长度是衡量查找算法效率的最主要的指标。 问题查找目的是什么 ——对查找表经常进行的操作。 为了提高查找效率一个办法就是在构造查找表时在集合中的数据元素之间人为地加上某种确定的约束关系。所以下面来研究查找表的各种组织方法及其查找过程的实施。
二.线性结构的查找
2.1顺序查找
【查找过程】从表的一端开始依次将记录的关键字和给定值进行比较若某个记录的关键字和给定值相等则查找成功反之若扫描整个表后仍未找到关键字和给定值相等的记录则查找失败。
【应用范围】顺序查找既适用于顺序表也适用于链表链表表示的静态查找表。若用顺序表查找可以从前往后扫描也可以从后往前扫描但若采用单链表则只能从前往后扫描。
【查找算法】 在顺序表L中查找值为 key 的数据元素。
//顺序表数据元素类型定义
typedef struct{KeyType key; //关键字域..... //其他域
}ElemType;
//顺序表结构类型定义
typedef struct{ElemType *R;//表基址int length; //表长
}SSTable; //Sequential Search Table
SSTable ST;//定义顺序表STint LocateELem(SSTable ST,KeyType key){ //若成功返回其位置信息否则返回0for (i0;i ST.length;i)if (ST.elem[i]e) return i1; return 0;
}//查找的其他形式
int LocateELem(SSTable ST,KeyType key){ //若成功返回其位置信息否则返回0for (i0;ST.R[i].key!key iST.length;i);//一次循环两次比较if(i0)return i;else return 0;
}【性能分析】
时间复杂度①查找成功时的平均查找长度设表中各记录查找概率相等
ASLs(n)(12 … n)/n (n1)/2
②查找不成功时的平均查找长度ASLf n1。 每执行一次循环都要进行两次比较是否能改进呢 【算法改进】 把待查关键字key存入表头“哨兵”从后向前逐个比较可免去查找过程中每一步都要检测是否查找完毕加快速度。 /*有哨兵顺序查找*/
int Sequential_Search(SSTable ST,KeyType key){ST.R[0].key key; //把关键字放在下标为0的位置称之为“哨兵”for (i0;ST.R[i].key!key iST.length;i);return i;}这种在查找方向的尽头放置“哨兵”免去了在查找过程中每一次比较后都要判断查找位置是否越界的小技巧看似与原先差别不大但在总数据较多时效率提高很大是非常好的编码技巧。 上述顺序表查找时间复杂度是O ( n )空间复杂度是O(1)多了一个哨兵
【算法特点】 算法简单对表结构无任何要求顺序和链式但n很大时查找效率较低ASL太长时间效率太低。
【改进措施】 非等概率查找时可按照查找概率进行排序。 那么记录的查找概率不相等时如何提高查找效率 查找表存储记录原则——按查找概率高低存储 1查找概率越高比较次数越少放在靠后的位置
2查找概率越低比较次数较多放在靠前的位置。 记录的查找概率无法测定时如何提高查找效率 ——按查找概率动态调整记录顺序 1在每个记录中设一个访问频度域
2始终保持记录按非递增有序的次序排列
3每次查找后均将刚查到的记录直接移至表头。 有序表查找有折半查找插值查找斐波那契查找这里介绍折半查找
2.2折半查找 折半查找(Binary Searh) 也称二分查找它是一种效率较高的查找方法。 【应用范围】 折半查找要求线性表必须采用顺序存储结构而且表中元素按关键字有序排列递增或递减不宜用于链式结构。
【查找过程】 从表的中间记录开始如果给定值和 中间记录的关键字相等 则查找成功如果给定值大于或者小于中间记录的关键字 则在表中大于或小于中间记录的那一半中查找这样重复操作直到查找成功或者在某一步中查找区间为空lowhigh则代表查找失败。
例如对序列5、13、19、21、37、56、64、75、80、88、92中查找21过程如下
①初时low1mid(111)/26 ,high11 ②此时.r[mid].key21,因此 highmid-15low1mid(15)/23 ③此时.r[mid].key21,因此 lowmid14high5mid(45)/24 ④此时kR[mid].key查找成功。
【算法思想】 非递归算法 设表长为nlow、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 初始时令low1,highn,mid(lowhigh)/2让k与mid指向的记录比较
①若kR[mid].key查找成功
②若kR[mid].key则highmid-1
③若kR[mid].key则lowmid1。重复上述操作直至lowhigh时查找失败。
【算法描述】
//采用折半查找发在顺序表上进行查找
int Search_Bin(SSTable ST,KeyType key){
//若找到则函数值为该元素在表中的位置否则为0low1;highST.length; //置区间初值 while(lowhigh){mid(lowhigh)/2;//取中间位置if(keyST.R[mid].key)return mid;//查找成功返回所在位置else if(keyST.R[mid].key) //缩小查找区间highmid-1; //从前半部分继续查找else lowmid1; //从后半部分继续查找} return 0; //表中不存在待查元素
} 下面来看一下同一种操作的不同算法——递归算法每一次判断是否与中间位置相等
int Search_Bin(SSTable ST,KeyType key,int low,int high){if(lowhigh)return 0;//区间不存在查找不到是返回0mid(lowhigh)/2;if(keyST.elem[mid].key)return mid;else if(keyST.elem[mid].key){highmid-1;Search_Bin(SSTable ST,key,low,high)//递归在前半区间进行查找}else{lowmid1;Search_Bin(SSTable ST,key,low,high)//递归在前半区间进行查找}
}【性能分析】 折半查找使用判定树进行分析。该判定树是一颗二叉排序树中序有序。判定树的构造过程为 第一次进行mid计算时的结点作为根节点并进行low结点位置和high结点的位置进行计算作为mid的左右孩子将前一子表low-mid、后一子表mid-high分别重复上述步骤直至所有结点都在判定树中。
如下对序列5、13、19、21、37、56、64、75、80、88、92进行判定树构造查找21 如下 (图中有错误二叉树的深度为⌈ l o g_2 ( n 1 ) ⌉ ) 所以折半查找的时间复杂度为O ( l o g_2 n ) 平均情况下比顺序查找的效率高。 假定每个元素的查找概率相等求查找成功时的平均查找长度。 对比顺序查找法的平均查找长度是111/26折半查找法减少了很多因为折半查找法的时间效率是对数级的而顺序查找法的时间效率是线性级的。
时间复杂度查找成功时的平均查找长度设表中各记录查找概率相等P_i1/n
设表长n2h-1则hlog_2(n1)此时判定树为深度h的满二叉树 利用二叉树的性质将一个一个n个的元素比较转化为一层一层j层的结点的比较
【算法特点】
①优点效率比顺序查找高。
②缺点只适用于有序表且限于顺序存储结构对线性链表无效找不到mid。 线性索引查找有稠密索引分块索引和倒排索引下面介绍分块索引
2.3分块查找
【应用范围】如果线性表既要快速查找又经常动态变化则可采用分块查找。
条件①分块有序即分成若干子表要求每个子表中的数值都比后一块中数值小但子表内部未必有序。
②然后将各子表中的最大关键字构成一个索引表表中还要包含每个子表的起始地址即头指针。 【查找过程】
① 先确定待查记录所在快对索引表使用折半查找法因为索引表是有序表
② 再在块内查找在子表内采用顺序查找法因为各子表内部是无序表
【查找算法】 分块查找的算法为顺序查找和折半查找两种算法的简单合成。
【性能分析】
【优缺点】
①优点插入和删除比较容易无需进行大量移动。
②缺点要增加一个索引表的存储空间并对初始索引表进行排序运算。 总结 三.树型结构的查找
线性表的查找更适用静态查找表当表插入删除操作频繁时为维护表的有序性需要移动表中很多记录可采用几种特殊的二叉树作为查找表的组织形式在此将它们统称为树表。表结构在查找过程中动态生成对于给定值key若表中存在则成功返回否则插入关键字等于key的记录。
根据用途不同动态查找表又分为很多种二叉排序树平衡二叉树红黑树B树B树键树等。
3.1二叉排序树
1.定义
二叉排序树 (Binary Sort Tree) 又称二叉查找树二叉搜索树它是一种对排序和查找都很有用的特殊二叉树。
【性质】二叉排序树或是空树或是满足如下性质的二叉树
①若其左子树非空则左子树上所有结点的值均小于根结点的值
②若其右子树非空则右子树上所有结点的值均大于等于根结点的值
③其左右子树本身又各是一棵二叉排序树 易错注意是“所有”例如下图所示树不是二叉排序树
【特点】 中序遍历二叉排序树得到一个关键字的递增有序序列。 下面来了解一下二叉树的操作
2.二叉排序树的常见操作 1查找 【算法思想】 二叉排序树上进行递归算法的思想 (1)若二叉排序树为空则查找失败返回空指针。
(2)若二叉排序树非空将给定值key与根结点的关键字T-data.key进行比较
① 若key等于T-data.key则查找成功返回根结点地址
② 若key小于T-data.key则进一步查找左子树
③ 若key大于T-data.key则进一步查找右子树。
【算法描述】
//二叉排序树的存储用二叉链表
typedef struct{KeyType key; //关键字项InfoType otherinfo; //其他数据域
}ElemType;
typedef struct BSTNode{ElemType data; //数据域struct BSTNode *Ichild,*rchild; //左右孩子指针
}BSTNode,*BSTree;
BSTree T; //定义二叉排序树TBSTree SearchBST(BSTree T,KeyType key) {if((!T) || keyT-data.key) return T; //找到返回结点地址找不到返回空指针 else if (keyT-data.key) return SearchBST(T-lchild,key); //在左子树中继续查找else return SearchBST(T-rchild,key); //在右子树中继续查找
}
} 2插入 【算法描述】 若二叉排序树为空则插入结点应为根结点否则继续在其左、右子树上查找
①树中已有不再插入
②树中没有查找直至某个叶子结点的左子树或右子树为空为止则插入结点应为该叶子结点的左孩子或右孩子。
【算法特点】插入的元素一定在叶结点上。
【算法过程】 在下图所示的二叉排序树上插入结点 20 过程如下①4520,继续在结点45的左子树上查询
②1220,继续在结点12的右子树上查询
③3720,继续在结点37的左子树上查询
④2420,继续在结点24左子树查询而该结点为叶子结点将此结点20插入结点24的左子树中。 【算法过程】
/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE否则返回FALSE
*/
/*
当二叉排序树T中不存在关键字等于key的数据元素时
插入key并返回TRUE否则返回FALSE
*/
bool InsertBST(BiTree *T, int key){BiTree p, s;if(!SearchBST(*T, key, NULL, p)){//查找不成功s (BiTree)malloc(sizeof(BiTNode));s-data key;s-lchild s-rchild NULL;if(!p){*T s; //插入s为新的根节点}else if(key p-data){p-lchild s; //插入s为左孩子}else{p-rchild s; //插入s为右孩子}return TRUE;}else{return FALSE; //树种已有关键字相同的结点不再插入}
}3生成 从空树出发经过一系列的查找插入操作之后可生成一棵二叉排序树。
一个无序序列可通过构造二叉排序树而变成一个有序序列构造树的过程就是对无序序列进行排序的过程。插入的结点均为叶子结点故无需移动其他结点。相当于在有序序列插入记录而无需移动其他记录。
从空树出发对序列{10 18 3 8 12 2 7} 构造二叉排序树。
【过程如下】 ①结点10作为根节点1810,插入为结点10的右子树 ②310,插入为结点10的左子树 ③810,38,插入为结点3的右孩子 ④1210.1218,插入为结点18的左孩子 ⑤21032,插入为结点3的左孩子 ⑥710,37,87,插入为结点8的左孩子至此二叉排序树生成。 【注意】 不同插入次序的序列生成不同形态的二叉排序树。如下图所示 【算法过程】
有了二叉排序树的插入代码我们要实现二叉排序树的构建就非常容易了几个例子
int i;
int a[10] {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
BiTree T NULL;
for(i 0; i10; i){InsertBST(T, a[i]);
}上面的代码就可以创建一棵下图这样的树。 4删除 从二叉排序树中删除一个结点不能把以该结点为根的子树都删去只能删掉该结点并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。
由于中序遍历二叉排序树可以得到一个递增有序的序列。那么在二叉排序树中删去一个结点相当于删除有序序列中的一个结点。
【删除思想】将因删除结点而断开的二叉链表重新链接起来防止重新链接后树的高度增加。
①删除叶结点只需将其双亲结点指向它的指针清零再释放它即可。
②被删结点缺右子树可以拿它的左子女结点顶替它的位置再释放它。
③被删结点缺左子树可以拿它的右子女结点顶替它的位置再释放它。
④被删结点左、右子树都存在依据中序遍历思想以下有两种方法具体情况考虑树的高度选择删除的方法
以其中序前趋值替换之值替换然后再删除该前趋结点。前趋是左子树中最大的结点。也可以用中序遍历的后继结点替换之然后再删除该后继结点。后继是右子树中最小的结点。 【算法过程】
/*从二叉排序树中删除结点p并重接它的左或右子树。*/
bool Delete(BiTree *p){BiTree q, s;if(p-rchild NULL){//右子树为空则只需重接它的左子树q p;p p-lchild;free(q);}else if(p-lchild NULL){//左子树为空则只需重接它的右子树q p;p p-rchild;free(q);}else{//左右子树均不空q p;s p-lchild; //先转左while(s-rchild){//然后向右到尽头找待删结点的前驱q s;s s-rchild;}//此时s指向被删结点的直接前驱p指向s的父母节点p-data s-data; //被删除结点的值替换成它的直接前驱的值if(q ! p){q-rchild s-lchild; //重接q的右子树}else{q-lchild s-lchild; //重接q的左子树}pree(s);}return TRUE;
}3.性能分析
二叉排序树的优点明显插入删除的时间性能比较好。而对于二叉排序树的查找平均查找长度和二叉树的形态有关查找的次数和关键字存在的位置有关即: ①最好ASL⌈ l o g_2 ( n 1 ) ⌉ 形态匀称与折半查找中的判定树相同;
②最坏ASLn1)/2单支树退化成了顺序查找法 问题如何提高形态不均衡的二叉排序树的查找效率 解决办法做“平衡化”处理即尽量让二叉树的形状均衡 3.2平衡二叉树
1.定义
【概念】左、右子树是平衡二叉树AVL所有结点的左、右子树深度之差的绝对值≤ 1 。任一结点的平衡因子只能取-1、0 或 1如果树中任意一个结点的平衡因子的绝对值大于1则这棵二叉树就失去平衡不再是AVL树
【平衡因子】 为了方便起见给每个结点附加一个数字给出该结点左子树与右子树的高度差这个数字称为平衡因子BF。
2.平衡二叉树的常见操作 1查找 在平衡二叉树上进行查找的过程与二叉排序树的相同。因此在查找过程中与给定值进行比较的关键字个数不超过树的深度。假设以 n_h表示深度为 h 的平衡树中含有的最少结点数。显然有 n_00,n_11,n_22 并且有n_hn_{h-1}n_{h-2}1。 2插入 二叉排序树保证平衡的基本思想如下每当在二叉排序树中插入(或删除)一个结点时首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A再对以A为根的子树在保持二叉排序树特性的前提下调整各结点的位置关系使之重新达到平衡。 注意:每次调整的对象都是最小不平衡子树即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。下图中的虚线框内为最小不平衡子树。 平衡二叉树的插入过程的前半部分与二叉排序树相同但在新结点插入后若造成查找路径上的某个结点不再平衡则需要做出相应的调整。可将调整的规律归纳为下列4种情况 调整原则①降低高度 ②保持二叉排序树的性质分析三个A,B,C结点的大小旋转的结果为左子树最小右子树最大根结点中间 LL平衡调整 如下图所示结点旁的数值代表结点的平衡因子而用方块表示相应结点的子树下方数值代表该子树的高度。 RR平衡调整 LR平衡调整 RL平衡调整 注意: LR和RL旋转时新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程而上图中是以插入C的左子树中为例。
举个例子 假设关键字序列为15 , 3 , 7 , 10 , 9 , 8 {15,3, 7, 10, 9, 8}15,3,7,10,9,8通过该序列生成平衡二叉树的过程如下图所示。
3.性能分析
对于一棵有n个结点的平衡二叉树AVL其高度保持在O(log2n)数量级平均查找长度ASL也保持在O(log2n)量级。
查找和二叉排序树一致比较的次数不超过平衡二叉树的深度。 前面我们认识了二叉排序树AVL树这些树的原理就是先把数据加载到内存里面然后在内存中进行处理数据量通常不会很大那如果数据量非常大大到内存根本存不下的时候为什么要存在内盘里面呢不能直接在硬盘上面操作这些数据吗 由此可见树越高硬盘的访问次数就越多那么减少输的高度是不是就可以减少非常耗时的这个硬盘操作呀那么在数据量不变的情况下如何让树高降低呢多路查找树就应用而生啦~
【多路查找树】
多路查找树(muitl-way search tree) 其每一个结点的孩子数可以多于两个且每一个结点处可以存储多个元素。由于它是查找树所有元素之间存在某种特定的排序关系。 在这里每一个结点可以存储多少个元素以及它的孩子数的多少是非常关键的。常见的有4种特殊形式2-3树、2-3-4树、B树和B树。这里主要介绍B树和B树因为2-3树、2-3-4树都是B树的特例。
如下图所示是一颗2-3树
3.3B树
1.定义
B树也称为B-树B-树是一种所有结点的平衡因子均等于0的平衡的多路查找树。同时B树访问结点是在硬盘上进行的结点内的数据操作是在内存中进行的。
【定义】 B树中所有结点的孩子个数的最大值称为B树的阶通常用m 表示。一棵B树具有如下图所示的三个特点平衡有序多路。 2.B树的相关操作 1查找 B树的查找包含两个基本操作:①在B树找结点硬盘上操作:②在结点内找关键字内存中操作先在该结点有序表中进行查找若找到则查找成功否则按照对应的指针信息到所指的子树中去查找。 最后如图所示查找到叶结点时(对应指针为空指针),则说明树中没有对应的关键字查找失败。
所有的叶子结点都出现在同一层次上并且不带信息通常称为失败结点即外部结点失败结点并不存在指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能。 2插入 将关键字key插入B树的过程如下: 分裂的方法是:取一个新结点在插入key后的原结点从中间位置(⌈m/2⌉) 将其中的关键字分为两部分左部分包含的关键字放在原结点中右部分包含的关键字放到新结点中中间位置(⌈ m/2⌉)的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限则继续进行这种分裂操作直至这个过程传到根结点为止进而导致B树高度增1。 对于m3的B树所有结点中最多有m-12个关键字若某结点中已有两个关键字则结点已满如图中a)所示。插入一个关键字60后结点内的关键字个数超过了m-1,如图中(b)所示此时必须进行结点分裂分裂的结果如图中©所示。 3删除 删除结点在非叶结点的部分需要按照类似于二叉搜索树左右子树都有的情况也就是用它的直接前趋或者后继去替换它不管是前趋还是后继都落在叶子结点上
B树中的删除操作与插入操作类似但要稍微复杂一些即要使得删除后的结点中的关键字个数⌈m/2⌉-1(避免下溢出,因此将涉及**结点的“合并”**问题。当被删关键字在终端结点(最低层非叶结点)中时有下列三种情况: 兄弟够借 兄弟不够借 尽管B树的诸多好处但其实它还是有缺陷的。对于树结构来说我们都可以通过中序遍历来顺序查找树中的元素需要在结点之间来回移动效率比较低而且这一切都是在内存中进行。可是在B树结构中我们往返于每个结点之间也就意味着我们必须得在硬盘的页面之间进行多次访问。 如上图所示。我们希望遍历这棵B树假设每个结点都属于硬盘的不同页面我们中序遍历所有的元素
页面 2 → 页面 1 → 页面 3 → 页面 1 → 页面 4 → 页面 1 → 页面 5
而且我们每次经过结点遍历时都会对结点中的元素进行一次遍历这就非常糟糕。有没有可能让遍历时每个元素只访问一次呢? B树来啦~
3.4B树
1.定义
B树是应数据库所需而出现的-种B树的变形树。 B树中叶子结点是对记录的索引非叶子结点层是对叶结点层关键字的索引所以整个B树是一个多级索引结构 B树的叶结点层包含了所有元素同时这些元素是从小到大排列的结点之间用指针连接起来。这样的话我们就可以很轻松的通过第一个结点前的头指针来快速的对所有的元素进行顺序遍历。同时因为B树常被用作数据库中的索引结构那实际上每个元素都包含指向对应记录存储地址的指针此时结点内的元素又被称作关键字key通过关键字包含的指针可以索引到数据库中的某一条记录。 B树中的非叶结点可以帮助我们快速的定位到叶结点上的某一关键字相当于给叶子结点层建立了索引为的就是实现以log级别的复杂度去查找叶子结点上的某一关键字记录。
下图所示为一棵4阶B树 【性质】 一棵m阶的B树需满足下列条件:
①每个分支结点最多有m棵子树(孩子结点)
②非叶根结点至少有两棵子树其他每个分支结点至少有⌈ m/2 ⌉棵子树
③结点的子树个数与关键字个数相等
④所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。
【B树的查找】
①顺序查找从最小关键字开始
②随机查找B树的查找最终一定会落到叶子结点层如果在非叶子结点上遇到了关键字还需要继续往下查找
③范围查找结合顺序查找和随机查找
【应用范围】 B树的查找、插入和删除操作和B树的基本类似。只是在查找过程中非叶结点上的关键字值等于给定值时并不终止而是继续向下查找直到叶结点上的该关键字为止。所以在B树中查找时无论查找成功与否每次查找都是一条从根结点到叶结点的路径。
B树的结构特别适合带有范围的查找。比如查找我们学校18~22岁的学生人数我们可以通过从根结点出发找到第一个18岁的学生然后再在叶子结点按顺序查找到符合范围的所有记录。
2.B树与B树的比较
下图以3阶B数树和B树为例观察两种树形结构的不特性 m阶的B树与m阶的B树的主要差异如下:
四.散列表
散列表是根据关键字而直接进行访问的数据结构。也就是说散列表建立了关键字和存储地址之间的一种直接映射关系。我们只需要通过某个函数f使得 存储位置 f ( 关键字 ) 那样我们可以通过查找关键字不需要比较就可获得需要的记录的存储位置。
【哈希方法】 既是一种存储方法 也是一种查找方法散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f使得每个关键字key对应一个存储位置 f(key)。查找时根据这个确定的对应关系找到位置上。
这里我们把这种对应关系 f 称为散列函数又称为哈希(Hash) 函数。按这个思想采用散列技术将记录存储在一块连续的存储空间中这块连续存储空间称为散列表或哈希表(Hash table)。那么关键字对应的记录存储位置我们称为散列地址。
【优点】 查找速度极快时间复杂度为O(1)查找效率与元素个数n无关
1.哈希函数的构造
在构造散列函数时必须注意以下几点
散列表的大小散列函数的定义域必须包含全部需要存储的关键字而值域的范围则依赖于散列表的大小或地址范围。关键字的分布情况散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中从而减少冲突的发生。执行速度散列函数应尽量简单能够在较短的时间内计算出任一关键字对应的散列地址。
1.常用构造方法 【直接定址法】 Hash(key) a·key b (a、b为常数)
①优点以关键码key的某个线性函数值为哈希地址不会产生冲突。
②缺点要占用连续地址空间空间效率低。
例如给定序列{100300500700800900}哈希函数Hash(key)key/100构造哈希表结果如下 【数字分析法】 选取数码分布较为均匀的若干位作为散列地址这种方法适合于已知的关键字集合若更换了关键字则需要重新构造新的散列函数。
【平方取中法】取关键字的平方值的中间几位作为散列地址具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系因此使得散列地址分布比较均匀,适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
【除留余数法】 Hash(key)key mod p (p是一个整数)。该方法的关键是选取有个合适的p值一般情况下若表长为m取p为小于等于m的最大质数。
【随机数法】选择一个随机数取关键字的随机函数值为它的散列地址。也就是H(key)random (key)
这里random是随机函数。当关键字的长度不等时采用这个方法构造散列函数是比较合适的。
2.冲突处理
【冲突】 不同的关键码映射到同一个哈希地址即key1≠key2但H(key1)H(key2)。这些发生碰撞的不同关键字称为同义词。一方面设计得好的散列函数应尽量减少这样的冲突另一方面由于这样的冲突总是不可避免的所以还要设计好处理冲突的方法。 【减少冲突的方式】 ①构造好的哈希函数②制定一个好的解决冲突方案因为冲突是不可能避免的。 1开放定址法 【基本思想】有冲突时就去寻找下一个空的哈希地址只要哈希表足够大空的哈希地址总能找到并将数据元素存入。其冲突函数为
Hi(Hash(key)di) mod m ( 1≤i m ) 【线性探测法】 在该方法中 优点只要哈希表未被填满保证能找到一个空地址单元存放有冲突的元素。 缺点可能使第i个哈希地址的同义词存入第i1个地址这样本应存入第i1个哈希地址的元素变成了第i2个哈希地址的同义词……产生 聚集现象 降低查找效率。 【二次探测法】 对于上述方法产生的聚集现象可采用二次探测法进行解决。在该方法中 【伪随机探测法】 在该方法中 2链地址法拉链法 【基本思想】相同哈希地址的记录链成一单链表m个哈希地址就设m个单链表然后用用一个数组将m个单链表的表头指针存储起来形成一个动态的结构。
【建立哈希表步骤】
①取数据元素的关键字key计算其哈希函数值地址。若该地址对应的链表为空则将该元素插入此链表否则执行②解决冲突。
②根据选择的冲突处理方法计算关键字key的下一个存储地址。若该地址对应的链表不为空则利用链表的前插法或后插法将该元素插入此表。
【优点】 ①非同义词不会冲突无“聚集”现象
②链表上结点空间动态申请更适合于表长不确定的情况。 3公共溢出区法 这个方法其实就更加好理解就是把凡是冲突的家伙额外找个公共场所待着。我们为所有冲突的关键字建立了一个公共的溢出区来存放。
就前面的例子而言我们共有三个关键字37 , 48 , 34与之前的关键字位置有冲突那么就将它们存储到溢出表中如下图所示。 如果相对于基本表而言有冲突的数据很少的情况下公共溢出区的结构对查找性能来说还是非常高的。
2.哈希表的查找
【比较步骤】 【例子】 ②用链地址法处理冲突 在此方法中ASL(162434)/121.75。
【效率分析】 使用平均查找长度ASL来衡量查找算法ASL取决于以下几个因素
①哈希函数
②处理冲突的方法
③哈希表的装填因子。α越大表中记录数越多说明表装得越满发生冲突的可能性就越大查找时比较次数就越多。 【三种方法比较】
对哈希表技术具有很好的平均性能优于一些传统的技术链地址法优于开地址法除留余数法作哈希函数优于其它类型函数。
