使用C语言实现双向链表（带头结点）

目录

1.双链表

2.双链表的相关操作

（1）数据结构的定义

（2）初始化和销毁

（3）判断空和表的长度

（4）节点的后插操作

（5）按序查找第i个节点和按值查找节点

（6）定位删除和按序删除

（7）打印操作

（8）主函数

（9）测试

---

1.双链表

相对于单链表来说就是多一个前驱的指针prior，指向前一个节点（主要是为了方便删除和插入）。

注：由于之前的实现的单链表总是会遇到一种情况就是，如果要删除当前的节点p的话，那么只能通过一种技巧的方式计算交换值；但是如果是需要进行更加复杂的操作的话，就会比较麻烦，可能还需要辅助的指针r来指向当前节点的前驱，这会给程序写起来和理解起来带来不便，所以为了实现当前节点能够访问前驱节点，那么提出了双链表的概念。

使用C语言实现单链表（带头结点）

使用C语言实现单链表（不带头结点）

2.双链表的相关操作

（1）数据结构的定义

#include
#include
 
#define MAXSIZE 10
 
typedef int ElemType;
 
typedef struct DNode {
	ElemType data;
	struct DNode*prior,*next;
}DNode,*DLinkList;
 
//清单列表
void MenuLinkList(){
	printf("-------------1.插入操作-------------\n");
	printf("-------------2.定位插入操作---------\n");
	printf("-------------3.按序查找操作---------\n");
	printf("-------------4.按值查找操作---------\n");
	printf("-------------5.定位删除操作---------\n");
	printf("-------------6.按值删除元素---------\n");
	printf("-------------7.删除整个表元素节点---\n"); 
	printf("-------------8.表的长度-------------\n");
	printf("-------------9.打印操作-------------\n");
	printf("-------------10.结束操作-------------\n");
} 

（2）初始化和销毁

//初始化操作
void InitDLinkList(DLinkList&L){
	L=(DNode*)malloc(sizeof(DNode));
	if(L==NULL){
		printf("申请空间失败!\n");
		return ;
	}
	L->prior=NULL;
	L->next=NULL;
	printf("申请空间成功!\n");
} 
 
//销毁表（头节点不销毁） 
DNode* DestryDLinkList(DNode*p,DLinkList&L,int flag=9){
	//从尾部开始删除节点
	DNode*r=p; 
	while(r!=L){
		DNode*s=r;
		r=r->prior;
		r->next=s->next;
		free(s);
	}
	//如果是结束操作的话，直接将头节点释放 
	if(flag==10){
		free(L); 
		L=NULL;
	}
	return r;
} 

这里的销毁操作主要是从最后节点开始进行删除，更加的方便，如果从头结点开始删除的话，需要判断的条件更多，相对麻烦一点，所以采用这种方法。读者自己可以实现从前往后的删除操作。

（3）判断空和表的长度

//判空
bool Empty(DLinkList L){
	if(L->next==NULL){
		return true;
	}else{
		return false;
	}
} 
//表的长度
int DLinkListLength(DLinkList L){
	int len=0;
	DNode*p=L->next;
	while(p!=NULL){
		len++;
		p=p->next;
	}
	return len;
} 

（4）节点的后插操作

//节点的插入操作(后插) 
DNode* InsertDLinkList(DNode*p,ElemType e){
	if(p==NULL){
		printf("插入的节点不合法!\n");
		return NULL;
	}
	DNode*s=(DNode*)malloc(sizeof(DNode));
	s->data=e;
	s->next=p->next;
	p->next=s;
	s->prior=p;
	printf("插入节点成功!\n");
	return s;
} 
 
//在第i个位置插入节点
void InsertIDLinkList(DLinkList&L,int i,ElemType e){
	DNode*p=FindDNode(L,i);
	//如果是插入到尾节点 
	if(p->next==NULL){
		InsertDLinkList(p,e); 
		return ;
	}
	//插入到中间的节点 
	if(p!=NULL){
		DNode*s=(DNode*)malloc(sizeof(DNode));
		s->data=e;
		s->next=p->next;
		p->next->prior=s;
		p->next=s;
		s->prior=p; 
		printf("插入节点成功!\n");
		return ;
	}
} 

