数据结构试验(回文判断).doc
文本预览下载声明
目录
实验题目
实验目的
实验要求
算法设计分析
测试调节
总结
代码附录
实验名称：
栈和队列的基本操作及其应用（回文判断）
实验目的：
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈和队列的特点，即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。
算法设计分析：
栈的初始化：
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; //入一个元素，栈顶指针增加1
}
（3）出栈：
char Pop(SqStack S,chare){
if(S.top==S.base) exit(OVERFLOW);
e= *--S.top; //删除栈顶元素并用e返回其值
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;i100;i++)
{
cinp;
if(p!=#) //作为结束标志
{ch[i]=p;}
else
{n=i;break;}
}
for(int h=0;hn;h++) //入栈
{Push(S,ch[h]);}
for(int w=0;wn;w++)
{
//coutdebug;
m=Pop(S,e); //这个地方有错误 //出栈
//coutm;
//coutdebug;
if(m==ch[w]) //比较字符是否与输入的字符相同
{t++;}
}
if(t==n)
{cout输入的字符串是回文编码!;}
else
{cout输入的字符串不是回文编码!;}
}*/
*********************《算法改进》***************************
for(i=0;i100;i++)
{
cinch[i];
if(ch[i]==#)
break;
Push(S,ch[i]);
n++;
for(i=0;in/2;i++) //回文为对称字符，因此只需判断一半即可
{
m=Pop(S,e);
if(m!=ch[i])
break;
t++;
}
}
if(t==n/2)
{cout输入的字符串是回文编码!;}
else
{cout输入的字符串不是回文编码!;}
}
测试调节：
总结：
通过对回文判断的代码编写，对栈的更加了解，初始化（开辟空间），
入栈、出栈等更加的了解。但是编写这个代码没有用到队列，以后在课下时间，会编写一个更复杂的代码，加以熟悉。总的来说，做这个小程序，对栈确实有了进一步的了解，一些基本的操作也更加的熟悉，为以后的课设打下基础。
代码附录：
#includeiostream.h
#includestdio.h
#includestdlib.h
#includestring.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;
显示全部