散列表上的运算

散列表上的运算

    　散列表上的运算有查找、插入和删除。其中主要是查找，这是因为散列表的目的主要是用于快速查找，且插入和删除均要用到查找操作。

1、散列表类型说明：
#define NIL -1 //空结点标记依赖于关键字类型，本节假定关键字均为非负整数
#define M 997 //表长度依赖于应用，但一般应根据。确定m为一素数
typedef struct{ //散列表结点类型
KeyType key；
InfoType otherinfo； //此类依赖于应用
}NodeType；
typedef NodeType HashTable[m]； //散列表类型

2、基于开放地址法的查找算法
    　散列表的查找过程和建表过程相似。假设给定的值为K，根据建表时设定的散列函数h，计算出散列地址h(K)，若表中该地址单元为空，则查找失败；否则将该地址中的结点与给定值K比较。若相等则查找成功，否则按建表时设定的处理冲突的方法找下一个地址。如此反复下去，直到某个地址单元为空(查找失败)或者关键字比较相等(查找成功)为止。

（1）开放地址法一般形式的函数表示
int Hash(KeyType k，int i)
   { //求在散列表T[0..m-1]中第i次探查的散列地址hi，0≤i≤m-1
    //下面的h是散列函数。Increment是求增量序列的函数，它依赖于解决冲突的方法
     return(h(K)+Increment(i))％m； //Increment(i)相当于是d_i
   }
    若散列函数用除余法构造，并假设使用线性探查的开放定址法处理冲突，则上述函数中的h(K)和Increment(i)可定义为：
int h(KeyType K){ //用除余法求K的散列地址
    return K％m；
}

int Increment(int i){//用线性探查法求第i个增量d_i
    return i; //若用二次探查法，则返回i*i
   }