1、初始状态 35214876 结果数据结构：本实验使用的数据结构是队列，应用队列先进先出的特点来实现对节点的保存和扩展。首先建立一个队列，将初始结点入队，并设置队列头和尾指，然后取出队列（头指针所指）的结点进行扩展，从它扩展出子结点，并将这些结点按扩展的顺序加入队列，然后判断扩展出的新结点与队列中的结点是否重复，如果重复则，否则记录其父结点，并将它加入队列，更新队列尾指针，然后判断扩展出的结点是否是目标结点，如果是则显示路径，程序结束。否则如果队列头的结点可以扩展，直接返回第二步。否则将队列头指针指向下一结点，再返回第二步，知道扩展出的结点是目标结点结束，并显示路径。代码如下： #include
2、 #include windows.hqueuestackusing namespace std;#define HashTableSize 362881 #define NOT !#define UP 0 #define DOWN 1 #define LEFT 2 #define RIGHT 3 #define Bit char typedef struct maps Bit detail9;int myindex; / 记录自己节点在hash表中的位置 Bit position; / 记录 空格（0）在序列中的位置 Map,*PMap;Map org; / 初始状态 int EndInde
3、x; /目标,上移 ，下移 ， 左移 ，右移 int const derection4 = -3 , 3 , -1 , 1 ;/ 可移动的四个方向 int const Factorial9 = 40320 , 5040 , 720 , 120 , 24 , 6 , 2 , 1 , 1 ;int HashTableHashTableSize=0; /hash表,其中记录的是上一个父节点对应的位置 /*八数码的输入（在这里不做任何输入检查，均认为输入数据是正确的）*/void input（） int i,j;int sum , count ,index ;printf（输入九个数：n）; /必须输
4、入一个0作为空值for（i = 0 ; i 9 ; i + ） scanf（%1d, &org.detail i ）;org.detail i | （org.position = i） ; i + ） /计算逆序 if（ 0 = org.detail i ） continue;for（j = 0 ; j i; j + ） sum += （ 0 != org.detail j & org.detail j org.detail i ;index += Factorial org.detail i * count; org.myindex = index + 1 ; EndIndex = sum%
5、2 ? 161328:322561; / 目标状态的hash值 return;/*hash值的计算*Parent:父状态的hash值*direct:移动的方向*/ inline int HashValue（Map& Parent , int& direct ） int i = Parent.position ; int newindex = Parent.myindex ; Bit *p = Parent.detail; switch（direct） case UP : newindex -= 3*40320 ; newindex += （ p i - 2 p i - 3 ） ? （ Fact
6、orial p i - 3 ） : （ - Factorial p i - 2 ）; newindex += （ p i - 1 （ - Factorial p i - 1 ）; break; case DOWN : newindex += 3*40320 ; newindex -= （ p i + 2 p i + 3 ） ? （ Factorial p i + 3 ） : （ - Factorial p i + 2 ）; newindex -= （ p i + 1 （ - Factorial p i + 1 ）; case LEFT : return newindex - 40320; ca
7、se RIGHT : return newindex + 40320; return newindex;/* * * 广度优先搜索*/ void Bfs（） queue Queue; Queue.push（org）; HashTable org.myindex = -1; while（ NOT Queue.empty（） ） Map node = Queue.front（）; Queue.pop（）; for（int k =0 ; k 4; k + ） Map tmp = node; tmp.position = node.position + derectionk; if（tmp.posit
8、ion 8 | （ k 1 & tmp.position / 3 != node.position /3 ） ） continue;tmp.myindex = HashValue（ node , k ）;if（0 != HashTabletmp.myindex ） continue;tmp.detail node.position = tmp.detail tmp.position ;/ 移动空格 tmp.detail tmp.position = 0 ;HashTabletmp.myindex = node.myindex; / 状态记录到hashtable中 if（ node.myinde
9、x = EndIndex ） return ; Queue.push（ tmp ）; return ;/* 通过hash表中记录的进行查找路径*/ void FindPath（） int nowindex; int count =0 ; int nixu9, result9; int i, j , k ; stack Stack; Stack.push（EndIndex）; nowindex = EndIndex; while（ -1 != HashTable nowindex ） Stack.push（HashTable nowindex ）; nowindex = HashTable no
10、windex ; printf（共需： %d 步n,Stack.size（）-1）; getchar（）; while（ NOT Stack.empty（） nowindex = Stack.top（） - 1 ; Stack.pop（）; for（ i = 0 ; 9; i + ） / 计算出逆序 nixui = nowindex / Factorial i ; nowindex %= Factorial i ; memset（ result , -1 , 9 *sizeof（int）; for（ i =0 ; i + ） / 根据逆序计算排列 for（ j = 0 , k = nixui
11、; if（resultj = -1 ） k -; if（ k 0 ） break; resultj = i ;%3d,resulti）; if（ 2 = i % 3 ） printf（ if（0 != Stack.size（） ） n 第%d步n,+count）;nFinish!int main（） input（）; /输入要排序的序列0-8 long time =GetTickCount（）; Bfs（）;计算用时：%dMSn,GetTickCount（）-time）; FindPath（）; return 0; /返回结果实验结果：输入数列087653214 结果：小结：本次实验让我学会了系统的去探索问题，并用科学的方法来解决它，同时也学会了用编程语言实现搜索算法。评定成绩： 批阅教师： 年 月 日
