数据结构课件-第四章.ppt

顺序栈的主要算法描述如下： （1）栈初始化： void InitStack（SqStack *S）{ /*建立一个空栈S*/ S-top=0; } （2）判空栈操作： int StackEmpty（SqStack *S）{ /*判断栈S是否为空，空则返回1，非空则返回0*/ if（S-top==0）/*栈空条件为S-top==0*/ return 1; else return 0;  }  （3）元素进栈操作： int Push（SqStack *S, ElemType x）{ /*若栈S未满，则将元素x进栈*/ if(S-top==MAXSIZE) /*栈满条件为S-top==MAXSIZE*/ {printf（″栈上溢出!＼n″）; return 0;}  else{ /*否则将x赋值给栈顶指针所指空间，然后将栈顶指针后移*/ S-elem［S-top］=x; S-top++; return 1; } }  （4）元素出栈操作： int Pop（SqStack *S，ElemType *x）{ /*从栈中弹出栈顶元素*/ if（S-top==0） {printf（″栈下溢出!＼n″）;return 0;} else {S-top--; /*否则栈顶指针减1，即栈顶下移*/ *x= S-elem［S-top］; return 1; } } 共享栈 在栈的共享技术中最常用的是两个栈的共享技术，它主要利用了“栈底位置不变，而栈顶位置动态变化”的特性。将两个栈的栈底设在数组空间的两端，让两个栈各自向中间延伸 栈的链式存储结构 栈的链接存储结构与线性表的链接存储结构相似，每个结点除了存储本身的信息之外，还需存储一个指示其直接后继的指针。 数据进栈相当于向链栈的表头插入新的结点并成为新的表头结点，数据出栈相当于删除链栈的表头结点 #define LEN sizeof(SNode) typedef struct SNode { ElemType data； /*结点的数据域*/ struct SNode *next； /*结点的指针域*/ }SNode，*Link； /*Link为结点指针类型*/ 链栈操作示意图 3.2.3　栈的简单应用 例3.1：设计算法，实现把十进制整数用2-9之间的任一进制数输出。 由计算过程可知，由低到高依次得到r进制中的每一位数字，而输出却是从高到低依次输出每一位，所以此类问题正符合栈后进先出的思想，适合用栈来解决此类问题，具体算法描述如下： void Alter(long n，int r) { Link S； /*假定使用链栈*/ InitStack (S)； /*初始化栈*/ while(n) /*由低到高求出每一个余数并入栈 {k=n%r ；push(S，k)；n/=r；} while(!StackEmpty(S)) {pop(S，k)；printf(“%d ”，k)；} } 例3.3 表达式中括号匹配问题。假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个判别表达式中括号是否正确配对的算法。 算法思想：算术表达式中三种括号出现的次序正好符合后到的括号要最先被匹配的“后进先出”的栈的操作特点，因此可以利用一个栈来存储三种左括号。当右括号出现时，看当前栈顶括号是否与之匹配，若匹配则退栈，若不匹配说明算术表达式中括号配对不正确。若算术表达式中所有括号都能正确的别消解，则改算术表达式中括号配对正确，否则该算术表达式中括号配对不正确。用顺序栈实现如下 ： void Correct (SqStack *S) /*判别表达式中括弧是否正确配对*/ { int tag; char ch, x; InitStack(S); printf(请输入算术表达式，检查其括弧是否正确配对,以#结束,如 {5*[b-(c+d)]}# \n); ch = getchar( ); tag = 1;/* 标志位。tag = 1，表达式中括弧正确配对；tag = 0 表达式中括弧不正确配对*/ while ( ( ch !=# ) ( tag ==