第八章查找(3)

void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法 {

for(i=1;i<=26;i++)

for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash

int H(char *s)//求Hash函数 {

if(s) return s[ 0 ]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H 9.45

typedef *LNode[MAXSIZE] CHashTable; //链地址Hash表类型

Status Build_Hash(CHashTable &T,int m)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突. {

if(m<1) return ERROR;

T=malloc(m*sizeof(WORD)); //建立表头指针向量 for(i=0;i

while((key=Inputkey())!=NULL) //假定Inputkey函数用于从键盘输入关键字 {

q=(LNode*)malloc(sizeof(LNode)); q->data=key;q->next=NULL; n=H(key);

if(!T[n]) T[n]=q; //作为链表的第一个结点 else {

for(p=T[n];p->next;p=p->next);

p->next=q; //插入链表尾部.本算法不考虑排序问题. }

}//while return OK; }//Build_Hash 9.46

Status Locate_Hash(HashTable H,int row,int col,KeyType key,int &k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k {

h=2*(100*(row/10)+col/10); //作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1) 000;

if(EQ(H.elem[h].key,key)) k=h; else k=NULL; }//Locate_Hash

分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).

数据结构辅导站 返回主页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第八章查找(3)在线全文阅读。