02142 ＜ 데이터 구조 서론 ＞ 제2 장 선형 표

2.1 선형 표 의 기본 개념

선형 표 (Linear List) 는 일종 의 선형 구조 로 n (n > = 0) 개의 데이터 요소 로 구 성 된 빈 서열 이 있 고 데이터 요 소 는 이 라 고도 부른다. 결점 개수 n 을 라 고 부른다. n = 0 일 때 선형 표 는 어떠한 데이터 요소 도 포함 하지 않 고 빈 표 라 고 부른다. ()

기본 적 인 특징: 선형 표 에서 결점 은 1 대 1 의 관 계 를 가진다. 만약 에 결점 이 0 이 아니라면 시작 결점 이 직접적인 전구 가 없 는 것 을 제외 하고 다른 결점 은 있 고 직접적인 전구 만 있다.터미널 노드 가 직접 후계 되 지 않 은 것 을 제외 하고 다른 노드 는 있 고 하나의 직접 후계 만 있다.

선형 표 기본 연산 및 기능 설명:

Initate (L) 초기 화: 데이터 요소 가 없 는 빈 테이블 L = 0 을 만 듭 니 다

표 길이 길이 (L): 선형 표 의 길 이 를 되 돌려 줍 니 다.

테이블 요소 읽 기 Get (L, i): 선형 테이블 i 번 째 요소 되 돌리 기

포 지 셔 닝 Locate (L, x): 선형 표 에서 데이터 요소 값 이 x 와 같은 결점 번 호 를 찾 습 니 다. 여러 개 있 으 면 최소 값 을 되 돌려 주 고 찾 지 못 하면 0

을 되 돌려 줍 니 다.

Insert (L, x, i) 삽입: 선형 표 L 의 i 번 째 요 소 를 삽입 하기 전에 x 의 새로운 데이터 요 소 를 삽입 합 니 다.

Delete (L, i) 삭제: 선형 i 번 째 요소 삭제

2.2 선형 표 의 순서 저장
선형 표 의 순서 저장 방법 은 표 의 결점 을 컴퓨터 메모리 의 연속 적 인 저장 장치 에 순서대로 저장 하 는 것 이다. 데이터 요 소 는 선형 표 에서 의 인접 관 계 는 그들의 저장 공간 에서 의 저장 위 치 를 결정 한다. 즉, 논리 구조 에서 인접 한 결점 은 저장 위치 도 인접 하 다. 순서대로 저장 하여 실현 하 는 선형 표를 순서 표 라 고 한다.일반적으로 데 이 터 를 사용 하여 순서 표를 표시 합 니 다. 일반적인 상황 에서 요소 의 비교 와 이동 횟수 는 다음 과 같 습 니 다. n-i+1 회 입 니 다. 예 를 들 어 순서 표 는 9 개의 요소 가 있 고 세 번 째 요소 앞 에 새로운 요 소 를 삽입 하면 이동 해 야 하 는 요소 의 개 수 는 9 - 3 + 1 = 7 개 입 니 다.
2.3 선형 표 의 링크 저장 소
단일 체인 시트, 순환 링크, 양 방향 순환 링크, 가장 간단 한 것 은 단일 체인 시트 로 나 뉜 다.
2.3.1 싱글 체인 테이블
data 부분 은 데이터 도 메 인 이 라 고 하 는데 선형 표 의 데이터 요 소 를 저장 하 는 데 사 용 됩 니 다. next 부분 은 포인터 나 체인 도 메 인 이 라 고 합 니 다. 이 지침 은 본 노드 에 포 함 된 데이터 요소 의 직접적인 후계 점 을 가리 키 고 있 습 니 다. 모든 노드 는 포인터 링크 를 통 해 링크 (Link List) 를 형성 하고 head 는 헤드 포인터 변수 라 고 합 니 다. 이 변수의 값 은 단일 체인 표 의 첫 번 째 노드 를 가리 키 는 지침 입 니 다.
2.3.2 선형 표 의 기본 연산:

초기 화

LinkList InitiateLinkList() {
	LinkList head; //   
	head = malloc(sizeof(Node));   //       ,      
	head->next=NULL;   //          NULL
	return head;
}

표 장 구하 기

int LengthLinkList(LinkList head){
	Node * p = head;  //   p     ,      
	int cnt =0;   //       0
	while(p->next != NULL) {  //         
		p = p->next;   //            
		cnt++;
	}
	return cnt;
}

읽 기 요소

//      ,    i     ,    ,              ;     NULL
Node *GetLinklist(LinkList head, int i){
	Node *p;  //         
	p=head->next //        
	int c = 1;
	while((c<=i) && (p!=NULL)){
		p=p->next;
		c++;
	}
	if i==c return p;
	else return NULL;

}

포 지 셔 닝

//          x      ,         ,     0
int LocateLinkList(LinkList head, DataType x){
	Node *p;
	p=head->next;
	int c=0;
	while(p!=NULL && p->data!=x){
		i++;
		p=p->next;
	}
	if (p!=NULL) return i+1;
	else return 0;
}

알고리즘 문자 설명 삽입: 주어진 값 x 를 링크 헤드 의 i 번 째 노드 에 삽입 하기 전에: 먼저 i - 1 번 째 노드 q 를 찾 은 다음 에 x 의 새로운 노드 p 를 생 성 합 니 다. p 의 지침 은 q 의 직접 후계 노드 를 가리 키 고 q 의 지침 도 메 인 은 p 를 가리 키 며 이렇게 하면 단일 링크 의 삽입 연산 을 완성 할 수 있 습 니 다.

void InsertLinklist(LinkList head, DataType x, int i){
	Node *p, *q;
	if (i==1) q=head;
	else q = GetLinklist(head, i-1);
	if (q==NULL) exit("       ")
	else {
	p = malloc(sizeof(Node)); //      
	p->data = x;  //        x
	p->next = q->next; // p  next   q      
	q->next =p; //q        p
}
}

알고리즘 문자 설명 삭제: 값 i 를 지정 하고 링크 의 i 번 째 노드 를 링크 에서 이동 시 키 며 관련 노드 의 지침 도 메 인 을 수정 하여 나머지 노드 의 링크 관 계 를 유지 합 니 다.

void DeleteLinklist(LinkList head, int i){
	Node *q, *p;
	if (i==1) q=head;
	else q = GetLinklist(head, i-1);  //          
	if (q!=NULL && q->next!=NULL){  //                  
		p=q->next;  //       
		q->next = p->next;  //      
		free(p);  //           
	else exit("     ")
	
}

}

2.5 기타 링크
2.5.1 순환 링크
단일 체인 시트 에서 마지막 노드 의 지침 역 이 첫 번 째 노드 를 가리 키 면 순환 링크 를 구성 할 수 있 습 니 다. 순환 링크 에서 모든 노드 에서 출발 하여 전체 링크 를 스 캔 할 수 있 습 니 다.
2.4.2 양 방향 순환 링크
단일 체인 시트 에서 각 노드 에 직접 앞 구 를 가리 키 는 포인터 필드 (prior) 를 설정 하면 각 노드 에 두 개의 포인터 prior data next 가 있 습 니 다.