第3章
综合练习
1.有五个数依次进栈：1,2,3,4,5。在各种出栈的序列中，以3,4先出的序列有哪几个。（３在４之前出栈）。
【解答】有3,4,2,1,5 3,4,2,5,1
3,4,5,2,1
2. 铁路进行列车调度时, 常把站台设计成栈式结构的站台，试问： 若进站的六辆列车顺序为：1,2,3,4,5,6， 那么是否能够得到435612， 325641， 154623和135426的出站序列， 如果不能，说明为什么不能； 如果能， 说明如何得到(即写出"进栈"或"出栈"的序列)。
【解答】能够得到325641，135426 , 不能得到 435612， 154623
3. 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长，当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] = top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈结构的类型定义，并实现判栈空、判栈满、插入、删除算法。
【解答】
首先定义存储结构
typedef struct /* 两栈共享一向量空间 */
{ ElemType v[m]; /* 栈可用空间0—m-1 */
int top[2]
}twostack;
int
push(twostack *s,int i, ElemType x)
/* 两栈共享向量空间,i是0或1，表示两个栈，x是进栈元素，*/
/* 本算法是入栈操作 */
{ if (s->top[1] - s->top[0])==1)
return(0);/* 栈满 */
else {switch (i)
{case 0:
s->v[++(s->top)]=x; break;
case 1:
s->v[--(s->top)]=x; break;
default:
printf(“栈编号输入错误”);return(0);
}
return(1); /* 入栈成功 */
}
} /* 算法结束 */
ElemType pop(twostack *s,int i)
/* 两栈共享向量空间,i是0或1，表示两个栈，本算法是退栈操作 */
{ ElemType x;
switch (i)
{case 0: if
(s->top[0]==-1) return(0);/* 栈空 */
x=s->v[(s->top)--];break;
case 1: if
(s->top[1]==m) return(0);/* 栈空 */
x=s->v[(s->top)++];break;
default:
printf(“栈编号输入错误”);return(0);
}
return(x); /* 退栈成功 */
} /* 算法结束 */
ElemType top (twostack *s,int i)
/* 两栈共享向量空间,i是0或1，表示两个栈，本算法是取栈顶元素操作 */
{ ElemType x;
switch (i)
{case
0: if (s->top[0]==-1) return(0);/* 栈空 */
x=s->v[s->top];break;
case 1: if (s->top[1]==m) return(0);/* 栈空 */
x=s->v[s->top];break;
default: printf(“栈编号输入错误”);return(0);
}
return(x);
/* 取栈顶元素成功 */
} /* 算法结束
*/
4
若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？
【解答】rear和front的值分别为2和4
5. 长度为n的队列用单循环链表表示，若只设头指针，则入队、出队操作的时间为何？若只设尾指针呢？
【解答】长度为n的队列用单循环链表表示，若只设头指针，则入队、出队操作的时间为 O(n)和O(1); 若只设尾指针, 则入队、出队操作的时间均为O(1).
6.
设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e3，e5，e4,e6,e2,e1,则栈S的容量至少应该是多少？
【解答】栈S的容量至少应该是4。
7. 写出下列中缀表达式的后缀形式：
(1) A * B * C
(2) (A + B)* C -D
(3) A* B + C/(D-E)
(4) (A + B) * D + E / (F + A * D) + C
【解答】
(1) A * B * C 的后缀形式是 AB*C*
(2) (A + B)* C –D 的后缀形式是 AB+C*D-
(3) A* B + C/(D-E) 的后缀形式是 AB*CDE-/+
(4) (A + B)
* D + E / (F + A * D) + C 的后缀形式是AB+D*EFAD*+/+C+
9 假设以数组Q[m]存放循环队列中的元素，同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(QueueIn)和删除(QueueOut)算法。
【解答】
首先定义存储结构
typedef struct /* 两栈共享一向量空间 */
{ElemType Q[m] ;
int rear,front; //队尾和队头指针
int tag; //标记, 0为空,1为非空
} CycQueue;
//设头 尾指针和标志域的循环队列
(1) void QueueInit (CycQueue cq); ｛初始化｝
{cq.tag=0; cq.tear=cq.front=0; }
(2) void QueueIn (CycQueue cq, ElemType x)
//cq是由头尾指针和标志域的循环队列，本算法是入队操作，若队列不满，则将x插入到队尾
{ if(cq.tag==1 && cq.front==cq.rear)
{printf(“队满”); exit(0); }
else {cq.rear=(cq.rear+1)
% m;
cq.Q[cq.rear]=x;
if (cq.tag==0) cq.tag=1; //由空变不空标记
}
}
(3) void QueueOut(CycQueue
cq);
//cq是由头尾指针和标志域的循环队列，本算法是出队操作，若队列非空,则将队头元素出队
{if (cq.tag==0)
{ printf(“队空”); exit(0); }
else {cq.front=(cq.front+1)
% m;
if (cq.front==cq.rear)
cq.tag=0; //由不空变队空标记
]
ENDP;
[算法讨论]
:当m较小时,设标记可用足m个单元,但每次操作要判tag,多用了时间,若m较大,不在乎一个单元，应使用牺牲一个单元办法,使操作加快(不再判断tag).
10. 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法。
【解答】
首先定义存储结构
typedef struct
{ElemType Q[m];/* 循环队列占m个存储单元 */
int
rear,length; /* rear指向队尾元素,length为元素个数*/
}sequeue;
(1) int QueueEmpty(sequeue *cq)
/* cq为循环队列，本算法判断队列是否为空 */
{ return (cq->length==0 ? 1: 0);
}
/* 算法结束 */
(2) sequeue *QueueIn(sequeue *cq，ElemType x)
/* cq是以如上定义的循环队列，本算法将元素x入队*/
{if (cq->length==m) return(0); /* 队满 */
else { cq->rear=(cq->rear+1) % m; /* 计算插入元素位置 */
cq->Q[cq->rear]=x; /* 将元素x入队列
*/
cq->length++;
/* 修改队列长度 */
}
return (cq);
}
/* 算法结束 */
ElemType QueueOut(sequeue *cq)
/* cq是以如上定义的循环队列，本算法是出队算法，且返回出队元素 */
{if (cq->length==0) return(0); /* 队空 */
else { int front=(cq->rear-cq->length+1+m) % m; /*
出队元素位置 */
cq->length--;
/* 修改队列长度 */
return (cq->Q[front]); /* 返回对头元素 */
}
}
/* 算法结束 */
11. 假设表达式由单字母变量和双目四则运算算符构成。试编写一个算法，对以逆波兰式表示的表达式求值。
【解答】
int GetValue_NiBoLan(char *str)
{//对逆波兰式求值
p=str;
StackInit(s);
//s为操作数栈
while(*p)
{if(*p>=0&&*p<=9) push(s,*p); //当前元素为操作数则入栈
else
//当前元素为操作符
{pop(s,a);pop(s,b);
//取出栈顶的两个操作数
r=compute(b,*p,a);
//假设compute为执行双目运算的过程
push(s,r);
//计算结果重新入栈
}
p++;
}
pop(s,r);return
r;
//最后取出栈顶元素的值即为运算结果
}
12. 设整数序列a1,a2,…,an，给出求解最大值的递归程序。
【解答】
int A[];
int max(int i,int j)
{int m1,m2.mid;
if (i==j)
return A[i];
else {mid=(i+j)/2;
m1=max(i,mid);
m2=max(mid+1,j);
if(m1>m2) return m1;
else return m2;
}
}
int MaxValue (int a[],int n)
//设整数序列存于数组a中，共有n个，本算法求解其最大值。
{if
(n==1) max=a[1];
else
if a[n]>MaxValue(a,n-1) max=a[n];
else
max=MaxValue(a,n-1);
return(max);
}
13. 已知f为单链表的表头指针， 链表中存储的都是整型数据，试写出实现下列运算的递归算法：
(1) 求链表的结点个数。 (2) 求所有整数的平均值。
【解答】
(1)
int num(LinkedList f)
{if(f==NULL) return 0;
else return num(f->next)+1;
}
(2)
f(n)=((n-1)/n)*f(n-1)+a[n]/n,其中：f(n)=(a[1]+a[2]+…+a[n])/n;
int aver; sum=0,num=0;
int average(LinkedList f)
{if (f)
{sum+=f->data; num++; average(f->next); }
return sum/num;
}
14. 三阶菲波那契数如下定义：
0
n=1
Fib= 0 n=2
1 n=3
Fib（n-1）+Fib（n-2）+ Fib（n-3） n>3
试用递归和非递归的两种方法分别求出第m项（m为正整数）的菲波那契数并且输出。注意：不得使用数组。
【解答】
递归程序：
int fib(int m)
{int f;
if(m= =1) f=0;
else if(m= =2) f=0;
else
if(m= =3) f=1;
else return
fib(m-1)+fib(m-2)+fib(m-3);
}
非递归程序：
int fib3(int m)
{int n=3;
f1=0;
f2=0;
f3=1;
while (n<m)
{fn=f3+f2+f1;
f1=f2;
f2=f3;
f3=f4;
n++;
}
return
fn;
}