선형 표 (1) - 기초 지식

1. 선형 표 의 개념
선형 표 (Linear List) 는 선형 데이터 구조 로 데이터 요소 의 비 공 유한 집합 에서 유일 하 게 '첫 번 째' 라 고 불 리 는 데이터 요소 가 존재 하 는 것 이 특징 이다.'마지막' 이 라 고 불 리 는 유일한 데이터 요소 가 존재 합 니 다.첫 번 째 를 제외 하고 집합 중의 모든 데이터 요 소 는 하나의 전구 만 있다.마지막 을 제외 하고 집합 중의 모든 데이터 요 소 는 하나의 후계 만 있다.
2. 선형 표 의 순서 저장
선형 표 의 순서 저장 은 한 그룹의 주소 로 연 속 된 저장 장치 로 선형 표를 순서대로 저장 하 는 데이터 요 소 를 말한다.이런 형식 으로 저 장 된 선형 표 는 순서 표 라 고 불 린 다.순서 표 의 논리 적 순 서 는 물리 적 순서 와 일치한다.
순서 표 는 데이터 요소 의 번호 에 따라 무 작위 로 접근 하 는 특징 을 가지 고 있다.고급 프로 그래 밍 언어 에 있 는 배열 형식 도 무 작위 액세스 특성 이 있 기 때문에 데이터 구조 에 있 는 순서 저장 구 조 를 배열 로 묘사 하 는 경우 가 많다.

#define LIST_INIT_SIZE 100
typedef struct{
	ElemType *elem;
	int length;
}SqList;

1. 순서 표 초기 화
즉, 순서 표 에 미리 정 의 된 크기 의 배열 공간 을 분배 하고 선형 표 의 현재 길 이 를 0 으로 설정 하 는 것 이다.

