- 선형 표 의 링크 (LinkList) 요약

- 선형 표 의 링크 (LinkList) 요약
데이터 구조의 기본 순서 구조 에서 선형 표 는 두 가지 저장 논리 가 있 는데 하 나 는 순서 표 이 고 하 나 는 링크 이다.체인 테이블 에는 단일 체인 테이블, 이중 체인 테이블, 단일 순환 체인 테이블, 이중 순환 체인 테이블, 정적 체인 테이블 도 포함 된다.본 고 는 가장 기본 적 인 단일 체인 표 구 조 를 정리 하고 나머지 몇 가 지 는 정태 체인 표를 제외 하고 모두 이 를 바탕 으로 이해 하고 실현 할 수 있다.
목차
- 선형 표 의 링크 (LinkList) 요약
구조
LinkNode (결점 류)
LinkList (링크 클래스)
클래스 방법 실현
잘못
총결산
참고 문헌
 
구조
먼저 구 조 를 정의 하고 하나의 링크 는 여러 개의 체인 노드 로 연결 되 어 있 으 며 머리 결 점 은 있어 도 되 고 없어 도 된다.한편, 각 노드 는 두 개의 속성 을 포함 해 야 한다. 하 나 는 현재 노드 의 값 이 고 하 나 는 다음 노드 를 가리 키 는 지침 이다. 둘 중 하나 가 없어 서 는 안 된다. 만약 에 머리 결점 이 있 으 면 데이터 항목 의 위치 에 길 이 를 저장 할 수 있다.
 
체인 시 계 는 암벽 등반 이 라 고 생각 합 니 다. 한 점 을 밟 아야 다음 점 을 밟 을 수 있 습 니 다. 이렇게 계속 밟 으 면 모든 점 을 한 번 밟 습 니 다. 즉, 위의 점 에 따라 다음 점 을 얻 습 니 다.
선형 표 는 강의 동 1 층 교실 이 라 고 생각 합 니 다. 방 번호 만 있 으 면 이 교실 에 빨리 도착 할 수 있 습 니 다. 앞 뒤 교실 이 어디 인지 아 세 요?
 
LinkNode (결점 류)

class LinkNode{
	private :
		Elemtype data;
		LinkNode *nextNode;
	public:
		LinkNode(Elemtype data);//    
		LinkNode* next();//  next   
		Elemtype getData();//  data  
		void setNext(LinkNode *ln); //  next   
		~ LinkNode();//     	
};

LinkList (링크 클래스)

class LinkList{
	private :
		int len;
		bool flag;//     
		LinkNode *next;
	public:
		LinkList();//     
		void InitList();//    
		void setNext(LinkNode *ln);//       
		int length();//     
		int LocateElem(Elemtype elem);//    
		Elemtype GetElem(int i); //    
		LinkNode* GetNext();// //        
		void ListInsert(int i ,Elemtype elem);
		void ListDelete(Elemtype elem);//    
		void PrintList(); 
		bool Empty();
		void DestroyList();
		void MergeList(LinkList lb);//     ，   
		~ LinkList();//     		
};

클래스 방법 실현

/*
*win10   
*DEV C++ 5.11
*TDM-GCC 4.9.2 64bit
*/
#include
#include
#include 
#define WRONG 0

using namespace std;
template 
class LinkNode{
	private :
		Elemtype data;
		LinkNode *nextNode;
	public:
		LinkNode(Elemtype data);//    
		LinkNode* next();//  next   
		Elemtype getData();//  data  
		void setNext(LinkNode *ln); //  next   
		~ LinkNode();//     
		
}; 


template 
LinkNode::LinkNode(Elemtype data){//     
	this->data = data;
	this->nextNode = NULL;
}

template 
LinkNode::~ LinkNode(){//     
	free(this);
}

template 
LinkNode* LinkNode::next(){//  next   
	return this->nextNode;
}

template 
Elemtype LinkNode::getData(){//  next   
	return this->data;
}

template 
void LinkNode::setNext(LinkNode *ln){ //  next   
	this->nextNode = ln;
}




