数据结构试验(回文判断).doc

目录
1、 实验题目

2、 实验目的

3、 实验要求

4、 算法设计分析

5、 测试调节

6、 总结

7、 代码附录

1、 实验名称：
栈和队列的基本操作及其应用（回文判断）

2、 实验目的：
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈和队列的特点，即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。

3、 算法设计分析：
（1） 栈的初始化：
void Init_stack(SqStack &S)
{
S.base= (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!S.base) exit(OVERFLOW);
S.top=S.base; //栈顶与栈尾指针指向栈尾
S.stacksize=STACK_INIT_SIZE;
// return 0;
}
（2） 入栈
void Push(SqStack &S,char e){
if(S.top-S.base>=S.stacksize) //首先判满
{
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREASE)*sizeof(char));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREASE;
}
*S.top++ =e; //入一个元素，栈顶指针增加1

}
（3）出栈：
char Pop(SqStack &S,char&e){
if(S.top==S.base) exit(OVERFLOW);
e= *--S.top; //删除栈顶元素并用e返回其值
return e;
}
（3） 回文判断
/*void Compare(SqStack &S)
{
int i,n=0;
int t=0;
char ch[100];
char m,e;
char p;
cout<<"请输入您要进行的判断的字符以#作为结束标志: \n";
for(i=0;i<100;i++)
{
cin>>p;
if(p!='#') //作为结束标志
{ch[i]=p;}
else
{n=i;break;}
}

for(int h=0;h<n;h++) //入栈
{Push(S,ch[h]);}

for(int w=0;w<n;w++)
{
//cout<<"debug";
m=Pop(S,e); //这个地方有错误 //出栈
//cout<<m;
//cout<<"debug";
if(m==ch[w]) //比较字符是否与输入的字符相同
{t++;}
}

if(t==n)
{cout<<"输入的字符串是回文编码!";}
else
{cout<<"输入的字符串不是回文编码!";}
}*/

*********************《算法改进》***************************
for(i=0;i<100;i++)
{
cin>>ch[i];
if(ch[i]=='#')
break;
Push(S,ch[i]);
n++;
for(i=0;i<n/2;i++) //回文为对称字符，因此只需判断一半即可
{
m=Pop(S,e);
if(m!=ch[i])
break;
t++;
}
}
if(t==n/2)
{cout<<"输入的字符串是回文编码!";}
else
{cout<<"输入的字符串不是回文编码!";}
}
（4） 测试调节：

（5） 总结：
通过对回文判断的代码编写，对栈的更加了解，初始化（开辟空间），
入栈、出栈等更加的了解。但是编写这个代码没有用到队列，以后在课下时间，会编写一个更复杂的代码，加以熟悉。总的来说，做这个小程序，对栈确实有了进一步的了解，一些基本的操作也更加的熟悉，为以后的课设打下基础。

（6） 代码附录：
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define STACK_INIT_SIZE 100
#define STACKINCREASE 10
#define OVERFLOW 0
//using namespace std;
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;

void Init_stack(SqStack &S)
{
S.base= (char *)malloc(STACK_INIT_SIZE * sizeof(char));
if(!S.base) exit(OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
// return 0;
}

void Push(SqStack &S,char e){
if(S.top-S.base>=S.stacksize)
{
S.base=(char *)realloc(S.base,(S.stacksize+STACKINCREASE)*sizeof(char));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREASE;
}
*S.top++ =e;

}

char Pop(SqStack &S,char&e){
//if(S.top==S.base) //exit(OVERFLOW);
// { cout<<"empty";
//e='E';
// }
//else
// { e=* --S.top;}
if(S.top==S.base) exit(OVERFLOW);
e=* --S.top;
return e;
}

/*void Compare(SqStack &S)
{
int i,n=0;
int t=0;
char ch[100];
char m,e;
char p;
cout<<"请输入您要进行的判断的字符以#作为结束标志: \n";
for(i=0;i<100;i++)
{
cin>>p;
if(p!='#')
{ch[i]=p;}
else
{n=i;break;}
}

for(int h=0;h<n;h++)
{Push(S,ch[h]);}

for(int w=0;w<n;w++)
{
//cout<<"debug";
m=Pop(S,e); //这个地方有错误
//cout<<m;
//cout<<"debug";
if(m==ch[w])
{t++;}
}

if(t==n)
{cout<<"输入的字符串是回文编码!";}
else
{cout<<"输入的字符串不是回文编码!";}
}*/

void Compare(SqStack &S){
int i,n=0;
int t=0;
char ch[100];
char m,e;
cout<<"请输入您要进行判断的字符,以'#'作为结束的标志: \n";
for(i=0;i<100;i++)
{
cin>>ch[i];
if(ch[i]=='#')
break;
Push(S,ch[i]);
n++;
for(i=0;i<n/2;i++)
{
m=Pop(S,e);
if(m!=ch[i])
break;
t++;
}
}
if(t==n/2)
{cout<<"输入的字符串是回文编码!";}
else
{cout<<"输入的字符串不是回文编码!";}
}
void main()
{
SqStack S;
Init_stack(S);
Compare(S);
}