数据结构与算法习题及答案 下载本文

内容发布更新时间 : 2024/12/23 12:49:31星期一 下面是文章的全部内容请认真阅读。

精心整理

(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)

精心整理