资源描述：
《［推荐］数据结构答案栈学习指导》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、3.1知识点分析1.栈的基木概念（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。（3）栈的存储结构有顺序栈和链栈Z分，要求掌握栈的C语言描述方法。（4）垂点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基木原理解决一些实际应用问题。2.顺序栈顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针來指示栈顶元素在栈中的位置。（1）用一维数组实现顺序栈设栈屮的数据元索的类
2、型是字符型，卅一个足够长度的一•维数组s來存放元索，数纽的最大容量为MAXLEN,栈顶指针为top,则顺序栈可以用C（或C++）语言描述如下：#defineMAXLEN10//分配戢大的栈空间chars[MAXLEN]；inttop；(2)用结构体数组实现顺序栈顺序栈的结构体描述：#defineMAXLEN10typedefstruct{datatypedata[MAXLENJ；inttop：JSeqStack；ScqStack*s；(3)基本操作的实现要点(a)顺序栈进栈之前必须判栈是否为满,(b)顺序栈出栈Z前必须判栈是否为空,(C)初始化栈(置栈空)：s->top==-lo(d
3、)进栈操作：if(s->top!=MAXLEN-l){s・>top++；s->data[s->top]=x；1(e)出栈操作：if(s->top!=-l){*x=s->data[s->topj:s->top—；1(f)读栈顶元素if(s->top!=-l)return(s->data[s->top])；//数据类型为字符型//定义栈顶指针//分配最大的栈空间//定义结构体//datatype可根据用需要定义类型//定义栈顶指针//定义S为结构体类型的指针变量判断的条件：s->top==MAXLEN-lo判断的条件：s->top==-lo//如果栈不满//指针加1//元索x进栈//如果
4、栈不空//出栈（即栈顶元素存入权）//指针加1//如果栈不空//读栈顶元索，但指针未移动1.链栈用链式存储结构实现的栈称为链栈。(1)链栈的特点：(a)数据元索的存储与不带头结点的单链表相似;(b)用指针sp指向单链表的第一个结点;(0)插入和删除在top端进行。(2)链栈的存储表示：//栈的存储结构//定义数据类型//定义一个结构体的链指针typedefstructstacknode{datatypedata;structstacknode水next;}stacknode,*Linkstack；Linkstacktop；〃iop为栈顶指针(3)基本操作的实现要点(a)链栈进栈Z前不
5、必判栈是否为满。(b)链栈出栈之前必须判栈是否为空，判断的条件：s->top==NULLo(c)初始化栈(直栈空)：s->top=NULLo(4)进栈操作：stacknodc*p=ncwstacknodc;p・>data二x;p->next=s->top;s->top=p;(5)出栈操作：intx;stacknode*p=s->top;x=p->data;s->top=p->next;deletep;retumx;(6)取栈顶元素if(p!=NULL){x=s->top・>data;retumx;}//申诸一个新结点//数据入栈//修改栈顶指针〃定义一个变量x,用以存放出栈的元素//
6、栈顶指针指向p//栈顶元素送X//修改栈顶指针//回收结点P//返回栈顶元素//输出栈顶元素//返回栈顶元素3.2典型习题分析【例1】若已知一个栈的入栈序列是1,2,3,…，n,其输出序列是Pi，P2,P3,…，若Pi=n,则R二()oA.iB.n-iC.n-i+1D.不确定分析：栈的特点是后进先出，pi输出为n,P2输出为n・l…，pi输出为n・i,所以选C。【例2】在对栈的操作中，能改变栈的结构的是()。A.SEmpty(S)B.SFull(S)C・ReadTop(S)D.InitStack(S)分析：SEmpty⑸是判栈满函数,SFull(S)是判栈空函数，ReadTop(S)
7、是读栈顶元素的函数,它们都不改变栈屮的数据和结构。InitStack(S)为初始化栈函数，若栈S屮原來有数据存在,则经过初始化以后，就成为一个空栈，也就是说改变了栈的结构。所以D为正确答案。【例3】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？分析：不一定。因为当栈后面的元素未进栈时，先入栈的元素可以先出栈。例如将1、2、3依次入栈，得到出栈的次序可以是：123、132、213、231、321五种。在1、2、3的六种全排列中，只有312不
