栈与队列习题与答案(8)

Qu.end1:=(Qu.end1-1) MOD maxsize; //修改end1

RETURN(Qu.end1+1) MOD maxsize); //返回插入元素的下标。 1: //在end2端插入 [Qu.end2:=x;

Qu.end2:=(Qu.end2+1) MOD maxsize; RETURN(Qu.end2-1) MOD maxsize); ]

ENDC; //结束CASE语句 ENDF; //结束算法add

FUNC delete (Qu: deque; VAR x:datatype; tag:0..1):integer;

//本算法在双端队列Qu中删除元素x，tag=0时从end1端删除，tag=1时从end2端删除。删除成功返回1，否则返回0。

IF (Qu.end1+1) MOD maxsize=Qu.end2 THEN [writeln(“队空”);return(0);] CASE tag OF

0: //从end1端删除

[i:=(Qu.end1+1) MOD maxsize; //i是end1端最后插入的元素下标。 WHILE(i<>Qu.end2) AND (Qu.elem[i]<>x) DO i=(i+1) MOD maxsize;//查找被删除元素x的位置 IF (Qu.elem[i]=x) AND (i<>Qu.end2) THEN [ j:=i;

WHILE((j-1+maxsize) MOD maxsize <>Qu.end1) DO [Qu.elem[j]:=Qu.elem[(j-1+maxsize) MOD maxsize]; j:=(j-1+maxsize) MOD maxsize; ]//移动元素，覆盖达到删除

Qu.end1:=(Qu.end1+1) MOD maxsize; //修改end1指针 RETURN(1); ]

ELSE RETURN(0);

]//结束从end1端删除。 1: //从end2端删除

[i:=(Qu.end2-1+maxsize) MOD maxsize; //i是end2端最后插入的元素下标。 WHILE(i<>Qu.end1) AND (Qu.elem[i]<>x) DO i=(i-1+maxsize) MOD maxsize;//查找被删除元素x的下标

IF (Qu.elem[i]=x) AND (i<>Qu.end1) THEN //被删除元素找到 [ j:=i;

WHILE((j+1) MOD maxsize <>Qu.end2) DO [Qu.elem[j]:=Qu.elem[(j+1) MOD maxsize]; j:=(j

+1) MOD maxsize; ]//移动元素，覆盖达到删除

Qu.end2:=(Qu.end2-1+maxsize) MOD maxsize; //修改end2指针

RETURN(1);//返回删除成功的信息 ]

ELSE RETURN(0);//删除失败 ]//结束在end2端删除。 ENDC;//结束CASE语句 ENDF;//结束delete

[算法讨论]请注意下标运算。(i+1) MOD maxsize容易理解，考虑到i-1可能为负的情况，所以求下个i时用了(i-1+maxsize) MOD maxsize。

13、[题目分析] 本题与上面12题基本相同，现用类C语言给出该双端队列的定义。 #define maxsize 32 typedef struct

{datatype elem[maxsize];

int end1,end2; //end1和end2取值范围是0..maxsize-1 } deque;

14、[题目分析] 根据队列先进先出和栈后进先出的性质，先将非空队列中的元素出队，并压入初始为空的栈中。这时栈顶元素是队列中最后出队的元素。然后将栈中元素出栈，依次插入到初始为空的队列中。栈中第一个退栈的元素成为队列中第一个元素，最后退栈的元素（出队时第一个元素）成了最后入队的元素，从而实现了原队列的逆置。 void Invert(queue Q)

//Q是一个非空队列，本算法利用空栈S和已给的几个栈和队列的ADT函数，将队列Q中的元素逆置。

{makempty(S); //置空栈

while (!isEmpty(Q)) // 队列Q中元素出队

{value=deQueue(Q); push(S,value); }// 将出队元素压入栈中 while(!isEmpty(S)) //栈中元素退栈

{value=pop(S); enQueue(Q,value); }//将出栈元素入队列 Q }//算法invert 结束

15、为运算方便，设数组下标从0开始，即数组v[0..m-1]。设每个循环队列长度（容量）为L，则循环队列的个数为n=ém/Lù。为了指示每个循环队列的队头和队尾，设如下结构类型 typedef struct {int f,r; }scq; scq q[n];

（1）初始化的核心语句

for(i=1;i<=n;i++) q[i].f=q[i].r=(i-1)*L; //q[i]是全局变量 （2）入队 int addq(int i;elemtp x)

//n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将元素插入到第i个循环队列中。若入队成功，返回1，否则返回队满标记0（入队失败）。

{ if (i<1||i>n) {printf(“队列号错误”);exit(0);}

if (q[i].r+1)%L+(i-1)*L==q[i].f) {printf(“队满\\n”);exit(0);} q[i].r=(q[i].r+1)%L+(i-1)*L; // 计算入队位置 v[q[i].r]=x; return(1);//元素x入队 }

（3）出队 int deleteq (int i) // n个循环队列共享数组v[0..m-1]和保存各循环队列首尾指针的q[n]已经定义为全局变量，数组元素为elemtp类型，本过程将第i个循环队列出队。若出队成功，打印出队列元素，并返回1表示成功；若该循环队列为空，返回0表示出队失败。 {if (<1||>n) {printf(“队列号错误\\n”);exit(0);} if (q[i].r==q[i].f) {printf(“队空\\n”); return(0);} q[i].f=(q[i].f+1)%L+(i-1)*L;

printf(“出队元素”,q[i].f); return(1); }

（4）讨论，上述算法假定最后一个循环队列的长度也是L，否则要对最后一个循环队列作特殊处理。另外，未讨论一个循环队列满而相邻循环队列不满时，需修改个循环队列首尾指针的情况（即各循环队列长度不等）。 n个循环队列共享数组v[0..m-1]的示意图如下： 0 L-1 2L-1 3L-1 (n-1)L-1 ?

第i个循环队列从下标 (i-1)L 开始，到iL-1为止。设每个循环队列均用牺牲一个单元的办法来判断队满，即为（q[i].r+1）%L+(i-1)*L=q[i].f时，判定为队满。 16、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); }