template 
class LinkList{
	private :
		int len;
		bool flag;//     
		LinkNode *next;
	public:
		LinkList();//     
		void InitList();//    
		void setNext(LinkNode *ln);//       
		int length();//     
		int LocateElem(Elemtype elem);//    
		Elemtype GetElem(int i); //    
		LinkNode* GetNext();// //        
		void ListInsert(int i ,Elemtype elem);
		void ListDelete(Elemtype elem);//    
		void PrintList(); 
		bool Empty();
		void DestroyList();
		void MergeList(LinkList lb);//     ，   
		~ LinkList();//     		
}; 

template 
LinkList::LinkList(){//     
	this->len = 0;
	this->next = NULL;
	this->flag = 1; 
}
 
template 
void LinkList:: InitList(){//    
	this->LinkList();
}

template 
void LinkList::setNext(LinkNode *ln){ //  next   
	this->next = ln;
}



template 
int LinkList::length(){//     
	return this->len;
}
 
template 
int LinkList::LocateElem(Elemtype elem){//    
	LinkNode *temp = this->next;
	int i = 1;
	while(temp!=NULL && temp->getData() != elem){//      
		i++;
		temp = temp->next();
	}
	if(temp->getData() == elem)
		return i;
	return 0;//     
}

template 
Elemtype LinkList::GetElem(int i){ //    
	LinkNode *temp = this->next;
	int j = 1; 
	while((++j!=i) && temp)
		temp = temp->next();
	if(i==j)
		return temp->next()->getData();
	else
		return NULL;
}
 
template 
LinkNode* LinkList::GetNext(){//       
	return this->next; 
} 

template 
void LinkList::ListInsert(int i ,Elemtype elem){//      ，       
	if(i==0)
		i=1;//    
	if(i==-1)
		i = this->len+1;//    
	if(i<=0||i>len+1)
		exit(WRONG);
	
	int j = 0;
	LinkNode *temp = new LinkNode(0);
	if(this->next==NULL){//      
		LinkNode *inNode = new LinkNode(elem);
		this->next = inNode;
		inNode->setNext(NULL);
		this->len++; 
		return;
	}
	else//   
		if(i==1){//   
			LinkNode *inNode = new LinkNode(elem);
			inNode->setNext(this->next);
			this->next = inNode;
			this->len++; 
			return;	
		}
		else
			temp = this->next;
	j+=2;
	while(j<=i-1){
		j++;
		temp = temp->next();
	}
		
	if((this->len==0)||(temp->getData()<=elem&&((temp->next()!=0)||(temp->next()->getData()>=elem))))
		flag = 1;
	else
		flag = 0;

	LinkNode *inNode = new LinkNode(elem);
	inNode->setNext((temp->next()));
	temp->setNext(inNode);
	this->len++;
}

 
template 
void LinkList::ListDelete(Elemtype elem){//    
	if(this->len == 0 )
		exit(WRONG);
	LinkNode *pre = this->next;
	LinkNode *temp = this->next;
	if(pre->getData()==elem){//     
		this->next=this->next->next();
		free(temp);
		this->len--;
		return ;
	}
	while(temp->getData()!=elem && temp){
		pre = temp;
		temp = temp->next();
	}
	if (temp->getData() == elem){
		pre->setNext(temp->next()) ;
		free(temp);
		this->len--;
	}
	else
		exit(WRONG);	
}
 
template 
void LinkList::PrintList(){ 
	LinkNode *temp = this->next;
	cout<len==0){
		cout<getData()<next()){
			cout<next()->getData()<next();
		}
	}
	cout<
bool LinkList::Empty(){
	return this->len == 0 ? 1 : 0; 
}
 
template 
void LinkList::DestroyList(){
	this->~LinkList();
}

