第八章 查找
定义：查找就是根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。
8.2 查找概论
查找表（Search table）：是由同一类型的数据元素构成的集合。
关键字（key）：是数据元素中某个数据项的值，又称为键值。
若此关键字可以唯一的标识一个记录，则称此关键字为主关键字（Primary key）。
对于那些可以识别多个数据元素的关键字，我们称为次关键字（Secondary key）。
查找表按照操作方式来分有两大种：静态查找表和动态查找表
静态查找表（Static Search Table）：只作查找操作的查找表，它的主要操作有：
1）查询某个“特定的”数据元素是否在查找表中
2）检索某个“特定的”数据原色和各种属性
动态查找表（Dynamic Search Table）：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素
操作就下面两个：
1）查找时插入数据元素
2）查找时删除数据元素
为了提高查找效率，我们需要专门为查找操作设置数据结构，这种面向查找操作的数据结构称为查找结构。
8.3 顺序表查找
又叫线性查找，查找过程是：从第一个记录开始，逐个进行记录的关键字和给定值比较，若存在某个记录的关键字和给定值相等则查找成功；如果知道最后都没有，则查找失败
算法简单，数据多的时候效率低。
时间复杂度：O(n)
8.4 有序表查找
8.4.1 折半查找
又称二分查找：前提是线性表中的记录必须是关键码有序（一般由小到大），线性表必须采用顺序存储。
时间复杂度：O(logn)
8.4.2 插值查找
8.4.3 斐波那契查找
8.5 线性索引查找
索引就是把一个关键字与它对应的记录相关联的过程。
一个索引由若干个索引项构成，每个索引项至少应该包含关键字和其对应的记录在存储器中的位置等信息。
所以按照结构可以分为：线性索引、树形索引、多级索引。
这里只介绍线性索引：将索引项集合组织为线性结构，也称为索引表。（介绍三种线性索引：稠密索引，分块索引、倒排索引）
8.5.1 稠密索引
是只在线性索引中，将数据集中的每一个记录都对应一个索引项。索引项一定是按照关键码有序的排列
当数据集非常大的时候，就意味着索引也得同样的数据集长度规模。索引表也占了很大的内存
8.5.2 分块索引
是把数据集的记录分成了若干块，并且这些块需要满足两个条件啊：块内无序，块间有序。
就有点像书架放书，把不同类别的分开放，专业书放一起，文学类放一起，漫画放一起，但是水浒传和三国的次序是不确定的。
8.5.3 倒排索引
8.6 二叉排序树
假如存在一个链表{22, 55 56, 76, 88, 99}。如果需要插入33，想要保证有序，就需要移动后面的元素。但是如果是二叉查找树就不需要了。
二叉排序树（Binary sort tree）：又称为二叉查找树，它或者是一棵空树，或者是具有下列性质的二叉树：
1）若它的左子树不空，则左子树上所有的结点的值均小于它根节点的值
2）若右子树不空，则右子树上所有的结点的值均大于它的根节点的值
3）它的左右子树也分别为二叉排序树
二叉树的结构：
typedef struct BiTNode
{
int data;
struct BiTNode *left;
struct BiTNode *right;
}BitNode;
1.查找操作
假定要查找的键值为key可以用递归。
从根节点开始，若结点的data等于key，则返回该结点。
若该结点data > key，则在该结点的左子树中查找
否则在右子树中查找。
2.插入操作
先判断结点存不存在（有时也可以插入想同的结点）。然后找到插入位置，也是从根节点开始。
3.删除操作
删除结点不能破坏了二叉搜索树的特性。
要分三种情况：
1）若是叶子结点则直接删除就可以了
2）若该结点有左子树或右子树其中一个，那么就直接把子树往上怼就好了。
3）若删除的结点有左右子树，则需要找到该结点的前驱结点（左子树中最大的）或后继结点（右子树中最小的）。（二叉搜索树的中序遍历就是有序的，可以利用那个特性找到前驱结点 后继结点）
接下来就有两种处理方式了：a：把前驱结点放到删除的结点中，然后删除前驱结点。 b：把后继结点放到删除的结点中，再删除后继结点
一个搜索二叉树的例子：http://www.cnblogs.com/xcywt/p/8289765.html
8.7 平衡二叉树
要满足两个条件：二叉排序树、任意结点平衡因子绝对值小于2.
是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1.
平衡因子（BF）：二叉树上结点的左子树深度减去右子树深度是值。
平衡二叉树上所有结点的平衡因子只可能是-1,0,1
8.8 多路查找树（B树）
多路查找树（muitl-way search tree）：其每个结点的孩子树可以多于两个，且每个结点处可以存储多个元素。
8.9 散列表查找（哈希表）概述
只需要通过某个函数f使得，： 存储位置=f(关键字). 这样就可以不通过关键字比较就获得记录的存储位置。这就是一种新的存储技术—散列技术。
散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key都对应一个存储位置f(key)。
这种对应关系f称为散列函数，又称为哈希（Hash）函数
采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表或者哈希表（Hash table）。
8.9.2 散列表查找步骤
1）在存储时，通过散列函数计算记录散列地址，并按照此散列地址存储该记录。
2）查找记录时：通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录。
散列技术既是一种存储方法，也是一种查找方法。
散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。
散列技术最适合的求解问题是查找与给定值相等的记录。
冲突：key1!=key2，但是f(key1) == f(key2)。key1和key2称为这个散列函数的同义词。
8.10 散列函数的构造方法
有两个原则参考：
1）计算简单
2）散列地址均匀分布
下面介绍几种常用的散列函数构造方法：
8.10.1 直接定址法
取关键字的某个线性函数值为散列地址，即：f(key) = a * key + b; (a b为常数)
优点：简单 均匀 不会有冲突
缺点：需要事先知道关键字的分布情况，适合查找表小切连续的情况。所以实际应用的不多
例子1：0-100岁的人口数字统计如下，那么我们对年龄这个关键字就可以直接用年龄的数字作为地址。此时 f(key) =key;
例子2：下面是1980年以后出声年份人口数，那么我们对出生年份这个关键字可以用年份减去1980来做地址，此时 f(key) = key – 1980;
我们要利用出生年份去获取人数，所以把出生年份看成key。
8.10.2 数字分析法
比如要存储公司员工信息，如果用手机号作为关键字，前7位可能会重复，我们可以抽取后四位作为散列地址。
如果这样抽取出现了冲突问题，还可以对抽取出来的数字进行变换。
关键词：抽取：使用关键字的一部分来计算散列存储位置的方法。
数字分析法适合处理关键字位数比较大的情况，如果实现知道关键字的分布且关键字的若干为分布较均匀就可以用这个方法。
8.10.3 平方取中法
假如关键字是1234，平方就是1522756。再抽取中间的3位做散列地址，就是227.
再比如4321，平方是18671041，中间三位可以是671，也可以是710 用作散列地址
平方取中法适合不知道关键字的分布，而位数又不是很大的情况
8.10.4 折叠发
将关键字从左到右分成位数相等的几部分，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。
比如：关键字是9876543210，分割成这样987|654|321|0，再相加987+654+321+0 = 1962，再用后三位得到散列地址为962.
如果会冲突就分布部分也翻转一下。
折叠法事先不需要知道关键字的分布，适合关键字位数较多的情况。
8.10.5 除留余数法
这个是最常用的构造散列函数的方法，对于散列表长为m的散列函数公式为：f(key) = key mod p (p <= m)
mod是取模（求余数）的意思。有时还可以对关键字折叠、平方后取模。
这样方法一定要选好合适的p，否则很容易出现同义词。
根据前辈们的经验：若表长为m，通常p为小于或等于表长（最好接近m）的最小质数或不包含小于20质因子的合数。
8.10.6 随机数法
选择一个随机数，取关键字的随机函数值为它的散列地址。也就是f(key) = random(key); 其中random为随机函数。
当关键字长度不等时，采用这个方法构造散列函数是比较合适的。
8.11 处理散列冲突的方法
8.11.1 开放定址法
一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。
8.11.2 再散列函数法
多准备几个散列函数，有冲突了就换另外一个。
8.11.3 链地址法
将所有关键字为同义词的记录存储在一个单链表中，我们称这种表为同义词子表。
8.11.4 公共溢出区法
为所有冲突的关键字建立一个公共的溢出区来存放。
查询的时候现在基本表中查询，查不到就去溢出表中进行顺序查找。
适合相对于基本表来说冲突数据很少的情况。
8.12 散列表的查找实现
8.12.2.查找性能分析
1）如果没有冲突，效率是最高的，时间复杂度是O(1)
实际应用中冲突是不可避免的，那么散列查找的平均查找长度取决于什么呢：
1.散列函数是否均匀：散列函数的好坏直接影响着出现冲突的频繁程度
2.处理冲突的方法：线性探测处理冲突可能会产生堆积，显然没有二次探测法好。而链地址处理冲突不会产生任何堆积，因而具有更加的平均查找性能
3.散列表的装填因子： a = 填入表中记录个数/散列表长度。a越大冲突的可能性就越大。散列表中的平均查找长度取决于装填因子，而不是取决于查找集合中的记录个数。
补充：
哈希冲突主要与两个因素有关：
1）填装因子：（指哈希表中已存入的数据元素个数n与哈希地址空间的大小m的比值， a = n/m; a越小，冲突的可能性越小，但是空间利用率也会越小）。为了兼顾哈希冲突和存储空间利用率，通常将a控制在0.6 – 0.9 之间。
2）与所用的哈希函数有关：如果哈希函数得当，就可以使哈希地址尽可能的均匀分布在哈希地址空间上。
例子：下面是一个哈希表的例子：
/* 作者：xcywt 时间：2018-02-01 说明：这里实现了一个简单的哈希表的操作，包括创建、插入、查询、删除 构造哈希表的方法是：除留取余法 f(key) = key mod p (p <= m); 其中m为散列表长 处理冲突的方法用的是：开放定址法 补充： 常用的构造方法：直接定址法、数字分析法、平方取中法、折叠法、除留取余法、随机数法 常用的处理冲突：开放定址法、再散列函数法、链地址法、公共溢出区法 */ #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXSIZE 100 // 哈希表中总容量 #define NULLKEY -1 // 表示无效的key typedef struct _HS { int key; char data[16]; // 这里用来存其他数据的。 }HashTable; int g_haskmod = 0; int Hash(int key) { return key % g_haskmod; } // 初始化哈希表 void InitHS(HashTable *hs, int len) { int i = 0; for(i = 0; i < len; i++) { hs[i].key = NULLKEY; memset(&hs[i].data, 0, sizeof(hs[i].data)); } } // 往哈希表中插入key int InsertHS(HashTable *hs, int len, int key) { int index = Hash(key); while(len--) { if(hs[index].key == NULLKEY) { hs[index].key = key; itoa(key, hs[index].data, 10); //printf("insert succedd, hs[%d].data = %s\n", index, hs[index].data); break; } else { //printf("confict, key:%d, index:%d +++ \n", key, index); index = (index + 1)%g_haskmod; // 开放定址法的线性探测 //printf("confict, key:%d, index:%d --- \n", key, index); } } return -1; } //查找key， 返回key在哈希表中的位置 int SearchHS(HashTable *hs, int len, int key) { int index = Hash(key); while(len--) { if((hs[index].key == NULLKEY) || (hs[index].key != key)) { index = (index + 1)%g_haskmod; } else { //printf("Search success. key:%d hs[%d].data = %s\n", key, index, hs[index].data); return index; } } printf("Search key:[%d] failed\n", key); return -1; } // 从哈希表中删除key int DeleteHS(HashTable *hs, int len, int key) { int index = SearchHS(hs, len, key); if(index == -1) { printf("DeleteHS key:[%d] failed\n", key); return -1; } // 找到了位置 hs[index].key = NULLKEY; memset(&hs[index].data, 0, sizeof(hs[index].data)); printf("delete [%d] success\n", key); return -1; } // 打印哈希表中的数据 void DisplayHS(HashTable *hs, int len) { printf("Display HashTable:\n"); int i = 0; for(i = 0; i < len; i++) { if(hs[i].key == NULLKEY) continue; printf(" hs[%d].key = %d, hs[%d].data = %s\n", i, hs[i].key, i, hs[i].data); } } int fun() { HashTable hs[MAXSIZE]; // 表的容量是 MAXSIZE InitHS(hs, MAXSIZE); int arr[] = {35, 48, 43, 15, 98, 115, 20, 7, 69, 57, 79, 81, 1, 21, 545, 1000, 99}; int i = 0, arrlen = sizeof(arr)/sizeof(int); printf("arrlen = %d\n", arrlen); g_haskmod = arrlen; for(i = 0; i < arrlen; i++) { InsertHS(hs, MAXSIZE, arr[i]); } DisplayHS(hs, MAXSIZE); SearchHS(hs, MAXSIZE, 35); SearchHS(hs, MAXSIZE, 79); SearchHS(hs, MAXSIZE, 81); SearchHS(hs, MAXSIZE, 32); DeleteHS(hs, MAXSIZE, 81); DeleteHS(hs, MAXSIZE, 81); DisplayHS(hs, MAXSIZE); return 0; } #endif int main() { fun(); return 0; }
