双链表的定义及其基本操作

双链表的代码定义

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->next=NULL;				//头结点之后暂无结点
	L->prior=NULL;				//头结点的prior永远指向NULL
	return true;
}

双链表的插入操作

//在*p结点之后插入*s结点
bool InsertNextNode(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;
}

双链表的删除结点操作

//删除*p结点的后继节点
bool DeleteNextNode(DNode *p){
	if(p=NULL)
		return false;
	Dnode *q=p->next;			//找到p的后继结点q
	if(q==NULL) 
		return fasle;			//p没有后继
	p->next=q->next;			
	if(q->next!=NULL)			//q不是最后一个结点
		q->next->prior=p;
	free(q);				//释放结点空间
	return true;
}