3-4数据结构作业.doc
文本预览下载声明
第三章
3.5 假设以S和X分别表示入栈和出栈的操作，则初态和终态均为空栈的入栈和出栈的操作序列可以表示为仅由S和X组成的序列。称可以操作的序列为合法序列（例如，SXSX为合法序列，SXXS为非法序列）。试给出区分给定序列为合法序列或非法序列的一般准则，并证明：两个不同的合法（栈操作）序列（对同一输入序列）不可能得到相同的输出元素（注意：在此指的是元素实体，而不是值）序列。
解：
一般准则：任何前n个序列中S的个数一定大于或等于X的个数且整个序列中S的个数一定等于X的个数。
证明：设两个合法序列为：
T1=S……X……S……
T2=S……X……X……
假定前n个操作都相同，从第n+1个操作开始，为序列不同的起始操作点。由于前n个操作相同，故此时两个栈（不妨为栈A、B）的存储情况完全相同，假设此时栈顶元素均为a。
第n+1个操作不同，不妨T1的第n+1个操作为S，T2的第n+1个操作为X。T1为入栈操作，假设将b压栈，则T1的输出顺序一定是先b后a；而T2将a退栈，则其输出顺序一定是先a后b。由于T1的输出为……ba……，而T2的输出顺序为……ab……，说明两个不同的合法栈操作序列的输出元素的序列一定不同。
3.9 试将下列递推过程改写为递归过程。
void ditui(int n)
{
int i;
i = n;
while(i1)
couti--;
}
解：
Void digui(int n){
if (n==2) printf(“%d”,n);
else {
printf(“%d”,n); digui(n-1);}
}
3.10 试将下列递归过程改写为非递归过程。
void test(int sum)
{
int x;
cinx;
if(x==0) sum=0;
else
{
test(sum);
sum+=x;
}
coutsum;
}
解：
void test(int sum){
sqstack s;
int x;
scanf(%d,x);
initstack(s);
while(x!=0){
*s.front++=x;
scanf(%d,x);
}
sum=0;
int e;
printf(%d,sum);
while(s.front!=s.base){
e=*(--s.front);
sum+=e;
printf(%d,sum);
}
}
3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存在着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化inistack(tws)、入栈push(tws,i,x)和出栈pop(tws,i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程(正/误状态变量可设为变参)或函数设计这些操作算法各有什么有缺点。
解：
程序源代码：
#includestdio.h
#includemalloc.h
#define STACK_INIT_SIZE 100
#define TURE 1
#define FALSE 0
#define ok 1
#define error 0
#define INFEASIBLE -1
typedef int selemtype ;
typedef int status;
typedef struct{
int * base[2];
selemtype * top[2];
int stacksize;
}sqstack;
status INITstack(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);
return ok;
}
status Push(sqstack * s,int i,selemtype e){
if(i==0){
if ((*s).top[0]=((*s).base[0]+(STACK_INIT_SIZE/2)-1)) return error;
else *(*s).top[0]++=e;
return ok;
}
if(i==1){
if((*s).top[1]=((*s).base[1]-(
显示全部