外观
3.4 链栈
栈顶放在哪一头
3.3节用一段连续的格子存栈。栈也可以用2.9节的链表来存:每个元素一个结点,用地址连起来。
和顺序栈一样,先要定栈顶放在哪一头。还是存1、2、3,3是栈顶,有两种放法。
放法一:第一个结点是栈底,栈顶在表尾。
text
L = 100
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ 1 │ 109 │────►│ 2 │ 105 │────►│ 3 │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
100 109 105Pop要删掉3结点,就得把2结点的地址格改成0。可2结点在哪?链表只记着第一个结点的地址,只能从L出发一个一个走过去。栈里有n个元素,就要走n−1步。
放法二:第一个结点是栈顶。
text
S = 105
│
▼
┌───┬─────┐ ┌───┬─────┐ ┌───┬─────┐
│ 3 │ 109 │────►│ 2 │ 100 │────►│ 1 │ 0 │
└───┴─────┘ └───┴─────┘ └───┴─────┘
105 109 100Pop删的是第一个结点:把S改成3结点地址格里的109,一步就到。Push也只是在最前面接一个结点,一步都不用走。
这和2.16节量出的结论一样:链表在头部插入、删除是O(1),在尾部是O(n),正好和顺序表相反。所以链栈的栈顶放在表头,也和顺序栈正好相反。两种存法,都把栈顶放在自己最省事的那一头。
本节问题栈顶在链表头,栈的五个操作怎么用C语言写出来?
链栈
用链式存储的栈叫链栈。栈顶就是第一个结点,所以头指针就是栈顶指针,记作S。
结点和2.10节的一样,只是数据格放整数:
c
typedef struct StackNode {
int data; /* 数据格 */
struct StackNode *next; /* 地址格:下面一个结点的地址 */
} StackNode, *LinkStack;StackNode是结点类型,LinkStack是指向结点的指针类型,和2.10节的Node、LinkList是一个意思。
链栈也竖着画,栈顶在上。左边是空栈,右边放了1、2、3:
空栈的S是NULL。放了1、2、3之后,S是105,指着栈顶3结点;3结点的地址格指着2结点,2结点指着1结点;栈底1结点的地址格是0,表示下面没有了。
不要头结点。2.14节给链表加了头结点,是为了让第0个结点也有前一个结点,插入、删除不用分情形。链栈只在第0个结点进出:Push是插在第0个,Pop是删第0个,从来不用找前一个结点。头结点在这里没有用处,所以链栈不加。
由此马上得到两个操作。初始化就是让S为NULL;判空就是看S是不是NULL:
c
void InitStack(LinkStack *S) {
*S = NULL;
}
int StackEmpty(LinkStack *S) {
return *S == NULL;
}为什么写*S
Push、Pop都要改S本身,让它指向另一个结点。所以调用时传的是S的地址,参数是LinkStack *,函数里用*S取到S。这和2.11节的*L一样。
链栈没有"栈满":只要还申请得到结点,就能Push。
Push:放到栈顶
栈里是1、2,S是109。现在Push(S, 3)。这和2.12节"在第0个位置插入结点"是同一件事。
第一步:申请结点q,放3。假设申请到的是105号:
c
StackNode *q = (StackNode *)malloc(sizeof(StackNode));
q->data = 3;q的地址格还没填,画成问号。申请不到时malloc返回NULL,Push就返回0。
第二步:q指向原来的栈顶。原栈顶2结点的地址109正记在S里,抄给q的地址格:
c
q->next = *S; /* q->next = 109 */第三步:S指向q。3结点成了新的栈顶:
c
*S = q; /* S = 105 */先连上,再改S,顺序不能反。先改S,原栈顶的地址109就从S里丢了,q的地址格再也抄不到它,1、2两个结点就找不回来了。
写成函数。要放的是x;申请不到结点返回0,放好了返回1:
c
int Push(LinkStack *S, int x) {
StackNode *q = (StackNode *)malloc(sizeof(StackNode)); /* 第一步:申请结点放x */
if (q == NULL) return 0;
q->data = x;
q->next = *S; /* 第二步:新结点指向原栈顶 */
*S = q; /* 第三步:S指向新结点 */
return 1;
}栈是空的时候,S是NULL,第二步让q的地址格得到NULL,正好表示下面没有了。不用另写代码。
Pop:删除栈顶,用x带回
栈里是1、2、3,S是105。现在Pop(S, &x)。这和2.13节"删除第0个结点"是同一件事,只多了一步:用x带回删掉的值。
第一步:判断栈空。S是105,不是NULL,有东西可删。
第二步:q记下栈顶结点,用x带回它的值:
c
StackNode *q = *S; /* q = 105 */
*x = q->data; /* x = 3 */第三步:S指向下一个结点。3结点的地址格是109,抄给S,2结点成了栈顶:
c
*S = q->next; /* S = 109 */第四步:释放q。3结点已经不在栈里了,还给系统:
c
free(q);先改S,再释放,顺序不能反。先free(q),3结点就还给了系统,再读q->next,读的是已经不归你的内存,读到什么说不准。这也是第二步要先用q记下栈顶的原因:S改走之后,只有q还找得到3结点。
写成函数。栈空返回0,删好了返回1:
c
int Pop(LinkStack *S, int *x) {
if (*S == NULL) return 0; /* 第一步:栈空,没有可删的 */
StackNode *q = *S; /* 第二步:记下栈顶结点,用x带回它的值 */
*x = q->data;
*S = q->next; /* 第三步:S指向下一个结点 */
free(q); /* 第四步:还给系统 */
return 1;
}GetTop:取栈顶
栈顶就是S指着的结点。GetTop只读它的数据格,S不动,也不释放:
c
int GetTop(LinkStack *S, int *x) {
if (*S == NULL) return 0; /* 栈空,没有栈顶 */
*x = (*S)->data; /* 栈顶就是S指向的结点 */
return 1;
}(*S)->data的括号不能省:先用*S取到S,再用->读它指着的结点。
把五个操作合起来
五个函数都写好了,还要写main。先别动手,预测一下:3.3节的main要改多少?
3.3节的main只调用了五个操作,没有碰过data和top。链栈的五个操作,名字和用法都和顺序栈一样。所以预测:main只改一处,把SeqStack换成LinkStack。
c
int main(void) {
LinkStack S; /* 原来是 SeqStack S; */
int x;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Pop(&S, &x); printf("%d ", x);
Pop(&S, &x); printf("%d ", x);
Push(&S, 3);
Pop(&S, &x); printf("%d\n", x);
printf("栈空吗:%d\n", StackEmpty(&S));
return 0;
}把这个main接在前面五个函数后面,再在开头加上#include <stdio.h>和#include <stdlib.h>,运行结果:
text
2 1 3
栈空吗:1和3.3节一模一样,预测成立。这就是3.2节的抽象数据类型带来的好处:main只依赖"能做什么","怎么存"可以整个换掉。
两种栈的五个操作都是O(1)。区别在空间上:顺序栈事先定好MAXSIZE,放满就不能再放;链栈要多少申请多少,但每个元素多占一个地址格,每次Push还要申请一次结点。
完整的程序放在下面,可以直接复制运行:
c
#include <stdio.h>
#include <stdlib.h>
typedef struct StackNode {
int data;
struct StackNode *next;
} StackNode, *LinkStack;
void InitStack(LinkStack *S) {
*S = NULL;
}
int StackEmpty(LinkStack *S) {
return *S == NULL;
}
int Push(LinkStack *S, int x) {
StackNode *q = (StackNode *)malloc(sizeof(StackNode)); /* 第一步:申请结点放x */
if (q == NULL) return 0;
q->data = x;
q->next = *S; /* 第二步:新结点指向原栈顶 */
*S = q; /* 第三步:S指向新结点 */
return 1;
}
int Pop(LinkStack *S, int *x) {
if (*S == NULL) return 0; /* 第一步:栈空,没有可删的 */
StackNode *q = *S; /* 第二步:记下栈顶结点,用x带回它的值 */
*x = q->data;
*S = q->next; /* 第三步:S指向下一个结点 */
free(q); /* 第四步:还给系统 */
return 1;
}
int GetTop(LinkStack *S, int *x) {
if (*S == NULL) return 0; /* 栈空,没有栈顶 */
*x = (*S)->data; /* 栈顶就是S指向的结点 */
return 1;
}
int main(void) {
LinkStack S;
int x;
InitStack(&S);
Push(&S, 1);
Push(&S, 2);
Pop(&S, &x); printf("%d ", x);
Pop(&S, &x); printf("%d ", x);
Push(&S, 3);
Pop(&S, &x); printf("%d\n", x);
printf("栈空吗:%d\n", StackEmpty(&S));
return 0;
}练习1:S和地址格里是什么?
填空
链栈,从空栈开始,依次调用:
Push(&S, 7),Push(&S, 8),Pop(&S, &x),Push(&S, 9)
7结点的地址是100,9结点的地址是118。
- 全部做完,S是
- 9结点的地址格是
- 7结点的地址格是
- x是
7入栈时栈是空的,7结点的地址格得到NULL,画成0。8入栈后又被Pop删掉,x是8。9入栈时,原栈顶是7结点,9结点的地址格抄来100;S改成9结点的地址118。
练习2:Pop的最后两步写反了会怎样?
单选
有人把Pop的第三步和第四步写反了:
c
free(q);
*S = q->next;会怎样?
A
没有影响,q->next的值还在
可能碰巧还在,也可能已经被改掉了。结点还给系统之后,里面的内容就不归你管了。
B
q->next读的是已经释放的结点,S可能得到一个错的地址
free之后再读这个结点,结果说不准。S一旦指错,后面的Pop、GetTop都会出错。
C
编译出错
两行都是合法的C语句,编译能通过,错在运行时。
S要先改到下一个结点,再释放旧的栈顶。释放之后,就不能再通过q读它。
到这里你有了链栈:栈顶在链表头,S就是头指针,不要头结点。五个操作都是O(1),换成链栈时main只改了类型名。下一步栈能用来解决哪些问题?