外观
2.18 循环链表
歌单播完最后一首
音乐播放器有一种"列表循环":歌单里有A、B、C三首歌,A、B、C播完,接着播A,一直循环下去。
把歌单存成2.14那样带头结点的单链表,每首歌是一个结点。正在播的这首记作cur,现在播到了C:
text
L = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ A │ 109 │────►│ B │ 105 │────►│ C │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
头结点 cur按"下一首",就是顺着cur的地址格走一步。从A到B、从B到C都没问题。可C的地址格是0,后面没有结点,播不下去了。
列表循环要求C的下一首是A。可这个关系,链表里没有记下来。
本节问题怎样在链表里记下"最后一首的下一首是第一首"?
什么是循环链表
2.9说过:关系丢了,就记下来。"C的下一首是A"没有记,那就让C的地址格不再是0,而是指回链表的开头。
指回头结点,不直接指A。头结点一直都在,A却可能被删掉;空歌单里没有A,头结点也照样能首尾相接。
这样,整条链首尾相接,成了一个圈:
text
L = 120
│ ╭─────────────────────────────────────────────────────╮
│ │ │
▼ ▼ │
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ │
│ │ 100 │────►│ A │ 109 │────►│ B │ 105 │────►│ C │ 120 ├──╯
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
头结点和原来比,只变了一个格子:C的地址格从0变成120,绕回头结点,就是上面那条长箭头。
像这样首尾相接的链表,叫循环链表。单链表首尾相接,叫循环单链表。一个循环链表,就是一串结点连成一个圈,头结点也在圈上。
空歌单只有头结点,它的地址格指向它自己:
text
L = 120
│ ╭────╮
│ │ │
▼ ▼ │
┌───┬─────┐ │
│ │ 120 ├─╯
└───┴─────┘
120
头结点下一首
现在cur在C上,按"下一首"。顺着C的地址格走一步,到的是120号,也就是头结点。头结点不存歌,要再走一步,才到A:
text
L = 120
│ ╭─────────────────────────────────────────────────────╮
│ │ │
▼ ▼ │
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ │
│ │ 100 │────►│ A │ 109 │────►│ B │ 105 │────►│ C │ 120 ├──╯
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
第1步 第2步 起点从A按下一首到B、从B到C,走一步就到,碰不到头结点。只有从最后一首往下走时,才会经过头结点。
写成函数:
c
Node *NextSong(LinkList *L, Node *cur) {
cur = cur->next; /* 顺着next走一步 */
if (cur == *L) /* 走到头结点,它不存歌 */
cur = cur->next; /* 再走一步,到第一首 */
return cur;
}从C开始连按六次,播的是A、B、C、A、B、C。从任何一首出发,一直按下一首,都能把整个歌单一圈一圈地播下去。
上一首:双向循环链表
播放器还有"上一首"。在A上按上一首,列表循环要求回到C。
单链表只能往后走。用2.17的双向链表,每个结点多记一个前一个结点的地址。再让头结点的前一个地址指向C,前后两个方向就都首尾相接了:
text
L = 120
│ ╭────────────────────────────────────────────────────────────────────────────╮
│ │ │
▼ ▼ │
┌─────┬───┬─────┐ ┌─────┬───┬─────┐ ┌─────┬───┬─────┐ ┌─────┬───┬─────┐ │
│ │ │ ├────►│ │ │ ├────►│ │ │ ├────►│ │ │ ├──╯
│ 105 │ │ 100 │ │ 120 │ A │ 109 │ │ 100 │ B │ 105 │ │ 109 │ C │ 120 │
╭─┤ │ │ │◄────┤ │ │ │◄────┤ │ │ │◄────┤ │ │ │
│ └─────┴───┴─────┘ └─────┴───┴─────┘ └─────┴───┴─────┘ └─────┴───┴─────┘
│ 120 100 109 105 ▲
╰────────────────────────────────────────────────────────────────────────────────╯
头结点上面那条长箭头是C的后一个地址,指回头结点;下面那条是头结点的前一个地址,指向C。双向链表首尾相接,叫双向循环链表。
"上一首"和"下一首"对称,把next换成prior:
c
Node *PrevSong(LinkList *L, Node *cur) {
cur = cur->prior; /* 顺着prior走一步 */
if (cur == *L) /* 走到头结点,它不存歌 */
cur = cur->prior; /* 再走一步,到最后一首 */
return cur;
}其他操作的变化
循环链表里没有NULL了。原来凡是靠NULL判断"走到头"的地方,都要改成"回到头结点"。下面以循环单链表为例,逐个看。
初始化。空表的头结点指向自己:
c
/* 原来 */ (*L)->next = NULL;
/* 现在 */ (*L)->next = *L;双向循环链表的头结点,前一个地址也指向自己。
判空。空表就是头结点的后一个是它自己:
c
/* 原来 */ (*L)->next == NULL
/* 现在 */ (*L)->next == *L求长度、遍历。从第0个结点往后走,原来走到NULL就停,现在回到头结点就停:
c
/* 原来 */ for (Node *p = (*L)->next; p != NULL; p = p->next)
/* 现在 */ for (Node *p = (*L)->next; p != *L; p = p->next)按位序的插入、删除。从头结点走i步,原来走到NULL说明位置不合法;现在是走着走着又绕回了头结点:
c
for (int k = 0; k < i; k++) {
prev = prev->next;
if (prev == *L) return 0; /* 绕回头结点:没有第i-1个 */
}销毁。原来从头结点一路释放到NULL。现在没有NULL,从第0个结点释放到回到头结点为止,最后再释放头结点:
c
Node *p = (*L)->next;
while (p != *L) { /* 释放到回到头结点为止 */
Node *next = p->next;
free(p);
p = next;
}
free(*L); /* 最后释放头结点 */循环还有一个附带的好处。2.17双向链表的InsertAfter、DeleteAfter里,各有一个if (p->next != NULL):最后一个结点后面没有结点,要跳过一步。双向循环链表里,每个结点后面都有结点,最后一个后面是头结点,这两个if就可以去掉了。
练习1:循环歌单里的地址
填空
头结点在120号,A、B、C分别在100、109、105号。
- 存成循环单链表,C的地址格是
- 空歌单时,头结点的地址格是
- 存成双向循环链表,头结点的前一个地址是
循环链表首尾相接:最后一个结点指回头结点;双向循环时,头结点的前一个是最后一个结点。空表只有头结点,它指向自己。
练习2:遍历歌单,写到哪停?
单选
把循环单链表里的歌从头到尾数一遍,p从第0个结点出发:
c
for (Node *p = (*L)->next; ______; p = p->next)
n++;空白处应该填什么?
A
p != *LB
p != NULL循环链表里没有NULL,p会一圈一圈地走下去,停不下来。
C
p->next != NULL同样等不到NULL,停不下来。
最后一个结点的后一个是头结点。p回到头结点,就说明每首歌都数过了。
练习3:NextSong去掉if,会怎样?
单选
有人把下一首写成了这样:
c
Node *NextSong(LinkList *L, Node *cur) {
return cur->next;
}cur在C上时按下一首,会怎样?
A
返回头结点,播放器要播一首不存在的歌
B
正常回到A
C的地址格指向的是头结点,不是A。走一步只到头结点。
C
返回NULL,播放停止
循环链表里没有NULL,C的后一个是头结点。
头结点也在圈上,可它不存歌。从最后一首往下走,会先经过头结点,要再走一步才到第一首。
到这里你有了循环链表,首尾相接,从任何一个结点出发都能走遍全表。下一步顺序表和链表各有输赢,什么场景该选哪个。