第九章　查找　題解

2019-11-17 05:36:29

字體：大中小

來源：轉載

供稿：網友

　　　　　　　　　　　　　　　　　　　第九章查找
9.25
int Search_Sq(SSTable ST,int key)/*在有序表上順序查找的算法,監(jiān)視哨設在高下標端
{
ST.elem[ST.length+1].key=key;
for(i=1;ST.elem[i].key>key;i++);
if(i>ST.lengthST.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; /*塊的數(shù)目
                   } 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; /*設置監(jiān)視哨
for(k=j;L.elem[k]!=key;k--); /*順序查找
L.elem[i-1]=temp; /*恢復元素
if(k<i) return ERROR; /*未找到
return k;
}/*Search_IdxSeq
分析:在塊內進行順序查找時,假如需要設置監(jiān)視哨,則必須先保存相鄰塊的相鄰元素,以免數(shù)據丟失.
9.29
typedef struct {
                     LNode *h; /*h指向最小元素
                     LNode *t; /*t指向上次查找的結點
                  } CSList;
LNode *Search_CSList(CSList &L,int key)/*在有序單循環(huán)鏈表存儲結構上的查找算法,假定每次查找都成功
{
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; /*供查找的雙向循環(huán)鏈表類型
DLNode *Search_DSList(DSList &L,int key)/*在有序雙向循環(huán)鏈表存儲結構上的查找算法,假定每次查找都成功
{
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); /*本算法仍是借助中序遍歷來實現(xiàn)
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_NL

上一篇：第七章　圖　題解

下一篇：第六章樹和二叉樹題解