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

《数据结构答案第3章栈学习指导.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈3.1知识点分析1．栈的基本概念（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。2．顺序栈顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位

2、置。（1）用一维数组实现顺序栈设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#defineMAXLEN10//分配最大的栈空间chars[MAXLEN]；//数据类型为字符型inttop；　//定义栈顶指针（2）用结构体数组实现顺序栈顺序栈的结构体描述：#defineMAXLEN10//分配最大的栈空间typedefstruct//定义结构体{datatypedata[MAXLEN]；//datatype可根据用需要定义类型inttop；

3、//定义栈顶指针}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

4、->top]；//出栈（即栈顶元素存入*x）s->top––；//指针加1}(f）读栈顶元素if（s->top!=–1）//如果栈不空return(s->data[s->top])；//读栈顶元素，但指针未移动1．链栈用链式存储结构实现的栈称为链栈。（1）链栈的特点：(a）数据元素的存储与不带头结点的单链表相似；(b）用指针top指向单链表的第一个结点；(c）插入和删除在top端进行。（2）链栈的存储表示：typedefstructstacknode//栈的存储结构{datatypedata;//定义数据类型structstacknode*next;

5、//定义一个结构体的链指针}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，用以存放出栈的元素stackn

6、ode*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输出为

7、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为正确答案。【例3】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？分析：不一定。因为当栈后面的元素未进栈时，先入

8、栈的元素可以先出栈。例如将1、2、3依次入栈，得到出栈的次序可以是：123、132、213、231、321五