（5）按序查找第i个节点和按值查找节点

//查找第i个位序的节点
DNode*FindDNode(DLinkList L,int i){
	if(L==NULL){
		printf("表为空!\n");
		return NULL;
	}
	if(i<0||i>DLinkListLength(L)){
		printf("查找的位置不正确!\n");
		return NULL;
	}
	int j=1;
	DNode*p=L->next;
	while(p!=NULL&&j
		p=p->next;
		j++;
	}
	return p;
} 
//按值查找操作
DNode*FindDElem(DLinkList L,ElemType e){
	if(L==NULL){
		printf("表为空!\n");
		return NULL;
	}
	DNode*p=L->next;
	while(p->data!=e){
		p=p->next;
	}
	return p;
} 

（6）定位删除和按序删除

//定位删除节点
void DeleteDLNode(DLinkList&L,int i,ElemType&e){
	DNode*p=FindDNode(L,i);
	e=p->data; 
	//如果是尾节点直接删除 
	if(p->next==NULL){
		p->prior->next=p->next;
		free(p);
		return ;
	}
	if(p!=NULL){
		DNode*s=p;
		p->prior->next=s->next;
		p->next->prior=s->prior;
		free(s);
		return ;
	}
} 
//按值删除
void DeleteDElem(DLinkList&L,ElemType e){
	DNode*p=FindDElem(L,e);
	//如果是尾节点直接删除 
	if(p->next==NULL){
		p->prior->next=p->next;
		free(p);
		return ;
	}
	if(p!=NULL){
		DNode*s=p;
		p->prior->next=s->next;
		p->next->prior=s->prior;
		free(s);
		return ;
	}
} 

（7）打印操作

//打印
void PrintDLinkList(DLinkList L){
	DNode*p=L->next;
	while(p!=NULL){
		printf("%d\t",p->data);
		p=p->next;
	}
	printf("\n");
} 

（8）主函数

int  main(){
	DLinkList L;
	InitDLinkList(L);
	//对顺序表进行插入操作
	ElemType x;
	int flag=-1;
	DNode*p=L; 
	//各种操作 
	while(1) {
		int i=0;
		ElemType e=0;
		MenuLinkList();
		printf("请输入操作: ");
		scanf("%d",&flag);
		int len=0;
		DNode*s;
		switch(flag){
			case 1:
				printf("请输入元素(-1_end): ");
				scanf("%d",&x);
				while(x!=-1) {
					p=InsertDLinkList(p,x);
					printf("请输入元素(-1_end): ");
					scanf("%d",&x);
				} 
				break;
			case 2:
				printf("请输入元素插入位置: \n");
				scanf("%d",&i); 
				printf("请输入元素: ");
				scanf("%d",&x);
				InsertIDLinkList(L,i,x);
				break;
			case 3:
				printf("请输入查找元素位置: ");
				scanf("%d",&i);
				s=FindDNode(L,i);
				if(s!=NULL){
					printf("查找的元素为 = %d\n",s->data);
				}
				break;
			case 4:
				printf("请输入要查找的值: ");
				scanf("%d",&x);
				s=FindDElem(L,x);
				if(s!=NULL){
					printf("查找的元素存在!\n");
				}else{
					printf("查找的元素不存在!\n");
				}
				break;
			case 5:
				printf("请输入删除的定位位置: ");
				scanf("%d",&i);
				DeleteDLNode(L,i,e);
				printf("删除的元素为 = %d\n",e);
				break;
			case 6:
				printf("请输入要删除的元素: ");
				scanf("%d",&e);
				DeleteDElem(L,e);
				break;
			case 7:
				p=DestryDLinkList(p,L);
				printf("删除成功!\n");
				break;
			case 8:
				len=DLinkListLength(L);
				printf("表的长度 = %d\n",len);
				break;
			case 9:
				PrintDLinkList(L);
				break;
			default:
				DestryDLinkList(p,L,flag);
				printf("结束操作\n");
		}
		if(flag==10){
			break;
		}
	}
	return 0;
}

（9）测试