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)//ÔÚÓÐÐòµ¥Ñ»·Á´±í´æ´¢½á¹¹ÉϵIJéÕÒËã·¨,¼Ù¶¨Ã¿´Î²éÕÒ¶¼³É¹¦ { 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 ·ÖÎö:ÓÉÓÚÌâÄ¿Öмٶ¨Ã¿´Î²éÕÒ¶¼Êdzɹ¦µÄ,ËùÒÔ±¾Ëã·¨ÖÐûÓйØÓÚ²éÕÒʧ°ÜµÄ´¦Àí.ÓÉ΢»ý·Ö¿ÉµÃ,ÔڵȸÅÂÊÇé¿öÏÂ,ƽ¾ù²éÕÒ³¤¶ÈԼΪ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)//ÔÚÓÐÐòË«ÏòÑ»·Á´±í´æ´¢½á¹¹ÉϵIJéÕÒËã·¨,¼Ù¶¨Ã¿´Î²éÕÒ¶¼³É¹¦ { p=L.sp; if(p->data>key) { while(p->data>key) p=p->pre; L.sp=p; } else if(p->data while(p->data 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 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 if(last<=x&&T->data>x) //ÕÒµ½ÁË´óÓÚxµÄ×îÐ¡ÔªËØ printf(\ 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 printf(\ 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 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 if(p->data>a) printf(\Êä³ö·ûºÏÌõ¼þµÄÔªËØ 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 if(T->rtag) //TûÓÐÓÒ×ÓÊ÷ʱ,×÷ΪÓÒº¢×Ó²åÈë { 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