清華考研真題第八章查找

第九intSearch_Sq(SSTableST,intkey)//在有序表上順序查找的算法,監(jiān)視哨設在高下標{ em[i].key<key)returnERROR;returni;分析:本算法查找成功情況下的平均查找長度為ST.length/2,不成功情況下為intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的遞歸{if(low>highreturn0;查找不到時返回0 em[mid].key==key)returnmid;elseif(S returnSearch_Bin_Recursive(ST,key,low,mid-1);}intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一個{int*r;if(key<r.key)returnelseif(key>=r[ST.length].key)returnST.length;{if(key>=r[mid].key&&key<r[mid+1].key)查找結束的條件returnelseif(key<r[mid].key)high=mid;elselow=mid;本算法不存在查找失敗的情況,returntypedefstructtypedefstruct

intmaxkey;intfirstloc;}int*elem;intIndexidx[MAXBLOCK每塊起始位置和最大元素,]不利用,其內容初始化為{0,0}以利于折半查intblknum;IdxSqListintSearch_IdxSeq(IdxSqListL,intkey)//分塊查找,用折半查找法確定記錄所在塊{if(key>L.idx[L.blknum].maxkey)returnERROR超過最大元素while(low<=high&&!found){elseif(key>L.idx[mid].maxkey)elsehigh=mid-}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)returnERROR未找到returnk;typedefstructLNode*h;//hLNode*t;//t}LNode*Search_CSList(CSList&L,intkey)//在有序單循環(huán)鏈表結構上的查找算SList&L,intkey)//在有序單循環(huán)鏈表結構上的查找算,{if(L.t->data==key)returnL.t;elseif(L.t->data>key)for(p=L.t,i=L.tpos;p->data!=key;p=p-L.t=p;treturn積分可得,在等概率情況下,n/3.typedefstructtypedefstruct

DLNode*pre;intdata;DLNode*next;}DLNode*sp;intlength;DSList;檎業(yè) 蜓妨幢砝嘈DLNode*Search_DSList(DSList&L,intkey)//在有序雙向循環(huán)鏈表結構上的查找{if(p-{while(p->data>key)p=p->pre;}elseif(p-{while(p->data<key)p=p->next;}returnintintIs_BSTree(BitreeT)//判斷二叉樹T是否二叉排序樹,是則返回1,否則{if(T->lchild&&flag)Is_BSTree(T-if(T->data<last)flag=0;//與其中序前驅相比last=T-returnflag;intvoidMaxLT_MinGT(BiTreeT,intx)//T中小于xx的最{if(last<x&&T->data>=x)//x的最大元素if(last<=x&&T->data>x)找到了大于xif(T->rchild)MaxLT_MinGT(T-voidPrint_NLT(BiTreeT,intx)//Tx{if(T->rchild)Print_NLT(T-if(T->data<x)exit();//當遇到小于x的元素時立即結束運printf("%d\n",T-)//voidDelete_NLT(BiTree&T,intx)//Tx元素結點,并釋放{if(T->rchild)Delete_NLT(T-if(T->data<x)exit();//當遇到小于x的元素時立即結束運free(q);//如果樹根不小于x,則刪除樹根,并以左的根作為新的樹voidPrint_Between(BiThrTreeT,inta,intb)//T中所ab的元素{while(!p->ltag)p=p->lchild;找到最小元素while(p&&p-{if(p->data>a)printf("%d\n",p->data);輸出符合條件的元素if(p->rtag)p=p->rtag;{while(!p->ltag)p=p-voidBSTree_Insert_Key(BiThrTree&T,intx)//在后繼線索二叉排序樹T中元素{if(T->data<x)//到右{if(T->rtag)//T沒有右時,作為右孩{q->rtag=1;q->rchild=p;}elseBSTree_Insert_Key(T->rchild,x);//T有右時,右elseif(T->data>x)//到左{if(!T->lchild)//T沒有左時,作為左孩{;//}elseBSTree_Insert_Key(T->lchild,x);//T有左時,左StatusBSTree_Delete_key(BiThrTree&T,intx)//Tx{BTNode*pre,*ptr,*suc;//ptr為x所在結點,presuc分別指向ptrp=T;last=NULL;lastp的前一個(前驅)while(!p->ltag)p=p->lchild;{if(p->data==x)//找到了元素x結{}elseif(last&&last->data==x)suc=p;找到了xif(p->rtag)p=p->rtag;{while(!p->ltag)p=p-轉到中序后繼}//whilex及其前驅和后繼結點if(!ptr)returnERROR;//未找到待刪結點Delete_BSTree(ptr);//x結點if(pre&&pre-pre->rchild=suc;修改線索returnOK;returnvoidDelete_BSTree(BiThrTree&T)//上給出的刪除二叉排序樹的T的算法,按{elseif(T->ltag&&!T->rtag)//結點無左,此時只需重接其右{{r=r->rchild;//找到結點的前驅rr的雙親}T->data=r->data;rTs->rchild=r-elses->lchild=r->lchild;//重接r的左到其雙親結點free(q);//刪除結分析:x結點的前驅和后繼,x結點的辦法,這樣修改線索時會比較簡單,直接讓前驅的線索指向后繼就行了.x結點的同時修改線索,則問voidBSTree_Merge(BiTree&T,BiTree&S)//ST{if(S->lchild)BSTree_Merge(T,S-if(S->rchild)BSTree_Merge(T,S->rchild);合并Insert_Key(T,S);//元素voidInsert_Node(Bitree&T,BTNode*S)//把樹結點S到T的合適位置{if(S->data>T-{if(!T->rchild)T->rchild=S;}{{if(!T->lchild)T->lchild=S;}S->lchild=NULL;//的新結點必須和原來的左右斷絕關//分析:這是一個與上不同的算法.在合并過程中,并不釋放或新建任何結點,而是到另一棵樹上,否則將會導致樹的結構的.voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序樹T為兩AB,Ax,Bx{if(T->lchild)BSTree_Split(T-if(T->data<=x)elseInsert_Node(B,T);//將元素結點合適的樹voidInsert_Node(Bitree&T,BTNode*S)//把樹結點S到T的合適位置{if(!T)T=S;//考慮到剛開始時樹A和樹B為空的情//{if(!T->rchild)T->rchild=S;}{if(!T->lchild)T->lchild=S;}S-typedefstruct

