C 언어 단일 순환 링크 의 표시 와 실현 사례 에 대한 상세 한 설명

1.개술:
순환 링크 에 있어 서 첫 번 째 노드 와 마지막 노드 가 연결 되 어 있다.이런 방식 은 단 방향 과 양 방향 링크 에서 모두 실현 할 수 있다.순환 링크 를 바 꾸 려 면 임의의 노드 에서 시작 한 다음 목록 의 모든 방향 을 따라 시작 노드 로 돌아 갈 때 까지 선택 할 수 있 습 니 다.또 다른 방법 을 보면 순환 체인 시 계 는'머리 도 꼬리 도 없다'고 볼 수 있다.이 목록 은 데이터 저장 캐 시 를 절약 하 는 데 유리 합 니 다.한 목록 에 대상 이 있다 고 가정 하고 모든 다른 대상 이 특별한 배열 이 아 닌 배열 로 교체 되 기 를 바 랍 니 다.
전체 목록 을 가리 키 는 지침 을 접근 지침 이 라 고 할 수 있 습 니 다.

단 방향 링크 로 구 축 된 순환 링크
순환 링크 의 첫 번 째 노드 는 바로 마지막 노드 이 고 반대로 도 마찬가지 이다.순환 링크 의 경계 가 없 기 때문에 이런 링크 에서 디자인 알고리즘 은 일반 링크 보다 더욱 쉽다.새로 가입 한 노드 는 첫 번 째 노드 전이 나 마지막 노드 이후 에 실제 요구 에 따라 유연 하 게 처리 할 수 있어 야 하 며 차이 가 크 지 않다(아래 실례 코드 참조).물론 마지막 에 만 데 이 터 를 삽입 하거나 이전 에 만 삽입 할 경우 처리 도 쉽다.
또 하나의 아 날로 그 순환 링크 는 마지막 노드 에 접근 한 후에 손 으로 첫 번 째 노드 로 이동 하 는 것 이다.첫 번 째 노드 에 접근 하기 전에 도 마찬가지다.이렇게 하면 순환 링크 의 기능 도 실현 할 수 있 고 순환 링크 를 직접 사용 하 는 것 이 비교적 번 거 롭 거나 문제 가 발생 할 수 있 을 때 사용 할 수 있다.
2.프로그램 구현:

/* c2-2.h             */
 struct LNode
 {
  ElemType data;
  struct LNode *next;
 };
 typedef struct LNode *LinkList; /*      LinkList    */

