数据结构导论-2.4 线性表的链式存储之循环链表与双向循环链表

我就是我 2022-05-08 13:56 173阅读 0赞

**循环链表与双向循环链表**

**一、循环链表**

1.思路

对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头指针置入该指针域，则使得链表头尾结点相连，就构成了单循环链表。

2.特点

无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活：从表中任一结点出发均可找到表中其他结点，提高查找效率。

3.图示

![70][]

**二、双向循环链表**

1．思路

每个结点包含两个指针域，一个指向直接前趋(prior) ，一个指向直接后继(next)。

双链表由头指针唯一确定。

将双链表中的头结点和尾结点链接起来可以构成循环链表，并称之为双向循环链表。

2．图示

![70 1][]

3．类型说明

> struct dbnode
> 
> \{ DataType data;
> 
> struct dbnode \*prior,\*next;
> 
> \}
> 
> typedef struct dbnode, \*dbpointer;
> 
> typedef dbpointer DLinkList;

4.双向循环链表的基本运算

1）删除

设p指向待删结点，删除\*p可通过以下语句完成

> p->prior->next=p->next;　　　　 //p前驱的后继为p的后继
> 
> p->next->prior=p->prior; 　　　　//p后继的前驱为p的前驱
> 
> free(p); 　　　　　　　　　　　//释放\*p的空间

![70 2][]

2）插入

在p所指结点的后面插入一个新结点\*t,需要修改4个指针，而且要**注意语句的顺序**。

> t->prior=p;
> 
> t->next=p->next;
> 
> p->next->prior=t;
> 
> p->next=t;

![70 3][]

**基于特殊链表的算法设计**

【例题·算法设计题】

若循环单链表长度大于1，p为指向链表中某结点的指针，试编写一算法删除p结点的前驱结点。

【解】

> Node \*delete(p)
> 
> Node \*P;
> 
> \{ 
> 
> Node \*q,\*r;
> 
> q=p;
> 
> While (q->next!=p) q=q->next; 　　　//找到p的前驱q
> 
> r=q;
> 
> while (r->next!=q) r=r->next; 　　　　//找到q的前驱r
> 
> r->next=p;　　　　　　　　　　　 //从链中摘掉q
> 
> free(q);
> 
> return(p);
> 
> \}

【解析】算法的思路是先找到p的前驱q,再找到q的前驱r,然后删除q，因为是循环链表，所以不必判断是否到达表尾，比较简单。大家也可对此算法进行改进。

[70]: /images/20220508/bfed8ea47ce649fe98fb2089db3209f4.png
[70 1]: /images/20220508/de7ff13f9ffb4ab8a1e56481293c6a01.png
[70 2]: /images/20220508/8fae8a23d5c8449db5a4440b90d9e745.png
[70 3]: /images/20220508/c257bc6a6a194bed9fcc0e8ec0841b17.png