1.假定有四个元素A、B、C、D，按所列次序进栈，试写出所有可能的出栈列，注意，每一
个元素进栈后都允许出栈，如ACDB就是一种出栈序列。
解：
ABCD ABDC ACBD ADCB BACD BADC BCAD
BCDA BDCA CBAD CDBA DCBA
2.在一个数组空间stack[StackMaxSize]中可以同时存放两个顺序栈，栈底分别在数组的两端
，当第一个栈的栈顶指针top1等于-1时则栈1为空，当第二个栈的栈顶指针top2等于StackMax
Size时栈2为空。两个栈均向中间增长，当向栈1插入元素时，使top1增1得到新的栈顶位置，
当向栈2插入元素时，则使top2减1才能够得到新的栈顶位置。当top1等于top2-1或者top2等
于top1+1时，存储空间用完，无法再向任一栈插入元素。用于双栈操作的顺序存储类型可定
义为：
struct Bothstack{
ElemType stack[stackMaxSize];
int top1,top2;
};
双栈操作的抽象数据类型可定义为：
DAT BSTACK is
Data:采用顺序结构存储的双栈，其存储类型为Bothstack
operations:
void InitStack(Bothstack& BS,int k);
//初始化栈。当k=1或2时对应置栈1或栈2为空，k=3时置两个格均为空
void Clearstack(BothStack& BS,int k)
//清除栈。当k=1或2时对应栈1或栈2被清除，k=3时两个栈均被清除
int StackEmpty(BothStack& BS,int k)
//判断栈是否为空。当k=1或2时判断对应的栈1或栈是否为空，k=3时
//判断两个栈是否同时为空。若判断结果为空则返回1，否则返回0
ElemType Peek(BothStack& BS,int k)
//取栈顶元素。当k=1或2时对应返回栈1或栈2的栈顶元素
void Push(BothStack& Bs,int k,const ElemType& item)
//进栈。当k=1或2时对应向栈1或栈2的顶端压入元素item
End BSTACK
1.试写出上述抽象数据类型中每一种操作的算法。
解：
void InitStack(BothStack& BS,int k)
{
if(k==1)
BS.top1=-1;
else if(k==2)
BS.top2=StackMaxSize;
else if(k==3){
BS.top1=-1;
BS.top2=StackMaxSize;
}
}
void ClearStack(BothStack& BS,int k)
{ //函数体同上
}
int StackEmpty(BothStack& BS,int k){
if(k==1)
return BS.top1==-1;
else if(k==2)
return BS.top2==StackMaxSize;
else if(k==3)
return(BS.top1==-1)&&(BS,top2==StackMaxSize);
else{
cerr<<"k的值不正确!"';
exit(1);
}
}
ElemType peek(BothStack& BS,int k)
{
if(k==1){
if(BS.top1==-1){
cerr<<"Stack 1 is empty!"<<end1;
exit(1);
}
return BS,stack(bs,top1);
}
else if(k==2){
if(BS.top2==StackMaxSize){
cerr<<"Stack 2 is empty!"<<end1;
exit(1);
}
return BS,stack[BS,top2];
}
else{
cerr<<"k的值不正确!";
exit(1);
}
}
void push(BothStack& BS,int k,const ElemType& item)
{
if(BS.top1==BS.top2-1){
cerr<<"Stack overflow!"<<end1;
exit(1);
}
if(k==1){
BS.top1++;
Bs.stack[BS.top1]=item;
}
else if(k==2){
BS.top1--;
BS.stack[BS.top2]=item;
}
}
ElemType pop(BothStack& BS,int k]
{
if(k==1){
if(BS.top==-1){
cerr<<"Stack 1 is empty!"<<end1;
exit(1);
}
BS.top--;
return BS,stack[BS.top1+1];
}
else if(k==2){
if(BS.top==StackMaxSize){
cerr<<"Stack 2 is empty!"<<end1;
exit(1);
}
BS.top2++;
return BS.stack[BS,top2-1];
}
else{
cerr<<"k的值不正确!";
exit(1);
}
}
2.假定上述所有操作的算法已存于头文件"bstack.h"中，试编写一个程序，让计算机随机
产生出100以内的20个正整数并输出，同时把它们中的偶数依次存入到第一个栈中，奇数
依次存入到第二个栈中，接着按照存入每个栈中元素的次序分别输出每个栈中的所有元素
(此操作不改变栈的状态)，然后按照后进先出的原则输出每个栈中的所有元素。
解：
#include<iostream.h>
#include<stdlib.h>
const int StackMaxSize=50;
typedef int ElemType;
struct BothStack{
ElemType stack[StackMaxSize];
int top1,top2;
};
#include"bstack.h"
void main()
{
BothStack a;
InitStack(a,3);//初始化两个栈
int i,j,k;
//计算机产生20个随机数并输出，同时按奇偶数不同分别放入不同的栈中
for(i=0;i<20;i++){
j=rand()%100;
cout<<j<<"";
if(j%2==0)
push(a,1,j);
else
push(a,2,j);
}
cout<<end1;
//按照存入栈1中元素的次序输出栈1中的所有元素
cout<<"栈1：";
for(i=0;i<=a.top1;i++)
cout<<a.stack[i]<<"";
cout<<end1;
//按照存入栈2中元素的次序输出栈2中的所有元素
cout<<"栈2：";
for(i=StackMaxSize-1;i>=a.top2;i--)
cout<<a.stack[i]<<"";
cout<<end1;
//按照后进先出的原则输出每个栈中的所有元素
for(k=1;k<=2;k++){
if(k==1)
cout<<"栈1：";
else
cout<<"栈2：";
while(!StackEmpty(a,k))
cout<<Pop(a,k)<<"";
cout<<end1;
}
}
该程序输入并运行后将得到如下结果(由于机器系统和C++版本不同，你得到的结果可能
与此不同)：
41 67 34 0 69 24 78 58 62 5 45 81 27 61 91 95 42 27 36
栈1：34 0 24 78 58 62 64 42 36
栈2：41 67 69 5 45 81 27 61 91 95 27
栈1：36 42 64 62 58 78 24 0 34
栈2：27 95 91 61 27 81 45 5 69 67 41
3.设用第二章定义的类型为AlinkList的一维数组MS[MaxSize]建立三个链接堆栈，其中前三个元
素的next域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用，
试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈：
⑴若输入的整数x小于60，则进第一个栈；
⑵若输入的整数x大于等于60同时小于100，则进第二个栈；
⑶若输入的整数大于100，则进第三个栈。
解：
void MoreStack(ALinkList MS,int n)
//把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中
{
if(n>MaxSize-3){
cerr<<"存储空间不足!";
exit(1);
}
int i,x,av;
for(i=0;i<3;i++)
MS[i].next=0//置空栈，即给三个栈顶指针赋0
av=3;//av指向可利用元素的下标，赋初值为3
cout<<"输入"<<n<<"个整数："<<end1;
for(i=0;i<n;i++){
//从键盘读入一个整数并把它赋给av元素的值域
cin>>x;
MS[av].data=x;
//按条件把av元素压入不同的栈，即链接到相应栈的栈顶
if(x<60){
Ms[av].next=MS[0].next;
MS[0].next=av;
}
else if(x>=60&&x<=100){
MS[av].next=MS[1].next;
MS[1].next=av;
}
else{
MS[av].next=MS[2].next;
MS[2].next=av;
}
//使av指向下一个可利用元素
av++;
}
}
4.编写一个程序，首先调用上题算法，然后分别打印出每个栈中的内容。
解：
#include<iostream.h>
#include<stdlib.h>
const int MaxSize=50;//要至少定义为比输入的整数个数大3
typedef int ElemType;
struct ALNode{
ElemType data;
int next;
};
typedef ALNode ALinkList[MaxSize];
void MoreStack(ALinkList MS,int n)
{//函数体在此省略
}
void main()
{
ALinkList a;
int n;
cout<<"从键盘输入的整数个数(1～47):";
cin>>n;
MoreStack(a,n);
for(int i=0;i<3;i++)
{ //依次将每个栈中的元素全部出栈并打印出来
int j=a[i].next;
while(j!=0){
cout<<a[j].data<<"";
j=a[j].next;
}
cout<<end1;
}
}
一次输入和运行结果如下：
从键盘上输入的整数个数为(1～47)：12
输入12个整数：
38 64 97 120 78 33 45 214 88 25 143 60
25 45 33 38
60 88 78 97 64
143 214 120
5.已知一个中缀算术表达式为：
3+4/(25-(6+15))*8@
⑴写出对应的后缀算术表达式。
解：3 4 25 6 15 + - /8 * + @
⑵画出在转换成后缀表达式的过程中运算符栈的变化。
解：略
6.已知一个后缀算术表达式为：
24 8 + 3 * 4 10 7 - * / @
⑴写出对应的中缀算术表达式。
解： (24+8)*3/(4*(10-7))
⑵画出在进行后缀算术表达式求值的过程中数值栈的变化。
解：略
7.为了计算表达式的值：
把栈Stack类型定义为带模板的类型，该类型中包含顺序存储的栈和对栈的每一种基
本操作的实现。
解：把进行后缀表达式求值的Compute算法改写为使用Stack类的算法。
解：把进行中缀表达式转换为后缀表达式的Change算法改写为使用Stack类的算法。
解：写出计算C(n,k)的递归算法。
解：利用二维数组写出计算C(n,k)的非递归算法。
解：分析递归算法和非递归算法的时间复杂度和空间复杂度。
解：
template<class ElemType>
class Stack{
ElemType stack[StackMaxSize];
int top;
public:
void InitStack()
//初始化栈对象，即把它置为空
{
top=-1;
}
void ClassStack()
//清除栈对象中的所有元素，使之成为一个空栈
{
top=-1;
}
int StackEmpty()
//判断栈对象是否为空，若是则返回1，否则返回0
{
return top==-1;
}
ElemType peek()
//返回栈对象的栈顶元素，但不移动栈顶指针
{
if(top==-1){
cerr<<"Stack is empty!"<<end1;
exit(1);
}
return stack[top];
}
void push(const ElemType& item)
//元素item进栈，即插入到栈顶
if(top==StackMaxSize-1){
cerr<<"Stack overflow!"<<end1;
exit(1);
}
top++;
stack[top]=item;
}
ElemType Pop()
//删除栈顶元素并返回之
{
if(top==-1){
cerr<<"Stack is empty!"<<end1;
exit(1);
}
ElemType temp=stack[top];
top--;
return temp;
}
}
float Compute(char* str)
{
Stack<float> s;//定义元素类型为float的栈
S.InitStack();
istrstream ins(str);
char ch;
float x;
ins>>ch;
while(ch!='@')
{ //扫描每一个字符并进行相应处理
switch(ch)
{
cass'+':
X=S.Pop()+S.Pop();
break;
cass'-':
X=S.Pop();
X=S.Pop()-X;
break;
cass'*':
X=S.Pop()*S.Pop();
break;
cass'/':
X=S.Pop();
if(X!=0.0)
X=S.Pop()/X;
else{
cerr<<"Divide by 0!"<<end1;
exit(1);
}
break;
default://读入的必为一个浮点数的最高位数字
ins.putback(ch);
ins<<X;
}
S.Push(X);
ins>>ch;
}
if(!S.StackEmpty())
{
x=s.Pop();
if(!S.StackEmpty())
return X;
else{
cerr<<"expression error!"<<end1;
exit(1);
}
}
else{
cerr<<"Stack is empty!"<<end1;
exit(1);
}
}
void Change(char* s1,char* s2)
{
Stack<char>R;//定义元素类型为char的栈
R.InitStack();
R.push('@');
int i,j;
i=0;
j=0;
char ch=s1[i];
while(ch='@')
{
if(ch=='')
ch=s1[++i];
else if(ch=='('){
R.Push(ch);
ch=s1[++i];
}
else if(ch==')'){
while(R.peek()!='(')
s2[j++]=R.Pop();
R.Pop();
ch=s1[++i];
}
else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){
char w=R.peek();
while(precedence(w)>=Precedence(ch){
s2[j++]=w;
R.Pop();w=R.Peek();
}
R.Push(ch);
ch=s1[++i];
}
else{
while(isdigit(ch)||ch=='.'){
s2[j++]=ch;
ch=s1[++i];
}
s2[j++]='';
}
}
ch=R.Pop();
while(ch!='@'){
s2[j++]=ch;
ch=R.Pop();
}
s2[j++]='@';
s2[j++]='\0';
}
8.编写把十进制正整数转换为十六进制数输出的算法。
解：
void Transform(long num)
//把一个正整数num转为一个十六进制数输出
{
Stack a;
InitStack(a);
while(num!=0){
int k=num % 16;
Push(a,k);
num/=16;
}
while(!StackEmpty(a))
{
int X=Pop(a);
if(x<10)
cout<<x;
else{
switch(x)
{
cass 10:
cout<<'A';
break;
cass 11:
cout<<'B';
break;
cass 12:
cout<<'C';
break;
cass 13:
cout<<'D';
break;
cass 14:
cout<<'E';
break;
cass 15:
cout<<'F';
}
}
}
cout<<end1;
}
9.编写把十进制正整数转换为S进制(2≤S≤9)数输出的递归算法，然后若把425转换为六进制
数，画出每次递归调用前和返回后系统栈的状态。
解：
只给出递归算法，画图从略。
void Transform(long num,int s)
//把十进制正整数转换为S进制数的递归算法
{
int k;
if(num!=0){
k=num%S;
Transfrom(num/S,S);
cout<<k;
}
}
10.裴波那契(Fibonacci)数列的定义为：它的第一项和第二项均为1，以后各项为其前两项之和。
若裴波那契数列中的第n项用Fid(n)表示，则计算公式为：
1 (n=1或n=2)
Fib(n)= Fib(n-1)+Fib(n-2) (n>=2)
试编写计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。
解：
递归算法为：
long Fib(int n)
{
if(n==1||n==2) //终止递归条件
return 1;
else
return Fib(n-1)+Fib(n-2);
}
非递归算法为
long Fib1(int n)
{
int a,b,c;//C代表当前项，a和b分别代表当前项前面的第2项和第1项
a=b=1; //给a和b赋初值1
if(n==1||n==2)
return 1;
else
for(int i=3;i<=n;i++){
c=a+b; //求出当前项
a=b;//把前面第1项赋给前面第2项
b=c;//把当前项赋给前面第1项
}
return c;//返回所求的第n项
}
11.根据代数中的二项式定理，二项式(x+y)n的展开式的系数序列可以表示成
图4-1那样的三角形，其中除每一行最左和最右两个系数等于1以外，其余各数均等于上一
行左右两系数之和。这个系数三角形称作杨辉三角形。
(x+y)0 1
(x+y)1 1 1
(x+y)2 1 2 1
(x+y)3 1 3 3 1
(x+y)4 1 4 6 4 1
(x+y)5 1 5 10 10 5 1
(x+y)6 1 6 15 20 15 6 1
(x+y)7 1 7 21 35 35 21 7 1
(x+y)8 1 8 28 56 70 56 28 8 1
图4-1 杨辉三角形
设C(n,k)表示杨辉三角形中第n行(n≥0)的第k个系数(0≤k≤n)，按照二项式定理，C(n,k)
可递归定义为：
1 (k=0或k=n)
C(n,k)=
C(n-1,k-1)+C(n-1,k) (n>=2)
int C(int n,int k)
//求出指数为n的二项展开式中第k项(0<=k<=n)系数的递归算法
{
if(k==0||k==n)
return 1;
else
return C(n-1,k-1)+C(n-1,k);
}
int C1(int n,int k)
//求出指数为n的二项展开式中第k项(0<=k<=n)系数的非递归算法
{
typedef int b[15];
//定义一维整型数组类型[15]为b，其尺寸要大于参数n
b*a=new b[n+1];
//动态分配具有b类型的一维数组，其尺寸为n+1，这样a就指向了一个具有
//[n+1][15]的二维数组。
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
//外循环每循环一次计算出指数为i的二项展开式的所有系数，内循环每循环
//一次计算出此展开式中第j项的系数
if(j==0||j==1)
a[i][j]=1;
else
a[i][j]=a[i-1][j-1]+a[i-1][j];
return a[n][k]; //返回指数为n的二项展开式中第k项的系数
}
递归时间复杂度和空间复杂度分别为O(2n)和O(n)，非递归算法的时间复杂
度和空间复杂度均为O(n2)。
12.利用堆栈编写出求解迷宫问题的非递归算法。
解：
设描述迷宫中当前位置的结构如下
struct item
{//定义描述迷宫中当前位置的结构
int x,y,d; //x和y分别表示当前位置的行坐标和列坐标，d表示移动到下一步的方向
};
此题的算法如下:
void Seekpath(int m,int n)
//查找m*n迷宫从入口(1,1)到出口(m,n)的一条通路
{
mark[1][1]=1;
Stack S;//栈的元素类型应定义为item
InitStack(s);
items temp;
temp.x=1;temp.y=1;temp.d=-1;
push(s,temp);//将入口点压入栈
while(!stackEmpty(s))
{ //每循环一次从查找的路径中退回一步
temp=Pop(S);//将保存的上一个位置出栈
int x=temp.x;int y=temp.y;int d=temp.d+1;
//沿着该位置的下一个方向前进
while(d<4)
{//按顺时针方向试探着前进
if(x==m&&y==n)//到达出口，按逆序输出路径中每个位置的坐标，然后返回
{
cout<<m<<""<<n<<end1;
while(!StackEmpty(S)){
temp=Pop(S);
cout<<temp.x<<""<<temp.y<<end1;
}
return;
}
int g=x+move[d][0];int h=y+move[d][1];
//按方向d前进，求出下一个位置的坐标
if(mase[g][h]==0&&mark[g][h]==0)
{//对未访问过的可通行的下一个位置，应将当前位置进栈，并将下一个位置
//变为当前位置，否则改变沿当前位置前进的方向
mark[g][h]=1;
temp.x=x;temp.y=y;temp.d=d;
Push(S,temp);
x=g;y=h;d=0;
//进入一个新位置后，重新从初开始方向东开始
}
else
d++;
}
}
cout<<"不存在从入口到出口的通路"<<end1;
}
调用此算法的完整程序如下。
#include<iostream.h>
#include<stdlib.h>
const int StackMaxSize=30;
struct item
{//定义描述迷宫中当前位置的结构
int x,y,d;//x和y分别表示当前位置的行坐标和列坐标，d表示移动到下一步的
//方向
};
typedef items ElemType; //定义栈中元素的类型为items类型
struct stack{
ElemType stack[StackMaxSize];
int top;
};
#include"stack.h"//保存栈基本操作算法的头文件
const M=10,N=10; //定义M和N常量，由它们决定迷宫的最大尺寸
int maze[M+2][N+2];//定义保存迷宫数据的数组
int mark[M+2][N+2];//定义保存访问标记的数组
int move[4][2]={{0,1},{0,-1},{-1,0}};
//行下标0,1,2,3分别代表东,南,西,北方向
void SeekPath(int m,int n)
//查找m*n迷宫中从入口(1,1)到出口(m,n)的一条通路
{//函数体在此省略
}
void main(void)
{
int i,j;
int m,n;
//输入迷宫尺寸
do{
cout<<"输入迷宫的行数m和列数n："；
cin>>m>>n;
if(m>M||n>N)cout<<"重新输入m和n的值."<<end1;
}while(m>M||n>N);
//输入迷宫数据
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
cin>>maze[i][j];
//初始化mark数组
for(i=0;i<m+2;i++)
for(j=0;j<n+2;j++)
mark[i][j]=0;
//求解maze迷宫中从入口(1,1)到出口(m,n)的一条路径
Seekpath(m,n);
}
13.编写一个递归算法，输出自然数1～n这n个元素的全排列。
分析：由排列组全的知识可知，n个元素的全排列共有n!种，如对于1,2,3这三个元素,其全排
列为123,132,213,231,321,312,共3!=6种。n!种可分解为n*(n-1)!种，而(n-1)!种又可分解
为(n-1)(n-2)!种，依次类推。对于n个元素 ,可把它们分别放入到n个位置上，让第一个元素
依次取每一个元素，共有n种不同的取法，对其后n-1个位置上的n-1个元素，共有(n-1)!种不
同的排列，所以总共有n(n-1)!种不同的排列；同样，
解：
对n个元素的全排列是一个递算法，具体描述如下。
void Permute(int a[],int s,int n)
//对a[s]～a[n-1]中的n-s个元素进行全排列，s的初始值为0
{
int i,temp;
if(s==n-1)
{ //当递归排序到最后一个元素时结束递归，输出a中保存的一种排列
for(i=0;i<n;i++)
cout<<a[i]<<"";
cout<<"";
}
else //继续递归排列
for(i=s;i<n;i++)
{ //每循环一次使a[s]取一个新值，并对其后的所有元素进行递归排序
temp=a[s];a[s]=a[i];a[i]=temp;
//交换a[s]与a[i]的元素值
Permute(a,s+1,n);
//对a[s+1]～a[n-1]中的元素进行递归排序
temp=a[s];a[s]=a[i];a[i]=temp;
//恢复a[s]与a[i]的原有值
}
}
调用此算法的完整程序如下。
#include<iostream.h>
const int UpperLimit=6;//定义全排列的元素个数的最大值
void Permute(int a[],int s,int n)
//对a[s]～a[n-1]中的n-s个元素进行全排列，s的初值为0
{
}//函数体在此省略
void main(void)
{
int a[UpperLimt];//定义存储n个整型元素的数组
int n;
cout<<"Enter a number'n'between 1and"
<<UpperLimit<<":";
cin>>n;//输入待全排的元素的个数
for(int i=0;i<n;i++)
a[i]=i+1; //给数组a赋初值
cout<<end1;
Permute(a,0,n);//对数组a中的n个元素(即1-n)进行全排列
cout<<end1;
}
14.根据
解： 略
15.假定用于顺序存储一个队列的数组的长度为N，队首和队尾指针分别为front和rear
，写出求此队列长度(即所含元素个数)的公式。
解：
队列长度的计算公式为：
(N+rear-front)%N
16.假定在一个链接队列中只设置队尾指针，不设置队首指针，并且让队尾结点的指针域
指向队首结点(称此为循环链队)，试分别写出在循环链队上进行插入和删除的算法。
解：
插入操作的算法如下。
void QInsert(LNode*&Rear,const ElemType& item)
//使新元素item的值插入到循环链队中
{
LNode*newptr=new Lnode;
//得到一个由newptr指针所指向的新结点
if(newptr==NULL){
cerr<<"Memory allocation failare"<<end1;
exit(1);
}
newptr->data=item;//把item的值赋给新结点的值域
if(Rear==NULL)
Rear=newptr->next=newptr;
//若链队为空，则新结点即是队首结点又是队尾结点
else{
newptr->next=Rear->next;
//使新结点的指针域指向队首结点
Rear->next=newptr;
//使队尾结点的指针域指向新结点
Rear=newptr;
//使新结点成为新的队尾结点
}
}
删除操作的算法如下。
ElemType QDelete(LNode*&Rear)
//从循环链队中删除队首元素
{
if(Rear==NULL){
cerr<<"Linked queue is empty!"<<end1;
exit(1);
}
LNode* p=Rear->next; //使p指向队首结点
if(p==Rear)
Rear=NULL;
//若链队中只有一个结点，则删除后队尾指针为空
else
Rear->next=p->next;
//使队尾结点的指针域指向队首结点的后继结点
ElemType temp=p->data;//暂存队首元素
delete p;//回收原队首结点
return temp;//返回被删除的队首元素
}
