else //处理小数部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’)
{num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; cin>>x; } }//else
push(OPND,num); num=0.0;//数压入栈，下个数初始化
case x=‘ ’:break; //遇空格，继续读下一个字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break;
case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND,pop(OPND)*pop(OPND));break;
case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符号不作处理。 }//结束switch
cin>>x;//读入表达式中下一个字符。 }//结束while（x！=‘$’）
cout<<“后缀表达式的值为”< [算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。 （5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 答案： ①A和D是合法序列，B和C 是非法序列。 ②设被判定的操作序列已存入一维数组A中。 int Judge(char A[]) //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true，否则返回false。 {i=0; //i为下标。 j=k=0; //j和k分别为I和字母O的的个数。 while(A[i]!=‘\\0’) //当未到字符数组尾就作。 {switch(A[i]) {case‘I’: j++; break; //入栈次数增1。 case‘O’: k++; if(k>j){cout<<“序列非法”< } i++; //不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k) {cout<<“序列非法”< [算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。 (6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 [题目分析] 置空队就是建立一个头节点，并把头尾指针都指向头节点，头节点是不存放数据的；判队空就是当头指针等于尾指针时，队空；入队时，将新的节点插入到链队列的尾部，同时将尾指针指向这个节点；出队时，删除的是队头节点，要注意队列的长度大于1还是等于1的情况，这个时候要注意尾指针的修改，如果等于1，则要删除尾指针指向的节点。 [算法描述] //先定义链队结构: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是结点类型的定义 typedef struct {queuenode *rear; }LinkQueue; //只设一个指向队尾元素的指针 (1) 置空队 void InitQueue( LinkQueue *Q) { //置空队：就是使头结点成为队尾元素 QueueNode *s; Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; delete s; }//回收结点空间 } (2) 判队空 int EmptyQueue( LinkQueue *Q) { //判队空。当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; } (3) 入队 void EnQueue( LinkQueue *Q, Datatype x) { //入队。也就是在尾结点处插入元素 QueueNode *p=new QueueNode;//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p; Q->rear=p;//将尾指针移至新结点 } (4) 出队 Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error(\ p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear) {//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next; } else Q->rear->next->next=p->next;//摘下结点p delete p;//释放被删结点 return x; } （7）假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 [算法描述] (1)初始化 SeQueue QueueInit(SeQueue Q) {//初始化队列 Q.front=Q.rear=0; Q.tag=0; return Q; } (2)入队 SeQueue QueueIn(SeQueue Q,int e) {//入队列 if((Q.tag==1) && (Q.rear==Q.front)) cout<<\队列已满\ else {Q.rear=(Q.rear+1) % m; Q.data[Q.rear]=e; if(Q.tag==0) Q.tag=1; //队列已不空 } return Q; } (3)出队 ElemType QueueOut(SeQueue Q) {//出队列 if(Q.tag==0) { cout<<\队列为空\else {Q.front=(Q.front+1) % m; e=Q.data[Q.front]; if(Q.front==Q.rear) Q.tag=0; //空队列 } return(e); } (8）如果允许在循环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出“从队尾删除”和“从队头插入”的算法。 [题目分析] 用一维数组 v[0..M-1]实现循环队列，其中M是队列长度。设队头指针 front和队尾指针rear，约定front指向队头元素的前一位置，rear指向队尾元素。定义front=rear时为队空，(rear+1)%m=front 为队满。约定队头端入队向下标小的方向发展，队尾端入队向下标大的方向发展。 [算法描述] ① #define M 队列可能达到的最大长度 typedef struct {elemtp data[M]; int front,rear; }cycqueue; ② elemtp delqueue ( cycqueue Q) //Q是如上定义的循环队列，本算法实现从队尾删除，若删除成功，返回被删除元素，否则 给出出错信息。 {if (Q.front==Q.rear) { cout<<\队列空\Q.rear=(Q.rear-1+M)%M; //修改队尾指针。 return(Q.data[(Q.rear+1+M)%M]); //返回出队元素。 }//从队尾删除算法结束 void enqueue (cycqueue Q, elemtp x) // Q是顺序存储的循环队列，本算法实现“从队头插入”元素x。 {if (Q.rear==(Q.front-1+M)%M) { cout<<\队满\ Q.data[Q.front]=x; //x 入队列 Q.front=(Q.front-1+M)%M; //修改队头指针。 }// 结束从队头插入算法。 （9）已知Ackermann函数定义如下: ① 写出计算Ack(m,n)的递归算法，并根据此算法给出出Ack(2,1)的计算过程。 ② 写出计算Ack(m,n)的非递归算法。 [算法描述] 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)); }//算法结束 ① Ack(2,1)的计算过程 Ack(2,1)= Ack(1,Ack(2,0)) //因m<>0,n<>0而得 ② int Ackerman(int m, int n) {int akm[M][N];int i,j; for(j=0;j {akm[i][0]=akm[i-1][1]; for(j=1;j akm[i][j]=akm[i-1][akm[i][j-1]]; } return(akm[m][n]); }//算法结束 = 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而得
数据结构 C语言版 第二版(严蔚敏) 第3章 栈和队列 答案
