查找成功时的平均查找长度
查找不成功时的平均查找长度
http://www.doc88.com/p-903238204265.html

	

“ 查找--比较淡然的一章。”
主要知识点
查找表的检索机制
平均查找长度
折半查找表
二叉排序树
哈希表
1 查找表的检索机制
本章给出了三种类型的查找表，
第一类是线性索引，记录关键字一般按序排列，以提高检索速度。对应检索采用基于比较检索方法。
第二类是树形检索，树形的典型结构是二叉排序树，其检索的时间复杂度与树的深度同级为对数函数，其对应的检索方法是基于树表式的检索，即将带查找的表组织成树，在树形结构上实现查找。
第三类是哈希结构，根据数据的”关键值”计算数据的存储地址，哈希表既是建立表，也是查找表的方法，其对应的检索方式是”计算式”的检索。
2 平均查找长度
为决定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。
计算平均查找长度的基本公式
    对于长度为n的列表，查找成功时的平均查找长度为：
         ASL=P1C1 + P2C2  +……+PnCn =∑ pici
    其中pi为查找列表中第i个数据元素的概率。Ci找到列表中第i二个数据元素时，已经进行过的关键字比较次数。
计算方法：
采用公式法计算(通用)，也可采用手工计算方法(具体)。针对实际的具体问题计算相应的查找成功时的平均差查找长度。
3 折半查找表
    折半查找法要求查找表按照顺序存储结构且按关键字有序排列。
    折半查找过程中借助于折半判定树加以描述。判定树中每一结点对应表中一个记录在表中的位置序号。
    折半查找算法的性能：在等概率时查找成功的平均查找长度与折半判定树的深度相关：
    折半查找算法查找速度快，平均性能好，插入删除比较困难。

                                               4  二叉排序树
    二叉排序树的定义。
    二叉排序树的性质：中序遍历一个二叉排序树，可以得到一个递增有序序列。
    含有n个节点的二叉排序树形态不唯一，其构造与数列的的输入顺序有关。
    查找过程与折半查找过程类似，在二叉排序树中查找一个记录时，其比较次数不超过树的深度。就平均性能而言，二叉排序树上的查找和折半查找相差不大。平均查找长度依然是
    二叉排序树的插入，删除操作无需移动大量结点，经常变化的动态表也采用二叉排序树结构。
5 哈希表
    基本思想：以元素的关键字k为自变量，通过哈希函数h，计算其存储位置p=H(k)，从而实现按照关键字计算的方式建立表与查找表。哈希表的查找过程与还是表的创建过程对应一致。
    哈希法主要包括1)哈希函数的构造，2)处理冲突的方法，
    构造哈希函数，常用的方法有除留余数法。
    处理冲突的基本方法包括性探测再散列，二次探测再散列，链地址法等。
    哈希表中影响关键字比较次数的因素有三个：哈希函数，处理冲突的方法以及哈希表的装填因子。
    哈希表的平均查找长度是装填因子的函数。
