数据结构实验报告(3)

八．实验小结

通过这次实验，掌握了线性表的定义，顺序存储及链式存储的方法及基本操作。学会了利用线性表的顺序存储结构完成一些数据的管理，实现数据通信元素的增加，删除等运算。

11

南昌大学实验报告

---（2）栈和队列

学生姓名： 学 号： 专业班级：

实验类型：□ 验证 □ 综合 ■ 设计 □ 创新 实验日期： 2010-4-5 实验成绩：

一．实验目的

深入了解栈和队列的特性，学会在实际问题下灵活运用它们。

二．问题描述

表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。

三．实验要求

1．算法优先级别如下：

'+', '-', '*', '/', '(', ')', '#' '+' '>', '>', '<', '<', '<', '>', '>', '-' '>', '>', '<', '<', '<', '>', '>', '*' '>', '>', '>', '>', '<', '>', '>', '/' '>', '>', '>', '>', '<', '>', '>', '(' '<', '<', '<', '<', '<', '=', ' ', ')' '>', '>', '>', '>', ' ', '>', '>', '#' '<', '<', '<', '<', '<', ' ', '='

2．以字符序列的形式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。

四．实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境

五．实验步骤

1． 根据给出的算符优先级，设置运算符栈和运算数栈；

2． 在读入表达式的同时，完成运算符和运算数的识别处理，并将运算数的字符序列形式转换成整数形式，并进行相应的运算；

3． 调试程序，检查输出结果； 4． 实验小结。

12

六．测试数据

1．输入数据：1+（20+4）/（4-1） 正确结果：9

2．输入数据：2*9-6-（20+4）/（4-1） 正确结果：4

七．实验结果

C程序：#include #include //typedef char char; typedef int status; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define stack_init_size 100 #define stack_increament 50 typedef struct{ char * base; char * top; int stacksize; int length; }charstack;

//----------------------------------

status InitStack(charstack & S){

S.base=(char *)malloc(stack_init_size*sizeof(char)); if(!S.base)return OVERFLOW; S.stacksize=100; S.length=0; S.top=S.base; }

status Push(charstack & S,char e){

13

if(!&S)return ERROR;

if(S.length==S.stacksize){//若存储空间不够则重新分配 char * newbase;

newbase=(char *)realloc(S.base,(S.stacksize+stack_increament)); if(!newbase)return OVERFLOW; S.base=newbase; }

*(S.top)=e;S.top++;S.stacksize++;//元素带入 return OK; }

status Pop(charstack &S,char &e){ if(!&S)return ERROR;

if(S.top ==S.base)return ERROR; e=*(S.top-1);S.top--;S.stacksize--; return OK; }

status FreeStack(charstack &S) {if(!&S)return ERROR; free(S.base); return OK; }

char GetTop(charstack &S){ char e;

if(S.top==S.base) return ERROR; e=*(S.top -1); return e; }//gettop

#include \#include \#include #include #include #include #define OPSETSIZE 7

14

unsigned char Prior[7][7] = { //用二维数组表示表

'>','>','<','<','<','>','>',

'>','>','<','<','<','>','>', '>','>','>','>','<','>','>', '>','>','>','>','<','>','>', '<','<','<','<','<','=',' ', '>','>','>','>',' ','>','>', '<','<','<','<','<',' ','=' };

char OP[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'};//算符集合

float Operate(float a,unsigned char theta, float b) { switch(theta) { case '+': return a+b; case '-': return a-b; case '*': return a*b; case '/': return a/b; default : return 0; } }//运算函数

status In(char Test,char* TestOp) { bool Find=false;

for (int i=0; i< OPSETSIZE; i++) { if (Test == TestOp[i]) Find= true; }

return Find; }//判断是否为运算符

int ReturnOpOrd(char op,char* TestOp) { int i;

for(i=0; i< OPSETSIZE; i++) { if (op == TestOp[i]) return i; }

15