[대학원 데이터 구조] 제2 장 선형 표 - 단일 체인 표

2.3 선형 표 의 체인 표시
체인 식 저장 선형 표 시 는 주소 연속 저장 부 를 사용 할 필요 가 없다. 즉, 논리 적 으로 연속 되 는 요소 가 물리 적 으로 도 연속 되 지 않 아 도 된다. 이 는 '체인' 을 통 해 데이터 요소 간 의 논리 적 관 계 를 구축 하기 때문에 이동 요 소 를 삽입, 삭제 할 필요 가 없고 지침 만 수정 해 야 하지만 순서 표 무 작위 액세스 의 장점 을 잃 을 수 있다.
2.3.1 단일 체인 테이블 의 정의
선형 표 의 체인 식 저장 소 는 단일 체인 표 라 고도 부른다.
(1) 단일 체인 표 는 순서 저장 에 대량의 연속 저장 장치 가 필요 하 다 는 단점 을 잘 해결 할 수 있 지만 단일 체인 표 에 지침 도 메 인 을 추가 하고 공간 을 낭비 하 는 단점 도 존재 한다.
(2) 단일 체인 표 의 요소 가 분 산 된 것 은 저장 공간 에 분포 되 어 있 기 때문에 단일 체인 표 는 무 작위 액세스 가 아 닌 저장 구조 로 표 의 특정한 노드 를 직접 찾 을 수 없다.결점 을 찾 으 려 면 처음부터 옮 겨 다 니 며 순서대로 찾 아야 한다.
(3) 싱글 체인 시 계 는 보통 헤드 포인터 로 표 시 됩 니 다. 헤드 포인터 가 NULL 일 때 빈 시계 입 니 다.머리 지침 은 단지 지침 일 뿐이다.
(4) 헤드 노드: 보통 단일 체인 표 의 첫 번 째 데이터 노드 전에 하나의 노드 를 추가 합 니 다. 이렇게 하 는 것 은 단일 체인 표 의 조작 을 편리 하 게 하기 위해 서 입 니 다. 이 노드 는 데 이 터 를 포함 하지 않 고 data 도 메 인 은 표 의 길이 등 정 보 를 저장 할 수 있 습 니 다.
(5) 두 결점 과 두 지침 의 차이: 앞장 서 든 말 든 두 지침 은 첫 번 째 결점 을 가리킨다.한편, 두 결점 은 두 결점 체인 표를 가 진 첫 번 째 결점 이다. 이 결점 은 데 이 터 를 포함 하지 않 고 그 data 역 은 표 의 길이 등 정 보 를 저장 할 수 있 으 며 지침 역 은 첫 번 째 데이터 결점 의 주소 이다.
(6) 도입 두 결점 의 장점:
4. 567917. 첫 번 째 데이터 노드 의 주 소 는 두 노드 의 지침 역 에 저장 되 어 있 기 때문에 링크 의 첫 번 째 위치 에서 의 조작 은 다른 위치 에서 의 조작 과 같 기 때문에 특별한 처리 가 필요 없다
4. 567917. 시계 가 비어 있 든 없 든 머리 지침 은 머리 결점 의 비 공 지침 (빈 시계 에서 머리 결점 의 지침 역 이 비어 있 음) 을 가리 키 기 때문에 빈 시계 와 비 공 표 의 처리 가 일치 합 니 다
단일 체인 시트 의 결산 점 설명

//           ，data next，          ，               
typedef struct LNode{
    Elemtype data;            //   
    struct LNode *next;        //   
}LNode;
//       LNode,*LinkList;，          ，      ，      ，   LNode   

2.3.2 단일 체인 표 기본 작업 의 실현
1. 헤드 삽입 법 으로 링크 만 들 기

//      
LNode* headCreate(LNode *L){			//        
        L = (LNode*) malloc (sizeof(LNode));     //      
	int nodeData;
	LNode *node;
	L->next = NULL;				//          
	while(~scanf("%d", &nodeData)){
		if(nodeData == 12138){		//  12138        
			printf("    
");
			break;
		}
		node = (LNode*) malloc (sizeof(LNode));		//         
		node->data = nodeData;				//          
		node->next = L->next;		//                      
		L->next = node;			//                
	}
	printf("     
");
	return L;				//      
}

int main(){
	LNode *myLinkList;
	//    
	myLinkList = headCreate(myLinkList);
	//   
//	myLinkList = tailCreate(myLinkList); 
//	printLinkList(myLinkList);
}

2. 꼬리 삽입 법 으로 링크 만 들 기

//      
LNode* tailCreate(LNode *L){
	L = (LNode*) malloc (sizeof(LNode)); //      
	LNode *r = L;
	LNode *node;
	int data;
	L->next = NULL;
	while(~scanf("%d",&data)){
		if(data == 12138)
			break;
		node = (LNode*) malloc (sizeof(LNode));
		
		node->data = data;
		node->next = NULL;
		r->next = node;
		r = node;
	}
	return L;
}
int main(){
	LNode *myLinkList;
	//    
//	myLinkList = headCreate(myLinkList);
	//   
	myLinkList = tailCreate(myLinkList); 
//	printLinkList(myLinkList);
}

3. 일련 번호 로 결점 값 찾기

//         
LNode* GetElem(LNode *L,int i){
	LNode *p = L->next;	//             p， p     
	if(i == 0)
		return L;	//i==0        
	if(i < 1)		//i    ，   
		return NULL;
	int count = 1;	//count              ,         
	//printf("p->data=%d
",p->data);
	while( p != NULL){	
	//      i     ，  count       i，          ，p==NULL，       
	//      i       ，p   NULL，   i    
		if(count == i){
			break;
		}else {
			p = p->next;
			count++;
		}
	} 
	return p;
} 

4. 값 에 따라 결점 찾기

//      
LNode* LocateElem(LNode *L,int e) {
	LNode *p = L->next;			//             
	while(p != NULL){
		if(p->data == e){
			return p;			//    ，     
		}
		p = p->next;
	} 
	return NULL;				//   ，  NULL 
}

5. 삽입 동작

//    
int ListInsert(LNode *L,int i,int e){
	if(i < 1 || i > ListLength(L)+1 ){
		return 0;
	} 
	//       
	LNode *insertNode = (LNode*) malloc (sizeof (LNode) );	
	//        
	insertNode->data = e;
	//             i-1 
	//            ，frontNode        ，            
	LNode *frontNode = GetElem(L,i - 1);
	//    
	insertNode->next = frontNode->next;
	frontNode->next = insertNode;
	//     
	return 1;
} 

6. 결점 삭제

//    ，   i   
int ListDel(LNode *L,int i){
	if(i < 1 || i > ListLength(L) ){
		return 0;
	}
	LNode *frontNode = GetElem(L,i - 1);
	LNode *delNode = GetElem(L,i);
	//    
	frontNode->next = delNode->next;
	//    
	//     
	free(delNode); 
	return 1;
}

7. 시계 장 구하 기

//   
int ListLength(LNode *L){
	int length = 0;
	LNode *p = L->next;
	while(p != NULL){
		length++;
		p = p->next;
	}
	return length;
}