实验3 顺序栈的基本操作及应用
一、 实验目的
1. 帮助学生理解栈结构的特点即后进先出。
2．掌握栈的顺序存储结构和基本操作，重点掌握入栈和弹栈操作。验证所学的算法和数据结构，以便在实际背景下灵活运用。
3．提高应用栈解决实际问题的能力。
二、 实验内容
1．仔细阅读程序sqstack.h和sqstack .c练习顺序栈基本操作，完成该程序并上机运行测试。
2．试利用栈作为辅助空间，编写一个算法，判别给定的字符序列是否是“回文”。回文是指不看空格正读反读均相同的字符序列，如\"abba\"和\"ab db a\"均是回文，但\"good\"不是回文。
int Palindrome(char *str)
/*判别字符序列str是否是“回文”。是返回1，不是返回0*/
{ sqstack S;
}
注：题目1程序清单
/*****************sqstack.h***********************/
/************顺序栈类型定义***********/
#define INITSIZE 100
typedef int ElemType;
typedef struct
{ ElemType *base;/*栈顶指针，又是存储元素的一维数组*/
int top; /*栈顶指针，记录栈顶的下一个位置*/
int stacksize; /* 记录存储空间的尺寸*/
}sqstack;
/***********函数声明**************/
void initstack(sqstack *S);
int getlen(sqstack S);
int gettop(sqstack S,ElemType *e);
int push(sqstack *S, ElemType x);
int pop(sqstack *S, ElemType *e);
int emptystack(sqstack S);
void print(sqstack S);
/*************函数定义***********/
/**构造空栈**/
void initstack(sqstack *S)
{/*构造一个空栈由指针S指出。*/
S->base= __(1)___;
if (!S->base)
{printf(\"OVERFLOW!\"); exit(1);}
S->top=__(2)__;
S->stacksize = INITSIZE;
}
/**求栈长操作**/
int getlen(sqstack S)
{
return (__(3)___);
}
/**取栈顶元素操作**/
int gettop(sqstack S,ElemType *e)
{
if(S.top == 0)
return 0;
_____(4)____________;
return 1;
}
/**压栈**/
int push(sqstack *S, ElemType x)
{/*向栈顶插入元素x，成功返回１，失败返回０*/
if(S->top == S->stacksize) /*栈已满*/
{
S->base = ___(5)______;
if(!S->base)
{ printf(\"OVERFLOW!\"); return 0;}
S->stacksize ++;
}
/*插入*/
____(6)_______;
____(7)___________;
return(1);
}
/**弹栈**/
int pop(sqstack *S, ElemType *e)
{/*若栈空, 则返回０*/
if(S->top==0)
return 0;
/*删除*/
______(8)___________;
______(9)____________;
return 1;
}
/**判栈空**/
int emptystack(sqstack S)
/*判栈S为空栈时返回值为1， 反之为0*/
{
return(____(10)____);
}
/**输出栈元素**/
void list(sqstack S)
{/*从栈底元素输出到栈顶元素*/
int i = 0;
if(emptystack(S)) {printf(\"none!\\n\"); return;}
while(i{printf(\"%4d\
i++;
}
printf(\"\\n\");
}
/***************** sqstack.c文件*************** **/
______(11)___________
void menu()
{
printf(\"******************menu***************\\n\");
printf(\" 0:list()\\n\");
printf(\" 1:getlen()\\n\");
printf(\" 2:gettop()\\n\");
printf(\" 3:push()\\n\");
printf(\" 4:pop()\\n\");
printf(\" 5:emptystack()\\n\");
printf(\" 6:exit()\\n\");
printf(\"*************************************\\n\");
printf(\"Please choice:\");
}
main()
{sqstack S;
ElemType x;
char choice;
//clrscr();
printf(\"\\n\\n-------------------SqStack Demo is running...----------------\\n\\n\");
______(12)_____;/*S初始化*/
menu();
/*根据选择演示顺序栈的基本操作*/
while(1)
{
scanf(\"%c\
switch(choice)
{
case '0': /*调用list()输出栈中元素*/
printf(\"The stack:\");
____(13)_______;
printf(\"Please choice:\");
break;
case '1': /*调用getlen()求栈长*/
printf(\"The length of S is %d.\\n\_(14)_______);
printf(\"Please choice:\");
break;
case '2': /*调用gettop()取栈顶元素*/
if(___(15)_____)
printf(\"The top element:%4d\\n\
else printf(\"No element!\\n\");
printf(\"Please choice:\");
break;
case '3': /*调用push()入栈*/
printf(\"Push an element! x=\");
scanf(\"%d\
if(___(16)__________)
printf(\"Push an element is failed!\\n\");
printf(\"Please choice:\");
break;
case '4': /*调用pop()出栈*/
if(____(17)________)
printf(\"No element!\\n\");
else
printf(\"Pop the top element:%d\\n\
printf(\"Please choice:\");
break;
case '5': /*调用emptystack()判栈空*/
if(____(18)_______) printf(\"The satck is empty!\\n\");
else printf(\"The stack is unempty!\\n\");
printf(\"Please choice:\");
break;
case '6': printf(\"Exit!\");
exit(1);
break;
}
}
