东北大学：《数据结构》课程教学资源（学习资料）第九章 查找

第九章查找 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[ST length). key) return ST length low=l; high=ST length while (low=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].keyhigh) 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[ST.length].key) return ST.length; low=1;high=ST.length; while(low=r[mid].key&&key<r[mid+1].key) //查找结束的条件 return mid;

else if(key L.idx[L blknum] markey) return ErroR;∥超过最大元素 low=l; high=L blknum found=0 whie(owL 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(keyL.idx[L.blknum].maxkey) return ERROR; //超过最大元素 low=1;high=L.blknum; found=0; while(lowL.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->datadatanext 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>datadata 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(lastdata=x)∥找到了小于x的最大元素 printf("a=%d\n",last) idasdata>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->datadatanext; 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->datadata; 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(lastdata>=x) //找到了小于 x 的最大元素 printf("a=%d\n",last); if(lastdata>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->datadata); 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) datalchild 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->datadata>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->datadata); 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->datalchild; 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->datadata>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->datartag) //T 没有右子树时,作为右孩子插入

p=T->rchild q=(BiThrNode*)malloc(sizeof(BiThrNode)) T->rchild=q: T->rtag=0 q-→tag=1;q→> Achild=p,∥/修改原线索 else BSTree Insert Key(I>chid,x)/T有右子树时插入右子树中 else if(>data>x)/插入到左子树中 if(f-> lchild)/没有左子树时作为左孩子插入 q= BiThrNode*)malloc(sizeof(BiThrNode): q->data=x T->lchild=q: q→tag=lq> rchild=T,∥修改自身的线索 else BSTree Insert Key(T-> Child,x)/T有左子树时插入左子树中 J//BSTree Insert Key 9.37 Status bstree_ Delete key( BiThr Tree&r,intx∥在后继线索二叉排序树T中删除 元素x BTNode*pre,tptr;*suc:/tr为x所在结点pre和suc分别指向ptr的前驱和后继 p= T: last=NULL;∥/ast始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p-> achild;/找到中序起始元素 while(p) iflp->data=x)/找到了元素x结点 ptrp, else if((last&&last->data=x)suc=p;∥找到了x的后继 if(p->rtag) p=p->rtag, else p=p->rchild while(p->ltag)p=p->lchild 转到中序后继 [;

{ 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 的后继 if(p->rtag) p=p->rtag; else { p=p->rchild; while(!p->ltag) p=p->lchild; } //转到中序后继 last=p;

} while∥借助中序遍历找到元素x及其前驱和后继结点 ifpt) return error;∥.找到待删结点 Delete BSTree(ptr),W删除ⅹ结点 if(pre&&pre->rtag) pre> rchild=suc;∥修改线索 eturn OK. 1//BSTree Delete key void Delete BSTree(BiThr Tree&Ty课本上给出的删除二叉排序树的子树T的算 法按照线索二叉树的结构作了一些改动 if(T-ltag&&r>rtag)∥结点无右子树此时只需重接其左子树 T-T->lchild else if((T->tag&&!I→rtag)/结点无左子树此时只需重接其右子树 T=T->rchild else if(T->ltag&&!I→rtag)/结点既有左子树又有右子树 while(!r->rtag S-l r=> rchild;∥我找到结点的前驱r和r的双亲s T->data=r>data;/用r代替T结点 f(s!=1 S->rchild=r->lchild else s-> Lchild=r> Child;∥重接r的左子树到其双亲结点上 q-r, please free(q,∥删除结点 i/Delete BSTree 分析本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线 索时会比较简单,直接让前驱的线索指向后继就行了如果试图在删除x结点的同 时修改线索,则问题反而复杂化了 9.38 void bs tree merge( BiTree&r, BiTree&S把二叉排序树S合并到T中 if(S->lchild) BSTree Merge(T, S->Child) ifS→ rchild) BSTree merge(T,S→> schild),∥合并子树 Insert Key(TS;/插入元素 i//BSTree Merge

}//while //借助中序遍历找到元素 x 及其前驱和后继结点 if(!ptr) return ERROR; //未找到待删结点 Delete_BSTree(ptr); //删除 x 结点 if(pre&&pre->rtag) pre->rchild=suc; //修改线索 return OK; }//BSTree_Delete_key void Delete_BSTree(BiThrTree &T)//课本上给出的删除二叉排序树的子树 T 的算 法,按照线索二叉树的结构作了一些改动 { q=T; if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树 T=T->lchild; else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树 T=T->rchild; else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild; //找到结点的前驱 r 和 r 的双亲 s } T->data=r->data; //用 r 代替 T 结点 if(s!=T) s->rchild=r->lchild; else s->lchild=r->lchild; //重接 r 的左子树到其双亲结点上 q=r; }//else free(q); //删除结点 }//Delete_BSTree 分析:本算法采用了先求出 x 结点的前驱和后继,再删除 x 结点的办法,这样修改线 索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除 x 结点的同 时修改线索,则问题反而复杂化了. 9.38 void BSTree_Merge(BiTree &T,BiTree &S)//把二叉排序树 S 合并到 T 中 { if(S->lchild) BSTree_Merge(T,S->lchild); if(S->rchild) BSTree_Merge(T,S->rchild); //合并子树 Insert_Key(T,S); //插入元素 }//BSTree_Merge

