主题:小弟也写了个迷宫,是我的课程设计作业,大家给点意见
我大二,刚学数据结构,大家看下这个程序,有什么不足的地方和我说下,我会努力做好的
#include"stdio.h"
#include"malloc.h"
struct node//迷宫链表结点
{
int a[100];
int col;//记录行数
struct node *next;
struct node *rear;
};
struct stacknode//链栈结点
{
int data;
struct node *row;
struct stacknode *next;
};
struct stack
{
struct stacknode *top;
};
struct stack * Creatstack( struct stack *s)//创建链栈
{
struct stacknode *p;
s=(struct stack *)malloc(sizeof(struct stack));
p=(struct stacknode *)malloc(sizeof(struct stacknode));
p=NULL;
s->top=p;
return s;
}
struct stack *push(struct stack *s,int i,struct node *p)//压栈
{
struct stacknode *q;
q=(struct stacknode *)malloc(sizeof(struct stacknode));
q->data=i;
q->row=p;
q->next=s->top;
s->top=q;
return s;
}
struct stack *pop(struct stack *s)//出栈
{
struct stacknode *q;
q=s->top;
s->top=s->top->next;
delete q;
return s;
}
struct node *Creat(int i,int j)//创建迷宫,用链表创建,结点为迷宫行数,结点数据a[i]为迷宫每行数据
{
struct node *head,*p,*q;
int m,n;
head=(struct node *)malloc(sizeof(struct node));
head->col=j;//总行数为j
for(n=0;n<j+2;n++)
head->a[n]=1;//创建围墙
p=head;
for(m=1;m<i+1;m++)//循环输入0,1
{
q=(struct node *)malloc(sizeof(struct node));
printf("输入第%d行\n",m);
q->a[0]=1;
q->a[j+1]=1;
for(n=1;n<j+1;n++)
scanf("%d",&q->a[n]);
printf("第%d行为",m);
for(n=1;n<j+1;n++)
printf("% d",q->a[n]);
printf("\n");
p->next=q;
q->rear=p;
p=q;
}
q=(struct node *)malloc(sizeof(struct node));
for(n=0;n<j+2;n++)//创建围墙
q->a[n]=1;
p->next=q;
q->rear=p;
p=q;
p->next=NULL;
return head;
}
struct node * print(struct node *head)//输出创建好的迷宫
{
struct node *p,*q;
int i;
p=head;
q=head;
printf("迷宫为:\n");
for(;p->next!=NULL;p=p->next)
{
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
printf("\n");
}
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
return head;
}
struct node *search(struct node *head)//寻找迷宫路径
{
int i,j,j1,m,n,x,y;
struct node *p,*q;
struct stack *s;
s=Creatstack(s);
printf("输入入口行数为:");
scanf("%d",&m);
printf("输入入口列数为:");
scanf("%d",&n);
printf("输入出口行数为:");
scanf("%d",&x);
printf("输入出口列数为:");
scanf("%d",&y);
j=0;
j1=0;
i=0;
p=head;
q=head;
do//寻找入口行
{
p=p->next;
j++;
}while(j!=m);
do//寻找出口行
{
q=q->next;
j1++;
}while(j1!=x);
do//寻找入口列
{
i++;
}while(i!=n);
p->a[i]=-1;//标记入口
for(;q->a[y]!=-1;)//标记出口,作为循环结束标志
{
if(p->a[i+1]==0)//向右查找
{
p->a[i+1]=-1;//标记通路
s=push(s,i,p);//将走过的路径入栈
i++;
}
else if(p->a[i-1]==0)//向左查找
{
p->a[i-1]=-1;
s=push(s,i,p);
i--;
}
else if(p->next->a[i]==0)//向下查找
{
p->next->a[i]=-1;
s=push(s,i,p);
p=p->next;
}
else if(p->rear->a[i]==0)//向上查找
{
p->rear->a[i]=-1;
s=push(s,i,p);
p=p->rear;
}
else if(s->top!=NULL)//死胡同
{
p->a[i]=-2;//标记死胡同
p=s->top->row;//回到上一路径
i=s->top->data;
s=pop(s);//将死胡同出栈
}
else
{
printf("无通路\n");
break;
}
}
return head;
}
void printsearch(struct node *head)//输出查找完成后的迷宫
{
struct node *p,*q;
int i;
p=head;
q=head;
printf("迷宫为:\n");
for(;p->next!=NULL;p=p->next)
{
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)//将不同标记以不同符号输出
printf(" ");
else if(p->a[i]==-1)
printf("* ");
else if(p->a[i]==-2)
printf("@ ");
else
printf("# ");
}
printf("\n");
}
for(i=0;i<=q->col+1;i++)//输出围墙
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
}
void main()
{
struct node *p;
int i,j;
printf("输入迷宫行数为:");
scanf("%d",&i);
printf("输入迷宫列数为:");
scanf("%d",&j);
p=Creat(i,j);
p=print(p);
printf("\n");
p=search(p);
printsearch(p);
}
#include"stdio.h"
#include"malloc.h"
struct node//迷宫链表结点
{
int a[100];
int col;//记录行数
struct node *next;
struct node *rear;
};
struct stacknode//链栈结点
{
int data;
struct node *row;
struct stacknode *next;
};
struct stack
{
struct stacknode *top;
};
struct stack * Creatstack( struct stack *s)//创建链栈
{
struct stacknode *p;
s=(struct stack *)malloc(sizeof(struct stack));
p=(struct stacknode *)malloc(sizeof(struct stacknode));
p=NULL;
s->top=p;
return s;
}
struct stack *push(struct stack *s,int i,struct node *p)//压栈
{
struct stacknode *q;
q=(struct stacknode *)malloc(sizeof(struct stacknode));
q->data=i;
q->row=p;
q->next=s->top;
s->top=q;
return s;
}
struct stack *pop(struct stack *s)//出栈
{
struct stacknode *q;
q=s->top;
s->top=s->top->next;
delete q;
return s;
}
struct node *Creat(int i,int j)//创建迷宫,用链表创建,结点为迷宫行数,结点数据a[i]为迷宫每行数据
{
struct node *head,*p,*q;
int m,n;
head=(struct node *)malloc(sizeof(struct node));
head->col=j;//总行数为j
for(n=0;n<j+2;n++)
head->a[n]=1;//创建围墙
p=head;
for(m=1;m<i+1;m++)//循环输入0,1
{
q=(struct node *)malloc(sizeof(struct node));
printf("输入第%d行\n",m);
q->a[0]=1;
q->a[j+1]=1;
for(n=1;n<j+1;n++)
scanf("%d",&q->a[n]);
printf("第%d行为",m);
for(n=1;n<j+1;n++)
printf("% d",q->a[n]);
printf("\n");
p->next=q;
q->rear=p;
p=q;
}
q=(struct node *)malloc(sizeof(struct node));
for(n=0;n<j+2;n++)//创建围墙
q->a[n]=1;
p->next=q;
q->rear=p;
p=q;
p->next=NULL;
return head;
}
struct node * print(struct node *head)//输出创建好的迷宫
{
struct node *p,*q;
int i;
p=head;
q=head;
printf("迷宫为:\n");
for(;p->next!=NULL;p=p->next)
{
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
printf("\n");
}
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
return head;
}
struct node *search(struct node *head)//寻找迷宫路径
{
int i,j,j1,m,n,x,y;
struct node *p,*q;
struct stack *s;
s=Creatstack(s);
printf("输入入口行数为:");
scanf("%d",&m);
printf("输入入口列数为:");
scanf("%d",&n);
printf("输入出口行数为:");
scanf("%d",&x);
printf("输入出口列数为:");
scanf("%d",&y);
j=0;
j1=0;
i=0;
p=head;
q=head;
do//寻找入口行
{
p=p->next;
j++;
}while(j!=m);
do//寻找出口行
{
q=q->next;
j1++;
}while(j1!=x);
do//寻找入口列
{
i++;
}while(i!=n);
p->a[i]=-1;//标记入口
for(;q->a[y]!=-1;)//标记出口,作为循环结束标志
{
if(p->a[i+1]==0)//向右查找
{
p->a[i+1]=-1;//标记通路
s=push(s,i,p);//将走过的路径入栈
i++;
}
else if(p->a[i-1]==0)//向左查找
{
p->a[i-1]=-1;
s=push(s,i,p);
i--;
}
else if(p->next->a[i]==0)//向下查找
{
p->next->a[i]=-1;
s=push(s,i,p);
p=p->next;
}
else if(p->rear->a[i]==0)//向上查找
{
p->rear->a[i]=-1;
s=push(s,i,p);
p=p->rear;
}
else if(s->top!=NULL)//死胡同
{
p->a[i]=-2;//标记死胡同
p=s->top->row;//回到上一路径
i=s->top->data;
s=pop(s);//将死胡同出栈
}
else
{
printf("无通路\n");
break;
}
}
return head;
}
void printsearch(struct node *head)//输出查找完成后的迷宫
{
struct node *p,*q;
int i;
p=head;
q=head;
printf("迷宫为:\n");
for(;p->next!=NULL;p=p->next)
{
for(i=0;i<=q->col+1;i++)
{
if(p->a[i]==0)//将不同标记以不同符号输出
printf(" ");
else if(p->a[i]==-1)
printf("* ");
else if(p->a[i]==-2)
printf("@ ");
else
printf("# ");
}
printf("\n");
}
for(i=0;i<=q->col+1;i++)//输出围墙
{
if(p->a[i]==0)
printf(" ");
else
printf("# ");
}
}
void main()
{
struct node *p;
int i,j;
printf("输入迷宫行数为:");
scanf("%d",&i);
printf("输入迷宫列数为:");
scanf("%d",&j);
p=Creat(i,j);
p=print(p);
printf("\n");
p=search(p);
printsearch(p);
}