}//InOrder
void SaveToDisk()
//将二叉排序树上的各整数按降序写入磁盘 {FILE *fp;
if ((fp=fopen(“file1.dat”, “wb”))==null) {printf(“file can not open!\\n”);exit(0); }
fwrite(a,sizeof (int),n,fp);//将数组a中的n个整数写入磁盘 fclose(fp);//关闭文件 }//SaveToDisk
19．本题的分析同第18题。这里直接写出算法 （1）递归算法
void DecPrint(BSTree t）
//递减序输出二叉排序树t中所有左子树为空右子树非空的结点数据域的值。 {if（t）
{DecPrint(t->rchild)；
if（!t->lchild && t->rchild）printf(t->data：4） DecPrint(t->lchild）； }
}//DecPrint （2）非递归算法
void DecPrint(BSTree t）
// 递减序输出二叉排序树t中所有左子女为空右子女非空的结点的值 {BSTree S[]；//S是二叉排序树结点指针的栈，容量足够大 int top=0；
while（t || top>0） {while（t）
{S[++top]=t；t=t->rchild ；} //沿右分枝向下 if（top>0） {t=S[top--]；
if（!t->lchild && t->rchild）printf(t->data：4)； t=t->lchild； // 去左分枝
}//if
}//while }//算法结束
20．[题目分析]这是一个在单链表中查找结点，在结点内查找给定值的过程，先定义存储结构：
typedef struct node
{int A[m]； //每个结点内含有m个正整数，本例中m为5 struct node *next；//指向下一结点的指针 }LNode，*LinkList； typedef struct
{int j；// 正整数在结点内的序号 struct node *s；// 结点的指针 }rcd;
rcd *LSearch(LinkList head,int n)
//在链表中查找正整数n，若查找成功，返回该结点指针及n在结点中的序号； //否则返回空指针表示失败。 {rcd *R;
P=head->next；// 假定链表带头结点，P指向链表第一元素结点 found=0；
while（P && !found） {for(i=0;i if(P->A[i]==n) found=1 //查找成功 P=P->next; //下一结点 } if（P==null）return （null）； else {R.j=i; R.s=P; return （R）；} }//LSearch 21．int Search（rectype R[]，int n,K） // 在具有n个元素的有序表R中，顺序查找值为K的结点，查找成功返回其位置， //否则返回-1表示失败 {i=0； while（i {if（R[i]==K） return （i）； else if（R[i]>K） return （-1）； i++; }//while return （-1）； }//结束search 在等概率情况下，则查找成功的平均查找长度为（n+1）/2，查找失败的平均查找长度为（n+2）/2（失败位置除小于每一个，还存在大于最后一个）。若查找成功和不成功的概率也相等，则查找成功时和关键字比较的个数的期望值约为(n+1)/4。 22．[题目分析]本题采用中序遍历，将遍历结点与前驱比较，若相同，则不输出并记数。 void BSTPrint(BSTree t,int *count） //递增序输出二叉排序树中结点的值，滤去重复元素 {if（t） {BSTPrint(t->lchild)； //中序遍历左子树 if（pre==null）pre=t; //pre是当前访问结点的前驱,调用本算法时初值为null else if(pre->key==t->key)*count++;//*count记重复元素，调用本算法时初值为0 else {printf（“M”,t->key）；pre=t；} // 前驱后移 BSTPrint(t->rchild)； //中序遍历右子树 }//if }//结束BSTPrint 算法 23．[题目分析]本题算法之一是如上题一样，中序遍历二叉树，在“访问根结点”处判断结点值是否≥x，如是则输出，并记住第一个≥x值结点的指针。这里给出另一个算法，利用二叉排序树的性质，如果根结点的值>=x,则除左分枝中可能有 从根结点开始查找，找到结点值 // 中序输出以t为根的二叉排序树的结点 {if（t）{Print（t->lchild）； printf（t->data：4）； Print（t->rchild）； } } void PrintAllx(BSTree bst，datatype x） //在二叉排序树bst中，查找值≥x的结点并输出 {p=bst； if（p） {while（p && p->data {f=p; p=p->lchild ；//找第一个值 while（p && p->data≥x）//沿左分枝向下，找第一个值 {f=p；p=p->lchild ；} //f是p的双亲结点的指针，且指向第一个值≥x的结点 if(p) f->lchild=null; //双亲与找到的第一个值 Print(bst)；//输出以bst为根的子树 }//while }//内层if（p） }//第一层if（p） }//PrintAllx 24．[题目分析] 因为T是二叉排序树，则可利用二叉排序树的性质，从根往下查找结点*x。若T的左子树为空，则其中序序号为1，否则为T->lchild->size+1。设T的中序序号为r，其左子女p的中序序号和右子女q的中序序号分别为r-p->rchild->size-1和r+q->lchild->size+1。 int Rank（tree T，node *x） // 在二叉排序树T上，求结点x的中序序号 {if（T->lchild）r=T->lchild->size+1；else r=1；//根结点的中序序号 while（T） if（T->key>x->key）//到左子树去查找 {T=T->lchild； if（T）{if（T->rchild）r=r-T->rchild->size-1；else r=r-1；} } else if（T->key if（T）{if（T->lchild）r=r+T->lchild->size+1；else r=r+1；} } else return （r）；//返回*x结点的中序序号 return （0）； //T树上无x结点。 }//结束算法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）；} //找到合适哈希地址，插入