精心整理

（3）设从键盘输入一整数的序列：a1,a2,a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 #definemaxsize栈空间容量 voidInOutS(ints[maxsize])

//s是元素为整数的栈，本算法进行入栈和退栈操作。 {inttop=0;//top为栈顶指针，定义top=0时为栈空。 for(i=1;i<=n;i++)//n个整数序列作处理。 {scanf(“%d”,&x);//从键盘读入整数序列。 if(x!=-1)//读入的整数不等于-1时入栈。

if(top==maxsize-1){printf(“栈满\\n”);exit(0);}elses[++top]=x;//x入栈。 else//读入的整数等于-1时退栈。

{if(top==0){printf(“栈空\\n”);exit(0);}elseprintf(“出栈元素是%d\\n”,s[top--])；}} }//算法结束。 （4）从键盘上输入一个后缀表达式，试编写算法计算表达式的值。规定：逆波兰表达式的长度不超过一行，以$符作为输入结束，操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如：23434+2*$。

[题目分析]逆波兰表达式(即后缀表达式)求值规则如下：设立运算数栈OPND,对表达式从左到右扫描(读入)，当表达式中扫描到数时，压入OPND栈。当扫描到运算符时，从OPND退出两个数，进行相应运算，结果再压入OPND栈。这个过程一直进行到读出表达式结束符$，这时OPND栈中只有一个数，就是结果。 floatexpr() //从键盘输入逆波兰表达式，以‘$’表示输入结束，本算法求逆波兰式表达式的值。 ｛floatOPND[30];//OPND是操作数栈。 init(OPND);//两栈初始化。 floatnum=0.0;//数字初始化。 scanf(“%c”,&x);//x是字符型变量。 while(x!=’$’) {switch {case‘0’<=x<=’9’:while((x>=’0’&&x<=’9’)||x==’.’)//拼数 if(x!=’.’)//处理整数 {num=num*10+（ord(x)-ord(‘0’)）;scanf(“%c”,&x);} else//处理小数部分。 {scale=10.0;scanf(“%c”,&x); while(x>=’0’&&x<=’9’) {num=num+(ord(x)-ord(‘0’)/scale; scale=scale*10;scanf(“%c”,&x);} }//else push(OPND,num);num=0.0;//数压入栈，下个数初始化 casex=‘’:break;//遇空格，继续读下一个字符。 casex=‘+’:push(OPND,pop(OPND)+pop(OPND));break;

casex=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; casex=‘*’:push(OPND,pop(OPND)*pop(OPND));break;

casex=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default://其它符号不作处理。 }//结束switch

scanf(“%c”,&x);//读入表达式中下一个字符。 }//结束while（x！=‘$’）

printf(“后缀表达式的值为%f”,pop(OPND)); 精心整理

精心整理

}//算法结束。

[算法讨论]假设输入的后缀表达式是正确的，未作错误检查。算法中拼数部分是核心。若遇到大于等于‘0’且小于等于‘9’的字符，认为是数。这种字符的序号减去字符‘0’的序号得出数。对于整数，每读入一个数字字符，前面得到的部分数要乘上10再加新读入的数得到新的部分数。当读到小数点，认为数的整数部分已完，要接着处理小数部分。小数部分的数要除以10（或10的幂数）变成十分位，百分位，千分位数等等，与前面部分数相加。在拼数过程中，若遇非数字字符，表示数已拼完，将数压入栈中，并且将变量num恢复为0，准备下一个数。这时对新读入的字符进入‘+’、‘-’、‘*’、‘/’及空格的判断，因此在结束处理数字字符的case后，不能加入break语句。

（5）假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

①下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO ②通过对①的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。 ①A和D是合法序列，B和C是非法序列。 ②设被判定的操作序列已存入一维数组A中。 intJudge(charA[]) //判断字符数组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){printf(“序列非法\\n”)；exit(0);} }

i++;//不论A[i]是‘I’或‘O’，指针i均后移。} if(j!=k){printf(“序列非法\\n”)；return(false);} else{printf(“序列合法\\n”)；return(true);} }//算法结束。 [算法讨论]在入栈出栈序列（即由‘I’和‘O’组成的字符串）的任一位置，入栈次数（‘I’的个数）都必须大于等于出栈次数（即‘O’的个数），否则视作非法序列，立即给出信息，退出算法。整个序列（即读到字符数组中字符串的结束标记‘\\0’），入栈次数必须等于出栈次数（题目中要求栈的初态和终态都为空），否则视为非法序列。 (6）假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针)，试编写

相应的置空队、判队空、入队和出队等算法。?

算法如下：

//先定义链队结构:

typedefstructqueuenode{

Datatypedata;

精心整理

精心整理

structqueuenode*next;

}QueueNode;//以上是结点类型的定义

typedefstruct{

queuenode*rear;

}LinkQueue;//只设一个指向队尾元素的指针

(1)置空队 voidInitQueue(LinkQueue*Q) {//置空队：就是使头结点成为队尾元素 QueueNode*s; Q->rear=Q->rear->next;//将队尾指针指向头结点 while(Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next; Q->rear->next=s->next; free(s);

}//回收结点空间

}

精心整理

精心整理

(2)判队空?

intEmptyQueue(LinkQueue*Q)

{//判队空

//当头结点的next指针指向自己时为空队

returnQ->rear->next->next==Q->rear->next;

}

(3)入队 voidEnQueue(LinkQueue*Q,Datatypex) {//入队 //也就是在尾结点处插入元素 QueueNode*p=(QueueNode*)malloc(sizeof(QueueNode));//申请新结点 p->data=x;p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;? Q->rear=p;//将尾指针移至新结点 }

(4)出队

DatatypeDeQueue(LinkQueue*Q)

精心整理