temp=r[k]; r[k]=r[i]; r[i]=temp; // r[k]和r[i]交换 c[i]=c[k]; // 将c[k]存入c[i], c[k]=k; // r[k]已是第k个记录 // while (c[i]!=i)
8.15
# define D 10 // 假设每个关键字长度为10 typedef struct
{ char key[D]; // 关键字用字符数组表示 anytype:otheritem; // 元素的其他信息
int next; // 指针域
}rcdnode;
rcdnode r[n]; // 为n个英文单词为关键字的记录排序
int f[27],e[27];
int distribute(int i; int p)
//静态链表r中的记录按key[i+1]，……..，key[D]有序，p指向链表中第一记录。本算法 //第I位关键字key[i]建立子表，同一子表中 的key[i]值相同。f[i]和e[i]分别指向各子表 //中第一个记录和最后一个记录。0<=j<=27，key[i]为空格时，j=0；而key[i]为字母时，j= //该字母的ASCII码-64。f[i]=0表示第j个子表为空 {for(j=0;j<=27;j++) f[j]=0; // 子表初始化为空表 while(p!=0) //p=0表示链表到尾
{if(r[p].key[i]= = ’ ’) j=0;
else j=r[p].key[i]-64; if(f[j]= =0) f[j]=p; else f[e[j]].next=p;
e[j]=p; //将p所指结点插入第j个子表 }p=r[p].next; // p指向下一个元素 } //for
int collet(int i)
// 本算法按key [i]自小到大将f[j]不等于0所指各子表链成一个链表，e[j]为相应子表的尾//指针，，函数返回链接后链表头指针。 {j=0;
while(f[j]= =0) j++; // 找第一个非空子表 p=f[j];t=e[j]; // p为链表头指针 while (j<=27)
{ j++;
while(j<=27&&f[j]= =0) j++; // 找下一个非空子表 if(f[j]!=0) { r[t].next=f[j]; t=e[j]} // 链接两个非空子表 }
r[t].next=0; // 置链表尾 return(p); }//collect
int radixwordsort( )
// n个英文单词为关键字的元素存放在静态链表的数据域中。本算法按基数排序思想对这些//英文字母进行排序。排序后按关键字自小到大升序相链，算法返回指向第一个记录的下标//值。
{ for(i=0;i for(i=d;i>0;i--) {p=distribute(i,p); p=collect(i); } return(p) } 8.16 见8.3 8.17 s=┌logkm┐//s为归并趟数，m为顺串个数，k为归并路数 因为m=100和s=3 所以k>=5，故至少取5路归并即可 第九章 查找（参考答案） 9.1 int seqsearch( rectype r[], keytype k) // 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据 // 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r[0].key=k; i=n; while (r[i].key>k) i--; if (i>0 && r[i].key==k) return(i); else return(0) } // 算法结束 查找过程的判定树是单支树。 查找成功的平均查找长度为 ASL=∑PICI =1/n*∑i = 1/2*(n+1) 查找不成功的平均查找长度为 ASL=1/(n+1)(∑i+(n+1))=(n+2)/2. 9.2 typedef struct lnode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; struct lnode *prior,*next; // 双向链表 }seqlist; typedef struct snode {int freq; // 访问频率域 keytype key; // 关键字 ElemType other; }snode; void locate(seqlist L,keytype X) // 在链表中查找给定值为X的结点，并保持访问频繁的结点在前 //调用本函数前，各结点的访问频率域（freq）值均为0。 {seqlist *p; // p是工作指针 p=L->next; // p指向第一元素 while (p!=null && p->key!=X) p=p->next; // 查找X结点 if (p==null) {printf(“no X”); return; } else {q=p->prior; // q是p的前驱 p->next->prior=p->prior; // 先将p结点从链表中摘下 q->next=p->next; while (q!=L && q->freq } // 算法结束 void locate(snode L[],int n;keytype X) // 在具有n个元素顺序存储的线性表L中查找给定值为X的结点，并保持 // 访问频繁的结点在前。调用本函数前，各结点的访问频率域值为0。 { int i=0, freq; L[n].key=X; // 监视哨 while (L[i].key!=X) i++; if (i==n) {printf(“no X”); return; } else { freq=L[i].freq; while ( L[i-1].freq } // 算法结束 9.3 10 5 15 2 7 12 18 1 3 6 8 11 13 16 19 4 9 14 17 20 注：判定树中的编号为元素在有序表中的序号 9.4 int binsearch(rectype s[],int low,int high, keytype k) // 有序的顺序表s,其元素的低端和高端下标分别为low和 high. // 本算法递归地折半查找关键字为k的数据元素，若存在，则返回其在有序 // 顺序表中的位置，否则，返回0。 { if (low<=high) {mid=(low+high)/2; if (s[mid].key return binsearch(s,mid+1,high,k); else if (s[mi].key>k return(binsearch(s,low,mid-1,k) else return(mid); } else return(0); } // 算法结束 9.5 int level(bstnode *bst, keytype K) // 在二叉排序树bst中，求关键字K所在结点的层次 {bstnode *p; // p为工作指针 int num=0; // 记层数 p=bst; while (p && p->key!=K) // 二叉排序树不空 且关键字不等 if (p->key int level(bstnode *bst, keytype K，int num) // 在二叉排序树中，求关键字K所在结点的层次的递归算法，调用时num=0 {if (bst==null) return 0; else if (bst->key==K) return ++num; else if (bst->key 9.6 bstnode *ancestor(bstnode *bst) // bst是非空二叉排序树根结点的指针。 // A和B是bst树上的两个不同结点，本算法求A和B的最近公共祖先。 // 设A和B的关键字分别为a和b，不失一般性，设a { bstnode *p=bst; if (p->key==a) { printf(“A 是B的祖先。\\n”); return(p); } else if (p->key==b) { printf(“B 是A的祖先。\\n”); return(p); } else if (p-key>a && p->key 9.7 int bstree(bstnode *bst, bstnode *pre) // bst是二叉树根结点的指针,pre总指向当前访问结点的前驱，调用本函数 // 时为null。本算法判断bst是否是二叉排序树。设一全程变量flag,初始值 // 为1，调用本函数后，若仍为1，是二叉排序树，否则，不是二叉排序树。 {if (bst!=null) {bstree(bst->lchild,pre); if (pre==null) pre=bst; else if (pre->key>bst->key) {printf (“非二叉排序树\\n”);flag=0; return 0;} else pre=p; bstree(bst->rchild,pre); } } 9.8（1） DEC NOV ASL=(1*1+2*2+3*3+3*4+2*5+1*6)/12=42/12 JAN FEB MAR APR JUN MAY SEP AUG JUL OCT