相关的操作实现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 SqStatus GetTop_Sq(SqStack S,SelemType &e)if(S.top==S.base)returnERROR:e=*(S.top-1);return OK;1栈满、栈空？Status Push Sq(SqStack &S ,SelemType e) *S.top++=e,1Status Pop_Sq(SqStack &S ,SelemType &e)e=*.-S.top,16中国科学技术大学ypb@ustc.edu.cn
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; . } 相关的操作实现 栈满、栈空？
C>链栈datanextStypedefLinkListLinkStack;栈项InitStack L(LinkStack &S)Push L(LinkStack &S ,SelemType e)Pop L(LinkStack &S ,SelemType &e)找底AStatus GetTop L(Linkstack S,SElemType &e)if(!S) return ERROR:e=S->data;return OK;vpb@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=an.dn+an-1.dn-1+... +aj.d+ao计算过程－入栈打印过程－出栈例把十进制数159转换成八进制数-top8159余 7top82余319top338余 22一1top770(159)10=(237)88片放中国科学技术大学ypb@ustc.edu.cn
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 LineEditO3.2.4迷宫求解入口出口中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 9 中国科学技术大学 3.2.2括号匹配检验 {[()]}等括号的匹配* 3.2.3行编辑程序 – 算法 void LineEdit() 3.2.4迷宫求解
S步序，坐标，方向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);StatusMazePath(MazeTypee&maze,PosTypestart,PosType end);10中国科学技术大学ypb@ustc.edu.cn
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) ; 步序，坐标，方向