기초 데이터 구조 - 양 방향 링크 의 실현

다음 코드 는 양 방향 링크 의 실현 으로 양 방향 링크 와 단 방향 링크 의 차이 가 크 지 않 기 때문에 실현 할 때 요소 증가 와 요 소 를 삭제 하 는 작업 만 실현 했다.
단 방향 링크 와 의 차 이 를 정리 하 다.
주로 코드 를 쓸 때 하나의 링크 요소 의 next 포인터 와 pre 포인터 두 방향 을 고려 해 야 합 니 다. 테스트 를 할 때 링크 를 정방 향 으로 하고 역방향 으로 한 번 뛰 어야 코드 의 정확성 을 확인 할 수 있 습 니 다.
체인 테이블 의 조작 이 가장 복잡 한 것 은 체인 테이블 헤드 와 테이블 끝의 토론 이다.
다음 코드 는 VS 2012 테스트 를 거 쳤 습 니 다.

#include 
#include 

//      
typedef struct listEle
{
	int data;
	struct listEle *pre;
	struct listEle *next;
}listEle;

//    
typedef struct list
{
	listEle *head;
	listEle *tail;
	int length;
}list;

//       
list* createList()
{
	list *l = (list*)malloc(sizeof(list));
	l->head = NULL;
	l->tail = NULL;
	l->length = 0;
	return l;
}

//    
int clearList(list *&l)
{
	if(!l) return -1;
	if(!l->head || !l->tail || l->length == 0) return 1;
	listEle *temp = l->head;
	listEle *dropEle = NULL;
	int i = 0;
	for(;ilength && temp; ++i)
	{
		dropEle = temp;
		temp = temp->next;
		free(dropEle);
	}
	l->head = NULL;
	l->tail = NULL;
	l->length = 0 ;
	if(i == l->length) return 1;
	return -1;
}

//    
void destroyList(list *&l)
{
	if(!l) return ;
	clearList(l);
	free(l);
	l = NULL;
}

//      （  ，    ）
void showList(list *l)
{
	if(!l ) 
	{
		printf("list not exist!
");
		return ;
	}
	if(!l->head || !l->tail || l->length == 0) 
	{
		printf("empty list!
");
		return ;
	}
	listEle *temp = l->head;
	int i = 0;
	printf("->:
");
	for(;ilength && temp; ++i,temp = temp->next)
	{
		printf("%d ",temp->data);
	}
	printf("
");
	temp = l->tail;
	i = 0;
	printf("length && temp; ++i,temp = temp->pre)
	{
		printf("%d ",temp->data);
	}
	printf("
");
}

//    
int insertElem(list *&l, int index, int *e)
{
	if(!l || index <0 || index >l->length || !e) return -1;
	listEle *temp = l->head;
	listEle *newEle = (listEle*)calloc(1,sizeof(listEle));
	newEle -> data = *e;
	int i = 0;
	for(;inext);
	if(i==index -1)
	{
		if(temp->next)
		{
			newEle->next = temp->next;
			temp->next->pre = newEle;
		}
		else
		{
			newEle->next = NULL;
			l->tail = newEle;
		}
		temp->next = newEle;
		newEle->pre = temp;
		l->length ++;
		return 1;
	}
	else if(index == 0)
	{
		if(!l->head || l->length == 0)
		{
			if( index > 0) return -1;
			newEle ->next = NULL;
			newEle->pre = NULL;
			l->head = newEle;
			l->tail = newEle;
			l->length = 1;
			return 1;
		}
		else
		{
			newEle->next = l->head;
			l->head->pre = newEle;
			newEle->pre = NULL;
			l->head = newEle;
			l->length ++;
			return 1;
		}
	}
	return -1;
}

//    
int deleteElem(list *&l, int index)
{
	if(!l || !l->head || !l->tail || l->length == 0 || index <0 || index >= l->length) return -1;
	listEle *temp = l->head;
	listEle *dropEle = NULL;
	int i = 0;
	for(;inext);
	if(i == index -1)
	{
		if(temp->next)
		{
			dropEle = temp->next;
			temp ->next = dropEle->next;
			if(dropEle->next)
			{
				dropEle->next->pre = temp;
			}
			else
			{
				l->tail = temp;
			}
			free(dropEle);
			dropEle=NULL;
			l->length --;
		}
		return -1;
	}
	else if(index == 0)
	{
		dropEle = l->head;
		if(l->tail == l->head) l->tail = NULL;
		l->head = dropEle->next;
		free(dropEle);
		dropEle = NULL;
		l->length --;
		return 1;
	}
	return -1;
}

//    
int main()
{
	list *l = createList();
	int e = 1;
	insertElem(l,0,&e);
	insertElem(l,10,&e);
	e = 2; insertElem(l,1,&e);
	e = 987; insertElem(l,0,&e);
	e = 15; insertElem(l,2,&e);
	e = 234; insertElem(l,0,&e);
	showList(l);

	deleteElem(l,2);
	showList(l);
	deleteElem(l,10);
	deleteElem(l,0);
	deleteElem(l,l->length -1);
	showList(l);

	destroyList(l);
	showList(l);

	getchar();
	return 0;
}