老调重提,利用SDK实现迷宫算法

我近来重看了数据结构的书,现在的教材还是使用C/C++的编写的算法,编译还是在console mode进行, 如果能把这些数据结构的算法使用在SDK上,那么就可以开发出 Windows 程序的算法程序提高学习,不用在 单调的console mode 中看着冷冰冰的字符来学习数据结构了,这样学习一方面可以学习调用 Windows API 和 Windows编程,另一方面可以学习数据结构. 希望我这样的学习方法对那些初学 Windows 的朋友有一些帮助.

这是使用 SDK 开发出来的迷宫程序(F1 键开始).

迷宫算法还是老路子,回溯法和堆栈实现,我采用的是堆栈实现. 使用双向链表摸拟堆栈,使用一个 ptrFirst 和一个 ptrLast 和作为堆栈的栈底和栈顶指针, 定义一 个堆栈元素结构, 这个结构保存迷宫中的位置.

typedef struct _tagNode {
　　int　　nRow;
　　int　　nColumn;
　　struct _tagNode* next;
　　struct _tagNode* previou;
} Node;定义一个标记数组

BOOL bPass[ Row ][ Column ];　　// Row 和 Column 为迷宫大小.迷宫算法的主要伪代码的实现方式.

A.从开始位置开始,判断小球的各个方向是否可行,若一个方向可行,则向该方向移动.

前进的位置进栈.

条件: 前进方向是墙, 则该方向不能向前.

前进和方向如果是经过的,则该方向不能向前.

if ( CanMove( gnRow, gnColumn, right ) )
　　 {
　　　　 gnColumn += moveRight; // 前进
　　　　 bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置
　　　　 // gnRow, gnColumn 位置入栈.
　　 }
　　 else if ( CanMove( gnRow, gnColumn, left ) ) // right 方不通, 向左.
　　 {
　　　　 gnColumn += moveLeft; // 前进
　　　　 bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置
　　　　 // gnRow, gnColumn 位置入栈.
　　 }
　　 else if ( CanMove( gnRow, gnColumn, forward ) ) // left 方不通, 向前.
　　 {
　　　　 gnColumn += moveForward; // 前进
　　　　 bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置
　　　　 // gnRow, gnColumn 位置入栈.
　　 }
　　 else if ( CanMove( gnRow, gnColumn, back ) ) // forward 方不通, 向后.
　　 {
　　　　 gnColumn += moveBack; // 前进
　　　　 bPass[ gnRow ][ gnColumn ] = TRUE; // 标记通过的位置
　　　　 // gnRow, gnColumn 位置入栈.
　　 }B.各个方向不能可行,退回前一个位置,利用退栈操作,回到 A.

else if ( CanMove( gnRow, gnColumn, back ) )
　　 {}A, B 不断重复, 直到找到出口, 或遍历迷宫(栈空)

if 为迷宫出口
　　　　 bSearch = FALSE;
　　 if 栈为空 // 没有出口,
　　　　 bSearch = FALSE;