3.2 强化习题详解
【基础知识题】
1若按教科书3.1.1节中图3.1（b）所示的铁道进行车厢调度（注意：两侧铁道均为单向行驶道），则请回答：
（1）如果进栈的车厢序列为123，则可能得到的出站车厢序列是什么？
（2）如果进栈的车厢序列为123456，则能否得到435612和135426的出站序列，并请说明为什么不能得到或者如何得到（即写出以‘S’表示进栈和以‘X’表示出栈的栈操作序列）。
答：（1）123，132，213，231，321。
（2）①可以得到135426的出栈序列，方法为：
1S，1X，输出为1；
2S，3S，3X，输出为1 3；
4S，5S，5X，输出为1 3 5；
4X，输出为1 3 5 4；
2X，输出为1 3 5 4 2；
6S，6X，输出为1 3 5 4 2 6。
②不能得到435612的出栈序列。因为4356出栈说明12已经在栈中，而1为栈底元素，2为栈顶元素，1不可能先于2出栈。
2简述栈和线性表的差别。
答：含有n个相同数据类型的数据元素的有限序列称为线性表，可以进行随机插入和删除操作；栈是限定仅在表尾进行插入或删除操作的线性表，具有后进先出的特点。
栈是特殊的线性表，其操作是线性表基本操作的子集。
3写出下列程序段的输出结果（栈的元素类型SElemType为char）。
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(!StackEmpty(S))
{
Pop(S,y);
printf(y);
}
printf(x);
}
答：根据进栈和出栈的顺序依次写出字符，答案为stack。
4简述以下算法的功能（栈的元素类型SElemType为int）。
（1）
status algo1(Stack S)
{
//初始时，S中已有255个元素
int i,n,A[255];
n=0;
while(!StackEmpty(S))
{
n++;
Pop(S,A[n]);
}
for(i=1;i<=n;i++)
Push(S,A[i]);
}
（2）
status algo2(Stack S,int e)
{
Stack T;
int d;
InitStack(T);
while(!StackEmpty(S))
{
Pop(S,d);
if(d!=e)Push(T,d);
}
while(!StackEmpty(T))
{
Pop(T,d);
Push(S,d);
}
}
答：（1）实现了栈中的数据元素逆置（栈具有后进先出的特点，元素依次出栈后再次入栈，会实现逆序）。
（2）利用栈T辅助查找栈中为e的元素，将其从栈中清除（先将元素全部出栈，如果元素不是e，则再次进栈，从而可以将栈中为e的元素清除）。
5假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
答：一般准则：任意一个由S和X组成的前n个序列中，S的数目一定大于或者等于X的数目，且整个序列中S和X的数目相等。
下面证明两个不同的合法序列不可能得到相同的输出元素序列：
设两个合法序列
T1＝S，…，X，…，S
T2＝S，…，X，…，X
分别是对存储在栈A和栈B中的元素进行操作的序列，设前n个序列相同，从第n＋1个操作开始序列不相同，由于前n个操作序列相同，则栈中已存元素个数相同。现假设当前栈顶元素均为a，不妨碍设第n＋1个操作分别为：T1向栈A压入b元素，T2从栈B退栈a元素，则T1操作得到的局部序列应为…，b，a，…，而T2操作得到的局部序列应为…，a，b，…，显然证得两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
6试证明：若借助栈由输入序列12…n得到的输出序列为P1P2P3（它是输入序列的一个排列），则在输出序列中不可能出现这样的情形：存在着i＜j＜k使Pj＜Pk＜Pi。
答：因为输入序列是从小到大排列的，所以若Pj＜Pk＜Pi，则可以理解为通过输入序列PjPkPi可以得到输出序列PiPjPk，设Pj＝1，Pk＝2，Pi＝3，由栈的后进先出特点可知，通过输入序列123是无法得到312的。所以不可能存在着i＜j＜k使Pj＜Pk＜Pi。
7按照四则运算加、减、乘、除和幂运算（↑）优先关系的惯例，并仿照教科书3.2节例3-2的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：A－B×C/D＋E↑F。
答：根据题意，其变化过程如表3-2所示。
表3-2 算术表达式求值变化过程表
8试推导求解n阶Hanoi塔问题至少要执行的move操作的次数。
答：设至少要执行M（n）次move操作，由该问题的递归方程
可得
M（n）＝2M（n－1）＋1＝2（2M（n－2）＋1）＋1＝…＝2n－1M（1）＋2n－2＋…＋21＋20
其中M（1）＝1；解得M（n）＝2n－1。
【算法设计题】
9试将下列递推过程改写为递归过程。
void ditui(int n)
{
int i;
i = n;
while(i>1)
printf(i--);
}
答：
void ditui(int j)
{
if(j>1)
{
printf(j);
ditui(j-1);
}
return;
}
10试将下列递归过程改写为非递归过程。
void test(int &sum)
{
int x;
scanf("%d", &x);
if(x==0)
sum=0;
else
{
test(sum);
sum+=x;
}
printf("%d\n", sum);
}
答：当参数sum传入20时，输入和输出结果如下：
输入：1 2 3 4 5 6 0
输出：0 26 25 24 23 22 21
由输出结果可知，输出＝输入＋sum，且输出结果与输入相逆，需要使用栈，其非递归程序如下：
void test(int &sum)
{
Stack s;
InitStack(s);
int x;
do
{
scanf("%d",&x);
Push(s,x);
}while(x>0);
while(!StackEmpty(s))
{
Pop(s,x);
sum+=x;
printf(sum);
}
DestoryStack(s);
}
11简述队列和栈这两种数据类型的相同点和差异处。
答：相同点：栈和队列都是操作受限的线性表。
不同点：
①栈是一种后进先出的线性表，且只允许在栈顶进行插入和删除操作。
②队列是一种先进先出的线性表，且只允许在队头进行删除操作，在队尾进行插入操作。
12写出以下程序段的输出结果（队列中的元素类型QElemType为char）。
void main()
{
Queue Q;
InitQueue(Q);
char x='e',y='c';
EnQueue(Q,'h');
EnQueue(Q,'r');
EnQueue(Q,y);
DeQueue(Q,x);
EnQueue(Q,x);
DeQueue(Q,x);
EnQueue(Q,'a');
While(!QueueEmpty(Q))
{
DeQueue(Q,y);
printf(y);
}
printf(x);
}
答：char（根据队列先进先出的操作特点，按照入队和出队顺序依次写出元素即可。）
13简述以下算法的功能（栈和队列的元素类型均为int）。
void algo3(Queue &Q)
{
Stack S;
int d;
InitStack(S);
while(!QueueEmpty(Q))
{
DeQueue(Q,d);
Push(S,d);
}
while(!StackEmpty(S))
{
Pop(S,d);
EnQueue(Q,d);
}
}
答：该算法充分利用栈后进先出的特点和队列先进先出的特点，功能是借助栈，将队列中的数据元素进行逆置。
14若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
答：（1）4132
（2）4213
（3）4231
【注意】特殊栈和队列在考研中时常出现，重点是会模拟其元素进出的过程。
15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参）或函数设计这些操作算法各有什么优缺点。
答：
typedef struct
{
Elemtype *base[2]; //表示初始栈顶位置
Elemtype *top[2]; //表示实际栈顶位置
}BDStacktype; //双向栈类型
Status inistack(BDStacktype &tws,int m) //初始化一个大小为m的双向栈tws
{
tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype));
tws.base[1]=tws.base[0]+m;
tws.top[0]=tws.base[0];
tws.top[1]=tws.base[1];
return OK;
} //inistack
Status push(BDStacktype &tws,int i,Elemtype x) //x入栈，i＝0表示低端栈，i＝1表示高端栈
{
if(tws.top[0]>tws.top[1])
return OVERFLOW; //注意此时的栈满条件
if(i==0)
*tws.top[0]++=x; //x入栈，进入低端栈
else if(i==1)
*tws.top[1]--=x; //x入栈，进入高端栈
else
return ERROR;
return OK;
} //push
Status pop(BDStacktype &tws,int i,Elemtype &x) //x出栈，i＝0表示低端栈，i＝1表示高端栈
{
if(i==0)
{
if(tws.top[0]==tws.base[0])
return Stack_Empty; //出栈时的栈空条件
x=*--tws.top[0]; //x从低端栈出栈
}
else if(i==1)
{
if(tws.top[1]==tws.base[1])
return Stack_Empty;
x=*++tws.top[1]; //x从高端栈出栈
}
else
return ERROR;
return OK;
} //pop
16假设如题1所示火车调度站的入口处有n节硬席或软席车厢（分别以H和S表示）等待调度，试编写算法，输出对这n节车厢进行调度的操作（即入栈或出栈操作）序列，以使所有的软席车厢都被调整到硬席车厢之前。
答：
void Train_arrange(char *train) //这里用字符串train表示火车，H表示硬席，S表示软席。
{
q=train;
p=train;
InitStack(s);
while(*p)
{
if(*p=='H')
push(s,*p); //把'H'存入栈中
else
*(q++)=*p; //把'S'调到前部，即软席车厢调整到硬席车厢之前
p++;
}
while(!StackEmpty(s))
{
pop(s,c);
*(q++)=c; //把'H'接在后部，即硬席车厢直接顺序接到后面
}
} //Train_arrange
17试写一个算法，识别一次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含字符'&'，且序列2是序列1的逆序列。例如，“a+b&b+a”是属该模式的字符序列，而“1+3&3-1”则不是。
答：
int IsReverse() //判断输入的字符串中'&'前和'&'后部分是否为逆串，是则返回1，否则返回0
{
InitStack(s);
while((e=getchar())!='&')
{
if(e=='@')
return 0; //不允许在'&'之前出现'@'
push(s,e);
}
while((e=getchar())!='@') //读入&字符后面的序列
{
if(StackEmpty(s))
return 0;
pop(s,c);
if(e!=c)
return 0; //弹出栈顶元素，若栈顶元素与所读字符不同，说明不是逆序列
}
if(!StackEmpty(s))
return 0; //最后添加判断，若栈中还有元素，说明不是逆序列，考虑情况1234&432@
return 1; //返回1，表明是符合模式的字符序列
} //IsReverse
18试写一个判别表达式中开、闭括号是否配对出现的算法。
答：（1）使用栈：
bool BracketCorrespondency(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i])
{
switch(a[i])
{
case '(':
Push(s,a[i]);
break; //遇到左小括号，则入栈
case '[':
Push(s,a[i]);
break; //遇到左中括号，则入栈
case ')': //遇到 ) 或 ] 时，取出栈顶元素进行匹配，不匹配则说明有误
GetTop(s,x);
if(x=='(')
Pop(s,x);
else
return FALSE;
break;
case ']':
GetTop(s,x);
if(x=='[')
Pop(s,x);
else
return FALSE;
break;
}
i++;
}
return true;
}
（2）不使用栈：
Status Bracket_Test(char *str) //判别表达式中小括号是否匹配
{
count=0;
for(p=str;*p;p++)
{
if(*p= ='(')
count++;
else if(*p= =')')
count--;
if(count<0) //count<0，说明“）”的个数多于“（”的个数，不可能出现“）”数目超过“（”数目的情况
return ERROR;
}
if(count)
return ERROR; // count>0，说明“（”的个数多于“）”的个数，表达式中小括号不匹配
return OK;
} //Bracket_Test
【注意】在（2）不使用栈的算法中，如果要判断[]的匹配，方法和（）的匹配一样。
19假设一个算术表达式中可以包含三种括号：圆括号“（”和“）”，方括号“[”和“]”和花括号“{”和“}”，且这三种括号可按任意的次序嵌套使用（如：…[…{…}…[…]…]…[…]…（…）…）。编写判别给定表达式中所含括号是否正确配对出现的算法（已知表达式已存入数据元素为字符的顺序表中）。
答：
Status AllBrackets_Test(char *str) //判别表达式中三种括号是否匹配
{
InitStack(s);
for(p=str;*p;p++)
{
if(*p=='(' || *p=='[' || *p=='{')
push(s,*p);
else if(*p==')'||*p==']'||*p=='}')
{
if(StackEmpty(s))
return ERROR; //此时栈空说明括号不匹配
pop(s,c);
if(*p==')'&&c!= '(')
return ERROR;
if(*p==']'&&c!= '[')
return ERROR;
if(*p=='}'&&c!= '{')
return ERROR; //必须与当前栈顶括号匹配
}
} //for
if(!StackEmpty(s))
return ERROR; //栈中元素有剩余，说明括号没有完全匹配
return OK;
} //AllBrackets_Test
【注意】在括号匹配中，都需要满足两个条件：一是括号必须成对出现；二是括号必须邻接匹配（即在所给表达式中，不能出现邻接的括号类似于“(”和“}”，这是不满足要求的）。
20假设以二维数组g（1…m，1…n）表示一个图像区域，g[i，j]表示该区域中点（i，j）所具颜色，其值为从0到k的整数。编写算法置换点（i0，j0）所在区域的颜色。约定和（i0，j0）同色的上、下、左、右的邻接点为同色区域的点。
答：
typedef struct
{
int x;
int y;
}coordinate;
void Repaint_Color(int g[m][n],int i,int j,int color) //把点(i,j)相邻区域的颜色置换为color
{
old=g[i][j];
InitQueue(Q);
EnQueue(Q,{i,j});
while(!QueueEmpty(Q))
{
DeQueue(Q,a);
x=a.x; y=a.y;
if(x>1)
if(g[x-1][y]==old)
{
g[x-1][y]=color; //将左邻点颜色置换为color
EnQueue(Q,{x-1,y}); //修改左邻点的颜色
}
if(y>1)
if(g[x][y-1]==old)
{
g[x][y-1]=color; //将上邻点颜色置换为color
EnQueue(Q,{x,y-1}); //修改上邻点的颜色
}
if(x<m)
if(g[x+1][y]==old)
{
g[x+1][y]=color; //将右邻点颜色置换为color
EnQueue(Q,{x+1,y}); //修改右邻点的颜色
}
if(y<n)
if(g[x][y+1]==old)
{
g[x][y+1]=color; //将下邻点颜色置换为color
EnQueue(Q,{x,y+1}); //修改下邻点的颜色
}
} //while
} //Repaint_Color
21假设表达式由单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。
答：
void NiBoLan(char *str,char *new) //把中缀表达式str转换成逆波兰式new，即后缀表达式
{
p=str;
q=new; //为方便起见，设str的两端都加上了优先级最低的特殊符号
InitStack(s); //s为运算符栈
while(*p)
{
if(*p是字母)
*q++=*p; //直接输出
else
{
c=gettop(s);
if(*p优先级比c高)
push(s,*p); //将比栈顶运算符优先级高的压入运算符栈，即栈顶的运算符优先级最高
else
{
while(gettop(s)优先级不比*p低)
{
pop(s,c);
*(q++)=c;
} //while
push(s,*p); //运算符在栈内遵循越往栈顶优先级越高的原则
} //else
} //else
p++;
} //while
} //NiBoLan
22如题21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。
答：
int GetValue_NiBoLan(char *str) //对逆波兰式求值
{
p=str;
InitStack(s); //s为操作数栈
while(*p)
{
if(*p是数)
push(s,*p);
else
{
pop(s,a);
pop(s,b); //从栈顶弹出两个操作数
r=compute(b,*p,a); //假设compute为执行双目运算的过程
push(s,r); //将运算结果作为新的操作数压入栈顶
} //else
p++;
} //while
pop(s,r);
return r;
} //GetValue_NiBoLan
23如题21的假设条件，试写一个算法，判断给定的非空后缀表达式是否为正确的逆波兰表达式（即后缀表达式），如果是，则将它转化为波兰式。
答：
Status NiBoLan_to_BoLan(char *str,stringtype &new) //把逆波兰表达式str转换为波兰式new
{
p=str;
Initstack(s); //s的元素为stringtype类型
while(*p)
{
if(*p为字母)
push(s,*p);
else
{ //每一次遇到运算符，都需要弹出两个栈顶元素（都是数字）
if(StackEmpty(s))
return ERROR;
pop(s,a);
if(StackEmpty(s))
return ERROR; //操作数不匹配
pop(s,b);
c=link(link(*p,b),a); //连接操作
push(s,c);
} //else
p++;
} //while
pop(s,new);
if(!StackEmpty(s))
return ERROR;
return OK;
} //NiBoLan_to_BoLan
【注意】本题中暂不考虑串的具体操作的实现，而将其看作一种抽象数据类型stringtype，对其可以进行连接操作：c=link(a,b)。
24试编写如下定义的递归函数的递归算法，并根据算法画出求g（5，2）时栈的变化过程。
答：
Status g(int m,int n,int &s) //求递归函数g的值s
{
if(m==0&&n≥0)
s=0;
else if(m>0&&n≥0)
s=n+g(m-1,2*n);
else
return ERROR;
return OK;
} //g
假设主函数的返回地址是0，递归函数三条语句的返回地址是1、2、3，求g（5，2）时栈的变化过程如表3-3所示。
表3-3 栈变化过程表
25试写出求递归函数F（n）的递归算法，并消除递归：
答：
Status F_recursive(int n,int &s) //递归算法
{
if(n<0)
return ERROR;
if(n==0)
s=n+1;
else
{
F_recurve(n/2,r); //递归调用本身
s=n*r;
}
return OK;
} //F_recursive
Status F_nonrecursive(int n,int s) //非递归算法，利用栈和循环
{
if(n<0)
return ERROR;
if(n==0)
s=n+1;
else
{
InitStack(s); //s的元素类型为struct {int a;int b;}
while(n!=0)
{
a=n;
b=n/2;
push(s,{a,b});
n=b;
} //while
s=1;
while(!StackEmpty(s))
{
pop(s,t);
s*=t.a;
} //while
}
return OK;
} //F_nonrecursive
26求解平方根
的迭代函数定义如下：
其中，p是A的近似平方根，e是结果允许误差。试写出相应的递归算法，并消除递归。
答：
float Sqrt_recursive(float A,float p,float e) //求平方根的递归算法
{
if(abs(p^2-A)<=e)
return p;
else
return sqrt_recurve(A,(p+A/p)/2,e);
} //Sqrt_recurve
float Sqrt_nonrecursive(float A,float p,float e) //求平方根的非递归算法
{
while(abs(p^2-A)>=e)
p=(p+A/p)/2;
return p;
} //Sqrt_nonrecu rsive
27已知Ackerman函数的定义如下：
（1）写出递归算法；
（2）写出非递归算法；
（3）根据非递归算法，画出求akm（2，1）时栈的变化过程。
答：（1）递归算法
unsigned int akm(unsigned int m,unsigned int n)
{
unsigned int g;
if(m==0)
return n+1;
else
if(n==0)
return akm(m-1,1);
else
{
g=akm(m,n-1);
return akm(m-1,g);
}
}
（2）非递归算法：
int akm1(int m,int n)
{
Stack s;
InitStack(s);
ElemType e,e1,d;
e.mval=m;
e.nval=n;
Push(s,e);
do
{
while(e.mval)
{
while(e.nval)
{
e.nval--;
Push(s,e); //元素依次进栈
}
e.mval--;
e.nval=1;
}
if(StackLength(s)>1)
{
e1.nval=e.nval;
Pop(s,e); //出栈
e.mval--;
e.nval=e1.nval+1;
}
}while(StackLength(s)!=1||e.mval!=0); //循环结束条件
return e.nval+1; //m=0时，akm(m,n)=n+1
}
（3）栈的变化过程：
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)
3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1)
4,akm(0,1) 4 0 1 akm=n+1=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)
3,akm(1,0) 6 1 0 akm=akm(m-1,1)=akm(0,1)=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2);
3,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)
2,akm(1,1) 4 1 1 g=akm(m,n-1)=akm(1,0)=2; akm=akm(m-1,g)=akm(0,2)=3; 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)
1,akm(2,0) 6 2 0 akm=akm(m-1,1)=akm(1,1)=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g)
4,akm(1,0) 6 1 0 akm=akm(0,1)
5,akm(0,1) 4 0 1 akm(0,1)=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0); akm(m-1,g)
4,akm(1,0) 6 1 0 akm=akm(0,1)=2 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2)
4,akm(0,2) 7 0 2 akm=n+1=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1); akm(m-1,g)
3,akm(1,1) 6 1 1 g=akm(1,0)=2; akm(m-1,g)=akm(0,2)=3 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3)
3,akm(0,3) 7 0 3 akm=n+1=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2); akm(m-1,g)
2,akm(1,2) 6 1 2 g=akm(1,1)=3; akm(m-1,g)=akm(0,3)=4 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4)
2,akm(0,4) 7 0 4 akm=n+1=5 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)
1,akm(1,3) 6 1 3 g=akm(1,2)=4; akm(m-1,g)=akm(0,4)=5 退栈
0,akm(2,1) 0 2 1 g=akm(2,0)=3; akm=akm(1,3)=5 退栈
akm(2,1)=5;
28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。
答：
void InitCiQueue(CiQueue &Q) //初始化循环链表表示的队列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode)); //动态创建循环链表结点
Q->next=Q; //置空
} //InitCiQueue
void EnCiQueue(CiQueue &Q,int x)
//把元素x插入循环链表表示的队列Q，Q指向队尾元素，Q->next指向头结点，Q->next->next指向队头元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;
Q->next=p; //直接把p加在Q的后面
Q=p; //修改尾指针
}
Status DeCiQueue(CiQueue &Q,int x)
//从循环链表表示的队列Q头部删除元素x
{
if(Q==Q->next)
return INFEASIBLE; //队列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p); //释放结点
return OK;
}
29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。
答：
#define MaxQSize 4
typedef int ElemType;
typedef struct
{
ElemType *base;
int front;
int rear;
Status tag;
}Queue;
Status InitQueue(Queue &q)
{
q.base=(ElemType*)malloc(MaxQSize*sizeof(ElemType));
if(!q.base)
return FALSE;
q.front=0;
q.rear=0;
q.tag=0;
return OK;
}
Status EnQueue(Queue &q,ElemType e)
{
if(q.front= =q.rear&&q.tag)
return FALSE; //队列的头指针和尾指针指向同一结点，并且队列状态为“满”，则元素不能入队
else
{
q.base[q.rear]=e;
q.rear=(q.rear+1)%MaxQSize; //循环队列计算尾指针的位置
if(q.rear= =q.front) //入队操作后如果头指针和尾指针指向同一个结点，说明队列已满
q.tag=1;
}
return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
if(q.front==q.rear&&!q.tag)
return FALSE; //队列的头指针和尾指针指向同一结点，并且队列状态为“空”，没有可出队的元素
else
{
e=q.base[q.front];
q.front=(q.front+1)%MaxQSize; //循环队列计算头指针的位置
q.tag=0; //出队操作后，队列可以继续入队
}
return OK;
} //设标志节省存储空间，但运行时间较长，不设标志则正好相反。
当循环队列容量较小而队列中每个元素占的空间较多时设置tag位能够充分利用存储空间，更有价值。
30假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。
答：设head指示循环队列中队头元素元素的位置，则有
head=((q.rear+MAXLEN)-q.length+1)%MAXLEN
其中MAXLEN为队列可用的最大空间。
队满的条件为：length==MAXLEN。
#define MaxQSize 4
typedef int ElemType;
typedef struct
{
ElemType *base;
int rear;
int length;
}Queue;
Status InitQueue(Queue &q)
{
q.base=(ElemType*)malloc(MaxQSize*sizeof(ElemType));
if(!q.base)
return FALSE;
q.rear=0;
q.length=0;
return OK;
}
Status EnQueue(Queue &q,ElemType e)
{
//入队操作，头指针与尾指针指向同一结点，队列满
if((q.rear+1)%MaxQSize==(q.rear+MaxQSize-q.length)%MaxQSize)
return FALSE;
else
{
q.base[q.rear]=e;
q.rear=(q.rear+1)%MaxQSize; //循环队列计算尾指针位置
q.length++;
}
return OK;
}
Status DeQueue(Queue &q,ElemType &e)
{
//出队操作，头指针与尾指针指向同一个结点，队列空
if((q.rear+MaxQSize-q.length)%MaxQSize==q.rear)
return FALSE;
else
{
e=q.base[(q.rear+MaxQSize-q.length)%MaxQSize]; //队头元素
q.length--;
}
return OK;
}
31假设称正读和反读都相同的字符序列为“回文”，例如，“abba”和“abcba”是回文，“abcde”和“ababab”则不是回文。试写一个算法判别读入的一个以'@'为结束符的字符序列是否是“回文”。
答：
int Palindrome_Test()
//判别输入的字符串是否回文序列，是则返回1，否则返回0
{
InitStack(S);
InitQueue(Q);
while((c=getchar())!='@') //字符串结束标志
{
Push(S,c);
EnQueue(Q,c); //同时使用栈和队列两种结构
}
while(!StackEmpty(S))
{
Pop(S,a); //出栈元素为字符串末尾的元素
DeQueue(Q,b)); //出队元素为字符串开头的元素
if(a!=b)
return ERROR;
}
return OK;
}
32试利用循环队列编写求k阶菲波那契序列中前n＋1项的算法，要求满足：fn≤max而fn＋1＞max，其中max为某个约定的常数。（注意：本题所用循环队列的容量仅为k，则在算法执行结束时，留在循环队列中的元素应是所求k阶菲波那契序列中的最后k项）
答：
void GetFib_CyQueue(int k,int n) //求k阶斐波那契序列的前n＋1项
{
InitCyQueue(Q); //其MAXSIZE设置为k
for(i=0;i<k-1;i++)
Q.base[i]=0;
Q.base[k-1]=1; //给前k项赋初值
for(i=0;i<k;i++)
printf("%d",Q.base[i]);
for(i=k;i≤n;i++)
{
m=i%k;
sum=0;
for(j=0;j<k;j++)
sum=sum+Q.base[(m+j)%k];
Q.base[m]=sum; //求第i项的值存入队列中并取代已无用的第一项
printf("%d",sum);
}
}
33在顺序存储结构上实现输出受限的双端循环队列的入列和出列（只允许队头出列）算法。设每个元素表示一个待处理的作业，元素值表示作业的预计时间。入队列采取简化的短作业优先原则，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
答：
typedef struct
{
ElemType *base;
int front;
int rear;
Status tag;
int MaxSize;
}DQueue; //定义队列的抽象数据类型
Status InitDQueue(Dqueue &q,int size)
{
q.MaxSize=size;
q.base=(ElemType*)malloc(MaxSize*sizeof(ElemType));
if(!q.base)
return FALSE; //初始化操作失败
q.front=0;
q.rear=0;
q.tag=0;
return OK;
}
Status EnDQueue(Dqueue &q,ElemType e)
{
if(q.front==q.rear&&q.tag)
return FALSE; //队列已满，无法进行入列操作
if(q.front==q.rear&&!q.tag) //空队列
{
q.base[q.rear]=e;
q.rear=(q.rear+1)%q.MaxSize;
if(q.rear==q.front)
q.tag=1;
}
else //非空非满，若一个新提交的作业的预计执行时间小于队头和队尾作业的平均时间，则插入在队头，否则插入在队尾。
{
if(e<(q.base[q.front]+q.base[(q.rear+q.MaxSize-1)%q.MaxSize])/2)
{
//从队头入队
q.front=(q.front+q.MaxSize-1)%q.MaxSize; //计算循环队列的头指针
q.base[q.front]=e;
if(q.rear==q.front)
q.tag=1; //判断队列是否已满
}
else //从队尾入队
{
q.base[q.rear]=e;
q.rear=(q.rear+1)%q.MaxSize; //计算循环队列的尾指针
if(q.rear==q.front)
q.tag=1; //判断队列是否已满
}
}
return OK;
}
Status DeDQueue(Dqueue &q,ElemType &e)
{
if(q.front==q.rear&&!q.tag)
return FALSE; //空队列，无法进行出列操作
else
{ //非空队列
e=q.base[q.front];
q.front=(q.front+1)%q.MaxSize; //计算头指针位置
q.tag=0; //设置队列不满的标志
}
return OK;
}
34假设在如教科书3.4.1节中图3.9所示的铁道转轨网的输入端有n节车厢：硬座、硬卧和软卧（分别以P，H和S表示）等待调度，要求这三种车厢在输出端铁道上的排列次序为：硬座在前，软卧在中，硬卧在后。试利用输出受限的双端队列对这n节车厢进行调度，编写算法输出调度的操作序列：分别以字符'E'和'D'表示对双端队列的头端进行入队列和出队列的操作；以字符A表示对双端队列的尾端进行入队列的操作。
答：
void Train_Rearrange(char *train)
//这里用字符串train表示火车，'P'表示硬座，'H'表示硬卧，'S'表示软卧，最终按P，S，H的顺序排列
{
char *r=train;
InitDQueue(Q);
while(*r)
{
if(*r=='P')
{
printf("E");
printf("D"); //先入列再出列，实际上等于不入队列,直接输出P车厢
}
else if(*r=='S')
{
printf("E");
EnDQueue(Q,*r,0); //0表示把S车厢从头端入队列
}
else
{
printf("A");
EnDQueue(Q,*r,1); //1表示把H车厢从尾端入队列
}
} //while
while(!DQueueEmpty(Q))
{
printf("D");
DeDQueue(Q);
} //从头端出队列的车厢必然按P，S，H的顺序排列
}