数据结构答案第3章栈学习指导

1、3. 链栈用链式存储结构实现的栈称为链栈。(1) 链栈的特点：(a) 数据元素的存储与不带头结点的单链表相似:(b) 用指针top指向单链表的第一个结点:(c) 插入和删除在top端进行。(2) 链栈的存储表示：/栈的存储结构/定义数据类型H定义一个结构体的链指针/top为栈顶抬针typcdef struct stacknode datatype data;stnict stacknode 幺next;stacknode» * Linkstack；Linkstack top；(3) 基本操作的实现要点(a) 链栈进栈之前不必判栈是否为满。(b) 链栈出栈之前必须判栈是否为空，判断的条

2、件：s->top=NULLo(c) 初始化栈(置栈空)：s->top=NULLo(4) 进栈操作：stacknodc *p=new stacknode; p->data=x;p->next=s->top;s->top=p:(5>出栈操作：int x;stacknode *p=s->top;x=p->data;s->top=p->next;delete p;return x;(6)取栈顶元素if(p!=NULL)x=s->top->data; return x:申请一个新结点/数据入栈/修改栈顶抬针定义一个变虽x.用以

3、存放出栈的元素栈顶描针抬向p栈顶元素送x/修改栈顶指针/回收结点p/返回栈顶元素H输出栈顶元素/返回栈顶元素3.2典型习题分析【例1】若已知一个栈的入栈序列是1，2, 3,，n,其输出序列是Pi, P2,厂，Pn, 若 P,=n,则 R二( )oA. iBn-iCn-i+1D不确定分析：栈的特点是后进先岀，pi输出为n, P2输出为nl,Pi输出为n-i,所以选C。【例2】在对栈的操作中，能改变栈的结构的是()。A. SEmpty(S)B SFuIl(S)C ReadTop (S) D InitStack(S)分析：SEmpty(S)是判栈满函数,SFull(S)是判栈空函数,ReadTop(

4、S)是读栈顶元素的函数, 它们都不改变栈中的数据和结构。InitStack(S)为初始化栈函数，若栈S中原来有数拯存在， 则经过初始化以后，就成为一个空栈，也就是说改变了栈的结构。所以D为正确答案。【例3】“后进先出”是栈的特点，那么岀栈的次序一立是入栈次序的逆序列吗？分析：不一左。因为当栈后而的元素未进栈时，先入栈的元素可以先岀栈。例如将1、2、3 依次入栈，得到出栈的次序可以是：123、132、213、231、321五种。在1、2、3的六种全 排列中，只有312不可能是出栈的序列。例如213可以这样得到：1入栈：2入栈，并出栈: 1出栈；3入栈，并出栈。312之所以不可能是岀栈的序列，原因

5、是：3第一个出栈，表示1、2必然在栈中，且2 是栈顶元素，它必须先于1岀栈。所以，312是不可能得到的出栈次序。【例4】设一个栈的进栈序列是a、b、c、d.进栈的过程中可以出栈，不可能的出栈序列 是（）。A. d, c, b, aB. c, d, b, aC. d, c, a, b D. a, b, c, d分析：栈是仅能在表的一端进行插入和删除操作的线性表，即进栈和出栈运算仅能在栈顶进 行，其操作原则是后进先岀。（1）要求出栈序列是d, c, b, a时，要将a, b, c, d都进栈，再依次出栈。（2）要求出栈序列是c, d, b, a时，需要将a, b, c进栈，c岀栈，d出栈，再b出栈

6、, a出栈。（3）要求岀栈序列是d, c, a, b时，需要将a、b、c、d依次进栈，d岀栈，c出栈，当 前栈顶元素是b,故a不能出栈。所以C是不可能的出栈序列。（4）要求出栈序列是a, b, c, d时，可将a、b、c、d逐个进栈后立即出栈。【例5】铁路列车调度时，常把站台设计成栈式结构，如图3-1所示。岀站进站1,2,345,6图3-1栈式站台结构（1）设有编号为1, 2, 3, 4, 5, 6的6俩列车顺序开入栈式结构的站台，则可能的出栈的 序列有几种？（2）进栈顺序如上所述，能否得到435612和325641两个岀栈序列。答：（1）可能的出栈的序列有（1 /（6+ 1）*Ci，=132

7、（2）不能得到435612的岀栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必33232325325325632564325641图3-2进栈、出栈过程分析【例6】在链栈中为什么不必设头结点? 分析：在链栈中，首结点为栈顶元素。在栈中的插入、删除操作都在栈顶进行，因此每次插入、 删除操作都要修改栈顶指针。如果设置头结点，则头结点后跟的是栈顶元素，每次插入、删 除操作就要修改头结点中的指针。反正要修改一个指针，可见设置头结点是没有必要的。【例7】指出下述程序段的功能是什么？void ProgKSeqStack *S) int i. n=0, a64;/设栈中的元素个数小于6

