分享
 
 
 

第九章 查找 题解

王朝other·作者佚名  2008-06-01
窄屏简体版  字體: |||超大  

第九章 查找

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.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; /*块的数目

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

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有