八数码问题数字华容道，九宫格深度搜索DFS广度搜索BFS和A*算法C++源码

本C++代码解决了八数码问题，采用深度优先，广度优先和A*算法实现，基于visual studio 2017

/******************************************************************************
* 使用深度优先、广度优先和A*算法解决九宫问题
******************************************************************************/

#include
#include
#include
#include
using namespace std;


#include“data.h“
#include“queue.h“
#include“stack.h“
#include“link.h“


#define DEEPSEARCH    1    
#define WIDESEARCH    2    
#define ASTART    3        

#define SEARCHTYPE WIDESEARCH   //定义使用广度优先


//#define SHOWPROCESS    //定义是否显示中间过程



class SearchTree {
private:
	/***********************定义open表的数据类型************************/
#if SEARCHTYPE==WIDESEARCH
	Queue open;
#elif SEARCHTYPE==DEEPSEARCH
	Stack open;
#else    
	link open;
#endif


	Stack close;
public:
	void init（）;    //初始化数据
	void extend（）;       //扩展close表尾节点并添加进open表
	void moveToClose（）;    //将open表的头节点移动到close表中
	bool success（）;        //判断搜索是否成功
	bool openEmpty（）;    //判断open表是否为空
	void showAnswer（）;    //显示最终结果
};

void SearchTree::showAnswer（） {
	close.show（）;
}

bool SearchTree::openEmpty（） {
	return open.empty（）;
}


void SearchTree::extend（） {
	DATATYPE temp[LINE][ROW] buf[LINE][ROW];
	Data *pid;
	int n m;
	pid = close.getTop（*buf）;    //将close表的最后一项记录复制到buf中
	for （n = 0; n		for （m = 0; m			if （buf[n][m] == 0）//寻找buf中0所在的位置，0表示空格
				goto L1;
L1:


	memcpy（temp buf DATASIZE * sizeof（DATATYPE））;
	if （n != 0） {    //空格上移
		temp[n][m] = temp[n - 1][m];
		temp[n - 1][m] = 0;
		if （close.exist（*temp） == false） open.push（*temp &pid）;
#ifdef SHOWPROCESS    //宏定义，决定时候输出中间过程
		cout << “move below data to open table:“ << endl;
		showElement（*temp）;
		getchar（）;
#endif
	}



	memcpy（temp buf DATASIZE * sizeof（DATATYPE））;
	if （n != 2） {    //空格下移
		temp[n][m] = temp[n + 1][m];
		temp[n + 1][m] = 0;
		if （close.exist（*temp） == false） open.push（*temp &pid）;
#ifdef SHOWPROCESS
		cout << “move below data to open table:“ << endl;
		showElement（*temp）;
		getchar（）;
#endif
	}

	memcpy（temp buf DATASIZE * sizeof（DATATYPE））;
	if （m != 0） {    //空格左移
		temp[n][m] = temp[n][m - 1];
		temp[n][m - 1] = 0;
		if （close.exist（*temp） == false） open.push（*temp &pid）;
#ifdef SHOWPROCESS
		cout << “move below data to open table:“ << endl;
		showElement（*temp）;
		getchar（）;
#endif
	}


	memcpy（temp buf DATASIZE * sizeof（DATATYPE））;
	if （m != 2） {    //空格右移
		temp[n][m] = temp[n][m + 1];
		temp[n][m + 1] = 0;
		if （close.exist（*temp） == false） open.push（*temp &pid）;
#ifdef SHOWPROCESS
		cout << “move below data to open table:“ << endl;
		showElement（*temp）;
		getchar（）;
#endif
	}



}

void SearchTree::moveToClose（） {
	DATATYPE dt[DATASIZE];
	Data *pid;
	open.pop（dt &pid）;
	close.push（dt &pid）;
}


bool SearchTree::success（） {
	DATATYPE dt[DATASIZE];
	close.getTop（dt）;
	return memcmp（dt *sg DATASIZE * sizeof（DATATYPE）） ? false : true;
}

void SearchTr

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2018-03-25 18:12  jiugongge8\
     目录           0  2018-03-25 17:22  jiugongge8\.vs\
     目录           0  2018-03-25 17:22  jiugongge8\.vs\jiugongge8\
     目录           0  2018-03-27 19:36  jiugongge8\.vs\jiugongge8\v15\
     文件       38912  2018-03-27 19:36  jiugongge8\.vs\jiugongge8\v15\.suo
     文件     4714496  2018-03-27 19:36  jiugongge8\.vs\jiugongge8\v15\Browse.VC.db
     目录           0  2018-03-25 17:23  jiugongge8\.vs\jiugongge8\v15\ipch\
     目录           0  2018-03-25 17:23  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\
     目录           0  2018-03-25 17:33  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\
     目录           0  2018-03-25 17:23  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\DATA-5979d51e\
     文件      327680  2018-03-25 17:31  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\DATA-5979d51e\DATA.ipch
     目录           0  2018-03-25 17:25  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\link-6cb0be72\
     文件      327680  2018-03-25 17:31  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\link-6cb0be72\link.ipch
     目录           0  2018-03-25 17:33  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\MAIN-d4d68584\
     文件    23789568  2018-03-27 07:00  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\MAIN-d4d68584\MAIN.ipch
     目录           0  2018-03-25 17:31  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\QUEUE-9f0ca209\
     文件      327680  2018-03-25 17:31  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\QUEUE-9f0ca209\QUEUE.ipch
     目录           0  2018-03-25 17:32  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\STACK-3659cb9a\
     文件      327680  2018-03-25 17:32  jiugongge8\.vs\jiugongge8\v15\ipch\AutoPCH\JIUGONGGE8-5696ac7f\STACK-3659cb9a\STACK.ipch
     目录           0  2018-03-25 17:40  jiugongge8\Debug\
     文件       59392  2018-03-25 17:58  jiugongge8\Debug\jiugongge8.exe
     文件      468932  2018-03-25 17:58  jiugongge8\Debug\jiugongge8.ilk
     文件      667648  2018-03-25 17:58  jiugongge8\Debug\jiugongge8.pdb
     目录           0  2018-03-25 18:12  jiugongge8\Release\
     文件       14848  2018-03-25 18:12  jiugongge8\Release\jiugongge8.exe
     文件       66319  2018-03-25 18:12  jiugongge8\Release\jiugongge8.iobj
     文件       25408  2018-03-25 18:12  jiugongge8\Release\jiugongge8.ipdb
     文件      651264  2018-03-25 18:12  jiugongge8\Release\jiugongge8.pdb
     目录           0  2018-03-25 18:12  jiugongge8\jiugongge8\
     目录           0  2018-03-25 17:58  jiugongge8\jiugongge8\Debug\
     文件        1057  2018-03-25 17:40  jiugongge8\jiugongge8\Debug\jiugongge8.Build.CppClean.log
............此处省略33个文件信息