单链表和双链表的区别：
定义双链表：
和单链表不同的是，双链表定义指针需要定义两个：前驱和后继指针
typedef struct DNode //定义双链表节点类型
{
ElemType data;//数据域
struct DNode* prior, * next;//前驱和后继指针
}DNode,*DLinkList;//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;
}
void testDLinkList()
{
//初始化链表
DLinklist L;
InitDLinkList(L);
}
//判断双链表是否为空
bool Empty(DLinklist L)
{
if (L->next == NULL)
return true;
else
return false;
}
双链表的插入：
后插操作：
bool InsertNextDNode(DNode* p, DNode* s)
{
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
}
但是，如果此时的p是最后一个节点，那么p->next->prior = s,是不存在的，那么我们需要对上述代码进行修改：
修改如下：
bool InsertNextDNode(DNode* p, DNode* s)
{
s->next = p->next;
if(p->next!=NULL)//对p是否为最后一个节点进行判断
p->next->prior = s;
s->prior = p;
p->next = s;
}
前插操作：
void DInsertBefore(DListNode*p,DataType x)
{
//在带头结点的双链表中，将值为x的新结点插入*p之前，设p≠NULL
DListNode
*s=malloc(sizeof(DListNode));
s->data=x;
s->prior=p->prior;
s->next=p;
p->prior->next=s;
p->prior=s;
}
而前插操作的实现：先找到指定节点的前驱结点，再对前驱结点进行后插操作。
双链表的删除：
但是，如果此时的p是最后一个节点，那么p->next->prior = s,是不存在的，那么我们需要对上述代码进行修改：
//删除p节点的后继节点
bool DelteNextDNode(DNode* p)
{
if (p == NULL)
return false;
DNode*q=p->next;//找到p的后继节点q
if (q == NULL)//p没有后继节点
return false;
p->next = q->next;
if (q->next != NULL)//q节点不是最后一个节点
q->next->prior = p;
free(q);//释放节点空间
return true;
}
释放双链表：
void DestoryList(DLinklist& L)
{
//循环释放各个数据节点
while (L->next != NULL)
DeletNextDNode(L);
free(L);//释放头结点
L = NULL;//头结点指向NULL
}
双链表的遍历：
//后向遍历
while (p != NULL)
{
//对节点p做相应处理
p = p->next;
}
//前向遍历
while (p != NULL)
{
//对节点p做相应处理
p = p->prior;
}
//前向遍历（跳过头结点）
while (p ->prior!= NULL)
{
//对节点p做相应处理
p = p->prior;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/81461.html
