数据结构 课程设计 迷宫程序

第第页数据结构课程设计迷宫程序C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

目次

一．课程设计目的二．功能说明三．具体设计

3.1．功能模块设计3.1.1．主函数main()执行流程图3.1.2．创建模块3.1.3．操作模块3.1.4．显示模块3.1.5．其他模块3.2．数据结构设计3.3．函数功能描述

四．程序实现

4.1．源码分析4.2．调试结果

4.3．遇到的问题及解决4.4．时间繁复度分析4.5．算法的改进思想

五．结束语六．

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

一．课程设计目的

1.理解和掌控双向链表的数据结构。

2.了解迷宫问题的提出背景、机器穷举法求解思路。3.运用机器穷举法和双向链表结构实现迷宫路径的查找。4.设计实现一个完整的迷宫求解程序。

二．功能说明

整个试验将实现迷宫路径的查找，并图形化输出其中最短的路径。本试验脚步的存放运用双向链表实现，迷宫运用二维数组存放。机器通过穷举法解出迷宫的最短路径，储存在双向链表中，最末输出。整个试验分为以下几个模块：

1.创建模块。本试验的创建包含两方面，迷宫的定义和脚步的初始化。迷宫的定义通过修改二维数组实现，最终创建一个确定的迷宫。脚步的初始化由程序自行完成，最终建立一个双向链表的附加头结点。

2.路径查找模块。路径查找核心分为两个部分：路径查找、更优解替换。路径查找包括可通性检查、脚步前进、脚步后退三个模块。可通性检查会检查当前脚步的四个方向是否有通路。脚步前进可以在有通路的状况下抵达下一个点，并记录在脚步双向链表中。脚步后退使在当前脚步无路的状况下后退一步，并转向其他方向，同时删除链表中最末一个脚步。当求出的路径比上一次求出的路径更短时，更优解替换将更优解替换进路径存储链表。3.输出模块。实现迷宫解的图形化显示和路径的坐标输出。

4.其他模块。格式化模块，用于迷宫求解后的处理。迷宫数组改写模块，根据求解的结果改写迷宫二维数组，以满意最终输出需要。

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

图1功能模块图

三．具体设计

3.1．功能模块设计

3.1.1．主函数main()执行流程图

程序启动时，执行main()函数输出菜单。用户依据菜单的提示输入要执行的功能，程序会依据用户的选择执行不同的功能。程序具体功能如下：

1.自动演示：指令1,由程序自动生成一个迷宫，并进行路径求解的演示。

2.手动迷宫：指令2，由用户自行创建一个迷宫，定义迷宫的大小、外形等，程序将对用户指定的迷宫进行求解。

3.程序援助：指令3，显示程序援助和须要信息。4.退出：指令4，退出程序。执行流程如下列图：

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

图2主函数main()执行流程图

3.1.2．创建模块

本模块将进行待解迷宫的创建。

1.在自动演示中，机器会调用autocreat()函数自动创建一个10*10的迷宫。2.在手动迷宫中，程序会运用creat()函数，用户可以通过指定迷宫大小m*n，输入迷宫每一行的数据来自行创建迷宫。

3.1.3．路径查找模块

1.路径查找。

本模块实现了路径的查找和脚步的移动。思路是依次判断上右下左四个方向，假设

可以通过那么前进，不可通过那么转向下一个方向，四个方向都不可通过那么后退。

1可通性检查。可通性检查用来判断指定的方向是否可以通过。需要判断两方面内容，即下一点是否有障碍〔通过chk()函数完成〕和下一点是否已包含在了已有路径之中。假设同时满意无障碍和无包含条件，那么可以通过。否那么不能通过。2脚步前进。下一点假设经过检查可以通过，那么通过move()函数完成前进。“前进”的实现有两方面，第一方面，将新脚步纳入双向链表中，另一方面，在迷宫数组中将本步坐标所指标记为“已走”。

3脚步后退。假设本步四个方向都不能行走，那么通过back()函数退后。退后包括两方面，一方面把链表中最末一个节点抛弃，当前脚步指向倒数第二个节点。另一

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

方面，将迷宫数组中已抛弃节点指向的元素重新标记为“未走”，以便进行其他路径的寻路操作时可以顺当通过。2.更优解替换。

本模块完成了更优解的替换。当程序查找到比已存解更短的解时，将会销毁已存解，并将新解作为优解。直到最末全部的路径都搜寻完毕，优解所存的路径即为最短路径。

3.1.3．输出模块

