数据结构课程设计

一、设计思想。

一）中缀转后缀的设计思想。

设计一个能实现表达式自动求值计算，算术表达式由操作数、算符和括号组成。由于运算符的优先级不同还要考虑括号。所以表达式不可能一直的从左到右进行，所以就借助栈来实现这个表达式的求值。

首先要把算术表达式变换成与之等值的无括号表达式，也就是中缀转后缀，它也是这个算法的关键。设计两个栈，一个为字符型的，存放运算符，用以将算术表达式变成无括号的表达式；另一个浮点型的，存放操作数，用以对无符号的表达式进行求值。我们要假设运算符的优先级首先将一左括号‘(’入栈，作为栈底元素；接着从左到右对算术表达式进行扫描。

每次读一位，若遇到左括号‘（’则进栈；若遇到的是操作数，则立即输出；若又遇到运算符，如果它的优先级比栈顶元素的优先级数高的话，则直接进栈，否则输出栈顶元素，直到新的栈顶元素的优先级数比它低的，然后将它压栈；若遇到是右括号‘）’则将栈顶的运算符输出，直到栈顶的元素为‘（’然后，左右括号互相底消；到设计的结束标志的时候表示表达式已经扫描完毕，表达式已经全部输入，将栈中的运算符全部输出，删除栈底的左括号。以上完成了中缀表达式转后缀表达式，输出无括号的后缀表达式。

读后缀表达式，若遇数值，操作数进栈；若遇运算符，让操作数栈的栈顶和次栈顶依次出栈并与此运算符进行运算，运算结果入操作数栈；重复这个步骤，直到遇到结束标志，则此时栈中的结果便是所求的后缀表达式的值，接着输出结果。以上就是设计这个算法的主要的思想。

(二) 直接计算的设计思想。

直接计算其实跟上一个相似，它是在上面扫两遍的思想进行修改的得来。

首先，要建立两个栈，一个为字符型的，存放运算符，另一个浮点型的，存放操作数，我们开始对表达式进行扫描。首先要确定运算符的优先级如果扫描到的是数字符号，把它们转换成浮点型数据或其他可运算的数据类型，存入操作数栈中。如果扫描到的是运算符号，第一个运算符进栈，遇到‘（’存入运算符栈中，我们按照第一种算法的方法将表达式依次扫描。

只不过不同的是，当每取得的一个运算符的时候，都要与栈顶的运算符进行比较，如果它的优先级小于栈顶运算符优先级时，取出栈顶运算符并从操作数栈中取栈顶两个数进行运算，得到的结果则要存回操作数栈，就这样边扫描边比较，再进行计算。遇到“）”对运算符的处理相同。扫描结束后，把运算符栈的元素和操作数栈里的数进行运算。

每次的运算结果再放入操作数栈，一直到计算到运算符栈空。最后操作数栈的栈顶留下的操作数即表达式的计算结果。以上就是直接计算表达式的思路。

二、算法流程图。

一）中缀转后缀算法的流程图。

图1中缀转后缀算法的流程图。

流程图说明：该流程图分两部分成，第一部分是中缀转后缀部分，第二部分是用于后缀表达式求值的。

二）直接计算算法的流程图。

图2接计算算法的流程图。

流程图说明：该流程图进过图1 改进得到，只是缺少中缀转后缀的部分。

三、源**。

下面给出的是用中缀转后缀算法实现的程序的源**：

#include <>

#define n 50

typedef struct stackarray

elseint pushchar(stackchar *p,char value) /操作符入栈*/

if(p->top<50-1)

elseint popnum(stackarray *p,float *value) /操作数出栈*/

if(p->top>=0) /判断栈是否为空*/

return 1;

int popchar(stackchar *p,char *q) /操作符出栈函数*/

if(p->top>=0) /定义操作符栈*/

return 1;

float visitnum(stackarray *p) /定义数值栈遍历函数*/

if(p->top!=-1)

return p->data[p->top];

else return 0;

char visitchar(stackchar *p) /定义操作符栈遍历函数*/

if(p->top!=-1)

return p->data[p->top];

else return 0;

int level(char c优先级*/

switch(c)

int strlen(char *l) /字符串长度函数*/

int i;

for(i=0;l[i]!=0';i++)循环条件*/

if(l[0]==l[0]==

i=i-1;

return i;

float compute(float a,char c,float b) /计算*/

switch(c)

void main()

stackarray *data;

stackchar *op;

int i,j=0;

float n;

float result,opa,opb;

char opchar;

char array[n];

char *ptarray=null; /定义指针*/

float houzhui[n];

printf("please enter a data:\t");

while((scanf("%s",array))!eof) /循环条件*/

op=initchar();

data=initnum();

pushchar(op,'#

array[strlen(array结束标志*/

ptarray=array;

for(i=0;i

if(array[i]>=48&&array[i]<=57||array[i判断数值。

double weight=0.1;

int flag=0; /定义变量*/

float n=0; /定义变量*/

n=array[i]-48;

while(array[i+1]>=48&&array[i+1]<=57||array[i+1判定数值*/

if(array[i+1小数*/

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了