8皇后问题用基本数据结构实现（不用stl）

  1 #include <iostream>
  2 using namespace std;
  3 
  4 #define STACKSIZE 256
  5 
  6 int Result;//记录结果
  7 
  8 typedef struct
  9 {
 10     int row;
 11     int col;
 12 }QueenPlace;
 13 
 14 typedef struct
 15 {
 16     QueenPlace* pBase;
 17     QueenPlace* pTop;
 18     int size;
 19     int now_size;
 20 }SeqStack;
 21 
 22 SeqStack StackQueen;
 23 
 24 bool InitStack(SeqStack& S)
 25 {
 26     S.pBase = (QueenPlace*)malloc(sizeof(QueenPlace) * 256);
 27     if (S.pBase == NULL) return false;
 28     S.size = 254;
 29     S.now_size = 0;
 30     S.pTop = S.pBase + 1;
 31     return true;
 32 }
 33 
 34 void DestoryStack(SeqStack& S)
 35 {
 36     if (S.pBase != NULL)
 37     {
 38         free(S.pBase);
 39         S.pBase = NULL;
 40     }
 41     S.pTop = NULL;
 42     S.size = 0;
 43     S.now_size = 0;
 44 }
 45 
 46 bool Push(SeqStack& S, QueenPlace e)
 47 {
 48     //假如栈超范围
 49     if (S.now_size >= S.size)
 50     {
 51         S.pBase = (QueenPlace*)realloc(S.pBase, sizeof(QueenPlace) * (256+STACKSIZE));
 52         if (S.pBase == NULL) return false;
 53         S.pTop = S.pBase + S.size + 1;
 54         S.size += 256;
 55     }
 56     S.pTop->row = e.row;
 57     S.pTop->col = e.col;
 58     S.now_size++;
 59     S.pTop++;
 60     return true;
 61 }
 62 
 63 bool IsEmpty(SeqStack& S)
 64 {
 65     if (S.pBase == S.pTop)return false;
 66     return true;
 67 }
 68 
 69 bool GetTop(SeqStack& S, QueenPlace& e)
 70 {
 71     S.pTop--;
 72     if (IsEmpty(S) == false) return false;
 73     e.col = S.pTop->col;
 74     e.row = S.pTop->row;
 75     S.now_size--;
 76 }
 77 
 78 bool Pop(SeqStack& S)
 79 {
 80     S.pTop--;
 81     if (IsEmpty(S) == false) return false;
 82     S.now_size--;
 83     return true;
 84 }
 85 
 86 void OutPutResult(SeqStack& S, int N)
 87 {
 88     QueenPlace* e = S.pBase+1;
 89     for (int i = 1; i <= N; i++)
 90     {
 91         cout << "(" << e->row << "," << e->col << ")";
 92         e = S.pBase + 1 + i;
 93     }
 94     cout << endl;
 95 }
 96 
 97 bool JudgeQueenConfliction(SeqStack & S,QueenPlace e)
 98 {
 99     int CurCol = e.col;
100     int CurRow = e.row;
101 
102     QueenPlace* CurQueen = S.pBase+1;
103     while (CurQueen < S.pTop-1)
104     {
105         int pCol = CurQueen->col;
106         int pRow = CurQueen->row;
107 
108         if (pCol == CurCol) return false;
109         if (abs(pCol - CurCol) == abs(pRow - CurRow)) return false;
110 
111         CurQueen++;
112     }
113     return true;
114 }
115 
116 void SearchQueenPlace(int row)
117 {
118     for (int i = 1; i <= 8; i++)
119     {
120         QueenPlace CurQueen;
121         CurQueen.row = row;
122         CurQueen.col = i;
123 
124         Push(StackQueen, CurQueen);
125         bool ret=JudgeQueenConfliction(StackQueen, CurQueen);
126         if (ret == true)
127         {
128             if (row < 8) SearchQueenPlace(row + 1);
129             else
130             {
131                 OutPutResult(StackQueen, 8);
132                 Result++;
133             }
134         }
135         Pop(StackQueen);
136     }
137 }
138 
139 
140 
141 int main()
142 {
143     Result= 0;
144     InitStack(StackQueen);
145     SearchQueenPlace(1);
146     cout << Result;
147     DestoryStack(StackQueen);
148 }

完全手搓栈并完成

回溯算法的使用