实验二 栈与迷宫.doc

实验二 栈（队列）的创建与应用#include #include #define MaxSize 100#define MaxOp 7struct char ch; /运算符int pri; /优先级 lpri=,0,(,1,*,2,/,2,+,3,-,3,),6, rpri=,0,(,6,*,4,/,4,+,2,-,2,),1;int leftpri(char op) /求左运算符op的优先级int i;for (i=0;iMaxOp;i+)if (lprii.ch=op) return lprii.pri;int rightpri(char op) /求右运算符op的优先级int i;for (i=0;iMaxOp;i+)if (rprii.ch=op) return rprii.pri;int InOp(char ch) /判断ch是否为运算符if (ch=( | ch=) | ch=+ | ch=- | ch=* | ch=/)return 1;elsereturn 0;int Precede(char op1,char op2) /op1和op2运算符优先级的比较结果if (leftpri(op1)=rightpri(op2)return 0;else if (leftpri(op1)=0 & *exp=0 & *postexp=9) /判定为数字字符d=10*d+*postexp-0; postexp+;st.top+;st.datast.top=d;break;postexp+;/继续处理其他字符return(st.datast.top);void main() char exp=(26-20)/(4+2);char postexpMaxSize;trans(exp,postexp);printf(中缀表达式:%sn,exp);printf(后缀表达式:%sn,postexp);printf(表达式的值:%gn,compvalue(postexp);printf(操作成功n);#include #include typedef char ElemType;typedef struct linknodeElemType data;/数据域struct linknode *next;/指针域 LiStack;/链栈类型定义void InitStack(LiStack *&s)s=(LiStack *)malloc(sizeof(LiStack);s-next=NULL;void ClearStack(LiStack *&s)LiStack *p=s-next;while (p!=NULL)free(s);s=p;p=p-next;free(s);/s指向尾结点,释放其空间int StackLength(LiStack *s)int i=0;LiStack *p;p=s-next;while (p!=NULL)i+;p=p-next;return(i);int StackEmpty(LiStack *s)return(s-next=NULL);void Push(LiStack *&s,ElemType e)LiStack *p;p=(LiStack *)malloc(sizeof(LiStack);p-data=e;p-next=s-next;/插入*p结点作为第一个数据结点s-next=p;int Pop(LiStack *&s,ElemType &e)LiStack *p;if (s-next=NULL)/栈空的情况return 0;p=s-next;/p指向第一个数据结点e=p-data;s-next=p-next;free(p);return 1;int GetTop(LiStack *s,ElemType &e)if (s-next=NULL)/栈空的情况return 0;e=s-next-data;return 1;void DispStack(LiStack *s)LiStack *p=s-next;while (p!=NULL)printf(%c ,p-data);p=p-next;printf(n);#include #define MaxSize 100#define M 8#define N 8int mgM+2N+2=1,1,1,1,1,1,1,1,1,1,1,0,0,1,0,0,0,1,0,1,1,0,0,1,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,0,1,1,0,1,0,0,0,1,0,0,1,1,0,1,1,1,0,1,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,1,1,1,1,1,1,1,1;int mgpath(int xi,int yi,int xe,int ye)/求解路径为:(xi,yi)-(xe,ye)struct int i;/当前方块的行号int j;/当前方块的列号int di;/di是下一可走方位的方位号 stMaxSize;/定义栈int top=-1;/初始化栈指针int i,j,k,di,find;top+; /初始方块进栈sttop.i=xi;sttop.j=yi;sttop.di=-1;mg11=-1; while (top-1)/栈不空时循环i=sttop.i;j=sttop.j;di=sttop.di; /取栈顶方块if (i=xe & j=ye)/找到了出口,输出路径 printf(迷宫路径如下:n);for (k=0;k=top;k+)printf(t(%d,%d),stk.i,stk.j);if (k+1)%5=0)/每输出每5个方块后换一行printf(n); printf(n);return(1);/找到一条路径后返回1find=0;while (di4 & find=0)/找下一个可走方块di+;switch(di)case 0:i=sttop.i-1;j=sttop.j;break;case 1:i=sttop.i;j=sttop.j+1;break;case 2:i=sttop.i+1;j=sttop.j;break;case 3:i=sttop.i,j=sttop.j-1;break;if (mgij=0) find=1;/找到下一个可走相邻方块if (find=1)/找到了下一个可走方块sttop.di=di;/修改原栈顶元素的di值top+;/下一个可走方块进栈sttop.i=i;sttop.j