数据结构与算法课程设计报告-哈工大-应用不相交集合生成随即迷宫 - 图文

哈尔滨工业大学课程设计报告

3 算法实现

3.1 开发语言及工具

开发语言：JAVA 开发工具：eclipse

3.2 算法关键代码

3.2.1 构建随机迷宫算法关键代码

public void CreateMaze(int Maze[][]) { //生成随机迷宫，存在二维数组Maze中

int x,y,i,j,d,xt1,yt1,xt2,yt2,count = n*n; Init(); //初始化等价类

for(i = 0;i < wid;i++) { //初始化二维数组 }

for(i = 1;i < wid;i++) { //初始化二维数组 }

while(count > 1) { //循环至只有一个等价类结束

do {

x = (int)(Math.random()*wid); y = (int)(Math.random()*wid); if(i%2 == 1) { } else { }

for(j = 1;j < wid;j += 2) { }

Maze[i][j] = 1;

//1为墙

for(j = 1;j < wid;j += 2) { }

for(j = 2;j < wid;j += 2) { }

Maze[i][j] = 1;

//1为墙

Maze[i][j] = 5;

//5为格子

for(j = 0;j < wid;j++) { }

Maze[i][j] = 9;

//9为不可到达的点

}while(Maze[x][y] != 1); d = x%2; if(d == 0) {

yt1 = y; xt2 = x - 1; yt2 = y;

if(FindSet(postolist(xt1,yt1)) != FindSet(postolist(xt2,yt2))) {

Maze[x][y] = 0;

9

//墙为竖直方向的

xt1 = x + 1;

哈尔滨工业大学课程设计报告

}

}

}

}

UnionSet(postolist(xt1,yt1),postolist(xt2,yt2)); count--;

else { //墙为水平方向的 }

xt1 = x; yt1 = y + 1; xt2 = x; yt2 = y - 1;

if(FindSet(postolist(xt1,yt1)) != FindSet(postolist(xt2,yt2))) { }

Maze[x][y] = 0;

UnionSet(postolist(xt1,yt1),postolist(xt2,yt2)); count--;

int rank[] = new int[MAX]; //存储节点的层数

int parent[] = new int[MAX]; //存储相应节点的父节点 public void Init() { }

public int FindSet(int x) { }

public void UnionSet(int root1,int root2) { }

public int postolist(int x,int y) { }

10

//初始化等价类，一个格子为一个等价类

for(int i = 0;i < MAXSIZE;i++) { }

//找到二叉树的根节点

rank[i] = 0; parent[i] = i;

if(x != parent[x])

parent[x] = FindSet(parent[x]); return parent[x];

//合并等价类

int x = FindSet(root1); int y = FindSet(root2); if(x == y) return;

if(rank[x] > rank[y]) parent[y] = x; else { }

//将二维数组中（x，y）转化为一维数组对应的i

parent[x] = y;

if(rank[x] == rank[y]) ++rank[y];

return (x/2)*n + (y/2);

哈尔滨工业大学课程设计报告

3.2.2 寻找迷宫路径算法关键代码

public Stack getPath(){ //寻找迷宫路径，存储在栈中 }

11

Stack stackP = new Stack(); int x=1,y=1;

//起点坐标（1，1）

stackP.Push(1,1);

setBeen(x,y); //标记为已到达

do{

if(ableRight(x,y)){ //如果向右没有墙，则将右边格子压入栈 }

else if(ableLeft(x,y)){ }

else if(ableUp(x,y)){ //如果向上没有墙，则将上边格子压入栈 }

else if(ableDown(x,y)){ } else{ }

if(x == mazeSize - 1 && y == mazeSize -1){ //到达终点 }

else if(stackP.isEmpty()){ //未找到路径 }

stackP.Pop();

x = stackP.End().getX(); y = stackP.End().getY();

System.out.println(\); break; break; setBeen(x,y+2); y = y+2;

stackP.Push(x,y);

//如果向下没有墙，则将下边格子压入栈

setBeen(x,y-2); y = y-2;

stackP.Push(x,y); setBeen(x-2,y); x = x-2;

stackP.Push(x,y);

//如果向左没有墙，则将左边格子压入栈

setBeen(x+2,y); x = x+2;

stackP.Push(x,y);

}while(true);

return stackP;

哈尔滨工业大学课程设计报告

3.2.3 图形界面算法关键代码

public void paintComponent(Graphics g) { //画出迷宫和路径

}

super.paintComponent(g); Graphics2D g2 = (Graphics2D) g;

System.out.println(\为空？\+path.isEmpty());

Rectangle2D rect = new Rectangle2D.Double(RectleftX, RecttopY, RectWidth, g2.draw(rect); //画出迷宫边界

for(int i=1;i<=N-1;i=i+1){ //根据二维数组Maze画出迷宫 }

while(!path.isEmpty()){ }

//根据栈中内容画出路径

g2.draw(new Ellipse2D.Double(RectleftX + (path.End().getX()-1)*SIZE + path.Pop();

for(int j=1;j<=N-1;j=j+1){ }

if(isWall(Maze[i][j])){ }

if(i%2==0){ } else{ }

g2.draw(new Line2D.Double(RectleftX + SIZE*(i-1),

RecttopY +SIZE*(j),RectleftX + SIZE*(i+1), RecttopY +SIZE*(j)));

g2.draw(new Line2D.Double(RectleftX + SIZE*(i),

RecttopY +SIZE*(j-1),RectleftX + SIZE*(i),RecttopY + SIZE * (j+1)));

RectHeight);

SIZE/3 , RecttopY + (path.End().getY()-1)*SIZE + SIZE/3,2*SIZE/3, 2*SIZE/3));

3.3 主要功能界面

[按照主要功能分小节，自行增删。每个界面下需要有简短的文字说明] 3.3.1 XXX功能运行结果

主要截图及说明 3.3.2 XXX功能运行结果

主要截图及说明 3.3.3 XXX功能运行结果

主要截图及说明

12