③相关的操作实现 Status InitStack Sq(sqstack &s)i S base=( SElem Type *)malloc(STACK INIT SIZE*sizeof( SElem Type)); if(!S base )exit(OVERFLOW) S top=S base S. stacksize STACK INIT SIZE: return OK 3 //InitStack Status GetTop Sq(sqstack S, Selem Type &e) if(Stop==S base)return ERROR e=*(S top-1); return OK; Status Push Sq(sqStack &s, selem Type e) 栈满、栈空? S top Status Pop sq(sqstack s, SelemType &e)f Stop; pboustc. 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; … } 相关的操作实现 栈满、栈空？
链栈 date next typedef LinkList Link Stack 视顶 InitStack L(Link Stack &s) Push L stack &s, Selem Type e) Pop L(LinkStack S, Selem Type &e) A|找底 Status getTop l linkstack s, selem Type &e i if(s)return ERROR e=s->data return OK pboustc. 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; }
③32栈的应用 1数制转换 N= an d+an1d|+…+a1d+a 计算过程-入栈 打印过程-出栈 例把十进制数159转换成八进制数 8159余7 ←top 819余3 p 82 余2 top 2|3|7 (159)0=(237) pboustc. 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.22括号匹配检验 [O}等括号的匹配* 32.3行编辑程序 算法 void lineedit(O 324迷宫求解 入口 出口 pboustc. edu. cn 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 3.2.2括号匹配检验 {[()]}等括号的匹配* 3.2.3行编辑程序 – 算法 void LineEdit() 3.2.4迷宫求解
typedef structint r, c; Pos Type; typedef struct(int ord Postype seat; int di selem Type Typedef int Maze Type MAXRJLMAXCI Status Pass(Maze Type maze, PosType Cur Pos void FootPrint(Maze Type &maze, Pos Type Cur Pos) void MarkPrint(Maze Type &maze, Pos Type CurPos PosType NextPos(Pos Type CurPos, int Dir) Status MazePath(Maze Type &maze, Pos Type start, Pos Type end pboustc. 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) ;