2 qq 24616763 qq_24616763 于 2014.12.18 21:25 提问

数据结构课设,急求代码注释

#include "stdlib.h"
#include "stdio.h"
#include "time.h"

#define STACK_INIT_SIZE 10

typedef struct
{
int x; //当前位置的横坐标
int y; //当前位置的纵坐标
char type; //当前位置的属性:墙壁或通道(0/1)
bool isfoot; //判断当位置是否已走过, true代表已走过
}Position; //当前位置信息

typedef struct
{
int order; //脚步在地图上的序号
Position seat; //行走的当前位置
int aspect; //下一步的方向
}Block; //脚步

typedef struct
{
int width; //地图的长度
int height; //地图的宽度
Position* site; //地图内的各个位置
}Maze; //地图

typedef struct
{
Block* base;
Block* top;
int lenght;
int stacksize;
}Stack;

bool InitStack(Stack &S)
{
S.base=(Block*)malloc(STACK_INIT_SIZE*sizeof(Block));
if(!S.base) return 0;
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
S.lenght=0;
return 1;
}

bool Push(Stack &S,Block data)
{
if(S.lenght>=S.stacksize)
{
S.base=(Block*)realloc(S.base,(STACK_INIT_SIZE+S.stacksize)*sizeof(Block));
if(!S.base) return 0;
S.top=S.base+S.stacksize;
S.stacksize+=STACK_INIT_SIZE;
}
*S.top=data;
S.top++;
S.lenght++;
return 1;
}

bool Pop(Stack &S,Block &data)
{
if(S.top==S.base) return 0;
S.top--;
data=*S.top;
S.lenght--;
return 1;
}

void DestroyStack(Stack &S)
{
free(S.base);
}

void ClearStack(Stack &S)
{
DestroyStack(S);
InitStack(S);
}
Maze* GreatMaze(int width,int height) //创建地图
{
Maze* maze=(Maze*)malloc(sizeof(Maze)); //为地图分配存放空间
maze->width=width;
maze->height=height;
maze->site=(Position*)malloc(width*height*sizeof(Position)); //为地图坐标分配空间
srand((unsigned)time(NULL)); //产生随机数

int i,k,j=0;
if(width>0&&height>0)
{
    for(i=0;i<maze->width;i++)
        for(k=0;j<maze->height*(i+1);j++,k++)
        {
            maze->site[j].x=k;
            maze->site[j].y=i;
            int n=rand()%9+1;
            if(n>5)
                maze->site[j].type='0';  //设置墙壁
            else
                maze->site[j].type='1';  //设置通道
        }
}
return maze;  //返回定义好的地图

}

void PrintMaze(Maze* maze) //打印地图
{
int i,j=0;
printf("\t");
for(i=0;iwidth;i++)
printf("%d ",i); //打印横坐标
printf("\n");
printf("\n");
for(i=0;iheight;i++)
{
printf("%d\t",i); //打印纵坐标
for(j;jwidth*(i+1);j++)
if(maze->site[j].type=='0')
printf("■"); //打印墙壁
else
printf("□"); //打印通道
printf("\n");
}
}

bool PositionComparison(Position maze,Position pos) //判断当前位置是否合法
{
if(maze.x==pos.x && maze.y==pos.y)
return 1;
else
return 0;
}

bool Pass(Maze* maze,Position curpos)
{
Position *pos;
pos=maze->site;
for(int i=0;iheight*maze->width;i++)
{
if(PositionComparison(*pos,curpos)) //判断当前位置是否合法
if(pos->type=='0'|| maze->site[i].isfoot==true) //判断当前位置是否可以前进或者是否走过
return 0;
else
return 1;
pos++;
}
return 0;
}

void FootSet(Maze* maze,Position site) //留下足迹
{
for(int i=0;iheight*maze->width;i++)
{
if(PositionComparison(maze->site[i],site))
{
maze->site[i].isfoot=true; //留下已走过的足迹
}
}
}

Position NextPos(Position &cur,int aspect)
{
switch(aspect)
{
case 1:cur.y+=1;break; //向下
case 2:cur.x+=1;break; //向右
case 3:cur.y-=1;break; //向上
case 4:cur.x-=1;break; //向左
}
return cur;
}

