数据结构 | 每日一练（57）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．假设一个单循环链表，其结点含有三个域 pre、data、link。其中 data 为数据域；pre 为指针域，它的值为空指针（NIL）；link 为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。

正确答案

ps：||代表注释

1. [题目分析] 将具有两个链域的单循环链表，改造成双向循环链表，关键是控制给每个结点均置上指向前驱的指针，而且每个结点的前驱指针置且仅置一次。

void StoDouble（LinkedList la）∥la是结点含有pre，data，link三个域的单循环链表。其中data为数据域,pre为空指针域，link是指向后继的指针域。本算法将其改造成双向循环链表。

{ while（la->link->pre==null）

{la->link->pre=la； ∥将结点la后继的pre指针指向la。

la=la->link； ∥la指针后移。

}

} ∥算法结束。

[算法讨论] 算法中没有设置变量记住单循环链表的起始结点，至少省去了一个指针变量。当算法结束时，la恢复到指向刚开始操作的结点，这是本算法的优点所在。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-