*因借用C++引用语法，主体代码以C++为主，提及C语言
目录
基础知识
双链表结点中由两个指针域和一个数据域构成：*prior（指向前驱），data（数据域），*next（指向后驱）
双链表的定义
函数定义
typedef struct DNode//定义单链表
{
ElemType data;//数据域（该节点内存储的数据）
struct DNode *prior,*next;//指针域（该节点内存储的指向上下节点的指针）
}DNode,*DLinkList;//单链表的类型定义（顺序表的别名）函数实现
DL=(DLinkList)malloc(sizeof(DNode));//申请一个双向链表的空间双向链表头插法
图解
代码实现
DLinkList Dlist_head_insert(DLinkList &DL)//双向链表头插法
{
DNode *s;int x;
DL=(DLinkList)malloc(sizeof(DNode));//申请带头结点的链表空间DL
DL->next=NULL;//初始化为空链表
DL->prior=NULL;//初始化头结点
scanf("%d",&x);//从标准输入读取数据
while(x!=9999)//输入9999代表结束
{
s=(DLinkList)malloc(sizeof(DNode));//申请一个新空间给新结点指针s
s->data=x;//将读取值x赋给新结点指针s所指向的结点
s->next=DL->next;//1.让s指向的结点(x)的后驱等于原DL所指向结点(a)的后驱
if(DL->next!=NULL)//插入第一个结点时，不需要这一步操作
{
DL->next->prior=s;//2.让c(DL->next)的前驱结点为s所指向结点(x)
}
s->prior=DL;//3.让s指向的结点(x)的前驱为DL所指向的结点(a)
DL->next=s;//4.让DL指向的结点(a)的后驱为s所指向的结点(x)
scanf("%d",&x);//输入下一个元素
}
return DL;//完成建表
}
Dlist_head_insert(DL);双向链表尾插法
图解
代码实现
DLinkList Dlist_tail_insert(DLinkList &DL)//双向链表尾插法
{
int x;
DL=(DLinkList)malloc(sizeof(DNode));//申请带头结点的链表空间DL
DNode *s,*r=DL;//r为链表表尾结点
DL->prior=NULL;//初始化头结点
scanf("%d",&x);//从标准输入读取数据
while(x!=9999)//输入9999代表结束
{
s=(DNode*)malloc(sizeof(DNode));//申请一个新空间给新结点指针s
s->data=x;//将读取值x赋给新结点指针s所指向的结点
r->next=s;//1.让原尾部结点(aj)的后驱指向新尾部结点(ai)
s->prior=r;//2.让新尾部结点(ai)的前驱指向原尾部结点(aj)
r=s;//让指针r指向新的尾部结点
scanf("%d",&x);//输入下一个元素
}
r->next=NULL;//将尾结点的next指针赋值为NULL
return DL;//完成建表
}
Dlist_tail_insert(DL);按序号查找结点值
函数定义
DNode *GetElem(DLinkList DL,int i)//按序号查找结点值
{
int j=1;//定义遍历时计数值
DNode *p=DL->next;//定义p为头结点
if(i==0)//若i等于0，则返回头结点
return DL;
if(i<1)//若i无效，则返回NULL
return NULL;
while(p&&j<i)//从1开始遍历，查找第i个结点
{
p=p->next;//遍历
j++;//计数++
}
return p;//返回查找到的指针 函数实现
search=GetElem(DL,2);//查找表L中序号为i的值
if(search!=NULL)//查找成功
{
printf("按序号查找成功\n");
printf("%d\n",search->data);//输出表L中序号为i的值
}*与单链表查找方式相同
新结点插入第i个位置
图解
代码实现
bool DListFrontInsert(DLinkList DL,int i,ElemType e)//新结点e插入第i个位置
//L为被插入顺序表，i代表插入的位置（从1开始计数），e为要插入的元素
{
DLinkList p=GetElem(DL,i-1);//查找插入位置的前驱结点
if(NULL==p)//判断插入位置是否合法
{
return false;
}
DLinkList s=(DLinkList)malloc(sizeof(DNode));//为新插入的结点s申请空间
s->data=e;//将读取值x赋给新结点指针s所指向的结点
s->next=p->next;//1.让s指向的结点(x)的后驱等于原p所指向结点(a)的后驱
p->next->prior=s;//2.让c(p->next)的前驱结点为s所指向结点(x)
s->prior=p;//3.让s指向的结点(x)的前驱为p所指向的结点(a)
p->next=s;//4.让p指向的结点(a)的后驱为s所指向的结点(x)
return true;//建表成功
}
DListFrontInsert(DL,i,e);//在表DL中将新结点e插入第i个位置删除第i个结点
图解
代码实现
bool DListDelete(DLinkList DL,int i)//删除表L中的第i个元素
{
DLinkList p=GetElem(DL,i-1);//查找删除位置的前驱结点
if(NULL==p)//判断删除位置是否合法
{
return false;
}
DLinkList q;
q=p->next;//定义q指向被删除元素
if(q==NULL)//判断删除的元素是否存在
return false;
p->next=q->next;//1.使p所指向结点指针域等于原q所指向结点指针域
if(q->next!=NULL)//若删除结点q为最后一个元素，则不进行这步
{
q->next->prior=p;//2.让c(p->next)的前驱结点为p所指向结点(a)
}
free(q);//释放被删除结点指针的空间
return true;//删除合法，返回正确
}
DListDelete(DL,i);//删除表L中的第i个元素链表打印
void PrintDList(DLinkList DL)//打印顺序表DL
{
DL=DL->next;//使指针DL指向第一个元素
while(DL!=NULL)//检查L是否合法
{
printf("%3d",DL->data);//以每个元素三个空格大小输出表中数据
DL=DL->next;//指向下一个结点
}
printf("\n");
}
PrintDList(DL);//打印链表