8、4while (! StackEmpty(S) an+=Pop(S);for (i=0; i<=n; i+)Push(S, ai);答：Progl的功能是将顺序栈S中的元素逆置。例如，执行Dcmol前S=(aba2,，a)则 执行 Progl 后 S=(an,az, aj。【例8】指出下述程序段的功能是什么？void Prog2(ScqStack *S1, S2) SeqStack SI, S2.Tcmp;设 SI 已存在，S2.Temp 已初始化DataType x;while (! StackEmpty(&Sl) x=Pop(&Sl);Push(&Temp,

9、x);while (! StackEmpty(&Tcmp) x=Pop (&Tcpm);Push(&Sl. x);Push(&S2, x);答：Prog2的功能是用Temp作为辅助栈，将SI复制到S2中，并保持S1中的内容不变。 设执行此程序段之前Sl=(ai,a2,，aj,执行此程序段之后，Sl=(a,a2,，an), S2=(ai,a2, a。程序的第一个while语句把S1的内容倒到Temp中，第二个while语句把Temp中的内容分别倒到S1和S2中。【例9】指出下述程序段的功能是什么？void Prog3 (SeqStack *S, char x) S

10、eqStack T;char i;InitStack (&T);while (! StackEmpty(S)if (i二Pop(S) !='k')Push(&T, i);while (! StackEmpty(&T) i=Pop (&T);Push(S, i);答：Prog3的功能是把栈S中值为“k”的结点删除。 【例10写出运行下列程序段的输出结果void main() Stack S;char x,y;InitStack(S);/ 初始化栈x= Hc M;y=Hk “；Push(S.x);Push(S, Ha M);Push(S,y);Pop

11、(S.x);Push(StM);Push(S.x);Pop(S.x);Push(Ss ”)；While (!SEmpty(S) Pop(S,y);cout«y; ;cout«x;分析：本题主要是分淸变量的内容进栈，还是字符直接进栈。按照程序，其进栈、出栈的主 要步骤，以及变量x和y值的变化过程如图3-3所示。在While循环语句中，栈顶数据依次 弹出到y,并输出。循环结朿输岀"stac",最后输出x的值"k",所以运行程序段的输岀结果 为:"stack y=图33进栈、出栈过程分析3.3单元练习3解答一.判断题答案题目123

12、45678910答案XdXXXXV（2）栈空二.填空题答案（1） 栈顶(3)0(1)(4) 0(1)(5)栈（6）栈空(7)p->next=top；(8) +(或=S->top+l )(9)LS>ncxl（10）栈顶元素(11)头（12）栈是否满(13)栈是否空(14)链(15)LS->next=NULL（16）首(17)相同(18) B(19)ABC/+DE*.(20) C三.选择题答案题目12345678910答案CDBDBAABDB题目11121314151617181920答案BAABBCBBCA四.答案（1 ） IIIOOOIOIO（2）求后缀表达式答案 IO

13、IIOOIIOOABACAD/0ABc*+ABc+*D*AB+C*EF852+/6 -D E / +E -G H / + / - D -（3）stack （分析见典型习题分析【例10）五.算法设计题答案（1）分析：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从Sl开始存放元素。【入栈程序代码】void push (char x) if (top+M)>MAXLEN-1) printf ("堆栈溢岀！ ”);else if (top= =0) top+;S top=x:else top=top+M;S top=x;【岀栈程序代码】void pop (char

14、x) if (top= =0)pnntf(“堆栈为空栈！ ”);else if (top=l) x= S topi; top:else x= S top; top=top-M;(2) 分析：设表达式在字符数组a中， 【程序代码】int correct (char a)stack s;InitStack (s);for (i=0; i <strlen(a);i+)if(ai=X5)Push (sj(');else if (ai= =')')if SEmpty (s)return 0;elsePop ；if (SEmpty )pnntf(“配对正确！ “); else

15、pnntf(“配对错误！ “);(3) 【程序代码】# includc<stdio.h>#include<stdlib.h>typedef struct stacknodeint data;使用一堆栈S来帮助判断。/调用初始化栈函数/ SEmpty (s)为判栈空函数/若栈为空返回0：否则出栈若栈空，说明配对正确，并返回1/配对错误返回0/栈的存储结构struct stacknode 切ext; stacknode;typedef structstacknode *top;/描向栈的抬针 linkstack:void Conversion(int n)/二十六进制转换函

16、数linkstack s:int x;s.top=NULL;dox=n%16;n=ii/16;stacknode *p;p=new (stacknode);p->next=s.top;s.top=p;s.top->data=x;while(n);printfC'ntt转换以后的16进制数值为：“);while(s.top) if (s.top->data<10)printf(,%dH,s.top->data);elseswitch (s.top->data) case 10: printf(,%c,VA,);break;case 11: printf(H%c*,B,);break;case 12: pri