/* bo2-4.c            (     c2-2.h  ) 12      */
 Status InitList_CL(LinkList *L)
 { /*     ：         L */
  *L=(LinkList)malloc(sizeof(struct LNode)); /*      ,  L       */
  if(!*L) /*        */
   exit(OVERFLOW);
  (*L)->next=*L; /*          */
  return OK;
 }
 Status DestroyList_CL(LinkList *L)
 { /*     ：     L */
  LinkList q,p=(*L)->next; /* p      */
  while(p!=*L) /*      */
  {
   q=p->next;
   free(p);
   p=q;
  }
  free(*L);
  *L=NULL;
  return OK;
 }
 Status ClearList_CL(LinkList *L) /*   L */
 { /*     ：   L   。    ： L      */
  LinkList p,q;
  *L=(*L)->next; /* L      */
  p=(*L)->next; /* p        */
  while(p!=*L) /*      */
  {
   q=p->next;
   free(p);
   p=q;
  }
  (*L)->next=*L; /*            */
  return OK;
 }
 Status ListEmpty_CL(LinkList L)
 { /*     ：   L   。    ： L   ，   TRUE，    FALSE */
  if(L->next==L) /*   */
   return TRUE;
  else
   return FALSE;
 }
 int ListLength_CL(LinkList L)
 { /*     ：L   。    ：  L        */
  int i=0;
  LinkList p=L->next; /* p      */
  while(p!=L) /*      */
  {
   i++;
   p=p->next;
  }
  return i;
 }
 Status GetElem_CL(LinkList L,int i,ElemType *e)
 { /*   i      ,    e   OK,    ERROR */
  int j=1; /*    ,j     */
  LinkList p=L->next->next; /* p        */
  if(i<=0||i>ListLength_CL(L)) /*  i       */
   return ERROR;
  while(j<i)
  { /*        ,  p   i    */
   p=p->next;
   j++;
  }
  *e=p->data; /*   i    */
  return OK;
 }
 int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /*     ：   L   ，compare()          */
  /*     ：  L  1  e    compare()        。 */
  /*                 ，     0 */
  int i=0;
  LinkList p=L->next->next; /* p        */
  while(p!=L->next)
  {
   i++;
   if(compare(p->data,e)) /*      */
    return i;
   p=p->next;
  }
  return 0;
 }
 Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
 { /*     ：   L    */
  /*     ： cur_e L     ，      ，  pre_e      ， */
  /*            ，pre_e    */
  LinkList q,p=L->next->next; /* p        */
  q=p->next;
  while(q!=L->next) /* p     */
  {
   if(q->data==cur_e)
   {
    *pre_e=p->data;
    return TRUE;
   }
   p=q;
   q=q->next;
  }
  return FALSE;
 }
 Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
 { /*     ：   L    */
  /*     ： cur_e L     ,       ,  next_e      ， */
  /*            ，next_e    */
  LinkList p=L->next->next; /* p        */
  while(p!=L) /* p     */
  {
   if(p->data==cur_e)
   {
    *next_e=p->next->data;
    return TRUE;
   }
   p=p->next;
  }
  return FALSE;
 }
 Status ListInsert_CL(LinkList *L,int i,ElemType e) /*   L */
 { /*  L  i         e */
  LinkList p=(*L)->next,s; /* p      */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)+1) /*     i        */
   return ERROR;
  while(j<i-1) /*    i-1    */
  {
   p=p->next;
   j++;
  }
  s=(LinkList)malloc(sizeof(struct LNode)); /*       */
  s->data=e; /*   L  */
  s->next=p->next;
  p->next=s;
  if(p==*L) /*       */
   *L=s;
  return OK;
 }
 Status ListDelete_CL(LinkList *L,int i,ElemType *e) /*   L */
 { /*   L  i   ,  e     */
  LinkList p=(*L)->next,q; /* p      */
  int j=0;
  if(i<=0||i>ListLength_CL(*L)) /*  i       */
   return ERROR;
  while(j<i-1) /*    i-1    */
  {
   p=p->next;
   j++;
  }
  q=p->next; /* q        */
  p->next=q->next;
  *e=q->data;
  if(*L==q) /*          */
   *L=p;
  free(q); /*         */
  return OK;
 }
 Status ListTraverse_CL(LinkList L,void(*vi)(ElemType))
 { /*     :L   。    :   L           vi()。  vi()  ,      */
  LinkList p=L->next->next;
  while(p!=L->next)
  {
   vi(p->data);
   p=p->next;
  }
  printf("
");
  return OK;
 }

/* main2-4.c      ,  bo2-4.c     */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h"
 #include"bo2-4.c"
 Status compare(ElemType c1,ElemType c2)
 {
  if(c1==c2)
   return TRUE;
  else
   return FALSE;
 }
 void visit(ElemType c)
 {
  printf("%d ",c);
 }
 void main()
 {
  LinkList L;
  ElemType e;
  int j;
  Status i;
  i=InitList_CL(&L); /*         L */
  printf("        L i=%d (1:     )
",i);
  i=ListEmpty_CL(L);
  printf("L    i=%d(1:  0: )
",i);
  ListInsert_CL(&L,1,3); /*  L     3,5 */
  ListInsert_CL(&L,2,5);
  i=GetElem_CL(L,1,&e);
  j=ListLength_CL(L);
  printf("L       =%d, 1      %d。
",j,e);
  printf("L         ：");
  ListTraverse_CL(L,visit);
  PriorElem_CL(L,5,&e); /*    5    */
  printf("5        %d。
",e);
  NextElem_CL(L,3,&e); /*    3    */
  printf("3        %d。
",e);
  printf("L    %d(1:  0: )
",ListEmpty_CL(L));
  j=LocateElem_CL(L,5,compare);
  if(j)
   printf("L  %d    5。
",j);
  else
   printf("     5   
");
  i=ListDelete_CL(&L,2,&e);
  printf("  L  2   ：
");
  if(i)
  {
   printf("       %d,  L         ：",e);
   ListTraverse_CL(L,visit);
  }
  else
   printf("     ！
");
  printf("  L：%d(1:   )
",ClearList_CL(&L));
  printf("  L ，L   ：%d(1:  0: )
",ListEmpty_CL(L));
  printf("  L：%d(1:   )
",DestroyList_CL(&L));
 }