数据结构的查找问题

一、

1、查找表，是由同一类型的数据元素（或记录）构成的集合；关键字，key是数据元素中某个数据项的值，又称为键值；也可以标识一个记录的某个数据项（字段），称为关键码；若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；对于那些可以识别多个数据元素或记录的关键字，称为次关键字；

2、查找表按照操作方式可分为静态查找表和动态查找

静态查找表，只作查找操作的查找表，主要操作有（1）：查询某个特定的额数据元素是否在查找表中；（2）：检索某个特定的数据元素和各种属性；

动态查找表，在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素；即查找时插入或删除；

二、顺序表查找

1、顺序表查找，也叫线性查找，查找过程是从表中第一个（或最后一个）记录开始，逐个进行记录的关键字和给定值比较，若某个记录的关键字和给定值相等，则查找成功，找到所查的记录；如果知道最后一个记录，其关键字和给定值比较都不等时，则表中没有所查的记录，查找不成功。

三、有序表查找

1、二分查找，前提是线性表中的记录必须是关键码有序，线性表必须采用顺序存储；二分查找的基本思想：在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键字相等，则查找成功；若给定值小于中间记录的关键字，则在中间记录的左半区继续查找；若给定值大于中间记录的关键字，则在中间记录的右半区继续查找；不断重复上述过程，直到查找成功，或所有查找区域无记录，查找失败为止；

2、插值查找，根据要查找的关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式

low+(key-a[low])*(high-low)/(a[high]-a[low])

3、斐波那契查找

四、线性索引查找

1、索引，就是把一个关键字与它对应的记录相关联的过程；

2、线性索引，就是将索引项集合组织为线性结构，也成为索引表；

3、稠密索引，指在线性索引中，将数据集中的每个记录对应一个索引项；对于稠密索引这个索引表来说，索引项一定是按照关键码有序的排列；

4、分块索引：

分块有序，就是把数据集的记录分成了若干块，并且这些块需要满足两个条件：块内无序和块间有序；每块对应一个索引项；

5、分块索引的索引项结构分为三个数据项：最大关键码，存储每一块中的最大关键字；块中的记录个数，用于指向块首数据元素的指针；

6、倒排索引，索引项的通用结构是：次关键码和记录号表；

其中记录号表存储具有相同次关键字的所有记录的记录号（可以是指向记录的指针或者是该记录的主关键字）

五、二叉排序树

1、二叉排序树也就是二叉查找树，或者是一棵空树，或者是具有以下性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树；

六、平衡二叉树AVL

1、平衡二叉树是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1；

2、将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF；

3、距离插入结点最近的，且平衡因子的绝对值大于1的结点为根的子树，称为最小不平衡子树；

七、多路查找树（B树）

1、多路查找树，其每一个结点的孩子数可以多于两个，且每一个结点出可以存储多个元素；

2、2-3树，一种多路查找树，其中的每一个结点都具有两个孩子或三个孩子；一个2结点包含一个元素和两个孩子（或没有孩子），且与二叉排序树类似；一个3结点包含一小一大两个元素和三个孩子（或没有孩子）；

3、2-3-4树，一个4结点包含小中大三个元素和四个孩子（或没有孩子），一个4结点要么没有孩子，要么具有4个孩子；如果某个4结点有孩子的话，左子树包含小于最小元素的元素，第二子树包含大于最小元素，小于第二元素的元素；第三子树包含大于第二元素，小于最大元素的元素；右子树包含大于最大元素的元素；

4、B树（B-tree）是一种平衡的多路查找树，2-3树和2-3-4树都是B树的特例；

结点最大的孩子数目称为B树的阶；因此，2-3树是3阶B树，2-3-4树是4阶B树；

5、一个m阶的B树具有如下属性：

如果根结点不是叶节点，则其至少有两棵子树；

每一个非根的分支结点都有k-1个元素和k个孩子；其中m/2向上取整<=k<=m；每一个叶子结点n都有k-1个元素；

所有叶子结点都位于同一层次；

所有分支结点包含下列信息数据（n,A0,K1,A1,…Kn,An），其中Ki为关键字，且

Ki<Ki+1

;Ai为指向子树根结点的指针，且指针Ai-1所指子树中所有结点的关键字均小于Ki，An所指子树中所有结点的关键字均大于Kn，n*（m/2向上取整<=n<=m-1）为关键字的个数（或n+1为子树的个数）；

6、B+树，出现在分支结点中的元素会被当做它们在该分支结点位置的中序后继者（叶子结点）中再次列出；另外，每一个叶子结点都会保存一个指向后一叶子结点的指针；

7、一棵m阶的B+树和m阶的B树的差异在于：

有n棵子树的结点中包含有n个关键字；

所有的叶子结点包含全部关键字的信息，及指向含这些关键字记录的指针，叶子结点本身依关键字的大小自小而大顺序链接；

所有分支结点可以看成是索引，结点中仅含有其子树中的最大（或最小）关键字；

八、散列表查找（哈希表）概述

1、散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f，使得每个关键字key对应一个存储位置f(key)；其中对应关系f称为散列函数，又称为哈希（hash）函数；

采用散列结束将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表（hash table）；关键字对应的记录存储位置称为散列地址；

2、在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录；

当查找记录时，通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录；

散列技术既是一种存储方法，也是一种查找方法；

3、两个关键字key1不等于key2,但是却有f(key1)=f(key2)，这种现象称为冲突，并把key1和key2称为这个散列函数的同义词；

九、散列函数的构造方法

1、好的散列函数：计算简单，散列地址分布均匀；

2、直接定址法：取关键字的某个线性函数值为散列地址f(key)=a*key+b;

3、数字分析法：对数字进行一定左移、右移或旋转

4、平方取中法：平方，取平方数中间三位数

5、折叠法：将关键字从左到右分割成位数相等的几部分（注意最后一部分位数不够时可以短些），然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址；

6、除留余数法：f(key)=key mod p (p<=m)

7、随机法：f(key)=random (key);

十、处理散列冲突的方法

1、开放定址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入；

f(key)=(f(key)+d) mod m

;

这种解决冲突的开放定址法称为线性探测法；

2、本来都不是同义词却需要争夺一个地址的情况称为堆积

3、增加平方运算的目的是为了不让关键字都聚集在某一块区域，称为二次探测法

fi(key)=(f(key)+di) mod m (di=1^2,-1^2,2^2,-2^2,...,q^2,-q^2,q<=m/2)
           

4、在冲突时，对于位移量di采用随机函数计算得到，称之为随机探测法；

5、再散列函数法：用多个散列函数，每当发生散列地址冲突时就换一个散列函数计算；

6、链地址法：将所有关键字为同义词的记录存储在一个单链表中，称这种表为同义词子表；

7、公共溢出区法：为所有冲突的关键字建立一个公共的溢出区来存放；

十一、散列表查找实现

1、性能：

散列函数是否均匀；

处理冲突的方法；

散列表的装填因子=填入表中的记录个数/散列表长度；