C 언어 양 방향 링크 의 표시 와 실현 사례 에 대한 상세 한 설명

1.개술:
C 언어 에서 더욱 복잡 한 링크 는'양 방향 링크'또는'양면 링크'이다.그 표 의 모든 노드 는 두 개의 연결 이 있 습 니 다.하 나 는 앞의 노드 를 가리 키 고(이'연결'이 첫 번 째'연결'일 때 빈 값 이나 빈 목록 을 가리 킵 니 다).다른 하 나 는 다음 노드 를 가리 키 고 있 습 니 다.(이'연결'이 마지막'연결'일 때 빈 값 이나 빈 목록 을 가리 키 고 있 습 니 다)

하나의 양 방향 링크 는 세 개의 전체 수치 가 있 습 니 다.수치,뒤쪽 노드 링크,앞 노드 링크 입 니 다.
일부 저급 언어 에서 XOR-linking 은 양 방향 링크 에서 한 단어 로 두 개의 링크(앞 뒤)를 나타 내 는데 우 리 는 이런 방법 을 제창 하지 않 는 다.
양 방향 링크 도 더 블 링크 라 고 합 니 다.양 방향 링크 에는 뒤의 노드 를 가리 키 는 지침 뿐만 아니 라 앞의 노드 를 가리 키 는 지침 도 있다.이렇게 하면 모든 노드 에서 앞의 노드 를 방문 할 수 있 고 물론 뒤의 노드 를 방문 하여 전체 링크 까지 방문 할 수 있다.일반적으로 대량의 양의 데 이 터 를 링크 에 저장 해 야 할 때 사용한다.양 방향 링크 도 아래 의 다른 링크 의 확장 에 맞 춰 사용 할 수 있다.
링크 내용 을 가리 키 는 지침 을 따로 저장 하고 인접 한 노드 를 수정 할 수 있 기 때문에 첫 번 째 노드 가 삭제 되 거나 그 전에 새로운 노드 를 추가 할 수 있 습 니 다.이 럴 때 는 첫 번 째 노드 를 가리 키 는 지침 을 수정 해 야 한다.이러한 특수 한 상황 을 없 앨 수 있 는 편리 한 방법 은 마지막 노드 이후 첫 번 째 노드 전에 영원히 삭제 되 거나 이동 되 지 않 는 가상 노드 를 저장 하여 다음 과 같은 순환 링크 를 형성 하 는 것 이다.이 가상 노드 뒤의 노드 는 바로 진정한 첫 번 째 노드 이다.이런 상황 은 보통 이 가상 노드 로 이 링크 를 직접 표시 할 수 있다.링크 를 단독 적 으로 배열 에 존재 하 는 상황 에 대해 서도 이 배열 로 링크 를 표시 하고 0 번 또는 1 번(컴 파일 러 가 지원 한다 면)노드 로 이 가상 노드 를 고정 적 으로 표시 할 수 있다.
2.프로그램 구현:
/*c2-4.h 선형 표 의 양 방향 링크 저장 구조*/
 typedef struct DuLNode
 {
   ElemType data;
   struct DuLNode *prior,*next;
 }DuLNode,*DuLinkList;
