2019-03-08 22:09:59 zj1131190425 阅读数 872
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    5081 人正在学习 去看看 佟刚

迷宫问题问题描述:

栈的实现在这篇博客中:https://blog.csdn.net/zj1131190425/article/details/87991662

迷宫是一个矩形区域,有一个出口和入口,迷宫内部包含不能穿越的墙壁和障碍物。

1.用矩阵来描述迷宫。入口是(0, 0), 出口是(m,n),现在需要在迷宫中选找一条路径,穿过迷宫。位置(i,j)=1表示有障碍。0表示无障碍。

思路:

1.出发点处,定义四个方向的坐标偏移量,搜索等四个方向,直到找到一个可行的方向,按照可行的方向移动到下一个位置,将前一个位置坐标压入栈中(保存路径),且将此位置设置为1(放置障碍物,防止往回退的时候又重新搜索这个方向)

2. 如果在某个位置没有找到可行的方向,则将当前这个位置设置为1(这个位置不可再回来),从栈顶弹出一个坐标,作为当前坐标(相当于走回头路),继续搜索其他的方向是否可行。

3. 如此往复

采用自顶向下设计的方法设计代码:

(1)输入迷宫

(2)寻找路径

(3)输出路径

#include <iostream>
#include "E:\back_up\code\c_plus_code\sparseMatrix\external_file\arraystack.h"
#include <string>
using namespace std;

