データ構造——線形時計チェーン式の表現と実現(2)

本文のすべてのコードは疑似コードで、アルゴリズムの基本思想だけを述べます.
-アルゴリズム1率先して接合する双方向循環チェーン表(記憶構造はc 2-4 hで定義される)の基本動作(14個)

 typedef struct DuLNode
 { ElemType data;
   DuLNode *prior,*next;
 }DuLNode,*DuLinkList;

 void InitList(DuLinkList &L)
 { //           L
   L=(DuLinkList)malloc(sizeof(DuLNode));
   if(L)
     L->next=L->prior=L;
   else
     exit(OVERFLOW);
 }

 void ClearList(DuLinkList L) //    L
 { //     ：L   。    ： L     
   DuLinkList p=L->next; // p   1   
   while(p!=L) // p      
   { p=p->next; // p       
     free(p->prior); //   p     
   }
   L->next=L->prior=L; //               
 }

 void DestroyList(DuLinkList &L)
 { //     ：        L
   ClearList(L); //  L     
   free(L); //      
   L=NULL; // L         
 }

 Status ListEmpty(DuLinkList L)
 { //     ：   L   。    ： L   ，   TRUE，    FALSE
   if(L->next==L&&L->prior==L)
     return TRUE;
   else
     return FALSE;
 }

 int ListLength(DuLinkList L)
 { //     ：L   。    ：  L       
   int i=0; //       0
   DuLinkList p=L->next; // p   1   
   while(p!=L) // p      
   { i++; //    +1
     p=p->next; // p       
   }
   return i;
 }

 Status GetElem(DuLinkList L,int i,ElemType &e)
 { //   i      ，    e   OK；    ERROR
   int j=1; //       1
   DuLinkList p=L->next; // p   1   
   while(p!=L&&j<i) //        ，  p   i    p     
   { j++; //    +1
     p=p->next; // p       
   }
   if(p==L||j>i) //  i      
     return ERROR; //     
   e=p->data; //   i     e
   return OK; //     
 }

 int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { //     ：L   ，compare()         
   //     ：  L  1  e    compare()        。
   //                      ，     0
   int i=0; //       0
   DuLinkList p=L->next; // p   1   
   while(p!=L) // p      
   { i++; //    +1
     if(compare(p->data,e)) //          
       return i; //      
     p=p->next; // p       
   }
   return 0; //             
 }

 Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e)
 { //     ： cur_e L     ，      ，  pre_e      ，  OK；
   //                 ，pre_e   ，  ERROR
   DuLinkList p=L->next->next; // p   2   
   while(p!=L) // p      
   { if(p->data==cur_e) // p    cur_e   
     { pre_e=p->prior->data; //  p         pre_e
       return OK; //     OK
     }
     p=p->next; // p       
   }
   return ERROR; //     ，  ERROR
 }

 Status NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e)
 { //     ： cur_e L     ，       ，  next_e      ，  OK，
   //                 ，next_e   ，  ERROR
   DuLinkList p=L->next->next; // p   2   
   while(p!=L) // p      
   { if(p->prior->data==cur_e) // p          cur_e
     { next_e=p->data; //  p    (cur_e   )    next_e
       return OK; //     OK
     }
     p=p->next; // p       
   }
   return ERROR; //     ，  ERROR
 }

 DuLinkList GetElemP(DuLinkList L,int i) //   
 { //      L    i      。i 0，        。  i      ，
   //   NULL(  2.18、2.19      )
   int j;
   DuLinkList p=L; // p     
   if(i<0||i>ListLength(L)) // i    
     return NULL;
   for(j=1;j<=i;j++) // p   i   
     p=p->next; // p       
   return p;
 }

 Status ListInsert(DuLinkList L,int i,ElemType e)
 { //              L  i         e，i     1≤i≤  +1
   //     2.18，        +1         
   DuLinkList p,s;
   if(i<1||i>ListLength(L)+1) // i    
     return ERROR; //     ERROR
   p=GetElemP(L,i-1); //  L    i          p
   if(!p) // p=NULL，  i         (      1      )
     return ERROR; //     ERROR
   s=(DuLinkList)malloc(sizeof(DuLNode)); //      
   if(!s)
     return ERROR; //          ERROR
   s->data=e; //  e     
   s->prior=p; //         i-1   
   s->next=p->next; //         i   
   p->next->prior=s; //  i           
   p->next=s; //  i-1           
   return OK; //     OK
 }

 Status ListDelete(DuLinkList L,int i,ElemType &e) //   2.19
 { //               L  i   ，i     1≤i≤  
   DuLinkList p;
   if(i<1) // i    
     return ERROR; //     
   p=GetElemP(L,i); //  L    i        p
   if(!p) // p=NULL，  i      
     return ERROR; //     
   e=p->data; //   i       e
   p->prior->next=p->next; //  i-1          i+1   
   p->next->prior=p->prior; //   i+1         i-1   
   free(p); //    i   
   return OK; //     
 }

 void ListTraverse(DuLinkList L,void(*visit)(ElemType))
 { //         L      ，             visit()
   DuLinkList p=L->next; // p      
   while(p!=L) // p      
   { visit(p->data); //  p        visit()
     p=p->next; // p       
   }
   printf("
");
 }

 void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
 { //         L      ，             visit()。  
   DuLinkList p=L->prior; // p     
   while(p!=L) // p      
   { visit(p->data); //  p        visit()
     p=p->prior; // p       
   }
   printf("
");
 }