5双链表带头结点

5双链表带头结点

数据结构持续总结ing

//初始化、判空、在p结点之后插入s结点、删除p结点的后继结点、销毁双链表
//尾插法建立双链表、头插法建立双链表、输出 
#include <stdio.h>
#include <stdlib.h>//malloc,free函数库
typedef int ElemType;//int另命名  

typedef struct DNode{
	ElemType data;
	struct DNode *prior,*next;//前驱和后继指针 
}DNode,*DLinkList;

bool InitDLinkList(DLinkList &L){//初始化 
	L=(DNode *)malloc(sizeof(DNode));//分配一个头结点
	if(L==NULL)
	    return false;
	L->prior=NULL;//头结点的prior永远指向NULL 
	L->next=NULL;//头结点之后暂时还没有结点 
	return true; 
	
}

bool Empty(DLinkList L){//判空（带头结点） 
	if(L->next==NULL)
	    return false;
	else
	    return true;
} 

bool InsertNextNode(DNode *p,DNode *s){//在p结点之后插入s结点 
	if(p==NULL || s==NULL)//非法参数 
	    return false;
	
	s->next=p->next;//s的next指针指向p的下一个结点 
	
	if(p->next !=NULL)//如果p结点有后继结点 
	    p->next->prior=s;//p的下一个结点的prior指针指向s 
	
	s->prior=p;//s的prior指针指向p结点 
	p->next=s;//p的next指针指向s结点 
	
	return true;
	
}

bool DeleteNextDNode(DNode *p){//删除p结点的后继结点 
	if(p==NULL)//非法参数 
	    return false;
	
	DNode *q=p->next;//找到p的后继结点q 
	if(q==NULL)//p没有后继 
	    return false;
	
	p->next=q->next;//p的next指针指向q的下一个结点 
	
	if(q->next !=NULL)//q结点不是最后一个结点 
	    q->next->prior=p;//q的下一个结点的prior指针指向p 
	
	free(q);//释放结点空间 
	return true;	 
}
 
 void DestoryList(DLinkList &L){//销毁双链表 
 	while(L->next !=NULL)//循环释放各个数据结点 
 	    DeleteNextDNode(L);
 	
	free(L);//释放头结点   注意：销毁表时才能删除头结点 
 	L=NULL;//头指针指向NULL 
 }

//1、后向遍历 
//while(p!=NULL)
//    p=p->next;
//2、前向遍历	
//while(p!=NULL)
//    p=p->prior;
//3、前向遍历（跳过头结点） 
//while(p->prior!=NULL)
//    p=p->prior;


DLinkList List_TailInsert(DLinkList &L){//尾插法建立双链表（带头结点）
	int x;
	L=(DLinkList)malloc(sizeof(DNode));//建立头结点,注意此处返回的是DLinkList，初始化空表 
	DNode *s;
	DNode *r=L;//r为表尾指针
	
	scanf("%d",&x);//输入结点的值
	while(x!=999){
		s=(DNode *)malloc(sizeof(DNode));//创建新结点（此时s结点已在循环体外声明）
		
		s->data=x;
		r->next=s;
        s->prior=r;
		r=s;//r指向新的表尾结点
		 
		scanf("%d",&x); 
	}
	r->next=NULL;//尾结点指针置空 
	return L;

	
} 

DLinkList List_HeadInsert(DLinkList &L){//头插法建立双链表（带头结点） 
	DNode *s;
	int x;
	L=(DLinkList)malloc(sizeof(DNode));//创建头结点 
	
	L->next=NULL;//初始化为空链表，养成好习惯，只要是初始化链表，都应该先把头指针指向NULL
	L->prior=NULL;//初始化 
	
	scanf("%d",&x);
	while(x!=9999){
		s=(DNode *)malloc(sizeof(DNode));//创建新结点（此时s结点已在循环体外声明） 
		
		s->data=x;
		s->next=L->next;
		if(L->next!=NULL)//双链表不为空，L的下一个结点的prior指针指向s 
		    L->next->prior=s;
		L->next=s;//将新结点插入表中，L为头指针
		s->prior=L;//s的prior指针指向L 
		
		scanf("%d",&x);
	}
	
	return L;
}



void DispList(DLinkList L){//输出 
	int i=1;
 	DNode *p=L->next;//定义一个结点指针p指向头结点的下一个结点
 	
	while(p!=NULL){ //如果p不为空则循环
		printf("第%d个元素为%d\n",i,p->data);
		p=p->next;//移动指针p遍历链表
		i++;
	
	}
	 
} 

int main(){
	DLinkList L;
	List_HeadInsert(L); 
	DispList(L);
}