数据结构与算法课程设计迷宫
Ⅰ 迷宫课程设计
#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;
}
}
Ⅳ 数据结构课程设计任务书 求迷宫中从入口到出口的所有路径
这是一个有向图的问题，查找两点间的通路。