A*算法和基于深度优先的八数码问题

人工智能课程的实验，比较经典的实验，实现了功能。

#ifndef	EightNumberA		//防止再次编译
#define EightNumberA

#include 
using namespace std;

#include “EightNumberADefine.h“

int list_initizalize（ List* list ）;//初始化链表
int list_push（ List* list Node* push_elem ）;//每个扩展的结点进行入队
int list_pop（ List* list int mode ）;//每个扩展的结点进行出队
Node* list_get_head（ List* list int mode ）;//读取栈或队列的头结点
int list_print（ List* list int mode ）;//打印链表
int initialize_puzzle（ Node* node ）;//初始化每个3*3的结点
int input_puzzle（ Node* node ）;//输入每个3*3的结点
int get_f_evaluation（ Node* current Node* target ）;//求f值
int get_initial_value_puzzle（ Node* start Node* target ）;//求f值
Node* expand（ Node* node_cur int direction ）;//从当前结点扩展出许多结点
Node* search（ Node* start Node* end ）;//对已经能扩展的结点存储在链表中，再进行扩展

/*主函数*/
int main（） {
	List*	list;
	Node*	node_start;
	Node*	node_end;
	Node*	ptr;

	list = （List*）malloc（sizeof（List））;
	list_initizalize（ list ）;
	node_start	= （Node*）malloc（sizeof（Node））;
	node_end	= （Node*）malloc（sizeof（Node））;
	initialize_puzzle（ node_start ）;
	initialize_puzzle（ node_end ）;

	cout<<“请输入初始棋盘（0表示空）：“<	input_puzzle（ node_start ）;
	cout<<“请输入目的棋盘（0表示空）：“<	input_puzzle（ node_end ）;
	cout<<“\n“<	get_initial_value_puzzle（ node_start node_end ）;
	if （ node_start->value == 0 ） {
		list_push（ list node_end ）;
		list_print（ list STACK ）;
		return 1;
	}

/*开始搜索 */
	if （ （ ptr = search（ node_start node_end ） ） != NULL ） {
		while （ ptr ） {
			list_push（ list ptr ）;
			ptr = ptr->parent;
		}
		list_print（ list STACK ）;
		cout<<“\n问题解决，解决路径如上！\n“<	}
	else cout<<“对于您输入的初始矩阵，无解！\n“<
	return 1;
}

int list_initizalize（ List* list ）{
	list->length = 0;
	list->head = list->tail = NULL;
	return 1;
}

int list_push（ List* list Node* push_elem ） {
	List_node* newnode;
	newnode = （List_node*）malloc（sizeof（List_node））;
	list->length ++;
	newnode->puzzle_node = push_elem;
	if （ list->tail == NULL ） {
		list->tail = list->head = newnode;
		newnode->next = newnode->pre = NULL;
	}
	else {
		newnode->pre = list->tail;
		newnode->next = NULL;
		list->tail->next = newnode;
		list->tail = newnode;
	}

	return 1;
}

int list_pop（ List* list int mode ） {
	List_node*	target;
	list->length --;
	if （ list->length == 0 ） {
		free（ list->head->puzzle_node ）;
		return 1;
	}
	switch （ mode ） {
	case QUEUE:
		target = list->head->next;
		free（ list->head ）;
		target->pre = NULL;
		list->head = target;
		break;

	case STACK:
		target = list->tail->pre;
		free（ list->tail ）;
		target->next = NULL;
		list->tail = target;
		break;
	}
	return 1;
}

Node* list_get_head（ List* list int mode ） {

	if （ list->length == 0 ） return NULL;
	switch （ mode ） {
	case QUEUE:
		return list->head->puzzle_node;
	
	case STACK:
		return list->tail->puzzle_node;
	}
	return NULL;
}

int list_print（ List* list int mode ） {
	List_node*	ptr;
	int		i;
	int		j;
	int		cnt;
	if （ （list->length == 0） || （list->head ==

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  1980-01-01 00:00  EightNumberA\
     目录           0  2014-05-05 14:58  EightNumberA\Debug\
     目录           0  2014-05-05 14:58  EightNumberDeep\Debug\
     目录           0  2014-05-05 14:58  EightNumberDeep\EightNumberDeep\
     目录           0  2014-05-05 14:58  EightNumberDeep\EightNumberDeep\Debug\
     目录           0  2014-05-05 14:58  EightNumberA\EightNumberA\
     目录           0  2014-05-05 14:58  EightNumberA\EightNumberA\Debug\
     目录           0  2014-05-05 14:58  EightNumberAStar\EightNumberAStar\Debug\
     目录           0  2014-05-05 14:58  EightNumberAStar\EightNumberAStar\
     目录           0  2014-05-05 14:58  EightNumberAStar\Debug\
     目录           0  1980-01-01 00:00  EightNumberAStar\
     目录           0  1980-01-01 00:00  EightNumberDeep\
     文件       71680  2013-11-22 13:08  EightNumberA\Debug\EightNumberA.exe
     文件      681384  2013-11-22 13:08  EightNumberA\Debug\EightNumberA.ilk
     文件      830464  2013-11-22 13:08  EightNumberA\Debug\EightNumberA.pdb
     文件     7557120  2013-11-22 13:41  EightNumberA\EightNumberA.sdf
     文件         903  2013-10-30 10:53  EightNumberA\EightNumberA.sln
     文件       20992  2013-11-22 13:41  EightNumberA\EightNumberA.v11.suo
     文件         654  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\cl.command.1.tlog
     文件        6050  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\CL.read.1.tlog
     文件         386  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\CL.write.1.tlog
     文件          64  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\EightNumberA.lastbuildstate
     文件        1363  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\EightNumberA.log
     文件      163287  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\EightNumberA.obj
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284.read.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284.write.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284-cvtres.read.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284-cvtres.write.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284-rc.read.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.2284-rc.write.1.tlog
     文件           2  2013-11-22 13:08  EightNumberA\EightNumberA\Debug\link.260.read.1.tlog
............此处省略96个文件信息