}
解：
voidtest（int&sum）{
sqstacks;
intx;
scanf（"%d",&x）;
initstack（s）;
while（x!
=0）{
*s.front++=x;
scanf（"%d",&x）;
}
sum=0;
inte;
printf（"%d",sum）;
while（s.front!
=s.base）{
e=*（--s.front）;
sum+=e;
printf（"%d",sum）;
}
}
3.15假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它
精彩文档
实用标准文案
的三个操作：
初始化
为0或1，用以分别指
）或函数设计这些操作
们的栈底分别设在数组的两个端点。
试编写实现这个双向栈tws
inistack（tws）、入栈push（tws,i,x）和出栈pop（tws,i）的算法，其中i示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为变参
算法各有什么有缺点。
解：
程序源代码：
#include
#include
#defineSTACK_INIT_SIZE100
#defineTURE1
#defineFALSE0
#defineok1
#defineerror0
#defineINFEASIBLE-1typedefintselemtype;
typedefintstatus;typedefstruct{
int*base[2];selemtype*top[2];
intstacksize;
}sqstack;
statusINITstack（sqstack*s）{
精彩文档
实用标准文案
int*p;
p=（selemtype*）malloc（STACK_INIT_SIZE*sizeof（selemtype））;
（*s）.base[0]=（*s）.top[0]=p;
（*s）.base[1]=（*s）.top[1]=p+STACK_INIT_SIZE-1;
if（!
（*s）.base[0]）exit（-2）;
if（!
（*s）.base[1]）exit（-2）;
returnok;
}
statusPush（sqstack*s,inti,selemtypee）{
if（i==0）{
if（（*s）.top[0]>=（（*s）.base[0]+（STACK_INIT_SIZE/2）-1））returnerror;
else*（*s）.top[0]++=e;
returnok;
}
if（i==1）{
if（（*s）.top[1]<=（（*s）.base[1]-（STACK_INIT_SIZE/2）+1））returnerror;
else*（*s）.top[1]--=e;
returnok;
}
returnerror;
}
statusPop（sqstack*s,inti,selemtype*e）{
精彩文档
实用标准文案
if（i==0&&（*s）.top[0]==（*s）.base[0]）returnerror;
if（i==1&&（*s）.top[1]==（*s）.base[1]）returnerror;if（i==0）{
*e=*（--（*s）.top[0]）;
returnok;
}
if（i==1）{
*e=*（--（*s）.top[1]）;
returnok;
}
}
voidmain（）
{
sqstacksta;
selemtypee;
selemtype*p;
inti;
if（INITstack（&sta））printf（"双栈已被创建\n"）;
printf（"请输入进栈端（0/1）及进栈元素：
\n"）;
scanf（"%d%d",&i,&e）;
if（Push（&sta,i,e））printf（"元素已入栈\n"）;
printf（"请输入进栈端（0/1）及进栈元素：
\n"）;
精彩文档
实用标准文案
scanf（"%d%d",&i,&e）;
if（Push（&sta,i,e））printf（"元素已入栈\n"）;
printf（"请输入进栈端（0/1）及进栈元素：
\n"）;
scanf（"%d%d",&i,&e）;
if（Push（&sta,i,e））printf（"元素已入栈\n"）;
printf（"左端栈元素：
"）;
p=sta.base[0];
while（sta.top[0]!
=p）{
printf（"%d",*p）;
p++;
}
printf（"右端栈元素：
"）;
p=sta.base[1];
while（sta.top[1]!
=p）{
printf（"%d",*p）;
p--;}
printf（"\n请输入出栈端（0/1）：
\n"）;
scanf（"%d",&i）;
if（Pop（&sta,i,&e））printf（"\n栈顶元素%d出栈\n",e）;
printf（"左端栈元素：
"）;
p=sta.base[0];
while（sta.top[0]!
=p）{
精彩文档
实用标准文案
printf（"%d",*p）;
p++;}
printf（"右端栈元素：
"）;
p=sta.base[1];
while（sta.top[1]!
=p）{
printf（"%d",*p）;
p--;
}
}
运行结果：
3.21假设表达式有单字母变量和双目四则运算符构成。
试写一个算法，将一个通常书写形式且书写正确的表达式转换为逆波兰表达式。
解：
程序源代码：
#include
精彩文档
实用标准文案
#include
#defineSIZE100
typedefcharselemtype;
typedefstruct{
selemtype*base;
selemtype*top;
intsize;
}stack;
intPrior（charc1,charc2）
{
charch[5]="#+-*/";
inti=0,j=0;
if（c1=='（'）return0;
while（ch[i]&&ch[i]!
=c1）i++;
if（i==2）i--;//加和减可认为是同级别的运算符
if（i==4）i--;//乘和除可认为是同级别的运算符
while（ch[j]&&ch[j]!
=c2）j++;
if（j==2）j--;
if（j==4）j--;
if（i>j）return1;
elsereturn0;
}
精彩文档
实用标准文案
voidmain（）{
stacksta;
charch=0,ct;
sta.base=（selemtype*）malloc（SIZE*sizeof（selemtype））;
if（!
sta.base）exit（0）;
sta.top=sta.base;
sta.size=0;
*sta.top++='#';
printf（"pleaseentertheexpression:
\n"）;
while（ch!
='#'&&*sta.base=='#'）{
ch=getchar（）;
if（'a'<=ch&&ch<='z'）printf（"%c",ch）;
else
if（ch=='#'）{
ct=*（--sta.top）;
while（ct!
='#'）
{printf（"%c",ct）;
ct=*（--sta.top）;}
--sta.top;
}
else
if（ch=='（'）*sta.top++=ch;
精彩文档
实用标准文案
else
if（ch=='）'）{
ct=*（--sta.top）;
while（ct!
='（'）
{printf（"%c",ct）;
ct=*（--sta.top）;
}
}
else{
ct=*（sta.top-1）;
if（Prior（ct,ch）==0）*sta.top++=ch;
else{
ct=*（--sta.top）;
while（Prior（ct,ch））
{printf（"%c",ct）;
ct=*（--sta.top）;}
*（++sta.top）=ch;
++sta.top;
}
}}}
运行结果：
精彩文档
实用标准文案
3.22如题3.21的假设条件，试写一个算法，对以逆波兰式表示的表达式求值。
解：
程序源代码：
#include
#include
#definemax_size_stack100
#defineincre10
#defineok1
#defineerror-100
typedefintelemtype2;
typedefintstatus;
typedefstruct{
elemtype2*top;
elemtype2*base;
intsize;
}stack2;
statusinitstack2（stack2&da）{da.base=（elemtype2*）malloc（max_size_stack*sizeof（elemtype2））;if（!
da.base）cout<<"操作失败，程序执行无效!
!
!
!
!
!
"<精彩文档
实用标准文案
da.size=max_size_stack;
returnok;
}
statuspop2（stack2&da,elemtype2&e）{
if（da.base==da.top）returnerror;
e=*（--da.top）;
returnok;
}
statuspush2（stack2&da,elemtype2e）{if（da.top-da.base>=da.size）{
da.base=（elemtype2*）realloc（da.base,（da.size+incre）*sizeof（elemtype2））;
!
!
!
!
!
!
"<if（!
da.base）cout<<"操作失败，程序执行无效
da.top=da.base+da.size;
da.size+=incre;
}
*da.top++=e;
returnok;
}
intcoun（elemtype2e1,elemtype2e2,charcch）{switch（cch）{case'+':
returne1+e2;
精彩文档
实用标准文案
case'-':
returne1-e2;
case'*':
returne1*e2;
case'/':
if（e2==0）returnerror;elsereturne1/e2;
case'#':
returnok;break;
default:
returnerror;
}
}
voidmain（）{
charcch;
inti,count=0,e1,e2;
stack2da;
initstack2（da）;
cout<<"请输入表达式的逆波兰式：
（#表结束）"<for（cch='1',i=0;cch!
='#'&&i<20;i++）{
cin>>cch;
if（cch!
='+'&&cch!
='-'&&cch!
='*'&&cch!
='/'&&cch!
='#'）
push2（da,cch-48）;
elseif（cch!
='#'）{
pop2（da,e2）;pop2（da,e1）;
if（coun（e1,e2,cch）==-100）{
cout<<"表达是不合法：
"<cout<<"操作失败，程序执行无效!
!
!
!
!
!
"<精彩文档
实用标准文案
else
push2（da,coun（e1,e2,cch））;
else{
pop2（da,e1）;
cout<<"表达式的值为：
"<}
}
}
运行结果：
3.14若以1234作为双端队列的输入序列，试分别求出满足以下条件的输出序列：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列。
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列。
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列。
解：
1,2,3,4
输入受限
1
2
3
4
精彩文档
实用标准文案
4和2不可相连
1,2,3,4
输出受限
1
2
1和2不可分开
4在1,3或2,3之间
由上分析可知：
输出受限不可得到：
1243，3412，1342，1432，3142，4132，1324，1423，
2143，3421，2341，2431，3241，4231，2314，2413．输入受限不可得到：
1243，3241，
1423，3421
3.29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0和1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。
试编写与此结构相应的入队列和出队列的算法，并从时间和空间角度讨论设标志和不设标志这两种方法的使用范围（如当循环队列容量较小而队列中每个元素占的空间较多时，哪一种方法较好）。
解：
程序源代码：
#include
#include
精彩文档
实用标准文案
#definemaxqsize5
#defineok1
#defineerror0
typedefintqelemtype;
typedefintstatus;
typedefstruct{
qelemtype*base;
intfront;
intrear;
inttag;
}squeue;
statusinitqueue（squeue&sq）{
sq.base=（qelemtype*）malloc（maxqsize*sizeof（qelemtype））;if（!
sq.base）exit（-2）;
sq.front=sq.rear=0;
sq.tag=0;
returnok;
}
statusenqueue（squeue&sq,qelemtypee）{
if（sq.rear==sq.front&&sq.tag）returnerror;sq.base[sq.rear]=e;
sq.rear=（sq.rear+1）%maxqsize;
精彩文档
实用标准文案
if（sq.rear==sq.front）sq.tag=1;
returnok;
}
statusdequeue（squeue&sq,qelemtype&e）{
if（sq.rear==sq.front&&!
sq.tag）returnerror;e=sq.base[sq.front];
sq.front=（sq.front+1）%maxqsize;
if（sq.tag==1）sq.tag=0;
returnok;
}
voidmain（）{
squeuesq;
qelemtypee;
inti;
initqueue（sq）;
cout<<"请输入队列元素：
"<cin>>e;
"<"<if（enqueue（sq,e））cout<<"元素已插入cout<<"请输入队列元素：
"<>e;
if（enqueue（sq,e））cout<<"元素已插入cout<<"请输入队列元素：
"<精彩文档
实用标准文案
cin>>e;
if（enqueue（sq,e））cout<<"元素已插入"<if（dequeue（sq,e））cout<<"队头元素:
"<cout<<"队列中元素为：
"<for（;dequeue（sq,e）;）
cout<cout<运行结果：
3.30假设将循环队列定义为:
以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。
试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法出队列的算法中要返回队头元素）解：
程序源代码：
#include#include#definemax3
精彩文档
实用标准文案
#defineok1
#defineerror0
typedefintstatus;
typedefintselemtype;
typedefstruct{
selemtype*base;
intrear;
intlength;
}squeue;
statusinitqueue（squeue&sq）{
sq.base=（selemtype*）malloc（max*sizeof（selemtype））;if（!
sq.base）exit（-2）;
sq.rear=0;
sq.length=0;
returnok;
}
statusenqueue（squeue&sq,selemtypee）{if（sq.length>=max）returnerror;sq.base[sq.rear]=e;
sq.rear=（sq.rear+1）%max;
sq.length++;
returnok;
精彩文档
实用标准文案
}
statusdequeue（squeue&sq,selemtype&e）{
if（sq.length<=0）returnerror;
e=sq.base[（sq.rear+max-sq.length）%max];
sq.length--;
returnok;
}
voidmain（）{
squeuesq;
selemtypee;
initqueue（sq）;
cout<<"请输入队列元素：
"<cin>>e;
if（enqueue（sq,e））cout<<"元素已插入"<elsecout<<"队列已满元素未被插入"<"<cin>>e;
if（enqueue（sq,e））cout<<"元素已插入"<elsecout<<"队列已满元素未被插入"<"<cin>>e;
if（enqueue（sq,e））cout<<"元素已插入"<精彩文档
实用标准文案
elsecout<<"队列已满元素未被插入"<cout<<"请输入队列元素：
"<cin>>e;
if（enqueue（sq,e））cout<<"元素已插入"<elsecout<<"队列已满元素未被插入"<if（dequeue（sq,e））cout<<"队头元素:
"<cout<<"队列中元素为：
"<for（;dequeue（sq,e）;）cout<cout<}
运行结果：
3.31假设称正读和反读都相同的字符序列为“回文”，例如，‘abba'和‘abcba'是回文，
abcde'和‘ababab'则不是回文。
试写一个算法判别读入的一个以‘@'为结束符的字符序列是否是“回文”解：
精彩文档
实用标准文案
程序源代码：
#include
#include
#definemax10
typedefcharelemtype;
typedefstruct{
elemt
升级会员 