外观
2.14 头结点
为什么要头结点
回到cat这个链表:
text
L = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105插入和删除,都要先找到"前一个结点",再改它的地址格。插在a后面,前一个是a结点;删t,前一个也是a结点。
可是c是第0个,它前面没有结点。插在第0个、删第0个时,没有"前一个结点"可改,只能改头指针。所以2.12的Insert和2.13的Delete,各多了一个"第0个改头指针"的分支。
本节问题能不能让第0个结点前面也有一个结点,把分支去掉?
什么是头结点
办法就在问题里:第0个前面没有结点,那就放一个。在第一个结点前面固定放一个结点,它的数据格不用,只用地址格,指向第0个结点;头指针指向它。这个结点叫头结点。
比如头结点放在120号,cat就成了这样:
text
L = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
头结点 第0个 第1个 第2个c、a、t三个结点一个没变,头指针从100变成了120。第0个结点c前面,现在也有一个结点了。
链表里一个字符都没有时,头结点仍然在,只是它的地址格是NULL。空表不再是L等于NULL:
text
L = 120
│
▼
┌───┬─────┐
│ │ 0 │
└───┴─────┘
120
头结点头结点不存元素,第0个元素仍然是c。头结点建好之后,头指针就再也不用改了:不管在哪里插入、删除哪一个,改的都是某个结点的地址格。
插入和删除不再分情形
有了头结点,再找"前一个结点"。头结点相当于第−1个:从它出发,走1步到第0个,走i步正好到第i−1个。
插在第0个,一步不用走,前一个就是头结点;插在第2个,走2步,前一个是a结点:
text
L = 120
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ │ 100 │────►│ c │ 109 │────►│ a │ 105 │────►│ t │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘ └───┴─────┘
120 100 109 105
prev prev
(i为0) (i为2)两种情形都有了前一个结点,后面的步骤完全一样,就是2.12"在中间位置插入结点"的四步:找到前一个结点,申请新结点,新结点指向后一个,前一个指向新结点。插在第0个时,改的是头结点的地址格,头指针不动。
所以Insert不再需要if。和2.12比,只改了一行:从头结点出发,走i步,而不是走i−1步:
c
/* 原来 */ for (int k = 0; k < i - 1 && prev != NULL; k++)
/* 现在 */ for (int k = 0; k < i && prev != NULL; k++)c
int Insert(LinkList *L, int i, char x) {
if (i < 0) return 0; /* 位置不合法 */
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0; /* 没有第i-1个:位置不合法 */
Node *q = (Node *)malloc(sizeof(Node)); /* 申请新结点 */
if (q == NULL) return 0;
q->data = x;
q->next = prev->next; /* 新结点指向后一个 */
prev->next = q; /* 前一个指向新结点 */
return 1;
}删除同理。删第0个时,前一个结点就是头结点,if分支也去掉了:
c
int Delete(LinkList *L, int i) {
if (i < 0) return 0; /* 位置不合法 */
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL || prev->next == NULL) return 0; /* 没有第i个 */
Node *q = prev->next; /* 记下要删的结点 */
prev->next = q->next; /* 越过它 */
free(q); /* 还给系统 */
return 1;
}其他操作的变化
其他操作的变化,都来自同一个事实:最前面多了一个不存数据的结点。
初始化。空表不再是L等于NULL,而是L指向一个地址格为NULL的头结点。所以初始化要申请头结点。申请可能失败,Init改成返回1或0报告成败,和2.8动态数组的Init一样:
c
int Init(LinkList *L) {
*L = (Node *)malloc(sizeof(Node)); /* 申请头结点 */
if (*L == NULL) return 0; /* 申请不到,初始化失败 */
(*L)->next = NULL; /* 后面还没有结点:空表 */
return 1;
}为什么写(*L)->next
*L是头指针,(*L)->next是头指针指向的结点,也就是头结点的地址格。括号不能省:->比*先算,写成*L->next,会被当成*(L->next)。L是指向头指针的指针,不是指向结点的指针,没有next,编译不过。
头指针不再变,为什么参数还写LinkList *L
有了头结点,除了初始化,再没有操作会改头指针。可是初始化要改它,参数必须是LinkList *L。其他操作也照样写,是为了和顺序表的签名一致,2.15的编辑器才能一行不改。
求长度、取第i个元素。头结点不存元素,不能算进去。p从头结点的下一个出发,也就是第0个元素所在的结点,其余不变:
c
Node *p = (*L)->next; /* 跳过头结点,从第0个结点出发 */销毁。头结点也是用malloc申请的,也要还给系统。代码不用改:p从L出发,第一个释放的正好是头结点。
练习1:有头结点时,空表是什么样?
单选
有头结点的链表,一个字符都没有时,是什么样?
A
L指向头结点,头结点的地址格是NULL
B
L等于NULL
那是没有头结点时的空表。有头结点时,头结点一直都在。
C
头结点的地址格指向头结点自己
那样从头走就停不下来。空表的头结点后面没有结点,地址格是NULL。
头结点在初始化时就申请好了,之后一直在。空表只是头结点后面没有存元素的结点。
练习2:头结点版的这几处怎么写?
填空
把2.11–2.13的操作改成有头结点的版本。
- 求长度时,p从 出发
- 删除第0个结点时,前一个结点是
- 删除第i个结点,从头结点出发走 步
头结点不存元素,求长度和取元素都要从它的下一个出发。头结点相当于第−1个,从它出发走i步,正好到第i−1个,也就是要删结点的前一个;删第0个时一步不走,前一个就是头结点。
头结点版的完整代码
先按前面的提示,自己把每个操作改出来,再和下面对照。2.15的编辑器就用这一版:
c
int Init(LinkList *L) {
*L = (Node *)malloc(sizeof(Node)); /* 申请头结点 */
if (*L == NULL) return 0;
(*L)->next = NULL; /* 空表 */
return 1;
}
int Length(LinkList *L) {
int n = 0;
for (Node *p = (*L)->next; p != NULL; p = p->next) /* 跳过头结点 */
n++;
return n;
}
char Get(LinkList *L, int i) {
if (i < 0) return '\0';
Node *p = (*L)->next; /* 跳过头结点 */
for (int k = 0; k < i && p != NULL; k++)
p = p->next;
if (p == NULL) return '\0';
return p->data;
}
int Insert(LinkList *L, int i, char x) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL) return 0;
Node *q = (Node *)malloc(sizeof(Node));
if (q == NULL) return 0;
q->data = x;
q->next = prev->next;
prev->next = q;
return 1;
}
int Delete(LinkList *L, int i) {
if (i < 0) return 0;
Node *prev = *L; /* 从头结点出发,走i步 */
for (int k = 0; k < i && prev != NULL; k++)
prev = prev->next;
if (prev == NULL || prev->next == NULL) return 0;
Node *q = prev->next;
prev->next = q->next;
free(q);
return 1;
}
void Destroy(LinkList *L) {
Node *p = *L; /* 从头结点开始,全部释放 */
while (p != NULL) {
Node *next = p->next;
free(p);
p = next;
}
*L = NULL;
}到这里你有了头结点,以及有头结点的六个操作。插入和删除不再分情形。下一步把编辑器原样搬到链表上。