정적 링크 의 설명 과 구현

사실 정적 링크 란 포인터 대신 배열 로 단일 체인 표를 묘사 하 는 것 이다.먼저, 배열 안의 요 소 는 두 개의 데이터 필드 로 구성 되 어 있 습 니 다. data 와 cur. 그 중에서 data 는 데이터 요 소 를 저장 하 는 데 사 용 됩 니 다. 즉, 처리 해 야 할 데이터 입 니 다.cur 는 단일 체인 표 의 next 지침 에 해당 하 며, 이 요 소 를 저장 한 후 배열 의 아래 에 표 시 됩 니 다. cur 는 커서 라 고도 합 니 다.이런 배열 로 묘 사 된 링크 는 정적 링크 라 고 하 는데 이런 링크 를 실현 하 는 방법 도 커서 실현 법 이 라 고 한다.
1. 정적 링크 저장 구조 와 초기 화

//          
#define MAXSIZE 1000  //      
typedef struct
{
	ElemType data;  // ElemType        ，     int
	int cur;        //   
}Component, StaticLinkList[MAXSIZE];

배열 에서 우 리 는 배열 의 첫 번 째 와 마지막 요 소 를 특수 요소 로 처리 하고 데 이 터 를 저장 하지 않 습 니 다.일반적으로 사용 되 지 않 은 배열 요 소 를 예비 링크 라 고 부 르 고 배열 의 첫 번 째 요소 (아래 표 시 는 0) 의 cur 는 예비 링크 의 첫 번 째 노드 의 아래 표 시 를 저장 합 니 다.한편, 배열 의 마지막 요소 인 cur 는 첫 번 째 수치 가 있 는 요소 의 아래 표 시 를 저장 하고 머리 결점 에 해당 하 며 링크 가 비어 있 으 면 0, 0 은 빈 지침 을 나타 낸다.배열 에서 어떤 분량 이 사용 되 지 않 았 는 지 알 기 위해 서 는 사용 되 지 않 은 모든 분량 을 커서 체인 으로 예비 링크 로 만들어 야 합 니 다.초기 화 에서 우 리 는 처음 과 끝 을 제외 한 분량 을 예비 링크 로 연결 합 니 다.

//    ：     space           
void InitList(StaticLinkList space)
{
	int i;
	for (i = 0; i < MAXSIZE; i++)
		space[i].cur = i + 1;
	space[MAXSIZE - 1].cur = 0;  //     ，       cur 0
}

2. 정적 링크 의 삽입 작업 과 삭제 작업
동적 링크 구조 에서 결점 의 신청 과 방출 은 각각 malloc () 와 free () 두 함 수 를 빌려 실현 한다.그러나 정적 링크 에서 조작 하 는 것 은 배열 이기 때문에 우 리 는 이 두 가지 함 수 를 손 으로 써 야 한다. 또한 정적 링크 의 길 이 를 구 하 는 함수 도 있다.

//        ，          ，    0
int Malloc_SLL(StaticLinkList space)
{
	int i = space[0].cur;  //             
	if (space[0].cur)
		space[0].cur = space[i].cur;  //               ，          cur                    
	return i;
}

//    k            
void Free_SLL(StaticLinkList space, int k)
{
	//    
	space[k].cur = space[0].cur;
	space[0].cur = k;
}

//         
int ListLength(StaticLinkList L)
{
	int j = 0;
	int i = L[MAXSIZE - 1].cur;
	while (i)
	{
		i = L[i].cur;
		j++;
	}
	return j;
}

//  L  i           e
bool ListInsert(StaticLinkList L, int i, ElemType e)
{
	int j, k, l;
	k = MAXSIZE - 1;
	if (i < 1 || i > ListLength(L) + 1)
		return false;
	j = Malloc_SLL(L);  // j        
	if (j)  //  j  0，          
	{
		L[j].data = e;
		for (l = 1; l < i - 1; l++)  //    i-1   
			k = L[k].cur;
		//     
		L[j].cur = L[k].cur;
		L[k].cur = j;
		return true;
	}
	return false;
}

//    L  i     e
bool ListDelete(StaticLinkList L, int i, ElemType &e)
{
	int j, k;
	if (i < 1 || i > ListLength(L))
		return false;
	k = MAXSIZE - 1;
	for (j = 1; j <= i - 1; j++)  //    i-1   
		k = L[k].cur;
	j = L[k].cur;   // j  i      
	e = L[j].data;  // e       
	L[k].cur = L[j].cur
	Free_SLL(L, j);
	return true;
}

3. 정적 링크 의 장단 점
장점:

작업 을 삽입 하고 삭제 할 때 커서 만 수정 하고 요 소 를 이동 할 필요 가 없 으 며 순서 저장 구조 에 대량의 요 소 를 삽입 하고 삭제 해 야 한 다 는 단점

을 개선 했다.
단점:

연속 저장 분배 에 따 른 표 장 이 확정 하기 어 려 운 문 제 를 해결 하지 못 했다

순서 저장 구조의 무 작위 액세스 특성 을 잃 었 습 니 다