这学期老师非得让用C语言写一个栈来解决迷宫可解性的问题,让我们这些学过一些stl的比较难以接受,明明两行就能解决的函数定义非要搞得那么麻烦....
用C语言来写顺栈的话,就是用数组模拟,链栈可以用链表,以链头当栈顶.
话不多说,直接上代码;
顺栈:
#include#include #define MAXN 20000 int migong[101][100]; int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; typedef struct{ int x; int y; int d; }date; struct seq { int t; date s[MAXN]; }; typedef struct seq * pseq; pseq creat_seq() { pseq pseqa; pseqa=(pseq)malloc(sizeof(seq)); if(pseqa==NULL) printf("malloc error!n"); else pseqa->t=-1; return pseqa; } void push_seq(pseq pseqa,date x) { if(pseqa->t>MAXN) printf("error 2!n"); else { pseqa->t++; pseqa->s[pseqa->t]=x; } } int empty_seq(pseq pseqa) { if(pseqa->t==-1) return 1; else return 0; } void pop_seq(pseq pseqa) { if(!empty_seq(pseqa)) pseqa->t--; } date top_seq(pseq pseq) { return pseq->s[pseq->t]; } int output_seq(pseq pseqa) { date n; if(empty_seq(pseqa)) return 0; n.x=pseqa->s[pseqa->t].x; n.y=pseqa->s[pseqa->t].y; pop_seq(pseqa); output_seq(pseqa); printf("(%d %d)",n.x,n.y); } int path(int migong[][100],int dirction[][2],int x1,int y1,int x2,int y2,int m,int n,pseq st) //x1,为起点纵坐标，x2为终点的，m行，n列 { int i,j,k,g,h,b,x0,y0; date a; if(st==NULL) return 0; migong[x1][y1]=2; a.x=x1; a.y=y1; a.d=-1; push_seq(st,a); if(x1==x2&&y1==y2) return 1; while(st->t!=-1) { a=top_seq(st); x0=a.x; y0=a.y; k=a.d+1; while(k<=3) { g=x0+direction[k][0]; h=y0+direction[k][1]; if(g>=0&&g<=n-1&&h>=0&&h<=m-1&&migong[g][h]==0) if(path(migong,direction,g,h,x2,y2,m,n,st)==1) return 1; k=k+1; } pop_seq(st); } return 2; } int main() { int x1,x2,y1,y2,m,n,i,j; pseq st; scanf("%d %d",&m,&n); scanf("%d %d %d %d",&x1,&y1,&x2,&y2); for(i=0;i<=m-1;i++) for(j=0;j<=n-1;j++) { scanf("%d",&migong[i][j]); } st=creat_seq(); if(path(migong,direction,x1,y1,x2,y2,m,n,st)==1) output_seq(st); else printf("No Path!"); return 0; }
链栈:
#include#include #define MAXN 20000 int migong[101][100]; int direction[4][2]={{-1,0},{1,0},{0,-1},{0,1}}; typedef struct{ int x; int y; int d; }date; struct Node { date data; struct Node *next; }; typedef struct{ struct Node *top; }stk; stk *creat_seq() { stk *p=NULL; p=(stk*)malloc(sizeof(stk)); if(p!=NULL) p->top=NULL; else printf("out of space!n"); return p; } int push_seq(stk *pseqa,date x) { struct Node *pnew=NULL; pnew=(struct Node*)malloc(sizeof(struct Node)); if(pnew!=NULL) { pnew->data=x; pnew->next=pseqa->top; pseqa->top=pnew; return 1; } printf("out of space!n"); return 0; } int empty_seq(stk *pseqa) { if(pseqa->top==NULL) return 1; else return 0; } date pop_seq(stk *pseqa) { date n; struct Node *ptemp=NULL; n=pseqa->top->data; ptemp=pseqa->top; pseqa->top=pseqa->top->next; free(ptemp); return n; } date top_seq(stk *pseq) { return pseq->top->data; } int output_seq(stk* pseqa) { date n; if(empty_seq(pseqa)) return 0; n.x=pseqa->top->data.x; n.y=pseqa->top->data.y; pop_seq(pseqa); output_seq(pseqa); printf("(%d %d)",n.x,n.y); } int path(int migong[][100],int dirction[][2],int x1,int y1,int x2,int y2,int m,int n,stk* st) //x1,为起点纵坐标，x2为终点的，m行，n列 { int i,j,k,g,h,b,x0,y0; date a; if(st==NULL) return 0; migong[x1][y1]=2; a.x=x1; a.y=y1; a.d=-1; push_seq(st,a); if(x1==x2&&y1==y2) return 1; while(!empty_seq(st)) { a=top_seq(st); x0=a.x; y0=a.y; k=a.d+1; while(k<=3) { g=x0+direction[k][0]; h=y0+direction[k][1]; if(g>=0&&g<=n-1&&h>=0&&h<=m-1&&migong[g][h]==0) if(path(migong,direction,g,h,x2,y2,m,n,st)==1) return 1; k=k+1; } if(!empty_seq(st)) pop_seq(st); } return 2; } int main() { int x1,x2,y1,y2,m,n,i,j; stk *st=NULL; scanf("%d %d",&m,&n); scanf("%d %d %d %d",&x1,&y1,&x2,&y2); for(i=0;i<=m-1;i++) for(j=0;j<=n-1;j++) { scanf("%d",&migong[i][j]); } st=creat_seq(); if(path(migong,direction,x1,y1,x2,y2,m,n,st)==1) output_seq(st); else printf("No Path!"); return 0; }
如有雷同,纯属巧合.
