当前位置：文档库 › 数据结构答案第3章栈学习指导

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

第3章栈

3.1 知识点分析

1．栈的基本概念

（1）栈是一种特殊的、只能在表的一端进行插入或删除操作的线性表。允许插入、删除的一端称为栈顶，另一端称为栈底。

（2）栈的逻辑结构和线性表相同，其最大特点是“后进先出”。

（3）栈的存储结构有顺序栈和链栈之分，要求掌握栈的C语言描述方法。

（4）重点掌握在顺序栈和链栈上实现：进栈、出栈、读栈顶元素、判栈空和判栈满等基本操作。

（5）熟悉栈在计算机的软件设计中的典型应用，能灵活应用栈的基本原理解决一些实际应用问题。

2．顺序栈

顺序栈是利用地址连续的存储单元依次存放从栈底到栈顶的元素，同时附设栈顶指针来指示栈顶元素在栈中的位置。

（1）用一维数组实现顺序栈

设栈中的数据元素的类型是字符型，用一个足够长度的一维数组s来存放元素，数组的最大容量为MAXLEN，栈顶指针为top，则顺序栈可以用C（或C++）语言描述如下：#define MAXLEN 10 // 分配最大的栈空间

char s[MAXLEN]；// 数据类型为字符型

int top；// 定义栈顶指针

（2）用结构体数组实现顺序栈

顺序栈的结构体描述：

#define MAXLEN 10 // 分配最大的栈空间

typedef struct // 定义结构体

{ datatype data[MAXLEN]；// datatype可根据用需要定义类型

int top；// 定义栈顶指针

}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++；// 指针加1

s->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])；// 读栈顶元素，但指针未移动

3．链栈

用链式存储结构实现的栈称为链栈。

（1）链栈的特点：