【例题1】1000个记录设计哈希表.假设哈希函数是均匀的，解决冲突用线性探测再散列法，并要求在等概率的情况下查找成功时的平均查找长度不超过3，查找不成功时的平均查找长度不超过13，则哈希表长度应取多大？
解：本题要求应用公式计算平均查找长度。
已知哈希函数是均匀的，且解决冲突用线性探测再散列法时，在等概率的情况下查找成功和查找不成功时的平均查找长度为
依题意有：
解的a<=0.8.取a=0.8，由于0.8=1000/m，所以m=1250
【例题2】对以下关键字序列建立哈希表：(SUN,MON,TUE,WED,THU,FRI,SAT),哈希函数为H(K)=(K中第一个字母在字母表中的序号)MOD 7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率情况下，查找成功的平均查找长度和不成功的平均查找长。
解：此题主要要求掌握手工计算平均查找长度的方法，
装填因子为0.7，根据公式，装填因子 = 元素个数/表长，知哈希表长度为=7/0.7=10.
各关键字第一个字母的序号分别为19(S)，13(M)，20(T),23(W)，6(F)。
建立哈希表,   成功的平均查找长度,      不成功的平均查找长度
计算各关键字的哈希地址
H(SUN)=19mod7=5;
H(MON)=13mod7=6;H(TUE)=19mod7=6;
H1(TUE)=(6+1)mod10=7;
H(WED)=23mod7=2;
H(THU)=20mod7=6   (与MON冲突)
H1(THU)=(6+1)mod10=7; (与TUE冲突)
H2(THU)=(6+2)mod10=8;
H(FRI)=6mod7=6; (与MON冲突)
H1(FRI)=(6+1)mod10=7; (与TUE冲突)
H2(FRI)=(6+2)mod10=8; (与TUE冲突)
H3(FRI)=(6+3)mod10=9;
H(SAT)=19mod7=5; (与SUN冲突)
H1(SAT)=(5+1)mod10=6; (与MON冲突)
H2(SAT)=(5+2)mod10=7; (与TUE冲突)
H3(SAT)=(5+3)mod10=8; (与THU冲突)
H4(SAT)=(5+4)mod10=9; (与FRI冲突)
H5(SAT)=(5+15)mod10=0;
由上可得构造哈希表：
0
1
2
3
4
5
6
7
8
9
SAT
WED
SUN
MON
TUE
THU
FRI
6
1
1
1
2
3
4
按查找成功的平均查找长度：
对于SUN,查找时所需的比较次数为1
对于MON,查找时所需的比较次数为1
对于TUE,查找时所需的比较次数为2
对于WED,查找时所需的比较次数为1
对于THU,查找时所需的比较次数为3
对于FRI,查找时所需的比较次数为4
对于SAT,查找时所需的比较次数为6
根据等概率下查找成功的平均查找长度计算公式可得
计算查找不成功的平均查找长度：
哈希函数值为0时，查找不成功时的比较次数为2
哈希函数值为1时，查找不成功时的比较次数为1
哈希函数值为2时，查找不成功时的比较次数为2
哈希函数值为3时，查找不成功时的比较次数为1
哈希函数值为4时，查找不成功时的比较次数为1
哈希函数值为5时，查找不成功时的比较次数为7
哈希函数值为6时，查找不成功时的比较次数为6
由等概率下查找不成功的平均查找长度计算公式得:
【例题3】已知某哈希表的装填因子小于1，哈希函数H(key)为关键字(标识符)的第一个字母在字母表当中的序号，处理冲突的方法为线性探测开放定址法。
一， 编写按第一个字母的顺序输出哈希表中所有关键字的算法。
二，编写模拟手工计算等的概率情况下查找不成功的平均查找长度算法。
实现步骤：
1 对字母序号为i，可先从该字母序号位置开始判断该处所存的关键词是否为i；
2 如果相同，则表示该关键词为与序号i对应的关键字，输出该值；
3 若不同，则表示该关键词并非为字母序号i对应的关键字，不输出；
4 按线性探测开放定址法继续判断下一个关键词，直到值为空；
5 字母序号从1到26，持续上述步骤，则可得  个按字母序号输出的所有关键字序列。
void printword(HsahTable ht)  {  int i,j;  for(i=1;i<=26;i++)// 字母序号从1-》26输出所有关键字序列    {      j=1;// 从字母序号为i的位置开始判断      while(ht[j].key !=NULLKEY)        {          if(hash(ht[j].key == i)// 若该关键字的哈希地址为i，则输出该关键字          printf("%s\n",ht[j].key);          j=(j+1)%m;// 按线性探测处理冲突        }    }}

散列技术时记录的存储位置和它的关键字之间建立的一个确定对应的关系f，使得每个关键字key对应一个存储位置f(key)，查找时根据这个对应的关系找到给定值key的映射f(key)，若查找集合中存储这个记录，则必定在f(key)的位置上。
常见散列方法：
1.直接定址法
其公式为:
2.数字分析法
容易重复分布太集中的某分布均匀，可作为散列地址几个数字，例如电话号码的后四位
3.平法取中法
4.折叠法
折叠法就是将关键字从左到右分割成位数相等的几个部分(注意最后一部分不够可以稍微短些)；然后将部分叠加求和，并按散列表的表长，取后几位作为散列地址。
5.除留余数法
公式：
6.随机数法
公式:
解决散列冲突的方法
开放定址法：一旦发生了冲突，就取寻找下一个空的散列地址，只有散列表足够大，空的散列地址总能找到，并将记录存入
公式:
链地址法:
关键字集合{12，67，56，16，25，37，22，29，15，47，48，34}表长为12，用散列函数
f(key) = key mod 12，得到如下所示:
散列表的查找实现
0.散列表结构和宏设计
typedef int Status;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 //存储空间初始分配量
#define SUCCESS 1
#define UNSUCCESS 0

//定义散列表长为数组的长度
#define HASHSIZE 12
#define NULLKEY -32768

typedef struct
{
    //数据元素存储基址，动态分配数组
    int *elem;
    //当前数据元素个数
    int count;
}HashTable;
int m=0; /* 散列表表长，全局变量 */
1.初始化散列表
// 初始化散列表
Status InitHashTable(HashTable *H)
{
    int i;
    
    //① 设置H.count初始值; 并且开辟m个空间
    m=HASHSIZE;
    H->count=m;
    H->elem=(int *)malloc(m*sizeof(int));
    
    //② 为H.elem[i] 动态数组中的数据置空(-32768)
    for(i=0;i<m;i++)
        H->elem[i]=NULLKEY;
    
    return OK;
}
2.散列函数
// 散列函数
int Hash(int key)
{
    //除留余数法
    return key % m;
}
3.插入关键字进散列表
//插入关键字进散列表
void InsertHash(HashTable *H,int key)
{
    //① 求散列地址
    int addr = Hash(key);
    
    //② 如果不为空，则冲突
    while (H->elem[addr] != NULLKEY)
    {
        //开放定址法的线性探测
        addr = (addr+1) % m;
    }
    
    //③ 直到有空位后插入关键字
    H->elem[addr] = key;
}
4. 散列表查找关键字
// 散列表查找关键字
Status SearchHash(HashTable H,int key,int *addr)
{
    //① 求散列地址
    *addr = Hash(key);
    
    //② 如果不为空，则冲突
    while(H.elem[*addr] != key)
    {
        //③ 开放定址法的线性探测
        *addr = (*addr+1) % m;
        
        //④H.elem[*addr] 等于初始值或者循环有回到了原点.则表示关键字不存在;
        if (H.elem[*addr] == NULLKEY || *addr == Hash(key))
            //则说明关键字不存在
            return UNSUCCESS;
    }
    
    return SUCCESS;
}
使用和打印
int arr[HASHSIZE]={12,67,56,16,25,37,22,29,15,47
int i,p,key,result;
HashTable H;
//1.初始化散列表
InitHashTable(&H);
//2.向散列表中插入数据
for(i=0;i<m;i++)
    InsertHash(&H,arr[i]);
//3.在散列表查找key=39
key=39;
result=SearchHash(H,key,&p);
if (result)
    printf("查找 %d 的地址为：%d n",key,p);
else
    printf("查找 %d 失败。n",key);
//4.将数组中的key,打印出所有在散列表的存储地址
for(i=0;i<m;i++)
{
    key=arr[i];
    SearchHash(H,key,&p);
    printf("查找 %d 的地址为：%d n",key,p);
}
return 0;

       哈希表的装填因子 α 的定义如下：
                α = 哈希表中元素个数 / 哈希表的长度
       α 可描述哈希表的装满程度。显然，α 越小，发生冲突的可能性越小，而 α 越大，发生冲突的可能性也越大。


手工计算等概率情况下查找 成功 的平均查找长度公式
       规则如下：


ASLsucc＝ 


       其中 Ci 为置入每个元素时所需的比较次数

       例如：已知一组关键字序列（19，14，23，01，68，20，84，27，55，11，10，79）按哈希函数H(key)=key
 % 13 和线性探测处理冲突构造所得哈希表ht[0..15],如图1所示


比较次数：1     2      1      4      3      1      1     3     9      1      1     3

       查找19时，通过计算H（19）= 6,ht[6].key非空且值为19查找成功，则查找关键字19 ，仅需要计算1次地址就可以找到；
       查找14时，通过计算H（14）= 1,ht[1].key非空且值为14查找成功，则查找关键字19 ，仅需要计算1次地址就可以找到；
       查找23时，通过计算H（23）=10，ht[10].key非空且值为23查找成功，则查找关键字23 ，仅需要计算1次地址就可以找到；
       同样,查找关键字68，20，11，均需要计算一次地址就可以找到；
       查找关键字01时，通过计算H（01）=1，ht[1].key非空且值为14≠01,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01，查找成功因此查找关键字01时，需要计算2次地址才可以找到；
       查找关键字55时，通过计算H（55）=3，ht[3].key非空且值为68≠55,则找第一次冲突处理后的地址H1=(3+1)% 13=4,此时，ht[4].key非空且值为27≠55，则找第二次冲突后处理地址H2=(3+2)% 13=5， ht[5].key非空且值为55查找成功，因此查找关键字27时，需要计算3次地址才能找到，同理，查找关键字10，84均需要计算3次地址才能找到；
       查找关键字27时，通过计算H（27）=1，ht[1].key非空且值为14≠27,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01≠27，则找第二次冲突后处理地址H2=(1+2)% 13=3， ht[3].key非空且值为68≠27，则找第三次冲突后处理地址H3=(1+3)% 13=4，ht[4].key非空且值为27，查找成功，因此查找关键字27时，需要计算4次地址才可以找到；
       根据上面的方法，查找关键字79时，通过计算H（79）=1，ht[1].key非空且值为14≠79,则找第一次冲突处理后的地址H1=(1+1)% 13=2,此时，ht[2].key非空且值为01≠79，则找第二次冲突后处理地址H2=(1+2)% 13=3， ht[3].key非空且值为68≠79，则找第三次冲突后处理地址H3=(1+3)% 13=4，ht[4].key非空且值为27≠79，则找第四次冲突后处理地址H4=(1+4)%
 13=5，ht[5].key非空且值为55≠79，则找第五次冲突后处理地址H5=(1+5)% 13=6，ht[6].key非空且值为19≠79则找第六次冲突后处理地址H6=(1+6)% 13=7，ht[7].key非空且值为20≠79，则找第七次冲突后处理地址H7=(1+7)% 13=8，ht[8].key非空且值为84≠79，则找第八次冲突后处理地址H8=(1+8)% 13=9，ht[9].key非空且值为79，查找成功，因此查找关键字79时，需要计算9次地址才可以找到。


       据此计算公式，对如图8.27的哈希表，采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找成功的平均查找长度为:
ASL(12)==2.5
       为便于计算, 在图8.27哈希表下方加注圆圈, 圆圈内表示的是有冲突时的计算次数, 如代表需要一次地址计算就可找到的关键字有6个，依此类推，即可得到计算结果。
同理据此公式, 对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找成功的平均查找长度为：
ASL(12)succ=
 
手工计算在等概率情况下查找 不成功 的平均查找长度公式


查找不成功的情况：(1)  遇到空单元
                               (2)  按解决冲突的方法完全探测一遍后仍未找到。0 -> r-1 个不成功查找的入口，从每个入口进入后，直到确定查找不成功为止，其关键字的比较次数就是与该入口对应的不成功查找长度。
       
规则如下：
ASLunsucc＝ 
       其中Ci为函数取值为 i 时确定查找不成功时比较次数
       据此计算公式，对如图8.27的哈希表，采用线性探测再散列法处理冲突, 计算出在等概率查找的情况下其查找不成功的平均查找长度为:
ASL(13)==6
       同理据此公式,对采用链地址法处理冲突的哈希表例图8.26, 计算出在等概率情况下其查找不成功的平均查找长度为：
ASL(13)unsucc= 
链地址法：