양 방향 링크 의 핵심 조작

4064 단어 데이터 구조
순환 체인 시 계 는 단일 체인 시 계 를 바탕 으로 앞 구 를 가리 키 는 지침 prior 를 추가 하 는데 대체적으로 단일 체인 표 와 마찬가지 로 핵심 적 인 차 이 는 삽입 삭제 가 다르다 는 것 이다.
삽입 과 삭 제 를 중심 으로 쓰 는 데 중심 을 두 고 다른 기능 은 스스로 실현 할 수 있다.만약 에 양 방향 체인 시 계 를 잘 모 르 면 싱글 체인 시 계 를 잘 모 르 고 제 싱글 체인 시 계 를 보고 알 수 있 습 니 다.https://blog.csdn.net/doubleguy/article/details/83384327
1. 양 방향 링크 만 들 기 (후 삽입 법)
//          
void CreateList(LinkList &l,int n){
	l = new LNode;
	l->next = NULL;
	LNode *r = l;
	for(int i=0;idata);
		p->prior = r;
		r->next = p;
		r = r->next;
		p->next = NULL;
	}
}

2. 찾기 
여기 서 주의 하 세 요. 삽입 과 삭제 의 편 의 를 위해 제 가 찾 는 작업 의 반환 값 은 찾 을 위 치 를 가리 키 는 지침 입 니 다.예 를 들 어 제 가 GetElem (l, 4) 을 호출 할 때 링크 에 4 비트 이상 의 요소 가 있 을 때 네 번 째 요소 의 위 치 를 가리 키 는 지침 을 되 돌려 줍 니 다.그것 의 장점 은 삽입 과 삭제 에서 뚜렷하게 알 수 있다.
//  
LNode *GetElem(LinkList l,int i){
	LNode *p = l->next;
	int j = 1;
	while(jnext;
		j++;
	}
	while(!p||i

3. 삽입
GetElement () 함 수 를 직접 호출 하면 링크 의 i 번 째 요소 의 위치 지침 을 직접 찾 을 수 있 습 니 다. 얼마나 편리 합 니까?또한, 이 삽입 은 i 번 째 위치 앞 에 있 는 요소 삽입 입 니 다.
//  (          l  i         e)
Status ListInsert(LinkList &l,int i,int &e){
	LNode *p = NULL;
	if(!(p = GetElem(l,i)))
		return 0;
	LNode *r = new LNode;
	r->data = e;
	r->prior = p->prior;
	p->prior->next = r;
	r->next = p;
	p->prior = r;
	return 1;
}

 4. 삭제
GetElement () 함 수 를 호출 할 때 포인터 p 는 i 번 째 요 소 를 가리 키 는 것 입 니 다. p - > next 가 비어 있 는 지, 즉 삭 제 된 요소 가 마지막 인지 토론 해 야 합 니 다.
//           l  i      
Status ListDelete(LinkList &l,int i){
	LNode *p = NULL;
	if(!(p = GetElem(l,i)))
		return 0;
	if(p->next != NULL){
		p->prior->next = p->next;
		p->next->prior = p->prior;
	}
	else
		p->prior->next = NULL;
	delete p;
	return 1;
}

전체 코드 는 다음 과 같 습 니 다:  
#include
#include
#include
#pragma execution_character_set("utf-8")
typedef int Status;
using namespace std;
typedef struct LNode{
	int data;
	struct LNode *prior;
	struct LNode *next;
}LNode,*LinkList;
 
Status InitList(LinkList &l){
	l = new LNode;
	return 1;
}
 
//          
void CreateList(LinkList &l,int n){
	l = new LNode;
	l->next = NULL;
	LNode *r = l;
	for(int i=0;idata);
		p->prior = r;
		r->next = p;
		r = r->next;
		p->next = NULL;
	}
}
 
//  
LNode *GetElem(LinkList l,int i){
	LNode *p = l->next;
	int j = 1;
	while(jnext;
		j++;
	}
	while(!p||idata = e;
	r->prior = p->prior;
	p->prior->next = r;
	r->next = p;
	p->prior = r;
	return 1;
}
 
//           l  i      
Status ListDelete(LinkList &l,int i){
	LNode *p = NULL;
	if(!(p = GetElem(l,i)))
		return 0;
	if(p->next != NULL){
		p->prior->next = p->next;
		p->next->prior = p->prior;
	}
	else
		p->prior->next = NULL;
	delete p;
	return 1;
}
 
//     
void PrintList(LinkList &l){
	LNode *p = l->next;
	if(!p){
		printf("   !");
		return;
	}
	while(p){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("
"); } int main(){ LinkList l; int n; int status; int e,loc; printf(" n:"); scanf("%d",&n); printf(" %d :",n); CreateList(l,3); printf(" :"); PrintList(l); printf(" :"); scanf("%d%d",&loc,&e); status = ListInsert(l,loc,e); if(status){ printf(" !
:"); PrintList(l); } else printf(" , !
"); printf(" :"); scanf("%d",&loc); status = ListDelete(l,loc); if(status){ printf(" !
:"); PrintList(l); } else printf(" , !
"); return 0; }

좋은 웹페이지 즐겨찾기