template 
void LinkList::MergeList(LinkList lb){//     ，   
	if(this->flag&&lb.flag){//    ，     
		
		LinkList *lc = new LinkList();
		LinkNode *c  = new LinkNode(0);
		lc->setNext(c);
		lc->len = 0;
		while(lb.len!=0 && this->len!=0){
			if(this->next->getData() < lb.next->getData()){
				c->setNext(this->next);
				this->next = this->next->next();
				c = c->next();
				this->len--;lc->len++;
			}// 
			else{//       
				c->setNext(lb.GetNext());
				lb.setNext(lb.GetNext()->next());
				c = c->next();//lb     ，     
				lb.len--;lc->len++;
			}	
		}
		while(lb.len){
			c->setNext(lb.GetNext());
			lb.setNext(lb.GetNext()->next());
			c = c->next();
			lb.len--;lc->len++;
		}
		while(this->len){
			c->setNext(this->next);
			this->next = this->next->next();
			c = c->next();
			this->len--;lc->len++;
			//cout<next->next()<next = lc->next->next();
		this->len  = lc->len;		
	}else{//    ，     
		LinkNode *temp = new LinkNode(0);
		temp = this->next;
		if(this->len==0)//       
			this->next = lb.GetNext();
		else{
			while(temp->next())
				temp = temp->next();
			temp->setNext(lb.next);
		}
		this->len += lb.length();//    
	}
}

template 
LinkList::~LinkList(){//    
/*	LinkNode *del = this->next;
	while(del->next()!=NULL){//this->len > 1
		cout<next<next = this->next->next(); 
		free(del);
		del = this->next;//       	
		this->len--;
	
	}
	free(this);
*/	this->next = NULL;
	this->len  = 0;
}


int main(){
	LinkList *la = new LinkList();
	cout<PrintList();
	la->ListInsert(1,10);cout<PrintList();cout<length()<ListInsert(1,6); cout<PrintList(); cout<length()<ListInsert(2,8); cout<PrintList(); cout<length()<ListInsert(4,7); cout<PrintList(); cout<length()<ListDelete(8);   cout<PrintList();    cout<length()<GetElem(2)<LocateElem(6)< *lb = new LinkList();
	lb->ListInsert(1,10);lb->ListInsert(1,9);
	lb->ListInsert(1,8); lb->ListInsert(1,7);
	lb->ListInsert(1,6); lb->ListInsert(1,4);
	cout<PrintList();
	
	LinkList *lc = new LinkList();
	lc->ListInsert(1,5);lc->ListInsert(1,3);
	lc->ListInsert(1,2); lc->ListInsert(1,1);
	lc->ListInsert(1,0); 
	cout<PrintList();
	
	lb->MergeList(*lc);   cout<PrintList();
	lb->MergeList(*la);   cout<PrintList();
	
	la->DestroyList();
	cout<PrintList();cout<length()<

잘못
코드 가 실현 되 는 과정 에서 방법 반환 값 이 지침 인지 문제 가 있 는 지 알 수 없 었 고 삽입 방법 과 합병 방법 중의 점 간 논리 관 계 는 순환 에서 경계 값 의 판단 을 잘 하지 못 해 bug 가 빈발 했다.문제 가 발생 한 원인 은 인 코딩 과정 에서 형식 과 변수 디자인 이 규범 에 맞지 않 고 c + 언어 중의 기본 적 인 정 의 를 이해 하지 못 하 며 프로 그래 밍 경험 이 적다.
 
총결산
단일 체인 표 결점: 원소 elem + 다음 결점 지침 * next, 끝 결점 next 는 NULL 을 가리킨다.
쌍 사슬 표 결점: 원소 elem + 다음 결점 지침 * next + 위의 결점 지침 * pre, 앞 뒤 가 서로 가리킨다.
순환 싱글 체인 시트: 마지막 노드 의 next 지침 을 첫 번 째 노드 로 가리 킵 니 다.
순환 더 블 링크: 첫 번 째 노드 의 pre 는 끝 점 을 가리 키 고 끝 점 의 next 는 첫 번 째 노드 를 가리킨다.
정적 링크: 순서 표를 만 들 고 요소 elem + 다음 노드 에 next 를 표시 합 니 다. 마치 2 차원 배열 처럼 보 입 니 다.
참고 문헌
엄 울 민, 오위 민. 데이터 구조 (C 언어 판) [M]. 북경: 청화대학 출판사, 2013.
 
잘못 이 있 으 면 친구 에 게 아 낌 없 는 지적 을 바 랍 니 다.