정적 체인 시계, 순환 체인 시계, 이중 순환 체인 시계

정적 체인 테이블

수조로 기술된 체인 테이블을 정적 체인 테이블이라고 한다.
수조의 원소는 두 부분으로 구성되어 있으며 데이터와cur,데이터는 데이터를 저장한다.cur는 이 요소의 후계가 수조에 있는 하표를 저장합니다. (단일 체인 테이블의next 포인터와 유사합니다.)데이터 요소는 아래 구조체와 유사하다

typedef struct{
ElemType data; 
int cur;
} Componet,StaticLinkList[MAXSIZE];

예비 체인 테이블

수조에 사용되지 않은 수조 원소;

수조의 첫 번째 원소, 즉 0으로 표시된 원소의cur는 예비 체인표의 첫 번째 결점 아래 표시를 저장하고 수조의 마지막 원소의cur는 첫 번째 수치가 있는 원소의 아래 표시를 저장한다. 이것은 단일 체인표의 첫 번째 결점의 작용에 해당한다. 체인표가 비어 있을 때 0이다.

정적 체인 테이블의 삽입 조작

다음 그림과 같다.
초기 체인 테이블
삽입 작업
병은 을과 정 사이에 삽입하기;

원소 프로필을 예비 체인 테이블에 추가하기;

을의cur를 병의 유표로 바꾸기;

병의cur를 정의 유표로 바꾸기;

정적 체인 테이블의 장단점;

1. 장점

삽입과 삭제 작업을 할 때 커서만 수정하고 요소를 이동할 필요가 없기 때문에 순서 저장 구조에서의 삽입과 삭제 작업이 대량의 요소를 이동해야 하는 단점을 개선했다.

2. 결점

지속적인 스토리지 할당으로 인해 테이블 길이를 파악하기 어려운 문제가 해결되지 않았습니다.

순서 저장 구조의 무작위 접근 특성을 잃었다.

순환 체인 테이블

단일 체인 테이블에서 단말기 결점의 바늘 끝을 빈 바늘에서 지향 머리 결점으로 바꾸면 전체 단일 체인 테이블에 하나의 고리를 형성한다. 이런 머리와 꼬리가 연결된 단일 체인 테이블을 단일 순환 체인 테이블이라고 한다.약칭 순환 체인 테이블;

꼬리 지침:rear;

시작 결점:rear->next->next;

양방향 체인 테이블

단방향 체인 시계의 모든 체인 시계 결점에서
모든 체인 테이블 원소의 구조는 아래와 유사하다

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

비공식 순환 선두 결점의 양방향 체인 테이블

양방향 체인 테이블의 삽입 조작

저장 원소 e의 결점이 s라고 가정하고 결점 s를 결점 p와 p->next 사이에 삽입하는 것을 실현해야 한다.알고리즘 방향:

s->prior = p;  /* p s */
s->next = p->next; /* p->next s->next*/
p->next->prior = s; /* s p->next */
p->next = s; /* s p->next*/

양방향 체인 테이블 삭제 작업

p->prior->next = p->next;   /* p->next  p->prior */
p->next->prior = p->prior;  /* p->prior p->next  */
free(p);