中南大学数据结构与算法第9章查找课后作业答案

}

if (ikeynmu)//若刚遍历的子树不是最后一棵子树 printf(\ } }

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; }