maze3_a.c

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

/* 迷宫A*搜索算法算法 */
#include"stdio.h"
/* A*搜索函数形式参数（迷宫，起点，目标点，路经，路径数，指向总数的指针） */
void a_search(int a[][10],*s_o,*s_g)
{
   int i;
   if((x==endx)&&(y==endy))
   {
      *p=*p+1;
      printf("\nThe number  %d path",*p);
      for(i=0;i<level;i++)
         printf("(%d,%d,%d)",path[i][0],path[i][1],path[i][2]);
	  return;
   }
   if((a[x][y+1]!=0)&&(a[x+1][y]!=0)&&(a[x][y-1]!=0)&&(a[x-1][y]!=0))
	   return;        /* 该if语句可以省略 */
   if(a[x][y+1]==0)
   {  path[level][0]=x;path[level][1]=y;path[level][2]=1;a[x][y]='*';
      puzzle(a,x,y+1,endx,endy,path,level+1,p);a[x][y]=0;
   }
   if(a[x+1][y]==0)
   {  path[level][0]=x;path[level][1]=y;path[level][2]=2;a[x][y]='*';
      puzzle(a,x+1,y,endx,endy,path,level+1,p);a[x][y]=0;
   }
   if(a[x][y-1]==0)
   {  path[level][0]=x;path[level][1]=y;path[level][2]=3;a[x][y]='*';
      puzzle(a,x,y-1,endx,endy,path,level+1,p);a[x][y]=0;
   }
   if(a[x-1][y]==0)
   {  path[level][0]=x;path[level][1]=y;path[level][2]=4;a[x][y]='*';
      puzzle(a,x-1,y,endx,endy,path,level+1,p);a[x][y]=0;
   }
   return;
}

main()
{
   int a[11][10]={
	1,1,1,1,1,1,1,1,1,1,
	1,0,0,0,0,0,0,1,0,1,
	1,0,0,1,0,0,0,1,0,1,
	1,0,0,0,0,1,1,0,1,1,
	1,0,1,1,1,0,0,1,0,1,
	1,0,0,0,1,0,0,0,0,1,
	1,0,1,0,0,0,1,0,1,1,
	1,0,1,1,1,1,0,0,1,1,
	1,1,1,0,0,0,1,0,1,1,
	1,1,1,0,0,0,0,0,0,1,
	1,1,1,1,1,1,1,1,1,1
	};
   int i,j;
   int startpointx=1;
   int startpointy=1;
   int endpointx=9;
   int endpointy=8;
   int *p,sum,path[72][3];
   sum=0;p=&sum;

   puzzle(a,startpointx,startpointx,endpointx,endpointy,path,0,p);
   printf("\nTotal number %d paths\n",sum);
   for(i=0;i<=10;i++)
   {for(j=0;j<=9;j++)         
         {printf(" %d",a[i][j]);}
		 if(j=10)printf("\n");}
}


#include <stdio.h>
#include <stdlib.h>

typedef struct tagDbNode
{
 int data;
 struct tagDbNode * left;
 struct tagDbNode * right;
} DbNode, * pdbNode;


//创建结点
pdbNode CreateNode(int data)
{
 pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
 pnode->data = data;
 pnode->left = pnode->right = pnode;    //创建新结点时，让其前驱和后继指针都指向自身
 
 return pnode;
}


//=========================================================================

//创建链表
pdbNode CreateList(int head)  //参数给出表头结点数据 （表头结点不作为存放有意义数据的结点）
{
 pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
 pnode->data = head;
 pnode->left = pnode->right = pnode;
 
 return pnode;
}

//插入新结点,总是在表尾插入; 返回表头结点
pdbNode InsertNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要插入的结点（结点数据为data）
{
 pdbNode pnode = CreateNode(data);
 pdbNode ptmp = node->left;
 
 // 从左到右恢复链接
 node->left->right = pnode;
 pnode->right = node;
 
 // 从右到左恢复链接
 node->left = pnode;
 pnode->left = ptmp;
 
 return node;
}

