S 相关的操作实现 Status InitStack_Sq(SqStack &S){ S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK INIT SIZE;return OK; }//InitStack Sq Status GetTop_Sq(SqStack S,SelemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1);returnOK; Status Push_Sq(SqStack &S,SelemType e){ 栈满、栈空？ *S.top++=e;… Status Pop_Sq(SqStack &S,SelemType &e){ e=*--S.top;... ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 Status InitStack_Sq(SqStack &S) { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; } //InitStack_Sq Status GetTop_Sq(SqStack S,SelemType &e){ if(S.top==S.base)return ERROR; e=*(S.top-1);return OK; } Status Push_Sq(SqStack &S ,SelemType e) { … *S.top++=e; … } Status Pop_Sq(SqStack &S ,SelemType &e){ … e=*--S.top; … } 相关的操作实现 栈满、栈空？
链栈 data next typedef LinkList LinkStack; 顶 InitStack L(LinkStack &S) Push L(LinkStack &S ,SelemType e) Pop_L(LinkStack &S ,SelemType &e) 找底 Status GetTop_L(Linkstack S,SElemType &e){ if(!S)return ERROR: e=S->data; return OK: ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 ➢ 链栈 typedef LinkList LinkStack; InitStack_L(LinkStack &S) Push_L(LinkStack &S ,SelemType e) Pop_L(LinkStack &S ,SelemType &e) Status GetTop_L(Linkstack S,SElemType &e){ if(!S) return ERROR; e=S->data; return OK; }
3.2栈的应用 1.数制转换 N=a.dn+an-1.d-1+...+a.d+ao 计算过程·入栈 打印过程- 出栈 例把十进制数159转换成八进制数 8159 余7 -top 819 余3 top 82 余2 top 3 0 7 237 (159)10=(237)8 ypb@ustc.edu.cn 8 树片放中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 3.2栈的应用 1.数制转换 N=an .d n+an-1 .d n-1+…+a1 .d+a0 计算过程 － 入栈 打印过程 － 出栈 例 把十进制数159转换成八进制数 (159)10=(237)8 8 159 8 19 8 2 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2
3.2.2括号匹配检验 {[O]}等括号的匹配* 3.2.3行编辑程序 -算法void LineEdit(O 3.2.4迷宫求解 入口 78 出口 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 3.2.2括号匹配检验 {[()]}等括号的匹配* 3.2.3行编辑程序 – 算法 void LineEdit() 3.2.4迷宫求解
typedef struct{int r,c;}PosType; 步序，坐标，方向 typedef struct{int ord;Postype seat;int di}SElemType; Typedef int MazeType[MAXR][MAXC]; Status Pass(MazeType maze,PosType CurPos); void FootPrint(MazeType &maze,PosType CurPos); void MarkPrint(MazeType &maze,PosType CurPos); PosType NextPos(PosType CurPos,int Dir); Status MazePath(MazeType &maze,PosType start, PosType end); ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 typedef struct{int r,c;} PosType; typedef struct{int ord;Postype seat;int di} SElemType; Typedef int MazeType[MAXR][MAXC]; Status Pass(MazeType maze, PosType CurPos); void FootPrint(MazeType &maze, PosType CurPos); void MarkPrint(MazeType &maze, PosType CurPos); PosType NextPos(PosType CurPos, int Dir); Status MazePath(MazeType &maze, PosType start, PosType end) ; 步序，坐标，方向