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

15第3章栈3.1知识点分析1．栈的基本概念（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。2．顺序栈顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位置。（1）用一维数组实现顺序栈设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#defineMAXLEN10//分配最大的栈空间chars[MAXLEN]；//数据类型为字符型inttop；//定义栈顶指针（2）用结构体数组实现顺序栈顺序栈的结构体描述：#defineMAXLEN10//分配最大的栈空间typedefstruct//定义结构体{datatypedata[MAXLEN]；//datatype可根据用需要定义类型inttop；//定义栈顶指针}SeqStack；SeqStack*s；//定义S为结构体类型的指针变量（3）基本操作的实现要点(a）顺序栈进栈之前必须判栈是否为满，判断的条件：s-top==MAXLEN–1。(b）顺序栈出栈之前必须判栈是否为空，判断的条件：s-top==–1。(c）初始化栈（置栈空）：s-top==–1。(d）进栈操作：if（s-top!=MAXLEN–1）//如果栈不满{s-top++；//指针加1s-data[s-top]=x；//元素x进栈}(e）出栈操作：if（s-top!=–1）//如果栈不空{*x=s-data[s-top]；//出栈（即栈顶元素存入*x）s-top––；//指针加1}(f）读栈顶元素if（s-top!=–1）//如果栈不空return(s-data[s-top])；//读栈顶元素，但指针未移动163．链栈用链式存储结构实现的栈称为链栈。（1）链栈的特点：(a）数据元素的存储与不带头结点的单链表相似；(b）用指针top指向单链表的第一个结点；(c）插入和删除在top端进行。（2）链栈的存储表示：typedefstructstacknode//栈的存储结构{datatypedata;//定义数据类型structstacknode*next;//定义一个结构体的链指针}stacknode，*Linkstack；Linkstacktop；//top为栈顶指针（3）基本操作的实现要点(a)链栈进栈之前不必判栈是否为满。(b)链栈出栈之前必须判栈是否为空，判断的条件：s-top==NULL。(c)初始化栈（置栈空）：s-top=NULL。（4）进栈操作：stacknode*p=newstacknode;//申请一个新结点p-data=x;//数据入栈p-next=s-top;//修改栈顶指针s-top=p;（5）出栈操作：intx;//定义一个变量x，用以存放出栈的元素stacknode*p=s-top;//栈顶指针指向px=p-data;//栈顶元素送xs-top=p-next;//修改栈顶指针deletep;//回收结点preturnx;//返回栈顶元素（6）取栈顶元素if(p!=NULL){x=s-top-data;//输出栈顶元素returnx;//返回栈顶元素}3.2典型习题分析【例1】若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是P1，P2，P3，…，Pn，若P1=n，则Pi=（）。A．iB．n-iC．n-i+1D．不确定分析：栈的特点是后进先出，p1输出为n，p2输出为n-1…，pi输出为n-i，所以选C。【例2】在对栈的操作中，能改变栈的结构的是（）。A．SEmpty(S)B．SFull(S)C．ReadTop(S)D．InitStack(S)分析：SEmpty(S)是判栈满函数，SFull(S)是判栈空函数，ReadTop(S)是读栈顶元素的函数，它们都不改变栈中的数据和结构。InitStack(S)为初始化栈函数，若栈S中原来有数据存在，则经过初始化以后，就成为一个空栈，也就是说改变了栈的结构。所以D为正确答案。17【例3】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？分析：不一定。因为当栈后面的元素未进栈时，先入栈的元素可以先出栈。例如将1、2、3依次入栈，得到出栈的次序可以是：123、132、213、231、321五种。在1、2、3的六种全排列中，只有312不可能是出栈的序列。例如213可以这样得到：1入栈；2入栈，并出栈；1出栈；3入栈，并出栈。312之所以不可能是出栈的序列，原因是：3第一个出栈，表示1、2必然在栈中，且2是栈顶元素，它必须先于1出栈。所以，312是不可能得到的出栈次序。【例4】设一个栈的进栈序列是a、b、c、d，进栈的过程中可以出栈，不可能的出栈序列是（）。A．d，c，b，aB．c，d，b，aC．d，c，a，bD．a，b，c，d分析：栈是仅能在表的一端进行插入和删除操作的线性表，即进栈和出栈运算仅能在栈顶进行，其操作原则是后进先出。（1）要求出栈序列是d，c，b，a时，要将a，b，c，d都进栈，再依次出栈。（2）要求出栈序列是c，d，b，a时，需要将a，b，c进栈，c出栈，d出栈，再b出栈，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所示。图3-1栈式站台结构（1）设有编号为1，2，3，4，5，6的6辆列车顺序开入栈式结构的站台，则可能的出栈的序列有几种？（2）进栈顺序如上所述，能否得到435612和325641两个出栈序列。答：（1）可能的出栈的序列有(1/(6+1))*C612=132（2）不能得到435612的出栈序列。因为若在4，3，5，6之后再将1，2出栈，则1，2必须一直在栈中，此时1先进栈，2后进栈，2应压在1的上面，不可能1先于2出栈。出栈序列325641可以得到，其进栈、出栈过程如图3-2所示。3562244441111111133232325325325632564325641图3-2进栈、出栈过程分析【例6】在链栈中为什么不必设头结点？分析：1,2,3,4,5,618在链栈中，首结点为栈顶元素。在栈中的插入、删除操作都在栈顶进行，因此每次插入、删除操作都要修改栈顶指针。如果设置头结点，则头结点后跟的是栈顶元素，每次插入、删除操作就要修改头结点中的指针。反正要修改一个指针，可见设置头结点是没有必要的。【例7】指出下述程序段的功能是什么？voidProg1(SeqStack*S){inti,n=0,a[64];//设栈中的元素个数小于64while(!StackEmpty(S))a[n++]=Pop(S);for(i=0;i=n;i++)Push(S,a[i]);}答：Prog1的功能是将顺序栈S中的元素逆置。例如，执行Demo1前S=(a1,a2,……，an)，则执行Prog1后S=(an,……,a2,a1)。【例8】指出下述程序段的功能是什么？voidProg2(SeqStack*S1,S2){SeqStackS1,S2,Temp;//设S1已存在，S2,Temp已初始化DataTypex;while(!StackEmpty(&S1)){x=Pop(&S1);Push(&Temp,x);}while(!StackEmpty(&Temp)){x=Pop(&Tepm);Push(&S1,x);Push(&S2,x);}}答：Prog2的功能是用Temp作为辅助栈，将S1复制到S2中，并保持S1中的内容不变。设执行此程序段之前S1=(a1,a2,……，an)，执行此程序段之后，S1=(a1,a2,……，an)，S2=(a1,a2,……，an)。程序的第一个while语句把S1的内容倒到Temp中，第二个while语句把Temp中的内容分别倒到S1和S2中。【例9】指出下述程序段的功能是什么？voidProg3(SeqStack*S,charx){SeqStackT;chari;InitStack(&T);while(!StackEmpty(S))if((i=Pop(S))!=’k’)Push(&T,i);while(!StackEmpty(&T)){i=Pop(&T);Push(S,i);}}19答：Prog3的功能是把栈S中值为“k”的结点删除。【例10】写出运行下列程序段的输出结果voidmain(){StackS;charx,y;InitStack(S);//初始化栈x=c;y=k;Push(S,x);Push(S,a);Push(S,y);Pop(S,x);Push(S,t);Push(S,x);Pop(S,x);Push(S,s);While(!SEmpty(S)){Pop(S,y);couty;};coutx;}分析：本题主要是分清变量的内容进栈，还是字符直接进栈。按照程序，其进栈、出栈的主要步骤，以及变量x和y值的变化过程如图3-3所示。在While循环语句中，栈顶数据依次弹出到y，并输出。循环结束输出stac，最后输出x的值k，所以运行程序段的输出结果为：stack。ksktttttaaaaaaaacccccccccx=cx=kx=kx=kx=kx=kx=kx=kx=kx=ky=ky=ky=ky=ky=ky=ky=sy=ty=ay=c图3-3进栈、出栈过程分析3.3单元练习3解答一．判断题答案题目12345678910答案√√×√××√××√二．填空题答案（1）栈顶（2）栈空（3）O(1)（4）O(1)（5）栈（6）栈空20（7）p-next=top；（8）++（或=S-top+1）（9）LS-next（10）栈顶元素（11）头（12）栈是否满（13）栈是否空（14）链（15）LS-next=NULL（16）首（17）相同（18）B（19）ABC/+DE*-（20）C三．选择题答案题目12345678910答案CDBDBAABDB题目11121314151617181920答案BAABBCBBCA四．答案（1）①IIIOOOIOIO②IOIIOOIIOO（2）求后缀表达式答案①AB^C^D/②0A–BC*+DE/+③ABC+*D*E-④AB+C*EFGH/+/-D-⑤852+/6-（3）stack（分析见典型习题分析【例10】）五．算法设计题答案（1）分析：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S[1]开始存放元素。①【入栈程序代码】voidpush(charx){if((top+M)MAXLEN-1)printf(“堆栈溢出！”);else{if(top==0){top++;S[top]=x;}else{top=top+M;S[top]=x;}}}②【出栈程序代码】21voidpop(charx){if(top==0)printf(“堆栈为空栈！”);else{if(top==1){x=S[top];top––;}else{x=S[top];top=top–M;}}}（2）分析：设表达式在字符数组a[]中，使用一堆栈S来帮助判断。【程序代码】intcorrect(chara[]){stacks;InitStack(s);//调用初始化栈函数for(i=0;istrlen(a);i++)if(a[i]==’(’)Push(s,’(’);elseif(a[