发布时间 : 星期二 文章严蔚敏-数据结构集合习题更新完毕开始阅读4410cb09bb68a98271fefaf5
}//结束算法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）；} //找到合适哈希地址，插入