《数据结构（C语言描述）（第2版）》教学课件3-03链栈及其操作

1、2016数据结构Data structure讲授：司蕾3.3链栈及其操作常州信息职业技术学院02三、链表的插入03链栈-描述3.3 若栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构来表示栈。 1、链栈（Linked Stack） 栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行，栈顶指针就是链表的头指针top a4 a3 a1 a2图3-2 链栈示意图04链栈-描述3.3top向栈中顺序插入（入栈） A、B、C、D04链栈-描述3.3top向栈中顺序插入（入栈） A、B、C、DA04链栈-描述3.3topB向栈中顺序插入（入栈）

2、 A、B、C、DA04链栈-描述3.3topB向栈中顺序插入（入栈） A、B、C、DAC04链栈-描述3.3topB向栈中顺序插入（入栈） A、B、C、DACD04链栈-描述3.3topB向栈中顺序插入（入栈） A、B、C、DACD从栈中顺序删除（退栈） D、C、B、A04链栈-描述3.3topB向栈中顺序插入（入栈） A、B、C、DAC从栈中顺序删除（退栈） D、C、B、A04链栈-描述3.3topB向栈中顺序插入（入栈） A、B、C、DA从栈中顺序删除（退栈） D、C、B、A04链栈-描述3.3top向栈中顺序插入（入栈） A、B、C、DA从栈中顺序删除（退栈） D、C、B、A04链栈-描

3、述3.3top向栈中顺序插入（入栈） A、B、C、D从栈中顺序删除（退栈） D、C、B、A04链栈-描述3.3向栈中顺序插入（入栈） A、B、C、D从栈中顺序删除（退栈） D、C、B、A插入、删除只在链表的一端进行topBACD03链栈-描述3.32、链栈的描述typedef struct/栈的描述 StackNode *top; /栈顶指针LinkStack; typedef char DataType;/假定栈元素的类型为字符类型typedef struct stacknode/结点的描述 DataType data; struct stacknode *next;StackNode;06

4、链栈-描述3.33、说明：（1）设S是LinkStack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针可表示为S- top；链栈栈顶元素可表示为S- top -data。（2）设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点的数据域可表示为p -data，该结点的指针域可表示为p - next。（3）条件S-top= NULL表示空栈，链栈没有栈满的情况。三、链表的插入07链栈的操作-进栈3.31、进栈2、算法思路： 生成一个新结点，将x写入数据域，再将新结点插入栈的顶部。StackNode *p=(StackNode *)malloc(sizeof(StackN

5、ode);p-data=x;p-next=S-top;S-top=p; topBAxptop083、具体算法：int Push(LinkStack *S,DataType x)/进栈StackNode *p=(StackNode *)malloc(sizeof(StackNode);if(p=NULL) puts (内存申请不成功!);return 0; p-data=x;p-next=S-top;/将新结点*p插入链栈头部S-top=p; /栈顶指针指向新结点return 1;将栈S和进栈元素x作为参数。将值为x的结点插入栈顶，进栈操作成功时，返回1，否则返回0。链栈的操作-进栈3.309链

6、栈的操作-退栈3.31、退栈2、算法思路：当栈空时，提示“栈空”，返回0当栈不空时，先将栈顶元素的值存入指针p指向的变量，再将栈顶结点删除。 判断栈S是否栈空topBACStackNode *p=S-top;*x=p-data; S-top=p-next; free(p);ptop091、退栈2、算法思路：当栈空时，提示“栈空”，返回0当栈不空时，先将栈顶元素的值存入指针p指向的变量，再将栈顶结点删除。 判断栈S是否栈空BAStackNode *p=S-top;*x=p-data; S-top=p-next; free(p);top链栈的操作-退栈3.3三、链表的插入103、具体算法：int Pop(LinkStack *S, DataType *x)/退栈StackNode *p=S-top;/保存栈顶指针if(StackEmpty(S)puts(栈空); return 0;*x=p-data; /保存栈顶结点数据S-top=p-next; /将栈顶结点从链上摘下free(p);return 1; 可将栈S和指针x作为参数。保存栈顶结点的数据，移除栈顶结点。退栈操作成功时，返回1，否则返回0。链栈的操作-退栈3.311链栈的操作-取栈顶元素3.31、取栈顶元素2、具体算法： 保存栈顶结点的数据。操作成功时，返回1，否则返回0。可将栈S和指针x作为参数。int StackT