走迷宫-实验报告

数据结构课程设计报告题目：迷宫问题院系名称：专业名称：班级：学号：学生姓名：指导教师：时间：课程设计目的1.熟悉数据结构中的各种存储结构，并且能够熟练的运用各种存储结构。2.利用所学的内容完成迷宫路径的寻找，不可使用递归。 二、课程设计内容1.迷宫存储在文件中，通过输入文件名（*.in），创建相应的迷宫。迷宫文件的格式自己设计。2.最终的解要求在屏幕上显示并存入文件(*.out)中。解的显示方式以及解文件的格式自己设计。如果有多条，求得路径长度最短的一条路径。三、需求分析1.本程序可以由使用者输入迷宫，并且在迷宫有路径时将迷宫及最短路径存储在文件中。也可实现系统中存储的迷宫（系统中必须有迷宫，否则程序无法进行）并存储最短路径。2.可以找出每一个迷宫的最短路径，并且要判断迷宫是否有解。3.若迷宫有解，输出最短路径并保存。若迷宫无解则终止程序。概要设计1.系统结构图开始程序M开始程序Main（）选择需求：1.自己输入迷宫。2.选择系统迷宫。3.输出系统所存迷宫的解。4.退出程序\选择1，用户输入迷宫，并保存。选择2，用户选择系统迷宫。选择3，用户选择输出迷宫的最短路径。选择4，终止程序。判断迷宫是否有路径找出最短路径，并保存路径。终止程序。main（）：主函数。readhead(structNode*head):从文件中读出系统迷宫的信息。out（）：输出系统迷宫的信息。read1（）：载入系统迷宫最短路径。savejie（）：将迷宫的最短路径保存在文件中。PD（）：判断迷宫是否有路径，若有路径进行下一步，若无路径则终止程序。savehead（）：保存迷宫文件及解文件的信息。PrintMaze（）：用户输入迷宫程序，并且在有路径时保存迷宫（用户自行命名文件名）并命名保存此迷宫最短路径的文件名。read（）：载入系统迷宫。Change（）：标记最短路径，以便保存于显示。MazePath（），save（）：寻找迷宫最短路径。Print2（）：用于输出找到最短路径时的迷宫及路径。Print（）：用于输出找路径前的迷宫。PosTypeNextPoint（）：方向判断函数。详细设计及运行结果main（）main（）readhead()选择:ii=3;out();read1();Print2();i=1;PrintMaze();savehead();i=2;out();read();终止程序Print()PD()MazePath();save();Change();savejie();Print2();i=4i=4 迷宫无路径迷宫无路径定义链表，用于存放迷宫信息。typedefstructNode{ charname[20];/迷宫文件名/ intm;/行数/ intn;/列数/ charjie[20];/最短路径文件名/ structNode*next;}Node;typedefstruct{intr,c;/*迷宫中位置的坐标*/}PosType;typedefstruct{intm,n;chararr[SIZE][SIZE];/*用二维数组表示迷宫*/}MazeType;确定放入栈中的元素的存储结构，表明通道块在路径上的“序号”，通道块的坐标位置以及下一步要走的方向。typedefstruct{intstep;PosTypeseat;/*当前位置在迷宫中的坐标*/intdi;/*从当前位置走到下一位置的方向*/}ElemType;确定栈的存储结构。typedefstructNodeType{ElemTypedata[SIZE];inttop;}SeqStack;初始化栈。voidInitStack(SeqStack*s){ s->top=-1;}入栈。intPush(SeqStack*s,ElemTypee){ if(s->top==SIZE-1)return0; s->top++; s->data[s->top]=e; return1;}出栈。intPop(SeqStack*s,ElemType*e){ if(s->top==-1) return0; else { *e=s->data[s->top]; s->top--; return1; }}取栈顶。intGetTop(SeqStack*s,ElemType*e){ if(s->top==-1) return0; else { *e=s->data[s->top]; return1; }}判栈空。intEmpty(SeqStack*s){ if(s->top==-1) return1; else return0;}定义在探索过程中的方向关系PosTypeNextPoint(PosTypecurpos,intdi){switch(di) {case1: curpos.c++;break;case2:curpos.r++;break;case3:curpos.c--;break;case4:curpos.r--;break; case5: break; }returncurpos;}找出最短路径。intMazePath(SeqStack*s,MazeType*L){ inti,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; return1; } 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++; }}判断迷宫是否有路径。intPD(MazeType*P,SeqStack*z,structNode*head){structNode*p; inti,j,k,count=1; inta,b; ElemTypee,t;PosTypev[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); gotoloop; } } } 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"); return1; } elseif(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)) { return1; } 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>#defineNsizeof(int)#defineSIZE100#defineKsizeof(structNode)intA=0;charname1[20];charname2[20];typedefstructNode{ charname[20]; intm; intn; charjie[20]; structNode*next;}Node;typedefstruct{intr,c;}PosType;typedefstruct{intm,n;intarr[SIZE][SIZE];}MazeType;typedefstruct{ intcount; PosTypehl[SIZE];}Save;typedefstruct{intstep;PosTypeseat;intdi;}ElemType;typedefstructNodeType{ElemTypedata[SIZE];inttop;}SeqStack;voidInitStack(SeqStack*s){ s->top=-1;}intPush(SeqStack*s,ElemTypee){ if(s->top==SIZE-1)return0; s->top++; s->data[s->top]=e; return1;}intPop(SeqStack*s,ElemType*e){ if(s->top==-1) return0; else { *e=s->data[s->top]; s->top--; return1; }}intGetTop(SeqStack*s,ElemType*e){ if(s->top==-1) return0; else { *e=s->data[s->top]; return1; }}intEmpty(SeqStack*s){ if(s->top==-1) return1; else return0;}PosTypeNextPoint(PosTypecurpos,intdi){switch(di) {case1: curpos.c++;break;case2:curpos.r++;break;case3:curpos.c--;break;case4:curpos.r--;break; case5: break; }returncurpos;}intsave(SeqStack*s,MazeType*L){ inti,j,k,count,l=1; inta,b; ElemTypee,t;PosTypev[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); gotoloop; } } } 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); return1; } elseif(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)) return1; else return0;}voidPrint(MazeType*L){ inti,j; for(i=0;i<L->m;i++) { printf("\n"); for(j=0;j<L->n;j++) { if(L->arr[i][j]==1) printf("#"); elseif(L->arr[i][j]==2) printf("入"); elseif(L->arr[i][j]==9999) printf("出"); else printf(""); } } printf("\n");}voidPrint2(MazeType*L){ inti,j; for(i=0;i<L->m;i++) { printf("\n"); for(j=0;j<L->n;j++) { if(L->arr[i][j]==1) printf("#"); elseif(L->arr[i][j]==2) printf("入"); elseif(L->arr[i][j]==9999) printf("出"); elseif(L->arr[i][j]==10000) printf("--"); elseif(L->arr[i][j]==10001) printf("*"); else printf(""); } } printf("\n");}intMazePath(SeqStack*s,MazeType*L){ inti,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; return1; } 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++; }}voidChange(SeqStack*s,MazeType*L){ ElemTypee[5000]; inti,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; }}voidread(MazeType*L,structNode*head){ FILE*fp; inti,j,k=0;structNode*p; charname[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);}voidreadhead(structNode*head){ FILE*fp; structNode*p; inti; fp=fopen("head.txt","rb"); while(1) { p=(structNode*)malloc(K); i=fread(p,K,1,fp); if(i==0) { free(p); break; } p->next=head->next; head->next=p; } fclose(fp);}voidPrintMaze(MazeType*L,structNode*head){ FILE*fp; inti,j,k,l,x=0; charname[20]; charnaj[20];structNode*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=(structNode*)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);}voidsavehead(structNode*head){ FILE*fp; structNode*p; p=head->next; fp=fopen("head.txt","wb"); while(p!=NULL)//尾节点的地址处不为NULL！！！！ { fwrite(p,K,1,fp); p=p->next; } fclose(fp);}intPD(MazeType*P,SeqStack*z,structNode*head){structNode*p; inti,j,k,count=1; inta,b; ElemTypee,t;PosTypev[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); gotoloop; } } } 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"); return1; } elseif(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)) { return1; } else { printf("此迷宫无解！！！\n"); head->next=p->next; free(p); savehead(head); printf("此迷宫无解请按任意键关闭程序！！\n");getch(); exit(-1); } }voidsavejie(MazeType*L,structNode*head){ FILE*fp; inti,j; structNode*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);}voidread1(MazeType*L,structNode*head){ FILE*fp; inti,j,k=0;structNode*p; charname[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==