数据结构课程设计报告
题 目： 迷宫问题
一、 课程设计目的
1.熟悉数据结构中的各种存储结构，并且能够熟练的运用各种存储结构。
2.利用所学的内容完成迷宫路径的寻找，不可使用递归。
二、课程设计内容
1.迷宫存储在文件中，通过输入文件名（*.in），创建相应的迷宫。迷宫文件的格式自己设计。
2.最终的解要求在屏幕上显示并存入文件(*.out)中。解的显示方式以及解文件的格式自己设计。
3．如果有多条，求得路径长度最短的一条路径。
三、需求分析
1.本程序可以由使用者输入迷宫，并且在迷宫有路径时将迷宫及最短路径存储在文件中。也可实现系统中存储的迷宫（系统中必须有迷宫，否则程序无法进行）并存储最短路径。
2.可以找出每一个迷宫的最短路径，并且要判断迷宫是否有解。
3.若迷宫有解，输出最短路径并保存。若迷宫无解则终止程序。
四、概要设计
1.系统结构图
main（）：主函数。
readhead(struct Node * head):从文件中读出系统迷宫的信息。
out（）：输出系统迷宫的信息。
read1（）：载入系统迷宫最短路径。
savejie（）：将迷宫的最短路径保存在文件中。
PD（）：判断迷宫是否有路径，若有路径进行下一步，若无路径则终止程序。
savehead（）：保存迷宫文件及解文件的信息。
PrintMaze（）：用户输入迷宫程序，并且在有路径时保存迷宫（用户自行命名文件名）并命名保存此迷宫最短路径的文件名。
read（）：载入系统迷宫。
Change（）：标记最短路径，以便保存于显示。
MazePath（），save（）：寻找迷宫最短路径。
Print2（）：用于输出找到最短路径时的迷宫及路径。
Print（）：用于输出找路径前的迷宫。
PosType NextPoint（）：方向判断函数。
五、详细设计及运行结果
定义链表，用于存放迷宫信息。
typedef struct Node
{
char name[20]; /迷宫文件名/
int m; /行数/
int n; /列数/
char jie[20]; /最短路径文件名/
struct Node * next;
}Node;
typedef struct
{
int r,c; /*迷宫中位置的坐标*/
}PosType;
typedef struct
{
int m,n;
char arr[SIZE][SIZE]; /*用二维数组表示迷宫*/
}MazeType;
确定放入栈中的元素的存储结构，表明通道块在路径上的“序号”，通道块的坐标位置以及下一步要走的方向。
typedef struct
{
int step;
PosType seat; /*当前位置在迷宫中的坐标*/
int di; /*从当前位置走到下一位置的方向*/
}ElemType;
确定栈的存储结构。
typedef struct NodeType
{
ElemType data[SIZE];
int top;
}SeqStack;
初始化栈。
void InitStack(SeqStack * s)
{
s->top=-1;
}
入栈。
int Push(SeqStack * s,ElemType e)
{
if(s->top==SIZE-1) return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
出栈。
int Pop(SeqStack * s,ElemType * e)
{
if(s->top==-1)
return 0;
else
{
*e=s->data[s->top];
s->top--;
return 1;
}
}
取栈顶。
int GetTop(SeqStack * s,ElemType * e)
{
if(s->top==-1)
return 0;
else
{
*e=s->data[s->top];
return 1;
}
}
判栈空。
int Empty(SeqStack * s)
{
if(s->top==-1)
return 1;
else
return 0;
}
定义在探索过程中的方向关系
PosType NextPoint(PosType curpos,int di)
{
switch(di)
{
case 1:
curpos.c++;
break;
case 2:
curpos.r++;
break;
case 3:
curpos.c--;
break;
case 4:
curpos.r--;
break;
case 5:
break;
}
return curpos;
}
找出最短路径。
int MazePath(SeqStack * s,MazeType * L)
{
int i,j,k=2;
InitStack(s);
while(1)
{
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
if(L->arr[i][j]==k)
{
k++;
if(L->arr[i+1][j]==9999 || L->arr[i-1][j]==9999 || L->arr[i][j+1]==9999 || L->arr[i][j-1]==9999)/判断是否到出口/
{
A=k-1;
return 1;
}
L->arr[i+1][j]=L->arr[i+1][j]+k; /给四个方向上的每一
L->arr[i-1][j]=L->arr[i-1][j]+k; 个数值加k；/
L->arr[i][j+1]=L->arr[i][j+1]+k;
L->arr[i][j-1]=L->arr[i][j-1]+k;
if(L->arr[i+1][j]!=k)
L->arr[i+1][j]=L->arr[i+1][j]-k; /找到数值为k的位置，
if(L->arr[i-1][j]!=k) 数值不为k的减去k;/
L->arr[i-1][j]=L->arr[i-1][j]-k;
if(L->arr[i][j+1]!=k)
L->arr[i][j+1]=L->arr[i][j+1]-k;
if(L->arr[i][j-1]!=k)
L->arr[i][j-1]=L->arr[i][j-1]-k;
k--;
}
}
}
k++;
}
}
判断迷宫是否有路径。
int PD(MazeType * P,SeqStack * z,struct Node * head)
{
struct Node * p;
int i,j,k,count=1;
int a,b;
ElemType e,t;
PosType v[5];
InitStack(z);
p=head->next;
for(i=0;i<P->m;i++)
{
for(j=0;j<P->n;j++)
{
if(P->arr[i][j]==2)
{
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(z,e);
goto loop;
}
}
}
loop:
while(!Empty(z))
{
GetTop(z,&t);
v[0].r=t.seat.r;
v[0].c=t.seat.c;
k=t.di+1;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
while(k<5)
{
if(P->arr[i][j]==9999)
{
count++;
z->data[z->top].di=k;
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(z,e);
printf("此迷宫有解请按任意键继续！！\n");
getch();
system("cls");
return 1;
}
else if(P->arr[i][j]==0)
{
count++;
z->data[z->top].di=k;
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
P->arr[i][j]=4;
Push(z,e);
break;
}
else
{
k++;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
}
if(k>4)
{
Pop(z,&e);
count--;
a=e.seat.r;
b=e.seat.c;
P->arr[a][b]=5;
}
}
}
if(!Empty(z))
{
return 1;
}
else
{
printf("此迷宫无解！！！\n");
head->next=p->next;
free(p);
savehead(head);
printf("此迷宫无解请按任意键关闭程序！！\n");
getch();
exit(-1);
}
}
主界面
有路径时：
输出迷宫最短路径：
用户自行输入迷宫：
迷宫无解时：
输出系统迷宫的最短路径;
六、调试情况，设计技巧及体会
在本次实习中，我每天能够积极的投入到实习课程中，每天积极的解决程序中所出现的问题，能够积极的和同学讨论问题。总体来说在这一周的实习过程中我表现良好。
在程序中合理之处在于寻找最短路径时程序十分的简单，明了。能够通过最短的时间找出最短路径。
不足之处在于无法找到所有路径，并且在存储时建立过多的文档，使得存储空间过多的浪费。
体会：
在这次为期一周的课程设计让我更加清晰的认识到数据结构的重要性。数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。
通过这次数据结构课程设计，让我学到了好多东西。在实际操作过程中犯了一些错误却让我有了意外的收获，所学数据结构理论知识得到了巩固。通过实际操作，学会数据结构程序编程的基本步骤、基本方法，开发了自己的逻辑思维能力，培养了分析问题、解决问题的能力。
七、参考文献
高等教育出版设 《数据结构（C语言描述）》耿国华主编；
清华大学出版社 《数据结构（C语言版）》严蔚敏主编；
清华大学出版社 《C程序设计》谭浩强 著。
八、附录：源代码
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<windows.h>
#include<string.h>
#define N sizeof(int)
#define SIZE 100
#define K sizeof(struct Node)
int A=0;
char name1[20];
char name2[20];
typedef struct Node
{
char name[20];
int m;
int n;
char jie[20];
struct Node * next;
}Node;
typedef struct
{
int r,c;
}PosType;
typedef struct
{
int m,n;
int arr[SIZE][SIZE];
}MazeType;
typedef struct
{
int count;
PosType hl[SIZE];
}Save;
typedef struct
{
int step;
PosType seat;
int di;
}ElemType;
typedef struct NodeType
{
ElemType data[SIZE];
int top;
}SeqStack;
void InitStack(SeqStack * s)
{
s->top=-1;
}
int Push(SeqStack * s,ElemType e)
{
if(s->top==SIZE-1) return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int Pop(SeqStack * s,ElemType * e)
{
if(s->top==-1)
return 0;
else
{
*e=s->data[s->top];
s->top--;
return 1;
}
}
int GetTop(SeqStack * s,ElemType * e)
{
if(s->top==-1)
return 0;
else
{
*e=s->data[s->top];
return 1;
}
}
int Empty(SeqStack * s)
{
if(s->top==-1)
return 1;
else
return 0;
}
PosType NextPoint(PosType curpos,int di)
{
switch(di)
{
case 1:
curpos.c++;
break;
case 2:
curpos.r++;
break;
case 3:
curpos.c--;
break;
case 4:
curpos.r--;
break;
case 5:
break;
}
return curpos;
}
int save(SeqStack * s,MazeType * L)
{
int i,j,k,count,l=1;
int a,b;
ElemType e,t;
PosType v[5];
InitStack(s);
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
if(L->arr[i][j]==2)
{
e.step=l;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(s,e);
goto loop;
}
}
}
loop:
count=2;
while(!Empty(s))
{
GetTop(s,&t);
v[0].r=t.seat.r;
v[0].c=t.seat.c;
k=t.di+1;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
while(k<5)
{
if(L->arr[i][j]==9999)
{
l++;
s->data[s->top].di=k;
e.step=l;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(s,e);
return 1;
}
else if(L->arr[i][j]==count+1)
{
l++;
s->data[s->top].di=k;
e.step=l;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(s,e);
count++;
break;
}
else
{
k++;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
}
if(k>4)
{
Pop(s,&e);
count--;
l--;
a=e.seat.r;
b=e.seat.c;
L->arr[a][b]=10000;
}
}
}
if(!Empty(s))
return 1;
else
return 0;
}
void Print(MazeType * L)
{
int i,j;
for(i=0;i<L->m;i++)
{
printf("\n");
for(j=0;j<L->n;j++)
{
if(L->arr[i][j]==1)
printf("# ");
else if(L->arr[i][j]==2)
printf("入");
else if(L->arr[i][j]==9999)
printf("出");
else
printf(" ");
}
}
printf("\n");
}
void Print2(MazeType * L)
{
int i,j;
for(i=0;i<L->m;i++)
{
printf("\n");
for(j=0;j<L->n;j++)
{
if(L->arr[i][j]==1)
printf("# ");
else if(L->arr[i][j]==2)
printf("入");
else if(L->arr[i][j]==9999)
printf("出");
else if(L->arr[i][j]==10000)
printf("--");
else if(L->arr[i][j]==10001)
printf("* ");
else
printf(" ");
}
}
printf("\n");
}
int MazePath(SeqStack * s,MazeType * L)
{
int i,j,k=2;
InitStack(s);
while(1)
{
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
if(L->arr[i][j]==k)
{
k++;
if(L->arr[i+1][j]==9999 || L->arr[i-1][j]==9999 || L->arr[i][j+1]==9999 || L->arr[i][j-1]==9999)
{
A=k-1;
return 1;
}
L->arr[i+1][j]=L->arr[i+1][j]+k;
L->arr[i-1][j]=L->arr[i-1][j]+k;
L->arr[i][j+1]=L->arr[i][j+1]+k;
L->arr[i][j-1]=L->arr[i][j-1]+k;
if(L->arr[i+1][j]!=k)
L->arr[i+1][j]=L->arr[i+1][j]-k;
if(L->arr[i-1][j]!=k)
L->arr[i-1][j]=L->arr[i-1][j]-k;
if(L->arr[i][j+1]!=k)
L->arr[i][j+1]=L->arr[i][j+1]-k;
if(L->arr[i][j-1]!=k)
L->arr[i][j-1]=L->arr[i][j-1]-k;
k--;
}
}
}
k++;
}
}
void Change(SeqStack * s,MazeType * L)
{
ElemType e[5000];
int i,j,k;
for(k=0;k<A;k++)
{
Pop(s,&e[A-1-k]);
}
for(k=1;k<A-1;k++)
{
i=e[k].seat.r;
j=e[k].seat.c;
L->arr[i][j]=10001;
}
}
void read(MazeType * L,struct Node * head)
{
FILE * fp;
int i,j,k=0;
struct Node * p;
char name[20];
p=head->next;
while(p!=NULL)
{
printf("请输入要打开的迷宫文件名：");
flushall();
gets(name);
while(p!=NULL)
{
if(strcmp(p->name,name)==0)
{
k++;
break;
}
else
{
p=p->next;
}
if(p==NULL)
{
printf("该文件不存在！！请重新输入！！\n");
p=head->next;
break;
}
}
if(k!=0)
break;
}
fp=fopen(name,"rb");
if(fp==NULL)
{
printf("error!");
exit(-1);
}
L->m=p->m;
L->n=p->n;
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
fread(&L->arr[i][j],N,1,fp);
}
}
fclose(fp);
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
printf("%2d",L->arr[i][j]);
}
printf("\n");
}
strcpy(name1,name);
}
void readhead(struct Node * head)
{
FILE * fp;
struct Node * p;
int i;
fp=fopen("head.txt","rb");
while(1)
{
p=(struct Node * )malloc(K);
i=fread(p,K,1,fp);
if(i==0)
{
free(p);
break;
}
p->next=head->next;
head->next=p;
}
fclose(fp);
}
void PrintMaze(MazeType * L,struct Node * head)
{
FILE * fp;
int i,j,k,l,x=0;
char name[20];
char naj[20];
struct Node * p1,* p2,* p;
p2=head;
p=head->next;
printf("请输入迷宫的行数 列数：");
scanf("%d %d",&k,&l);
printf("请输入迷宫1为墙，2为入口，9999为出口，0为路\n");
for(i=0;i<k;i++)
{
printf("第%d行\n",i+1);
for(j=0;j<l;j++)
{
scanf("%d",&L->arr[i][j]);
}
}
L->m=k;
L->n=l;
while(p!=NULL)
{
printf("请输入文件名以.txt为后缀(eg:1.txt)：");
flushall();
gets(name);
while(p!=NULL)
{
if(strcmp(p->name,name)==0 ||strcmp(p->jie,name)==0 )
{
printf("该文件存在!!请重新输入!!\n");
p=head->next;
break;
}
else
p=p->next;
}
}
p=head->next;
while(p!=NULL)
{
printf("请输入迷宫解的文件名以.txt为后缀(eg:1.txt)请不要与上一个文件名重复!!：");
flushall();
gets(naj);
while(p!=NULL)
{
if(strcmp(p->name,naj)==0 || strcmp(p->jie,name)==0)
{
printf("该文件存在!!请重新输入!!\n");
p=head->next;
break;
}
else
p=p->next;
}
}
fp=fopen(name,"wb");
if(fp==NULL)
{
printf("error!");
exit(-1);
}
for(i=0;i<k;i++)
{
for(j=0;j<l;j++)
{
fwrite(&L->arr[i][j],N,1,fp);
}
}
fclose(fp);
p1=(struct Node * )malloc(K);
p1->m=k;
p1->n=l;
strcpy(p1->name,name);
strcpy(p1->jie,naj);
p1->next=p2->next;
p2->next=p1;
strcpy(name2,name);
}
void savehead(struct Node * head)
{
FILE * fp;
struct Node * p;
p=head->next;
fp=fopen("head.txt","wb");
while(p!=NULL)//尾节点的地址处不为NULL！！！！
{
fwrite(p,K,1,fp);
p=p->next;
}
fclose(fp);
}
int PD(MazeType * P,SeqStack * z,struct Node * head)
{
struct Node * p;
int i,j,k,count=1;
int a,b;
ElemType e,t;
PosType v[5];
InitStack(z);
p=head->next;
for(i=0;i<P->m;i++)
{
for(j=0;j<P->n;j++)
{
if(P->arr[i][j]==2)
{
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(z,e);
goto loop;
}
}
}
loop:
while(!Empty(z))
{
GetTop(z,&t);
v[0].r=t.seat.r;
v[0].c=t.seat.c;
k=t.di+1;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
while(k<5)
{
if(P->arr[i][j]==9999)
{
count++;
z->data[z->top].di=k;
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
Push(z,e);
printf("此迷宫有解请按任意键继续！！\n");
getch();
system("cls");
return 1;
}
else if(P->arr[i][j]==0)
{
count++;
z->data[z->top].di=k;
e.step=count;
e.seat.r=i;
e.seat.c=j;
e.di=0;
P->arr[i][j]=4;
Push(z,e);
break;
}
else
{
k++;
v[k]=NextPoint(v[0],k);
i=v[k].r;
j=v[k].c;
}
if(k>4)
{
Pop(z,&e);
count--;
a=e.seat.r;
b=e.seat.c;
P->arr[a][b]=5;
}
}
}
if(!Empty(z))
{
return 1;
}
else
{
printf("此迷宫无解！！！\n");
head->next=p->next;
free(p);
savehead(head);
printf("此迷宫无解请按任意键关闭程序！！\n");
getch();
exit(-1);
}
}
void savejie(MazeType * L,struct Node * head)
{
FILE * fp;
int i,j;
struct Node * p,* p1;
p=head->next;
p1=head->next;
while(p!=NULL)
{
if(strcmp(p->name,name1)==0 || strcmp(p->name,name2)==0)
{
break;
}
else
p=p->next;
}
fp=fopen(p->jie,"wb");
if(fp==NULL)
{
printf("error!");
exit(-1);
}
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
fwrite(&L->arr[i][j],N,1,fp);
}
}
fclose(fp);
}
void read1(MazeType * L,struct Node * head)
{
FILE * fp;
int i,j,k=0;
struct Node * p;
char name[20];
p=head->next;
while(p!=NULL)
{
printf("请输入要打开的迷宫的解的文件名：");
flushall();
gets(name);
while(p!=NULL)
{
if(strcmp(p->jie,name)==0)
{
k++;
break;
}
else
{
p=p->next;
}
if(p==NULL)
{
printf("该文件不存在！！请重新输入！！\n");
p=head->next;
break;
}
}
if(k!=0)
break;
}
fp=fopen(name,"rb");
if(fp==NULL)
{
printf("error!");
exit(-1);
}
L->m=p->m;
L->n=p->n;
for(i=0;i<L->m;i++)
{
for(j=0;j<L->n;j++)
{
fread(&L->arr[i][j],N,1,fp);
}
}
fclose(fp);
}
out(struct Node * head)
{
struct Node * p;
p=head->next;
printf("================================\n");
printf("迷宫 行数 列数 最短路径\n");
printf("================================\n");
while(p!=NULL)
{
printf("%s %d %d %s\n",p->name,p->m,p->n,p->jie);
p=p->next;
}
}
void main()
{
struct Node * head;
int i;
SeqStack s,z;
MazeType L,P;
head=(struct Node * )malloc(K);
head->next=NULL;
readhead(head);
while(1)
{
while(1)
{
printf("请选择：\n");
printf("1.自己输入迷宫。\n2.选择系统迷宫。\n3.输出系统所存迷宫的解。\n4.退出程序\n");
scanf("%d",&i);
system("cls");
if(i==1)
{
PrintMaze(&L,head);
savehead(head);
break;
}
else if(i==2)
{
out(head);
read(&L,head);
break;
}
else if(i==3)
{
out(head);
read1(&L,head);
Print2(&L);
printf("请按任意键回到菜单!!\n");
getch();
system("cls");
continue;
}
else if(i==4)
exit(-1);
else
{
system("cls");
printf("输入错误!!请重新输入!!\n");
}
}
P=L;
Print(&L);
PD(&P,&z,head);
MazePath(&s,&L);
save(&s,&L);
Change(&s,&L);
printf("\n");
savejie(&L,head);
printf("迷宫通路为：\n");
Print2(&L);
printf("请按任意键回到菜单!!\n");
getch();
system("cls");
}
}