#include<stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 70
#define STACK_SIZE  10
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
typedef struct{

 int i;

 int j;  

 ElemType a;
}PassStackElem;

typedef struct{
    PassStackElem * top;
    PassStackElem * base;
    int size;
}PassStack;
bool InitStack(PassStack &S) {
    // 初始化栈
    S.base = (PassStackElem *)malloc(STACK_INIT_SIZE*sizeof(PassStackElem));
    if(!S.base)
        exit(0);
    S.top = S.base;
    S.size = 0;
    return true;
} // InitStack
bool pop(PassStack &S, ElemType &e, int &m, int &n) {
    if(S.top == S.base)
        return false;
    e = --S.top->a;
    m = S.top->i;
    n = S.top->j;
    S.size--;
    return true;
}
bool push(PassStack &S, int v, int m, int n) {
    if(S.top - S.base >= S.size)
    {
        S.base = (PassStackElem *)realloc(S.base, (S.size + STACK_SIZE)*sizeof(PassStackElem));
        if(!S.base)
            exit(0);
        S.top = S.base + S.size;
        S.size += STACK_SIZE;
    }
    S.top->i = m;
    S.top->j = n;
    S.top->a = v;
    S.top++;
    S.size++;
    return true;
} // Push
Status StackEmpty(PassStack &S)
{

 if(S.top==S.base)

 return 1;

 else return 0;
}     //判断空栈
Status find(PassStack s, int m, int n){
    PassStackElem * p = s.top-1;
    int i=1;
    while(i <= s.size){
        if(p->i == m && p->j == n)
            break;
        p--;
        i++;   
    }
    if(i <= s.size)
        return 1;
    else
        return 0;
}
void print(PassStack ps, int *board){
    int m,n,a,i=1;
    while(!StackEmpty(ps)){   
        pop(ps, a, m, n);
        board[8*m+n] = i;
        printf("%d ",board[8*m+n]);
        //board[m][n] = i;
        i++;
    }
    for(i=0; i<8; i++){
        for(int j=0; j<8; j++)
            printf("%d ",board[8*i+j]);
        printf("\n");
    }
}
void explore(ElemType *board,PassStack &ps, int i, int j){
    int m = i;
    int n = j;
    int val;
    push(ps, 0, m, n);
    while(ps.size <= 64){
        if(board[8*m+n] == 0){
            board[8*m+n]++;
            if(i-2>=0 && j+1<=7){
                m = i - 2;
                n = j + 1;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);               
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 1){
            board[8*m+n]++;
            if(i-1>=0 && j+2<=7){
                m = i - 1;
                n = j + 2;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 2){
            board[8*m+n]++;
            if(i+1<=7 && j+2<=7){
                m = i + 1;
                n = j + 2;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 3){
            (board[8*m+n])++;
            if(i+2<=7 && j+1<=7){
                m = i + 2;
                n = j + 1;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 4){
            (board[8*m+n])++;
            if(i+2<=7 && j-1>=0){
                m = i + 2;
                n = j - 1;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 5){
            (board[8*m+n])++;
            if(i+1<=7 && j-2>=0){
                m = i + 1;
                n = j - 2;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 6){
            (board[8*m+n])++;
            if(i-1>=0 && j-2>=0){
                m = i - 1;
                n = j - 2;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 7){
            (board[8*m+n])++;
            if(i-2>=0 && j-1>=0){
                m = i - 2;
                n = j - 1;
                if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；
                }
                else{          //栈中不存在，入栈；
                    board[8*m+n] = 0;
                    val = board[8*m+n];
                    push(ps,val,m,n);
                    i = m;
                    j = n;
                }
            }
        }
        if(board[8*m+n] == 8){
            if(ps.size == 64){
                break;
            }           
            else {
                pop(ps,val,m,n);
            }       
        }
    }
}
int main(){
    PassStack ps;
    int i,j;
    int board[64] = {};
    InitStack(ps);   
    printf("请输入初始位置i和j:（两个不大于7的正整数，包括0）\n");
    scanf("%d%d",&i,&j);
    explore(board, ps, i, j);
    print(ps,board);
    return 0;
}

【马踏棋盘】
*问题描述：将马随机放在国际象棋的8X8棋盘Bo阿rd[0..7,0..7]的某个方格中，马按走棋规则进行移动。要求每个方格上只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线 ，并按求出的行走路线，将数字1，2，…，64依次填入8X8的方阵输出之。
*测试数据：由读者指定,可自行指定一个马的初始位置。
*实现提示：每次在多个可走位置中选择一个进行试探，其余未曾试探过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”(悔棋)使用。并探讨每次选择位置的“最佳策略”，以减少回溯的次数。

//这样怎么还不行？

#include<stdio.h>
#include <stdlib.h>
#define STACK_INIT_SIZE 70
#define STACK_SIZE  10
#define ERROR 0
#define OK 1
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
int board[8][8] = {{}};           //定义棋盘
int tryi[8]={1,-1,-2,2,2,1,-1,-2};/*存储马各个出口位置相对当前位置行下标的增量数组*/
int tryj[8]={2,-2,1,1,-1,-2,2,-1};/*存储马各个出口位置相对当前位置列下标的增量数组*/
typedef struct{

 int i;

 int j;  

 ElemType a;
}PassStackElem;

typedef struct{
    PassStackElem * top;
    PassStackElem * base;
    int size;
}PassStack;
bool InitStack(PassStack &S) {
    // 初始化栈
    S.base = (PassStackElem *)malloc(STACK_INIT_SIZE*sizeof(PassStackElem));
    if(!S.base)
        exit(0);
    S.top = S.base;
    S.size = 0;
    return true;
} // InitStack
bool pop(PassStack &S, ElemType &e, int &m, int &n) {
    if(S.top == S.base)
        return false;
    e = (--S.top)->a;
    m = S.top->i;
    n = S.top->j;
    S.size--;
    return true;
}
bool push(PassStack &S, int v, int m, int n) {
    /*if(S.top - S.base >= S.size)
    {
        S.base = (PassStackElem *)realloc(S.base, (S.size + STACK_SIZE)*sizeof(PassStackElem));
        if(!S.base)
            exit(0);
        S.top = S.base + S.size;
        S.size += STACK_SIZE;
    }*/
    S.top->i = m;
    S.top->j = n;
    S.top->a = v;
    S.top++;
    S.size++;
    return true;
} // Push
Status StackEmpty(PassStack &S)
{
     if(S.top==S.base)
         return 1;
     else {
         printf("栈中有%d个元素",S.size);
         return 0;   
     }
}     //判断空栈
Status find(PassStack s, int m, int n){
    PassStackElem * p = s.top-1;
    int i=1;
    while(i <= s.size){
        if(p->i == m && p->j == n)
            break;
        p--;
        i++;   
    }
    if(i <= s.size)
        return 1;
    else
        return 0;
}
void print(PassStack &ps){
    int m,n,a,i=64;
    printf("%d",--ps.top->a);
    while(!StackEmpty(ps)){   
        pop(ps, a, m, n);
        board[m][n] = i;
        printf("%d ",board[m][n]);
        i--;
    }
    for(i=0; i<8; i++){
        for(int j=0; j<8; j++)
            printf("%d ",board[i][j]);
        printf("\n");
    }
}
void explore(PassStack &ps, int &i, int &j){
    int m = i;
    int n = j;
    int val = 0;
    push(ps, 0, m, n);
    printf("%d",StackEmpty(ps));

    while(ps.size <= 64){
        //printf("%d",StackEmpty(ps));
        while(val < 8){
            board[m][n]++;
            (ps.top-1)->a = board[m][n];
            m = i + tryi[val];
            n = j + tryj[val];
            if(find(ps,m,n)){
                    m = i;
                    n = j;    //栈中已存在，恢复下标；               
                }
            else{          //栈中不存在，入栈；
                board[m][n] = 0;
                push(ps,0,m,n);               
                i = m;
                j = n;
            }
            val = board[m][n];
        }
        printf("%d",StackEmpty(ps));
        while(val = 8){
            if(ps.size == 64){
                printf("%d",StackEmpty(ps));
            }           
            else {
                pop(ps,val,m,n);
            }       
        }
           
    }
}
int main(){
    PassStack ps;
    int i,j;       
    printf("请输入初始位置i和j:（两个不大于7的正整数，包括0）\n");
    scanf("%d%d",&i,&j);
    InitStack(ps);
    explore(ps, i, j);
    //printf("%d",StackEmpty(ps));
    print(ps);
    return 0;
}