void insert node( Bitree& TBTNode*Sy/把树结点S插入到T的合适位置上 if(S→data>T->data if(!T->rchild) T->rchild=S else Insert Node(T->rchild, S) else if(S->datadata) if(!T->lchild )T->lchild=S else Insert Node(T->lchild, S) S->lchild=NULL;/插入的新结点必须和原来的左右子树断绝关系 S→ achild=NULL;∥香则会导致树结构的混乱 g//nsert Node 分析这是一个与课本上不同的插入算法在合并过程中,并不释放或新建任何结 点而是采取修改指针的方式来完成合并这样就必须按照后序序列把一棵树中 的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱 9.39 void BSTree Split( BiTree&T,Bire&A,Bire&B,intx)把二叉排序树T分裂为 两棵二叉排序树A和B,其中A的元素全部小于等于xB的元素全部大于x if(T->lchild)BSTree Split(T->lchild, A, B, x) if(T-> rchild) BSTree Split(T> rchild,A,B,x),∥分裂左右子树 if(T->datadata>T>data)∥/其余部分与上一题同 if(T->rchild)T-rchild=S else Insert Node(T->rchild, S); else if(S->datadata) if(!T->lchild )T->lchild=S else Insert Node(T->lchild, S) S->lchild=NULL:

void Insert_Node(Bitree &T,BTNode *S)//把树结点 S 插入到 T 的合适位置上 { if(S->data>T->data) { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S); } else if(S->datadata) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL; //插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL; //否则会导致树结构的混乱 }//Insert_Node 分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结 点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中 的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱. 9.39 void BSTree_Split(BiTree &T,BiTree &A,BiTree &B,int x)//把二叉排序树 T分裂为 两棵二叉排序树 A 和 B,其中 A 的元素全部小于等于 x,B 的元素全部大于 x { if(T->lchild) BSTree_Split(T->lchild,A,B,x); if(T->rchild) BSTree_Split(T->rchild,A,B,x); //分裂左右子树 if(T->datadata>T->data) //其余部分与上一题同 { if(!T->rchild) T->rchild=S; else Insert_Node(T->rchild,S); } else if(S->datadata) { if(!T->lchild) T->lchild=S; else Insert_Node(T->lchild,S); } S->lchild=NULL;

S->rchild=NULL i//nsert Key 940 typedef struct i int data int bf. int lsize;/size域表示该结点的左子树的结点总数加1 BIcNode *lchild. *rchild } BIcNode,* BInTree含 Size域的平衡二叉排序树类型 BTNode* Locate_ BIc tree( BIcTree T;intk/在含 Size域的平衡二叉排序树T中确 定第k小的结点指针 if(! T) return NULI;/k小于1或大于树结点总数 if(> lsize=k) retun t,/就是这个结点 else if(T->lsize>k return locate Blc tree(-> lchild. k),∥在左子树中寻找 else return Locate_ BInTree(-> orchid. k-T-> lsize);,∥在右子树中寻找注意要修改k 的值 i //Locate BIcTree 94 typedef struct i enum{LEAF, BRANCH}tag;∥结点类型标识 int keynum BPLink parent;/双亲指针 int key MAXCHILD]∥关键字 union i BPLink child MAXCHILD]∥非叶结点的孩子 指针 struct ectype* info MAXCHILD]叶子结 点的信息指针 BPNode*next;∥/指向下一个叶子结点的链接 } BPNode,+ BLInk*BPTe/B+树及其结点类型 Status bptree search( BPTree T; int key, BPNode*ptr, Int pos)/B+树中按关键字随 机查找的算法返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中 的位置pos

S->rchild=NULL; }//Insert_Key 9.40 typedef struct { int data; int bf; int lsize; //lsize 域表示该结点的左子树的结点总数加 1 BlcNode *lchild,*rchild; } BlcNode,*BlcTree; //含 lsize 域的平衡二叉排序树类型 BTNode *Locate_BlcTree(BlcTree T,int k)//在含 lsize 域的平衡二叉排序树 T 中确 定第 k 小的结点指针 { if(!T) return NULL; //k 小于 1 或大于树结点总数 if(T->lsize==k) return T; //就是这个结点 else if(T->lsize>k) return Locate_BlcTree(T->lchild,k); //在左子树中寻找 else return Locate_BlcTree(T->rchild,k-T->lsize); //在右子树中寻找,注意要修改 k 的值 }//Locate_BlcTree 9.41 typedef struct { enum {LEAF,BRANCH} tag; //结点类型标识 int keynum; BPLink parent; //双亲指针 int key[MAXCHILD]; //关键字 union { BPLink child[MAXCHILD];//非叶结点的孩子 指针 struct { rectype *info[MAXCHILD];//叶子结 点的信息指针 BPNode *next; //指向下一个叶子结点的链接 } leaf; } } BPNode,*BPLink,*BPTree;//B+树及其结点类型 Status BPTree_Search(BPTree T,int key,BPNode *ptr,int pos)//B+树中按关键字随 机查找的算法,返回包含关键字的叶子结点的指针 ptr 以及关键字在叶子结点中 的位置 pos {

while(ptag= BRANCH)∥沿分支向下查找 for(i=0ip-> keynum&&key>p-> key; i+),/确定关键字所在子树 if(i=p-> keynum) return error,关键字太大 p=p->child[i] for(i=0;ip-> keynum&&key!=p>key;+),∥在叶子结点中查找 ifi=p-> keynum) return Error;∥找不到关键字 ptrp pos=1, eturn OK 3//BPTree Search 942 void Trie Tree Insert Key( TrieTree& T, String Type key/在Te树T中插入字符串 key, String Type的结构见第四章 q=(TrieNode* )malloc(sizeof(TrieNode)); q->kind=LEAF; q->fk-key,∥建叶子结点 klen=keya] p=T;r=1; while(p&&ibh. ptrord(keyD p=p->bh. ptrlord(key D }∥自上而下查找 ifp->kind= BRANCH)/如果最后落到分支结点(无同义词) p-> bh. ptrlord(key[)=q,∥直接连上叶子 p- >bh. num++. else∥如果最后落到叶子结点(有同义词 r=( TrieNode*) malloc(sizeof( TrieNode),∥建立新的分支结点 last-> bh. ptrlord(key[i-])=,∥用新分支结点取代老叶子结点和上一层的联系 [->kind=BRANCH: r->bh. num=2 r->bh. ptrIord(key D=q r-> bh. ptrlord(p→fk[jD=p,/新分支结点与新老两个叶子结点相连 i//Trie Tree Insert Key 分析:当自上而下的査找结束时存在两种情况一种情况树中没有待插入关键字

p=T; while(p.tag==BRANCH) //沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++); //确定关键字所在子树 if(i==p->keynum) return ERROR; //关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++); //在叶子结点中查找 if(i==p->keynum) return ERROR; //找不到关键字 ptr=p;pos=i; return OK; }//BPTree_Search 9.42 void TrieTree_Insert_Key(TrieTree &T,StringType key)//在 Trie 树 T 中插入字符串 key,StringType 的结构见第四章 { q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key; //建叶子结点 klen=key[0]; p=T;i=1; while(p&&ibh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; } //自上而下查找 if(p->kind==BRANCH) //如果最后落到分支结点(无同义词): { p->bh.ptr[ord(key[i])]=q; //直接连上叶子 p->bh.num++; } else //如果最后落到叶子结点(有同义词): { r=(TrieNode*)malloc(sizeof(TrieNode)); //建立新的分支结点 last->bh.ptr[ord(key[i-1])]=r; //用新分支结点取代老叶子结点和上一层的联系 r->kind=BRANCH;r->bh.num=2; r->bh.ptr[ord(key[i])]=q; r->bh.ptr[ord(p->lf.k[i])]=p; //新分支结点与新老两个叶子结点相连 } }//TrieTree_Insert_Key 分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字