bool MazePath(Maze* maze,Position start,Position end,Stack &S)
{
int curstep;
Position curpos; //探索的位置
Block path; //脚步
InitStack(S);
curpos.x=start.x;
curpos.y=start.y; //入口
curstep=1; //探索第一步
do
{
if(Pass(maze,curpos)) //当前位置是否可以通过
{
FootSet(maze,curpos); //留下足迹
path.order=curstep; //当前走过的总步数
path.seat=curpos; //踏下脚步
path.aspect=1;
Push(S,path); //保存脚步
if(PositionComparison(curpos,end)) //判断是否是重点
return 1;
curpos=NextPos(curpos,1); //继续向下一个方向探索
curstep++; //探索的步数增加一
}
else
{
if(S.lenght!=0)
{
Pop(S,path); //退到上一步
while(path.aspect==4 && S.lenght!=0) //如果当前位置无法再前行,再退回一步
Pop(S,path);
if(path.aspect<4) //如果当前位置可再继续探索
{
path.aspect++; //转变探索方向
Push(S,path); //保存当前位置(只更新了探索方向)
curpos=NextPos(path.seat,path.aspect); //继续探索下一个方向
}
}
}
}while(S.lenght!=0);
return 0;
}

int main(int argc)
{
Position start,end;
Block blk;
Stack S;
int width,height;
printf("输入迷宫比例X*Y\n");
printf("输入X:");
scanf("%d",&width);
printf("输入Y:");
scanf("%d",&height);
Maze* maze=GreatMaze(width,height);
PrintMaze(maze);
printf("\n");
printf("请输入入口坐标X:");
scanf(" %d",&start.x);
printf("请输入入口坐标Y:");
scanf(" %d",&start.y);
printf("请输入出口坐标X:");
scanf(" %d",&end.x);
printf("请输入出口坐标Y:");
scanf(" %d",&end.y);
MazePath(maze,start,end,S);
printf("走完所需路径长度为:%d",S.lenght);
printf("\n");
Stack Sa;
InitStack(Sa);
while(S.lenght!=0)
{
Pop(S,blk);
Push(Sa,blk);
}
while(Sa.lenght!=0)
{
Pop(Sa,blk);
if(Sa.lenght!=0)
printf("[%d,%d]->",blk.seat.x,blk.seat.y); //打印足迹
else
printf("[%d,%d]",blk.seat.x,blk.seat.y); //打印最后一步
}
}
求帮忙注释,最好能指导下哪里用到了什么

2个回答

u012848247
u012848247   2014.12.19 00:13

迷宫求解问题,可以参考下
/////////////LinkList.h文件//////////////////////////
#include
#include
using namespace std;
struct DataType //定义描述迷宫中当前位置的结构类型
{
int x; //x代表当前位置的行坐标
int y; //y代表当前位置的列坐标
int pre; //pre表示移动到下一步的方向
};
struct Move //定义下一个位置的方向
{
int x;
int y;
};
struct LinkNode //链表结点
{
DataType data;
LinkNode *next;
};
//下面定义栈
class stack
{
private:
LinkNode *top; //指向第一个结点的栈顶指针
public:
stack(); //构造函数,置空栈
~stack(); //析构函数
void Push(DataType data); //把元素data压入栈中
DataType Pop(); //使栈顶元素出栈
DataType GetPop(); //取出栈顶元素
void Clear(); //把栈清空
bool IsEmpty(); //判断栈是否为空,如果为空则返回1,否则返回0
};