/*bo2-5.c 더 블 체인 순환 선형 표(저장 구 조 는 c2-4.h 로 정의)의 기본 동작(14 개)*/
 Status InitList(DuLinkList *L)
 { /* 빈 양 방향 순환 링크 L*/
   *L=(DuLinkList)malloc(sizeof(DuLNode));
   if(*L)
   {
     (*L)->next=(*L)->prior=*L;
     return OK;
   }
   else
     return OVERFLOW;
 }
 Status DestroyList(DuLinkList *L)
 { /* 조작 결과:양 방향 순환 링크 L 제거*/
   DuLinkList q,p=(*L)->next; /* p 첫 번 째 결점 을 가리 키 는*/
   while(p!=*L)/*p 가 시계 머리 에 도착 하지 않 았 습 니 다*/
   {
     q=p->next;
     free(p);
     p=q;
   }
   free(*L);
   *L=NULL;
   return OK;
 }
 Status ClearList(DuLinkList L)/*변경 하지 않 음 L*/
 { /* 초기 조건:L 이 이미 존재 합 니 다.작업 결과:L 을 빈 테이블 로 초기 화*/
   DuLinkList q,p=L->next; /* p 첫 번 째 결점 을 가리 키 는*/
   while(p!=L)/*p 가 시계 머리 에 도착 하지 않 았 습 니 다*/
   {
     q=p->next;
     free(p);
     p=q;
   }
   L->next=L->prior=L; /* 두 노드 의 두 바늘 영역 은 모두 자신 을 가리 키 고 있 습 니 다*/
   return OK;
 }
 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;
   DuLinkList p=L->next; /* p 첫 번 째 결점 을 가리 키 는*/
   while(p!=L)/*p 가 시계 머리 에 도착 하지 않 았 습 니 다*/
   {
     i++;
     p=p->next;
   }
   return i;
 }
 Status GetElem(DuLinkList L,int i,ElemType *e)
 { /* i 번 째 요소 가 존재 할 때 그 값 을 e 에 부여 하고 OK 로 되 돌려 줍 니 다.그렇지 않 으 면 ERROR*/로 되 돌려 줍 니 다.
   int j=1; /* j 는 계수기*/
   DuLinkList p=L->next; /* p 첫 번 째 결점 을 가리 키 는*/
   while(p!=L&&j   {
     p=p->next;
     j++;
   }
   if(p===L|j>i)/*i 번 째 요 소 는 존재 하지 않 습 니 다*/
     return ERROR;
   *e=p->data; /* 제 i 개 원소 취하 기*/
   return OK;
 }
 int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /* 초기 조건:L 이 이미 존재 하고 compare()는 데이터 요소 판정 함수*/
   /* 작업 결과:L 의 첫 번 째 e 만족 관계 compare()의 데이터 요소 의 위 치 를 되 돌려 줍 니 다.*/
   /*           이러한 데이터 요소 가 존재 하지 않 으 면 반환 값 은 0*/
   int i=0;
   DuLinkList p=L->next; /* p 는 첫 번 째 요 소 를 가리 키 고 있 습 니 다*/
   while(p!=L)
   {
     i++;
     if(compare(p->data,e)/*이러한 데이터 요 소 를 찾 았 습 니 다*/
       return i;
     p=p->next;
   }
   return 0;
 }
 Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
 { /* 조작 결과:약 cure 는 L 의 데이터 요소 이 고 첫 번 째 가 아니면 pree.전구 로 돌아 갑 니 다.*/
   /*           그렇지 않 으 면 조작 실패,pree 정의 없 음*/
   DuLinkList p=L->next->next; /* p 는 두 번 째 요 소 를 가리 키 고 있 습 니 다*/
   while(p!=L)/*p 가 시계 머리 에 도착 하지 않 았 습 니 다*/
   {
     if(p->data==cur_e)
     {
       *pre_e=p->prior->data;
       return TRUE;
     }
     p=p->next;
   }
   return FALSE;
 }
 Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
 { /* 조작 결과:약 cure 는 L 의 데이터 요소 이 고 마지막 이 아 닌 nexte.후계 로 돌아 갑 니 다.*/
   /*           그렇지 않 으 면 조작 실패,nexte 정의 없 음*/
   DuLinkList p=L->next->next; /* p 는 두 번 째 요 소 를 가리 키 고 있 습 니 다*/
   while(p!=L)/*p 가 시계 머리 에 도착 하지 않 았 습 니 다*/
   {
     if(p->prior->data==cur_e)
     {
       *next_e=p->data;
       return TRUE;
     }
     p=p->next;
   }
   return FALSE;
 }
 DuLinkList GetElemP(DuLinkList L,int i)/*추가*/
 { /* 양 방향 링크 L 에서 두 번 째 요소 의 위치 포인터(알고리즘 2.18,2.19 호출 할 함수)*/
   int j;
   DuLinkList p=L;
   for(j=1;j<=i;j++)
     p=p->next;
   return p;
 }
 Status ListInsert(DuLinkList L,int i,ElemType e)/*개선 알고리즘 2.18*/
 { /* 선두 결점 의 더 블 체인 순환 선형 표 L 중 i 번 째 위치 전에 요소 e 를 삽입 하고 i 의 합 법 적 인 수 치 는 1≤i≤표 장+1*/
   DuLinkList p,s;
   (i<1|i>ListLength(L)+1)/*i 값 이 합 법 적 이지 않 은 경우*/
     return ERROR;
   p=GetElemP(L,i-1); /* L 에서 제 i-1 원소 의 위치 포인터 p*/확인
   if(!p)/*p=NULL,즉 i-1 번 요소 가 존재 하지 않 습 니 다*/
     return ERROR;
   s=(DuLinkList)malloc(sizeof(DuLNode));
   if(!s)
     return OVERFLOW;
   s->data=e; /* i-1 번 요소 뒤에 삽입*/
   s->prior=p;
   s->next=p->next;
   p->next->prior=s;
   p->next=s;
   return OK;
 }
 Status ListDelete(DuLinkList L,int i,ElemType*e)/*알고리즘 2.19*/
 { /* 선두 결점 을 가 진 쌍 사슬 순환 선형 표 L 의 제 i 요 소 를 삭제 하고 i 의 합 법 치 는 1≤i≤표 장+1*/
   DuLinkList p;
   (i<1|i>ListLength(L))/*i 값 이 비합법적 인 경우*/
     return ERROR;
   p=GetElemP(L,i);  /* L 에서 i 번 째 요소 의 위치 포인터 p*/를 확인 합 니 다.
   if(!p)/*p=NULL,즉 i 번 째 요 소 는 존재 하지 않 습 니 다*/
     return ERROR;
   *e=p->data;
   p->prior->next=p->next;
   p->next->prior=p->prior;
   free(p);
   return OK;
 }
 void ListTraverse(DuLinkList L,void(*visit)(ElemType))
 { /* 쌍 사슬 순환 선형 표 L 의 두 노드 에서 출발 하여 모든 데이터 요소 에 함수 visit()*/
   DuLinkList p=L->next; /* p 지 향 두 결점*/
   while(p!=L)
   {
     visit(p->data);
     p=p->next;
   }
   printf("");
 }
 void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
 { /* 쌍 사슬 순환 선형 표 L 의 두 노드 에서 출발 하여 역순 으로 모든 데이터 요소 에 함수 visit()를 호출 합 니 다.별도로*/
   DuLinkList p=L->prior; /* p 지향 끝 점*/
   while(p!=L)
   {
     visit(p->data);
     p=p->prior;
   }
   printf("");
 }