단일 체인 표 및 그 기본 방법의 실현

단일 체인 표 및 그 기본 방법의 실현
정의: 선형 표 의 체인 저장 구 조 는 임의의 저장 장치 (연속 할 수도 있 고 연속 하지 않 을 수도 있 음) 를 사용 하여 선형 표 의 데이터 요 소 를 저장 합 니 다.각 노드 는 두 개의 도 메 인 을 포함 합 니 다. 포인터 도 메 인 (직접 후계 의 저장 위치 저장) 과 데이터 도 메 인 (데이터 요소 정 보 를 저장 하 는 데 사용).
특징: 링크 는 논리 적 으로 인접 한 요소 가 물리 적 위치 에서 도 인접 하도록 요구 하지 않 기 때문에 순서 표 가 무 작위 로 접근 하 는 장점 이 없습니다. 모든 요소 가 메모리 에 있 는 위 치 는 이 요소 의 직접 앞으로 가 는 지침 역 에 포함 되 어 있 습 니 다.그러나 체인 식 저장 구 조 는 요 소 를 삽입 하고 삭제 하 는 데 효율 이 높 아 요소 이동 의 대가 가 필요 없다.

//           

#include<iostream>
#include<iomanip>
#include<stdlib.h>
#include<string.h>
using namespace std;

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

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

//    
void DestroyList(LinkList &L){
	LinkList p = L->next, q;
	while(p){
		q = p;
		p = p->next;
		free(q);
	}
	free(L);
	L = NULL;
}

//    
void TraverseList(LinkList &L){
	LinkList p = L;
	while(p){
		cout<<setw(5)<<(p->data);
		p = p->next;
	}
	cout<<endl;
}

//   i   
bool GetElem(LinkList &L, int i, ElemType &e){
	LinkList p = L->next;	//p       
	int j = 1;
	while(p && j<i){
		p = p->next;
		++j;
	}
	if(!p||j>i)return false;	//     
	e = p->data;
	return true;
}

//  i        
bool ListInsert(LinkList &L, int i, ElemType e){
	LinkList p = L;
	int j = 0;
	while(p && j<i-1){
		p = p->next;
		++j;
	}
	if(!p||j>i-1)return false;
	LinkList s = (LinkList) malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

//   i   
bool ListDelete(LinkList &L,int i, ElemType &e){
	LinkList p = L;
	int j = 0;
	while(p->next && j<i-1){
		p = p->next;
		++j;
	}
	if(!(p->next) || j>i-1)return false;
	e = p->next->data;
	p->next = p->next->next;
	return true;
}

//    
void MergeList(LinkList &La, LinkList &Lb, LinkList &Lc){
	LinkList pa = La->next;
	LinkList pb = Lb->next;
	LinkList pc = Lc = La;
	while(pa && pb){
		if(pa->data <= pb->data){
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa? pa : pb;	//     
	free(Lb);
}

//     
void ReverseList(LinkList &L){
	if(L==NULL || L->next==NULL)return;	//    
	LinkList pNext = NULL;	//     
	LinkList pPrev = L;		//     
	LinkList pCur = L->next;//    

       //    ，                
	while(pCur != NULL){
		pNext = pCur->next;
		pCur->next = pPrev;
		pPrev = pCur;
		pCur = pNext;
	}
	L->next = NULL;	//              
	L = pPrev;		//       
}

int main(){
	//  
	cout<<"    "<<endl;
	LinkList L;
	CreateList(L, 10);
	TraverseList(L);

	cout<<"    "<<endl;
	ElemType e;
	GetElem(L,4,e);
	cout<<e<<endl;

	cout<<"    "<<endl;
	ListInsert(L,4,99);
	TraverseList(L);
	cout<<"    "<<endl;
	ListDelete(L,4,e);
	TraverseList(L);

	cout<<"    "<<endl;
	ReverseList(L);
	TraverseList(L);
	DestroyList(L);
	return 0;
}

결과:

    
    0    1    2    3    4    5    6    7    8    9   10
    
4
    
    0    1    2    3   99    4    5    6    7    8    9   10
    
    0    1    2    3    4    5    6    7    8    9   10
    
   10    9    8    7    6    5    4    3    2    1    0

메모: 위의 검색 작업 GetElem, 삽입 작업 ListInsert, 삭제 작업 ListDelete 의 시간 복잡 도 는 모두 O (n) 입 니 다.
여기 서 단일 체인 표 의 병합 정렬 알고리즘 은 시간 복잡 도와 순서 표 가 같 지만 공간 복잡 도 는 다르다.두 개의 링크 를 하나의 링크 로 통합 할 때 다른 새 표 의 노드 공간 이 필요 하지 않 습 니 다. 원래 두 개의 링크 에서 노드 간 의 관 계 를 해제 하고 요소 값 이 체감 되 지 않 는 관계 에 따라 모든 노드 를 새로운 표 로 연결 하면 됩 니 다.
by chenqi / 20110914