}
if (i
29若采用除余法作为散列函数,线性探查解决冲突,则9.4.4节中通用的散列表查找算法可改写为对线性探查专用的查找算法:
int HashSearch(HashTable T,KeyType K,int *pos){ int i=0;//记录探查次数
*pos=K%m; //散列函数值作为第一个散列地址 while(i++ if(T[*pos].key==K) return 1;//查找成功返回 if(T[*pos].key==NIL) return 0;//查找失败返回 *pos=(*pos+1)%m;//用线性探查法求下一个探查地址 } return -1;//查找失败,且表满 }//HashSearch 假设散列表上的删除操作已将结点的关键字标记为DELETED(例如,不妨设DELETED为-2)。请修改上述散列表上的查找算法及插入算法HashInsert,使之能正确地查找和插入。 解: (1)查找算法 #define DELETED -2 #define NIL -1 //空结点标记依赖于关键字类型,本节假定关键字均为非负整数 #define M 997 //表长度依赖于应用,但一般应根据。确定m为一素数 typedef struct{ //散列表结点类型 KeyType key; InfoType otherinfo; //此类依赖于应用 }NodeType; typedef NodeType HashTable[m]; //散列表类型 int HashSearch(HashTable T,KeyType K,int *pos){ int i=0;//记录探查次数 *pos=K%m; //散列函数值作为第一个散列地址 while(i++ if(T[*pos].key==K) return 1;//查找成功返回 if(T[*pos].key==NIL) return 0;//查找失败返回 *pos=(*pos+1)%m;//用线性探查法求下一个探查地址 } return -1;//查找失败,且表满 }//HashSearch (2)插入算法HashInsert int HashInsert(HashTable T,KeyType K){ //返回1,表示表中已有k,返回0表示正常插入,返回-1表示插入失败 int i=0;//记录探查次数 int j=-1;//记录DELETED的位置 int pos=K%m; //散列函数值作为第一个散列地址 while(i++ if(T[pos].key==K) return 1;//查找成功返回 if(T[pos].key==NIL) {if (j==-1) T[pos].key=K;//查找失败,插入 else T[j].key=K;//插入到被删除元素留出的位置 return 0; }//正常插入 if(T[pos].key==DELETED) if (j==-1) j=pos; pos=(pos+1)%m;//用线性探查法求下一个探查地址 } return -1;//查找失败,且表满 } 30用拉链法解决冲突,有关的类型说明和插入算法如下,请据此写出散列表的建表、查找及删除算法。 typedef struct node{ KeyType key;//关键字 InfoType Otherinfo;//以下不处理此域 struct node *next;//链域 }CNodeType; typedef CNodeType *CHashTable[m];//散列表类型是一个指针数组 void ChainHashInsert(CHashTable T,KeyType K){ //将关键字K插入表T中,设散列函数为h(K)=K%m CNodeType *p; int addr; p=ChainHashSearch(T,K);//在T中查找有无关键字为K的结点 if (p) printf(\关键字已存在 else {//申请一个新结点,将其关键字置为K,并插入相应链表的头上 addr=K%m;//求散列函数值作为散列地址 p=(CNodeType *)malloc(sizeof(CNodeType)); p->key=K;p->next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部 }//endif }//ChainHashInsert 解: (1)建表 void ChainHashCreat(CHashTable T){ //设散列函数为h(K)=K%m,建立以拉链法为解决冲突方法的散列表 CNodeType *p; int addr; int i; KeyType K; for(i=0;i while (K)//设输入的数据以0结束 { p=ChainHashSearch(T,K);//在T中查找有无关键字为K的结点 if (p) printf(\关键字已存在 else {//申请一个新结点,将其关键字置为K,并插入相应链表的头上 addr=K%m;//求散列函数值作为散列地址 p=(CNodeType *)malloc(sizeof(CNodeType)); p->key=K;p->next=T[addr];T[addr]=p;//将*p插入链表T[addr]的头部 }//endif scanf(\ }//endwhile }//ChainHashCreat (2)查找 CNodeType ChainHashSearch(CHashTable T,KeyType K) {//查找关键字值为K的结点,若有返回该结点指针,否则返回NULL CNodeType *p; int addr; addr=K%m;//求散列函数值 p=T[addr]; while (p)&&(p->key!=K) p=p->next; return p; } (3)删除 CNodeType ChainHashDelete(CHashTable T,KeyType K) {//删除关键字值为K的结点,若有返回该结点指针,否则返回NULL CNodeType *p,*q; int addr; addr=K%m;//求散列函数值 p=T[addr]; if (p)&&(p->key==K) T[addr]=p->next;//要删的是 T[addr]表的第一个结点 while (p->next)&&(p->next->key!=K) p=p->next; if (p->next) {q=p;p=p->next;q->next=p->next;//删除p} return p; }