c語言迷宮問題課程設計
『壹』 c語言做的迷宮問題
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>struct node
{
int sign;//標識,0什麼都不在,1在open中,2在closed中
int flag;//標志位 0/1,0可以走,1不可以走
int f,g,h;//判斷函數
int x,y;//坐標
int old;//是否old節點,0非,1是
};struct link
{
node fnode;
link *next;
link *pri;
};link *open,*closed,*bestnode,*successor,*p,*q,*r,*s;int maze_flag[7][7]={ {0,1,0,0,0,0,0},
{0,1,0,1,0,1,0},
{0,1,0,0,0,1,0},
{0,1,0,1,0,1,0},
{0,0,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,1,0}};//表示迷宮的數組,0可以走,1不可以走node maze[7][7];int judge(node n)//判斷函數,判斷n節點是否可以走
{
if(n.flag==1)
return(1);
else
return(0);
}void in_open(node n)//將n節點放入open表
{
p=open;
while(p->next!=open)
{
if(n.f>=p->fnode.f)
{
p->next->pri=(link *)malloc(sizeof(link));
p->next->pri->pri=p;
p=p->next;
p->pri->next=p;
p->pri->pri->next=p->pri;
p=p->pri;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}
else
p=p->next;
}
open->pri=(link *)malloc(sizeof(link));
open->pri->pri=p;
open->pri->next=open;
p->next=open->pri;
p=p->next;
p->fnode.flag=n.flag;
p->fnode.f=n.f;
p->fnode.g=n.g;
p->fnode.h=n.h;
p->fnode.x=n.x;
p->fnode.y=n.y;
p->fnode.old=n.old;
p->fnode.sign=n.sign=1;
}void out_open(node n)//將n節點從open表中移出
{
p=open;
while(p->next!=open)
{
if(n.f=p->fnode.f)
{
link *p1;
p1=p->next;
p->next=p->next->next;
p->next->pri=p;
free(p1);
n.sign=0;
}
else
p=p->next;
}
}void in_closed(node n)//將n節點放入closed表
{
while(q->next!=closed)
{
if(n.f>=q->fnode.f)
{
q->next->pri=(link *)malloc(sizeof(link));
q->next->pri->pri=q;
q=q->next;
q->pri->next=p;
q->pri->pri->next=q->pri;
q=q->pri;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}
else
q=q->next;
}
closed->pri=(link *)malloc(sizeof(link));
closed->pri->pri=q;
closed->pri->next=closed;
q->next=closed->pri;
q=q->next;
q->fnode.flag=n.flag;
q->fnode.f=n.f;
q->fnode.g=n.g;
q->fnode.h=n.h;
q->fnode.x=n.x;
q->fnode.y=n.y;
q->fnode.old=n.old;
q->fnode.sign=n.sign=2;
}void out_closed(node n)//將n節點從closed表中移出
{
q=closed;
while(q->next!=closed)
{
if(n.f=q->fnode.f)
{
link *q1;
q1=q->next;
q->next=q->next->next;
q->next->pri=q;
free(q1);
n.sign=0;
}
else
q=q->next;
}
}void in_bestnode(node n)//將n節點設為bestnode節點
{
while(r->next!=bestnode)
{
if(n.f>=r->fnode.f)
{
r->next->pri=(link *)malloc(sizeof(link));
r->next->pri->pri=r;
r=r->next;
r->pri->next=r;
r->pri->pri->next=r->pri;
r=r->pri;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}
else
r=r->next;
}
bestnode->pri=(link *)malloc(sizeof(link));
bestnode->pri->pri=r;
bestnode->pri->next=bestnode;
r->next=bestnode->pri;
r=r->next;
r->fnode.flag=n.flag;
r->fnode.f=n.f;
r->fnode.g=n.g;
r->fnode.h=n.h;
r->fnode.x=n.x;
r->fnode.y=n.y;
r->fnode.old=n.old;
}void out_bestnode(node n)//將n節點的bestnode去掉
{
r=bestnode;
while(r->next!=bestnode)
{
if(n.f=p->fnode.f)
{
link *r1;
r1=r->next;
r->next=r->next->next;
r->next->pri=r;
free(r1);
}
else
r=r->next;
}
}void in_successor(node n)//將n節點設置為successor節點
{
s=successor;
while(s->next!=successor)
{
if(n.f>=s->fnode.f)
{
s->next->pri=(link *)malloc(sizeof(link));
s->next->pri->pri=s;
s=p->next;
s->pri->next=s;
s->pri->pri->next=s->pri;
s=s->pri;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}
else
s=s->next;
}
successor->pri=(link *)malloc(sizeof(link));
successor->pri->pri=s;
successor->pri->next=successor;
s->next=successor->pri;
s=s->next;
s->fnode.flag=n.flag;
s->fnode.f=n.f;
s->fnode.g=n.g;
s->fnode.h=n.h;
s->fnode.x=n.x;
s->fnode.y=n.y;
s->fnode.old=n.old;
}void out_successor(node n)//將n節點的successor去掉
{
s=successor;
while(s->next!=successor)
{
if(n.f=p->fnode.f)
{
link *s1;
s1=s->next;
s->next=s->next->next;
s->next->pri=s;
free(s1);
}
else
s=s->next;
}
}void print(link *n)//輸出link類型的表n
{
link *forprint;
forprint=n;
printf("the key is ");
while(forprint->next!=n)
printf("(%d,%d)\n",forprint->fnode.x,forprint->fnode.y);
}int main()
{
//初始化部分
//這部分的功能是將二維的整形數組賦值給node型的二維數組
int i=0,j=0;
for(i=0;i<7;i++)
for(j=0;j<7;j++)
{
maze[i][j].x=i;
maze[i][j].y=j;
maze[i][j].flag=maze_flag[i][j];
if(maze[i][j].flag==0)
{
maze[i][j].h=6-i+6-j;
maze[i][j].sign=maze[i][j].f=maze[i][j].g=maze[i][j].old=0;
}
else
maze[i][j].h=-1;
}
for(i=0;i<7;i++)//輸出迷宮示意圖
{
for(j=0;j<7;j++)
{
printf("%2d",maze_flag[i][j]);
}
printf("\n");
}
//這部分的功能是將open,closed,bestnode表初始化,都置為空表
p=open=(link *)malloc(sizeof(link));
open->next=open;
open->pri=open;
q=closed=(link *)malloc(sizeof(link));
closed->next=closed;
closed->pri=closed;
r=bestnode=(link *)malloc(sizeof(link));
bestnode->next=bestnode;
bestnode->pri=bestnode;
//將第一個元素即(0,0)節點放入open表,開始演算法
in_open(maze[0][0]);
maze[0][0].f=maze[0][0].h;
link *s2;
s2=successor;
if(open->next!=open)//open表為空時則失敗退出
{
while(1)
{
in_bestnode(open->fnode);//將open表的第一個元素放入bestnode中
in_closed(maze[open->fnode.x][open->fnode.y]);//將open表的第一個元素放入closed中
maze[open->fnode.x][open->fnode.y].g++;//將open表的第一個元素的g值加一,表示已經走了一步
out_open(maze[open->fnode.x][open->fnode.y]);//將open表的第一個元素刪除 if(bestnode->fnode.x==6&&bestnode->fnode.y==6)//若bestnode是目標節點,則成功退出
{
printf("succes!!\nthen print the key:\n");
print(closed);
break;
}
else//若bestnode不是目標節點,則擴展其臨近可以走的節點為successor
{
if(i==0||j==0||i==6||j==6)
{
if(i==0&&j==0)//若為(0,0),則判斷右邊和下邊的元素
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==0&&j==6)//若為(0,6),則判斷左邊和下邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6&&j==0)//若為(6,0),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==6&&j==6)//若為(6,6),則判斷左邊和上邊的元素
{
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
else if(i==0)//若為第一行的元素(不在角上),則判斷左邊,下邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
else if(i==6)//若為第七行的元素(不在角上),則判斷左邊,上邊和右邊
{
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
}
else if(j==0)//若為第一列的元素(不在角上),則判斷右邊,下邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
}
else if(j==6)//若為第七列的元素(不在角上),則判斷左邊,上邊和上邊
{
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
}
}
else//若為中將的元素,則判斷四個方向的節點
{
if(judge(maze[i][j-1])==0)
in_successor(maze[i][j-1]);
if(judge(maze[i][j+1])==0)
in_successor(maze[i][j+1]);
if(judge(maze[i-1][j])==0)
in_successor(maze[i-1][j]);
if(judge(maze[i+1][j])==0)
in_successor(maze[i+1][j]);
}
}
while(s2->next!=successor)//對所有的successor節點進行下列操作
{
maze[s2->fnode.x][s2->fnode.y].g=bestnode->fnode.g+bestnode->fnode.h;//計算g(suc)=g(bes)+h(bes,suc)
if(s2->fnode.sign==1)//若在open表中,則置為old,記下較小的g,並從open表中移出,放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_open(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else if(s2->fnode.sign==2)//若在closed表中,則置為old,記下較小的g,並將old從closed表中移出,將較小的g的節點放入closed表中
{
s2->fnode.old=1;
if(s2->fnode.g<maze[s2->fnode.x][s2->fnode.y].g)
{
maze[s2->fnode.x][s2->fnode.y].g=s2->fnode.g;
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
out_closed(maze[s2->fnode.x][s2->fnode.y]);
in_closed(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].old=0;
}
else
continue;
}
else//若即不再open表中也不在closed表中,則將此節點放入open表中,並計算此節點的f值
{
in_open(maze[s2->fnode.x][s2->fnode.y]);
maze[s2->fnode.x][s2->fnode.y].f=maze[s2->fnode.x][s2->fnode.y].g+maze[s2->fnode.x][s2->fnode.y].h;
}
s2=s2->next;
}
s2=successor;
}
}
else
printf("error!!This maze does not have the answer!");
return(0);
}
『貳』 c語言的課程設計：迷宮問題。
參考一下這個
/*4.3.3源程序*/
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
#define N 20/*迷宮的大小，可改變*/
int oldmap[N][N];/*遞歸用的數組,用全局變數節約時間*/
int yes=0;/*yes是判斷是否找到路的標志,1找到，0沒找到*/
int way[100][2],wayn=0;/*way數組是顯示路線用的,wayn是統計走了幾個格子*/
void Init(void);/*圖形初始化*/
void Close(void);/*圖形關閉*/
void DrawPeople(int *x,int *y,int n);/*畫人工探索物圖*/
void PeopleFind(int (*x)[N]);/*人工探索*/
void WayCopy(int (*x)[N],int (*y)[N]);/*為了8個方向的遞歸，把舊迷宮圖拷貝給新數組*/
int FindWay(int (*x)[N],int i,int j);/*自動探索函數*/
void MapRand(int (*x)[N]);/*隨機生成迷宮函數*/
void PrMap(int (*x)[N]);/*輸出迷宮圖函數*/
void Result(void);/*輸出結果處理*/
void Find(void);/*成功處理*/
void NotFind(void);/*失敗處理*/
void main(void)/*主函數*/
{
int map[N][N]; /*迷宮數組*/
char ch;
clrscr();
printf("\n Please select hand(1) else auto\n");/*選擇探索方式*/
scanf("%c",&ch);
Init(); /*初始化*/
MapRand(map);/*生成迷宮*/
PrMap(map);/*顯示迷宮圖*/
if(ch=='1')
PeopleFind(map);/*人工探索*/
else
FindWay(map,1,1);/*系統自動從下標1,1的地方開始探索*/
Result();/*輸出結果*/
Close();
}
void Init(void)/*圖形初始化*/
{
int gd=DETECT,gm;
initgraph(&gd,&gm,"c:\\tc");
}
void DrawPeople(int *x,int *y,int n)/*畫人工控制圖*/
{/*如果將以下兩句注釋掉，則顯示人工走過的路徑，*/
setfillstyle(SOLID_FILL,WHITE); /*設置白色實體填充樣式*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
/*恢復原通路*/
switch(n)/*判斷x,y的變化，8個方向的變化*/
{
case 1: (*x)--;break; /*上*/
case 2: (*x)--;(*y)++;break ;/*右上*/
case 3: (*y)++;break; /*右*/
case 4: (*x)++;(*y)++;break; /*右下*/
case 5: (*x)++;break; /*下*/
case 6: (*x)++;(*y)--;break; /*左下*/
case 7: (*y)--;break; /*左*/
case 8: (*x)--;(*y)--;break; /*左上*/
}
setfillstyle(SOLID_FILL,RED);/*新位置顯示探索物*/
bar(100+(*y)*15-6,50+(*x)*15-6,100+(*y)*15+6,50+(*x)*15+6);
}
void PeopleFind(int (*map)[N])/*人工手動查找*/
{
int x,y;
char c=0;/*接收按鍵的變數*/
x=y=1;/*人工查找的初始位置*/
setcolor(11);
line(500,200,550,200);
outtextxy(570,197,"d");
line(500,200,450,200);
outtextxy(430,197,"a");
line(500,200,500,150);
outtextxy(497,130,"w");
line(500,200,500,250);
outtextxy(497,270,"x");
line(500,200,450,150);
outtextxy(445,130,"q");
line(500,200,550,150);
outtextxy(550,130,"e");
line(500,200,450,250);
outtextxy(445,270,"z");
line(500,200,550,250);
outtextxy(550,270,"c");/*以上是畫8個方向的控制介紹*/
setcolor(YELLOW);
outtextxy(420,290,"Press 'Enter' to end");/*壓回車鍵結束*/
setfillstyle(SOLID_FILL,RED);
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);/*入口位置顯示*/
while(c!=13)/*如果按下的不是回車鍵*/
{
c=getch();/*接收字元後開始各個方向的探索*/
if(c=='w'&&map[x-1][y]!=1)
DrawPeople(&x,&y,1);/*上*/
else
if(c=='e'&&map[x-1][y+1]!=1)
DrawPeople(&x,&y,2);/*右上*/
else
if(c=='d'&&map[x][y+1]!=1)
DrawPeople(&x,&y,3);/*右*/
else
if(c=='c'&&map[x+1][y+1]!=1)
DrawPeople(&x,&y,4);/*右下*/
else
if(c=='x'&&map[x+1][y]!=1)
DrawPeople(&x,&y,5);/*下*/
else
if(c=='z'&&map[x+1][y-1]!=1)
DrawPeople(&x,&y,6); /*左下*/
else
if(c=='a'&&map[x][y-1]!=1)
DrawPeople(&x,&y,7); /*左*/
else if(c=='q'&&map[x-1][y-1]!=1)
DrawPeople(&x,&y,8); /*左上*/
}
setfillstyle(SOLID_FILL,WHITE); /*消去紅色探索物，恢復原迷宮圖*/
bar(100+y*15-6,50+x*15-6,100+y*15+6,50+x*15+6);
if(x==N-2&&y==N-2)/*人工控制找成功的話*/
yes=1; /*如果成功標志為1*/
}
void WayCopy(int (*oldmap)[N],int (*map)[N])/*拷貝迷宮數組 */
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
oldmap[i][j]=map[i][j];
}
int FindWay(int (*map)[N],int i,int j)/*遞歸找路*/
{
if(i==N-2&&j==N-2)/*走到出口*/
{
yes=1;/*標志為1,表示成功*/
return;
}
map[i][j]=1;/*走過的地方變為1*/
WayCopy(oldmap,map); /*拷貝迷宮圖*/
if(oldmap[i+1][j+1]==0&&!yes)/*判斷右下方是否可走*/
{
FindWay(oldmap,i+1,j+1);
if(yes)/*如果到達出口了，再把值賦給顯示路線的way數組,也正是這個原因,所以具體路線是從最後開始保存*/
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j]==0&&!yes)/*判斷下方是否可以走,如果標志yes已經是1也不用找下去了*/
{
FindWay(oldmap,i+1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j+1]==0&&!yes)/*判斷右方是否可以走*/
{
FindWay(oldmap,i,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j]==0&&!yes)/*判斷上方是否可以走*/
{
FindWay(oldmap,i-1,j);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j+1]==0&&!yes)/*判斷右上方是否可以走*/
{
FindWay(oldmap,i-1,j+1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i+1][j-1]==0&&!yes)/*判斷左下方是否可以走*/
{
FindWay(oldmap,i+1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i][j-1]==0&&!yes)/*判斷左方是否可以走*/
{
FindWay(oldmap,i,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
WayCopy(oldmap,map);
if(oldmap[i-1][j-1]==0&&!yes)/*判斷左上方是否可以走*/
{
FindWay(oldmap,i-1,j-1);
if(yes)
{
way[wayn][0]=i;
way[wayn++][1]=j;
return;
}
}
return;
}
void MapRand(int (*map)[N])/*開始的隨機迷宮圖*/
{
int i,j;
cleardevice();/*清屏*/
randomize(); /*隨機數發生器*/
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
if(i==0||i==N-1||j==0||j==N-1)/*最外面一圈為牆壁*/
map[i][j]=1;
else
if(i==1&&j==1||i==N-2&&j==N-2)/*出發點與終點表示為可走的*/
map[i][j]=0;
else
map[i][j]=random(2);/*其它的隨機生成0或1*/
}
}
}
void PrMap(int (*map)[N])/*輸出迷宮圖*/
{
int i,j;
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(map[i][j]==0)
{
setfillstyle(SOLID_FILL,WHITE);/*白色為可走的路*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
else
{
setfillstyle(SOLID_FILL,BLUE);/*藍色為牆壁*/
bar(100+j*15-6,50+i*15-6,100+j*15+6,50+i*15+6);
}
}
void Find(void)/*找到通路*/
{
int i;
setfillstyle(SOLID_FILL,RED);/*紅色輸出走的具體路線*/
wayn--;
for(i=wayn;i>=0;i--)
{
bar(100+way[i][1]*15-6,50+way[i][0]*15-6,100+
way[i][1]*15+6,50+way[i][0]*15+6);
sleep(1);/*控制顯示時間*/
}
bar(100+(N-2)*15-6,50+(N-2)*15-6,100+
(N-2)*15+6,50+(N-2)*15+6); /*在目標點標紅色*/
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Find a way!");
}
void NotFind(void)/*沒找到通路*/
{
setcolor(GREEN);
settextstyle(0,0,2);/*設置字體大小*/
outtextxy(130,400,"Not find a way!");
}
void Result(void)/*結果處理*/
{
if(yes)/*如果找到*/
Find();
else/*沒找到路*/
NotFind();
getch();
}
void Close(void)/*圖形關閉*/
{
closegraph();
}
『叄』 C語言用圖的廣度優先遍歷做漫步迷宮問題
這是我們老師給我們上數據結構課的課件
#include "stdio.h"
typedef int datatype; /*假定線性表元素的類型為整型*/
#define maxsize 1024 /*假定線性表的最大長度為1024*/
# define n 100 /* 圖的頂點最大個數 */
typedef char VEXTYPE; /* 頂點的數據類型 */
typedef float ADJTYPE; /* 權值類型 */
typedef struct
{ VEXTYPE vexs[n] ; /* 頂點信息數組 */
ADJTYPE arcs[n][n] ; /* 邊權數組 */
int num ; /* 頂點的實際個數 */
}GRAPH;
/***********************1。置空圖**********************/
void GraphInit(GRAPH *L)
{
L->num=0;
}
/***********************2。求結點數**********************/
int GraphVexs(GRAPH *L)
{
return(L->num);
}
/***********************3。創建圖**********************/
void GraphCreate(GRAPH *L)
{
int i,j;
GraphInit(L);
printf("請輸入頂點數目：");
scanf("%d",&L->num);
printf("請輸入各頂點的信息(單個符號）：");
for(i=0;i<L->num;i++)
{
fflush(stdin);
scanf("%c",&L->vexs[i]);
}
printf("請輸入邊權矩陣的信息：");
for(i=0;i<L->num;i++)
{
for(j=0;j<L->num;j++)
{
scanf("%f",&L->arcs[i][j]);
}
}
printf("圖已經創建完畢！");
}
/***********************4。圖的輸出**********************/
void GraphOut(GRAPH L)
{
int i,j;
printf("\n圖的頂點數目為：%d",L.num);
printf("\n圖的各頂點的信息為：\n");
for(i=0;i<L.num;i++)
printf("%c ",L.vexs[i]);
printf("\n圖的邊權矩陣的信息為：\n");
for(i=0;i<L.num;i++)
{
for(j=0;j<L.num;j++)
{
printf("%6.2f ",L.arcs[i][j]);
}
printf("\n");
}
printf("圖已經輸出完畢！");
}
/***********************5。圖的深度周遊**********************/
void DFS(GRAPH g,int qidian,int mark[])
//從第qidian個點出發深度優先周遊圖g中能訪問的各個頂點
{
int v1;
mark[qidian]=1;
printf("%c ",g.vexs[qidian]);
for(v1=0;v1<g.num;v1++)
{
if(g.arcs[qidian][v1]!=0&&mark[v1]==0)
DFS(g,v1,mark);
}
}
/***********************6。圖的深度周遊**********************/
void GraphDFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n深度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
//printf("v=%d ",v);
v1=v%g.num;
if(mark[v1]==0)
DFS(g,v1,mark);
}
}
typedef int DATATYPE; //隊列元素的數據類型
typedef struct
{
DATATYPE data[maxsize]; //隊中元素
int front,rear; //隊頭元素下標、隊尾元素後面位置的下標
} SEQQUEUE;
/*****************************************************************************/
void QueueInit(SEQQUEUE *sq)
//將順序循環隊列sq置空（初始化）
{
sq->front=0;
sq->rear=0;
}
/*****************************************************************************/
int QueueIsEmpty(SEQQUEUE sq)
//如果順序循環隊列sq為空，成功返回1，否則返回0
{
if (sq.rear==sq.front)
return(1);
else
return(0);
}
/*****************************************************************************/
int QueueFront(SEQQUEUE sq,DATATYPE *e)
//將順序循環隊列sq的隊頭元素保存到e所指地址，成功返回1，失敗返回0
{
if (QueueIsEmpty(sq))
else
}
/*****************************************************************************/
int QueueIn (SEQQUEUE *sq,DATATYPE x)
//將元素x入隊列sq的隊尾，成功返回1，失敗返回0
{
if (sq->front==(sq->rear+1)%maxsize)
{
printf("queue is full!\n");
return 0;
}
else
{
sq->data[sq->rear]=x;
sq->rear=(sq->rear+1)%maxsize;
return(1);
}
}
/*****************************************************************************/
int QueueOut(SEQQUEUE *sq)
//將隊列sq隊首元素出隊列，成功返回1,失敗返回0
{
if (QueueIsEmpty(*sq))
{
printf("queue is empty!\n");
return 0;
}
else
{
sq->front=(sq->front+1)%maxsize;
return 1;
}
}
/***********************7。圖的廣度周遊**********************/
void BFS(GRAPH g,int v,int mark[])
//從v出發廣度優先周遊圖g中能訪問的各個頂點
{
int v1,v2;
SEQQUEUE q;
QueueInit(&q);
QueueIn(&q,v);
mark[v]=1;
printf("%c ",g.vexs[v]);
while(QueueIsEmpty(q)==0)
{
QueueFront(q,&v1);
QueueOut(&q);
for(v2=0;v2<g.num;v2++)
{
if(g.arcs[v1][v2]!=0&&mark[v2]==0)
{
QueueIn(&q,v2);
mark[v2]=1;
printf("%c ",g.vexs[v2]);
}
}
}
}
/***********************8。圖的廣度周遊**********************/
void GraphBFS(GRAPH g)
//深度優先周遊圖g中能訪問的各個頂點
{
int qidian,v,v1,mark[maxsize];
printf("\n廣度周遊：");
printf("\n請輸入起點的下標：");
scanf("%d",&qidian);
for(v=0;v<g.num;v++)
{
mark[v]=0;
}
for(v=qidian;v<g.num+qidian;v++)
{
v1=v%g.num;
if(mark[v1]==0)
BFS(g,v1,mark);
}
}
/***********************主函數**********************/
void main()
{
GRAPH tu;
GraphCreate(&tu);
GraphOut(tu);
GraphDFS(tu);
GraphBFS(tu);
}
『肆』 c語言程序設計 迷宮問題
海龜作圖行不。這是我大一時的C語言課程設計，我自已做的。
高級級語言課程設計實驗報告
實驗課程：課程設計 年級：2004級 實驗成績：
課程設計名稱 海龜作圖 姓名：
任課教師： 學號：2004810025 實驗日期：
一、目的
通過編一些小程序，鞏固和利用所學的知識，加強變成能力。
本課題涉及的知識內容：for循環嵌套，if語句，二維數組，文件創建與保存，自定義函數等高級語言內容。
二、內容與設計思想
1． 設計內容
海龜爬行過程中，筆朝下紀錄海龜爬行蹤跡，筆朝上則不紀錄並保存蹤跡，
1表示筆朝上，2表示朝下，3右轉彎，4左轉彎，5，x向前走x格，6列印
9結束
2． 主要代碼結構
main()函數調用了兩個函數
3． 主要代碼段分析。
譬如print函數，列印海龜蹤跡並保存。Step函數當筆朝上時海龜走過的數組值加一
三、使用環境
本次上機實踐所使用的平台和相關軟體。
平台：Windows 2000
相關軟體：VC++
四、調試過程
1． 測試結果分析
經檢驗，運行結果正確
五、總結
1． 設計中遇到的問題及解決過程
調試過程中出現一些邏輯和語法錯誤，但是語法錯誤容易糾正，而
邏輯錯誤則比較難糾正。有時會漏掉「，」，「;」，「}」等符號
2． 設計體會和收獲。
發現自己也能解決有點復雜的問題
六、附錄
1． 源代碼
/*海龜作圖，活動區域50*50，超出區域，海龜死亡游戲完*/
#include<stdio.h>
void print(int [][49]);
void move(int [][49],int,int,int);
main()
{
int step[49][49];
int a,gostep,direct=1,record=1,i,j;
for(i=0;i<=49;i++)
for(j=0;j<=49;j++)
step[i][j]=0;
while(1)
{
scanf("%d,%d",&a,&gostep);
if(a==2) record=1;
if(a==1) record=0;
if(a==4)
{
direct++;
if(direct==5) direct=1;
continue;
}
if(a==3)
{
direct--;
if(direct==0) direct=4;
continue;
}
if(a==5)
{
move(step,gostep,direct,record);
continue;
}
if(a==6)
print(step);
if(a==9)
return 0;
}
}
/*列印海龜蹤跡並保存*/
void print(int s[][49])
{
int i,j;
FILE *fp;
fp=fopen("D:\\step.txt","w");
for(i=0;i<=49;i++)
{
for(j=0;j<=49;j++)
{
printf(s[i][j]==0? " ":"*");
fprintf(fp,s[i][j]==0? " ":"*");
}
printf("\n");
}
fclose(fp);
}
void move(int t[][49],int i,int j,int k)
{
static int x=0,y=0;
int xmove,ymove,num;
if(j==1)
{
xmove=1;ymove=0;}
if(j==2)
{
xmove=0;ymove=-1;
}
if(j==3)
{
xmove=-1;ymove=0;
}
if(j==4)
{
xmove=0;ymove=1;
}
for(num=0;num<i;num++)
{
t[0][0]=1;
x+=xmove;
y+=ymove;
if(x<0||x>49||y<0||y>49)
{
printf("the place is danger ,you are died");
exit();
}
t[y][x]+=k;
}
}
『伍』 迷宮問題的課程設計報告
http://download.csdn.net/source/298953
這里有下載呼呼
還有個要交錢的也給你吧
http://cn.happycampus.com/docs/983345939101@hc04/56958/
『陸』 c語言課程設計一個迷宮
讓人完全幫你寫一個這基本沒機會，
迷宮的隨機生成要注意調整隨機變數的值，不斷測試，盡量得出一個比較可行迷宮生成器。
提醒你一下就是 自動運行探索那裡，如果要用遞歸的話，寫一個函數，判斷該店是否可行，如果可行，就調用該函數探索周圍的點，地圖可以看做一個二維數組,0，1判斷是否可行，
這里給你一個偽代碼例子
//1表示可行，0表示不可行
search_map（a[][MAX],point_x,point_y）
{
if（a[point_x][point_y]==0&&數組未越界)
{
search_map(a,point_x+1,point_y);
search_map(a,point_x-1,point_y);
search_map(a,point_x,point_y+1);
search_map(a,point_x,point_y-1);
}
}
調用這個函數的時候在主函數調用search_map（a,入口_x，入口_y)即可，這樣可以查到所有可以達到的范圍，最後可以抽取一條或數條可行路徑。
『柒』 C++課程設計：迷宮問題演示程序
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;
#define M 15
#define N 15
int z=0;
struct Point
{
int m_1;
int n_1;
Point_cout();
Point_cout1();
};
Point::Point_cout()
{
return(m_1);
}
Point::Point_cout1()
{
return(n_1);
}
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
}; struct Element
{
int x,y; //x行,y列
int d; //d下一步的方向
}; typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/ int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
} int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
} int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
} int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[2][4][2],int z,int &a,int &b)
{
int m=a;
int n=b;
int i,j,d;
int a_1,b_1;
Element elem;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
if(z<2)
{
for(int w_1=0;w_1<9;w_1++)
for(int w_2=0;w_2<8;w_2++)
if(maze[w_1][w_2]==2)
maze[w_1][w_2]=0;
maze[start.x][start.y]=2;
//入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1;
Push(S1,elem); //開始為-1
//cout<<elem.x<<" "<<elem.y<<" "<<elem.d<<" "; while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
//cout<<elem.x<<elem.y<<elem.d;
i=elem.x;
j=elem.y;
d=elem.d+1;while(d<4) //試探東南西北各個方向
{
a_1=i+diradd[z][d][0];
b_1=j+diradd[z][d][1];
if(a_1==end.x && b_1==end.y && maze[a_1][b_1]==0) //如果到了出口
{
cout<<"可以到達出口的路徑有："<<endl;
//maze[a][b]=2
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a_1;
elem.y=b_1;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
//cout<<"\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)";
cout<<endl;
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,elem);
//cout<<"("<<e.x<<","<<e.y<<","<<e.d<<")"<<"-->";
Push(S2,elem);
}
while(S2)
{
Pop(S2,elem);
printf("-->(%d,%d,%d)",elem.x,elem.y,elem.d);
}
cout<<endl;
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
++z;
MazePath(start,end,maze,diradd,z,a,b);
}
if(maze[a_1][b_1]==0) //找到可以前進的非出口的點
{
maze[a_1][b_1]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a_1; //下一點轉化為當前點
j=b_1;
d=-1;
}
d++;
}
}
//cout<<"("<<elem.x<<","<<elem.y<<","<<elem.d<<")"<<"-->"<<"||";
}
//cout<<"沒有找到可以走出此迷宮的路徑\n";
}
/*************建立迷宮*******************/
int initmaze(int maze[M][N],int &a,int &b)
{
int i,j;
int m,n; //迷宮行,列
cout<<"請輸入迷宮的行數 m=";
cin>>m;
cout<<"請輸入迷宮的列數 n=";
cin>>n;
a=m;
b=n;
cout<<"請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆:";
cout<<endl;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
cin>>maze[i][j];
cout<<"你建立的迷宮為:";
cout<<endl;
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=8;
maze[i][n+1]=8;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=8;
maze[m+1][j]=8;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
cout<<maze[i][j]<<" ";
cout<<endl;
}
return 0;
} void main()
{
int a=0;
int b=0;
int sto[M][N]; struct mark start,end; //start,end入口和出口的坐標
int add[2][4][2]={{{0,1},{1,0},{0,-1},{-1,0}},{{1,0},{0,1},{0,-1},{-1,0}}};//行增量和列增量 方向依次為東西南北
cout<<"注:上面的式子一維為2，根據東西南北，共有16種排列，因數量太多，故省略只寫順序依次為東南西北和南東西北";
cout<<endl;
initmaze(sto,a,b);//建立迷宮
cout<<"輸入入口的橫坐標,縱坐標";
cin>>start.x>>start.y;
cout<<"輸入出口的橫坐標,縱坐標";
cin>>end.x>>end.y;
MazePath(start,end,sto,add,z,a,b); //find path
//system("PAUSE");
}
// 下面是以9行8列的輸入（你可以復制，黏貼就ok 了）0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1
『捌』 c語言迷宮問題程序功能介紹.設計思路.數據結構設計及用法說明程序結構（流程圖）.各模塊的功能及程序說明.
原來也做過，以下是寫的源代碼，裡面有部分注釋，應該能看懂，可以運行。總結的話，把代碼寫進去，再隨便弄幾句心得說幾句好好學C應該就OK了吧
#include<stdio.h>
#include<stdlib.h>
#define M 15
#define N 15
struct mark //定義迷宮內點的坐標類型
{
int x;
int y;
};
struct Element //"戀"棧元素，嘿嘿。。
{
int x,y; //x行,y列
int d; //d下一步的方向
};
typedef struct LStack //鏈棧
{
Element elem;
struct LStack *next;
}*PLStack;
/*************棧函數****************/
int InitStack(PLStack &S)//構造空棧
{
S=NULL;
return 1;
}
int StackEmpty(PLStack S)//判斷棧是否為空
{
if(S==NULL)
return 1;
else
return 0;
}
int Push(PLStack &S, Element e)//壓入新數據元素
{
PLStack p;
p=(PLStack)malloc(sizeof(LStack));
p->elem=e;
p->next=S;
S=p;
return 1;
}
int Pop(PLStack &S,Element &e) //棧頂元素出棧
{
PLStack p;
if(!StackEmpty(S))
{
e=S->elem;
p=S;
S=S->next;
free(p);
return 1;
}
else
return 0;
}
/***************求迷宮路徑函數***********************/
void MazePath(struct mark start,struct mark end,int maze[M][N],int diradd[4][2])
{
int i,j,d;int a,b;
Element elem,e;
PLStack S1, S2;
InitStack(S1);
InitStack(S2);
maze[start.x][start.y]=2; //入口點作上標記
elem.x=start.x;
elem.y=start.y;
elem.d=-1; //開始為-1
Push(S1,elem);
while(!StackEmpty(S1)) //棧不為空 有路徑可走
{
Pop(S1,elem);
i=elem.x;
j=elem.y;
d=elem.d+1; //下一個方向
while(d<4) //試探東南西北各個方向
{
a=i+diradd[d][0];
b=j+diradd[d][1];
if(a==end.x && b==end.y && maze[a][b]==0) //如果到了出口
{
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem);
elem.x=a;
elem.y=b;
elem.d=886; //方向輸出為-1 判斷是否到了出口
Push(S1,elem);
printf("\n0=東 1=南 2=西 3=北 886為則走出迷宮\n\n通路為:(行坐標,列坐標,方向)\n");
while(S1) //逆置序列 並輸出迷宮路徑序列
{
Pop(S1,e);
Push(S2,e);
}
while(S2)
{
Pop(S2,e);
printf("-->(%d,%d,%d)",e.x,e.y,e.d);
}
return; //跳出兩層循環，本來用break,但發現出錯，exit又會結束程序，選用return還是不錯滴o(∩_∩)o...
}
if(maze[a][b]==0) //找到可以前進的非出口的點
{
maze[a][b]=2; //標記走過此點
elem.x=i;
elem.y=j;
elem.d=d;
Push(S1,elem); //當前位置入棧
i=a; //下一點轉化為當前點
j=b;
d=-1;
}
d++;
}
}
printf("沒有找到可以走出此迷宮的路徑\n");
}
/*************建立迷宮*******************/
void initmaze(int maze[M][N])
{
int i,j;
int m,n; //迷宮行,列
printf("請輸入迷宮的行數 m=");
scanf("%d",&m);
printf("請輸入迷宮的列數 n=");
scanf("%d",&n);
printf("\n請輸入迷宮的各行各列:\n用空格隔開,0代表路,1代表牆\n",m,n);
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
scanf("%d",&maze[i][j]);
printf("你建立的迷宮為o(∩_∩)o...\n");
for(i=0;i<=m+1;i++) //加一圈圍牆
{
maze[i][0]=1;
maze[i][n+1]=1;
}
for(j=0;j<=n+1;j++)
{
maze[0][j]=1;
maze[m+1][j]=1;
}
for(i=0;i<=m+1;i++) //輸出迷宮
{
for(j=0;j<=n+1;j++)
printf("%d ",maze[i][j]);
printf("\n");
}
}
void main()
{
int sto[M][N];
struct mark start,end; //start,end入口和出口的坐標
int add[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//行增量和列增量 方向依次為東西南北
initmaze(sto);//建立迷宮
printf("輸入入口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&start.x,&start.y);
printf("輸入出口的橫坐標,縱坐標[逗號隔開]\n");
scanf("%d,%d",&end.x,&end.y);
MazePath(start,end,sto,add); //find path
system("PAUSE");
}
『玖』 數據結構課程設計的迷宮問題~~~~急！！！
看下我的程序,,要不是你要的.
#include <iostream>
#include <iomanip>
using namespace std;
#define M 20
#define N 20
struct move{int dx,dy;};
move mazemove[8];
char ma[M][N];
int False=0;
void maze()
{int i,j,num;
for(i=1;i<M-1;i++)
{for(j=1;j<N-1;j++)
{num=(800*(i+j)+1500)%327;
if((num<156)&&(i!=M||j!=N))
ma[i][j]='1';
else
ma[i][j]='0';
}
}
ma[1][1]='0';
ma[M-2][N-2]='0';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
cout<<setw(3)<<ma[i][j];
cout<<endl;
}
}
void inimove()
{mazemove[0].dx=0;mazemove[0].dy=1;
mazemove[1].dx=1;mazemove[1].dy=1;
mazemove[2].dx=1;mazemove[2].dy=0;
mazemove[3].dx=1;mazemove[3].dy=-1;
mazemove[4].dx=0;mazemove[4].dy=-1;
mazemove[5].dx=-1;mazemove[5].dy=-1;
mazemove[6].dx=-1;mazemove[6].dy=0;
mazemove[7].dx=-1;mazemove[7].dy=1;
}
void outpath()
{int i,j,x,y,k;
i=1;j=1;k=0;
while((i!=(M-2))||(j!=(N-2)))
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='0'){k=0;break;}
}
if(k!=8)
{if(ma[i][j]=='8')ma[i][j]='2';
if(ma[i][j]=='0')ma[i][j]='>';
i=x;j=y;
}
else
{for(k=0;k<8;k++)
{x=i+mazemove[k].dx;
y=j+mazemove[k].dy;
if(ma[x][y]=='8')break;
}
ma[i][j]='2';
i=x;j=y;
}
if((i==1)&&(j==1))
{False=0;
break;
}
else False=1;
}
}
int main()
{int i,j;
maze();
inimove();
outpath();
cout<<endl;
if(False==0)
cout<<"無法走出該迷宮!"<<endl;
else
{cout<<"走出迷宮的路徑(用『>』符號表示)為:"<<endl;
ma[M-2][N-2]='>';
for(i=0;i<M;i++)
{for(j=0;j<N;j++)
{ {if(ma[i][j]=='2')ma[i][j]='>';
if(ma[i][j]=='0')ma[i][j]=' ';
if(ma[i][j]=='1')ma[i][j]='*';
}
cout<<setw(3)<<ma[i][j];
}
cout<<endl;
}
}
return 0;
}