网志栈编辑推荐
各章中除给出本章练习题的参考答案外，还总结了本章的知识体系结构，并补充了大量的练习题并予以解析。附录中给出了几份近年来本科生、研究生数据结构考试试题及参考答案。书中列出了全部的练习题，因此自成一体，可以脱离主教材单独使用。 ；
内容简介
本书是《数据结构教程（第5版）》（李春葆等编著，清华大学出版社出版）的配套学习指导书。两书章节一一对应，内容包括绪论、线性表、栈和队列、串、递归、数组和广义表、树和二叉树、图、查找、内排序、外排序和文件。各章中除给出本章练习题的参考答案以外还总结了本章的知识体系结构，并补充了大量的练习题且予以解析，因此自成一体，可以脱离主教材单独使用。 本书适合高等院校计算机和相关专业的本科生及研究生使用。
作者简介
暂无
目录
目录
第1章绪论/
1.1本章知识体系/
1.2教材中的练习题及参考答案/
1.3补充练习题及参考答案/
1.3.1单项选择题/
媒体评论
评论
前沿
序言
免费在线读
第3章栈和队列
3.1本章知识体系1. 知识结构图
本章的知识结构如图3.1所示。
图3.1第3章知识结构图
2. 基本知识点(1) 栈、队列和线性表的异同。(2) 顺序栈的基本运算算法设计。(3) 链栈的基本运算算法设计。(4) 顺序队的基本运算算法设计。(5) 环形队列和非环形队列的特点。(6) 链队的基本运算算法设计。(7) 利用栈/队列求解复杂的应用问题。3. 要点归纳(1) 栈和队列的共同点是它们的数据元素都呈线性关系，且只允许在端点处插入和删除元素。(2) 栈是一种“后进先出”的数据结构，只能在同一端进行元素的插入和删除。(3) 栈可以采用顺序栈和链栈两类存储结构。(4) n个不同元素的进栈顺序和出栈顺序不一定相同。(5) 在顺序栈中通常用栈顶指针指向当前栈顶的元素。(6) 在顺序栈中用数组data［0..MaxSize-1］存放栈中元素，只能将一端作为栈底，另一端作为栈顶，通常的做法是将data［0］端作为栈底，data［MaxSize-1］端作为栈顶。用户也可以将data［MaxSize-1］端作为栈底，data［0］端作为栈顶，但不能将中间位置作为栈底或者栈顶。(7) 初始时栈顶指针top设置为-1，栈空的条件为top=-1，栈满的条件为top=MaxSize-1，元素x的进栈操作是top ; data［top］=x，出栈操作是x=data［top］; top--。这是经典做法，但不是唯一的方法，如果初始时top设置为0，可以设置栈空的条件为top=0，栈满的条件为top=MaxSize，元素x的进栈操作是data［top］=x; top ，出栈操作是top--; x=data［top］。(8) 在顺序栈或链栈中，进栈和出栈操作不涉及栈中元素的移动。(9) 在链栈中，由于每个结点是单独分配的，通常不考虑上溢出问题。(10) 无论是顺序栈还是链栈，进栈和出栈运算的时间复杂度均为O(1)。(11) 队列是一种“先进先出”的数据结构，只能从一端插入元素，从另一端删除元素。(12) 队列可以采用顺序队和链队两类存储结构。(13) n个元素进队的顺序和出队顺序总是一致的。(14) 在顺序队中的元素个数可以由队头指针和队尾指针计算出来。(15) 环形队列也是一种顺序队，是通过逻辑方法使其首尾相连的，解决非环形队列的假溢出现象。(16) 在环形队列中，队头指针f指向队头元素的前一个位置，队尾指针r指向队尾元素，这是一种经典做法，但不是唯一的方法，也可以让队头指针f指向队头元素。(17) 无论是顺序队还是链队，进队和出队运算的时间复杂度均为O(1)。(18) 在实际应用中，一般栈和队列都是用来存放临时数据的，如果先保存的元素先处理，应该采用队列； 如果后保存的元素先处理，应该采用栈。
3.2教材中的练习题及参考答案1. 有5个元素，其进栈次序为A、B、C、D、E，在各种可能的出栈次序中以元素C、D最先出栈(即C第一个且D第二个出栈)的次序有哪几个？答： 要使C第一个且D第二个出栈，应是A进栈，B进栈，C进栈，C出栈，D进栈，D出栈，之后可以有以下几种情况： (1) B出栈，A出栈，E进栈，E出栈，输出序列为CDBAE； (2) B出栈，E进栈，E出栈，A出栈，输出序列为CDBEA； (3) E进栈，E出栈，B出栈，A出栈，输出序列为CDEBA。所以可能的次序有CDBAE、CDBEA、CDEBA。2. 在一个算法中需要建立多个栈(假设3个栈或以上)时可以选用以下3种方案之一，试问这些方案相比各有什么优缺点？(1) 分别用多个顺序存储空间建立多个独立的顺序栈。(2) 多个栈共享一个顺序存储空间。(3) 分别建立多个独立的链栈。答： (1) 优点是每个栈仅用一个顺序存储空间时操作简单； 缺点是分配空间小了容易产生溢出，分配空间大了容易造成浪费，各栈不能共享空间。(2) 优点是多个栈仅用一个顺序存储空间，充分利用了存储空间，只有在整个存储空间都用完时才会产生溢出； 缺点是当一个栈满时要向左、右查询有无空闲单元，如果有，则要移动元素和修改相关的栈底和栈顶指针。当接近栈满时要查询空闲单元、移动元素和修改栈底、栈顶指针，这一过程计算复杂且十分耗时。(3) 优点是多个链栈一般不考虑栈的溢出； 缺点是栈中元素要以指针相链接，比顺序存储多占用了存储空间。3. 在以下几种存储结构中哪个最适合用作链栈？(1) 带头结点的单链表。(2) 不带头结点的循环单链表。(3) 带头结点的双链表。答： 栈中元素之间的逻辑关系属线性关系，可以采用单链表、循环单链表和双链表之一来存储，而栈的主要运算是进栈和出栈。当采用(1)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。当采用(2)时，前端作为栈顶，当进栈和出栈时首结点都发生变化，还需要找到尾结点，通过修改其next域使其变为循环单链表，算法的时间复杂度为O(n)。当采用(3)时，前端作为栈顶，进栈和出栈运算的时间复杂度为O(1)。但单链表和双链表相比，其存储密度更高，所以本题中最适合用作链栈的是带头结点的单链表。4. 简述以下算法的功能(假设ElemType为int类型)。
void fun(ElemType a［］,int n)
{int i;ElemType e;
SqStack *st1,*st2;
InitStack(st1);
InitStack(st2);
for (i=0;i
if (a［i］%2==1)
Push(st1,a［i］);
else
Push(st2,a［i］);
i=0;
while (!StackEmpty(st1))
{Pop(st1,e);
a［i ］=e;
}
while (!StackEmpty(st2))
{Pop(st2,e);
a［i ］=e;
}
DestroyStack(st1);
DestroyStack(st2);
}
答： 算法的执行步骤如下。(1) 扫描数组a，将所有奇数进到st1栈中，将所有偶数进到st2栈中。(2) 先将st1的所有元素(奇数元素)退栈，放到数组a中并覆盖原有位置的元素； 再将st2的所有元素(偶数元素)退栈，放到数组a中并覆盖原有位置的元素。(3) 销毁两个栈st1和st2。所以本算法的功能是利用两个栈将数组a中的所有奇数元素放到所有偶数元素的前面。例如ElemType a［］={1,2,3,4,5,6}，执行算法后数组a改变为{5,3,1,6,4,2}。5. 简述以下算法的功能(顺序栈的元素类型为ElemType)。
void fun(SqStack *&st,ElemType x)
{SqStack *tmps;
ElemType e;
InitStack(tmps);
while(!StackEmpty(st))
{Pop(st,e);
if(e!=x) Push(tmps,d);
}
while (!StackEmpty(tmps))
{Pop(tmps,e);
Push(st,e);
}
DestroyStack(tmps);
}
答： 算法的执行步骤如下。(1) 建立一个临时栈tmps并初始化。(2) 退栈st中的所有元素，将不为x的元素进栈到tmps中。(3) 退栈tmps中的所有元素，并进栈到st中。(4) 销毁栈tmps。所以本算法的功能是如果栈st中存在元素x，将其从栈中清除。例如，st栈中从栈底到栈顶为a、b、c、d、e，执行算法fun(st，c)后，st栈中从栈底到栈顶为a、b、d、e。6. 简述以下算法的功能(栈st和队列qu的元素类型均为ElemType)。
bool fun(SqQueue *&qu,int i)
{ElemType e;
int j=1;
int n=(qu->rear-qu->front MaxSize)%MaxSize;
if (j<1 ‖ j>n) return false;
for (j=1;j<=n;j )
{deQueue(qu,e);
if (j!=i)
enQueue(qu,e);
}
return true;
}
答： 算法的执行步骤如下。(1) 求出队列qu中的元素个数n，参数i错误时返回假。(2) qu出队共计n次，除了第i个出队的元素以外，其他出队的元素立即进队。(3) 返回真。所以本算法的功能是删除qu中从队头开始的第i个元素。例如，qu中从队头到队尾的元素是a、b、c、d、e，执行算法fun(qu，2)后，qu中从队头到队尾的元素改变为a、c、d、e。7. 什么是环形队列？采用什么方法实现环形队列？答： 在用数组表示队列时把数组看成是一个环形的，即令数组中的第一个元素紧跟在最末一个单元之后就形成了一个环形队列。环形队列解决了非环形队列中出现的“假溢出”现象。通常采用逻辑上求余数的方法来实现环形队列，假设数组的大小为n，当元素下标i增1时采用i=(i 1)%n来实现。8. 环形队列一定优于非环形队列吗？在什么情况下使用非环形队列？答： 队列主要用于保存中间数据，而且保存的数据满足先产生先处理的特点。非环形队列可能存在数据假溢出现象，即队列中还有空间，可是队满的条件却成立了，为此改为环形队列，这样克服了假溢出现象。但并不能说环形队列一定优于非环形队列，因为环形队列中出队元素的空间可能被后来进队的元素覆盖，如果算法要求在队列操作结束后利用进队的所有元素实现某种功能，这样环形队列就不适合了，在这种情况下需要使用非环形队列，例如利用非环形队列求解迷宫路径就是这种情况。9. 假设以I和O分别表示进栈和出栈操作，栈的初态和终栈均为空，进栈和出栈的操作序列可表示为仅由I和O组成的序列。(1) 在下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO(2) 通过对(1)的分析，设计一个算法判定所给的操作序列是否合法，若合法返回真，否则返回假(假设被判定的操作序列已存入一维数组中)。解： (1) 选项A、D均合法，而选项B、C不合法。因为在选项B中先进栈一次，立即出栈3次，这会造成栈下溢。在选项C中共进栈5次，出栈3次，栈的终态不为空。(2) 本题使用一个链栈来判断操作序列是否合法，其中str为存放操作序列的字符数组，n为该数组的字符个数(这里的ElemType类型设定为char)。对应的算法如下：
bool judge(char str［］,int n)
{int i=0; ElemType x;
LinkStNode *ls;
bool flag=true;
InitStack(ls);
while (i
Push(ls,str［i］);
else if (str［i］==O)//出栈
{if (StackEmpty(ls))
flag=false;//栈空时
else
Pop(ls,x);
}
else
flag=false;//其他值无效
i ;
}
if (!StackEmpty(ls)) flag=false;
DestroyStack(ls);
return flag;
}
10. 假设表达式中允许包含圆括号、方括号和大括号3种括号，编写一个算法判断表达式中的括号是否正确配对。解： 设置一个栈st，扫描表达式exp，当遇到(、［或{时将其进栈； 当遇到)时，若栈顶是(，则继续处理，否则以不配对返回假； 当遇到］时，若栈顶是［，则继续处理，否则以不配对返回假； 当遇到}时，若栈顶是{，则继续处理，否则以不配对返回假。在exp扫描完毕后，若栈不空，则以不配对返回假； 否则以括号配对返回真。本题的算法如下：
bool Match(char exp［］,int n)
{LinkStNode *ls;
InitStack(ls);
int i=0;
ElemType e;
bool flag=true;
while (i
Push(ls,exp［i］);//遇到(、［或{,将其进栈
if (exp［i］==))//遇到),若栈顶是(,继续处理,否则以不配对返回
{if (GetTop(ls,e))
{if (e==() Pop(ls,e);
else flag=false;
}
else flag=false;
}
if (exp［i］==］)//遇到］,若栈顶是［,继续处理,否则以不配对返回
{if (GetTop(ls,e))
{if (e==［) Pop(ls,e);
else flag=false;
}
else flag=false;
}
if (exp［i］==})//遇到},若栈顶是{,继续处理,否则以不配对返回
{if (GetTop(ls,e))
{if (e=={) Pop(ls,e);
else flag=false;
}
else flag=false;
}
i ;
}
if (!StackEmpty(ls)) flag=false;//若栈不空,则不配对
DestroyStack(ls);
return flag;
}
11. 设从键盘输入一序列的字符a1、a2、…、an。设计一个算法实现这样的功能： 若ai为数字字符，ai进队； 若ai为小写字母，将队首元素出队； 若ai为其他字符，表示输入结束。要求使用环形队列。解： 先建立一个环形队列qu，用while循环接收用户的输入，若输入数字字符，将其进队； 若输入小写字母，出队一个元素，并输出它； 若为其他字符，则退出循环。本题的算法如下：
void fun()
{ElemType a,e;
SqQueue *qu;//定义队列指针
InitQueue(qu);
while (true)
{printf("输入a:");
scanf("%s",&a);
if (a>= && a<=9)//为数字字符
{if (!enQueue(qu,a))
printf("队列满,不能进队＼n");
}
else if (a>=a && a<=z)//为小写字母
{if (!deQueue(qu,e))
printf("队列空,不能出队＼n");
else
printf("出队元素:%c＼n",e);
}
else break;//为其他字符
}
DestroyQueue(qu);
}
12. 设计一个算法，将一个环形队列(容量为n，元素下标从0到n-1)的元素倒置。例如，图3.2(a)为倒置前的队列(n=10)，图3.2(b)为倒置后的队列。
图3.2一个环形队列倒置前后的状态
解： 使用一个临时栈st，先将qu队列中的所有元素出队并将其进栈st，直到队列空为止。然后初始化队列qu(队列清空)，再出栈st的所有元素并将其进队qu，最后销毁栈st。对应的算法如下：
void Reverse(SqQueue *&qu)
{ElemType e;
SqStack *st;
InitStack(st);
while (!QueueEmpty(qu))//队不空时出队并进栈
{deQueue(qu,e);
Push(st,e);
}
InitQueue(qu);//队列初始化
while (!StackEmpty(st))//栈不空时出栈并将元素入队
{Pop(st,e);
enQueue(qu,e);
}
DestroyStack(st);
}
13. 编写一个程序，输入n(由用户输入)个10以内的数，每输入i(0≤i≤9)就把它插入到第i号队列中，最后把10个队中的非空队列按队列号从小到大的顺序串接成一条链，并输出该链的所有元素。解： 建立一个队头指针数组quh和队尾指针数组qut，quh［i］和qut［i］表示i号(0≤i≤9)队列的队头和队尾，先将它们的所有元素置为NULL。对于输入的x，采用尾插法将其链到x号队列中。然后按0~9编号的顺序把这些队列中的结点构成一个不带头结点的单链表，其首结点指针为head。最后输出单链表head的所有结点值并释放所有结点。对应的程序如下：
#include
#include
#define MAXQNode 10//队列的个数
typedef struct node
{int data;
struct node *next;
} QNode;
void Insert(QNode *quh［］,QNode *qut［］,int x)//将x插入到相应队列中
{QNode *s;
s=(QNode *)malloc(sizeof(QNode));//创建一个结点s
s->data=x; s->next=NULL;
if (quh［x］==NULL)//x号队列为空队时
{quh［x］=s;
qut［x］=s;
}
else//x号队列不空队时
{qut［x］->next=s;//将s结点链到qut［x］所指的结点之后
qut［x］=s;//让qut［x］仍指向尾结点
}
}
void Create(QNode *quh［］,QNode *qut［］)//根据用户的输入创建队列
{int n,x,i;
printf("n:");
scanf("%d",&n);
for (i=0;i
{do
{printf("输入第%d个数:",i 1);
scanf("%d",&x);
} while (x<0 ‖ x>10);
Insert(quh,qut,x);
}
}
void DestroyList(QNode *&head)//释放单链表
{QNode *pre=head,*p=pre->next;
while (p!=NULL)
{
free(pre);
pre=p; p=p->next;
}
free(pre);
}
void DispList(QNode *head)//输出单链表的所有结点值
{printf("＼n输出所有元素:");
while (head!=NULL)
{printf("%d ",head->data);
head=head->next;
}
printf("＼n");
}
QNode *Link(QNode *quh［］,QNode *qut［］)//将非空队列链接起来并输出
{QNode *head=NULL,*tail;//总链表的首结点指针和尾结点指针
int i;
for (i=0;i
if (quh［i］!=NULL)//i号队列不空
{if (head==NULL)//若i号队列为第一个非空队列
{head=quh［i］;
tail=qut［i］;
}
else//若i号队列不是第一个非空队列
{tail->next=quh［i］;
tail=qut［i］;
}
}
tail->next=NULL;
return head;
}
int main()
{int i;
QNode *head;
QNode *quh［MAXQNode］,*qut［MAXQNode］;//各队列的队头quh和队尾指针qut
for (i=0;i
quh［i］=qut［i］=NULL;//置初值空
Create(quh,qut);//建立队列
head=Link(quh,qut);//链接各队列产生单链表
DispList(head);//输出单链表
DestroyList(head);//销毁单链表
return 1;
}
3.3补充练习题及参考答案3.3.1单项选择题
1. 以下数据结构中元素之间为线性关系的是。
A. 栈B. 队列C. 线性表D. 以上都是答： D。2. 栈和队列的共同点是。A. 都是先进后出B. 都是先进先出C. 只允许在端点处插入和删除元素D. 没有其同点答： 栈和队列都是受限线性表，所谓“受限”指的是在端点处插入和删除元素，所以本题的答案为C。3. 经过以下栈运算后x的值是。
InitStack(s);Push(s，a);Push(s，b);Pop(s，x);GetTop(s，x);
A. aB. bC. 1D. 0答： A。4. 经过以下栈运算后StackEmpty(s)的值是。
InitStack(s);Push(s，a);Push(s，b);Pop(s，x);Pop(s，y)
A. aB. bC. 1D. 0答： C。5. 设一个栈的输入序列为a，b，c，d，则借助一个栈所得到的输出序列不可能是。A. a，b，c，dB. d，c，b，aC. a，c，d，bD. d，a，b，c答： 以d开头的出栈序列只有d，c，b，a一种。本题的答案为D。6. 已知一个栈的进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=n，则pi的值是。A. iB. n-iC. n-i 1D. 不确定答： 当p1=n时输出序列只有一种，即n，n-1，…，3，2，1，则p2=n-1，p3=n-2，…，pn=1，推断出pi=n-i 1，本题的答案为C。7. 设n个元素进栈序列是1，2，3，…，n，其输出序列是p1，p2，…，pn，若p1=3，则p2的值。A. 一定是2B. 一定是1C. 不可能是1D. 以上都不对答： 当p1=3时，说明1、2、3先依次进栈，出栈3，然后可能出栈2，也可能是4或后面的元素进栈后再出栈。因此，p2可能是2，也可能是4，…，n，但一定不能是1。本题的答案为C。8. 设n个元素进栈序列是p1，p2，p3，…，pn，其输出序列是1，2，3，…，n，若pn=1，则pi(1≤i≤n-1)的值是。A. n-i 1B. n-iC. iD. 有多种可能答： 当pn=1时，表示它是第一个出栈元素，因此这样的输出序列是唯一的，即有pn-1=2，pn-2=3，…，p1=n，也就是说pi=n-i 1。本题的答案为A。9. 一个栈的入栈序列为1、2、3、…、n，其出栈序列是p1、p2、p3、…、pn。若p2=3，则p3可能取值的个数是。A. n-3B. n-2C. n-1D. 无法确定答： 若1进栈，1出栈(p1)，2进栈，3进栈，3出栈(p2)，之后可以2出栈(p3)，也可以4~n的任何元素进栈再出栈(p3)，所以p3可以是2或者4~n。另外，1、2依次进栈，2出栈(p1)，3进栈，3出栈(p2)，1出栈(p3)。也就是说，p3可以是3以外的任何元素。本题的答案为C。10. 设栈S和队列Q的初始状态为空，元素e1~e6依次通过栈S，一个元素出后即进队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是。
A. 5B. 4C .3D. 2答： 操作过程为e1进栈，e2进栈，e2出栈后进队，e3进栈，e4进栈，e4出栈后进队，e3出栈后进队，e5进栈，e6进栈，e6出栈后进队，e5出栈后进队，e1出栈后进队，栈中元素最多时为3个。本题的答案为C。11. 判定一个顺序栈st(元素的个数最多为MaxSize)为空的条件可以设置为。A. st->top== MaxSize/2B. st->top!= MaxSize/2C. st->top!=MaxSize-1D. st->top==MaxSize-1答： 顺序栈总是以一端(0或者MaxSize-1端)作为栈底，栈空是指栈不存在元素，合适的栈空条件为st->top== MaxSize-1。本题的答案为D。12. 若一个栈用数组data［1..n］存储，初始栈顶指针top为n 1，则以下元素x进栈的操作正确的是。A. top ;data［top］=x;B. data［top］=x;top ;C. top--;data［top］=x;D. data［top］=x;top--;答： 初始栈顶指针top为n 1，说明是将data［n］端作为栈底、data［1］端作为栈顶，在进栈时top应递减，由于不存在data［n 1］的元素，所以在进栈时应先将top递减，再将x放在top处。本题的答案为C。13. 若一个栈用数组data［1..n］存储，初始栈顶指针top为n，则以下元素x进栈的操作正确的是。A. top ;data［top］=x;B. data［top］=x;top ;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为n，说明是将data［n］端作为栈底、data［1］端作为栈顶，在进栈时top应递减，由于存在data［n］的元素，所以在进栈时应先将x放在top处，再将top递减。本题的答案为D。14. 若一个栈用数组data［1..n］存储，初始栈顶指针top为0，则以下元素x进栈的操作正确的是。A. top ;data［top］=x;B. data［top］=x;top ;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为0，说明是将data［1］端作为栈底、data［n］端作为栈顶，在进栈时top应递增，由于不存在data［0］的元素，所以在进栈时应先将top递增，再将x放在top处。本题的答案为A。
15. 若一个栈用数组data［1..n］存储，初始栈顶指针top为1，则以下元素x进栈的操作正确的是。A. top ;data［top］=x;B. data［top］=x;top ;C. top--;data［top］=x;D. data［top］=x; top--;答： 初始栈顶指针top为1，说明是将data［1］端作为栈底、data［n］端作为栈底，在进栈时top应递增，由于存在data［1］的元素，所以在进栈时应先将x放在top处，再将top递增。本题的答案为B。
说明： 从12~15小题可以看出，顺序栈的设计并不是唯一的，只要能满足栈的操作特点又能充分利用存储空间就是一种合适的设计。
16. 以下各链表均不带有头结点，其中最不适合用作链栈的链表是。A. 只有表头指针没有表尾指针的循环双链表B. 只有表尾指针没有表头指针的循环双链表C. 只有表尾指针没有表头指针的循环单链表D. 只有表头指针没有表尾指针的循环单链表答： 只有表头指针没有表尾指针的循环单链表(不带头结点)在进栈和出栈操作后需要保持循环单链表形式不变，实现进栈和出栈运算的时间复杂度均为O(n)。本题的答案为D。17. 由两个栈共享一个数组空间的好处是。A. 减少存取时间，降低上溢出发生的几率B. 节省存储空间，降低上溢出发生的几率C. 减少存取时间，降低下溢出发生的几率D. 节省存储空间，降低下溢出发生的几率答： B。18. 表达式a*(b c)-d的后缀表达式是。A. abcd* -B. abc *d-C. abc* d-D. - *abcd答： 选项A对应的中缀表达式为a-(b c*d)，选项B对应的中缀表达式为a*(b c)-d，选项C对应的中缀表达式为(a b*c)-d，选项D不是合法的后缀表达式。本题的答案为B。19. 在将算术表达式“1 6/(8-5)*3”转换成后缀表达式的过程中，当扫描到5时运算符栈(从栈顶到栈底次序)为。A. - / B. - ( / C. / D. / - 答： 算术表达式“1 6/(8-5)*3”的后缀表达式是“1 6 8 5 - / 3 * ”，当扫描到5时，前面的运算符 、/、(和-均在栈中，运算符栈中从栈顶到栈底次序为- ( / 。本题的答案为B。20. 在利用栈求表达式的值时，设立运算数栈OPND，设OPND只有两个存储单元，在求下列表达式中不发生上溢出的是。A. a-b*(c d)B. (a-b)*c d
C. (a-b*c) dD. (a-b)*(c d)答： 选项A对应的后缀表达式为a b c d * -，在求值时OPND的最少存储单元为4。选项B对应的后缀表达式为a b - c * d ，在求值时OPND的最少存储单元为2。选项C对应的后缀表达式为a b c * - d ，在求值时OPND的最少存储单元为3。选项D对应的后缀表达式为a b - c d *，在求值时OPND的最少存储单元为3。本题的答案为B。21. 经过以下队列运算后QueueEmpty(qu)的值是。
InitQueue(qu);enQueue(qu，a);enQueue(qu，b);deQueue(qu，x);deQueue(qu，y);
A. aB. bC. trueD. false答： C。22. 环形队列。A. 不会产生下溢出B. 不会产生上溢出C. 不会产生假溢出D. 以上都不对答： C。23. 在环形队列中元素的排列顺序。A. 由元素进队的先后顺序确定B. 与元素值的大小有关C. 与队头和队尾指针的取值有关D. 与队中数组大小有关答： A。24. 某环形队列的元素类型为char，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素，如图3.3所示，则队中元素为。A. abcd123456B. abcd123456cC. dfgbcaD. cdfgbcab
图3.3一个环形队列
答： front=12，队头元素应为下标13的元素，rear=2，队尾元素应为下标2的元素，队中元素从队头到队尾是data［13..2］，本题的答案为C。25. 已知环形队列存储在一维数组A［0..n-1］中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列空，且要求第一个进入队列的元素存储在A［0］处，则初始时front和rear的值分别是。A. 0，0B. 0，n-1C. n-1，0D. n-1，n-1答： 在环形队列中，进队操作是队尾指针rear循环加1，再在该处放置进队的元素，这里要求第一个进队元素存储在A［0］处，则rear应为n-1，因为这样(rear 1)%n=0。而队头指向队头元素，此时队头位置为0，所以front的初值为0。本题的答案为B。26. 若某环形队列有队头指针front和队尾指针rear，在队不满时进队操作仅会改变。A. frontB. rearC. front和rearD. 以上都不对答： B。27. 设环形队列中数组的下标是0~N-1，其队头指针为f(指向队头元素的前一个位置)、队尾指针为r(指向队尾元素)，则其元素个数为。A. r-fB. r-f-1C. (r-f)％N 1D. (r-f N)％N答： 对于非环形队列，每次是先移动指针，再存取元素，其中的元素个数=r-f，但由于是环形队列，r可能小于f，为此求环形队列中元素个数的公式改为(r-f N)％N。本题的答案为D。28. 设环形队列的存储空间为a［0..20］，且当前队头指针(f指向队首元素的前一个位置)和队尾指针(r指向队尾元素)的值分别为8和3，则该队列中的元素个数为。A. 5B. 6C. 16D. 17答： 这里MaxSize=21，其中的元素个数=(r-f MaxSize)%MaxSize=16。本题的答案为C。29. 设环形队列中数组的下标是0~N-1，已知其队头指针f(f指向队首元素的前一个位置)和队中元素个数n，则队尾指针r(r指向队尾元素的位置)为。A. f-nB. (f-n)%NC. (f n)％ND. (f n 1)％N答： C。30. 设环形队列中数组的下标是0~N-1，已知其队尾指针r(r指向队尾元素的位置)和队中元素个数n，则队尾指针f(f指向队头元素的前一个位置)为。A. r-nB. (r-n)%N
C. (r-n N)％ND. (r n)％N答： C。31. 若用一个大小为6的数组来实现环形队列，rear作为队尾指针指向队列中的尾部元素，front作为队头指针指向队头元素的前一个位置。现在rear和front的值分别是0和3，当从队列中删除一个元素再加入两个元素后rear和front的值分别是。A. 1和5B. 2和4C. 4和2D. 5和1答： 删除一个元素时front循环增1，进队两个元素时rear循环增2。本题的答案为B。32. 有一个环形队列qu(存放元素位置0~MaxSize-1)，rear作为队尾指针指向队列中的尾部元素，front作为队头指针指向队头元素的前一个位置，则队满的条件是。A. qu->front==qu->rearB. qu->front 1==qu->rearC. qu->front==(qu->rear 1)%MaxSizeD. qu->rear==(qu->front 1)%MaxSize答： 根据环形队列的结构很快可以排除选项A和B(因为它们与MaxSize无关)。环形队列中约定，当进队一个元素后到达了队头就表示队满，进队操作是rear循环增1。本题的答案为C。33. 假设用Q［0..M］实现环形队列，f作为队头指针指向队头元素的前一个位置，r作为队尾指针指向队尾元素。若用“(r 1)%(M 1)==f”作为队满的标志，则。A. 可用“f==r”作为队空的标志B. 可用“f>r”作为队空的标志C. 可用“(f 1)%(M 1)==r”作为队空的标志D. 队列中最多可以有M l个元素答： 这里MaxSize等于M 1，若用“(r 1)%(M 1)==f”作为队满的标志，队列中最多可以有M个元素。本题的答案为A。34. 环形队列存放在一维数组A［0.. M-1］中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可以进行入队和出队操作，队列中最多能容纳M-1个元素，初始时为空。下列判断队空和队满的条件中正确的是。A. 队空： end1==end2;队满： end1==(end2 1) mod MB. 队空： end1==end2;队满： end2==(end1 1) mod (M-1)C. 队空： end2==(end1 1) mod M;队满： end1==(end2 1) mod MD. 队空： end1==(end2 1) mod M;队满： end2==(end1 1) mod (M-1)答： 这里环形队列是让队头指针指向队头元素、队尾指针指向队尾元素的后一个位置，和经典做法让队头指针指向队头元素的前一个位置、队尾指针指向队尾元素，在判断队空和队满的条件上是相同的，都是通过少放一个元素来区分队空和队满。本题的答案为A。35. 若用data［0.. n-1］数组来实现环形队列，初始时队头指针front(指向队头元素的前一个位置)和队尾指针rear(指向队列中的尾部元素)均为0，现有1~6的6个元素进队，然后出队8次，发现原来存放元素4的位置变为队头，则n为。A. 5B. 4C. 8D. 10答： 初始时，front=rear=0，进队1~6元素，此时元素4的位置为3，出队8次后，队头指针front=(front 8)%n=8%n，即8%n=3，则n=5。本题的答案为A。36. 假设用一个不带头结点的单链表表示队列，队尾应该在链表的位置。A. 链头B. 链尾C. 链中D. 以上都可以答： B。37. 最适合用作链队的链表是。A. 带队首指针和队尾指针的循环单链表B. 带队首指针和队尾指针的非循环单链表C. 只带队首指针的非循环单链表D. 只带队首指针的循环单链表答： 对于链队，进队操作是在队尾插入结点，出队操作是删除队首结点。对于带队首指针和队尾指针的非循环单链表，这两种操作的时间复杂度均为O(1)，所以本题的答案为B。38. 最不适合用作链队的链表是。A. 只带队首指针的非循环双链表B. 只带队首指针的循环双链表C. 只带队尾指针的循环双链表D. 只带队尾指针的循环单链表答： 选项A和B均可用作链式队列，但不必采用循环单链表，这样反而降低了队列基本运算的效率。本题的答案为A。3.3.2填空题1. 栈是一种具有特性的线性表。答： 后进先出或先进后出。2. 设栈S和队列Q的初始状态均为空，元素a，b，c，d，e，f，g依次进栈S。若每个元素出栈后立即进入队列Q，且7个元素出列的顺序是b，d，c，f，e，a，g，则栈S的容量至少是。答： 3。由于队列不改变进出序列，这里变为求通过一个栈将a，b，c，d，e，f，g序列变为b，d，c，f，e，a，g序列时栈空间至少多大？从其进出栈过程可以看到，栈中最多有3个元素，即栈大小至少为3。3. 一个初始输入序列1,2,…,n，出栈序列是p1,p2,…,pn，若p1=1，则p2的可能取值个数为。答： n-1。p2不可能取值1，其他2~n的值都可能。4. 一个初始输入序列1,2,…,n，出栈序列是p1,p2,…,pn，若p1=4，则p2的可能取值个数为。答： n-3。p2不可能取值4、2、1，其他值都可能。5. 栈的常用运算是进栈和出栈，设计栈的一种好的存储结构应尽可能保证进栈和出栈运算的时间复杂度为。答： O(1)。6. 当利用大小为n的数组data［0..n-1］存储一个顺序栈时，假定用top==n表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。答： top--。7. 当利用大小为n的数组data［0..n-1］存储一个顺序栈时，假定用top==-1表示栈空，则向这个栈插入一个元素时首先应执行语句修改top指针。答： top 。8. 若用data［1..m］作为顺序栈的存储空间，栈空的标志是栈顶指针top的值等于m 1，则每进行一次①操作，需将top的值加1； 每进行一次②操作，需将top的值减1。答： ①出栈②进栈。这里以data［m］端作为栈底、data［1］端作为栈顶。9. 当两个栈共享一个存储区时，栈利用一维数组data［1..n］表示，栈1在低下标处，栈2在高下标处。两栈顶指针为top1和top2，初始值分别为0和n 1，则当栈1空时top1为①，栈2空时②，栈满时为③。答： ①top1=0②top2=n 1③top1 1=top2。10. 表达式“a ((b*c-d)/e f*g/h) i/j”的后缀表达式是。答： a b c * d - e / f g * h / i j / 。11. 如果栈的最大长度难以估计，则其存储结构最好使用。答： 链栈。12. 若用带头结点的单链表st来表示链栈，则栈空的标志是。答： st->next==NULL。13. 若用不带头结点的单链表st来表示链式栈，则创建一个空栈所要执行的操作是。答： st=NULL。14. 在用栈求解迷宫路径时，当找到出口时，栈中所有方块。答： 构成一条迷宫路径。15. 若用Q［1..m］作为非环形顺序队列的存储空间，则最多只能执行次进队操作。答： m。16. 若用Q［1..100］作为环形队列的存储空间，f、r分别表示队头和队尾指针，f指向队头元素的前一个位置，r指向队尾元素，则当f=70，r=20时，队列中共有个元素。答： 50。这里MaxSize=100，元素个数=(r-f MaxSize)%MaxSize=50。17. 环形队列用数组A［m..n］(m
答： 栈的特点是先进后出，所以在解决的实际问题涉及后进先出的情况时可以考虑使用栈。例如求解表达式括号匹配问题时通常使用一个栈，将读到的左括号进栈，每读入一个右括号，判断栈顶是否为左括号，若是，则出栈； 否则，表示不匹配。队列的特点是先进先出。例如求解操作系统中的作业排队问题时通常使用队列，因为在允许多道程序运行的计算机系统中同时有几个作业运行，如果运行的结果都需要通过通道输出，那就要按请求输出的先后次序排队。每当通道传输完毕并可以接受新的输出任务时，队头的作业先从队列中退出做输出操作(出队)。凡是申请输出的作业都从队尾进入队列(进队)。2. 假设有4个元素a、b、c、d依次进栈，进栈和出栈操作可以交替进行，试写出所有可能的出栈序列。答： 当进栈的元素为n个时，经过栈运算后可得到的输出序列个数为1n 1Cn2n，其中Cn2n=(2n)!n!n!。这里n=4时，出栈序列个数为15×8!4!×4!=14种，如表3.1所示。
表3.1出栈序列
以a开头abcdabdcacbdacdbadcb以b开头bacdbadcbcadbcdabdca以c开头cbadcbdacdba以d开头dcba
3. 假设以S和X分别表示进栈和出栈操作，则初态和终态均为栈空的进栈和出栈的操作序列，可以表示为仅由S和X组成的序列，称可以实现的栈操作序列为合法序列(例如SSXX为合法序列，而SXXS为非法序列)。试给出区分给定序列为合法序列或非法序列的一般准则，并证明对同一输入序列的两个不同的合法序列不可能得到相同的输出序列。答： 合法的栈操作序列必须满足以下两个条件。(1) 在操作序列的任何前缀(从开始到任何一个操作时刻)中，S的个数不得少于X的个数。(2) 整个操作序列中S和X的个数相等。要求证明： 对同一输入序列a1a2…an的两个不同的合法操作序列p=p1p2…pj-1pj…p2n，q=q1q2…qj-1qj…q2n，不可能得到相同的输出序列。
证明： 因为p≠q，所以一定存在一个j(1≤j≤2n)，使得p1p2…pj-1=q1q2…qj-1，而pj≠qj，假设操作子序列p1p2…pj-1已将a1a2…ai-1进栈且将其中的某些元素出栈，而aiai 1…an尚未进栈。
因为p和q都是合法的栈操作序列，且pj≠qj，所以pj和qj中必有一个为S操作，另一个为X操作(不失一般性，不妨设pj为S操作，qj为X操作)，而且栈不必为空(否则就不能进行X操作)。设栈顶元素为af(1≤f≤i)。因此对于操作序列p来说，在其对应的输出序列中ai必领先于af(因为pj为S操作，它使ai进栈而af尚在栈中)，对于操作序列q来说，在其对应的输出序列中af必领先于ai(因为qj为X操作，它使af出栈而ai尚未进栈)，所以p和q必定对应不同的输出序列。4. 什么是队列的上溢现象和假溢出现象？解决假溢出有哪些方法？
答： 在队列的顺序存储结构中，设队头指针为front、队尾指针为rear、队的容量(存储空间的大小)为MaxSize。当有元素进队时，若rear=MaxSize(初始时rear=0)，则发生队列的上溢现象，不能做进队操作。所谓队列假溢出现象是指队列中还有剩余空间但元素却不能进入队列，造成这种现象的原因是队列的设计不合理。解决队列假溢出的方法有以下几种： (1) 建立一个足够大的存储空间，但这样做会造成空间的使用效率降低。(2) 当出现假溢出时可采用以下几种方法。① 采用平移元素的方法： 每当进队一个元素时，队列中已有的元素向队头移动一个位置(当然要有空闲的空间可供移动)。这种方法对应进队运算的时间复杂度为O(n)。② 每当出队一个元素时，依次移动队中的元素，始终使front指针指向队列中的第一个元素位置。这种方法对应出队运算的时间复杂度为O(n)。③ 采用环形队列方式： 把队列看成一个首尾相接的环形队列，在环形队列上进行进队或出队运算时仍然遵循“先进先出”的原则。这种方法对应进队和出队运算的时间复杂度均为O(1)。5. 在利用两个栈S1、S2模拟一个队列时如何用栈的基本运算实现队列的进队、出队以及队列的判空等基本运算，请简述算法思想。答： 利用两个栈S1和S2模拟一个队列的基本思想是用栈S1作为输入栈、栈S2作为输出栈。进队时，总是将元素进栈到S1，出队时，若输出栈S2已空，则将S1中的元素全部出栈到S2中，然后由S2出栈元素。若输出栈S2不空，则直接由S2出栈元素。显然，只有当输入栈、输出栈均为空时队列才为空。6. 设输入元素为1、2、3、P和A，输入次序为123PA，元素经过一个栈后产生输出序列，在所有输出序列中有哪些序列可作为高级语言的变量名(以字母开头的字母数字串)。答： AP321，PA321，P3A21，P32A1，P321A。7. 用栈实现将中缀表达式8-(3 5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。答： 栈的变化过程如表3.2所示。最后生成的后缀表达式为8 3 5 5 6 2 / - * -，其求值结果为-8。
表3.2将中缀表达式8-(3 5)*(5-6/2)转换成后缀表达式时栈的变化过程
op栈postexp说明8#将8#存入postexp中-8#-进栈-(8#(进栈-(8#3#将3#存入postexp中-( 8#3# 进栈-( 8#3#5#将5#存入postexp中-8#3#5# 遇到)，将 和(出栈-*8#3#5# *进栈-*(8#3#5# (进栈-*(8#3#5# 5#将5#存入postexp中-*(-8#3#5# 5#-进栈-*(-8#3#5# 5#6#将6#存入postexp中-*(-/8#3#5# 5#6#/进栈-*(-/8#3#5# 5#6#2#将2#存入postexp中-*8#3#5# 5#6#2#/-遇到)，将/\-和(出栈8#3#5# 5#6#2#/-*-exp扫描完毕，将栈中的所有运算符依次出栈并存入数组postexp中，得到后缀表达式
8. 简述以下算法的功能：
void fun(int a［］,int n)
{int i=0,e;
SqStack *st;
InitStack(st);
for (i=0;i
Push(st,a［i］);
i=0;
while (!StackEmpty(st))
{Pop(st,e);
a［i ］=e;
}
DestroyStack(st);
}
答： 算法的执行步骤如下。(1) 扫描整数数组a，将所有元素进到st栈中。(2) 将st的所有元素退栈，放到数组a中并覆盖原有位置的元素，从而将数组a的所有元素逆置。(3) 销毁栈st。所以本算法的功能是利用栈st将数组a中的所有元素逆置。9. 阅读以下程序，给出其输出结果：
char *fun(int d)
{char e;int i=0,x;
static char b［MaxSize］;
SqStack *st;
InitStack(st);
while (d!=0)
{x=d%16;
if (x<10)e= x;
elsee=A x-10;
Push(st,e);
d/=16;
}
while (!StackEmpty(st))
{Pop(st,e);
b［i ］=e;
}
b［i］=＼0;
DestroyStack(st);
return b;
}
int main()
{int d=1000,i;
char *b;
b=fun(d);
for (i=0;b［i］;i )
printf("%c",b［i］);
printf("＼n");
return 1;
}
答： fun(d)算法的功能是采用辗转相除法将十进制数d转换成十六进制数，并用数组b存放十六进制数串。本程序的功能是将十进制数1000转换成十六进制数并输出，其结果为3E8。10. 算法fun的功能是借助栈结构实现整数从十进制到八进制的转换，阅读算法并回答问题： (1) 画出n为十进制数1348时算法执行过程中栈的动态变化情况。(2) 说明算法中while循环完成的操作。
void fun(int n)//n为非负的十进制整数
{int e;
SqStack*S;
InitStack(S);
do
{Push(S,n%8);
n=n/8;
} while (n);
while (!StackEmpty(S))
{Pop(S,e);
printf("%ld",e);
}
}
答： (1) n为十进制数1348时算法执行过程中栈的动态变化情况如图3.4所示，产生对应的八进制数为2504。
图3.4栈的动态变化情况
(2) 算法中while循环的操作是退栈所有元素并输出，即从高位到低位输出八进制数。11. 简述以下算法的功能(栈的元素类型为int)。
void fun(SqStack *&st)
{int i,j=0,A［MaxSize］;
while (!StackEmpty(st))
{Pop(S,A［j］);
j ;
}
for(i=0;i
Push(S,A［i］);
}
答： 算法的执行步骤如下。(1) 将栈st中的所有元素退栈并存放到数组A中。(2) 将A中的元素一一进栈，达到逆置栈st的目的。所以本算法的功能是逆置栈st的所有元素。3.3.5算法设计题1. 【顺序栈算法】 设计一个算法将一个十进制正整数d转换为相应的二进制数。
解： 将十进制正整数转换成二进制数通常采用除2取余数法。在转换过程中，二进制数是按照从低位到高位的次序得到的，这和通常的从高位到低位输出二进制的次序相反。为此设计一个栈st，用于暂时存放每次得到的余数，当转换过程结束时，退栈所有元素便得到从高位到低位的二进制数。图3.5所示为十进制数12转换为二进制数1100的过程。
图3.5整数12转换为二进制数的过程
对应的算法如下：
#include "SqStack.cpp"//包含顺序栈的定义及运算函数
void trans(int d,char b［］)//b用于存放d转换成的二进制数串
{char e;
SqStack *st;
InitStack(st);
int i=0;
while (d!=0)
{e= d%2;//求余数并转换为字符
Push(st,e);
d/=2;//继续求更高位
}
while (!StackEmpty(st))
{Pop(st,e);//出栈元素e
b［i］=e;//将e存放在数组b中
i ;
}
b［i］=＼0;//加入字符串结束标志
DestroyStack(st);//销毁栈
}
2. 【顺序栈算法】 设计一个算法，利用顺序栈的基本运算从栈顶到栈底输出栈中的所有元素，要求仍保持栈中元素不变。解： 先建立并初始化一个临时栈tmpst。退栈st中的所有元素，输出这些元素并进栈到tmpst中，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。注意本题要求只能使用栈的基本运算来完成，不能直接用st->data［i］输出栈中的元素。对应的算法如下：
#include "SqStack.cpp"//包含顺序栈的定义及运算函数
void DispStack(SqStack *st)
{ElemType x;
SqStack *tmpst;//定义临时栈
InitStack(tmpst);//初始化临时栈
while (!StackEmpty(st))//临时栈tmpst中包含st栈中的逆转元素
{Pop(st,x);
printf("%d ",x);
Push(tmpst,x);
}
printf("＼n");
while (!StackEmpty(tmpst))//恢复st栈中原来的内容
{Pop(tmpst,x);
Push(st,x);
}
DestroyStack(tmpst);
}
3. 【顺序栈算法】 设计一个算法，利用顺序栈的基本运算求栈中从栈顶到栈底的第k个元素，要求仍保持栈中元素不变。解： 先建立并初始化一个临时栈tmpst。退栈st中的所有元素x，并用i累计元素个数，当i==k时置e=x，并将所有元素进栈到tmpst中，然后将临时栈tmpst中的元素逐一出栈并进栈到st中，这样恢复st栈中原来的元素。如果栈中没有第k个元素，返回假； 否则返回真，并通过引用型参数e保存第k个元素。注意本题要求只能使用栈的基本运算来完成，不能直接用st->data［i］求第k个栈中元素。对应的算法如下：
#include "SqStack.cpp"//包含顺序栈的定义及运算函数
bool Findk(SqStack *st,int k,ElemType &e)
{int i=0;
bool flag=false;
ElemType x;
SqStack *tmpst;//定义临时栈
InitStack(tmpst);//初始化临时栈
while (!StackEmpty(st))//临时栈tmpst中包含st栈中的逆转元素
{i ;
Pop(st,x);
if (i==k)
{e=x;
flag=true;
}
Push(tmpst,x);
}
while (!StackEmpty(tmpst))//恢复st栈中原来的内容
{Pop(tmpst,x);
Push(st,x);
}
DestroyStack(tmpst);
return flag;
}
4. 【顺序栈算法】 有abcde共n(n=5)个字符，通过一个栈可以产生多种出栈序列，设计一个算法判断序列str是否为一个合适的出栈序列，并给出操作过程，要求用相关数据进行测试。解： 先建立一个字符顺序栈st，将进栈序列abcde
存放到字符数组A中。用i、j分别扫描数组A和str，它们的初始值均为0。当数组A和str都没有扫描完时循环： 比较栈顶元素e和str［j］，若两者不相同，则将A［i］进栈，i加1； 若两者相同，则出栈栈顶元素e，j加1。上述循环结束后退栈所有元素。如果序列str是一个合适的出栈序列，必有j==n，否则str不是一个合适的出栈序列。对应的算法如下：
#include "SqStack.cpp"//包含顺序栈的定义及运算函数
bool isSerial(char str［］,int n)
{int i,j;
char A［MaxSize］,e;
SqStack *st;//建立一个顺序栈
InitStack(st);
for (i=0;i
A［i］=a i;//将abcde放入数组A中
i=0;j=0;
while (i
{Push(st,A［i］);
printf("元素%c进栈＼n",A［i］);
i ;
}
else
{Pop(st,e);
printf("元素%c出栈＼n",e);
j ;
}
}
while (!StackEmpty(st) && GetTop(st,e) && e==str［j］)
{Pop(st,e);
printf("元素%c出栈＼n",e);
j ;
}
DestroyStack(st);
if (j==n) return true;//是出栈序列时返回true
else return false;//不是出栈序列时返回false
}
void Disp(char str［］,int n)//输出str
{int i;
for (i=0;i
printf("%c ",str［i］);
}
int main()
{int n=5;
char str［］="acbed";
Disp(str,n); printf("的操作序列:＼n");
if (isSerial(str,n))
{Disp(str,n);
printf("是合适的出栈序列＼n");
}
else
{Disp(str,n);
printf("不是合适的出栈序列＼n");
}
return 1;
}
本程序的执行结果如下：
acbed的操作系列:
元素a进栈
元素a出栈
元素b进栈
元素c进栈
元素c出栈
元素b出栈
元素d进栈
元素e进栈
元素e出栈
元素d出栈
acbed是合适的出栈序列
5. 【共享栈算法】 用一个一维数组S(设大小为MaxSize)作为两个栈的共享空间，说明共享方法，以及栈满、栈空的判断条件，并用C/C 语言设计公用的初始化栈运算InitStack1(st)、判栈空运算StackEmpty1(st，i)、进栈运算Push1(st，i，x)和出栈运算Pop1(st，i，x)，其中i为1或2，用于表示栈号，x为进栈或出栈元素。解： 设用一维数组S［MaxSize］作为两个栈S1和S2的共享空间，整型变量top1、top2分别作为两个栈的栈顶指针，并约定栈顶指针指向当前元素的下一个位置。S1的栈底位置设在S［0］，S2的栈底位置设在S［MaxSize-1］，如图3.6所示。
图3.6共享栈示意图
栈S1空的条件是top1==-1，栈S1满的条件是top1==top2-1； 栈S2空的条件是top2==MaxSize，栈S2满的条件是top2==top1 1。归纳起来，栈S1和S2满的条件都是top1==top2-1。元素x进栈S1的算法是Push1(&st，1，x)，当不满时，执行st.top1 ，st.S［st.top1］=x； 元素x进栈S2的算法是Push1(&st，2，x)，当不满时，执行st.top2--，st.S［st.top2］=x。元素x退栈S1的算法是Pop1(&st，1，&x)，当不空时，执行x=st.S［st.top1］，st.top1--； 元素x退栈S2的算法是Pop1(&st，2，&x)，当不空时，执行x=st.S［st.top2］，st.top2 。共享栈的类型定义和相关运算算法如下：
#include
#define MaxSize 100
typedef char ElemType;
typedef struct
{ElemType S［MaxSize］;//存放共享栈中的元素
int top1,top2;//两个栈顶指针
} StackType;//声明共享栈类型
//-----栈初始化算法------
void InitStack1(StackType &st)
{st.top1=-1;
st.top2=MaxSize;
}
//-----判栈空算法： i=1:栈1，i=2:栈2------
bool StackEmpty1(StackType st,int i)
{if (i==1)
return(st.top1==-1);
else //i=2
return(st.top2==MaxSize);
}
//-----进栈算法： //i=1:栈1，i=2:栈2------
bool Push1(StackType &st,int i,ElemType x)
{if (st.top1==st.top2-1)//栈满
return false;
if (i==1)//x进栈S1
{st.top1 ;
st.S［st.top1］=x;
}
else if (i==2)//x进栈S2
{st.top2--;
st.S［st.top2］=x;
}
else//参数i错误返回false
return false;
return true;//操作成功返回true
}
//-----出栈算法： i=1:栈1，i=2:栈2------
bool Pop1(StackType &st,int i,ElemType &x)
{if (i==1)//S1出栈
{if (st.top1==-1)//S1栈空
return false;
else//出栈S1的元素
{x=st.S［st.top1］;
st.top1--;
}
}
else if (i==2)//S2出栈
{if (st.top2==MaxSize)//S2栈空
return false;
else//出栈S2的元素
{x=st.S［st.top2］;
st.top2 ;
}
}
else//参数i错误返回false
return false;
return true;//操作成功返回true
}
6. 【环形队列算法】 设计一个算法，利用环形队列的基本运算返回指定队列中的队尾元素，要求算法的空间复杂度为O(1)。解： 由于算法要求空间复杂度为O(1)，所以不能使用临时队列。先求出队列qu中的元素个数m。循环m次，出队一个元素x，再将元素x进队，最后的x即为队尾元素。对应的算法如下：
#include "SqQueue.cpp"//包含顺序队的类型定义和运算函数
ElemType Last(SqQueue *qu)
{ElemType x;
int i,m=(qu->rear-qu->front MaxSize)%MaxSize;
for (i=1;i<=m;i )
{deQueue(qu,x);//出队元素x
enQueue(qu,x);//将元素x进队
}
return x;
}
7. 【环形队列算法】 对于环形队列，利用队列的基本运算设计删除队列中从队头开始的第k个元素的算法。解： 先求出队列qu中的元素个数count，若k小于0或大于count，返回假。出队所有元素，并记录元素的序号i，当i=k时对应的元素只出不进，否则将出队的元素又进队。对应的算法如下：
#include "SqQueue.cpp" //包含顺序队的类型定义和运算函数
bool Delk(SqQueue *&qu,int k)
{ElemType e;
int i,count=(qu->rear-qu->front MaxSize)%MaxSize;
if (k<=0 ‖ k>count)
return false;
for (i=1;i<=count;i )
{deQueue(qu,e);//出队元素e
if (i!=k)//第k个元素只出不进
enQueue(qu,e);//其他元素出队后又进队
}
return true;
}
说明： 在设计本题算法时不能通过移动元素的方式直接对数组data删除第k个元素，这样是把顺序队看成一个顺序表，没有作为一个队列看待。8. 【环形队列算法】 对于环形队列来说，如果知道队尾元素的位置和队列中元素的个数，则队头元素所在的位置显然是可以计算的。也就是说，可以用队列中元素的个数代替队头指针。编写出这种环形顺序队列的初始化、进队、出队和判空算法。解： 当已知队头元素的位置rear和队列中元素的个数count后，队空的条件为count==0； 队满的条件为count==MaxSize； 计算队头位置为front=(rear-count MaxSize)%MaxSize。对应的算法如下：
typedef struct
{ElemType data［MaxSize］;
int rear;//队尾指针
int count;//队列中元素的个数
}QuType;//队列类型
void InitQu(QuType *&q)//队列的初始化运算
{q=(QuType *)malloc(sizeof(QuType));
q->rear=0;
q->count=0;
}
bool EnQu(QuType *&q,ElemType x)//进队运算
{if (q->count==MaxSize)//队满上溢出
return false;
else
{q->rear=(q->rear 1)%MaxSize;
q->data［q->rear］=x;
q->count ;
return true;
}
}
bool DeQu(QuType *&q,ElemType &x)//出队运算
{int front;//局部变量
if (q->count==0)//队空下溢出
return false;
else
{front=(q->rear-q->count MaxSize)%MaxSize;
front=(front 1)%MaxSize;//队头位置进1
x=q->data［front］;
q->count--;
return true;
}
}
bool QuEmpty(QuType *q)//判空运算
{
return(q->count==0);
}
9. 【环形队列算法】 设计一个环形队列，用front和rear分别作为队头和队尾指针，另外用一个标志tag标识队列可能空(0)或可能满(1)，这样加上front==rear可以作为队空或队满的条件，要求设计队列的相关基本运算算法。解： 设计的队列类型如下：
typedef struct
{ElemType data［MaxSize］;
int front,rear;//队头和队尾指针
int tag;//为0表示队可能空,为1时表示队可能满
} QueueType;
初始时tag=0，front=rear=0，成功的进队操作后tag=1(任何进队操作后队列可能满，但不一定满，任何进队操作后队列不可能空)，成功的出队操作后tag=0(任何出队操作后队列可能空，但不一定空，任何出队操作后队列不可能满)，因此这样的队列的4要素如下。
① 队空条件： qu.front==qu.rear && qu.tag==0；② 队满条件： qu.front==qu.rear && qu.tag==1；③ 元素x进队： qu.rear=(qu.rear 1)%MaxSize; qu.data［qu.rear］=x; qu.tag=1;④ 元素x出队： qu.front=(qu.front 1)%MaxSize; x=qu.data［qu.front］; qu.tag=0。对应的算法如下：
void InitQueue1(QueueType &qu)//初始化队列算法
{qu.front=qu.rear=0;
qu.tag=0;//为0表示队空可能为空
}
bool QueueEmpty1(QueueType qu)//判队空算法
{
return(qu.front==qu.rear && qu.tag==0);
}
bool QueueFull1(QueueType qu)//判队满算法
{
return(qu.tag==1 && qu.front==qu.rear);
}
bool EnQueue1(QueueType &qu,ElemType x)//进队算法
{if (QueueFull1(qu)==1)//队满
return false;
qu.rear=(qu.rear 1)%MaxSize;
qu.data［qu.rear］=x;
qu.tag=1;//至少有一个元素,可能满
return true;
}
bool DeQueue1(QueueType &qu,ElemType &x)//出队算法
{if (QueueEmpty1(qu)==1)//队空
return false;
qu.front=(qu.front 1)%MaxSize;
x=qu.data［qu.front］;
qu.tag=0;//出队一个元素,可能空
return true;
}
10. 【双端队列应用】 假设有一个整型数组存放n个学生的分数，将分数分为3个等级，分数高于或等于90的为A等，分数低于60的为C等，其他为B等。要求采用双端队列，先输出A等分数，再输出C等分数，最后输出B等分数。解： 设计双端队列的从队头出队算法deQueue1、从队头进队算法enQueue1和从队尾进队算法enQueue2。对于含有n个分数的数组a，扫描所有元素a［i］，若a［i］为A等，直接输出； 若为B等，将其从队尾进队； 若为C等，将其从队头进队。最后从队头出队并输出所有的元素。对应的算法如下：
#include "SqQueue.cpp"//包含顺序队的类型定义和运算函数
bool deQueue1(SqQueue *&q,ElemType &e)//从队头出队算法
{if (q->front==q->rear)//队空下溢出
return false;
q->front=(q->front 1)%MaxSize;//修改队头指针
e=q->data［q->front］;
return true;
}
bool enQueue1(SqQueue *&q,ElemType e)//从队头进队算法
{if ((q->rear 1)%MaxSize==q->front)//队满
return false;
q->data［q->front］=e;//e元素进队
q->front=(q->front-1 MaxSize)%MaxSize; //修改队头指针
return true;
}
bool enQueue2(SqQueue *&q,ElemType e)//从队尾进队算法
{if ((q->rear 1)%MaxSize==q->front)//队满上溢出
return false;
q->rear=(q->rear 1)%MaxSize;//修改队尾指针
q->data［q->rear］=e;//e元素进队
return true;
}
void fun(int a［］,int n)
{int i;
ElemType e;
SqQueue *qu;
InitQueue(qu);
for (i=0;i
{if (a［i］>=90)
printf("%d ",a［i］);
else if (a［i］>=60)
enQueue2(qu,a［i］);//从队尾进队
else
enQueue1(qu,a［i］);//从队头进队
}
while (!QueueEmpty(qu))
{deQueue1(qu,e);//从队头出队
printf("%d ",e);
}
printf("＼n");
DestroyQueue(qu);
}
11. 【顺序栈和顺序队算法】 用于列车编组的铁路转轨网络是一种栈结构，如图3.7所示，其中右边轨道是输入端、左边轨道是输出端。当右边轨道上的车皮编号顺序为1、2、3、4时，如果执行操作进栈、进栈、出栈、进栈、进栈、出栈、出栈、出栈，则在左边轨道上的车皮编号顺序为2、4、3、1。
图3.7铁路转轨网络
设计一个算法，输入n个整数，表示右边轨道上n节车皮的编号，用上述转轨栈对这些车皮重新编排，使得编号为奇数的车皮都排在编号为偶数的车皮的前面。解： 将转轨栈看成一个栈，将左边轨道看成是一个队列。从键盘逐个输入表示右边轨道上车皮编号的整数，根据其奇偶性做以下处理： 若是奇数，则将其插入到表示左边轨道的顺序队列的队尾； 若是偶数，则将其插入到表示转轨栈的顺序栈的栈顶。当n个整数都检测完之后，这些整数已全部进入队列或栈中。此时，首先按先进先出的顺序输出队列中的元素，然后再按后进先出的顺序输出栈中的元素。算法中直接使用两个数组st和qu分别存放栈和队列中的元素。对应的算法如下：
#include
#define MaxSize 100
void fun1()
{int i,n,x;
int st［MaxSize］,top=-1;//顺序栈和栈顶指针
int qu［MaxSize］,front=0,rear=0;//队列和队指针
printf("n:");
scanf("%d",&n);
for (i=0;i
{printf("第%d个车皮编号:",i 1);
scanf("%d",&x);
if (x%2==1)//编号为奇数,则进队列
{qu［rear］=x;
rear ;
printf("%d进队＼n",x);
}
else//编号为偶数,则进栈
{top ;
st［top］=x;
printf("%d进栈＼n",x);
}
}
printf("出轨操作:＼n");
while (front!=rear)//队列中的所有元素出队
{printf("%d出队 ",qu［front］);
front ;
}
while (top>=0)//栈中的所有元素出栈
{printf("%d出栈 ",st［top］);
top--;
}
printf("＼n");
}
int main()
{fun1();
return 1;
}
本程序的一次求解结果如下：
n:4↙
第1个车皮编号:4↙4进栈
第2个车皮编号:1↙1进队
第3个车皮编号:3↙3进队
第4个车皮编号:2↙2进栈
出轨操作：
1出队3出队2出栈4出栈
数据结构教程（第5版）学习指导 pdf下载声明
本pdf资料下载仅供个人学习和研究使用，不能用于商业用途，请在下载后24小时内删除。如果喜欢，请购买正版
