数据结构实验报告二

姓名：李娜

学号：1062810208 一、问题描述

1、阅读并完善程序

a、顺序栈实验：阅读下面的程序，编写一个主函数，测试程序代码的正确性。

b、循环队列实验：参照教材所给出的循环队列的实现，以模板的方式，进行编码、调 试、测试。

2、设计实验

栈的应用实验--表达式求值

二、问题分析

使用栈作为辅助工具，编程实现一位整数的四则混合运算。例如：2*(3+5) - 6 的值是10。

表达式求值，一般采用两种方法： 其一：直接模仿手工计算表达式值的过程。

其二：首先将普通表达式转换成后缀表达式，然后对后缀表达式求值。 本实验对第二种方法的实现给予提示。

① 从键盘输入表达式，将其存储在一个字符串中。例如 char exp[]=\"2*(3+5) - 6#\" 这里，#是表达式结束符。

② 将普通表达式exp[]的内容转换为后缀表达式postexp[]。 ③ 对后缀表达式postexp[]求值。

三、算法设计

算法设计中，主要是在表达式求值中比较重要，在表达式求值中，对于运算符的优先顺序是很重要的，这个问题是很重要的。我采用的是按顺序进行计算，将数据和运算符分别存放在两个栈里，然后再进行计算。

四、主要源程序

1、主函数：

#include #include\"循环队列.h\" #include\"栈.h\"

int Compute(char a,char b,char c) { if(c=='+') return a+b; if(c=='-') return a-b; if(c=='*') return a*b; if(c=='/') return a/b; }

