实验二栈队列算法设计.doc

实验二 栈、队列的实现、递归应用 一、实验目的1 熟悉栈、队列这种特殊线性结构的特性2 熟练掌握栈、队列在顺序存储结构和链表存储结构下的基本操作。 二、实验要求 1 实验之前认真准备，编写好源程序。2 实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性的验证。3 不断积累程序的调试方法。 三、实验内容 基本题（必做）：1 分别就栈的顺序存储结构和链式存储结构实现栈的各种基本操作。2 、假设以带头结点的循环链表表示队列，并且只设一个指针指向对尾结点，不设头指针，试设计相应的置队空、入队和出队的程序。加强题：1、设线性表A中有n个字符，试设计程序判断字符串是否中心对称，例如xyzyx和xyzzyx都是中心对称的字符串。提高题：1、试编写程序：a.将中缀表达式计算转换成后缀表达式。b.后缀表达式的计算实现4.2.2中的算法，要考虑实际运算时，后缀表达式中相邻操作数的界定。 四．实验代码 基础题1 #include iostream.h #include conio.h #include stdlib.h const STACK_INIT_SIZE=100; //存储空间初始分配量 const STACKINCREMENT=10; //存储空间分配增量 typedef struct{ int *base; //在构造之前和销毁之后，base的值为NULL int *top; //栈顶指针 int stacksize; //当前已分配的存储空间，以元素为单位 }SqStack; void InitStack(SqStack S){ //构造一个空栈S S.base=(int *)malloc(STACK_INIT_SIZE*sizeof(int)); if(!S.base) exit(0); //存储分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; cout初始化完毕endl; }//InitStack void GetTop(SqStack S,int e){ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR if(S.top==S.base) { cout此栈为空!!!endl; exit(0); } e=*(S.top-1); couteendl; cout取值结束endl; }//GetTop void Push(SqStack S,int e){ //插入元素e为新的栈顶元素 if(S.top-S.baseS.stacksize){//栈满，追加存储空间 S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(int)); if(!S.base) { cout新分配空间失败！！！endl; exit(0); } S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; } *S.top++=e; cout插入元素成功endl; }//Push void Pop(SqStack S,int e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.base==S.top) { cout此栈为空栈，无法删除！！！endl; exit(0); } e=*--S.top; cout删除成功！！！endl; }//Pop void ClearStack(SqStack S){ //把S置为空栈 if(S.base==S.top) cout此栈已经为空!!!endl; S.top=S.base; }//ClearStack int visit(int *p) { return *p; } void Traverse(SqStack S) { int *p; p=S.base; while(p!=S.top) { coutvisit(p) ; p++; } coutendl; } void main(){ SqStack Stack; int m,n,x,y,z,i=0; char c; InitStack(Stack); cout请输入您要建立的栈的大小：endl; cinn; Stack.stacksize=n; do{ cout请选择操作：endl; cout 1，进栈 2，出栈 3，查看栈顶值 4，清空栈 5，退