/////////////////////////////////////
/////////LinkList.cpp文件////////////
#include"LinkList.h"
stack::stack() //构造函数,置空栈
{
top=NULL;
}
stack::~stack() //析构函数
{

}
void stack::Push(DataType x) //把元素data压入栈中
{
LinkNode *TempNode;
TempNode=new LinkNode;
TempNode->data=x;
TempNode->next=top;
top=TempNode;
}
DataType stack::Pop() //使栈顶元素出栈
{
DataType Temp;
LinkNode *TempNode;
//if(top==NULL) return NULL;
// else
// {
TempNode=top;
top=top->next;
Temp=TempNode->data;
delete TempNode;
return Temp;
// }
}
DataType stack::GetPop() //取出栈顶元素
{
return top->data;
}
void stack::Clear() //把栈清空
{
top=NULL;
}
bool stack::IsEmpty() //判断栈是否为空,如果为空则返回1,否则返回0
{
if(top==NULL) return true;
else return false;
}
////////////////////////////////////////////////////////
////////////////main.cpp文件////////////////////////////

#include"LinkList.h"
Move move[4]={{0,1},{1,0},{0,-1},{-1,0}}; //定义当前位置移动的4个方向
bool Mazepath(int maze,int m,int n);
//寻找迷宫maze中从(0,0)到(m,n)的路径
//到则返回true,否则返回false
void PrintPath(stack p); //输出迷宫的路径
void Restore(int **maze,int m,int n); //恢复迷宫
int
GetMaze(int &m,int &n); //获取迷宫(可从文件中读取,也可输入)
//返回存取迷宫的二维指针

int main()
{
int m=0,n=0; //定义迷宫的长和宽
int **maze; //定义二维指针存取迷宫
maze=GetMaze(m,n); //调用GetMaze(int &m,int &n)函数,得到迷宫
if(Mazepath(maze,m,n)) //调用Mazepath(int **maze,int m,int n)函数获取路径
cout<<"迷宫路径探索成功!/n";
else cout<<"路径不存在!/n";
return 0;
}

