數據結構與演算法課程設計迷宮
Ⅰ 迷宮課程設計
#include<stdio.h> struct PosType //迷宮坐標位置類型 { int x; int y; }; #define MAXLENGTH 25 //設迷宮的最大行列為25 typedef int MazeType[MAXLENGTH][MAXLENGTH];//[行][列] struct PosType end; //迷宮終點位置 MazeType m; //迷宮數組 int x,y; //迷宮行數，列數 void Print(int x,int y) { int i,j; for(i = 0;i<x;i++) { for(j=0;j<y;j++) printf("%3d",m[i][j]); printf("\n"); } printf("\n"); } void Try(struct PosType cur,int curstep) { int i;//由當前位置，當前步驟curstep試探下一點 struct PosType next;//下一個位置 struct PosType direc[4] = {{0,1},{1,0},{0,-1},{-1,0}};//{行增量}，{列增量} for(i=0;i<=3;i++) { next.x = cur.x + direc[i].x; next.y = cur.y + direc[i].y; if(m[next.x][next.y]==-1)//是通路 { m[next.x][next.y]=++curstep; if(next.x!=end.x || next.y!=end.y)//沒到終點 Try(next,curstep);//試探下一點（遞歸調用） else Print(x,y);//輸出結果 m[next.x][next.y]=-1;//恢復為通路，試探下一條路 curstep--; } } } void main() { struct PosType begin; int i,j,x1,y1; printf("請輸入迷宮的行數，列數（包括外牆):"); scanf("%d,%d",&x,&y); for(i = 0;i<x;i++)//定義周邊值為0（同牆) { m[0][i] = 0; //行周邊 m[x-1][i] = 0; } for(j=1;j<y-1;j++) { m[j][0]=0;//列周邊 m[j][y-1]=0; } for(i=1;i<x-1;i++) for(j=1;j<y-1;j++) m[i][j]=-1;//定義通道初值為-1 printf("請輸入迷宮內牆單元數："); scanf("%d",&j); if(j) printf("請依次輸入迷宮內牆每個單元的行數，列數：\n"); for(i=1;i<=j;i++) { scanf("%d,%d",&x1,&y1); m[x1][y1]=0; } printf("迷宮結構如下:\n"); Print(x,y); printf("請輸入起點的行數，列數:"); scanf("%d,%d",&begin.x,&begin.y); printf("請輸入終點的行數，列數"); scanf("%d,%d",&end.x,&end.y); m[begin.x][begin.y]=1; Try(begin,1); }
Ⅱ 數據結構課程設計的迷宮問題~~~~急！！！
看下我的程序,,要不是你要的.
#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;
}
Ⅲ 用數據結構解迷宮
#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();
}
另外一個，是數據結構的：
#include<stdio.h>
#define NUM 10/* 定義物品總數*/
#define CONTENT 10 /*定義包的容量*/
void knapsack(int v[NUM],int w[NUM],int c,int m[NUM ][CONTENT])
{
int n=NUM-1;
int i,j;
int jMax;
if((w[n]-1)< c)
jMax = w[n]-1;
else
jMax = c;
/* 初始化m[n][j] */
for(j = 0; j <= jMax; j++)
m[n][j] = 0;
for(j = jMax +1; j <= c; j++)
m[n][j] = v[n];
/*使用非遞歸的演算法來求解m[i][j] */
for(i = n-1; i > 0; i--)
{
if((w[i]-1)< c)
jMax = w[i]-1;
else
jMax = c;
for(j = 0; j <= jMax; j++)
m[i][j] = m[i+1][j] ;
for(j = jMax +1; j <= c; j++)
{
if(m[i+1][j] >= (m[i+1][j-w[i]]+v[i]))
m[i][j] = m[i+1][j] ;
else
m[i][j] = m[i+1][j-w[i]]+v[i];
}
}
if(c>w[0])
{
if(m[1][c] >= (m[1][c-w[0]]+v[0]))
m[0][c]= m[1][c];
else
m[0][c]= m[1][c-w[0]]+v[0];
}
else
m[0][c]= m[1][c];
}
/*尋找最優解*/
void traceback(int flag[NUM],int w[NUM],int m[NUM][CONTENT])
{
int n = NUM -1;
int i;
int c = CONTENT;
for(i = 0; i < n; i++)
{
if(m[i][c] == m[i+1][c])
flag[i] = 0;
else
{
flag[i] = 1;
c-=w[i];
}
}
if(m[n][c] >0)
flag[n] = 1;
else
flag[n] = 0;
}
/* 列印最優解*/
void printResult(int flag[NUM],int w[NUM],int v[NUM],int m[NUM][CONTENT])
{
int i;
printf("the knapsack should contain:\n");
printf(" num weight value \n");
for(i = 0;i < NUM; i++)
{
if(flag[i] == 1)
printf(" %d %d %d\n",i,w[i],v[i]);
}
printf("the max value in the knapsack is: %d\n",m[0][CONTENT]);
}
int main()
{
int value[NUM]={5,2,3,4,3,6,5,7,8,2};
int weight[NUM]={2,1,3,2,4,3,5,6,2,2};
int c = CONTENT;
int maxvalue[NUM][CONTENT];
int flag[NUM]={0,0,0,0,0,0,0,0,0,0};
clrscr();
printf("****************************************\n");
printf("* this program will solve *\n");
printf("* the problem of 0-1knapsack *\n");
printf("****************************************\n");
/*計算最優值*/
knapsack(value,weight,c,maxvalue);
/*構造最優解*/
traceback(flag,weight,maxvalue);
/*列印程序的結果*/
printResult(flag,weight,value,maxvalue);
getch();
return 0;
}
Ⅳ 能給個數據結構自動生成迷宮圖的演算法嗎
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int M,N;
typedef struct _Position
{
int x;
int y;
}Position;
void Print( int** const );
void Line( int** const p, Position, Position );
int main()
{
srand( (unsigned)time(NULL) );
Position a,b;
int i,j;
printf("請輸入迷宮行列:");
scanf("%d %d",&M,&N);
while(getchar()!='\n');
int** const p = (int**) malloc( M*sizeof(int*) );
for( i=0; i<M; i++ )
{
p[i] = (int*) malloc( N*sizeof(int) );
for( j=0; j<N; j++ )
{
p[i][j]=1;
}
}
p[1][1]=p[M-2][N-2]=0;
a.x=M-2;
a.y=N-2;
b.x=1;
b.y=1;
Line( p, a, b );
while(1)
{
a.x=rand()%(M-1)+1;
a.y=rand()%(N-1)+1;
b.x=rand()%(M-1)+1;
b.y=rand()%(N-1)+1;
if( a.x < b.x )
{
i=a.x;
a.x=b.x;
b.x=a.x;
}
Line( p, a, b);
if( rand()%6 ==0 ) break;
}
Print( p );
getchar();
return 0;
}
void Print( int** const dat )
{
int i,j;
for( i=0; i<M; i++ )
{
for( j=0; j<N; j++ )
{
printf("%d",dat[i][j]);
}
printf("\n");
}
printf("\n");
}
void Line( int** const p, Position Fr, Position To )
{
srand( (unsigned)time(NULL) );
int a,b,x,y,i,j;
a=Fr.x;
b=Fr.y;
i=Fr.x-1;
while(i>=To.x)
{
if(i==To.x)
{
j=To.y;
}
else
{
j=rand()%(N-1)+1;
}
p[i][j]=0;
x=i;
y=j;
while(j!=b)
{
p[i][j]=0;
if(p[i+1][j]==0)
{
break;
}
if(j>b)
{
j--;
}
else
{
j++;
}
if(i!=a && (rand()%2)==0)
{
p[i][j]=0;
i++;
}
}
a=x;
b=y;
i=x-1;
}
}
Ⅳ 數據結構課程設計任務書 求迷宮中從入口到出口的所有路徑
這是一個有向圖的問題，查找兩點間的通路。