//查找结点，成功则返回满足条件的结点指针，否则返回NULL
pdbNode FindNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要查找的结点（其中结点数据为data）
{
 pdbNode pnode = node->right;
 while (pnode->right != node && pnode->data != data)
 {
  pnode = pnode->right;
 }
 
 if (pnode->right == node)  return NULL;
 
 return pnode;
}

//删除满足指定条件的结点, 返回表头结点, 删除失败返回NULL（失败的原因是不存在该结点）
pdbNode DeleteNode(pdbNode node, int data) // 参数1是链表的表头结点，参数2是要删除的结点（其中结点数据为data）
{
 pdbNode ptmp;
 pdbNode pnode = FindNode(node, data);
 
 if (NULL == pnode) return NULL;
 
 ptmp = pnode->left;
 ptmp->right = pnode->right;
 pnode->right->left = ptmp;
 
 free(pnode);
 
 return node;
}

//获取链表的长度
int GetLength(pdbNode node) // 参数为链表的表头结点
{
 int nCount = 0;
 pdbNode pnode = node->right;
 
 while (pnode->right != node)
 {
  nCount++;
 }
 
 return nCount;
}

//打印整个链表
void PrintList(pdbNode node) // 参数为链表的表头结点
{
 pdbNode pnode;

 if (NULL == node) return;
 
 pnode= node->right;
 
 while (pnode != node)
 {
  printf("%d   ", pnode->data);
  pnode = pnode ->right;
 }
 
 printf("\n");
}

//将链表反序打印
void ReverPrint(pdbNode node) //参数为链表的表头结点
{
 pdbNode pnode;

 if (NULL == node) return;
 
 pnode= node->left;

 while (pnode != node)
 {
  printf("%d   ", pnode->data);
  pnode = pnode->left;
 }
 
 printf("\n");
}

//删除链表
void DeleteList(pdbNode node) //参数为链表表头结点
{
 pdbNode pnode = node->right;
 pdbNode ptmp;

 if (NULL == node) return; 
 
 while (pnode != node)
 {
  ptmp = pnode->right;
  free(pnode);
  pnode = ptmp;
 }

 free(node);
}


//测试程序

#include <stdio.h>
#include <stdlib.h>
#include "dblist.h"

#define FALSE 0
#define TRUE  1

typedef unsigned int bool;


void main()
{
 int nChoose;
 int data;
 //int length;
 bool bFlag = FALSE;
 pdbNode pnode;
 pdbNode list = CreateList(0);
 
 while(FALSE == bFlag)
 {
  printf("Main Menu\n");
  printf("1.  Insert\n");
  printf("2.  Delete Node\n");
  printf("3.  Find\n");
  printf("4.  Length\n");
  printf("5.  Positive Print\n");
  printf("6.  Negative Print\n");
  printf("7.  Delete List\n");
  printf("0.  quit\n\n");
  
  scanf("%d", &nChoose);
  
  switch(nChoose)
  {
  case 1:
   printf("Input the data to insert:");
   scanf("%d", &data);
   list = InsertNode(list, data);
   PrintList(list);
   break;
  case 2: 
   printf("Input the data to delete:");
   scanf("%d", &data);
   DeleteNode(list, data);
   break;
  case 3:
   printf("Input the data to find:");
   scanf("%d", &data);
   pnode = FindNode(list, data);
   
   if (NULL != pnode)
   {
    printf("Find succeed!\n");
   }
   else
   {
    printf("Find failed!\n");
   }
   break;
  case 4:
   printf("The list's length is %d", GetLength(list));
   break;
  case 5:
   PrintList(list);
   break;
  case 6:
   ReverPrint(list);
   break;
  case 7:
   DeleteList(list);
   break;
  case 0:
   DeleteList(list);
   bFlag = TRUE;
  }
 }
}