九宫问题Word下载.docx

1、 struct Node *pointData; /指向节点的指针 struct SpringLink *next; /指向当前节点的其他扩展节点SPLink, *PSPLink;/声明OPEN表和CLOSED表PNode open;PNode closed;/计算棋盘状态的逆序数int InverseNumber（status a） int i, j, sum=0; int data_changsize*size=0; /将二维数组转换成一维数组，以方便求逆序数 for（i=0;isize;i+） for（j=0;j=0;j-） /当后一个数比前一个数小时 if（data_changinex

2、t = NULL;/判断链表是否为空bool isEmpty（PNode Head） if（Head-next = NULL）/从链表中拿出一个数据void popNode（PNode &Head , PNode &FNode） if（isEmpty（Head） FNode = NULL; return; FNode = Head-next;next = Head-next- FNode-/向节点的最终后继节点链表中添加新的子节点void addSpringNode（PNode &Head , PNode newData） PSPLink newNode = （PSPLink）malloc（s

3、izeof（SPLink）; newNode-pointData = newData;child;child = newNode;/释放状态图中存放节点后继节点地址的空间void freeSpringLink（PSPLink & PSPLink tmm; while（Head != NULL） tmm = Head; Head = Head- free（tmm）;/释放open表与closed表中的资源void freeLink（PNode & PNode tmn; tmn = Head; Head = Head- free（tmn）; /首先释放存放节点后继节点地址的空间 freeSprin

4、gLink（Head-child）; tmn = Head; free（tmn）;/向普通链表中添加一个节点void addNode（PNode &newNode）next = newNode;/向非递减排列的链表中添加一个节点void addAscNode（PNode & PNode P; PNode Q; P = Head- Q = Head; while（P != NULL & P-f_value /上面判断好位置之后，下面就是简单的插入节点了next = Q- Q-/计算节点到目标状态的预计耗散值int computeh_value（PNode theNode,status targe

5、tStatus） int num = 0; for（int i = 0 ; i 3 ; i+） for（int j = 0 ; j dataij != targetStatusij） num+; return num;/计算节点的f，g，h值void computeAllValue（PNode &theNode , PNode parentNode, status targetStatus） if（parentNode = NULL） theNode-g_value = 0;g_value = parentNode-g_value + 1; theNode-h_value = computeh

6、_value（theNode,targetStatus）;f_value = theNode-g_value + theNode-h_value;/初始化函数，进行算法初始条件的设置void initial（status startStatus,status targetStatus） /初始化open以及closed表 initLink（open）; initLink（closed）; /初始化起始节点，令初始节点的父节点为空节点 PNode NULLNode = NULL; PNode StartNode = （PNode）malloc（sizeof（NNode）; StartNode-d

7、ataij = startStatusij; StartNode-parent = NULL;child = NULL; computeAllValue（StartNode, NULLNode,targetStatus）; /起始节点进入OPEN表 addAscNode（open , StartNode）;/将B节点的状态赋值给A节点void statusAEB（PNode &ANode , PNode BNode） ANode-dataij = BNode-dataij;/两个节点是否有相同的状态bool hasSameStatus（PNode ANode , PNode BNode） si

8、ze ; if（ANode-= BNode-dataij） return false; return true;/节点与其祖先节点是否有相同的状态bool hasAnceSameStatus（PNode OrigiNode , PNode AnceNode） while（AnceNode ! if（hasSameStatus（OrigiNode , AnceNode） return true; AnceNode = AnceNode-parent; return false;/取得方格中空的格子的位置void getPosition（PNode theNode , int &row , int

9、 &col）dataij = 0） row = i; col = j; return;/交换两个数字的值void changeAB（int &a , int &b） int c; c = b; b = a; a = c;/检查相应的状态是否在某一个链表中bool inLink（PNode spciNode , PNode theLink , PNode &theNodeLink , PNode &preNode） preNode = theLink; theLink = theLink- while（theLink ! if（hasSameStatus（spciNode , theLink）

10、theNodeLink = theLink; preNode = theLink; theLink = theLink-/产生节点的后继节点链表void SpringLink（PNode theNode , PNode &spring, status targetStatus） int row; int col; getPosition（theNode , row , col）; /空的格子右边的格子向左移动 if（col != 2） PNode rlNewNode = （PNode）malloc（sizeof（NNode）; statusAEB（rlNewNode, theNode）; ch

11、angeAB（rlNewNode-datarowcol, rlNewNode-datarowcol + 1）; if（hasAnceSameStatus（rlNewNode, theNode-parent） free（rlNewNode）;/与父辈相同，丢弃本节点 else rlNewNode-parent = theNode; computeAllValue（rlNewNode, theNode, targetStatus）; /将本节点加入后继节点链表 addNode（spring, rlNewNode）; /空的格子左边的格子向右移动= 0） PNode lrNewNode = （PNo

12、de）malloc（sizeof（NNode）; statusAEB（lrNewNode, theNode）; changeAB（lrNewNode-datarowcol, lrNewNode-datarowcol - 1）; if（hasAnceSameStatus（lrNewNode, theNode- free（lrNewNode）; lrNewNode- computeAllValue（lrNewNode, theNode, targetStatus）; addNode（spring , lrNewNode）; /空的格子上边的格子向下移动 if（row ! PNode udNewNo

13、de = （PNode）malloc（sizeof（NNode）; statusAEB（udNewNode , theNode）; changeAB（udNewNode-datarowcol, udNewNode-datarow - 1col）; if（hasAnceSameStatus（udNewNode, theNode- free（udNewNode）; udNewNode- computeAllValue（udNewNode, theNode, targetStatus）; addNode（spring, udNewNode）; /空的格子下边的格子向上移动 PNode duNewNo

14、de = （PNode）malloc（sizeof（NNode）; statusAEB（duNewNode, theNode）; changeAB（duNewNode-datarowcol, duNewNode-datarow + 1col）; if（hasAnceSameStatus（duNewNode, theNode- free（duNewNode）; duNewNode- computeAllValue（duNewNode, theNode, targetStatus）; addNode（spring , duNewNode）;/输出给定节点的状态void outputStatus（P

15、Node stat） cout dataij ; cout g_value; if（goal-parent ! outputBestRoad（goal-parent）; cout 第 deepnum- 步的状态： outputStatus（goal）;void AStar（status startStatus,status targetStatus） PNode tmpNode; /指向从open表中拿出并放到closed表中的节点的指针 PNode spring; /tmpNode的后继节点链 PNode tmpLNode; /tmpNode的某一个后继节点 PNode tmpChartNo

16、de; PNode thePreNode; /指向将要从closed表中移到open表中的节点的前一个节点的指针 bool getGoal = false; /标识是否达到目标状态 long numcount = 1; /记录从open表中拿出节点的序号 initial（startStatus,targetStatus）; /对函数进行初始化 initLink（spring）; /对后继链表的初始化 tmpChartNode = NULL;从OPEN表中拿出的节点的状态及相应的值 while（!isEmpty（open） /从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中 popNode（open, tmpNode）; addNode（closed, tmpNode）; numcount+ 其g值为：g_value 其h值为：h_value tmpChartNode-g_value） tmpChartNode-parent = tmpLNode-g_value = tmpLNode-f_value = tmpLNode-f_value; fre