输出模块调用outlin()函数，依据不同的参数值，输出不同的内容。主要功能是输出迷宫的图形化路径，并输出此路径的坐标顺次表示。

3.1.4．其他模块

1.格式化模块。调用formatmaze()函数，初始化存储迷宫的二维数组、各变量值，销

毁上次求解时产生的双向链表，释放内存空间。

2.迷宫数组改写模块，调用revise()函数，根据最终生成的最短双向链表记录的结果改写迷宫二维数组，以满意最终输出需要。

3.2．数据结构设计

存储脚步的双向链表定义如下：typedefstructlnode{

structlnode*ne*t;structlnode*pre;int*;inty;

intstepsum;//表示当前脚步为第几步。intdi;//用di代表已尝试的脚步方向。

}node,*linklist;

3.3．函数功能描述

1.autocreat()

autocreat()用以自动生成一个10*10的迷宫。2.creat()

通过用户输入的数据，创建一个指定大小为m*n，具有特定外形的迷宫。

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

3.seek()

seek()程序为迷宫查找的核心函数，通过调用chk()、move()、back()以及自身的优解替换功能，最终求解出一个迷宫的最短路径，存储在双向链表之中。此外，seek()函数还具有判断处理非常迷宫的功能。seek()函数不同返回值的含义，返回-1无解，1正常解出，2入口和出口重合。4.chk(intdirection)

chk()函数用来判断指定方向的可通性，并返回。返回1表示可通，返回0表示不可通。5.move(intdirection)

move()函数可以实现脚步向指定方向移动。即把新的脚步纳入脚步双向链表中，并将maze数组中相应的元素记录为-1表示已走。6.back()

当脚步的四个方向均已不能通过时，调用back()函数删除双向链表的最末一个脚步，并将maze数组中相应元素标记为1，实现脚步的回退。7.revise()

运用指针p,依据已求的的脚步，改写maze数组，使之满意输出需要。设有指针p,那么依据p-pre，p，p-ne*t三点所记录的坐标，可以求出p的脚步外形，并标记在maze[p-*][p-y]中。8.outlin()

输出迷宫求解的结果。9.help()

help()函数用以输出程序须要的援助信息。10.formatmaze()

初始化存储迷宫的二维数组、各变量值，销毁上次求解时产生的双向链表，释放内存空间。

四．程序实现

4.1.源码分析

#includestdio.h#includestdlib.h#includemath.h#definema*size36#definestatusint

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

typedefstructlnode{

structlnode*ne*t;structlnode*pre;int*;inty;

intstepsum;//表示当前脚步为第几步。

intdi;//用di代表已尝试的脚步方向。01234分别代表未尝试、↑、→、↓、←。

}node,*linklist;

//全局变量开始

linklistL,L2,p,q,g;//三个指针pqg满意不同函数临时指针需要node*nowstep,*laststep;

intmaze[ma*size+2][ma*size+2];//存储迷宫的数组，+2是为了加围墙。intm,n;//迷宫行、列数变量

inte*it*,e*ity,entrance*,entrancey;//出入口。。*y分别代表行列.

intfinish=0;//走迷宫的最终全局结果。1有路，-1无路，2出入口重合。

inte*istL=0;//手动创建迷宫,选择r重新创建迷宫，formatmaze()将格式化各变量。检测L链表是否存在防止程序崩溃。

intmindistance=0;//存放求出的最短路径的步数。

//创建迷宫statuscreat(){

system(cls);inti,j;charcord='a';

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

