数据结构——第二章 线性表（5）——双向循环链表

1.双向循环链表的定义

单向链表便于查询后继结点，不便于查询前驱结点。为了方便两个方向的查询，可以在结点中设两个指针域，一个存放直接前驱结点的地址，另一个存放直接后继结点的地址。
双向循环链表的数据类型描述如下。

typedef struct dnode
{
ElemType* data;
struct dnode* pre;//存放前驱结点的地址
struct dnode* next;//存放后继结点的地址
}DNode,*DLinkList;

2.双向循环链表的基本操作实现

2.1 双向循环链表的初始化操作

双向循环链表的初始化是创建一个带有头结点的空链表。
分析：初始化操作需要将申请的头结点地址分别赋给头指针以及头结点的两个指针域，双向循环链表为空的条件是L->next == L&&L->pre == L为真，算法如下。
【算法】

int initDLinkList(DLinkList* L)
{*L = (DLinkList)malloc(sizeof(DNode));if (*L == NULL){perror("initDLinkList::");exit(0);}(*L)->pre = (*L)->next = *L;return 1;
}

2.2.双向循环链表的插入操作

双向循环链表有两个方向，其后继方向的单向循环链表相同。
分析：插入新结点必须考虑前驱和后继方向的链接，插入位置按后继方向查找。由于新结点的两个指针域是无确定指向的，因此将按以下顺序完成。
（1）确定新结点的直接前驱和直接后继。
s->pre=p;s->next=p->next;
（2）确定p->next的直接前驱。
p->next->pre=s;
（3）确定p的后继。
p->next=s;
【算法】

int insertDLinkList(DLinkList L, int i, ElemType x)
{DLinkList p = L, s;int pos = 0;//让p指向第i-1个结点，pos记录结点的位置while (p->next != L && pos < i - 1){p = p->next;pos++;}if (p->next == L && pos<i - 1 || pos>i - 1){printf("插入位置不合理！\n");return 0;}s = (DLinkList)malloc(sizeof(DNode));if (s == NULL){perror("insertDLinkList::");return 0;}s->data = x;s->pre = p;s->next = p->next;p->next->pre = s;p->next = s;return 1
}

2.3. 双向循环链表的删除操作

【算法实现】

int deleteDLinkList(DLinkList L, int i)
{DLinkList p = L, q;int pos = 0;if (L->next == L && L->pre == L){printf("链表为空！\n");return 0;}while (p->next != L && pos < i - 1){p = p->next;pos++;}if (p->next == L || pos > i - 1){printf("删除位置不合理！\n");return 0;}q = p->next;p->next = q->next;p->next->pre = p;free(q);return 1;
}