int Priority(char a,char b) { if(a=='(') return 0; else if(b==')') return 1; else if(a=='*' && (b=='+' || b=='-')) return 1; else if(a=='/' && (b=='+' || b=='-')) return 1; else if(a=='+'&&(b=='*'||b=='/')) return 0; else if(a=='-'&&(b=='*'||b=='/')) return 0; else if(a=='+' && b=='-') return 1; else if(a=='-' && b=='+') return 1; else if(a=='+' && b=='+') return 1; else if(a=='*' && b=='*') return 1; else if(a=='/' && b=='/') return 1; else if(a=='-' && b=='-')

return 1; else if(a=='*' && b=='/') return 1; else if(a=='/' && b=='*') return 1; else if(a=='#') return 0; // else // return 1; }

void Result(char a[],int t) { char b; int i=0,j=0; int x,y,result=0,resu=0; Stack data(20); Stack operate(20);

/* cout<<\"输入的表达式为:\"<='0' && a[i]<='9') { data.Push_1((int)(a[i]-48)); } else { if(a[i]=='#' && operate.GetTop()=='#') { result=data.GetTop();// break; } if(a[i]=='#') {

while(operate.GetTop()!='#') { x=data.Pop_1(); y=data.Pop_1(); result=Compute(y,x,operate.Pop_1()); cout<<\"中间结果：\"<break; }

if(Priority(operate.GetTop(),a[i])==0) { if(operate.GetTop()==')') { operate.Pop_1(); operate.Pop_1(); i=i-1; continue; } operate.Push_1(a[i]); } else { x=data.Pop_1(); y=data.Pop_1(); cout<<\"中间结果：\"<operate.Push_1(a[i]); if(operate.GetTop()==')') { operate.Pop_1(); operate.Pop_1(); } } else{ x=data.Pop_1(); y=data.Pop_1(); cout<<\"中间结果：\"</////////////////////////////////////////////////// //////////////////////////////////////////////// void main() { cout<<\"*********************************************\"< *s = new Stack(); for(int i=0; i<10; i++ ) s->Push (i);

int num; while(!s->IsEmpty()) { s->Pop(num); cout<cout<<\"*********************************************\"< Q; int j,num1; cout<<\"输入进队的元素为:\"<>num1; if(Q.Outq(num1)==-1) { cout<<\"q请重新输入，该队列里没有该数！\"<cout<<\"*********************************************\"<cout<<\"请输入表达式（注释：以输入#结束）:\"<>a; str[k]=a; k++; } Result(str,k); //调用函数Result，来求解表达式的值 }

2、顺序栈：

//顺序栈的定义与实现 //顺序栈的定义与实现 #include #include template class Stack {

protected:

int top; //栈顶指针 Type *elements; //栈元素数组 int maxSize; //栈最大容量 public:

Stack ( int sz = 10 ); //构造函数 ~Stack ( ) { delete [ ] elements; }

void Push ( Type & item ); //进栈 void Push_1 ( Type item ); //用于表达式求值

int Pop( Type & item); //出栈 int Pop_1 () ; //用于表达式求值

Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ) { top = -1; } //置空栈 int IsEmpty ( ) const { return top == -1; } int IsFull ( ) const

{ return top == maxSize-1; } };

///////////////////////////

template

Stack ::Stack ( int s ) : top (-1), maxSize (s) {

elements = new Type[maxSize];

assert ( elements != NULL ); //断言，关于断言的使用，见这儿 }

///////////////////////////////

template

void Stack ::Push ( Type & item ) {

assert ( !IsFull ( ) ); //先决条件断言 elements[++top] = item; //加入新元素 } ;

template

void Stack ::Push_1 ( Type item ) {

assert ( !IsFull ( ) ); //先决条件断言 elements[++top] = item; //加入新元素 } ;

/////////////////////////

template

int Stack ::Pop (Type &Item ) {

if ( IsEmpty ( ) ) return 0; //栈空不退栈 Item=elements[top]; top--;

return 1; //退出栈顶元素 };

template int Stack ::Pop_1 () { Type Item ;

if ( IsEmpty ( ) ) return 0; //栈空不退栈 Item=elements[top]; top--;

return Item; //退出栈顶元素}

****** /////////////////////////////////////////////////////////

template

Type Stack::GetTop ( ) {

assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top]; //取出栈顶元素 };

/////////////////////////////////////////////////////////

3、队列

#include #include template class Queue {

protected:

int front,rear; T *data; //表示元素数组 int maxSize;

int count; //队列中实际元素个数 public: Queue ( int sz = 10 ) { maxSize=sz; data=new T[maxSize];//new 用来动态存储分配，运算符返回一个指向所分配空间的指针,动态创建数组 assert (data!= NULL ); count=front=rear=0; }; ~Queue ( ) { delete [] data; }

void Enq (T & item ); //在队尾插入一个元素 int Outq( T & item); //输出队列元素 void MakeEmpty ( ); //置空 int IsEmpty ( ); //判断是否为空 int IsFull ( ); //判断是否溢出 };

/////////////////////////////////////

//在队尾插入一个元素 template

void Queue::Enq(T &item ) { rear=(rear+1)%maxSize; //队尾指针在循环意义下加1 data[rear]=item; count++; };

/////////////////////////////////////// //输出队列元素 template

int Queue::Outq(T & item) { int i; if(IsEmpty()) for(i=0;i/////////////////////////////////////

template

void Queue::MakeEmpty() { front=rear=0; };

///////////////////////////////////////

template

int Queue::IsEmpty() { if(front!=rear) return 1; else return 0; };

/////////////////////////////////////////

template int Queue::IsFull() { if((rear+1)%maxSize==front) return 1; else return 0; };

/////////////////////////////////////

五、程序调试及记录

1、验证性试验的调试

2、表达式求值的调试

六、心得体会

通过这次实验，我对栈和队列的算法以及如何使用有了更进一步的了解，对于如何进行表达式求值，本来打算是采用将表达式转换为后缀形式然后再进行求值的方式的，可是因为自己对栈的概念因为理解的不透彻，所以只能选择放弃，由此我深刻的了解到自己的不足，对栈的算法了解的还不够透彻。所以通过这次试验，我找到了自己的不足，并且通过本次试验，自己也正在努力改进中。