《数据结构》课件附录A

附录A课程设计指导问题1：设计一程序，要求从键盘上输入一个只含加、减、乘、除等四种运算符的算术表达式，便可计算表达式的结果。

解：本题的求解如下。

1.相关知识要对一个表达式求值，首先要了解算术四则运算的规则。即：

(1)先乘除，后加减。

(2)同级运算，从左到右。

(3)先括号内，后括号外。因此，例如求解表达式4 + 5 × (6-2) + 8，根据运算规则，这个表达式的计算顺序应为

4 + 5 × (6-2) + 8

=4 + 5 × 4 + 8

=4 + 20 + 8

=24 + 8

=32这种根据运算符的优先关系来实现对表达式求值的方法称为“算符优先法”。任何一个表达式都是由操作数、算符组成的。一般地，操作数既可以是常数也可以是被说明为变量或常量的标识符。算符包括运算符和界符两种，其中运算符又可以分为算术运算符、关系运算符和逻辑运算符等三类，基本界符有左右括号和表达式结束符等。为了叙述的简洁，我们仅讨论简单算术表达式的求值问题。这种表达式只含加、减、乘、除等四种运算符。根据上述的三条运算规则，我们可以把算符的优先级从高到低排列出来为：左括号→乘、除→加、减→右括号。因此，在运算的每一步中，任意两个相继出现的算符a和b，至多是下面三种关系之一：

a＜ba的优先级低于b

a＝ba的优先级等于b

a＞ba的优先级高于b

2.算法分析为实现算符优先算法，使用两个工作栈。一个称做算符栈tr，用以存放算符；另一个称做操作数栈nd，用以存放操作数或运算结果。

(1)首先置操作数栈和算符栈为空栈。

(2)读入表达式，用一个指针指向该表达式的每个字符，若是操作数，则进nd栈，若是算符，则与tr栈的栈顶算符比较优先级后做相应操作，直到整个表达式求值完毕(即tr栈为空)。

3.程序实现

#include<stdio.h>

#include<stdlib.h>

#include<io.h>

#include<string.h>

#defineMAX20

structst_optr /*算符栈的描述*/{charelem[MAX+1];inttop;};structst_opnd /*操作数栈的描述*/{floatelem[2*MAX];inttop;};structst_optrtr;structst_opndnd;charaa[30]; /*定义一个全程变量，用以存放输入的表达式*/intflag=1; /*标志变量值为0则说明表达式已求解完毕*/voidpush_r(chare) /*算符进栈函数*/{if(tr.top==MAX){printf("内存不够!\n");exit(-2);}else{tr.top=tr.top+1;tr.elem[tr.top]=e;

}}

voidpush_d(floatm) /*操作数进栈函数*/{

if(nd.top==2*MAX-1){printf("内存不够!\n");exit(-2);}else{nd.top=nd.top+1;nd.elem[nd.top]=m;}}charpop_r() /*算符出栈函数*/{

chare; if(tr.top>0) {

e=tr.elem[tr.top];

tr.top=tr.top-1;returne;}elsereturnNULL;}chargettop_r() /*取算符栈栈顶元素的函数*/{ chare; if(tr.top>0){

e=tr.elem[tr.top];

returne;}elsereturnNULL;}floatpop_d() /*操作数出栈函数*/{ floatm; if(nd.top>0){m=nd.elem[nd.top];nd.top=nd.top-1;returnm;}elsereturnNULL;}voidcount() /*运算函数*/{floatn1,n2;charop;/*取得两操作数*/n2=pop_d();n1=pop_d();op=pop_r(); /*取得运算符*/switch(op){case'+':n1=n1+n2;break;case'-':n1=n1-n2;break;case'*':n1=n1*n2;break;case'/':n1=n1/n2;break;}push_d(n1); /*将运算的中间结果进栈保存*/}voidstch(char*bb,charitem)

/*数值型字符串形成函数*/{char*ee;ee=bb+strlen(bb);*ee=item,ee++;*ee='\0';}inttest(char*qq)