// 迷宫
template<typename T>
void print_array(T a[][12])
{
	for(int i=0; i<12; i++)
	{
		for(int j=0; j<12; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}


class position    // 存储位置坐标 
{
	public:
	int row;
	int col;
	position()
	{
		row = 0;
		col = 0;
	}
	
	position(int row, int col)
	{
		this->row = row;
		this->col = col;
	}
	
	void add_offset(position& ps)
	{
		row += ps.row;
		col += ps.col;
	} 
}; 



void find_path(bool map[][12])
{
	int map_1[12][12];
	// 保存map()的一个副本
	for(int i=0; i<12; i++)
	{
		for(int j=0; j<12; j++)
		{
			map_1[i][j] = (int)map[i][j];
		}
	} 
	// 寻找迷宫的路径
	arrayStack<position> path; // 存储路径信息

	// 偏移量
	position offset[4];
	
	// 向右偏移  index=0 
	offset[0].row = 0;
	offset[0].col = 1; 
	// 向下偏移  index=1
	offset[1].row = 1;
	offset[1].col = 0;
	// 向左偏移   index=2
	offset[2].row = 0;
	offset[2].col = -1;
	// 向上偏移   index=3
	offset[3].row = -1;
	offset[3].col = 0; 	
	
	position current_position(1,1);   // 初始化当前位置
	int option = 0;  //初始化选的方向,右,下,左,上=(0,1,2,3)
	int max_otion = 3;   // 方向的选择范围
	
	map[1][1] = 1;   // 在(1,1)位置放置障碍 
	cout << "current position: " << current_position.row << "  " << current_position.col << endl;

	while(current_position.row!=10 || current_position.col!=10)
	{
		
		int r,c;
		while(option<=max_otion)
		{
			r = current_position.row + offset[option].row;
			c = current_position.col + offset[option].col;
			if(map[r][c]==0)   // 新的位置可行
			{
				break;
			} 
		    option++;
		}
		
		if(option<=max_otion)  // 找到了可行的方向
		{
			path.push(current_position); 
			//current_position.add_offset(offset[position]);    // current_position更新 
			
			current_position.row = r;    // 移动到新的位置 
			current_position.col = c;
			
			map[r][c] = 1;  // 放置障碍物  避免回退时又选到这个方向 
			option = 0; 
		} 
		
		else     // 选择的位置走不通 
		{
			if(path.empty())
	        {
        		cout << "The puzzle has no solution" << endl;
        		return;
        	}
        	
        	position next = path.top();
        	path.pop();
        	// 计算返回后的搜索方向:
			// 按照前面对方向的定义,返回后应该搜索未搜索过的两个方向:
			// map[currentRow][currentCol] = 1;  // 走不通的位置设置障碍,避免重复搜索 
			map[current_position.row][current_position.col] = 1;   // 当前的位置是死路 
			option = 0;
			current_position = next;   // 浅复制即可 这个类默认的拷贝构造函数 
		}
		cout << "(r,c)= " << r << "," << c << endl;
	}
	
	position tmp;
	while(!path.empty())
	{
		// cout << "revise the map" << endl;
	    tmp = path.top();
	    path.pop();
	    map_1[tmp.row][tmp.col] = 2;
	}
	
	// 结果输出 
	char result[12][12];
	for(int i=0; i<12; i++)
	{
		for(int j=0; j<12; j++)
		{
			if(map_1[i][j]==1)
			{
				result[i][j]='1';
			}
			else if(map_1[i][j]==0)
			{
				result[i][j]='0';
			}
			else
			{
				result[i][j]='*';
			}
		}
	}

	print_array(result); 	
    
	
}


int main(int argc, char *argv[])
{
    //int a[12][12];
    bool a[][12] = {
				     {1,1,1,1,1,1,1,1,1,1,1,1},
				     {1,0,1,1,1,1,1,0,0,0,0,1},
				     {1,0,0,0,0,0,1,0,1,0,0,1},
				     {1,0,0,0,1,0,1,0,0,0,0,1},
					 {1,0,1,0,1,0,1,0,1,1,0,1},
					 {1,0,1,0,1,0,1,0,1,0,0,1},
					 {1,0,1,1,1,0,1,0,1,0,1,1},
					 {1,0,1,0,0,0,1,0,1,0,1,1},
					 {1,0,1,0,1,1,1,0,1,0,0,1},
					 {1,1,0,0,0,0,0,0,1,0,0,1},
					 {1,0,0,0,0,1,1,1,1,0,0,1},
			 		 {1,1,1,1,1,1,1,1,1,1,1,1} 
			        };
    //print_array(a);
    find_path(a);
    return 0;
}

运行结果:

迷宫问题最短路径

可以使用队列来实现寻找最短路径的操作

首先介绍C++ 实现队列:关于队列的实现参考博客: https://blog.csdn.net/zj1131190425/article/details/88090905,下面的队列是对https://blog.csdn.net/zj1131190425/article/details/88090905中队列的改进,主要是改经了ensureCapacity()函数,因为原来的队列中ensureCapacity()函数有点小的bug.

定义一个队列的基类,queueABC

queueABC.h文件

#ifndef QUEUE_ABC_H
#define QUEUE_ABC_H

using namespace std;
// 定义抽象类
template<typename T>
class queueABC
{
	public:
	// virtual ~queue();
	virtual bool empty() const=0;  // 纯虚函数 只读
	virtual int size() const=0;    // 返回队列中元素的个数   
	virtual T& front() = 0;        // 返回队首元素
	virtual T& back() = 0;         // 返回队尾元素
	virtual void pop() = 0;        // 删除队首的元素
	virtual void push(T x) = 0;    // 队尾插入元素 
};
#endif

queue.h

#ifndef QUEUE_H
#define QUEUE_H

#include <iostream>
#include <algorithm>
#include "E:\back_up\code\c_plus_code\dequeue\external_file\queueABC.h"   // 包含ABC文件 
#include "E:\back_up\code\c_plus_code\dequeue\external_file\queueemptyEx.h"   // 包含异常类文件 
using namespace std;

template<typename T>
class queue : public queueABC<T>
{
	private:
	int arrayLength;  // 数组的长度
	int queueSize;   // 队列中元素的个数
	int queueFront;   // 队首元素所在的位置
	int queueBack;    // 队尾元素所在的位置
	T* element; 
	void ensureArrayLength();   // 进行数组扩容 
	
	public:
	queue(int arrayLength=10);    // 构造函数 
	~queue();                     // 析构函数 
	queue(const queue& q);        // 拷贝构造函数 
	
	// ADT 
	bool empty() const;
	int size() const;
	T& front();
	T& back();
	void pop();
	void push(T x);
	void display_queue() const;   // 打印输出队列中的元素 
	
};

template<typename T>
queue<T>::queue(int arrayLength)
{
		this->arrayLength = arrayLength;
		this->queueSize = 0;
		this->queueFront = 0;
		this->queueBack = 0;
		element = new T[arrayLength];
}

template<typename T>
queue<T>::~queue()
{
	delete [] element;
} 

template<typename T>
queue<T>::queue(const queue& q)
{
	arrayLength = q.arrayLength;
	queueSize = q.queueSize;
	queueFront = q.queueFront;
	queueBack = q.queueBack;
	element = new T[arrayLength];
	for(int i=0; i<queueSize; i++)
	{
		element[i] = q.element[i];
	}
} 

template<typename T>
bool queue<T>::empty() const
{
	return queueSize==0;
} 

template<typename T>
int queue<T>::size() const
{
	return queueSize;
}

template<typename T>
T& queue<T>::front()
{
	return element[(queueFront+1)%arrayLength];  // queueFront是队首元素的前一个位置,+1是表示队首元素的位置 
}

template<typename T>
T& queue<T>::back()
{
	return element[queueBack%arrayLength];    // queueback队尾元素的位置 
}

/*
template<typename T>
void queue<T>::ensureArrayLength()
{
	// 如果需要,增加数组长度 
	if((queueBack+1)%arrayLength==queueFront)   // 环形的数组 
	{
		T* old;
		old = element;
		//delete element;
		// arrayLength = arrayLength*2;   // 增加分配的内存长度 
		element = new T[2*arrayLength]; 
		// 环形数组重新布局
		// 先将数组复制过来
		//更新关于数组复制
		int index_tmp;
	    for(int i=0; i<queueSize; i++)
	    {
    		index_tmp = (queueFront+1+i)%arrayLength;
    		element[index_tmp] = old[index_tmp];
    	}
		 
		delete old;
		// 重新布局  // 分为三种情况:1.queuefront=0; queuefront==arrayLength-1; else;
		int pre_start = queueFront%arrayLength;  // 队列首元素的前一个位置 
		if(pre_start==0)
		{
			// 移动所有的数组元素 
			for(int i=0; i<queueSize; i++)
			{
				element[2*arrayLength-1-i] = element[(queueBack%arrayLength)-i];
			} 
			queueFront = queueFront + arrayLength;
			queueBack = queueBack + arrayLength;
		} 
		else if(pre_start==arrayLength-1)   // arrayLength还是原来的值 
		{
			// 不用移动数组元素,之更改front 
			queueFront = queueFront + arrayLength; 
		}
		else
		{
			// 移动第二段的元素:
			int element_to_move = arrayLength-1-(queueFront%arrayLength);  // 计算第二段需要移动的元素的数量 
			for(int i=0; i<element_to_move; i++)
			{
				element[2*arrayLength-1-i] = element[queueBack%arrayLength-i];
			} 
			queueFront = queueFront + arrayLength;
		}
		arrayLength = arrayLength*2;   // 更新arrayLength 		 
	}
	// 添加一个动态减少内存的函数 
}
*/

template<typename T>
void queue<T>::ensureArrayLength()
{
	if((queueBack+1)%arrayLength==queueFront)   // 环形的数组 
	{
		T* new_element = new T[2*arrayLength];
		int start = (queueFront+1)%arrayLength;
		if(start<2)   // 没有形成环
		{
			copy(element+start, element+start+arrayLength-1, new_element);    // 复制操作 
		} 
		else   // 形成环
		{
			copy(element+start, element+arrayLength, new_element);
			copy(element, element+queueBack+1, new_element+arrayLength-start);
		} 
		queueFront = 2*arrayLength-1;
		queueBack = arrayLength-2;
		arrayLength *= 2;
		delete[] element;
		element = new_element;
	}
}

// push()操作:
template<typename T>
void queue<T>::push(T x)
{
	ensureArrayLength();     // 先保证数组长度满足条件
	queueSize++;
	//queueBack = (queueBack+1)%arrayLength;
	//element[queueBack] = x;	 
	queueBack++;
	element[queueBack%arrayLength] = x;
} 

//pop()操作 
template<typename T>
void queue<T>::pop()
{
	if(empty())
        throw queueEmptyException(0); 
	queueFront++;
	queueSize--;
	// element[queueFront].~T;
} 

template<typename T>
void queue<T>::display_queue() const
{
	//int tmp = queueFront;
	// int start_pos = (tmp+1)%arrayLength;
	if(empty())
	{
		cout << "The queue is empty!" << endl;
		return;
	}
	
	for(int i=0; i<queueSize; i++)
	{
		cout << element[(queueFront+1+i)%arrayLength] << " ";
	}
	cout << endl;
}

#endif 

自定义的异常类:

queueemptyException:

// 自定义异常类
#ifndef QUEUE_EMPTY_EXCEPTION
#define QUEUE_EMPTY_EXCEPTION
#include <stdexcept>
#include <iostream>
using namespace std;

class queueEmptyException : public runtime_error
{
	private:
	int queueSize;
	
	public:
	queueEmptyException(int queueSize) : runtime_error("The queue empty!")
	{
		this->queueSize = queueSize;
	}
	
	void display_error_info()
	{
		cout << "The queue size is " << queueSize << endl;
	}
};
#endif

寻找最短路径的算法思路:

从上面的迷宫中,找一条从入口到出口的最短路径,要有两个过程:

1. 一个是距离标记过程

2. 另一个是路径标记过程

在距离标记过程中,把能从入口到达的相邻位置标记为1,然后把从编号为1可到达的相邻位置标记为2(表示与入口相距为2),直到到达出口或者没有可标记的相邻位置为止。

在路径标记过程中,从出口开始,首先移动到比出口的编号小1的位置,再从当前位置移动到比其编号小1的位置上,直到到达起点为止,这便是最短的路径

3.按照上述思路编写代码实现:

main.cpp

#include <iostream>
#include "E:\back_up\code\c_plus_code\dequeue\external_file\queue.h"
using namespace std;

// 迷宫
template<typename T>
void print_array(T **a, int size)
{
	for(int i=0; i<size; i++)
	{
		for(int j=0; j<size; j++)
		{
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl;
}


class position    // 存储位置坐标 
{
	public:
	int row;
	int col;
	position()
	{
		row = 0;
		col = 0;
	}
	
	position(int row, int col)
	{
		this->row = row;
		this->col = col;
	}
	
	/*
	void add_offset(position& ps)
	{
		row += ps.row;
		col += ps.col;
	}
	*/
	 
}; 


void findPath(int** map, int mapSize=10)
{
	// 这里默认起始点为(0,0),终点为(9,9)
	
	// 给地图添加围墙:
	int** new_map = new int*[mapSize+2];
	for(int i=0; i<mapSize+2; i++)
	{
		new_map[i] = new int[mapSize+2];
	} 
	for(int i=0; i<mapSize+2; i++)
	{
		for(int j=0; j<mapSize+2; j++)
		{	
			if(i==0 || i==mapSize+2-1)
			{
				new_map[i][j] = 1;  // 增加行围墙 
			}
			else if(j==0 || j==mapSize+2-1)   //增加列围墙 
			{
				new_map[i][j] = 1;
			}
			else  // 保存地图 
			{
				new_map[i][j] = map[i-1][j-1]; 
			} 
			
		}
	}
	
	// print_array(map, mapSize);
	cout << "原始地图: " << endl;
	print_array(new_map, mapSize+2);
	
	// 初始化偏移量
	position offset[4];
	// 向右偏移  index=0 
	offset[0].row = 0;
	offset[0].col = 1; 
	// 向下偏移  index=1
	offset[1].row = 1;
	offset[1].col = 0;
	// 向左偏移   index=2
	offset[2].row = 0;
	offset[2].col = -1;
	// 向上偏移   index=3
	offset[3].row = -1;
	offset[3].col = 0; 	
	
	position current_position(1,1);   // 初始化当前位置
	position end_position(10,10);
	new_map[current_position.row][current_position.col] = 2;  // 这里距离标记从2开始,实际距离等于标号-2
	int direction_number = 4;   // 一个方格相邻位置的个数 
	position neighbor;
	queue<position> q;    // 队列,用于存放标记的位置 
	while(true)
	{
		// 给相邻位置做标记
		for(int i=0; i<direction_number; i++)
		{
			neighbor.row = current_position.row + offset[i].row;
			neighbor.col = current_position.col + offset[i].col;
			if(new_map[neighbor.row][neighbor.col]==0)  // 可标记的位置
			{
				new_map[neighbor.row][neighbor.col] = new_map[current_position.row][current_position.col]+1; // 标记 
				if(neighbor.row==end_position.row && neighbor.col==end_position.col)
				{
					break;   // 标记完成 
				} 
				q.push(neighbor); 
			} 
		}
		if(neighbor.row==end_position.row && neighbor.col==end_position.col)
		{
			break;   // 到达 
		}
		
		if(q.empty())    // 迷宫无解; 
		{
			cout << "The puzzle has no solution" << endl;
			return;
		}
		
		current_position = q.front();
		q.pop(); 
	}
	//cout << "标记完的矩阵: " << endl; 
	//print_array(new_map, 12); 
	
	// 构造路径;
	int pathLength = new_map[end_position.row][end_position.col]-2;  // 路径的长短 
    // position* path = new position[pathLength];
	
	queue<position> q_path;   // 存储路径 
	current_position =  end_position;   // 从终点回溯
	for(int i=pathLength-1; i>=0; i--)
	{
		// path[i] = current_position;   
		q_path.push(current_position);    // 当前的位置放入队列中 
		for(int j=0; j<direction_number; j++)
		{
			neighbor.row = current_position.row + offset[j].row;
			neighbor.col = current_position.col + offset[j].col;
			if(new_map[neighbor.row][neighbor.col] == i+2)
			{
				break;
			}
		} 
		//测试 
		// cout << "current position: " << current_position.row << ',' << current_position.col << endl;
		current_position = neighbor;	
	} 
	
	/*    测试代码 
	position tmp; 
	while(!q_path.empty())
	{
		tmp = q_path.front();
		cout << "path: " << tmp.row << "," << tmp.col << endl;
		q_path.pop();
	}
	*/
	
	/*   测试代码 
	for(int i=0; i<pathLength; i++)
	{
		cout << "path: " << path[i].row << "," << path[i].row << endl;
	}
	*/
	
	
	
	// 输出结果 
	char** result = new char*[mapSize+2];    // 创建一个新的矩阵保存可视化结果 
	for(int i=0; i<mapSize+2; i++)
	{
		result[i] = new char[mapSize+2];
	}
	// 初始化:
	position tmp;
	while(!q_path.empty())
	{
		tmp = q_path.front();
		result[tmp.row][tmp.col] = '*';
		q_path.pop();
	} 
	
	for(int i=0; i<mapSize+2; i++)
	{
		for(int j=0; j<mapSize+2; j++)
		{
			if(result[i][j] != '*' && new_map[i][j]==1)
			{
				result[i][j] = '1';
			}
			if(result[i][j] != '*' && (new_map[i][j]==0 || new_map[i][j]>1))
			{
				result[i][j] = '0';
			}
		}
	}	
	
	// 输出迷宫路径
	cout << "最短路径: " << pathLength << endl; 
	cout << "迷宫路径如下所示: " << endl;
	print_array(result, mapSize+2); 
	
} 



int main(int argc, char *argv[])
{	
    int map_size = 10;
    int input_map[10][10] = {
   	                   {0,1,1,1,1,1,0,0,0,0},
   	                   {0,0,0,0,0,1,0,1,0,0},
					   {0,0,0,1,0,1,0,0,0,0},
					   {0,1,0,1,0,1,0,1,1,0},
					   {0,1,0,1,0,1,0,0,0,0},
					   {0,1,0,0,0,1,0,1,0,1},
					   {0,1,0,0,0,1,0,1,0,1},
					   {1,0,0,0,0,0,0,1,0,0},
					   {0,0,0,0,1,1,1,1,0,0} 
                      };
    // 数据转换 
	int** map_in = new int*[map_size];
	for(int i=0; i<map_size; i++)
	{
		map_in[i] = new int[map_size];
	}
	for(int i=0; i<map_size; i++)
	{
		for(int j=0; j<map_size; j++)
		{
			map_in[i][j] = input_map[i][j];
		}
	}
	
	// 将原始地图转换为指针的形式
	findPath(map_in, map_size);    
	return 0;
}

算法的运行结果如下图所示:

---------------------------------------------------end----------------------------------------------------------

2017-07-10 20:21:16 u012734723 阅读数 2567
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    5081 人正在学习 去看看 佟刚

1.走迷宫算法思想
走迷宫有很多种实现方式,包括:
(1)递归:
a.创建一个存储通路结点的栈Stack。
b.从矩阵的第一个结点(0,0)开始,将(0,0)结点压入栈中,顺时针从右->下->左->上寻找通路结点(这里我的设计是值为1的就是通路,值为0的就不是通路,这里的通路结点是要在通向目的结点那条道上的结点),将每个通路结点压入栈中,直到找到的通路结点是目的结点。
c.设置一个判断是否已经访问过的数组boolean visited[][],如果结点已经访问过,将数组中对应位置的值设置为true。
d.对于通路结点的选择,要判断是否在边界内,以及是否曾经压入栈中,也就是是否曾经访问过。
(2)深度优先搜索遍历
(3)广度优先搜索遍历
2.算法代码实现

/**
 * @description 迷宫结点
 * @author liuffei
 * @date 2017-07
 */
public class MazeNode {

    private int row;//结点行数
    private int col;//结点列数

    public MazeNode(int row,int col){
        this.row = row;
        this.col = col;
    }

    public int getRow() {
        return row;
    }

    public void setRow(int row) {
        this.row = row;
    }

    public int getCol() {
        return col;
    }

    public void setCol(int col) {
        this.col = col;
    }
}
import java.util.Stack;

/**
 * @description 寻找迷宫的出路
 * @author liuffei
 * @date 2017-06-16 
 */
public class MazeRoute {

    //创建存储路过结点的栈
    public Stack<MazeNode> stack = new Stack<MazeNode>();

    //maze中的结点为1表示是通路,0表示不是通路
    public  Stack findRoute(int[][] maze){
        MazeNode beginNode = new MazeNode(0,0);//进入结点
        stack.push(beginNode);
        //对于一个结点,从它的右-下-左-上顺时针进行遍历。判断当前节点的邻结点是否为通路,如果是的话,就压入栈中,继续寻找下一个通路。
        int x = maze.length;//迷宫矩阵的行数
        int y = maze[0].length;//迷宫矩阵的列数
        int i = 0,j = 0;//i,j表示当前移动的位置
        boolean visited[][] = new boolean[x][y];//标志结点是否有访问过
        visited[0][0] = true;
        while(i < x - 1 || j < y - 1){
            MazeNode nextNode = getNext(beginNode,maze,visited);
            if(nextNode.getRow() != beginNode.getRow() || nextNode.getCol() != beginNode.getCol()){
                stack.push(nextNode);
                beginNode = nextNode;
            }
            i = nextNode.getRow();
            j = nextNode.getCol();
        }
        return stack;
    }

    //寻找当前结点的下一个通路 current表示当前结点
    public  MazeNode getNext(MazeNode current,int[][] maze,boolean visited[][]){
        //表示下一个通路结点
        MazeNode next = null;
        int x = maze.length;//迷宫矩阵的行数
        int y = maze[0].length;//迷宫矩阵的列数
        //当前结点current的上下左右结点中一定有一个结点是isWalk = true的。如果其他位置的三个结点都不是通路,则回到这个结点。
        //current所在位置
        int col = current.getCol();
        int row= current.getRow();
        //栈顶元素
        MazeNode top = stack.peek();
        //判断当前结点的右结点(row,col+1)是否是通路,
        if(col + 1 < y && maze[row][col+1] == 1 && !visited[row][col+1]){
            next = new MazeNode(row,col+1);
            visited[row][col+1]  = true;
        }else{
            //如果右节点不是通路,寻找下结点 
            if(row + 1 < x && maze[row+1][col] == 1 && !visited[row+1][col]){
                next = new MazeNode(row+1,col);
                visited[row+1][col]  = true;
            }else{
                //如果下节点不是通路,寻找左结点 
                if(col - 1 >= 0 && maze[row][col-1] == 1 && !visited[row][col-1]){
                    next = new MazeNode(row,col-1);
                    visited[row][col-1]  = true;
                }else{
                    //如果左结点不是通路,寻找上结点
                    if(row - 1 >= 0 && maze[row-1][col] == 1  && !visited[row-1][col]){
                        next = new MazeNode(row-1,col);
                        visited[row-1][col]  = true;
                    }else{
                        //如果上结点都不是通路,就回到栈的栈顶位置。
                        next = top;
                    }
                }
            }

        }
        return next;
    }

}
import java.util.Stack;

/**
 * 走迷宫算法测试
 * @author liuffei
 * @date 2017年7月10日
 * @description
 */
public class MazeMain {

    public static void main(String[] args) {

        int maze[][] = {
                {1,0,1,0,0,1,0},
                {1,0,0,0,1,0,1},
                {1,0,1,1,1,0,0},
                {1,1,1,0,1,1,1},
                {0,1,0,0,1,0,1},
                {0,0,0,0,0,0,1}
        };

        MazeRoute mazeRoute = new MazeRoute();
        Stack stack = mazeRoute.findRoute(maze);
        while(!stack.isEmpty()){
            MazeNode node = (MazeNode) stack.pop();
            System.out.println("("+node.getRow()+","+node.getCol()+")");
        }
    }

}

3.效果展示
这里写图片描述

2018-06-11 12:59:24 Shuffle_L 阅读数 636
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    5081 人正在学习 去看看 佟刚

问题描述:

设计一个能自动求解给定二维迷宫最短路径问题的程序,并输出所有的求解得到的最短路径和路径长度。


技术方案:

二维迷宫最短路径问题
为了表示迷宫,定义一个二维数组mg,其中的每个元素表示一个方块的状态,1表示墙壁,0表示通路。出于算法实现方便考虑,在迷宫周围建立了一道围墙,内部是8*8的迷宫地图,可以自由编辑,规定迷宫的入口为(1,1),迷宫的出口为(8,8)。
求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走;否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。
为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。
对于迷宫中的每个方块,有上下左右四个方块相邻,第i行第j列的当前方块的位置为(i,j),规定上方方块为方位0,顺时针方向递增编号。在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。
为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中。
求解迷宫(1,1)到(M,N)路径的具体过程是:
先将入口进栈(初始方位设置为-1),在栈不空时循环:取栈顶方块(不退栈),若该方块是出口,则输出栈中方块即为路径。
否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈。若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈(初始方位设置为-1)。

为了保证试探的可走相邻方块不是已走路径上的方块,如(i,j)已进栈,在试探(i+1,j)的下一可走方块时,又试探到(i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的mg数组元素值改为-1(变为不可走的相邻方块),当退栈时(表示没有可走相邻方块),将其恢复为0。


/**************************************
Exp_2:二维迷宫问题
Author:Shawn__L
Date:2018.5.27
**************************************/
#include "stdafx.h"
#include <stdio.h>
#define M 8					//行数
#define N 8					//列数
#define MaxSize 100			//栈最多元素个数

struct 
{
	int i,j;
	int di;
} Stack[MaxSize],Path[MaxSize];		//定义栈和存放最短路径的数组
int top=-1;									//栈顶指针
int count=1;							  //路径数计数
int minlen=MaxSize;					//最短路径长度
int m,n;
int mg[M+2][N+2];			//迷宫的四周为1的墙壁

void init()					//建立迷宫
{
	for(m=0;m<M+2;m++)			//建立迷宫四周墙壁
	{
		mg[0][m]=1;
		mg[M+1][m]=1;
		mg[m][0]=1;
		mg[m][N+1]=1;
	}
	printf("提示:\n这是一个8*8的迷宫,四周墙壁已经建好,只需要输入迷宫的内部地图,1表示墙壁,0表示通路。\n");
	printf("迷宫的入口为(1,1),迷宫的出口为(8,8),每个数字以空格分开,每一行输入8个数字后按回车键结束。\n");
	for(m=1;m<=M;m++)
	{
		printf("\n请输入第%d行地图:",m);
		for(n=1;n<=N;n++)
		{
			scanf("%d",&mg[m][n]);
		}
	}
	printf("\n迷宫如下:");
	for(m=0;m<M+2;m++)
	{
		printf("\n");
		for(n=0;n<N+2;n++)
		{
			printf("%d ",mg[m][n]);
		}
	}
}

void mgpath(int xi,int yi,int xe,int ye)		//求迷宫路径
{
	int i,j,di,find,k;
	top++;							//进栈
	Stack[top].i=xi;
	Stack[top].j=yi;
	Stack[top].di=-1;
	mg[xi][yi]=-1;					//初始方块进栈
	while (top>-1)					//栈不空时循环
	{
		i=Stack[top].i;
		j=Stack[top].j;
		di=Stack[top].di;
		if (i==xe && j==ye)			//找到了出口,输出路径
		{ 
			printf("%d:  ",count++);
			for (k=0;k<=top;k++)
			{
				printf("(%d,%d)  ",Stack[k].i,Stack[k].j);
				if ((k+1)%12==0)
					printf("\n    ");			//输出时每12个方块换一行
			}
			printf("\n");
			if (top+1<minlen)						//比较找最短路径
			{
				for (k=0;k<=top;k++)
					Path[k]=Stack[k];
				minlen=top+1;
			}
			mg[Stack[top].i][Stack[top].j]=0;		//让该位置变为其他路径可走方块
			top--; 
			i=Stack[top].i;
			j=Stack[top].j;
			di=Stack[top].di;
		}
		find=0;
		while (di<4 && find==0)		//找下一个可走方块
		{	
			di++;
			switch(di)
			{
			case 0:
				i=Stack[top].i-1;
				j=Stack[top].j;
				break;
			case 1:
				i=Stack[top].i;
				j=Stack[top].j+1;
				break;
			case 2:
				i=Stack[top].i+1;
				j=Stack[top].j;
				break;
			case 3:
				i=Stack[top].i;
				j=Stack[top].j-1;
				break;
			}
			if (mg[i][j]==0) 
				find=1;
		}
		if (find==1)				//找到了下一个可走方块
		{	
			Stack[top].di=di;		//修改原栈顶元素的di值
			top++;
			Stack[top].i=i;
			Stack[top].j=j;
			Stack[top].di=-1;	//下一个可走方块进栈
			mg[i][j]=-1;			//避免重复走到该方块
		}
		else						//没有路径可走,则退栈
		{
			mg[Stack[top].i][Stack[top].j]=0;    //让该位置变为其他路径可走方块
			top--;
		}
	}
	printf("\n最短路径长度:%d\n",minlen);
	printf("最短路径:");
	for (k=0;k<minlen;k++)
	{
		printf("(%d,%d)  ",Path[k].i,Path[k].j);
		if ((k+1)%12==0)
			printf("\n\t  ");		//输出时每12个方块换一行
	}
	printf("\n");
}
void main()
{
	init();
	printf("\n\n迷宫所有路径如下:\n");
	mgpath(1,1,M,N);
}
2019-03-07 10:29:33 weixin_41913008 阅读数 50
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    5081 人正在学习 去看看 佟刚

栈和队列都可以使用顺序表实现,为了节约时间我们使用python里的list实现。

class Stack(object):
    """栈"""
    def __init__(self):
         self.items = []

    def is_empty(self):
        """判断是否为空"""
        return self.items == []

    def push(self, item):
        """加入元素"""
        self.items.append(item)

    def pop(self):
        """弹出元素"""
        return self.items.pop()

    def peek(self):
        """返回栈顶元素"""
        return self.items[len(self.items)-1]

    def size(self):
        """返回栈的大小"""
        return len(self.items)

if __name__ == "__main__":
    stack = Stack()
    stack.push("hello")
    stack.push("world")
    stack.push("itcast")
    print stack.size()
    print stack.peek()
    print stack.pop()
    print stack.pop()
    print stack.pop()

队列

class Queue(object):
    """队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.items == []

    def enqueue(self, item):
        """进队列"""
        self.items.insert(0,item)

    def dequeue(self):
        """出队列"""
        return self.items.pop()

    def size(self):
        """返回大小"""
        return len(self.items)

if __name__ == "__main__":
    q = Queue()
    q.enqueue("hello")
    q.enqueue("world")
    q.enqueue("itcast")
    print q.size()
    print q.dequeue()
    print q.dequeue()
    print q.dequeue()

双端队列

class Deque(object):
    """双端队列"""
    def __init__(self):
        self.items = []

    def is_empty(self):
        """判断队列是否为空"""
        return self.items == []

    def add_front(self, item):
        """在队头添加元素"""
        self.items.insert(0,item)

    def add_rear(self, item):
        """在队尾添加元素"""
        self.items.append(item)

    def remove_front(self):
        """从队头删除元素"""
        return self.items.pop(0)

    def remove_rear(self):
        """从队尾删除元素"""
        return self.items.pop()

    def size(self):
        """返回队列大小"""
        return len(self.items)


if __name__ == "__main__":
    deque = Deque()
    deque.add_front(1)
    deque.add_front(2)
    deque.add_rear(3)
    deque.add_rear(4)
    print deque.size()
    print deque.remove_front()
    print deque.remove_front()
    print deque.remove_rear()
    print deque.remove_rear()
2016-11-07 09:39:17 qq_19995883 阅读数 625
  • 图解Java数据结构算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    5081 人正在学习 去看看 佟刚

#include <iostream>

using namespace std;

 

const int maxnum = 100;

 

typedef struct Datastack

{

int num;

int x, y;

struct Datastack  * pre, * next;

}datastack;

 

datastack *Create_stack();

 

datastack *push_stack(datastack *p, int x1, int y1); //进栈

 

datastack *pop_stack(datastack *p);                 //出栈

 

bool Isempty_stack(datastack *p);                   //判栈空

 

bool Isfull_stack(datastack *p);                    //判栈满

 

bool IsExit(datastack *p);                          //判是否已达出口

 

datastack *judge_kernel(datastack *p, int s[12][12]);      //评判核心

 

int main()

{

datastack *head = NULL;                         //栈头指针  

cout << "Create_stack() 正在创建栈区域... ";

head = Create_stack();

if (head != NULL)

{

cout << "创建栈区域成功!\n";

}

else

{

cout << "创建栈区域失败!\n";

return 0;

}

int M[12][12] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

              1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1,   //起始点为(1,1)

              1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1,

              1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1,

              1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1,

              1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1,

              1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1,

              1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1,

              1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1,

              1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1,

              1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 1,   //终止点为(10,10)

              1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1

};

//打印起始迷宫图

cout << "The Enter is at (1,1):\n";

for (int i = 0; i < 12; i++)

{

if (i == 1)

{

cout << "Enter-->";

}

else

{

cout << "        ";

}

for (int j = 0; j < 12; j++)

{

if (j == 11)

{

cout << M[i][j];

}

else

{

cout << M[i][j] << " ";

}

}

if (i == 10){ cout << "-->Exit"; }

cout << endl;

}

head = judge_kernel(head, M);  //开始评判

if (Isempty_stack(head))

{

cout << "No Path!No Gate!\n";      //不存在这样的路径

}

else

{

cout << "Path: ";           //打印出路径

datastack *head2 = head->pre;

for (int a = 0; a <( head->num)/5+1; a++)

{

if (a >= 1)

{

cout << "      ";

}

for (int b = 0; b < 5; b++)

{

cout << "maze[" << head2->x << "][" << head2->y << "],";

if (head2->next == NULL){ break; }

head2 = head2->next;

}

cout << endl;

//if (head2->next == NULL){ break; }

}

cout << "Path Length: " << head->num << endl;           //打印路径长度

head2 = NULL;

cout << "One Path: \n";           //打印出路径

//打印带路径的迷宫图

for (int i = 0; i < 12; i++)

{

if (i == 1)

{

cout << "Enter-->";

}

else

{

cout << "        ";

}

for (int j = 0; j < 12; j++)

{

if (M[i][j] == 0 || M[i][j] == 1)

{

if (i == 10 && j == 11)

{

cout << M[i][j];

}

else

{

cout << M[i][j] << " ";

}

}

else if (M[i][j]==2)

{

cout << "0"<<" ";

}

else if (M[i][j] == 3)

{

cout <<"x"<< " ";

}

}

if (i == 10){ cout << "-->Exit"; }

cout << endl;

}

}

while (!Isempty_stack(head))

{

head = pop_stack(head); //清空栈,回收空间

}

free(head);

return 0;

}

 

//核心评判

datastack *judge_kernel(datastack *p, int s[12][12])

{

p = push_stack(p, 1, 1);                  //起始点坐标进栈

s[((p->next)->x)][((p->next)->y)] = 3;    //表示元素在栈中,只能进行退栈操作

while (!Isempty_stack(p))

{

if (IsExit(p)){ break; }              //是否已找到出口点

 

    if (s[((p->next)->x)][((p->next)->y) + 1] == 0)

{

s[((p->next)->x)][((p->next)->y) + 1] = 3;

p = push_stack(p, ((p->next)->x), ((p->next)->y) + 1); //向右移动

 

}

else if (s[((p->next)->x) + 1][((p->next)->y)] == 0)

{

s[((p->next)->x) + 1][((p->next)->y)] = 3;

p = push_stack(p, ((p->next)->x) + 1, ((p->next)->y)); //向下移动

 

}

else if (s[((p->next)->x) - 1][((p->next)->y)] == 0)

{

s[((p->next)->x) - 1][((p->next)->y)] = 3;

p = push_stack(p, ((p->next)->x) - 1, ((p->next)->y)); //向上移动

 

}

else if (s[((p->next)->x) - 1][((p->next)->y) + 1] == 0)

{

s[((p->next)->x) - 1][((p->next)->y) + 1] = 3;

p = push_stack(p, ((p->next)->x) - 1, ((p->next)->y) + 1); //向右上角移动

 

}

else if (s[((p->next)->x) + 1][((p->next)->y) + 1] == 0)

{

s[((p->next)->x) + 1][((p->next)->y) + 1] = 3;

p = push_stack(p, ((p->next)->x) + 1, ((p->next)->y) + 1); //向右下角移动

 

}

else if (s[((p->next)->x) + 1][((p->next)->y) - 1] == 0)

{

s[((p->next)->x) + 1][((p->next)->y) - 1] = 3;

p = push_stack(p, ((p->next)->x) + 1, ((p->next)->y) - 1); //向左下角移动

 

}

else if (s[((p->next)->x)][((p->next)->y) - 1] == 0)

{

s[((p->next)->x)][((p->next)->y) - 1] = 3;

p = push_stack(p, ((p->next)->x), ((p->next)->y) - 1); //向左移动

 

}

else if (s[((p->next)->x) - 1][((p->next)->y) - 1] == 0)

{

s[((p->next)->x) - 1][((p->next)->y) - 1] = 3;           

p = push_stack(p, ((p->next)->x) - 1, ((p->next)->y) - 1); //向左上角移动

}

else

{

s[((p->next)->x)][((p->next)->y)] = 2;     //标记退栈元素

p = pop_stack(p);  //退栈

}

}

return p;

}

 

//创建栈

datastack *Create_stack()         

{

datastack *p = NULL;

datastack *s = NULL;

s = (datastack *)malloc(sizeof(datastack));     //仅创建栈计数节点

s->pre = NULL;

s->num = 0;

s->next = NULL;

p = s;

return  p;

}

 

//进栈

datastack *push_stack(datastack *p, int x1, int y1)

{

datastack  *s = NULL;

if (Isfull_stack(p))     //判栈满

{

cout << "栈已满,入栈操作失败!\n";

return p;

}

if (p->num == 0)

{

s = (datastack *)malloc(sizeof(datastack));  //新节点空间

s->pre = p;

s->x = x1;

s->y = y1;

s->next = NULL;

p->pre = s;     //方便后续打印路径数组

p->next = s;

p->num++;

}

else

{

s = (datastack *)malloc(sizeof(datastack));  //新节点空间

s->pre = p->next;

s->x = x1;

s->y = y1;

s->next = NULL;

(p->next)->next = s;

p->next = s;

p->num++;

}

return p;

}

 

//出栈

datastack *pop_stack(datastack *p)

{

datastack *pfree = NULL;

if (Isempty_stack(p))     //判栈空

{

cout << "栈已空,出栈操作失败!\n";

return p;

}

pfree = p->next;

p->next = pfree->pre;

(p->next)->next = NULL;

pfree->pre = NULL;

if (p->pre == pfree){ p->pre = NULL; }

free(pfree);

p->num--;

return p;

}

 

//判是否已达出口点

bool IsExit(datastack *p)

{

if (Isempty_stack(p))     //判栈空

{

cout << "栈已空,没有到达出口点!\n";

return false;

}

if ((p->next)->x == 10 && (p->next)->y == 10)

{

return true;  //已到达出口点

}

return false;

}

 

//判栈满

bool Isfull_stack(datastack *p)

{

if (p->num == maxnum)

{

return true;

}

return false;

}

 

//判栈空

bool Isempty_stack(datastack *p)

{

if (p->num == 0)

{

return true;

}

return false;

}

 

 

 

 

没有更多推荐了,返回首页