17、本题与上题类似，只是这里是同时求n个数中的最大值和最小值的递归算法。 int MinMaxValue(int A[],int n,int *max,int *min)

//一维数组A中存放有n个整型数，本算法递归的求出其中的最小数。 {if (n>0)

{if(*max<A[n]) *max=A[n]; if(*min>A[n]) *min=A[n]; MinMaxValue(A,n-1,max,min); }//算法结束

[算法讨论]调用本算法的格式是MinMaxValue(arr,n,&max,&min);其中，arr是具有n个整数的一维数组，max=-32768是最大数的初值,min=32767是最小数的初值。

18、[题目分析] 求两个正整数m和n的最大公因子，本题叙述的运算方法叫辗转相除法，也称欧几里德定理。其函数定义为： gcd(m,n)=

int gcd (int m,n)

//求正整数m和n的最大公因子的递归算法

{if(m<n) return(gcd(n,m))； //若m<n，则m和n互换 if(n==0) return(m); else return(gcd(n,m%n)); }//算法结束

使用栈，消除递归的非递归算法如下： int gcd(int m,n)

{int s[max][2]; //s是栈，容量max足够大 top=1; s[top][0]=m; s[top][1]=n; while (s[top][1]!=0)

if (s[top][0]<s[top][1]) //若m<n，则交换两数 {t=s[top][0]; s[top][0]=s[top][1]; s[top][1]=t;}

else{t=s[top][0]%s[top][1]; top++; s[top][0]=s[top-1][1]; s[top][1]=t; } return(s[top][0]); }//算法结束

由于是尾递归，可以不使用栈，其非递归算法如下 int gcd (int m,n)

//求正整数m和n的最大公因子

{if (m<n){t=m;m=n;n=t;}// 若m<n，则m和n互换 while (n!=0) {t=m; m=n; n=t%n;} return(m); } //算法结束

19、[题目分析]这是以读入数据的顺序为相反顺序进行累乘问题，可将读入数据放入栈中，到输入结束，将栈中数据退出进行累乘。累乘的初值为1。 PROC test;

CONST maxsize=32;

VAR s:ARRAY[1..maxsize] OF integer, top,sum,a:integer; [top:=0; sum:=1;// read(a);

WHILE a<>0 DO

[top:=top+1; s[top]:=a; read(a); ] write(sum:5); WHILE top>0 DO

[sum:=sum*s[top]; top:=top-1; write(sum:5);] ENDP;

20、[题目分析] 本题与第19题基本相同，不同之处就是求和，另外用C描述。 int test;

{int x,sum=0,top=0,s[]; scanf(“%d”,&x) while (x<>0)

{s[++top]:=a; scanf(“%d”,&x); } printf(sum:5); while (top)

{sum+=s[top--]; printf(sum:5); } };

21、int Ack(int m,n) {if (m==0) return(n+1);

else if(m!=0&&n==0) return(Ack(m-1,1)); else return(Ack(m-1,Ack(m,m-1)); }//算法结束

（1）Ack(2,1)的计算过程

Ack(2,1)=Ack(1,Ack(2,0)) //因m<>0,n<>0而得 =Ack(1,Ack(1,1)) //因m<>0,n=0而得

=Ack(1,Ack(0,Ack(1,0))) // 因m<>0,n<>0而得 = Ack(1,Ack(0,Ack(0,1))) // 因m<>0,n=0而得 =Ack(1,Ack(0,2)) // 因m=0而得 =Ack(1,3) // 因m=0而得

=Ack(0,Ack(1,2)) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(1,1))) //因m<>0,n<>0而得

= Ack(0,Ack(0,Ack(0,Ack(1,0)))) //因m<>0,n<>0而得 = Ack(0,Ack(0,Ack(0,Ack(0,1)))) //因m<>0,n=0而得 = Ack(0,Ack(0,Ack(0,2))) //因m=0而得 = Ack(0,Ack(0,3)) //因m=0而得 = Ack(0,4) //因n=0而得 =5 //因n=0而得

（2）int Ackerman( int m, int n) {int akm[M][N];int i,j;

for(j=0;j<N;j++) akm[0][j];=j+1; for(i=1;i<m;i++) {akm[i][0]=akm[i-1][1]; for(j=1;j<N;j++)

akm[i][j]=akm[i-1][akm[i][j-1]]; }

return(akm[m][n]); }//算法结束

22、[题目分析]从集合（1..n）中选出k(本题中k=2)个元素，为了避免重复和漏选，可分别求出包括1和不包括1的所有组合。即包括1时，求出集合（2..n）中取出k-1个元素的所有组合；不包括1 时，求出集合（2..n）中取出k个元素的所有组合。，将这两种情况合到一起，就是题目的解。

int A[],n; //设集合已存于数组A中。 void comb(int P[],int i,int k)

//从集合（1..n）中选取k（k<=n）个元素的所有组合

{if (k==0) printf(P);

else if(k<=n) {P[i]=A[i]; comb(P,i+1,k-1); comb(P,i+1,k); }

}//算法结束

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库栈与队列习题与答案(8)在线全文阅读。