控制台程序 八数码 代码 可执行程序

/*AI1.cpp 函数的实现*/ #include<stdio.h> #include<math.h> #include<windows.h> #include"AI1.h" int CountF(NODE * node,NODE * target)/*计算g，w和f，返回f*/ { int i,j=0; node->w = 0; for(;j<9;j++) { i=0; while((node->s[i] != target->s[j]) && i < 9) i++; if(i == j) continue; else { node->w += ((abs(i-j)) / 3 + (abs(i-j)) % 3 ); } } node->f = node->w + node->g; return node->f; } void PrintNode(NODE * node) { int i=0; for(;i<9;i++) { printf("%6d",node->s[i]); if(i%3 == 2) printf("\n"); } } void IniteNode(NODE * node,NODE * target)/*初始化开始节点和目标节点的状态*/ { int i=0; printf("请输入9个数字0--9，依次作为开始状态\n"); for(;i < 9;i++) scanf("%d",&node->s[i]); node->g = node->w = node->f = 0; node->father = NULL; node->next = NULL; PrintNode(node); printf("请输入9个数字0--9，依次作为目标状态\n"); for(i=0;i < 9;i++) scanf("%d",&target->s[i]); target->g = target->w = target->f = 0; target->next = NULL; target->father = NULL; PrintNode(target); } void InsertToOpen(NODE * node,OPEN * open)/*将扩展后的节点加入到open中，排序插入*/ { Node p = open->next; Node first=open->next; Node prep=p; int f_node = node->f; if(open->next == NULL) { open->next = node; node->next = NULL; return; } while(p) { if(f_node <= p->f && p == first) { node->next = p; open->next = node; return; } if(f_node <= p->f) { node->next = p; prep->next=node; return; } prep=p; p = p->next; } prep->next = node;//node的f 最大,放在链尾 node->next = NULL; return; } bool IsOpenNull(Open open) { return (open->next == NULL)? true : false ; } void FirstNodeFromOpenToClose(Open open,Close close) { Node p_close = close->next; Node temp = open->next; open->next = temp->next; if(!p_close)//close为空 { close->next=temp; temp->next=NULL; return ; } while(p_close->next) { p_close = p_close->next; } p_close->next = temp; temp->next = NULL; return; } bool IsTarget(NODE * node,NODE * target) { int i = 0; for(i; i < 9; i++) if(node->s[i] != target->s[i]) return false; return true; } void CopyOpenFirstNode(Open open,Node first) { int i = 0; Node node = open->next; for(i; i < 9; i++) first->s[i] = node->s[i] ; first->g = node->g; first->w = node->w; first->f = node->f; first->father = node->father; first->next = NULL; } void CopyCloseTail(Node first ,Close close) { int i = 0; Node tail = close->next; if(!tail) return; while(tail->next) tail = tail->next; for(i; i < 9; i++) first->s[i] = tail->s[i] ; first->g = tail->g; first->w = tail->w; first->f = tail->f; first->father = tail->father; first->next = NULL; } void PrintPath(Close close,Node pnode ) { Node father; father = pnode->father; PrintNode(pnode); while(father) { PrintNode(father); printf(" |\n"); printf(" |\n"); Sleep(2000); father = father->father; } return; } void PrintClose(Close close) { Node father = close->next; printf("最佳路径如下：\n"); while(father) { PrintNode(father); printf(" | g w f %d %d %d \n",father->g,father->w,father->f); printf(" |\n"); printf(" |\n"); Sleep(1000); father = father->next; } printf("------------end---------------\n"); } int FindZero(NODE * node) { int i = 0 ; for(i; i < 9; i++) if(node->s[i] == 0) return i; return -1; } bool IsInClose(NODE *node ,Close close) { int i; Node temp = close->next; while(temp) { i = 0; while(i < 9) { if(temp->s[i] != node->s[i]) break; i++; } if(i == 9) return true; temp = temp->next; } return false; } void Expand0(NODE * node,Close close,Open open,Node target) { int i; Node p1 = new NODE; Node p2 = new NODE; bool in; for(i = 0;i < 9; i++) { p1->s[i] = p2->s[i] = node->s[i]; } p1->g = p2->g = node->g + 1; p1->w = p2->w = 0; p1->father = p2->father = node; p1->next = p2->next = NULL; p1->s[0] = p1->s[1]; p1->s[0] = 0; p2->s[0] = p2->s[3]; p2->s[3] = 0; in=IsInClose(p1,close); if(in) { delete p1; p1 = NULL; } in=IsInClose(p2,close); if(in) { delete p2; p2 = NULL; } if(p1) { CountF(p1,target); InsertToOpen(p1,open); } if(p2) { CountF(p2,target); InsertToOpen(p2,open); } } void Expand1(NODE * node,Close close,Open open,Node target) { int i; Node p1 = new NODE; Node p2 = new NODE; Node p3 = new NODE; bool in; for(i = 0;i < 9; i++) { p3->s[i] = p1->s[i] = p2->s[i] = node->s[i]; } p1->g = p2->g = p3->g = node->g + 1; p1->w = p2->w = p3->w = 0; p1->father = p2->father = p3->father = node; p1->next = p2->next = p3->next = NULL; p1->s[1] = p1->s[0]; p1->s[0] = 0; p2->s[1] = p2->s[2]; p2->s[2] = 0; p3->s[1] = p3->s[4]; p3->s[4] = 0; in=IsInClose(p1,close); if(in) { delete p1; p1 = NULL; } in=IsInClose(p2,close); if(in) { delete p2; p2 = NULL; } in=IsInClose(p3,close); if(in) { delete p3; p3 = NULL; } if(p1) { CountF(p1,target); InsertToOpen(p1,open); } if(p2) { CountF(p2,target); InsertToOpen(p2,open); } if(p3) { CountF(p3,target); InsertToOpen(p3,open); } } void Expand2(NODE * node,Close close,Open open,Node target) { int i; Node p1 = new NODE; Node p2 = new NODE; bool in; for(i = 0;i < 9; i++) { p1->s[i] = p2->s[i] = node->s[i]; } p1->g = p2->g = node->g + 1; p1->w = p2->w = 0; p1->father = p2->father = node; p1->next = p2->next = NULL; p1->s[2] = p1->s[1]; p1->s[1] = 0; p2->s[2] = p2->s[5]; p2->s[5] = 0; in=IsInClose(p1,close); if(in) { delete p1; p1 = NULL; } in=IsInClose(p2,close); if(in) { delete p2; p2 = NULL; } if(p1) { CountF(p1,target); InsertToOpen(p1,open); } if(p2) { CountF(p2,target); InsertToOpen(p2,open); } } void Expand3(NODE * node,Close close,Open open,Node target) { int i; Node p1 = new NODE; Node p2 = new NODE; Node p3 = new NODE; bool in; for(i = 0;i < 9; i++) { p3->s[i] = p1->s[i] = p2->s[i] = node->s[i]; } p1->g = p2->g = p3->g = node->g + 1; p1->w = p2->w = p3->w = 0; p1->father = p2->father = p3->father = node; p1->next = p2->next = p3->next = NULL; p1->s[3] = p1->s[0]; p1->s[0] = 0; p2->s[3] = p2->s[6]; p2->s[6] = 0; p3->s[3] = p3->s[4]; p3->s[4] = 0; in=IsInClose(p1,close); if(in) { delete p1; p1 = NULL; } in=IsInClose(p2,close); if(in) { delete p2; p2 = NULL; } in=IsInClose(p3,close); if(in) { delete p3; p3 = NULL; } if(p1) { CountF(p1,target); InsertToOpen(p1,open); } if(p2) { CountF(p2,target); InsertToOpen(p2,open); } if(p3) { CountF(p3,target); InsertToOpen(p3,open); } } void Expand4(NODE * node,Close close,Open open,Node target) { int i; Node p1 = new NODE; Node p2 = new NODE; Node p3 = new NODE; Node p4 = new NODE; bool in; for(i = 0;i < 9; i++) { p4->s[i] = p3->s[i] = p1->s[i] = p2->s[i] = node->s[i]; } p4->g = p1->g = p2->g = p3->g = node->g + 1; p1->w = p2->w = p3->w = p4->w = 0; p4->father = p1->father = p2->father = p3->father = node; p4->next = p