int** GetMaze(int &m,int &n)
//获取迷宫(可从文件中读取,也可输入)
//返回存取迷宫的二维指针
{
int **maze; //定义二维指针存取迷宫
int i=0,j=0;
char Choose; //定义一个标志,选择读取文件或直接输入,获取迷宫
cout<<"请选择从文件中读取文件(1)或重新输入(2):";
cin>>Choose; //输入标志
if(Choose=='1') //当标志Choose为‘1’时,读取文件
{
cout<<"文件里的数字化迷宫如下:/n";
char ch; //定义一个字符,读取文件中的内容
i=0,j=0;
//首先得到文件中数字字符的数目,并得到迷宫的长和宽
ifstream fip("test.txt");
//定义一个文件对象,并打开文件“test.txt”
while(fip.get(ch)) //从读取文件中内容(一个个字符)
{
if(ch>='0'&&ch<='9') //获取文件中的数字字符
{
j++; //如果是字符,宽就加1
}
if(ch=='/n')
{
i++; //如果是换行,就行加1
n=j; //得到宽,即列数
j=0;
}
}
fip.close(); //读取文件结束
m=i; //得到长即行数
maze=new int *[m+2]; //申请长度等于行数加2的二级指针
for(i= 0;i {
maze[i]=new int[n+2];
}
i=j=1;
ifstream fip2("test.txt");//重新读取文件,以得到内容
while(fip2.get(ch))
{
if(ch>='0'&&ch<='9')
{
maze[i][j]=ch-'0'; //把数字字符转化为数字,并存到指针里
cout<<maze[i][j]<<" "; //在屏幕中显示迷宫
j++;
}
if(ch=='/n') //遇到换行,指针也相应换行
{
cout<<endl;
i++;
j=1;
}
}
fip2.close(); //读取结束
}

else //Choose=2 ,输入迷宫
{
cout<<"请输入迷宫的长和宽:";
int a,b;
cin>>a>>b; //输入迷宫的长和宽
cout<<"请输入迷宫内容:/n";
m=a;
n=b; //m,n分别代表迷宫的行数和列数
maze=new int *[m+2]; //申请长度等于行数加2的二级指针
for(i= 0;i {
maze[i]=new int[n+2];
}
for(i=1;i for(j=1;j cin>>maze[i][j];
cout<<"是否保存新迷宫?/n";
char choose;
cin>>choose;
if(choose=='Y'||choose=='y')
{
char ch;
ofstream fop("Newtest.txt");
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
ch='0'+maze[i][j];
fop< }
fop flush(cout);
}
fop.close();
}
}
//给迷宫的四周加一堵墙,即把迷宫四周定义为1
for(i=0;i maze[i][0]=maze[i][n+1]=1;
for(i=0;i maze[0][i]=maze[m+1][i]=1;
return maze; //返回存贮迷宫的二维指针maze
}
bool Mazepath(int **maze,int m,int n)
//寻找迷宫maze中从(0,0)到(m,n)的路径
//到则返回true,否则返回false
{
stack q,p; //定义栈p、q,分别存探索迷宫的过程和存储路径
DataType Temp1,Temp2;
int x,y,loop;
Temp1.x=1;
Temp1.y=1;
q.Push(Temp1); //将入口位置入栈
p.Push(Temp1);
maze[1][1]=-1; //标志入口位置已到达过
while(!q.IsEmpty()) //栈q非空,则反复探索
{
Temp2=q.GetPop(); //获取栈顶元素
if(!(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y))
p.Push(Temp2);
//如果有新位置入栈,则把上一个探索的位置存入栈p
for(loop=0;loop {
x=Temp2.x+move[loop].x; //计算出新位置x位置值
y=Temp2.y+move[loop].y; //计算出新位置y位置值
if(maze[x][y]==0) //判断新位置是否可达
{
Temp1.x=x;
Temp1.y=y;
maze[x][y]=-1; //标志新位置已到达过
q.Push(Temp1); //新位置入栈
}
if((x==(m))&&(y==(n))) //成功到达出口
{
Temp1.x=m;
Temp1.y=n;
Temp1.pre=0;
p.Push(Temp1); //把最后一个位置入栈
PrintPath(p); //输出路径
Restore(maze,m,n); //恢复路径
return 1; //表示成功找到路径
}
}
if(p.GetPop().x==q.GetPop().x&&p.GetPop().y==q.GetPop().y)
//如果没有新位置入栈,则返回到上一个位置
{
p.Pop();
q.Pop();
}
}
return 0; //表示查找失败,即迷宫无路经
}
void PrintPath(stack p) //输出路径
{
cout cout stack t; //定义一个栈,按从入口到出口存取路径
int a,b;
DataType data;
LinkNode *temp;
temp=new LinkNode; //申请空间
temp->data=p.Pop(); //取栈p的顶点元素,即第一个位置
t.Push(temp->data); //第一个位置入栈t
delete temp; //释放空间
while(!p.IsEmpty()) //栈p非空,则反复转移
{
temp=new LinkNode;
temp->data=p.Pop(); //获取下一个位置
//得到行走方向
a=t.GetPop().x-temp->data.x; //行坐标方向
b=t.GetPop().y-temp->data.y; //列坐标方向
if(a==1) temp->data.pre=1; //方向向下,用1表示
else if(b==1) temp->data.pre=2; //方向向右,用2表示
else if(a==-1) temp->data.pre=3; //方向向上,用3表示
else if(b==-1) temp->data.pre=4; //方向向左,用4表示
t.Push(temp->data); //把新位置入栈
delete temp;
}
//输出路径,包括行坐标,列坐标,下一个位置方向
while(!t.IsEmpty()) //栈非空,继续输出
{
data=t.Pop();
cout<<'('<<data.x<<','<<data.y<<','<<data.pre<<","; //输出行坐标,列坐标
switch(data.pre) //输出相应的方向
{
case 1:cout<<"↓)/n";break;
case 2:cout<<"→)/n";break;
case 3:cout<<"↑)/n";break;
case 4:cout<<"←)/n";break;
case 0:cout<<")/n";break;
}
}
}
void Restore(int **maze,int m,int n) //恢复迷宫
{
int i,j;
for(i=0;i<m+2;i++) //遍历指针
for(j=0;j<n+2;j++)
{
if(maze[i][j]==-1) //恢复探索过位置,即把-1恢复为0
maze[i][j]=0;
}
}

wangyaninglm
wangyaninglm   Ds   Rxr 2014.12.19 12:26

楼上那个就挺好啊。我觉的

Csdn user default icon
上传中...
上传图片
插入图片