栈与队列,是很多学习算法的同学遇到第一只拦路虎,很多人从这一章开始坐晕车,一直晕到现在。所以,理解栈与队列,是走向算法高手的一条必由之路。栈与队列的题目涉及面很广,也很灵活。但是也是很实用的呢。
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)
评论