第九章查找 925 int Search Sq(ssTable ST, int key )/在有序表上顺序查找的算法,监视哨设在高下 标端 STelem(ST length+1 ].key=key; for(F1; STelem[i]. key>key; i++) if(>ST. lengthIST elem[]. keykey) return ERROR; /ISearch Sq 分析本算法査找成功情况下的平均查找长度为 STrength/2,不成功情况下为 ST length 9.26 int search bin recursive( SSTable ST,int key, int low, int high)折半查找的递归算 i(low>high) retur0,∥查找不到时返回0 mid=-(low+high )/2; if(STelem[mid ]. key==key) return mid else if(STelem(mid ]. key>key) return Search Bin Recursive( st, key, low, mid-1) else return Search Bin Recursive(sT, key, mid+1, high) i //Search Bin Recursive 9.27 Int locate_Bin( SSTable st, int key折半査找,返回小于或等于待查元素的最后 个结点号 int *r STele if(key<r. key )return 0 else if(key>=r[ST length). key) return ST length low=l; high=ST length while (low<=high mid=(low+high)2 if(key>=rmid]key&&key<rmid+1]key)∥查找结束的条件 return mid
第九章 查找 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 }∥本算法不存在査找失败的情况,不需要 return0; 3//Locate Bin 928 typedef struct int mackey int firstloc ypedef struct i int length Index idx MAXBLOCK];∥每块起始位置和最大元素,其 中dx[O不利用,其内容初始化为{0,0}以利于折半查找 int blknun,∥块的数目 } IdxSqList;/索引顺序表类型 int Search IdxSeq( Idxsqlist L, int key )分块査找,用折半査找法确定记录所在块, 块内采用顺序查找法 ikey> L.idx[L blknum] markey) return ErroR;∥超过最大元素 low=l; high=L blknum found=0 whie(ow<high&&! found)∥折半查找记录所在块号md mid=dlow+highT key<=L idx[mid ] maxkey&&key>L idx[mid-1]. maxkey) found=1 else if(key>L idx[ mid mackey) low=mid+ else high=mid-1 i=Ldx[mid] firstloc;/块的下界 j=i计+ blksize-1;∥块的上界 temp=Llem[i-1]∥保存相邻元素 L elem[ill=key,∥设置监视哨 for(k= j, L elem(k!=keyk-),∥顺序查找 L elem[i1}=temp;∥恢复元素 if(ki) return ERROr;∥未找到 eturn k. i//Search IdxSeq
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
分析在块内进行顺序查找时如果需要设置监视哨,则必须先保存相邻块的相邻 元素,以免数据丢失 929 typedef struct i LNode *h;/h指向最小元素 LNode*t;M指向上次查找的结点 i CLIst LNode* Search clist( CLIst& L, int key》在有序单循环链表存储结构上的查找 算法假定每次查找都成功 if(L t->data==key)return Lt else if(L t->data>key) for(p=L h, Fl; p->datal=key P=p->next, i++); else for(p=Lt, i=L tpos p->datal=key: p=p->next, 1++); Lt=p;/更新t指针 eturn p, i//Search CSList 分析由于题目中假定每次查找都是成功的所以本算法中没有关于查找失败的处 理由微积分可得在等概率情况下,平均查找长度约为n/3 9.30 ypedef struct DLNode'pre; DLNode *nex 3 DLNode; typedef struct i DLNode * sp; } DEList;∥供査找的双向循环链表类型 DLNode* Search delist( DEList&L, int key)∥在有序双向循环链表存储结构上的 查找算法,假定每次查找都成功 if(p->data>key) hile(p->data>key) p=p->pre; L sp=p:
分析:在块内进行顺序查找时,如果需要设置监视哨,则必须先保存相邻块的相邻 元素,以免数据丢失. 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 i//Search DSList 分析本题的平均查找长度与上一题相同,也是n3 9.31 int last=0, flag=1 int Is BsTree(Bitree T判断二叉树T是否二叉排序树是则返回1,否则返回0 if(T->lchild &&flag) Is Bs Tree(T->lchild) if(T>data<last)flg=0,∥与其中序前驱相比较 last=T->data if(T->rchild &&flag) Is BsTree(T->rchild) return flag: i//s BSTree 9.32 void malt Mingt( BiTree T, int x)找到二叉排序树T中小于x的最大元素和大 于x的最小元素 if(T-> Lchild) MaxLt MingT(I> Child.x);∥本算法仍是借助中序遍历来实现 if(last<x&&T->data=x)∥找到了小于x的最大元素 printf("a=%d\n",last) idas<=x&&T>data>x)/找到了大于x的最小元素 printf("b=%d n"T->data); last=T->data if(T->rchild) MaxLT MingT(T->rchild, x); i//MaxLT MingT 9.33 void Print nlt( BiTree T int x)从大到小输出二叉排序树T中所有不小于x的元 素 if(T->rchild)Print NLT(T->rchild, x)
} 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) exito,∥当遇到小于x的元素时立即结束运行 printf("%d n",T->data); f(T> lchild) Print Nlt(I> Child,x,∥先右后左的中序遍历 3//Print NLT 9.34 void delete nlt( BiTree&T,ntx删除二叉排序树T中所有不小于x元素结点, 并释放空间 mT ->rchild) Delete nLT(T->rchild, x) data<x) exitO,∥当遇到小于x的元素时立即结束运行 T=T->lchild free(q,∥如果树根不小于x,则删除树根,并以左子树的根作为新的树根 f( T Delete NLT(I,x),∥继续在左子树中执行算法 i//Delete NLT 9.35 void Print Between (BiThr Tree T, int a, int b)/打印输出后继线索二叉排序树T中所 有大于a且小于b的元素 while(lp->ltag)p=p> Child;/找到最小元素 while(p&&p->data<b) ifp->data>a) printf("%odn"p->data)/输出符合条件的元素 if(p->rtag)p=p->rtag: p=p->rchild while(p->ltag) p=p->Child }/转到中序后继 i//while 3//Print Between 936 void BSTree Insert Key( BiThr Tree& Tint x)/在后继线索二叉排序树T中插入元 素 if(T> datas)/插入到右侧 (T>rag)/T没有右子树时作为右孩子插入
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 没有右子树时,作为右孩子插入