数据结构全套配套课件C语言描述第2版李学刚教学课件3-03链栈及其操作.pptx

《数据结构全套配套课件C语言描述第2版李学刚教学课件3-03链栈及其操作.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

3、链栈-描述3.3^top向栈中顺序插入（入栈）A、B、C、DA从栈中顺序删除（退栈）D、C、B、A04链栈-描述3.3^top向栈中顺序插入（入栈）A、B、C、D从栈中顺序删除（退栈）D、C、B、A04链栈-描述3.3向栈中顺序插入（入栈）A、B、C、D从栈中顺序删除（退栈）D、C、B、A插入、删除只在链表的一端进行^topBACD03链栈-描述3.32、链栈的描述typedefstruct{//栈的描述StackNode*top;//栈顶指针}LinkStack;typedefcharDataType;//假定栈元素的类型为

4、字符类型typedefstructstacknode{//结点的描述DataTypedata;structstacknode*next;}StackNode;06链栈-描述3.33、说明：（1）设S是LinkStack类型的指针变量，则S是指向链栈的指针，链栈栈顶指针可表示为S->top；链栈栈顶元素可表示为S->top->data。（2）设p是StackNode类型的指针变量，则p是指向链栈某结点的指针，该结点的数据域可表示为p->data，该结点的指针域可表示为p->next。（3）条件S->top==NULL表示空栈，链

5、栈没有栈满的情况。三、链表的插入07链栈的操作-进栈3.31、进栈2、算法思路：生成一个新结点，将x写入数据域，再将新结点插入栈的顶部。StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->next=S->top;S->top=p;^topBAxptop083、具体算法：intPush(LinkStack*S,DataTypex){//进栈StackNode*p=(StackNode*)malloc(sizeof(StackNode));if(p==NUL

6、L){puts("内存申请不成功!");return0;}p->data=x;p->next=S->top;//将新结点*p插入链栈头部S->top=p;//栈顶指针指向新结点return1;}将栈S和进栈元素x作为参数。将值为x的结点插入栈顶，进栈操作成功时，返回1，否则返回0。链栈的操作-进栈3.309链栈的操作-退栈3.31、退栈2、算法思路：当栈空时，提示“栈空”，返回0当栈不空时，先将栈顶元素的值存入指针p指向的变量，再将栈顶结点删除。判断栈S是否栈空^topBACStackNode*p=S->top;*x=p->d

7、ata;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、具体算法：intPop(LinkStack*S,DataType*x){//退栈StackNode*p=S->top;//保存栈顶指针if(StackEmpty(S))

8、{puts("栈空");return0;}*x=p->data;//保存栈顶结点数据S->top=p->next;//将栈顶结点从链上摘下free(p);return1;}可将栈S和指针x作为参数。保存栈顶结点的数据，移除栈顶结点。退栈操作成功时，返回1，否则返回0。链栈的操