数据结构考研分类复习真题 第三章 答案[15]

五算法设计题

[题目分析]两栈共享向量空间将两栈栈底设在向量两端初始时s栈顶指针为s栈顶为maxsize两栈顶指针相邻时为栈满两栈顶相向迎面增长栈顶指针指向栈顶元素

#define maxsize 两栈共享顺序存储空间所能达到的最多元素数

#define elemtp int //假设元素类型为整型

typedef struct

{elemtp stack[maxsize]; //栈空间

int top[]; //top为两个栈顶指针

}stk;

stk s; //s是如上定义的结构类型变量为全局变量

()入栈操作

int push(int iint x)

//入栈操作i为栈号i=表示左边的栈si=表示右边的栈sx是入栈元素入栈成功返回否则返回

{if(i<||i>){printf(栈号输入不对);exit();}

if(stop[]stop[]==) {printf(栈已满\n);return();}

switch(i)

{case : sstack[++stop[]]=x; return(); break;

case : sstack[stop[]]=x; return();

}

}//push

（） 退栈操作

elemtp pop(int i)

//退栈算法i代表栈号i=时为s栈i=时为s栈退栈成功返回退栈元素否则返回

{if(i< || i>){printf(栈号输入错误\n)exit();}

switch(i)

{case : if(stop[]==) {printf(栈空\n)return（）}

else return(sstack[stop[]]);

case : if(stop[]==maxsize {printf(栈空\n); return();}

else return(sstack[stop[]++]);

}

}//算法结束

[算法讨论] 请注意算法中两栈入栈和退栈时的栈顶指针的计算两栈共享空间示意图略s栈是通常意义下的栈而s栈入栈操作时其栈顶指针左移（减）退栈时栈顶指针右移（加）

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []