栈与队列，是很多学习算法的同学遇到第一只拦路虎，很多人从这一章开始坐晕车，一直晕到现在。所以，理解栈与队列，是走向算法高手的一条必由之路。栈与队列的题目涉及面很广，也很灵活。但是也是很实用的呢。 1.用队列来走一个4X4的迷宫，具体严本上有算法，这里只是实现。 #include #define m 4 #define n 4 int mg[m+1][n+1]; struct mgque { int x,y,pre; }mgque[25];/*队列：用来存路径*/ struct zl { int x,y; }zl[5];/*四个方向的增量*/ int outlj(struct mgque mgque[],int rear) { int i; i=rear; do{ printf("(%d,%d)",mgque[i].x,mgque[i].y); i=mgque[i].pre; }while(i!=0); }/*输出用rear反方向输出*/ int mglj() { int x,y,i=1,j=1,d,find;/*d是用来循环的增量*/ int rear=0,front=0; mgque[0].x=1;mgque[0].y=1;mgque[0].pre=-1; mg[1][1]=-1;/*迷宫左上第一个，若为0可通，标志为-1防止重复*/ find=0; while(front<=rear&&!find) { x=mgque[front].x;y=mgque[front].y; for(d=1;d<=4;d++) { i=x+zl[d].x; j=y+zl[d].y; if(mg[i][j]==0) { rear++; mgque[rear].x=i; mgque[rear].y=j; mgque[rear].pre=front; mg[i][j]=-1; } if((i==m)&&(j==n)) { find=1; outlj(mgque,rear); return 1; } }/*如果方向上的值为0表示可以通，入队，保存队列静态下标pre*/ front++; } printf("no way!"); return 0; } int main() { int i,j; /*下面初始化迷宫*/ for(i=1;i<=m;i++) for(j=1;j<=n;j++) scanf("%d",&mg[i][j]); for(i=0;i<=m+1;i++) { mg[i][0]=1; mg[i][n+1]=1; } for(j=0;j<=n+1;j++) { mg[0][j]=1; mg[m+1][j]=1; } for(i=0;i<=m+1;i++) for(j=0;j<=n+1;j++) { printf("%2d",mg[i][j]); if(j==(n+1))printf("\n"); } /*用来测试输入迷宫*/ zl[1].x=0;zl[1].y=-1; zl[2].x=-1;zl[2].y=0; zl[3].x=0;zl[3].y=1; zl[4].x=1;zl[4].y=0;/*四个方向上增量*/ mglj(); } 2.数制转换 栈(stack)就是线性表，但是受限制的线性表，特性FILO，使用前依然要先定义，分配空间。 #include #define Max 100 typedef struct sqstack{ int element[Max]; int top; }Stack; push(Stack *s,int x)/*压入x，参数为指针s，压入数据x*/ { if(s->top==Max-1)exit(0); s->top++; s->element[s->top]=x; } int pop(Stack *s)/*弹出，出栈操作返回datatype*/ { int x; if(s->top==-1)exit(0); x=s->element[s->top]; s->top--; return x; } EmptyS(Stack *s) /*判断空栈*/ { return s->top==-1; } main() { int N=1348; Stack *s; s=(Stack *)malloc(sizeof(Stack)); s->top=-1; while(N) { push(s,N%8); N=N/8; } while(EmptyS) { printf("%d",pop(s)); } } 3.报数问题，薛超英书上的。题目忘了:) #include main() { int a[8]; int i,j,f,r; for(i=0;i<8;i++) a[i]=i+1; f=0;r=7;/*注意指针位置！！！这里的指针并不是地址指针呢！*/ while(f!=r) { printf("%d ",a[f]); f=(f+1)%8; r=(r+1)%8; a[r]=a[f]; f=(f+1)%8; } printf("%d ",a[f]); } 4.报数问题，找到题目了 /*n个人按12121212...的方法报数，数到1出列，数到2站到队伍的最右端，求出列顺序。输入样例：12345678输出：*/ #include typedef struct Queue{ int a[8]; int front; int left; int count; }CircleQ; /*队列以count记数*/ int delq(CircleQ *q) /*出队*/ { int y; y=q->a[q->front]; q->front=(q->front+1)%8; q->count--; if(q->front==q->left)q->count=0; return y; } void Enq(CircleQ *q,int b)/*入队*/ { q->a[q->left]=b; q->left=(q->left+1)%8; q->count++; } main() { CircleQ *p; int i,j; p=(CircleQ *)malloc(sizeof(CircleQ)); for(i=0;i<8;i++) p->a[i]=i+1; p->front=p->left=0;/*队列满，所以，两指针重合！！！*/ p->count=8; while(p->count!=0) /*1，出队一个 2，下一个出队元素入队*/ { printf("%d ",delq(p)); j=delq(p); Enq(p,j); } } 5.链栈 /*此例主要理会建栈和地址传递(y)的应用*/ #include typedef struct stack_node{ char data; struct stack_node *next; }SLnode;/*栈结点结构*/ typedef struct { SLnode *top; }LS;/*栈顶指针*/ void InitStack(LS *s)/*建空栈*/ { s->top=NULL; } void Push(LS *s,char x)/*入栈*/ { SLnode *p; p=(SLnode *)malloc(sizeof(SLnode));/*结点空间生成*/ p->data=x; p->next=s->top;/*指针指向*/ s->top=p; } char pop(LS *s,char *y) { SLnode *p; *y=s->top->data;/*通过地址传递得到栈顶元素值*/ p=s->top; s->top=p->next;/*修改栈顶指针*/ free(p);/*释放空间*/ } void main() { LS *s;char y; s=(LS *)malloc(sizeof(LS)); /*s的定义也可以用 LS s;然后赋予下面的各个函数以&s;如果这样则&s也是LS*型的地址*/ InitStack(s); Push(s,'a'); Push(s,'b'); Push(s,'e'); pop(s,&y); printf("%c",y); } 6.循环队列 #include #define Max 100 typedef struct queue{ int front; int rear; int count; /*计数器来判断q->front与q->rear相等时是否空满*/ int data[Max]; }Cq; void InitCq(Cq *q) { q->front=q->rear=0; q->count=0; } int CqEmpty(Cq *q) { return q->count==0; } void CqFull(Cq *q) { return q->count==Max; } void EnQ(Cq *q,int x) /*入队*/ { if(CqFull(q))printf("error!"); q->data[q->rear]=x; q->count++; q->rear=(q->rear+1)%Max; /*这一句是循环队列的关键所在*/ } int DeQ(Cq *q) /*出队*/ { int x; if(CqEmpty(q))printf("error!"); x=q->data(q->front); q->front=(q->front+1)%Max; /*牢记循环队列的条件！?！出队操作也是一样的*/ q->count--; return x; } main() { int i; Cq *q; q=(Cq *)malloc(sizeof(Cq)); } 7.中缀后缀转换 转换例子 18*(3+9)/4 转 18 3 9 + * 4 / 16-9*(4+3) 转 16 9 4 3 + * - 请自行转下下面的 3*(x-y)/(1+x)
评论