intdata;intbf;intlsize;//lsize域表示該結點的左的結點總數加1ode*lchild,*rchild; ode,*BlcTree;lsizeBTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsizeTk{{if(!T)returnNULL;//k1elseif(T->lsize>k)returnLocate_BlcTree(T->lchild,k);//在左中尋elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右中尋找,注意要修改k的值typedefstructenum{LEAF,BRANCH}tag;結點類型標識intkeynum;BPLinkparent;雙親指intkey[MAXCHILD關鍵字union{BPLinkchild[MAXCHILD];//非葉結點的孩子指針struct{rectype*info[MAXCHILD];//葉子結點的信息針BPNode*next;}}}機查找的算法,ptrpo{//{for(i=0;i<p->keynum&&key>p->key[i];i++);確定關鍵字所在if(i==p->keynum)returnERROR;//關鍵字太大}for(i=0;i<p->keynum&&key!=p->key[i];i++);在葉子結點中查找if(i==p->keynum)returnERROR;//找不到關鍵字returnOK;voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie樹T中字符串key,StringType的結構見第四章{q->lf.k=key;建葉子結點while(p&&i<=klen&&p-{if(p->kind==BRANCH)//如果最后落到分支結點(無同義詞{p->bh.ptr[ord(key[i])]=q;直接連上葉子}else如果最后落到葉子結點(有同義詞{r=(TrieNode*)malloc(sizeof(TrieNode));//建立新的分支結last->bh.ptr[ord(key[i-1])]=r;//用新分支結點取代老葉子結點和上一層的聯(lián)r->bh.ptr[ord(p->lf.k[i])]=p;//新分支結點與新老兩個葉子結點相}StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey)//在Trie樹T{while(p&&p->kind==BRANCH&&i<=key[0])//查找待刪除元{}if(p&&p->kind==LEAF&&p->lf.k=key)//找到了待刪除元{returnOK;return}elsereturnERROR;voidPrint_Hash(HashTableH)//Hash表中的所有關鍵字,其中處理采用線性探測開放定址法{for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex線性探測if(H(H.elem[j].key)==i)intH(char*s)//Hash{if(s)returns[0]-96;//求關鍵一個字母的字母序號(小寫)elsereturn0;typedef*LNode[MAXSIZE]CHashTableHashStatusBuild_Hash(CHashTable&T,intm)//輸入一組關鍵字,建立Hash表,m,用鏈地址法處理.{if(m<1)returnERROR;T=malloc(m*sizeof(WORD建立表頭指針向量for(i=0;i<m;i++)while((key=Inputkey())!=NULL)Inputkey{if(!T[n])T[n]=q;作為鏈表的第一個結點{for(p=T[n];p->next;p=p-p->next=q;//鏈表尾部.本算法不考慮排序問題}returnOK;StatusL