实验名：栈和队列的基本操作及其应用

一、实验目的

1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。

2、掌握栈和队列的特点，即后进先出和先进先出的原则。

3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

二、实验内容

题目一：回文判断（*）

[问题描述]

对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。

[算法设计]

本实验构造了一个栈表，并对栈中的元素进行回文判断。

程序中构造了主函数main（）和InitStack（）Push（） puanduan（）各功能函数。实现了对所建立的栈表中的元素进行回文判断。

1.   构造一个空栈

Status InitStack (SqStack &S,int maxsize)//构造一个空栈

{S.base=new SElemType[maxsize];

if(!S.base)exit(1);

S.stacksize = maxsize;

*S.base=NULL;

S.top=S.base;

return OK;

}

2.       建立栈表

Status Push(SqStack &S, char a[])//建立栈表

{ int i,n;

       cout<<"请输入元素的个数"<<endl;

       cin>>n;

       cout<<"请输入元素"<<endl;

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

       cin>>a[i];}

       for(i=0;i<n;i++){

*S.top=a[i];

++S.top;

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

        return ERROR;} 

}

3．判断是不是回文

void puanduan(SqStack &S)// 判断是不是回文

{bool b=1 ;

while (S.base<S.top)

{S.top=S.top-1;

if(*S.top!=*S.base) b=0;

else {S.top--;S.base++;}

}

if(b==1)cout<<"是回文 "<<endl;

else cout<<" 不是回文"<<endl;}

4.主函数

void main()//主函数

{int n;char a[100];SqStack S;

cout<<"请输入你要选择的功能:1.建立栈表层,2.判断是否为回文,3.退出"<<endl;

cin>>n;

while(n!=3){

switch(n)

{case 1: InitStack ( S,100);

Push(S,a ); break;

case 2:puanduan(S);break;

default:cout<<"输入错误"<<endl;}

cout<<"请输入你要选择的功能:1.建立栈表层,2.判断是否为回文,3.退出"<<endl;

cin>>n;

}

}

file:///C:/DOCUME%7E1/ADMINI%7E1/LOCALS%7E1/Temp/msohtml1/01/clip_image002.jpg

【调试分析】

调试时初始化栈表时出错，我采用了数组和栈的顺序结构相结合，在判断回文算法时采用了一个while循环和一个if从句。

【心得体会】

对栈的顺序存储结构用了更深刻的了解，同时也对程序设计能力有了提高，加深了对栈先进后出性质的理解，对数组的应用也十分熟练。

【附录】：

#include<stdlib.h>

#include<iostream.h>

#define NULL  0;

#define OK  1;

#define ERROR 0;

typedef int  Status;

typedef char SElemType;

      typedef struct {

       SElemType *base;

       SElemType *top;

        int stacksize;

      }SqStack; //定义存储类型

Status InitStack (SqStack &S,int maxsize)//构造一个空栈

{S.base=new SElemType[maxsize];

if(!S.base)exit(1);

S.stacksize = maxsize;

*S.base=NULL;

S.top=S.base;

return OK;

}

Status Push(SqStack &S, char a[])//建立栈表

{ int i,n;

       cout<<"请输入元素的个数"<<endl;

       cin>>n;

       cout<<"请输入元素"<<endl;

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

       cin>>a[i];}

       for(i=0;i<n;i++){

*S.top=a[i];

++S.top;

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

        return ERROR;} 

    }

void puanduan(SqStack &S)// 判断是不是回文

{bool b=1 ;

while (S.base<S.top)

{S.top=S.top-1;

if(*S.top!=*S.base) b=0;

else {S.top--;S.base++;}

}

if(b==1)cout<<"是回文 "<<endl;

else cout<<" 不是回文"<<endl;}

void main()//主函数

{int n;char a[100];SqStack S;

cout<<"请输入你要选择的功能:1.建立栈表层,2.判断是否为回文,3.退出"<<endl;

cin>>n;

while(n!=3){

switch(n)

{case 1: InitStack ( S,100);

Push(S,a ); break;

case 2:puanduan(S);break;

default:cout<<"输入错误"<<endl;}

cout<<"请输入你要选择的功能:1.建立栈表层,2.判断是否为回文,3.退出"<<endl;

cin>>n;