第九章 查找.txt

严蔚敏《数据结构(c语言版)习题集》 参考答案

第九章 查找  

 


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].key<key) return ERROR;
　return i;
}//Search_Sq
分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.

9.26

int Search_Bin_Recursive(SSTable ST,int key,int low,int 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

int Locate_Bin(SSTable ST,int key)//折半查找,返回小于或等于待查元素的最后一个结点号
{
　int *r;
　r=ST.elem;
　if(key<r.key) return 0;
　else 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&&key<r[mid+1].key) //查找结束的条件
　　　return mid;
　　else if(key<r[mid].key) high=mid;
　　else low=mid;
　} //本算法不存在查找失败的情况,不需要return 0;
}//Locate_Bin

9.28

typedef struct {
　　　　　　 　　　　int maxkey;
　　　　　　　　　　 int firstloc;
　　　　　　　　　 } Index;

typedef struct {
　　　　　　　　　　 int *elem;
　　　　　　　　　　int length;
　　　　　　　　　　Index idx[MAXBLOCK]; //每块起始位置和最大元素,其中idx[0]不利用,其内容初始化为{0,0}以利于折半查找
　　　　　　  　　　 int blknum; //块的数目
　　　　　　　  　 } IdxSqList; //索引顺序表类型

int Search_IdxSeq(IdxSqList 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--); //顺序查找
　L.elem[i-1]=temp; //恢复元素
　if(k<i) return ERROR; //未找到
　return k;
}//Search_IdxSeq
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻元素,以免数据丢失.

9.29

typedef struct {
　　　　　　　　  　 LNode *h; //h指向最小元素
　　　　　　　　  　 LNode *t; //t指向上次查找的结点
　　　　　　　　  } CSList;

LNode *Search_CSList(CSList &L,int 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 {
　　　　　　 　　　　DLNode *pre;
　　　　　　　　　　 int data;
　　　　  　　　　　 DLNode *next;
　　　　　　　　  } DLNode;

typedef struct {
　　　　　　　　　　 DLNode *sp;
　　　　　  　　　　 int length;
　　　　　　　　  } DSList; //供查找的双向循环链表类型

DLNode *Search_DSList(DSList &L,int key)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功
{
　p=L.sp;
　if(p->data>key)
　{
　　while(p->data>key) p=p->pre;
　　L.sp=p;
　}
　else if(p->data<key)
　{
　　while(p->data<key) p=p->next;
　　L.sp=p;
　}
　return p;
}//Search_DSList
分析:本题的平均查找长度与上一题相同,也是n/3.

9.31

int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0
{
　if(T->lchild&&flag) Is_BSTree(T->lchild);
　if(T->data<last) flag=0; //与其中序前驱相比较
　last=T->data;
　if(T->rchild&&flag) Is_BSTree(T->rchild);
　return flag;
}//Is_BSTree

9.32

int last=0;

void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
　if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
　if(last<x&&T->data>=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);
}//MaxLT_MinGT

9.33

void Print_NLT(BiTree T,int x)//从大到小输出二叉排序树T中所有不小于x的元素
{
　if(T->rchild) Print_NLT(T->rchild,x);
　if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
　printf("%d\n",T->data);
　if(T->lchild) Print_NLT(T->lchild,x); //先右后左的中序遍历
}//Print_NLT

9.34

void Delete_NLT(BiTree &T,int x)//删除二叉排序树T中所有不小于x元素结点,并释放空间
{
　if(T->rchild) Delete_NLT(T->rchild,x);
　if(T->data<x) exit(); //当遇到小于x的元素时立即结束运行
　q=T;
　T=T->lchild;
　free(q); //如果树根不小于x,则删除树根,并以左子树的根作为新的树根
　if(T) Delete_NLT(T,x); //继续在左子树中执行算法
}//Delete_NLT

9.35

void Print_Between(BiThrTree T,int a,int b)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素
{
　p=T;
　while(!p->ltag) p=p->lchild; //找到最小元素
　while(p&&p->data<b)
　{
　　if(p->data>a) printf("%d\n",p->data); //输出符合条件的元素
　　if(p->rtag) p=p->rtag;
　　else
　　{
　　　p=p->rchild;
　　　while(!p->ltag) p=p->lchild;
　　} //转到中序后继
　}//while
}//Print_Between

9.36

void BSTree_Insert_Key(BiThrTree &T,int x)//在后继线索二叉排序树T中插入元素x
{
　if(T->data<x) //插入到右侧
　{
　　if(T->rtag) //T没有右子树时,作为右孩子插入
　　{
　　　p=T->rchild;
　　　q=(BiThrNode*)malloc(sizeof(BiThrNode));
　　　q->data=x;
　　　T->rchild=q;T->rtag=0;
　　　q->rtag=1;q->rchild=p; //修改原线索
　　}
　　else BSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中
　}//if
　else if(T->data>x) //插入到左子树中
　{
　　if(!T->lchild) //T没有左子树时,作为左孩子插入
　　{
　　　q=(BiThrNode*)malloc(sizeof(BiThrNode));
　　　q->data=x;
　　　T->lchild=q;
　　　q->rtag=1;q->rchild=T; //修改自身的线索
　　}
　　else BSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中
　}//if
}//BSTree_Insert_Key

9.37

Status BSTree_Delete_key(BiThrTree &T,int x)//在后继线索二叉排序树T中删除元素x
{
　BTNode *pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继
　p=T;last=NULL; //last始终指向当前结点p的前一个(前驱)
　while(!p->ltag) p=p->lchild; //找到中序起始元素
　while(p)
　{
　　if(p->data==x) //找到了元素x结点
　　{
　　　pre=last;
　　　ptr=p;
　　}
　　else if(last&&last->data==x) suc=p; //找到了x的后继