do{

if(cord=='r')

formatmaze();

printf(\n请输入迷宫行、列数(最大%d*%d)。\n行:,ma*size,ma*size);scanf(%d,m);printf(列:);scanf(%d,n);

while(mma*size||nma*size||m1||n1){

printf(输入有误。只支持%d*%d以内的迷宫，请重新输入行列数。\n

行:,ma*size,ma*size);

}

printf(\n输入迷宫数据，0为砖头，1为通路，数字间用空格间隔。系统将自动添

scanf(%d,m);printf(列:);scanf(%d,n);

加围墙。\n);

printf(\n\n设定出入口数学坐标(*,y)。\n已建立%d行%d列的迷宫，坐标应在(1,1)

for(i=1;i=m;i++){}

printf(\n已胜利建立迷宫，图形如下:\n);outlin();

printf(第%d行的%d个数据(共%d行):,i,n,m);for(j=1;j=n;j++)

scanf(%d,maze[i][j]);

至(%d,%d)之间。\n,m,n,n,m);

printf(设定入口坐标，格式例如1,1:);

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

while(entrance*m||entranceyn||maze[entrance*][entrancey]==0){

printf(输入有误，请检查。坐标应在(1,1)至(%d,%d)之间。\n请重新输入入口

坐标，格式例如1,1:,n,m);

printf(输入出口坐标，格式例如%d,%d:,n,m);scanf(%d,%d,e*ity,e*it*);

while(e*it*m||e*ityn||maze[e*it*][e*ity]==0){

printf(输入有误，请检查。坐标应在(1,1)至(%d,%d)之间。\n请重新输入出口

}

scanf(%d,%d,entrancey,entrance*);

坐标，格式例如%d,%d:,m,n,n,m);

}

system(cls);

printf(\n你设定的迷宫如下：\n);maze[entrance*][entrancey]=-1;maze[e*it*][e*ity]=-2;outlin();

maze[entrance*][entrancey]=1;maze[e*it*][e*ity]=1;

printf(入口和出口分别为(%d,%d)(%d,%d)。\n键入y将开始求解,键入r重新设定:

scanf(%d,%d,e*ity,e*it*);

,entrancey,entrance*,e*ity,e*it*);

scanf(%c%c,cord,cord);while(cord!='y'cord!='r'){}

printf(输入有误，请重新输入:);scanf(%c%c,cord,cord);

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

}

}while(cord!='y');

//格式化迷宫。再创建新迷宫时用。。。formatmaze(){

if(e*istL==2){

while(L2-ne*t){}free(L2);

L2=L2-ne*t;free(L2-pre);

inti,j;

for(i=0;im+2;i++)

for(j=0;jn+2;j++)

maze[i][j]=0;

finish=0;

//以下语句把上次求解迷宫时建立的链表空间释放。if(e*istL!=0){

while(L-ne*t){}free(L);

L=L-ne*t;free(L-pre);

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

}

}

e*istL=0;finish=0;mindistance=0;

//迷宫求解。。

statusseek(){

intallfinished=0;

if(entrance*==e*it*entrancey==e*ity)//入口和出口重合的非常状况。

L=(linklist)malloc(sizeof(node));//建立存储脚步的链表.L-ne*t=NULL;L-pre=NULL;L-stepsum=0;e*istL=1;

//初始化nowstep，令其在入口处。nowstep=(node*)malloc(sizeof(node));nowstep-*=entrance*;nowstep-y=entrancey;nowstep-pre=L;nowstep-ne*t=NULL;nowstep-di=0;nowstep-stepsum=1;

return2;

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

//开始查找第一条可通路径。

while(nowstep-*!=e*it*||nowstep-y!=e*ity)//用1234代表↑→↓←四个方向。{

if(nowstep-di==0chk(1)==1)//可通需要满意两个条件，下一个点无障碍、下一

个点未涌现在已构建的路径中。

move(1);

elseif(nowstep-di==1chk(2)==1)

move(2);

elseif(nowstep-di==2chk(3)==1)

move(3);

elseif(nowstep-di==3chk(4)==1)

move(4);

elseif(nowstep-*==entrance*nowstep-y==entrancey)//假如脚步停留在了入口，

说明迷宫无解，不再查找。

//OK,查找出了第一条路径L，说明迷宫有解。建立L2比较路径，尝试查找比L更短

return-1;

else}

mindistance=laststep-stepsum;

back();//本步无路了，回退。

的路径。

if(laststep-stepsum==abs(entrance*-e*it*)+abs(entrancey-e*ity))//假设第一条路径与理论

最小路径相等，那么不需要再次比较，径直返回。

{

L2=L;revise();return1;

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

e*istL=2;

while(allfinished==0){

L2=(linklist)malloc(sizeof(node));L2-ne*t=NULL;L2-pre=NULL;L2-stepsum=0;

//将最末一个最小路径备份到L2，继续求解。p=L2;g=L-ne*t;

while(g){}

q-ne*t=NULL;

q=(node*)malloc(sizeof(node));q-di=g-di;

q-stepsum=g-stepsum;q-*=g-*;q-y=g-y;q-pre=p;p-ne*t=q;g=g-ne*t;p=q;

//开始查找第二条可通路径。

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

while(nowstep-*!=e*it*||nowstep-y!=e*ity){

if(nowstep-di==0chk(1)==1)

move(1);

elseif(nowstep-di==1chk(2)==1)

move(2);

elseif(nowstep-di==2chk(3)==1)

move(3);

elseif(nowstep-di==3chk(4)==1)

move(4);

else{

if(nowstep-stepsum==1nowstep-di==4)//第一步的四个方向也都尝试

过了，说明迷宫全部可能路径都已尝试完毕。

}

{}back();

allfinished=1;break;

if(nowstep-stepsum=mindistance)//新路径大于旧路径，就不要再往下尝试浪

费时间了。换其他路径。

if(allfinished==0)//每次找到更短路径，都要存入L2，并销毁原L2释放空间。{

mindistance=laststep-stepsum;

}

back();

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

};

}

