第3章习题答案
习题3
1.名词解释：栈、队列、循环队列。
解：栈是只能在一端进行插入和删除操作的线性表，允许插入和删除的一端叫栈顶，另一端叫栈底。最后插入的元素最先删除，故栈也称后进先出表。
队列是允许在一端插入而在另一端删除的线性表，允许插入的一端叫队尾，允许删除的一端叫队头。最后插入的元素最先删除，故栈也称先进先出表。最先入队的元素最先删除，故队列也称先进先出表。
用常规意义下顺序存储结构的一维数组表示队列，由于队列的性质（队尾插入，队头删除），容易造成“假溢出”现象，即队尾已达到一维数组的高下标，不能再插入，然而队中元素个数小于队列的长度。循环队列是解决“假溢出”的一种方法。通常把一维数组看成首尾相接。在循环队列下，通常采用“牺牲一个存储空间”的方法解决“队满”和“队空”的判定问题。
2.如果输入序列为1，2，3，4，5，6，试问能否通过栈结构得到以下两个序列：4，3，5，6，1，2和1，3，5，4，2，6；请说明为什么不能或如何才能得到。
解：输入序列为1，2，3，4，5，6，不能得到4，3，5，6，1，2，其理由是：输出序列最后两个元素是1，2，前面四个元素（4，3，5，6）得到后，栈中元素剩下1，2，且2在栈顶，栈底元素1不可能在栈顶元素2出栈之前出栈。
得到序列1，3，5，4，2，6的过程是：1入栈并出栈；然后2和3依次入栈，3出栈，部分输出序列是1，3；紧接着4和5入栈，5，4和2依次出栈，此时输出序列为1，3，5，4，2；最后6入栈并出栈，得到最终结果序列是1，3，5，4，2，6。
3.试证明：若借助栈由输入序列1，2，…，n 得到序列1p ，2p ，…，n p (它是输入序列的一个全排列)，则在输出序列中不可能出现下列情形：存在着i 解：如果i 4.当函数f 递归调用自身时，函数f 内定义的局部变量在函数f 的2次调用期间是否占用同一数据区？为什么？ 解：函数f 递归调用自身时，函数f 内定义的局部变量在函数f 的2次调用期间不占用同一数据区。每次调用都保留其数据区，这是由递归定义所决定的，用“递归工作栈”来实现。 5.简要叙述循环队列的数据结构，并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值。 解：循环队列的数据结构略。 typedef struct{ ElemType *elem; int front; int rear; }SqQueue,Q; （1）初始状态: Q.front=Q.rear=0; （2）队列空: Q.front=Q.rear=0; （3）队列满: Q.front=(Q.rear+1)%MAXSIZE; 6.设一个双端队列，元素进入该队列的次序为1，2，3，4.求既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列。 解：既不能由输入受限的双端队列得到，又不能由输出受限的双端队列得到的输出序列是：4，2，3，1。 7.简述以下算法的功能。 (1)void algo1(Stack S){ int i,n,A[255]; n=0; while(!StackEmpty(S)){n++;Pop(S,A[n]);}; for(i=1;i<=n;i++)Push(S,A[i]); } (2)void algo2(Stack S,int e){ Stack T;int d; InitStack(T); while(!StackEmpty(S)){Pop(S,d);if(d!=e)Push(T,d);} while(!StackEmpty(T)){Pop(T,d);Push(S,d);} } (3)void algo3(Queue &Q){//栈和队列的元素类型均为int Stack S;int d; InitStack(T); while(!QueueEmpty(Q)){DeQueue(Q,d);Push(S,d);} while(!StackEmpty(S)){Pop(S,d);EnQueue(Q,d);} } 解：（1）将栈中元素逆置。 （2）将栈中的0元素删除。 （3）将队列中元素逆置。 8.试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中不含字符@，且序列2是序列1的逆序列。 解： int IsReverse(){//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 SqStack s; char c,x; InitStack(s); while((c=getchar())!='&')Push(s,c); while((c=getchar())!='@'){ if(StackEmpty(s))return 0; Pop(s,x); if(x!=c)return 0; } if(!StackEmpty(s))return 0; return 1; } 9.在火车调度站的入口处有n 节硬席或软席车厢(分别以H 和S 表示)等待调度，试写一算法，输出对这n 节车厢进行调度的操作(即入栈或出栈操作)序列，以使所有的软席车厢都被调整到硬席车厢之前。 解：typedef char SS[MAX]; void Train_arrange(SS &train){//这里用字符串train 表示火车,'H'表示硬席,'S'表示软席 SqStack s; char *p,*q,c; p=train; q=train; InitStack(s); while(*p){ if(*p=='H')Push(s,*p);//把'H'存入栈中 else *(q++)=*p; //把'S'调到前部 p++; } while(!StackEmpty(s)){ Pop(s,c); *(q++)=c;//把'H'接在后部 } } 10.试写出求递归函数)(n F 的递归算法，并消除递归： ???>?=+=0 )2/(01)(n n F n n n n F 解： int F_recursive(int n,int &s){//递归算法 if(n<0) return ERROR; if(n==0) s=n+1; else{ F_recursive(n/2,s); s=n*s; } return OK; }//F_recursive typedef struct { ElemType a; ElemType b; }node; typedef struct { node *data; int top;//栈顶指针 int stacksize; }SqStack; void F_nonrecursive(int n,int &s){//非递归算法 SqStack T; node x,t; if(n<0) exit(0); if(n==0) s=n+1; else { InitStack(T); while(n!=0){ x.a=n;x.b=n/2; Push(T,x); n=x.b; }//while s=1; while(!StackEmpty(T)){ Pop(T,t); s*=t.a; }//while } }//F_nonrecursive 11.试将下列递归函数改为非递归函数。 void test(int &sum){ int x; scanf ("%d",&x); if (x==0)sum=0; else {test(sum);sum+=x;} printf ("sum=%d\n",sum); } 解： void test(){ int x,sum=0,top=-1,s[10]; scanf("%d",&x); while(x!=0){s[++top]=x; scanf("%d",&x);} printf("sum=%d",sum); while(top>-1){sum+=s[top--]; printf("sum=%d\n",sum);} }; 12.设整数列1p ，2p ，…，n p ，给出求解最大值的递归程序。 解： int MaxValue(int a[],int n){ int max; if(n==1)max=a[0]; else if(a[n-1]>MaxValue(a,n-1))max=a[n-1]; else max=MaxValue(a,n-1); return max; } 13.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队和出队的算法。 解： (1) void InitQueue(CirLinkList &rear){ rear=new LNode; rear->next=rear; } (2) void EnQueue(CirLinkList &rear, ElemType x){ LNode *s; s=new LNode; s->data=x; s->next=rear->next; rear->next=s; rear=s; } (3) void DnQueue(CirLinkList &rear,ElemType &x){ LNode *s; if(rear->next==rear){printf("队空\n");exit(0);} s=rear->next->next;//s指向队头元素 rear->next->next=s->next;//队头元素出队 x=s->data; if(s==rear)rear=rear->next;//空队 delete s; } 14.假设称正读和反读都相同的字符序列为“回文”，试写一个算法判别读入的一个亿@为结束符的字符序列是否是“回文”。 解： int Test(){//判别输入的字符串是否回文序列,是则返回1,否则返回0 SqStack S; SqQueue Q; char c; ElemType a,b; InitStack(S);InitQueue(Q); while((c=getchar())!='@'){ Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构 } while(!StackEmpty(S)){ Pop(S,a); DeQueue(Q,b); if(a!=b) return ERROR; } return OK; } 15.写一算法，借助于栈将一个单链表逆序输出。 解： void process(LinkList &L){ LNode *p; SqStack s; ElemType x; p=L->next; InitStack(s); while (p){Push(s,p->data);p=p->next;} while (!StackEmpty(s)){Pop(s,x);printf("%d ",x);} } 16.假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 解： typedef struct { ElemType *base;//动态分配存储空间 int length;//队列长度 i nt rear;//尾指针，指向队列尾元素 }SqQueue; int EnQueue(SqQueue &Q,ElemType x){ //带length域的循环队列入队算法 if(Q.length==MAX)return ERROR;//队列满 Q.rear=(Q.rear+1)%MAX; Q.base[Q.rear]=x; Q.length++; return OK; } int DeQueue(SqQueue &Q,ElemType &x){ //带length域的循环队列出队算法 int head; if(Q.length==0)return ERROR;//队列空 head=(Q.rear-Q.length+1)%MAX; x=Q.base[head]; Q.length--; return OK; } int InitQueue(SqQueue &Q){//构造一个空循环队列Q Q.base=new ElemType[MAX]; if(!Q.base)exit(OVERFLOW); Q.rear=0; Q.length=0; return OK; }