C++实现A*算法十五数码问题

课上老师布置的用C++实现A*算法的十五数码问题，该程序能够完美运行，并且输出最佳解路径。

  
#include “iostream“  
#include “stdlib.h“  
#include “conio.h“  
  
#define size 4  
using namespace std;  
  
//定义二维数组来存储数据表示某一个特定状态  
typedef int status[size][size];  
struct Springlink;  
  
//定义状态图中的结点数据结构  
typedef struct Node  
{  
    status data;//结点所存储的状态  
    struct Node *parent;//指向结点的父亲结点  
    struct Springlink *child;//指向结点的后继结点  
    struct Node *next;//指向open或者closed表中的后一个结点  
    int fvalue;//结点的总的路径  
    int gvalue;//结点的实际路径  
    int hvalue;//结点的到达目标的苦难程度  
}NNode  *PNode;  
  
  
//定义存储指向结点后继结点的指针的地址  
typedef struct Springlink  
{  
    struct Node *pointData;//指向结点的指针  
    struct Springlink *next;//指向兄第结点  
}SPlink  *PSPlink;  
  
  
PNode open;  
PNode closed;  
  
  
//开始状态与目标状态  
status startt = {5124963813151011140712};  
status target = {1234567891011121314150};  
  
  
//初始化一个空链表  
void initlink（PNode &Head）  
{  
    Head = （PNode）malloc（sizeof（NNode））;  
    Head->next = NULL;  
}  
  
  
//判断链表是否为空  
bool isEmpty（PNode Head）  
{  
    if（Head->next == NULL）  
        return true;  
    else  
        return false;  
}  
  
  
//从链表中拿出一个数据  
void popNode（PNode &Head  PNode &FNode）  
{  
    if（isEmpty（Head））  
    {  
        FNode = NULL;  
        return;  
    }  
    FNode = Head->next;  
    Head->next = Head->next->next;  
    FNode->next = NULL;  
}  
  
  
  
//向结点的最终后继结点链表中添加新的子结点  
void addSpringNode（PNode &Head  PNode newData）  
{  
    PSPlink newNode = （PSPlink）malloc（sizeof（SPlink））;  
    newNode->pointData = newData;  
    newNode->next = Head->child;  
    Head->child = newNode;  
}  
  
  
//释放状态图中存放结点后继结点地址的空间  
void freeSpringlink（PSPlink &Head）  
{  
    PSPlink tmm;  
  
    while（Head != NULL）  
    {  
        tmm = Head;  
        Head = Head->next;  
        free（tmm）;  
    }  
}  
  
  
//释放open表与closed表中的资源  
void freelink（PNode &Head）  
{  
    PNode tmn;  
  
    tmn = Head;  
    Head = Head->next;  
    free（tmn）;  
  
    while（Head != NULL）  
    {  
        //首先释放存放结点后继结点地址的空间  
        freeSpringlink（Head->child）;  
        tmn = Head;  
        Head = Head->next;  
        free（tmn）;  
    }  
}  
  
  
//向普通链表中添加一个结点  
void addNode（PNode &Head  PNode &newNode）  
{  
    newNode->next = Head->next;  
    Head->next = newNode;  
}  
  
  
//向非递减排列的链表中添加一个结点  
void addAscNode（PNode &Head  PNode &newNode）  
{  
    PNode P;  
    PNode Q;  
  
    P = Head->next;  
    Q = Head;  
    while（P != NULL && P->fvalue < newNode->fvalue）  
    {  
        Q = P;  
        P = P->next;  
    }  
    //上面判断好位置之后，下面就是简单的插入了  
    newNode->next = Q->next;  
    Q->next = newNode;  
}  
  
  
//计算结点额h值  
int computeHValue（PNode theNode）  
{  
    int num = 0;  
  
    for（int i = 0 ; i < 4 ; i++）  
    {  
        for（int j = 0 ; j < 4 ; j++）  
        {  
            if（theNode->data[i][j] != target

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      13459  2015-12-19 22:54  AAA\AAA\AAA.cpp

     文件       3216  2015-12-13 19:51  AAA\AAA\AAA.vcxproj

     文件        941  2015-12-13 19:51  AAA\AAA\AAA.vcxproj.filters

     文件        143  2015-12-13 19:51  AAA\AAA\AAA.vcxproj.user

     文件        381  2015-12-19 22:54  AAA\AAA\Debug\AAA.exe.intermediate.manifest

     文件         75  2015-12-19 22:54  AAA\AAA\Debug\AAA.lastbuildstate

     文件       2320  2015-12-19 22:54  AAA\AAA\Debug\AAA.log

     文件      68288  2015-12-19 22:54  AAA\AAA\Debug\AAA.obj

     文件        713  2015-12-13 19:51  AAA\AAA\Debug\AAA.vcxprojResolveAssemblyReference.cache

     文件          0  2015-12-13 19:51  AAA\AAA\Debug\AAA.write.1.tlog

     文件        568  2015-12-19 22:54  AAA\AAA\Debug\cl.command.1.tlog

     文件       5270  2015-12-19 22:54  AAA\AAA\Debug\CL.read.1.tlog

     文件        350  2015-12-19 22:54  AAA\AAA\Debug\CL.write.1.tlog

     文件       1190  2015-12-19 22:54  AAA\AAA\Debug\link.command.1.tlog

     文件       2580  2015-12-19 22:54  AAA\AAA\Debug\link.read.1.tlog

     文件        614  2015-12-19 22:54  AAA\AAA\Debug\link.write.1.tlog

     文件        444  2015-12-19 22:54  AAA\AAA\Debug\mt.command.1.tlog

     文件        648  2015-12-19 22:54  AAA\AAA\Debug\mt.read.1.tlog

     文件        276  2015-12-19 22:54  AAA\AAA\Debug\mt.write.1.tlog

     文件     207872  2015-12-19 22:54  AAA\AAA\Debug\vc100.idb

     文件     241664  2015-12-19 22:54  AAA\AAA\Debug\vc100.pdb

     文件    5722112  2015-12-21 22:43  AAA\AAA.sdf

     文件        876  2015-12-13 19:51  AAA\AAA.sln

    ..A..H.     27648  2015-12-21 22:43  AAA\AAA.suo

     文件      43520  2015-12-19 22:54  AAA\Debug\AAA.exe

     文件     377044  2015-12-19 22:54  AAA\Debug\AAA.ilk

     文件     568320  2015-12-19 22:54  AAA\Debug\AAA.pdb

     文件   14352384  2015-12-21 22:43  AAA\ipch\aaa-18971181\aaa-113b12ef.ipch

     目录          0  2015-12-19 22:54  AAA\AAA\Debug

     目录          0  2015-12-21 22:43  AAA\ipch\aaa-18971181

............此处省略7个文件信息