m_list.cpp

利用人工智能的经典算法实现迷宫游戏；里面的A星（a*）算法可以很方便的移植到应用程序中

// m_List.cpp: implementation of the m_List class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "qiyuan.h"
#include "m_List.h"
#include <stdio.h>
#include <stdlib.h>
#include "afxwin.h"
#include "list_node1.h"
//#include ""


#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//extern list_node m_list; //建立一个 自己用的 链表 用于存放 a*搜到的 路径


//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

listnode::listnode()
{

}

listnode::~listnode()
{

}

/*	????   listnode::open_list()
{
		m_List Open_m_List;
		return *Open_m_List.link_node; 
}
*/

//======================================================================= 
// Description : 构造函数，创建双向链表的一个结点，并赋值当前结点为空。 
// Parameters  : int类型的数据，由于表头结点中的数据不会被使用， 
//     因此该数据可以为任何不在后继结点中使用的数据即可。 
// Returns     : 无 
// Supplement  : 无 
//use======================================================================== 
list_node *  listnode::create_node(int row_1,int collum_1,int f_n_1)
{
	list_node *pnode;
 if ((pnode =(list_node* )malloc(sizeof(list_node)))==NULL) 
 {
	 AfxMessageBox("不能分配内存空间");
	} ;
 pnode->row = row_1;
  pnode->collum = collum_1;
   pnode->f_n = f_n_1;
    pnode->g_n = 0;
	 pnode->h_n = 0;
	  pnode->father=NULL;
	   pnode->son1=NULL;
	    pnode->son2=NULL;
		 pnode->son3=NULL;
		  pnode->son4=NULL;
 pnode->prior = pnode->next = pnode;    //创建新结点时，让其前向和后向指针都指向自身 
 return (pnode);
}

//======================================================================= 
// Description : 构造函数，创建一个双向链表,其实就是创建创建链表的头指针。 
// Parameters  : int类型的数据，由于表头结点中的数据不会被使用， 
//				 因此该数据可以为任何不在后继结点中使用的数据即可。
// Supplement  : 无 
//======================================================================== 
//创建链表use
int listnode::create_list(int head1,int head2,int head3)			//参数给出表头结点数据 （表头结点不作为存放有意义数据的结点）
{
	list_node * pnode1;

 if ((pnode1 =(list_node* )malloc(sizeof(list_node)))==NULL) 
 {
//	 MessageBox(NULL,"不能分配内存空间",NULL,NULL);
	} ;
  pnode1->row = head1;
  pnode1->collum = head2;
  pnode1->f_n = head3;
    pnode1->g_n = 0;
	 pnode1->h_n = 0;
	  pnode1->father=NULL;
	   pnode1->son1=NULL;
	    pnode1->son2=NULL;
		 pnode1->son3=NULL;
		  pnode1->son4=NULL;
  pnode1->prior = pnode1->next = pnode1;
return (TRUE);
}
int listnode::openlist(list_node * open_list )
{
 return (1);
}