(a）数据元素的存储与不带头结点的单链表相似；

(b）用指针top指向单链表的第一个结点；

(c）插入和删除在top端进行。

（2）链栈的存储表示：

typedef struct stacknode // 栈的存储结构

{ datatype data; // 定义数据类型

struct stacknode *next; // 定义一个结构体的链指针

}stacknode，* Linkstack；

Linkstack top；// top为栈顶指针

（3）基本操作的实现要点

(a) 链栈进栈之前不必判栈是否为满。

(b) 链栈出栈之前必须判栈是否为空，判断的条件：s->top==NULL。

（4）进栈操作：

stacknode *p=new stacknode; // 申请一个新结点

p->data=x; // 数据入栈

p->next=s->top; // 修改栈顶指针

s->top=p;

（5）出栈操作：

int x; // 定义一个变量x，用以存放出栈的元素

stacknode *p=s->top; // 栈顶指针指向p

x=p->data; // 栈顶元素送x

s->top=p->next; // 修改栈顶指针

delete p; // 回收结点p

return x; // 返回栈顶元素

（6）取栈顶元素

if (p!=NULL)

{

x=s->top->data; //输出栈顶元素

return x; // 返回栈顶元素

}

3.2 典型习题分析

【例1】若已知一个栈的入栈序列是1，2，3，…，n，其输出序列是P1，P2，P3，…，P n ，若P1=n，则P i=（）。

A．i B．n-i C．n-i+1 D．不确定

分析：栈的特点是后进先出，p1输出为n，p2输出为n-1…，p i输出为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】“后进先出”是栈的特点，那么出栈的次序一定是入栈次序的逆序列吗？

分析：不一定。因为当栈后面的元素未进栈时，先入栈的元素可以先出栈。例如将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，a B．c，d，b，a C．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出栈，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,3,4,5,6

图3-1 栈式站台结构

（1）设有编号为1，2，3，4，5，6的6辆列车顺序开入栈式结构的站台，则可能的出栈的序列有几种？

（2）进栈顺序如上所述，能否得到435612和325641两个出栈序列。

答：

（1）可能的出栈的序列有(1/(6+1))*C6

=132

（2）不能得到435612的出栈序列。因为若在4，3，5，6之后再将1，2出栈，则1，2必须一直在栈中，此时1先进栈，2后进栈，2应压在1的上面，不可能1先于2出栈。

出栈序列325641可以得到，其进栈、出栈过程如图3-2所示。

3 5 6

2 2 4 4 4 4

1 1 1 1 1 1 1 1

3 32 32 325 325 3256 3256

4 325641

图3-2 进栈、出栈过程分析

【例6】在链栈中为什么不必设头结点？

分析：

在链栈中，首结点为栈顶元素。在栈中的插入、删除操作都在栈顶进行，因此每次插入、删除操作都要修改栈顶指针。如果设置头结点，则头结点后跟的是栈顶元素，每次插入、删除操作就要修改头结点中的指针。反正要修改一个指针，可见设置头结点是没有必要的。【例7】指出下述程序段的功能是什么？

void Prog1(SeqStack *S)

{ int i, n=0, a[64]; // 设栈中的元素个数小于64

while (! StackEmpty(S))

a[n++]=Pop(S);

for (i=0; i<=n; i++)

Push(S, a[i]);

}

答：Prog1的功能是将顺序栈S中的元素逆置。例如，执行Demo1前S=(a 1,a2,……，a n)，则执行Prog1后S=(a n, ……, a2, a1)。

【例8】指出下述程序段的功能是什么？

void Prog2(SeqStack *S1, S2)

{ SeqStack S1, S2,Temp; // 设S1已存在，S2, Temp已初始化

DataType x;

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,……，a n)，执行此程序段之后，S1=(a1,a2,……，a n)，S2=(a1,a2,……，a n)。程序的第一个while语句把S1的内容倒到Temp中，第二个while语句把Temp中的内容分别倒到S1和S2中。

【例9】指出下述程序段的功能是什么？

void Prog3 (SeqStack *S, char x)

{ SeqStack 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= "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);cout<

cout<

}

分析：本题主要是分清变量的内容进栈，还是字符直接进栈。按照程序，其进栈、出栈的主要步骤，以及变量x和y值的变化过程如图3-3所示。在While循环语句中，栈顶数据依次弹出到y，并输出。循环结束输出"stac"，最后输出x的值"k "，所以运行程序段的输出结果为："stack "。

k s

k t t t t t

a a a a a a a a

c c c c c c c c c

y= "k" y= "k " y= "k " y= "k" y= "k" y= "k" y= "s"y= "t" y= "a" y= "c"

图3-3 进栈、出栈过程分析

3.3 单元练习3解答

一．判断题答案

题目 1 2 3 4 5 6 7 8 9 10

答案√√×√××√××√

二．填空题答案

（1）栈顶（2）栈空

（3）O(1) （4）O(1)

（5）栈（6）栈空

（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

三．选择题答案

题目 1 2 3 4 5 6 7 8 9 10

答案C D B D B A A B D B

题目11 12 13 14 15 16 17 18 19 20

答案 B A A B B C B B C A

四．答案

（1）①IIIOOOIOIO ②IOIIOOIIOO

（2）求后缀表达式答案

① A B ^ C ^ D /

②0 A – B C * + D E / +

③ A B C + * D * E -

④ A B + C * E F G H / + / - D -

⑤8 5 2 + / 6 -

（3）stack （分析见典型习题分析【例10】）

五．算法设计题答案

（1）分析：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S [1]开始存放元素。

①【入栈程序代码】

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 x)

{ if (top= =0)

printf (“堆栈为空栈！”);

else

{ if (top= =1)

{ x= S [top];

top––;

}

else

{ x= S [top];

top=top–M;

}

（2）分析：设表达式在字符数组a[ ]中，使用一堆栈S来帮助判断。

【程序代码】

int correct (char a[ ])

{

stack s ;

InitStack (s); // 调用初始化栈函数

for (i=0; i

if (a[i]= =’(’)

Push (s,’(’);

else if (a[i]= =’)’)

{

if SEmpty (s) // SEmpty (s)为判栈空函数

return 0; // 若栈为空返回0；否则出栈

else

Pop(s);

}

if (SEmpty (s) )

printf (“配对正确！”); //若栈空，说明配对正确，并返回1 else

printf (“配对错误！”); // 配对错误返回0

}

（3）【程序代码】

#include

typedef struct stacknode // 栈的存储结构

{

int data;

struct stacknode *next;

}stacknode;

typedef struct

{

stacknode *top; // 指向栈的指针

}linkstack;

void Conversion(int n) // 二——十六进制转换函数{

linkstack s;

int x;

s.top=NULL;

{

x=n%16;

n=n/16;

stacknode *p;

p=new (stacknode);

p->next=s.top;

s.top=p;

s.top->data=x;

}

while(n);

printf("\n\t\t 转换以后的16进制数值为：");

while(s.top)

{ if (s.top->data<10)

printf("%d",s.top->data);

else

switch (s.top->data)

{ case 10: printf("%c",'A');break;

case 11: printf("%c",'B');break;

case 12: printf("%c",'C');break;

case 13: printf("%c",'D');break;

case 14: printf("%c",'E');break;

case 15: printf("%c",'F');break;

}

stacknode* p=s.top;

s.top=s.top->next;

free(p);

}

printf("\n\n");

}

void main()

{

int n;

printf("\n\t\t 请输入一个10进制正整数：");

scanf("%d",&n);

Conversion(n);

}