《数据结构》
实
验
报
告
书
实验内容：栈和队列的基本操作及其应用
计算机学院计算机科学与技术
计科：**********
前言
计算机编程中加工处理的对象是数据，而数据具有一定的组织结构，所以学习计算机编程仅仅了解计算机语言是不够的，还必须掌握数据的组织、存储和运算的一般方法，这便是数据结构课程中所研究的内容，也是我们编写计算机程序的重要基础，由于它对计算机学科起到承前启后的作用，因此本课程被列为计算机等相关专业最重要的专业基础课；同时数据结构是计算机专业教学的一门核心课程。计算机各领域都要用到各种数据结构，而且要从事计算机科学与技术工作，尤其是计算机领域的软件开发工作，必须具备较强的数据结构基础。
数据结构课程内容丰富、学习量大，实践性强；隐含在各部分内容中的方法和技术多；算法设计具有动态性和抽象性等特点，看懂听明白与掌握会应用之间有相当大的一段距离。所以学生必须多实践才能进一步加深对课程的理解，理解和掌握算法设计所需的方法和技术，为整个专业学习打下良好的基础。
栈和队列的基本操作及其应用
回文判断
一、实验目的
1、掌握栈和队列的顺序存储结构和链式存储结构，以便在实际中灵活应用。
2、掌握栈和队列的特点，即后进先出和先进先出的原则。
3、掌握栈和队列的基本运算，如：入栈与出栈，入队与出队等运算在顺序存储结构和链式存储结构上的实现。
[问题描述]
对于一个从键盘输入的字符串，判断其是否为回文。回文即正反序相同。如“abba”是回文，而“abab”不是回文。
[基本要求]
（1）数据从键盘读入；
（2）输出要判断的字符串；
（3）利用栈的基本操作对给定的字符串判断其是否是回文，若是则输出“Yes”，否则输出“No”。
[测试数据]
由学生任意指定。
算法设计：
首先，先建立两个空栈。分别命名为S、L。现将输入的字符串，储存于S栈中。然后，编写代码。使得S栈中的字符依出栈，并保存于L栈中。这样可以使得S 栈与L栈中的字符完全相同，但顺序颠倒。然后依次比较L栈与S栈中的字符是否相同。如果相同，则说明，所输入的字符。颠倒顺序后与原字符依然相同。所以可判断为回文。否则，就不是回文。在本代码中，栈的数据结构设计了三个指针。base指向栈底，top指向栈顶，sel也指向栈顶。sel的作用是用于将栈S 中的元素，依次传给栈L。从而避免了，在传元素的过程中，栈S的top指针回到base指针上。导致栈S变为空栈。
最后说明一下。字符串的输入是一“#”字符为结束标志的。但这个符号本身不算字符串的一部分。
建立堆栈的数据结构:
typedef struct Stick
{
ele *base;
ele *top;
ele *sel;
int stacksize;
}Sqstack;
当然此处定义：
typedef char ele;
初始化所有可能用到的数据：
#define NULL 0
#define SIZE 100
#define OVER 100
堆栈的建立算法：
i nt Init(Sqstack &S)
{
S.base=(ele *)malloc(SIZE * sizeof(ele));
if(!S.base) exit(0);
S.top=S.base;
S.sel=S.base;
S.stacksize=SIZE;
return 1;
}
堆栈的建立好以后就可以想法向里面输入字符，并定义以下算法实现向堆栈里面输入字符：
int push(Sqstack &S,ele e)
{
if (S.top-S.base>=S.stacksize)
{
S.base=(ele *)realloc(S.base,(S.stacksize+OVER)*sizeof(ele));
if(!S.base) exit(0);
S.top=S.base+S.stacksize;
S.stacksize=S.stacksize+OVER;
}
*S.top++=e;
S.sel=S.top;
return 1;
}
此程序是为实现回文的判断定义以下实现函数comp(Sqstack &S,Sqstack
&L):
int comp(Sqstack &S,Sqstack &L) //对两个堆栈中的字符串进行比较并判断是否为回文
{
int n=1;
if (L.top-L.base>=L.stacksize)
{
L.base=(ele *)realloc(L.base,(L.stacksize+OVER)*sizeof(ele));
if(!L.base) exit(0);
L.top=L.base+S.stacksize;
L.stacksize=L.stacksize+OVER;
}
S.sel=S.sel-1;
while(S.sel>=S.base)
{
*L.top=*S.sel;
S.sel=S.sel-1;
L.top =L.top+1;
}
S.top=S.top-2;
L.top=L.top-1;
while((S.top>=S.base)&&(L.top>=L.base-1))
{
