实验题目

1:依据顺序栈存储结构的定义如下:(利用以下的常用操作设计算法并实现完成2、3题)


#define MAXSIZE 100

typedef char SElemType;

typedef struct

{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;

//调试并测试常用操作如下:

int InitStack( SqStack &S )

int StackEmpty( SqStack S )

int StackLength( SqStack S )

int Push( SqStack &S, SElemType e)

int Pop( SqStack &S, SElemType &e)

2:设单链表中存放n个字符,试设计一个算法,判断该字符串是否中心对称。

3:利用栈来实现算术表达式求值的算法。程序运行时,输入合法的算术表达式(中间值及最终结果要在0~9之间,可以包括加减乘除和括号),便可输出相应的计算结果。

头文件


#ifndef _STACK_H_

#define _STACK_H_



#include <iostream>

#include <cstdlib>

#include <stdio.h>



#define MAXSIZE 100

#define OK 1

#define ERROR 0

#define OVERFLOW -2

typedef int Status;

typedef char SElemType;

using namespace std;



typedef struct//栈结构体

{

SElemType *base;

SElemType *top;

int stacksize;

}SqStack;





typedef struct LNode//单链表结构体

{

SElemType data;

struct LNode *next;

}LNode,*LinkList;



//初始化栈

Status InitStack(SqStack &S){

S.base = new SElemType [MAXSIZE];

if (!S.base)

exit(OVERFLOW);

S.top = S.base;

S.stacksize = MAXSIZE;

return OK;

}



//判断栈满栈空

Status StackEmpty(SqStack S){

if(S.top - S.base == S.stacksize)

return ERROR;

else return OK;

}



//求栈长

int StackLength(SqStack S){

return (S.top - S.base);

}



//入栈函数

Status Push(SqStack &S,SElemType e){

if(StackEmpty(S)){

*S.top++ = e;

return OK;

}

else return ERROR;

}



//出栈函数

Status Pop(SqStack &S,SElemType &e){

if(S.top == S.base)

return ERROR;

e = *--S.top;

return OK;

}



//取栈顶元素

SElemType GetTop(SqStack S){

if(S.top != S.base){

return *(S.top-1);

}

else return ERROR;

}



//创建单链表

void CreateList_L(LinkList &L,int n){

L=new LNode;

L->next=NULL; //先建立一个带头结点的单链表

LinkList p;

// InitList_L(L);

for(int i=n;i>0;--i){

p=new LNode; //生成新结点

cin>>p->data; //输入元素值

p->next=L->next;L->next=p; //插入到表头

}

}

//打印单链表

void PrintList_L(LinkList &L){

LinkList p=L->next;

while(p) {

cout<<p->data<<endl;

p=p->next;

}

}



//单链表删除元素

Status ListDelete(LinkList &L,int i){



LinkList p=L,q;

int j=0;

while((p->next) && (j<i-1)){

p=p->next;

++j;

}

if(!(p->next) || (j>i-1))

return ERROR;

q=p->next;

p->next=q->next;

delete q;

return OK;

}

//获取单链表元素值

Status GetElem(LinkList L,int i,SElemType &e){

LinkList p=L->next;

int j=1;

while (p && j<i){

p=p->next;

++j;

}

if(!p || j>i)

return ERROR;

e=p->data;

return OK;

}



#endif // _STACK_H_



main.cpp


#include "stack.h"



Status TestStack(SqStack &S,SElemType &e);

int Center(LinkList &L,SqStack &S);

char EvaluateExpression ();

SElemType Precede(SElemType t1,SElemType t2);

Status In(SElemType c);

SElemType Operate(SElemType a,SElemType theta,SElemType b);



int main()

{

LinkList L;

SqStack S;

SElemType e;

//SqStack *p = &S;



printf("第1题\n");

TestStack(S,e);

//cout << "" << endl;



printf("第2题\n");

printf("请输入要判断中心对称的字符串,长度为5\n");

CreateList_L(L,5);

ListDelete(L,3);

//PrintList_L(L);

if(Center(L,S))

printf("该字符串不是中心对称的字符串\n");

else

printf("该字符串是中心对称的字符串\n");





printf("第3题\n");

cout<<"请输入算术表达式,并以#结束."<<endl;

cout<<EvaluateExpression()<<endl;





return 0;

}



//栈基础测试函数

Status TestStack(SqStack &S,SElemType &e){

InitStack(S);

cout << "当前栈的长度为:" ;

cout << StackLength(S) << endl;

cout << "请输入将要入栈的元素:" << endl;

cin >> e;

Push(S,e);

cout << "当前栈的长度为:" ;

cout << StackLength(S) << endl;

Pop(S,e);

cout << "出栈:" ;

cout << e <<endl;

cout << "当前栈的长度为:" ;

cout << StackLength(S) << endl;

return OK;

}



//判断是否中心对称

int Center(LinkList &L,SqStack &S){

int i;

SElemType e;

for(i=1;i<=4;i++){

GetElem(L,i,e);

if(e == GetTop(S)){

Pop(S,e);

}else{

Push(S,e);

}

}

if(StackLength(S))

return 1;

return 0;

//GetElem(LinkList L,int i,SElemType &e)

}



char EvaluateExpression() {//算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈



SqStack OPTR, OPND;

char ch, theta, a, b, x;



InitStack(OPND); //初始化OPND操作数栈

InitStack(OPTR); //初始化OPTR运算符栈

Push(OPTR, '#'); //将表达式起始符“#”压入OPTR栈



scanf("%c",&ch);

while (ch != '#' || (GetTop(OPTR) != '#')) //表达式没有扫描完毕或OPTR的栈顶元素不为“#”

{

if (!In(ch)) {

Push(OPND, ch);

scanf("%c",&ch);

} //ch不是运算符则进OPND栈

else

switch (Precede(GetTop(OPTR), ch)) //比较OPTR的栈顶元素和ch的优先级

{

case '<': //栈顶元素优先级低

Push(OPTR, ch);

scanf("%c",&ch); //当前字符ch压入OPTR栈,读入下一字符ch

break;

case '>':

Pop(OPTR, theta); //弹出OPTR栈顶的运算符

Pop(OPND, b);

Pop(OPND, a); //弹出OPND栈顶的两个运算数

Push(OPND, Operate(a, theta, b)); //将运算结果压入OPND栈

break;

case '=': //OPTR的栈顶元素是“(”且ch是“)”

Pop(OPTR, x);

scanf("%c",&ch); //弹出OPTR栈顶的“(”,读入下一字符ch

break;

} //switch

} //while

return GetTop(OPND); //OPND栈顶元素即为表达式求值结果

}



Status In(SElemType c)// 应在前面有定义typedef char SElemType;

{ // 判断c是否为运算符

switch(c)

{

case '+':return true;break;

case '-':return true;break;

case '*':return true;break;

case '/':return true;break;

case '(':return true;break;

case ')':return true;break;

case '#':return OVERFLOW;break;

default:return false;

}

}



SElemType Precede(SElemType t1,SElemType t2)

{ //根据教材表3.1,判断两个运算符的优先关系

SElemType f;

switch(t2)

{

case '+':

if(t1=='('||t1=='#')

f='<';

else

f='>';

break;

case '-':

if(t1=='('||t1=='#')

f='<';

else

f='>';

break;//……//补充完整

case '*':

if(t1=='*' || t1=='/' || t1==')')

f='>';

else

f='<';

break;

case '/':

if(t1=='*' || t1=='/' || t1==')')

f='>';

else

f='<';

break;

case '(':

f='<';

break;

case ')':

if(t1=='(')

f='=';

else

f='>';

break;

case '#':

if(t1=='#')

f='=';

else

f='>';

break;

}

return f;

}



SElemType Operate(SElemType a,SElemType theta,SElemType b)

{

SElemType c;

a=a-48;

b=b-48;

switch(theta)

{

case'+':c=a+b+48;

break;//……//补充完整

case'-':c=a-b+48;

break;

case'*':c=a*b+48;

break;

case'/':c=a/b+48;

break;

}

return c;

}

实验运行结果


1

当前栈的长度为:0

请输入将要入栈的元素:

1

当前栈的长度为:1

出栈:1

当前栈的长度为:0

2

请输入要判断中心对称的字符串,长度为5

1

2

3

4

5

该字符串不是中心对称的字符串

3

请输入算术表达式,并以#结束.

1+3/3+(2*3)-2#

6



Process returned 0 (0x0) execution time : 37.894 s

Press any key to continue.




1

当前栈的长度为:0

请输入将要入栈的元素:

1

当前栈的长度为:1

出栈:1

当前栈的长度为:0

2

请输入要判断中心对称的字符串,长度为5

1

2

3

2

1

该字符串是中心对称的字符串

3

请输入算术表达式,并以#结束.

1+3*2-3/3#

6



Process returned 0 (0x0) execution time : 28.153 s

Press any key to continue.