数据结构C语言版 哈希表.doc

《数据结构C语言版 哈希表.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、数据结构C语言版哈希表.txtゅ你不用一上线看见莪在线，就急着隐身，放心。莪不会去缠你。说好的不离不弃现在反而自己却做不到╮/*数据结构C语言版哈希表P259编译环境：Dev-C++4.9.9.2日期：2011年2月15日*/#include#include#defineNULLKEY0//0为无记录标志#defineN10//数据元素个数typedefintKeyType;//设关键字域为整型typedefstruct{KeyTypekey;intord;}ElemType;//数据元素类型//开放定址哈希表的存储结构

2、inthashsize[]={11,19,29,37};//哈希表容量递增表，一个合适的素数序列intm=0;//哈希表表长，全局变量typedefstruct{ElemType*elem;//数据元素存储基址，动态分配数组intcount;//当前数据元素个数intsizeindex;//hashsize[sizeindex]为当前容量}HashTable;#defineSUCCESS1#defineUNSUCCESS0#defineDUPLICATE-1//构造一个空的哈希表intInitHashTable(HashTable*H){inti;(*H).

3、count=0;//当前元素个数为0(*H).sizeindex=0;//初始存储容量为hashsize[0]m=hashsize[0];(*H).elem=(ElemType*)malloc(m*sizeof(ElemType));if(!(*H).elem)exit(0);//存储分配失败for(i=0;i

4、).count=0;(*H).sizeindex=0;}//一个简单的哈希函数(m为表长，全局变量)unsignedHash(KeyTypeK){returnK%m;}//开放定址法处理冲突voidcollision(int*p,intd)//线性探测再散列{*p=(*p+d)%m;}//算法9.17//在开放定址哈希表H中查找关键码为K的元素,若查找成功,以p指示待查数据//元素在表中位置,并返回SUCCESS;否则,以p指示插入位置,并返回UNSUCCESS//c用以计冲突次数，其初值置零，供建表插入时参考。intSearchHash(HashTable

5、H,KeyTypeK,int*p,int*c){*p=Hash(K);//求得哈希地址while(H.elem[*p].key!=NULLKEY&&!(K==H.elem[*p].key)){//该位置中填有记录．并且关键字不相等(*c)++;if(*c

6、}intInsertHash(HashTable*,ElemType);//对函数的声明//重建哈希表voidRecreateHashTable(HashTable*H)//重建哈希表{inti,count=(*H).count;ElemType*p,*elem=(ElemType*)malloc(count*sizeof(ElemType));p=elem;printf("重建哈希表");for(i=0;ikey!=NULLKEY)//该单元有数据*p++=*((*H).e

7、lem+i);(*H).count=0;(*H).sizeindex++;//增大存储容量m=hashsize[(*H).sizeindex];p=(ElemType*)realloc((*H).elem,m*sizeof(ElemType));if(!p)exit(0);//存储分配失败(*H).elem=p;for(i=0;i

8、//算法9.18//查找不成功时插入数据元素e到开放