mg[j][r]=rand（）%2;
（2）
voidstep（stack*s,pos*cur,stack*reslut）//探索路径函数
{Initstack（s）;curpos=start;//设定“当前位置”为“入口位置”
curstep=1;//探索第一步
do{
if（Pass（curpos））
{FootPrint（curpos）;//留下足迹
e=（curstep,curpos,1）;
Push（S,e）;//加入路径
if（curpos==end）return（TRUE）;//到达终点（出口）
curpos=NextPos（curpos,1）;
curstep++;}//探索下一步
else{//当前位置不能通过
if（!
StackEmpty（s））{
pop（S,e）;
while（e.di==4&&!
StackEmpty（S））{
MarkPrint（e.seat）;pop（S,e）;//留下不能通过的标记，并退回一步
}//while
if（e.di<4）{
e.di++;Push（S,e）;//换下一个方向探索
curpos=NextPos（e.seat,e.di）;//设定当前位置是该新方向上的相领块
}//if
}//if
}//else
}while（!
StackEmpty（S））;
return（FALSE）;}//MazePath
（3）
voidsavepath（stack*s,pos*cur,stack*result）//保存路径函数
{pos*top=s->t;
if（stackempty（result））//若栈result为空
{push（result,cur）;//可通路径坐标存入result栈
While（top>s->b）
Push（result,--top）;}
elseif（sizeof（result）>sizeof（s））//若result栈中元素多于s栈中元素
clearstack（result）;
push（result,cur）;//可通路径坐标存入result栈
while（top>s->b）
push（result,--top）;}//Savepath
（4）
voidprint（stack*s,pos*s,stack*result）//输出
{if（StackEmpty（result））
printf（“Nowayavailable!
”）;//输出没有找到
else
while（!
StackEmpty（result））//当栈非空
{pop（result,cur）;
draw（y,x）;//在屏幕上绘出路径
printf（“（%d,%d）”,x,y）;}}//输出路径坐标
3、函数关系调用图
4、调试分析
A、调试中遇到的问题既对问题的解决方案
（1）在输入迷宫的大小n时，若n太大，例如n=30，屏幕无法显示第25行以及其后的方块。
解决方法：
EXEC:
printf（“Pleaseinputthesizeofmaze（n*n）:
”）;
scanf（“%d”,&n）;
添加语句：
if（n>24）
{printf（“\nThenumberissolarge!
Tryitagain!
\n”）;
gotoEXEC;}
（2）在输入迷宫的起点与终点坐标时，若输入坐标超过迷宫的表示范围则程序立即结束并不返回任何值，若输入的坐标在迷宫的“围墙”上时，搜索依然进行，并返回路径。
解决方法：
up:
printf（“Pleaseinputthestartpath（c,d）:
”）;
scanf（“%d%d”,&d,&c）;
printf（“Pleaseinputtheendpath（a,b）:
”）;
scanf（“%d%d”,&b,&a）;
添加语句：
if（c>n-2||d>n-2||a>n-2||b>n-2||c==0||d==0||a==0||b==0）
{printf（“Thenumberextendtheboundar
array!
Tryitagain!
\n”）;
gotoup;}
B、算法的时间复杂度和空间复杂度：
整个程序转为.EXE可执行后整体的：
空间复杂度为18.3KB
时间复杂度O（n4）
测试结果
a．输入迷宫大小（n*n）：
b．输入起点（c，d）与终点（a，b）坐标：
运行结果：
6.源程序（带注释）
#include
#include
#include
#include
typedefstruct{/*定义结构体其中坐标（x,y）搜索方向dir*/
intx,y;
intdir;
}pos,elem;
typedefstruct{/*定义栈顶指针t栈底指针b栈的大小size*/
elem*b,*t;
intsize;
}stack;
voidinitstack（stack*s）/*定义栈的存储空间*/
{s->b=（elem*）malloc（150*sizeof（elem））;
if（s->b）{
s->t=s->b;
s->size=150;
return;}
exit（0）;}
voidpush（stack*s,elem*e）/*数据入栈*/
{*s->t=*e;s->t++;}
voidpop（stack*s,elem*e）/*弹出栈中元素*/
{*e=*--s->t;}
voidclearstack（stack*s）/*清空栈中所有元素*/
{s->t=s->b;}
intstackempty（stack*s）/*判断栈是否为空*/
{return!
（s->t-s->b）;}
intdestroystack（stack*s）/*销毁栈*/
{free（s->b）;/*由系统回收栈底指针*/
free（s）;/*系统回收栈s的存储空间*/
return1;}
intd,c,n,a,b,i,r,j,mg[100][100],x1,y1,dongx[100],dongy[100];doublez;
voidstep（stack*s,pos*cur,stack*result）;
voidsavepath（stack*s,pos*cur,stack*result）;
voiddraw（inty,intx）;/*画图函数*/
voidstep（stack*s,pos*cur,stack*result）/*搜索可通路径函数*/
{if（stackempty（result）||s->t-s->bt-result->b）{
for（cur->dir++;cur->dir<5;cur->dir++）{/*探索"上下左右"四个方向是否可通*/
switch（cur->dir）{case1:
/*向上*/
if（!
mg[cur->y-1][cur->x]）{
mg[cur->y][cur->x]=1;
push（s,cur）;
cur->y--;
cur->dir=0;
return;}
break;
case2:
/*向右*/
if（!
mg[cur->y][cur->x+1]）{
mg[cur->y][cur->x]=1;
push（s,cur）;
cur->x++;
cur->dir=0;
return;}
break;/*向下*/
case3:
if（!
mg[cur->y+1][cur->x]）{
mg[cur->y][cur->x]=1;
push（s,cur）;
cur->y++;
cur->dir=0;
return;}
break;
case4:
/*向左*/
if（!
mg[cur->y][cur->x-1]）{
mg[cur->y][cur->x]=1;
push（s,cur）;
cur->x--;
cur->dir=0;
return;}
break;
default:
exit（0）;}
}
}
setfillstyle（SOLID_FILL,2）;/*可走路径设置为绿色*/
draw（cur->y,cur->x）;/*画出可走路径*/
pop（s,cur）;
mg[cur->y][cur->x]=0;}/*从栈s中弹出探索路径坐标*/
voidsavepath（stack*s,pos*cur,stack*result）/*保存最短路径函数*/
{pos*top=s->t;
if（stackempty（result））{/*若栈result为空*/
push（result,cur）;/*可通路径坐标存入result栈中*/
while（top>s->b）
push（result,--top）;}
/*若result栈中元素多于s栈中元素则清空reslut栈并把可通路径坐标
存入result栈中*/
elseif（result->t-result->b>s->t-s->b）{
clearstack（result）;
push（result,cur）;
while（top>s->b）
push（result,--top）;}}
voiddraw（inty,intx）
{bar（130+15*x,130+15*y,117+15*x,117+15*y）;/*绘制方块大小*/}
voidmain（void）/*主函数*/
{intx,y;
intgd=DETECT,gm;
charch;
stack*s=NULL;/*初始化栈s,result和路径坐标指针cur*/
stack*result=NULL;
pos*cur=NULL;
EXEC:
printf（"Pleaseinputthesizeofmaze（n*n）:
"）;/*输入迷宫大小*/
scanf（"%d",&n）;
if（n>24）/*屏幕所显示的最大迷宫*/
{printf（"\nThenumberissolarge!
Tryitagain!
\n"）;
gotoEXEC;}
for（i=0;i{mg[i][0]=1;
mg[i][n-1]=1;
mg[0][i]=1;
mg[n-1][i]=1;}
for（j=1;jfor（r=1;rmg[j][r]=rand（）%2;
initgraph（&gd,&gm,""）;/*在屏幕上绘画出迷宫*/
for（x=0;xfor（y=0;yif（mg[y][x]）{
setfillstyle（SOLID_FILL,9）;/*墙设置为蓝色*/
draw（y,x）;/*在屏幕上画出墙*/}}
result=（stack*）malloc（sizeof（stack））;/*由系统生成result,s栈*/
initstack（result）;
s=（stack*）malloc（sizeof（stack））;
cur=（pos*）malloc（sizeof（pos））;
up:
printf（"Pleaseinputthestartpath（c,d）:
"）;/*输入起点*/
scanf（"%d%d",&d,&c）;
printf（"Pleaseinputtheendpath（a,b）:
"）;/*输入终点*/
scanf（"%d%d",&b,&a）;
if（c>n-2||d>n-2||a>n-2||b>n-2||c==0||d==0||a==0||b==0）/*判断是否为合法输入*/
{printf（"Thenumberextendtheboundaryofthearray!
tryitagain!
\n"）;
gotoup;}
initstack（s）;
cur->x=c;/*搜索起始坐标为（m,n）*/
cur->y=d;
cur->dir=0;
push（s,cur）;/*把入口坐标压入栈s中*/
n=i=0;
do{if（cur->x==a&&cur->y==b）/*若找到出口则把s栈中元素存入result栈中*/
savepath（s,cur,result）;
step（s,cur,result）;
}while（!
stackempty（s））;/*当s栈非空时*/
if（stackempty（result））/*若result栈为空*/
{printf（"nowayavailable!
"）;}/*没有找到路径*/
else{intch=0;
printf（"followingistheshortestpath:
\n"）;/*以下是最短路径*/
while（!
stackempty（result））{/*若栈非空*/
pop（result,cur）;/*从result栈中弹出数据*/
setfillstyle（SOLID_FILL,15）;/*路径为白色*/
draw（cur->y,cur->x）;/*在屏幕上画出路径*/
if（ch>8）{putchar（'\n'）;ch=0;}/*一行打印八个坐标*/
printf（"（%d,%d）,",cur->x,cur->y）;/*在屏幕上输出路径坐标*/
ch++;n++;i++;
dongx[i]=cur->x;dongy[i]=cur->y;/*把路径坐标存入数组dongx[]和dongy[]中*/
}
/*产生动画*/
for（i=1;i<=n;i++）
{x1=138+15*（dongx[i]-1）;
y1=138+15*（dongy[i]-1）;
setcolor（4）;/*4表示红色*/
line（x1-5,y1,x1+5,y1）;/*绘制红色十字*/
line（x1,y1-5,x1,y1+5）;
for（z=0;z<9e+6;z++）;/*时间延迟*/
/*擦除所走过的路径*/
setcolor（15）;/*15表示白色*/
line（x1-5,y1,x1+5,y1）;
line（x1,y1-5,x1,y1+5）;}
}
for（i=0;i<23;i++）
printf（"\n"）;
printf（"\nDoyouwantacontinue（Y/N）?
\n"）;/*是否继续生成迷宫*/
destroystack（s）;/*销毁栈s*/
destroystack（result）;/*销毁栈result*/
free（cur）;
ch=getch（）;
if（ch=='y'||ch=='Y'）
gotoEXEC;}/*返回程序起始址*/
参考文献
1严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.
2严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.
3《DATASTRUCTUREWITHC++》.WilliamFord，WilliamTcpp.清华大学出版社（影印版）.
4谭浩强.《C语言程序设计》.清华大学出版社.
总结
在这三周的数据结构课程设计中,我的题目是:
迷宫问题,这三周课程设计中,通过该题目的设计过程,我加深了对栈的逻辑结构,存储结构及入栈出栈过程的理解,对栈的基本运算的实现有所掌握,对课本中所学的各种数据结构进一步理解和掌握,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。
一个人要完成所有的工作是非常困难和耗时的。
在以后的学习中我会更加注意各个方面的能力的协调发展。
在课程设计时遇到了很多的问题，在老师的帮助，和对各种资料的查阅中，将问题解决，培养了我自主动手，独立研究的能力，为今后在学习工作中能更好的发展打下了坚实的基础。
三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织，来配合学习，三周中我收益很大，学到很多。
致谢
首先感谢我的指导老师李睿老师，他在我的课程设计过程中提出了指导性的方案和架构，并指引我阅读相关的资料和书籍，使我在不熟悉的领域中仍能迅速掌握新的技术。
感谢我的数据结构老师李睿老师和C语言老师任旭鹏在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。
我的同学在设计完成后对程序的测试，没有他们，也许就难以发现一些潜在的错误，在此一并表示感谢。
附件Ⅰ部分源程序代码
//直接插入排序算法
#include
#include
#defineNULL0
#defineLENsizeof（structstudent）
structstudent/*定义节点*/
{
intnum;
intscore;
structstudent*next;
};
/*建立链表*/
structstudent*creat（void）
{
structstudent*head,*p1,*p2;
intn=0;
p1=p2=（structstudent*）malloc（LEN）;
scanf（"%d,%d",&p1->num,&p1->score）;
while（p1->num!
=0）
{
n=n+1;
if（n==1）head->next=p1;
elsep2->next=p1;
p2=p1;
p1=（structstudent*）malloc（LEN）;
scanf（"%d,%d",&p1->num,&p1->score）;
}
p2->next=NULL;
returnhead;
}
/*打印单链表信息*/
print（structstudent*head）
{
structstudent*p=creat（）;
if（p!
=NULL）
{
for（;p!
=NULL;p=p->next）{
printf（"%d,%d\n",p->num,p->score）;
}
}
}
/*插入排序*/
structstudent*insert_sort（structstudent*head）
{
structstudent*h1,*p,*q,*t;
head=creat（）;
h1=head->next;
while（h1!
=NULL）/*循环直至等待插入的链表为空*/
{
t=h1;/*保存等待插入链表的头指针*/
h1=h1->next;//h1后移
p=head;
q=head;
while（p!
=NULL&&t->num>p->num）/*进行节点大小比较*/
{
q=p;
p=p->next;
}
if（p==q）/*说明待排序点值最大,应排在首位*/
{
head=t;
t->next=p;
}
else{
t->next=p;
q->next=t;
}
}
returnhead;
}
/*主函数*/
main（）
{
structstudent*head,*p;
printf（"PleaseInputInfo（endwith0,0）:
\n"）;
head=insert_sort（&head）;
printf（"Sort:
\n"）;
for（p=head;p!
=NULL;p=p->next）
printf（"%d:
%d\n",p->num,p->score）;
getch（）;
}
运行结果：
源程序（带注释）
#include
#include
#include
#include
typedefstruct{/*定义结构体其中坐标（x,y）搜索方向dir*/
intx,y;
intdir;
}pos,elem;
typedefstruct{/*定义栈顶指针t栈底指针b栈的大小size*/
elem*b,*t;
intsize;
}stack;
voidinitstack（stack*s）/*定义栈的存储空间*/
{s->b=（elem*）malloc（150*sizeof（elem））;
if（s->b）{
s->t=
升级会员 