第八章查找

9.1

(1)无序表：顺序查找不成功时，查找长度为n+1；成功时，平均查找长度为1/(n+1)*(1+2+…+(n+1))=(n+2)/2；两者不相同。

（2）表中只有一个关键字等于给定值k的记录，无序表、有序表：顺序查找成功时，平均查找长度均为1/(n)*(1+2+…+n)=(n+1)/2；两者相同。

（3）表中只有m个关键字等于给定值k的记录，无序表：ASL=n+1；有序表：ASL=（n+1）/2+m；两者不相同。 9.3

5

2 1 3 4

ASL=1/10（1+2*2+4*3+3*4）=2.9 9.11

9.14

6 7 8

9

10 30 20 20 30 20 50 30 52 30 20 50 52 20 50 60 52 30 52 30 68 20 60 68 50 50 20

删除50后

60 70 52 68 20 30 60 70

52 20 30 60 70 删除68后 9.19 22 67 41 30 53 46 13 01 0 1 2 3 4 5 6 7 8 9 10

ASL=（4*1+2*2+3+6）/8=17/8 9.25

int Search-Seq(SSTable ST, KeyType key){

//在顺序表ST中顺序查找其关键字等于key的数据元素，ST按关键字自大至小有序， //若找到，则函数值为该元素在表中的位置，否则为0 ST.elem[ST.length+1].key=key;

for (i=1; ST.elem[i].key>key; ++i);

if (ST.elem[i].key==key)&&(i<=ST.length) return i else return 0 ;

}//Search-Seq 9.31

TelemType Maxv(Bitree T){

//返回二叉排序树T中所有结点的最大值 for (p=T; p->rchild; p=p->rchild); return p->data; }//Maxv

TelemType Minv(Bitree T){

//返回二叉排序树T中所有结点的最小值 for (p=T; p->lchild; p=p->lchild); return p->data; }//Minv

Status IsBST(Bitree T){ //判别T是否为二叉排序树 if (!T) return OK; else if

((!T->lchild)||((T->lchild)&&(IsBST(T->lchild)&&(Maxv(T->lchild)data)))

&&((!T->rchild)||((T->rchild)&&(IsBST(T->rchild)&&(Minv(T->rchild)>T->data)))

return OK else return ERROR;

}//IsBST 9.33

Status OutputGEx(Bitree T, TelemType x){

//从大到小输出给定二叉排序树T中所有值不小于x的数据元素 if (T) {

if (OutputGEx(T->rchild, x)) if (T->data>=x) { print(T->data);

if (OutputGEx(T->lchild, x)) return OK; }

else return OK; }

else return OK; }//OutputGEx

第九章 查找 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

分析:本算法查找成功情况下的平均查找长度为ST.length/2,不成功情况下为ST.length.

9.26

int Search_Bin_Digui(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_Digui(ST,key,low,mid-1);

else return Search_Bin_Digui(ST,key,mid+1,high); }

}//Search_Bin_Digui 9.27

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

int *r;

r=ST.elem;

if(key

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

else if(key

} //本算法不存在查找失败的情况,不需要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

}//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

while(p->datanext; L.sp=p; }

return p;

}//Search_DSList

分析:本题的平均查找长度与上一题相同,也是n/3. 9.31

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库第八章查找在线全文阅读。