算法基础

注：为了不离开本节讨论的重点--栈，迷宫的自动生成以后重新写。这里用简单的二维数组代替，手动迷宫，呵呵！
MAP里面0代表墙（通不过），1代表空格（可通过）代码中每一步有详细注释。欢迎大家交流，嘻嘻。
001// DataStructure_ZJC.cpp : 定义控制台应用程序的入口点。 
002/*
003二. 栈的应用-迷宫解题
004*/ 
005#include "stdafx.h" 
006#include<stdio.h> 
007#include<malloc.h> 
008#include<stdlib.h> 
009   
010#define TRUE  1  
011#define FALSE 0 
012#define OK    1 
013#define ERROR 0 
014#define INFEASIBLE -1 
015#define OVERFLOW   -2 
016   
017typedef struct 
018{ 
019    int x;          //x坐标 
020    int y;          //y坐标 
021}Postype;           //坐标类型 
022typedef struct 
023{ 
024    //int ord;      //通道块在路径上的序号 
025    //Postype seat; //通道块在迷宫中的坐标 
026    //int di;       //从此通道块走向下一通道块的“方向” 
027    int x; 
028    int y;          //元素坐标 
029   
030//  bool track;     //是否已经走过 
031}ElemType;          //栈的元素类型 
032   
033int MAP[9][9] =     /*二维数组就够用了，先从简单的地图开始*/ 
034{   
035   //0 1 2 3 4 5 6 7 8 
036        
037     0,0,0,0,0,0,0,0,0, 
038     0,1,0,0,1,1,1,1,0, 
039     0,1,0,0,1,1,1,1,0, 
040     0,1,1,1,1,0,1,1,0, 
041     0,1,0,1,0,1,1,1,0, 
042     0,1,0,1,0,1,1,1,0, 
043     0,1,0,1,0,1,1,1,0, 
044     0,0,0,1,1,1,1,1,0, 
045     0,0,0,0,0,0,0,0,0, 
046   
047   
048}; 
049/*-------------------------------------栈的元素类型定义完毕-------------------------*/ 
050typedef int Status;     //函数返回值 
051   
052#define STACK_INIT_SIZE 100     // 栈的初始大小 
053#define STACK_INCREMENT 10      // 每次增加的空间大小 
054   
055   
056//下面给出栈的相关定义 
057typedef struct 
058{ 
059    ElemType *base;     //在构造栈之前和销毁之后，base的值为NULL 
060    ElemType *top;      //栈顶指针 
061    int stacksize;      //当前已分配的存储空间，以元素为单位 
062}ZJC_Stack; 
063   
064//--------------------------------------栈基本操作的算法部分--------------------------  
065//栈的初始化 
066Status InitStack(ZJC_Stack &S)   
067{ 
068        
069    S.base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));    //分配内存空间 
070    if(!S.base)           
071        exit(OVERFLOW); 
072       
073    else                //否则分配成功 
074    { 
075        S.top = S.base;   
076        S.stacksize  = STACK_INIT_SIZE;   
077        return  OK; 
078    } 
079   
080} 
081                        //获得栈顶元素 
082ElemType GetTop(ZJC_Stack S) 
083{     
084    if(S.top == S.base ) 
085        exit(ERROR);      
086    return *(S.top - 1);      
087} 
088//压栈 
089Status Push(ZJC_Stack &S,ElemType e) 
090{                     
091    if(S.top - S.base >= S.stacksize)      
092    { 
093        S.base = (ElemType*)realloc(S.base,(S.stacksize + STACK_INCREMENT) * sizeof(ElemType)); 
094        if(!S.base) 
095            exit(OVERFLOW); 
096        S.stacksize += STACK_INCREMENT;       
097        S.top = S.base + S.stacksize;        
098    } 
099    *S.top++ = e; 
100    return OK; 
101} 
102void Print_Path(ZJC_Stack S)    //打印出栈中的元素 
103{ 
104    printf("\n寻路完成..路径坐标值如下：......\n"); 
105    ElemType *p = S.base;       //首先p指向栈底指针 
106    ElemType temp;    
107    while( p != S.top)          //只要没有到顶端，指针就移动，然后输出元素值 
108    { 
109        temp = *p; 
110        printf("\n路径 x = %d , y = %d",temp.x,temp.y); 
111        p++;         
112    } 
113} 
114   
115//出栈函数 
116Status Pop(ZJC_Stack &S,ElemType &e) 
117{ 
118    if(S.top == S.base      )   //空栈，返回错误 
119    return ERROR; 
120    else                        //不是空栈 
121    {        
122        e = * --S.top; 
123        return OK; 
124    } 
125} 
126void PathAddToStack(int i,int j,ElemType temp,ZJC_Stack &robot)     //因为要修改值，所以取地址，开始没加取地址符号，栈顶元素一直是(1,1) 
127{ 
128    temp.x = i,temp.y = j; 
129    Push(robot,temp); 
130    MAP[i][j] = 2;                      //标记已经走过该格子了,当初想是否需要用其他标记，实际上不需要的，既然标记2，那么证明当然可以走过(不是墙)! 
131} 
132void MAZH_SOLVE(int endx,int endy)      //解决迷宫问题函数,参数为终点的坐标 
133{                            
134    int i = 1,j = 1;                    //起点坐标   
135    ZJC_Stack robot;                    //定义栈； 
136    if(InitStack( robot ) )             //初始化栈 
137        printf("\n栈的初始化完成....\n");                                       
138    ElemType CurrentPos ;               //当前位置        
139    ElemType start;                     //初始位置的相关信息 
140    ElemType temp;                      //暂时用的 
141    start.x = i; 
142    start.y = j; 
143    temp = start; 
144    //start.track = true;               //Robot站在初始位置，初始位置已经走过 
145    MAP[i][j] = 2;                      //走过的标记为2            
146    Push(robot,start);                  //初始位置入栈 
147    printf("\n开始寻路....\n");  
148    do                                  //主要寻路算法： 
149    { 
150           
151          CurrentPos = GetTop(robot); 
152          i = CurrentPos.x; 
153          j = CurrentPos.y; 
154          printf(" \n寻路过程如下栈顶元素的 x = %d ,y = %d....\n",i,j); 
155          if(MAP[i][j+1] == 1)          //表明向下一格走得通 
156          {                                      
157              printf("\n向下能走动");    //向下前进一步，压栈，标记 
158              j++; 
159              PathAddToStack(i,j,temp,robot);                            
160          } 
161          else if( MAP[i + 1][j] == 1)        
162          { 
163               printf("\n向右能走动"); 
164                i++;                          
165                PathAddToStack(i,j,temp,robot); 
166          } 
167          else  if(MAP[i - 1][j] == 1)         
168          { 
169               printf("\n向左能走动"); 
170                i--;                          
171                PathAddToStack(i,j,temp,robot); 
172          } 
173          else if(MAP[i][j - 1] == 1)         
174          { 
175               printf("\n向上能走动"); 
176                j--;                          
177                PathAddToStack(i,j,temp,robot); 
178          } 
179          else  //都走不动 
180          { 
181               printf("\n都走不动，退栈");                          
182               Pop(robot,temp); 
183          } 
184       
185    }while( GetTop(robot).x != endx || GetTop(robot).y != endy);        //只要栈顶元素的x,y不等于终点坐标的x,y,则一直循环找路径 
186    printf("\n完成!\n"); 
187    Print_Path(robot);                  //打印出坐标值                              
188} 
189int _tmain(int argc, _TCHAR* argv[])    //入口函数 
190{     
191    MAZH_SOLVE(7,7);      
192    return 0; 
193} 
194   
195   