《数据结构题集》答案第9章查找

1 / 33 第九章查找 9.25 int Search_Sq(SSTable ST,int key在有序表上顺序查找的算法，监视哨设在高 下标端

{ ST.elem[ST.length+1].key=key;

for(i=1;ST.elem[i].key>key;i++); if(i>ST.length||ST.elem[i].keyreturn i; }//Search_Sq 分析:本算法查找成功情况下的平均查找长度为 ST.le ngth/2,不成功情况下为 ST.length.

9.26 int Search_Bin_Recursive(SSTable ST,i nt key,i nt low,i nt high折半查找的递归 算法

{ if(low>high) return 0; // 查找不到时返回 0

mid=(low+high)/2; if(ST.elem[mid].key==key) return mid; else if(ST.elem[mid].key>key) return Search_Bin_Recursive(ST,key,low,mid-1); else return Search_Bin_Recursive(ST,key,mid+1,high); }//Search_Bin_Recursive 9.27 2 / 33

int Locate_Bi n(SSTable ST,i nt key)折半查找返回小于或等于待查元素的最后 一个结点号

{ int *r;

r=ST.elem; if(keyelse if(key>=r[ST.length].key) return ST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2;

if(key>=r[mid].key&&keyif(key

else low=mid; } // 本算法不存在查找失败的情况 ,不需要 return 0; }//Locate_Bin 9.28 typedef struct { int maxkey; int firstloc; } Index; typedef struct { int *elem; 3 / 33

int length; Index idx[MAXBLOCK];/每块起始位置和最大元素，其中idx[O]不利用,其容初 始化为{0 , 0}以利于折半查找 int blknum; //块的数目

} IdxSqList; 〃索引顺序表类型 int Search_ldxSeq(ldxSqList L,int key)分块查找, 用折半查找法确定记录所在块 ,块采用顺序查找法

{ if(key>L.idx[L.blknum].maxkey) return ERROR; /超/ 过最大元素

low=1;high=L.blknum; found=0; while(low<=high&&!found) // 折半查找记录所在块号 mid { mid=(low+high)/2;

if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; else if(key>L.idx[mid].maxkey) low=mid+1; else high=mid-1; } i=L.idx[mid].firstloc; // 块的下界

j=i+blksize-1; // 块的上界 temp=L.elem[i-1]; // 保存相邻元素 L.elem[i-1]=key; // 设置监视哨 for(k=j;L.elem[k]!=key;k--); // 顺序查找 4 / 33

L.elem[i-1]=temp; // 恢复元素 if(kreturn k; }//Search_IdxSeq 分析 :在块进行顺序查找时 ,如果需要设置监视哨 ,则必须先保存相邻块的相邻 元素 ,以免数据丢失 .

9.29 typedef struct { LNode *h; //h 指向最小元素 LNode *t; //t 指向上次查找的结点 } CSList;LNode *Search_CSList(CSList & L,i nt key在有序单循环链表存储结构上的查找算法 ，假定 每次查找都成功

{ if(L.t->data==key) return L.t;

else if(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p; //更新 t 指针 return p; }//Search_CSList 分析 :由于题目中假定每次查找都是成功的 ,所以本算法中没有关于查找失败 的处理 .由微积分可得 ,在等概率情况下 ,平均查找长度约为 n/3.

9.30 typedef struct { 5 / 33

DLNode *pre; int data; DLNode *next; } DLNode; typedef struct { DLNode *sp; int length; } DSList; //供查找的双向循环链表类型 DLNode *Search_DSList(DSList&L,i ntkey)在有序双向循环链表存储结构上的查找算 法,假定每次查找都成功

{ p=L.sp;

if(p->data>key) { while(p->data>key) p=p->pre;

L.sp=p; } else if(p->data

{ while(p->datanext;

L.sp=p; } return p;

}//Search_DSList 6 / 33

分析 :本题的平均查找长度与上一题相同 ,也是 n/3. 9.31 int last=0,flag=1; int ls_BSTree(Bitree T)/判断二叉树T是否二叉排序树，是则返回1,否则返回 0 { if(T->lchild&&flag) ls_BSTree(T->lchild);

if(T->datalast=T->data; if(T->rchild&&flag) ls_BSTree(T->rchild); return flag; }//ls_BSTree 9.32 int last=0;

void MaxLT_MinGT(BiTree T,int x)/找到二叉排序树 T中小于x的最大元素和 大于x的最小元素

{ if(T->lchild)MaxLT_Mi nGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x) //找到了小于x的最大元素

printf("a=%d\n",last); if(last<=x&&T->data>x) //找到了大于x的最小元素 printf("b=%d\n",T->data); last=T->data; if(T->rchild) MaxLT_MinGT(T->rchild,x); 7 / 33

}//MaxLT_MinGT 9.33 void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树 T中所有不小于x的 元素

{ if(T->rchild) Print_NLT(T->rchild,x);

if(T->dataprintf("%d\n",T->data); if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历 }//Print_NLT 9.34 void Delete_NLT(BiTree &T,intx)//删除二叉排序树 T中所有不小于x元素结 点,并释放空间

{ if(T->rchild) Delete_NLT(T->rchild,x);

if(T->dataq=T; T=T->lchild; free(q); //如果树根不小于x,则删除树根，并以左子树的根作为新的树根 if(T)Delete_NLT(T,x); //继续在左子树中执行算法

}//Delete_NLT 9.35 void Prin t_Betwee n(BiThrTree T,i nt a,i nt b)// 打印输出后继线索二叉排序树T 中所有大于 a 且小于 b 的元素

{