数据结构第5课栈.pptx

数据结构之二 ;点击添加文本;点击添加文本;求解;点击添加文本;2.1栈的顺序存储;2.1栈的顺序存储;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.2栈顺序的基本操作;2.3栈的链式存储;2.4链栈的基本操作;2.4链栈的基本操作;2.4链栈的基本操作;2.4链栈的基本操作;点击添加文本;2.5.1 数制转换; 采用静态顺序栈方式实现 void conversion(int n , int d) /*将十进制整数N转换为d(2或8)进制数*/ { int k, e ; init_stack( ); while (n0) { k=n%d ; push(k) ; n=n/d ; } /* 求出所有的余数，进栈 */ while (top!=0) /* 栈不空时出栈，输出 */ { e=pop( ) ; coute ; } } ;2.5.2表达式求值; 例：4 + 2 * 3 – 10 / ( 7 – 5 );表达式求值 ——算法思想;算法思想： 设立：s1----操作数栈,存放暂不运算的数和中间结果 s2----运算符栈,存放暂不运算的运算符 1.置s1,s2为空栈；开始符#进s2； 2.重复： { 2.1 从表达式读取“字符”w----操作数/算符 2.2 若w为操作数，则w进s1； 2.3 若w为运算符，则： 2.3.1 若ws2的栈顶运算符，则w进s2； 2.3.2 若w=s2的栈顶运算符，或w=“)”，则pop(s2)； 2.3.3 若ws2的栈顶运算符，则： { pop(s1,a)；pop(s1,b)；pop(s2,op)； c=b op a； push(s1,c)； 转2.3.1； } } 直到w=“#”=s2的栈顶算符。;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ; 例. # 4 + 2 * 3 – 12 / ( 7 – 5 ) # ;算法描述;//构造一个空栈?? int?initstack(stack?*S){?? ????S-base?=?0;???? ????S-top=S-base;?? ????S-stacksize=STACK_INIT_SIZE;?? ????return?OK;?? }?? //判断是否为空栈?? int?stackempty(stack?S){?? ????if(S.top?==?S.base)?? ????????return?TRUE;?? ????else?? ????????return?FALSE;?? }?? //用e返回S的顶元素?? int?gettop(stack?S,?int?*e){?? ????if(S.top?==?S.base)?? ????????return?ERROR;?? ????*e?=?*(S.top-1);?? ????return?OK;?? }??;//插入e为新的顶元素?? int?push(stack?*S,?int?e){?? ????if(S-top??=?S-stacksize-1)? ???????exit(OVERFLOW);?? ????*(S-top)=e;?? ????S-top++;?? ????return?OK;?? }?? //删除S的顶元素，并用e返回其值?? int?pop(stack?*S,?int?*e){?? ????if(S-top?==?S-base)?? ????????return?ERROR;?? ????S-top--;?? ????*e?=?*(S-top);?? ????return?OK;?? }??;//从栈底到栈顶依次对S的每个元素调用函数Visit（），一旦失败操作无效?? int?listtraverse(stack?S,int?(*visit)(int)){?? ????int*p;?? ????p=S.base;?? ????for(p=S.base;pS.top;p++)?? ????????(*visit)(*p);?? ?? ????return?OK;?? }?? //输出元素e?? int?output(int?e){?? ????coute;?? ?? ????return?OK;