人工智能课，第一个实验就是八数码问题。老师让用3中方式都实现一遍，分别是广度优先搜索、深度优先搜索和启发式搜索。心塞╮(╯▽╰)╭。紧急补了一些数据结构的知识，就匆匆上阵。先分享深度优先搜索，后两篇我会分享广度优先搜索和启发式搜索的实现。

概念就不讲了，百度就行了。简单说一下我的实现：Situation类存储节点信息，包括父节点的code值（code是一个字符串，存储的是八数码的状态，比如“138427056”），当前节点的code值，以及深度（深度从0开始，即起始节点深度为0）；在Test.cpp的main函数中，我定义了两个链表open和closed分别存放未被扩展的节点和被扩展的节点。深度优先，新生成的有效的子节点存放在open表的开头。每次扩展，拿open表的开头的那个节点来扩展，方法是把open表的头节点移动到closed表的末端，生成的最多4个有效的子节点存放在open表的开头。其他就是比较生成的节点和目标节点是否相等了。

以下代码在win8.1下VS2013中测试成功。

头文件Deep.h：

Deep.cpp：