//插入新结点,总是在表尾插入; 返回表头结点use
list_node * listnode::insert_node(list_node * node_temp, int data1,int data2,int data3) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）
{
list_node *  pnode; 
if ((pnode =(list_node* )malloc(sizeof(list_node)))==NULL) 
 {
	 //MessageBox(HWND Hwnd,"不能分配内存空间",NULL,NULL);
	} ;
 pnode->row = data1;
  pnode->collum = data2;
   pnode->f_n = data3;
    pnode->g_n = 0;
	 pnode->h_n = 0;
	  pnode->father=NULL;
	   pnode->son1=NULL;
	    pnode->son2=NULL;
		 pnode->son3=NULL;
		  pnode->son4=NULL;
 pnode->prior = pnode->next = pnode;    //创建新结点时，让其前向和后向指针都指向自身 
 list_node *  temp = node_temp->prior;
 // 从左到右恢复链接
 node_temp->prior->next = pnode;
 pnode->next = node_temp; 
 // 从右到左恢复链接
 node_temp->prior = pnode;
 pnode->prior = temp; 
 return node_temp;

}
//插入新结点,总是在表尾插入; 返回表头结点
list_node *  listnode::insert_node2(list_node * list_head2,list_node * node_temp) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）
{ 
	 list_node  * temp = list_head2->prior;
	if(node_temp==NULL||list_head2==NULL)
{
	AfxMessageBox("错误的插入空节点或表为空");
}
 // 从左到右恢复链接
 list_head2->prior->next = node_temp;
 node_temp->next =list_head2; 
 // 从右到左恢复链接
 list_head2->prior = node_temp;
 node_temp->prior = temp; 
 return list_head2;
}
// use查找结点，成功则返回满足条件的结点指针，否则返回NULL
// use查找结点，成功则返回满足条件的结点指针，否则返回NULL
list_node * listnode::find_closed(list_node * node_temp, int target1,int target2) // 参数1是链表的表头结点，参数2是要查找的结点（其中结点数据为target）
{
 list_node * pnode = node_temp->next;
 while (pnode->next != node_temp && (!(pnode->row== target1&& pnode->collum==target2)))
 {
  pnode = pnode->next;
 } 
 if (pnode->next == node_temp&& (!(pnode->row== target1&& pnode->collum==target2)))  return NULL; 
 return  pnode;
}
//=============================================================================== 
// Description : 删除当前结点。 
// Parameters  : d第一个是表头地址，第二个是要删的节点的地址 
// Returns     : 无 
// Supplement  : 无 
//use================================================================================ 
int   listnode::del_node2(list_node * list_head1,list_node * node_current) 
{  
	 list_node *  ptmp;
 if (NULL == node_current) 
 { 
  AfxMessageBox("删除节点出现错误。:-(  \n");
  return 0;
 } 
  if (NULL == list_head1) 
 { 
  AfxMessageBox("删除节点出现错误。：您企图从空表中删除元素	:-(  \n");
  return 0;
 }
 if (node_current == list_head1)			// 若删除的是第一个节点，											
 {											// 则删后表会空或者表空时还要删，这是不符合逻辑的
   AfxMessageBox("你弄错了.\n");
	AfxMessageBox("你正在企图删除表头，请重新确定您的意图。:-（\n");
 return 0;
 }
  ptmp = node_current->prior;
  ptmp->next = node_current->next;
  ptmp->next->prior = ptmp; 
 //free(node_current); 
 return  1;
}
//=============================================================================== 
// Description : 该函数判断双向链表是否为空。 
// Parameters  : 无 
// Returns     : 若链表为空则返回1，否则返回0。 
// Supplement  : 无 
//use================================================================================ 
int listnode::IsMyListEmpty(list_node * link_temp) 
{ 
	if(link_temp->next==link_temp) 
 { 
  return 1;
 }
 return 0;
}
//============================================================================ 
// Description : 该函数从链表开始位置寻找结点数据等于fn的结点。 
// Parameters  : 无 
// Returns     : 若找到满足条件的结点则返回指向该结点指针，    
// Supplement  : 无 
//use============================================================================
list_node *  listnode::find_fn(list_node * node_temp)		// 参数1是链表的表头结点
{
	int findout=0;
 list_node * pnode  = node_temp->next;
 list_node * min_fn = node_temp->next;

 while (pnode->next != node_temp ) 
 {
	if(pnode->f_n<=min_fn->f_n)					/* 谁小谁标记为min_fn */
	   {
	      min_fn=pnode;
		}
	pnode = pnode->next;
	findout++;

 }

if(pnode->f_n<=min_fn->f_n)					    /* 谁小谁标记为min_fn */
		{
		  min_fn=pnode;
		} 
 return  (min_fn);
}
//======================================================================= 
// Description :  迷宫A*搜索算法中的重新计算子孙节点的fn值程序
// Parameters  : 入口参数：当前节点,;返回值:
// Supplement  : 无 
//======================================================================== 
list_node *  listnode::son_fn(list_node * temp,int dg)
{
	if(temp->son1!=NULL)						 //若有第一子节点计算其fn		
	{
		temp->son1->g_n=+dg;
		temp->son1->f_n=temp->son1->g_n+temp->son1->h_n;
		temp=temp->son1;
		son_fn(temp,dg);
	}
		if(temp->son2!=NULL)						// 若有第二子节点计算其fn
	{
		temp->son2->g_n=+dg;
		temp->son2->f_n=temp->son2->g_n+temp->son2->h_n;
		temp=temp->son2;
		son_fn(temp,dg);
	}
			if(temp->son3!=NULL)						// 若有第三子节点计算其fn		
	{
		temp->son3->g_n=+dg;
		temp->son3->f_n=temp->son3->g_n+temp->son3->h_n;
		temp=temp->son3;
		son_fn(temp,dg);
	}
				if(temp->son4!=NULL)					// 若有第四子节点计算其fn		
	{
		temp->son4->g_n=+dg;
		temp->son4->f_n=temp->son4->g_n+temp->son4->h_n;
		temp=temp->son4;
		son_fn(temp,dg);
	}
	return NULL;
}
//======================================================================= 
// Description :  迷宫A*搜索算法程序
// Parameters  :链表定义，结合状态空间的定义等，已于上面完成
// Supplement  : 无 
//use======================================================================== 


int listnode::Destroy(list_node *list_head1)
{
	list_node * ptmp1;	
	ptmp1=list_head1->prior;

	list_node * ptmp2;
	if(list_head1==NULL)
	{
	//	MessageBox("不能删除空节点");
	}
	while(list_head1!=ptmp1)
	{
	
		ptmp2=list_head1->next;
	//	list_head1->prior=ptmp->prior;
	//	ptmp->prior->next = list_head1; 
		free(list_head1);
		list_head1=ptmp2;
	}
	free(list_head1);
 return (TRUE);

}