数据结构-双链表基本操作（C语言实现）

参考书：王道考研数据结构

（此贴为博主学习408的笔记，因博主也是学习者，个人总结如有错误欢迎指正。如有侵权请告知，马上删除致歉）​​

一：双链表含义

        双链表是在单链表的基础上增加了一个指向前驱结点的prior指针。以此解决了单链表只可以找到后继而无法找到前驱结点的痛点问题，因为单链表只有一个指向后继的next指针，使得单链表只能从头到尾依次顺序的向后遍历。

        双链表的按值查找和按位查找与单链表相同，但是增加与删除操作上与单链表不同，不仅要修改后继指针，也要修改其prior前驱指针，在此过程中应注意不可断链！！

 二：双链表的插入操作演示

核心操作：

①s->next = p->next;

②p->next->prior = s;

③s->prior = p;

④p->next = s;

三：双链表删除 

核心操作：

1.p->next = q->next;

2.q->next->prior = p;

四：其余操作与单链表操作基本大同小异。

#include 
#include 



#define Max 10  


typedef struct DNode{
	int data;	//数据域
	struct DNode *prior,*next;		//前驱指针和后继指针
}DNode,*DLinkList;         //前者强调这是结点，后者强调这是链表


DLinkList InitDLinkList(DLinkList &L){
	int x; //输入data值
	L = (DLinkList)malloc(sizeof(DNode)); //申请链表的头结点
	DNode *s,*r = L;//初始化两个结点指针指向头结点
	if(L==NULL)			//没有申请到内存空间则返回false
		return false;
	L->prior=NULL;
	L->next=NULL;

	printf("输入（9999结束）");
	scanf("%d",&x);//输入插入的值，输入9999结束
	while(x!=9999){
		s = (DNode*)malloc(sizeof(DNode));//动态申请一个存放插入值的结点
		s->data=x;//将输入的值赋值给新申请结点
		r->next=s;//将指向头结点的r的next指针指向s
		s->prior=r;//将新节点的前驱指针指向上一个
		r=s;//将r的指针指向s新节点
		printf("输入（9999结束）");
		scanf("%d",&x);
	}
	r->next=NULL;//r的next指针指向NULL
	return L;
}


bool InsertNextDNode(DNode *p,DNode *s){
	if(p==NULL || s==NULL)
		return false;
	s->next=p->next;
	if(p->next !=NULL)
		p->next->prior = s;   
	s->prior = p;
	p->next = s;
	return true;
}


DNode *GetElem(DLinkList L,int i){
	int j=1;//因为有头结点，所以从1开始遍历
	if(i<1){//判断查找的位置是否合法
		printf("数值非法");
	}
	DNode *p = L->next;//初始化结点指针
	while(p!=NULL&&jnext;
		j++;
	}
	return p;
}


DLinkList DeleteNode(DLinkList &L,int i){
	DNode *p;
	p=GetElem(L,i);//调用按位查找函数
	if(p==NULL)
		return false;
	if(p->next!=NULL){
		p->prior->next = p->next;//p的前驱的后继指针指向p的后继
		p->next->prior=p->prior;//p的后继的前驱指针指向p的前驱
		free(p);	//释放
	}
	return L;
	

}


DLinkList InsertNextNode(DLinkList &L,DNode *p,int e){
	if(p==NULL)
		return false;
	DNode *s = (DNode*)malloc(sizeof(DNode));//申请不到内存空间则返回false
	if(s==NULL)
		return false;
	s->data=e;
	s->next=p->next;
	p->next->prior = s;
	s->prior = p;
	p->next=s;
	return L;
}

DLinkList InsertNNode(DLinkList &L,int i,int e)
{
	if(i<1)
		return false;
	DNode *s;
	int j=0;
	s=L;
	while(s!=NULL&&jnext;
		j++;
	}
	if(s==NULL)
		return false;
	
	return InsertNextNode(L,s,e);
}
 


int Length(DLinkList L)
{
	int len=0;
	DNode *p=L;
	while (p->next!=NULL)
	{
		p=p->next;
		len++;
	}
	return len;
}


void Show(DLinkList L){
	printf("当前单链表的所有元素：【head】<=>");
	DNode *p;
	p =L->next;
	while(p!=NULL){
		printf("[%d]<=>",p->data);
		p=p->next;
	}
	printf("NULL");
	printf("n");
	printf("当前表长为%dn",Length(L));
	printf("-----------------------------------------------------------n");
}

void DestroyList(DLinkList &L)
{
	
	DNode *p ,*q;//初始化两个指针，p用来free释放，q用来在p释放后将p指针指向下一个
	p= L->next;//删除带头链表头结点不删除
	q=p;		
	while(p!=NULL){
		q=p->next;  //提前将q指向下一个
		free(p);	//释放p
		p = q;		//将p指向q所指向的下一个
	}
	L->next = NULL; //头结点指向NULL
	printf("n销毁成功n");
}

int main(){
	DLinkList(l);
	l = InitDLinkList(l);
	Show(l);
	DeleteNode(l,3);
	printf("删除第三个位置的元素后：");
	Show(l);
	printf("在第二个位置后插入99：");
	InsertNNode(l,2,99);
	Show(l);
	return 0;
}