void InitList(SqList &L)
{
	L.elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(L.elem==NULL){
		printf("      ！
");
		exit(1);
	}
	L.length=0;
} 

2. 연산 삽입
표 의 제 i (1 < = i < = n) 개 요 소 를 삽입 하기 전에 값 이 e 인 새로운 요 소 를 삽입 하고 삽입 한 후에 원래 표 의 길 이 를 하나 더 합 니 다.삽입 할 때 n 번 째 요 소 를 i (총 n - i + 1) 번 째 요소 로 한 자리 옮 겨 야 합 니 다.이때 시간 복잡 도 는 O (n) 이다.

int ListInsert(SqList &L,ElemType e,int i)
{
	if(i<0||i>L.length)
		return 0;//     
	else{
		for(j=L.length;j>i;j--){
			L.elem[j]=L.elem[j-1];
		}
		L.elem[i]=e;
		L.length++;
		return 1;//     
	} 
}

3. 삭제 작업
표 의 i (1 < = i < = n) 개 요 소 를 선형 표 에서 삭제 하고 원래 표 의 길 이 를 1 로 줄 입 니 다.삭제 할 때 i + 1 에서 n (총 n - i) 개 요 소 를 한 단계 앞으로 이동 해 야 합 니 다.이 작업 시간의 복잡 도 는 O (n) 입 니 다.

int ListDelete(SqList &L,int i)
{
	if(i<0||i>L.length)
		return 0;
	p=&(L.elem[i-1]);//p         
	q=L.elem+L.length-1;//q   ，          
	for(++p;p<=q;++p){
		*(p-1)=*p;
	} 
	L.length--;
	return 1;
} 

4. 값 으로 찾기
선형 표 에서 주어진 값 e 와 같은 데이터 요 소 를 찾 습 니 다. e 와 같은 데이터 요 소 를 찾 으 면 순서 표 에 저 장 된 위 치 를 되 돌려 줍 니 다. 그렇지 않 으 면 - 1 시간 복잡 도 는 O (n) 입 니 다.

int LocationElem(SqList &L,ElemType e)
{
	i=0;
	while(i

3. 선형 표 의 체인 저장
1. 싱글 체인 시트
단일 체인 테이블 의 결점 은 하나의 데이터 영역 과 하나의 지침 영역 으로 구성 된다.단일 체인 시트 의 접근 은 반드시 처음부터 시작 해 야 한다.헤드 포인터 가 링크 의 첫 번 째 노드 의 저장 위 치 를 표시 합 니 다.마지막 노드 의 포인터 영역 이 비어 있 습 니 다 (NULL).
결점 을 시작 하기 전에 부가 하 는 결점 을 두 결점 이 라 고 한다.헤드 노드 의 가입 은 완전히 연산 의 편 의 를 위해 서 입 니 다. 데이터 필드 는 정의 되 지 않 습 니 다. 포인터 필드 에 저 장 된 것 은 첫 번 째 데이터 노드 의 주소 이 고 빈 표 는 비어 있 습 니 다.
단일 체인 시트 의 저장 구조:

typedef struct LNode{
	ElemType data;
	Struct LNode *next;
}LNode,*LinkList;

헤드 포인터 변 수 를 정의 하면 LinkList L 이 있 고 L 을 단일 체인 표 의 헤드 포인터 로 표시 합 니 다.
단일 체인 테이블 에서 i 번 째 요 소 를 얻 으 려 면 반드시 처음부터 지침 을 찾 아야 하기 때문에 단일 체인 테이블 은 무 작위 액세스 가 아 닌 저장 구조 이다.
단일 링크 만 들 기:
n 개 요소 의 값 을 역순 으로 입력 하고 선두 노드 의 단일 링크 L 을 만 듭 니 다.처음부터 결산 점 의 빈 표 부터 하나의 데이터 요 소 를 읽 을 때마다 하나의 결산 점 을 신청 한 다음 에 링크 머리 에 꽂 습 니 다. 링크 머리 에 삽입 되 기 때문에 데 이 터 를 읽 는 순서 와 선형 표 의 논리 적 순 서 는 반대 입 니 다.

void CreateList(LinkList &l,int n)
{
	L=(LinkList)malloc(sizeof(LNode));
	L->next=NULL;
	for(i=n;i>0;i++){
		p=(LinkList)malloc(sizeof(LNode));
		scanf(&p->data);
		p->next=L->next;
		L->next=p;
	}
}

시계 길이:
이동 포인터 p 와 카운터 n 을 설정 하고 초기 화 한 후에 p 가 가리 키 는 결점 뒤에 몇 개의 결점 이 있 습 니 다. p 는 뒤로 이동 하고 계수 기 는 하 나 를 추가 합 니 다.체인 테이블 L 은 선두 결점 을 가 진 선형 체인 테이블 (선형 테이블 의 길 이 는 머리 결점 을 포함 하지 않 음) 이다.

int ListLength(LinkList &L)
{
	n=0;
	p=L;
	while(p->next){
		p=p->next;
		n++;
	}
	return n;
}

번호 찾기:
노드 를 이 끄 는 링크 L 에 i 번 째 요소 가 존재 하면 그 값 을 e 병 에 게 1 로 되 돌려 주 고 그렇지 않 으 면 0 으로 되 돌려 줍 니 다.

int GetElemList(LinkList &L,int i,ElemType &e)
{
	p=L->next;
	j=1;
	while(p&&jnext;
		j++;
	} 
	if(!p||j>i)	return 0;
	else{
		e=p->data;
		return 1;
	}
}

삽입 연산:

int InsertList(LinkList &L,int i,ElemType e)//         L  i        e 
{
	p=L;
	j=0;
	while(p&&jnext;
		j++;
	} 
	if(!p||jdata=e;
		s->next=p->next;
		p->next=s;
		return 1;
	}
}

삭제 연산:

int DeleteList(LinkList &L,int i)//         L ，   i   
{
	p=L;
	j=0;
	while(p->next&&jnext;
		j++;
	} 
	if(!p->next||jnext;
		p->next=q->next;
		free(q);
		return 1;
	}
} 

2. 순환 링크
표 에서 마지막 결점 의 지침 역 은 머리 결점 을 가리 키 고 전체 체인 표 는 하나의 고 리 를 형성 하면 단일 순환 체인 표를 구성한다.이로부터 표 중의 어떤 결점 에서 출발 하여 표 중의 다른 결점 을 찾 을 수 있다.단일 순환 링크 의 꼬리 지침 (T 로 설정) 을 알 았 을 때 다른 한쪽 의 머리 지침 은 T - > next - > next (선두 결점) 입 니 다.
두 개의 단일 순환 링크 H1, H2 에 대한 연결 작업 은 H2 의 첫 번 째 데이터 노드 를 H1 꼬리 노드 에 연결 하 는 것 이다.만약 에 헤드 포인터 로 표 지 를 한다 면 첫 번 째 링크 의 끝 점 을 찾 아야 한다. 그 시간 복잡 도 는 O (n) 이 고 링크 는 각각 꼬리 포인터 T1, T2 로 표 지 를 하면 시간 복잡 도 는 O (1) 이다. 그 조작 은 다음 과 같다.

p=T1->next;//  T1       
T1->next=T2->next->next;//     
free(T2->next);//           
T2->next=p;//       

3. 양 방향 링크 (이중 링크 목록)
양 방향 링크 의 결산 점 에 두 개의 지침 역 이 있 는데 하 나 는 직접 연결 을 가리 키 고 다른 하 나 는 직접 전구 를 가리 키 며 그 저장 구 조 는 다음 과 같다.

typedef struct DuLNode{
	ElemTyPE DATA;
	struct DuLNode *prior;
	struct DuLNode *next;
}DuLNode,*DuLNode;

노드 삭제:

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

노드 삽입:

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

4. 정적 링크
포인터 형 이 묘사 한 선형 링크 와 구별 되 고 배열 로 묘사 한 링크 를 정적 링크 라 고 합 니 다.그 유형 은 다음 과 같다.

#define MAXSIZE 100//       
typedef struct{
	ElemType data;
	int cur;
}component,SlinkList[MAXSIZE];

배열 의 한 분량 은 결점 을 표시 하 는 동시에 포인터 대신 커서 (지시기 cur) 로 결점 이 배열 에 있 는 상대 적 인 위 치 를 표시 합 니 다.배열 의 0 분 의 1 은 두 결점 으로 볼 수 있 고 지침 역 은 링크 의 첫 번 째 결점 을 가리킨다.이러한 저장 구 조 는 비교적 큰 공간 을 미리 분배 해 야 하지만 선형 표 의 삽입 과 삭제 작업 을 할 때 이동 요 소 를 필요 로 하지 않 고 지침 만 수정 해 야 하기 때문에 체인 식 저장 구조의 주요 장점 을 가진다.S 가 SlinkList 형 변수 라 고 가정 하면 S [0]. cur 는 첫 번 째 노드 가 배열 에 있 는 위 치 를 표시 합 니 다. i = 을 설정 하면
S [0]. cur 는 S [i]. data 는 선형 표 의 첫 번 째 데이터 요 소 를 저장 하고 S [i]. cur 는 두 번 째 노드 가 배열 에 있 는 위 치 를 가리킨다.일반적인 상황 에서 i 번 째 분량 이 링크 의 첫 번 째 k 번 째 노드 를 나타 내 면 S [i]. cur 는 k + 1 번 째 노드 의 위 치 를 가리킨다.따라서 정적 링크 에서 선형 표 의 조작 과 동적 링크 가 비슷 하고 전체 커서 i 로 동적 포인터 p, i = s [i]. cur 의 조작 을 포인터 로 한 후 이동 (p = p - > next 와 유사) 합 니 다.
정적 링크 초기 화:

void InitSpace(SlinkList &S)//     S            ，S[0].cur    
//“0”      
{
	for(i=0;i

정적 링크 에서 포 지 셔 닝 작업 실현:
정적 단일 링크 L 에서 첫 번 째 값 이 e 인 요 소 를 찾 습 니 다.찾 으 면 L 에 있 는 위 치 를 되 돌려 줍 니 다. 그렇지 않 으 면 0 으로 돌아 갑 니 다.

int LocateElem(SlinkList &S,ElemType e)
{
	i=S[0].cur;
	while(i&&S[i].data!=e)
		i=S[i].cur;
	return i;
}

4. 순서 표 와 링크 의 비교
1. 순서 표 의 특징

선형 표 의 순서 저장 구 조 는 논리 적 으로 인접 한 두 요소 가 물리 적 위치 에서 도 인접 하기 때문에 무 작위 로 표 의 한 요 소 를 액세스 할 수 있다.

순서 표 의 단점 은 크기 가 고정 되 어 증감 결점 에 불리 하 다 는 것 이다. 순서 표를 삽입 하고 삭제 할 때 대량의 데이터 요 소 를 이동 해 야 하기 때문에 운행 효율 에 영향 을 미친다.

순서 표 가 공간 을 미리 분배 할 때 반드시 최대 공간 에 따라 분배 해 야 하 며 빈 점 을 충분히 이용 하지 못 한다.

2. 링크 의 특징

선형 표 의 체인 식 저장 구 조 는 주소 연속 저장 장치 로 이 루어 질 필요 가 없다. 논리 적 으로 연속 되 는 두 데이터 요소 가 물리 적 으로 도 인접 하도록 요구 하지 않 고 '체인' 을 통 해 데이터 요소 간 의 논리 적 관 계 를 구축 하기 때문에 무 작위 로 접근 할 수 없고 순서대로 만 접근 할 수 있 기 때문이다.

링크 의 장점 은 포인터 방식 으로 결점 을 증감 하 는 것 으로 매우 편리 하 며 포인터 의 방향 만 수정 하고 데이터 요 소 를 이동 하지 않 아 도 된다 는 것 이다.

링크 의 모든 노드 에 지침 도 메 인 을 추가 하여 추가 저장 공간 이 커진다.