严蔚敏-数据结构集合习题 下载本文

}//结束算法Rank

算法2:本题的另一种解法是设r是以*x为根的中序序号。同样,若x的左子树为空,r=1;否则,r=x->lchild->size+1。利用结点的双亲域,上溯至根结点,即可求得*x的中序序号。

int Rank(tree T,node *x)

// 在二叉排序树T上,求结点x的中序序号

{{if(x->lchild)r=x->lchild->size+1;else r=1;//x的这个序号是暂时的 p=x; //p要上溯至根结点T,求出*x的中序序号 while (p!=T)

{if (p==p->parents->rchild) //p是其双亲的右子女 {if (p->parents->lchild==null) r++; else r=r+p->parent->lchild->size+1; }

else r-- //p是其双亲的左子女 p=p->parents; }//while return (r); }//Rank

25.[题目分析] 本题未直接给出哈希表表长,但已给出装填因子小于1,且哈希函数H(k)为关键字第一个字母在字母表中的序号,字母‘A’的序号为1,表长可设为n(n≥27),而链地址法中,表长26。查找不成功是指碰到空指针为止(另一种观点是空指针不计算比较次数)。

(1)void Print(rectype h[ ])

//按关键字第一个字母在字母表中的顺序输出各关键字 {int i,j;

for(i=0;i≤26;i++) // 哈希地址0到26 {j=1;printf(“\\n”);

while(h[j]!=null) // 设哈希表初始值为null

{if(ord(h[j])==i)// ord()取关键字第一字母在字母表中的序号 printf(“%s”,h[j]);j=(j+1)% n; }}}

(2)int ASLHash(rectype h[ ])

// 求链地址解决冲突的哈希表查找不成功时的平均查找长度 {int i,j;count=0;//记查找不成功的总的次数

LinkedList p;

for(i=0;i≤26;i++)

{p=h[i];j=1;//按我们约定,查找不成功指到空指针为止。 while(p!=null){j++;p=p->next;} count+=j; }

return (count/26.0); }

26.[题目分析]非零元素个数是100,负载因子取0.8,表长125左右,取p为127,散列地址为0到126。哈希函数用H(k)=(3*i+2*j) % 127,i,j为行值和列值。

#define m 127 typedef struct

{int i,j;datatype v;}triple; void CreatHT(triple H[m])

//100个非零元素生成稀疏矩阵的哈希表,表中元素值均初始化为0。 {for(k=0;k<100;k++)

{scanf(&i,&j,&val);//设元素值为整型 h=(3*i+2*j)% m; //计算哈希地址

while(HT[h].v!=0)) h=(h+1) % m; //线性探测哈希地址 HT[h].i=i;HT[h].j=j;HT[h].v=val; //非零元素存入哈希表 }

}//算法CreatHT结束

datatype Search(triple HT[m],int i,int j)

//在哈希表中查找下标为i,j的非零元素,查找成功返回非零元素,否则返回零值。 {int h=(3*i+2*j) % m;

while ((HT[h].i!=i || HT[h].j!=j) && HT[h].v!=0) h=(h+1)% m; return (HT[h].v); }//Search

27.[题目分析] 本题哈希函数H(key),用线性探测解决冲突,空单元用EMPTY,删除标记用DELETED,占用单元用INUSE,其它均符合哈希表标准操作。 (1)int Search(rectype HT[],int m,datatype key) //在长度为m的哈希表HT中查找关键字key,若查找成功,返回true,否则返回false。

{i=H(key); // 计算哈希地址

if(HT[i]==EMPTY)return (false); //查找失败 else if(HT[i]== key)return (true); else {j=(i+1)% m; //形成探测序列 while(j!=i) //至多循环哈希表长

{if(HT[j]==key) return (true); //查找成功 else if(HT[j]==EMPTY)return (false);//查找失败

j=(j+1)% m;

}

return (false);//查遍哈希表,未查到给定关键字key

}//else

//结束Search

(2)int Insert(rectype HT[],int m,datatype key) //在长为m的哈希表中插入关键字key {i=H(key);//计算哈希地址

if(HT[i]==EMPTY || HT[i]==DELETED) //若HT[i]空或删除标记。 {HT[i]=key;return (true);} //插入成功 else //探测插入元素的散列地址 {j=(i+1)% m; while(j!=i)

{if(HT[j]==EMPTY || HT[j]==DELETED)

{HT[j]=key;return (true);} //找到合适哈希地址,插入