分析在块内进行顺序查找时如果需要设置监视哨,则必须先保存相邻块的相邻 元素,以免数据丢失 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;