两个必要张

  1 //===================MCC_Header.h==================
  2     //头文件支持
  3 #include<iostream>
  4 #include<iomanip>
  5 #include<vector>
  6     using namespace std;
  7 //用typedef定义类型
  8 typedef vector<char> Collection;
  9 typedef vector<vector<char> > Matrix;
 10 //相关函数
 11 //输出集合
 12 void Coll_Print(Collection C);
 13 //输出集类
 14 void Matrix_Print(Matrix M);
 15 //定位元素在集合中的位置
 16 int Coll_ChLocate(Collection C, char ch);
 17 //判断字符元素是否属于集合
 18 bool Coll_ChFind(Collection Ca, char ch);
 19 //判断集合(一维向量)是否属于集类(二维向量)
 20 bool Matrix_ColFind(Matrix M, Collection C);
 21 //判断集合是否包含于集合
 22 bool Coll_Belong(Collection Ca, Collection Cb);
 23 //集合交
 24 Collection Coll_Or(Collection Ca, Collection Cb);
 25 //集合并
 26 Collection Coll_And(Collection Ca, Collection Cb);
 27 //集类并
 28 Matrix Matrix_Or(Matrix Ma, Matrix Mb);
 29 //集类减运算
 30 Matrix Matrix_Minus(Matrix Ma, Matrix Mb);
 31 //关系矩阵算法
 32 void Make_MCC(Collection Ca, vector<Collection> &pi, vector<vector<bool> > R);
 33     //=================MCC_Function.cpp===============
 34 #include"MCC_Header.h"
 35     //输出集合
 36  void Coll_Print(Collection C)
 37 {
 38     cout << "{";
 39     for (int i = 0; i < C.size(); i++)
 40     {
 41         cout << C[i];
 42         if (i != C.size() - 1)
 43             cout << ",";
 44     }
 45     cout << "}";
 46 }
 47 //输出集类
 48 void Matrix_Print(Matrix M)
 49 {
 50     cout << "{  ";
 51     for (int i = 0; i < M.size(); i++)
 52     {
 53         Coll_Print(M[i]);
 54         if (i != M.size() - 1)
 55             cout << ",";
 56     }
 57     cout << "  }" << endl;
 58 
 59 }
 60 //定位元素在集合中的位置
 61 int Coll_ChLocate(Collection C, char ch)
 62 {
 63     for (int i = 0; i < C.size(); i++)
 64         if (C[i] == ch)
 65             return i;
 66 
 67     return -1;
 68 }
 69 //判断字符元素是否属于集合
 70 bool Coll_ChFind(Collection Ca, char ch)
 71 {
 72     for (int i = 0; i < Ca.size(); i++)
 73     {
 74         if (Ca[i] == ch)
 75             return true;
 76     }
 77 
 78     return false;
 79 }
 80 //判断集合(一维向量)是否属于集类(二维向量)
 81 bool Matrix_ColFind(Matrix M, Collection C)
 82 {
 83     for (int i = 0; i < M.size(); i++)
 84         if (M[i] == C)
 85             return true;
 86 
 87     return false;
 88 }
 89 //判断集合Ca是否包含于集合Cb
 90 bool Coll_Belong(Collection Ca, Collection Cb)
 91 {
 92     if (Ca.size() > Cb.size())
 93         return false;
 94     else
 95     {
 96         for (int i = 0; i < Ca.size(); i++)
 97         {
 98             if (!Coll_ChFind(Cb, Ca[i]))
 99                 return false;
100         }
101 
102         return false;
103     }
104 
105 }
106 //集合交
107 Collection Coll_Or(Collection Ca, Collection Cb)
108 {
109     int min = (Ca.size() > Cb.size() ? Cb.size() : Ca.size());
110 
111     Collection CB = (Ca.size() > Cb.size() ? Ca : Cb);
112     Collection CS = (Ca.size() > Cb.size() ? Cb : Ca);
113 
114     Collection Cc;
115 
116     for (int i = 0; i < min; i++)
117     {
118         if (Coll_ChFind(CB, CS[i]))
119             Cc.push_back(CS[i]);
120     }
121 
122     return Cc;
123 }
124 //集合并
125 Collection Coll_And(Collection Ca, Collection Cb)
126 {
127     int min = (Ca.size() > Cb.size() ? Cb.size() : Ca.size());
128 
129     Collection CB = (Ca.size() > Cb.size() ? Ca : Cb);
130     Collection CS = (Ca.size() > Cb.size() ? Cb : Ca);
131 
132 
133     for (int i = 0; i < min; i++)
134     {
135         if (!Coll_ChFind(CB, CS[i]))
136             CB.push_back(CS[i]);
137     }
138     return CB;
139 }
140 //集类并
141 Matrix Matrix_Or(Matrix Ma, Matrix Mb)
142 {
143     int min = (Ma.size() > Mb.size() ? Mb.size() : Ma.size());
144     Matrix MB = (Ma.size() > Mb.size() ? Ma : Mb);
145     Matrix MS = (Ma.size() > Mb.size() ? Mb : Ma);
146 
147     for (int i = 0; i < min; i++)
148         if (!Matrix_ColFind(MB, MS[i]))
149             MB.push_back(MS[i]);
150 
151     return MB;
152 }
153 //集类减运算
154 Matrix Matrix_Minus(Matrix Ma, Matrix Mb)
155 {
156     int i, min = (Ma.size() > Mb.size() ? Mb.size() : Ma.size());
157     Matrix Mc;
158 
159     for (i = 0; i < min; i++)
160     {
161         if (!Matrix_ColFind(Mb, Ma[i]))
162             Mc.push_back(Ma[i]);
163     }
164     if (min == Ma.size())
165         return Mc;
166     else
167     {
168         for (; i < Ma.size(); i++)
169             Mc.push_back(Ma[i]);
170         return Mc;
171     }
172 }
173 //关系矩阵算法
174 void Make_MCC(Collection Ca, vector<Collection> &pi, vector<vector<bool> > R)
175 {
176     int n = Ca.size(), i, j, k;
177     Collection A = Ca, Xi;
178     Collection S, S1, S2, Col_temp1, Col_temp2;
179     vector<Collection> Mat_temp1, Mat_temp2;
180 
181     if (n == 1)
182     {
183         cout << "Can't Creat the MCC!
";
184         return;
185     }
186     //关系矩阵算法(详参见教材P108)
187     for (i = n - 1; i > 1; i--)
188     {
189         Xi.clear();
190         Xi.push_back(Ca[i - 1]);
191 
192         A.clear();
193         for (j = i + 1; j <= n; j++)
194         {
195             if (R[j - 1][i - 1])
196                 A.push_back(Ca[j - 1]);
197         }
198         for (k = 0; k < pi.size(); k++)
199         {
200             S = pi[k];
201             if ((Coll_And(S, A)).size() != 0)
202             {
203                 Col_temp1.clear();
204                 Col_temp2.clear();
205 
206                 Col_temp1 = Coll_And(S, A);
207                 Col_temp2 = Coll_Or(Xi, Col_temp1);
208 
209                 Mat_temp1.clear();
210                 Mat_temp1.push_back(Col_temp2);
211 
212 
213                 pi = Matrix_Or(pi, Mat_temp1);
214             }
215         }
216         for (i = 0; i < pi.size(); i++)
217         {
218             S1.clear();
219             S1 = pi[i];
220             for (j = 0; j < pi.size(); j++)
221             {
222                 S2.clear();
223                 S2 = pi[j];
224                 if (Coll_Belong(S1, S2))
225                 {
226                     Mat_temp2.clear();
227                     Mat_temp2.push_back(S1);
228 
229                     pi = Matrix_Minus(pi, Mat_temp2);
230                 }
231             }
232         }
233     }
234 }
235 #include"MCC_Header.h"
236 int main()
237 {
238     Collection A;
239     Matrix pi;
240     vector<vector<bool> > R;
241     char ch, ch1, ch2;
242     int number, i, j;
243     //输入A中元素的个数
244     cout << "Please Input The Number Of A's Elements:
";
245     cin >> number;
246     //输入A中的各个元素
247     cout << "Please Input Each Element Of A:
";
248     for (i = 0; i < number; i++)
249     {
250         cin >> ch;
251         A.push_back(ch);
252     }
253     //输出集合A
254     cout << "Output A As Followed:
";
255     cout << "A=";
256     Coll_Print(A);
257     cout << endl;
258     //初始化关系矩阵R并输出
259     vector<bool> bl_temp(A.size(), 0);
260     for (i = 0; i < A.size(); i++)
261         R.push_back(bl_temp);
262     cout << "Initialize Matrix R AS 0 Matrix And Output As Followed:
";
263     for (i = 0; i < R.size(); i++)
264     {
265         for (j = 0; j < R[0].size(); j++)
266             cout << R[i][j] << " ";
267         cout << endl;
268     }
269     //请输入序偶(以#字符结束输入)来重置矩阵并输出
270     cout << "Now,Type The T_Char To ReInitialize R:
";
271     while (cin >> ch1 >> ch2 && ch1 != '#')
272     {
273         R[Coll_ChLocate(A, ch1)][Coll_ChLocate(A, ch2)] = 1;
274     }
275     cout << "Output Matrix R as Followed:
";
276     for (i = 0; i < R.size(); i++)
277     {
278         for (j = 0; j < R[0].size(); j++)
279             cout << R[i][j] << " ";
280         cout << endl;
281     }
282     //初始化pi并输出
283     vector<char> ch_temp;
284     for (i = 0; i < A.size(); i++)
285     {
286         ch_temp.clear();
287         ch_temp.push_back(A[i]);
288         pi.push_back(ch_temp);
289     }
290     cout << "Initialize Matrix pi And Output As Followed:
";
291     cout << "pi=
";
292     Matrix_Print(pi);
293     //调用关系矩阵函数
294     Make_MCC(A, pi, R);
295     cout << "The Maximal_Consistent_Class Have Been Created As Followed:
";
296     for (i = 0; i < pi.size(); i++)
297     {
298         Coll_Print(pi[i]);
299         cout << endl;
300     }
301     return 0;
302 }

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 typedef enum { ERROR, OK } Status;
  4 typedef struct
  5 {
  6     int row, line;
  7 }PosType;
  8 
  9 typedef struct
 10 {
 11     int  di, ord;
 12     PosType seat;
 13 }SElemType;
 14 
 15 typedef struct
 16 {
 17     SElemType * base;
 18     SElemType * top;
 19     int        stacksize;
 20 }SqStack;
 21 
 22 Status InitStack(SqStack &S);
 23 Status Push(SqStack &S, SElemType &a);
 24 Status Pop(SqStack &S, SElemType &a);
 25 Status StackEmpty(SqStack S);
 26 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end);
 27 void Initmaze(int maze[12][12], int size);
 28 void printmaze(int maze[12][12], int size);
 29 Status Pass(int maze[12][12], PosType CurPos);
 30 void Markfoot(int maze[12][12], PosType CurPos);
 31 PosType NextPos(PosType CurPos, int Dir);
 32 void printpath(int maze[12][12], SqStack S, int size);
 33 void main(void)
 34 {
 35     SqStack S;
 36     int size, maze[12][12];
 37     for (int n = 0; n < 10; n++)
 38     {
 39         printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于50):
");
 40         scanf("%d", &size);
 41         if (size < 1 || size>10)
 42         { 
 43             printf("输入错误!");
 44             return;
 45         }
 46         Initmaze(maze, size);
 47         printmaze(maze, size);
 48         PosType start, end;
 49         printf("输入入口行坐标和列坐标:");
 50         scanf("%d", &start.row); 
 51         scanf("%d", &start.line);
 52         printf("输入出口行坐标和列坐标:");
 53         scanf("%d", &end.row);
 54         scanf("%d", &end.line);
 55         if (MazePath(maze, S, start, end))
 56             printpath(maze, S, size);
 57         else
 58             printf("找不到通路!

");
 59     }
 60 }
 61 Status MazePath(int maze[12][12], SqStack &S, PosType start, PosType end)
 62 {
 63     PosType curpos;
 64     int curstep;
 65     SElemType e;
 66     InitStack(S);
 67     curpos = start;
 68     curstep = 1;
 69     do {
 70         if (Pass(maze, curpos))
 71         {
 72             Markfoot(maze, curpos);
 73             e.di = 1;
 74             e.ord = curstep;
 75             e.seat = curpos;
 76             Push(S, e);
 77             if (curpos.row == end.row && curpos.line == end.line)
 78                 return OK;
 79             curpos = NextPos(curpos, 1);
 80             curstep++;
 81         }
 82         else
 83         {
 84             if (!StackEmpty(S))
 85             {
 86                 Pop(S, e);
 87                 while (e.di == 4 && !StackEmpty(S))
 88                 {
 89                     Markfoot(maze, e.seat);
 90                     Pop(S, e);
 91                 }
 92                 if (e.di < 4)
 93                 {
 94                     e.di++;
 95                     Push(S, e);
 96                     curpos = NextPos(e.seat, e.di);
 97                 }
 98             }
 99         }
100     } while (!StackEmpty(S));
101     return ERROR;
102 }
103 void Initmaze(int maze[12][12], int size)
104 {
105     char select;
106     printf("选择创建方式 A:自动生成 B:手动创建
");
107 label:scanf("%c", &select);
108     if (select == 'a' || select == 'A')
109     {
110         for (int i = 0; i < size + 2; i++)
111             maze[0][i] = 1;
112         for (int i = 1; i < size + 1; i++)
113         {
114             maze[i][0] = 1;
115             for (int j = 1; j < size + 1; j++)
116                 maze[i][j] = rand() % 2;
117             maze[i][size + 1] = 1;
118         }
119         for (int i = 0; i < size + 2; i++)
120             maze[size + 1][i] = 1;
121     }
122     else if (select == 'b' || select == 'B')
123     {
124         printf("按行输入%d*%d数据,0代表可通,1代表不可通(每行以Enter结束):
", size, size);
125         for (int i = 0; i < size + 2; i++)maze[0][i] = 1;
126         for (int i = 1; i < size + 1; i++)
127         {
128             maze[i][0] = 1;
129             for (int j = 1; j < size + 1; j++)
130                 scanf("%d", &maze[i][j]);
131             maze[i][size + 1] = 1;
132         }
133         for (int i = 0; i < size + 2; i++)
134             maze[size + 1][i] = 1;
135     }
136     else if (select == '
')
137         goto label;
138     else printf("输入错误!");
139 }
140 void printmaze(int maze[12][12], int size)//
141 {
142     printf("

");
143     printf("显示所建的迷宫(#表示外面的墙):
");
144     for (int i = 0; i < size + 2; i++)
145         printf("%c ", '#');
146     printf("
");
147     for (int i = 1; i < size + 1; i++)
148     {
149         printf("%c ", '#');
150         for (int j = 1; j < size + 1; j++)
151         {
152             printf("%d ", maze[i][j]);
153         }
154         printf("%c", '#');
155         printf("
");
156     }
157     for (int i = 0; i < size + 2; i++)
158         printf("%c ", '#');
159     printf("
");
160 
161 }
162 
163 void printpath(int maze[12][12], SqStack S, int size)
164 {
165     printf("

通路路径为:
");
166     SElemType * p = S.base;
167     while (p != S.top)
168     {
169         maze[p->seat.row][p->seat.line] = 2;
170         p++;
171     }
172     for (int i = 0; i < size + 2; i++)
173         printf("%c ", '#'); printf("
");
174     for (int i = 1; i < size + 1; i++)
175     {
176         printf("%c ", '#');
177         for (int j = 1; j < size + 1; j++)
178         {
179             if (maze[i][j] == 2) 
180                 printf("%c ", '0');
181             else              
182                 printf(" ");
183         }
184         printf("%c", '#');
185         printf("
");
186     }
187     for (int i = 0; i < size + 2; i++)
188         printf("%c ", '#'); 
189     printf("

");
190 
191 }
192 
193 Status Pass(int maze[12][12], PosType CurPos)
194 {
195     if (maze[CurPos.row][CurPos.line] == 0)
196         return OK;
197     else 
198         return ERROR;
199 }
200 void Markfoot(int maze[12][12], PosType CurPos)
201 {
202     maze[CurPos.row][CurPos.line] = 1;
203 }
204 PosType NextPos(PosType CurPos, int Dir)
205 {
206     PosType ReturnPos;
207     switch (Dir)
208     {
209     case 1:
210         ReturnPos.row = CurPos.row;
211         ReturnPos.line = CurPos.line + 1;
212         break;
213     case 2:
214         ReturnPos.row = CurPos.row + 1;
215         ReturnPos.line = CurPos.line;
216         break;
217     case 3:
218         ReturnPos.row = CurPos.row;
219         ReturnPos.line = CurPos.line - 1;
220         break;
221     case 4:
222         ReturnPos.row = CurPos.row - 1;
223         ReturnPos.line = CurPos.line;
224         break;
225     }
226     return ReturnPos;
227 }
228 Status InitStack(SqStack &S)
229 {
230     S.base = (SElemType *) malloc(100 * sizeof(SElemType));
231     if (!S.base)return ERROR;
232     S.top = S.base;
233     S.stacksize = 100;
234     return OK;
235 }
236 Status Push(SqStack &S, SElemType &a)
237 {
238     *S.top++ = a;
239     return OK;
240 }
241 Status Pop(SqStack &S, SElemType &a)
242 {
243     if (S.top == S.base)
244         return ERROR;
245     a = *--S.top;
246     return OK;
247 }
248 
249 Status StackEmpty(SqStack S)
250 {
251     if (S.top == S.base)
252         return OK;
253     return ERROR;
254 }