{}free(L2);

L2=L2-ne*t;free(L2-pre);

revise();//改写maze数组里存储的内容，把每一步的方向信息写进去，以便输出图形路

径。}

return1;

statuschk(intdirection)//判断下一个方向是否有障碍的函数。{

nowstep-di++;if(direction==1){}

elseif(direction==2){}

if(maze[nowstep-*][(nowstep-y)+1]==1)

return1;

if(maze[(nowstep-*)-1][nowstep-y]==1)

return1;

else

return0;

else

return0;

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

}

{}

elseif(direction==4){}

if(maze[nowstep-*][(nowstep-y)-1]==1)

return1;

if(maze[(nowstep-*)+1][nowstep-y]==1)

return1;

else

return0;

else

return0;

statusmove(intdirection)//假如chk函数判断下一点可通，那么运用此函数实现走动。{

switch(direction){

laststep=nowstep;//将laststep指向nowstep，再建立新的nowstep，实现nowstep的前进。nowstep=(node*)malloc(sizeof(node));nowstep-di=0;nowstep-ne*t=NULL;nowstep-pre=laststep;

nowstep-stepsum=laststep-stepsum+1;nowstep-*=laststep-*;nowstep-y=laststep-y;laststep-ne*t=nowstep;

maze[laststep-*][laststep-y]=-1;//用-1将maze数组中的值标记，表示已经走过

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

case1:nowstep-*--;break;case2:nowstep-y++;break;case3:nowstep-*++;break;case4:nowstep-y--;}

}

statusback(){nowstep=laststep;free(nowstep-ne*t);

maze[nowstep-*][nowstep-y]=1;//将maze数组中标记的-1改为1，以便其他路径尝试

时可以通过。laststep=laststep-pre;nowstep-ne*t=NULL;

}

revise()//│─┌┐└┘六个符号在maze数组里分别由234567表示.{intd*,dy;p=L2-ne*t-ne*t;while(p-ne*tp-pre){d*=(p-ne*t-*)-(p-pre-*);

dy=(p-ne*t-y)-(p-pre-y);if(dy==0)

maze[p-*][p-y]=2;

elseif(d*==0)

maze[p-*][p-y]=3;

elseif(d*==1dy==1)

{

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

}

}

}

maze[p-*][p-y]=5;

else

maze[p-*][p-y]=6;

elseif(d*==-1dy==1){}

elseif(d*==1dy==-1){}

elseif(d*==-1dy==-1){}p=p-ne*t;

if(p-*==p-pre-*)

maze[p-*][p-y]=6;if(p-*==p-pre-*)

maze[p-*][p-y]=4;if(p-*==p-pre-*)

maze[p-*][p-y]=7;

else

maze[p-*][p-y]=4;

else

maze[p-*][p-y]=7;

else

maze[p-*][p-y]=5;

maze[e*it*][e*ity]=-2;maze[entrance*][entrancey]=-1;

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

//输出迷宫的函数statusoutlin(){

printf();//开始输出图形。for(j=0;jn+2;j++)

printf(%2d,j);inti,j;

if(finish==-1){}

elseif(finish==2){}

elseif(finish==1)

printf(\n\n已胜利查找出最短路径，输出如下：\n);printf(\n\n。。入口和出口重合了!\n);return1;

printf(\n\n没找到路!你的迷宫有问题...\n);return1;

printf(\n);for(i=0;im+2;i++){

printf(%2d,i);for(j=0;jn+2;j++){

switch(maze[i][j]){

case-1:printf(入);break;

C语言、双向链表实现的迷宫巡径程序,包括课程设计和全部源代码。模块化附说明,方便改为其他数据结构实现。

}

}

}

}

case-2:printf(出);break;case0:printf(■);break;case1:printf();break;case2:printf(│);break;case3:printf(─);break;case4:printf(┌);break;case5:printf(┐);break;case6:printf(└);break;case7:printf(┘);break;

printf(\n);

if(finish==1)