정적 링크 의 설명 과 구현
14403 단어 데이터 구조 와 알고리즘데이터 구조체인 테이블
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. 정적 링크 의 장단 점
장점:
단점: