qq_24616763 2014-12-18 13:25 采纳率: 0%
浏览 1902

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

#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条回答

  • Alden-lei 2014-12-18 16: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;
    }
    }

    评论

报告相同问题?

悬赏问题

  • ¥15 fpga自动售货机数码管(相关搜索:数字时钟)
  • ¥20 Python安装cvxpy库出问题
  • ¥15 用前端向数据库插入数据,通过debug发现数据能走到后端,但是放行之后就会提示错误
  • ¥15 python天天向上类似问题,但没有清零
  • ¥30 3天&7天&&15天&销量如何统计同一行
  • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
  • ¥15 C#调用python代码(python带有库)
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题