第3章习题答案

第3章 栈与队列

}

}//F_nonrecursive

11.试将下列递归函数改为非递归函数。 void test(int &sum){ int x;

scanf(\ if(x==0)sum=0;

else{test(sum);sum+=x;} printf(\} 解： void test(){

int x,sum=0,top=-1,s[10]; scanf(\

while(x!=0){s[++top]=x; scanf(\ printf(\

while(top>-1){sum+=s[top--]; printf(\};

12.设整数列p1，p2，…，pn，给出求解最大值的递归程序。 解：

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.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设头指针)，试编写相应的队列初始化、入队和出队的算法。

解：

5

while(!StackEmpty(T)){

Pop(T,t); s*=t.a;

}//while

第3章 栈与队列

(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\ 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())!='@'){

6

第3章 栈与队列

}

while(!StackEmpty(S)){ }

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(\}

16.假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

解：

typedef struct {

ElemType *base;//动态分配存储空间 int length;//队列长度

int 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;

7

Push(S,c);EnQueue(Q,c); //同时使用栈和队列两种结构

Pop(S,a); DeQueue(Q,b);

if(a!=b) return ERROR;

第3章 栈与队列

}

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; }

8