/*测试运算是否结束，并显示最终结果*/{

intkk;kk=strlen(aa);if((qq<aa+kk)) /*若还未扫描完毕*/return1; /*返回1，表示应继续扫描*/while(tr.top!=0) /*若表达式已全部扫描完，并且算符栈中还有运算符*/count(); /*则执行最后一次运算*/printf("数学表达式%s==%f\n",aa,nd.elem[1]);

/*显示最后的计算结果*/flag=0; /*修改标志变量，以结束程序的运行*/}main(){intyy=0;charch,bb[10]="",*sp,*qq;/*设置两个栈为空*/tr.top=0;nd.top=0;sp=aa; /*让字符指针sq指向表达式的第一个字符*/printf("请输入表达式：\n");gets(sp); /*接收表达式*/for(;flag!=0;sp++){yy=0; if(*sp=='') /*去除表达式中的空格*/continue; while(*sp>='0'&&*sp<='9')

/*若扫描到的是数字字符*/{yy=1;stch(bb,*sp);

/*则去形成数字字符串*/ sp++;}/*while*/if(yy==1) /*如果刚处理的是数字字符串*/{

qq=sp;sp--;push_d(atoi(bb));

/*将数字字符串转换为数值后进操作数栈*/bb[0]='\0';if(test(qq))

/*测试表达式是否扫描完毕*/continue;}

if(*sp<‘0’||*sp>‘9’) /*若扫描到的字符不是数字，则进行判断*/ch=*sp;switch(ch){case'(':qq=sp; /*若是'('算符*/push_r(ch); /*则进算符栈保存*/test(qq);break;case'*':case'/':while(gettop_r()=='*'||gettop_r()=='/')

/*若栈中有乘或除运算符*/count();

/*则先去计算栈中的乘法或除法*/qq=sp;push_r(ch);

/*将这次扫描得到的运算符进栈，以便下次运算*/test(qq);break;case'+':case'-':while(gettop_r()!='('&&tr.top>0)/*若是加法或减法运算符，则只要算符栈中有运算符，并已不是'('运算符。*/

count();

/*则去计算原来栈中的运算*/qq=sp;push_r(ch);

/*保存这次的运算符*/test(qq);break;case')':while(gettop_r()!='(')

/*若扫描到的是')'，且算符栈中有其他运算符*/count(); /*则去计算原来栈中的运算*/pop_r(); /*消去一对括号*/qq=sp+1;test(qq);break;default:printf("输入错误！\n");exit(-1);

/*中断程序的执行*/}/*switch*/}/*for*/}/*main*/问题2：在有n个选手P1，P2，P3，…，Pn参加的单循环赛中，每对选手之间非胜即负。现要求求出一个选手序列，，，…,，，使其满足胜(i = 1，…，n-1)。解：本题的求解如下：

1.模型表示由于仅涉及到n个选手，并且这些选手之间的关系仅是胜负关系，因此可用图来表示。

(1)用顶点表示选手。

(2)用弧表示选手之间的胜负关系：当且仅当Pi胜Pj时，有从顶点i到j的一条弧。在这种表示下，本题变成了在有向图中求解出一条包含所有顶点的简单路径的问题。附图1所示为一个有8个选手的问题的一个示例，其中的一个解为1,2,3,4,8,6,5,7。附图18个选手比赛情况示例

2.算法设计

(1)设计本题算法的构思：为搜索出符合条件的简单路径，需按深度优先搜索方式进行遍历。因此求解算法应是深度遍历算法的变形形式，也应是递归形式的算法。由于要求遍历序列中的各结点按次序构成一条简单路径，因此算法与深度遍历算法有明显的不同：并非任意选择的起点和访问次序都能得到解。而这些又是事先难以确定的。这就要求在求解过程中进行试探：试探起点以及访问次序。既然要在求解过程中进行试探，则需要记录试探的中间状态：某顶点是否在当前试探的路径中，已经试探的各顶点的次序，当前正在试探的顶点等。

(2)将所用到的变量及有关参数设置如下：①设图为g。②设当前试探路径中最后的顶点号为v。③ v在试探路径中的序号为k。④用int型数组visited[n+1]表示各顶点是否在当前试探的路径中(初值为全0)。⑤用数组B[n+1]存储当前路径中的各顶点(在前k个元素中，事实上应是栈)。

(3)可能情况的处理：既然是试探型求解，则需对当前顶点v的每个邻接点(不妨用w表示)进行试探，试探由v经w往下是否可以得到解。每个w都可能有成功(指现在可以将该顶点放在路径上，这包括暂时的和最终的)与失败(指此路不通)两种情况，对此应分别作不同的处理：①若试探成功，则应将w放入路径中，并置相应的状态值。然后再由w往下求解。②若不成功，则应恢复w的有关信息，以使w在试探其它路径时成为可选顶点。为了能求出解以及所有可能的解，需要做如下两方面的工作：①选择起点：应以每个顶点为起点进行搜索。②搜索路径：在从v往下搜索时，应依次选择v的所有不在当前试探路径中的邻接点往下搜索。为此，需要有这方面的保证：应在试探某顶点w后并在换下一个试探顶点前恢复w的有关状态，以使其仍为可选择的顶点。

(4)本算法的基本思想：①若k = n，则说明已经求得一解，因此可输出结果，并结束本次调用。②若k＜n，则依次选择v的所有不在当前试探路径中的邻接点w往下搜索，这包括以下的操作：试探：将w放到B[k + 1]中，并置visited[w]为1，然后以w为起点往下搜索。恢复：将w恢复为不在当前路径中，以使其在试探其它路径时可用。

(5)有关算法中的变量设置：可将上述讨论中所提及的变量k、v作为参数(仅提供值而不返回值)，将g作为地址传送型参数(虽然不会改变其值，但这种形式更节省时间和空间)，将数组B和visited作为全程变量，以便各调用层能共享，并节省时间、空间，同时使程序更清晰。

3.程序实现为上机实现