第九章 查找（参考答案）.doc

第九章 查找（参考答案） 9.1 int seqsearch( rectype r[], keytype k) // 监视哨设在n个元素的升序顺序表低下标端，顺序查找关键字为k的数据 // 元素。若存在，则返回其在顺序表中的位置，否则，返回0 r[0].key=k; i=n; while (r[i].keyk) i--; if (i0 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-freqp-freq) q=q-prior; // 找p结点位置 q-next-prior=p; // 将p结点插入链表 p-next=q-next; p-prior=q; q-next=p; } // 算法结束 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].freqfreq) { L[i].freq=L[l-1].freq; i--; } L[i+1].freq=freq; } } // 算法结束 9.3 注：判定树中的编号为元素在有序表中的序号 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].keyk ) return binsearch(s,mid+1,high,k); else if (s[mi].keyk 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) // 二叉排序树不空 且关键字不等