「データ構造とアルゴリズム分析」コース設計——食いしん坊問題

88006 ワード

中国鉱業大学信控学院
 
 
//*文献参照*/
https://blog.csdn.net/Fdog_/articale/detail/102625969
https://blog.csdn.net/DY_1024/articale/detail/78841757
 
一、問題の説明
 
データ構造を考えたデザインで、食いしん坊のミニゲームを実現しました.
 
二、需要分析
 
まず、どのようにウィンドウズウィンドウを設計するかを考えて、結果をリアルタイムに表示します.
そして蛇の体は一節だと考えられています.この時最も連想しやすいデータ構造は順番表、チェーンです.蛇を順番表やチェーン表に並べて食べたら、後で食べ物を食べたら、体が長くなります.これは挿入の操作に関わるので、より効率的にチェーンで私達の蛇の部分を実現します.最初は蛇の体を四つの結点に合わせてスクリーンにプリントしました.
蛇の動きについては、画面の上で蛇の動きは体全体が前に向かって一つの単位を移動するように見えますが、その原理は私達がスクリーンのもう一つのところで蛇を新たに印刷して、また前の蛇の体を取り除くことです.
食べ物の発生については、ランダムに地図の中でノードが発生し、蛇の頭座標と食べ物の座標が重複すると、食べ物が消失し、蛇の体が長くなり、蛇のノード数が一つ増えます.
蛇のいくつかの状態、正常状態:蛇頭ノードの座標は壁の座標と自分の体の座標と一致していません.
自分で殺される:蛇の頭の座標と蛇の体の座標が重なって、
壁にぶつかる:蛇の頭の座標と壁の座標が重なる.
 
三、アルゴリズムの設計
 
1.関連変数
1 1.    。
2 int JudgeSum = 0;            //      
3 int Pause = 200000000;       //    (    )
4 int * PJ = &JudgeDirection;  //           
5 nakebody *end = NULL;        //   
 
2.チェーンを作って、蛇を食べたい体はどうやって保存するかがゲームの中心です.だから、チェーンを使って蛇の体を保存します.そうしたら、いつでも蛇の体のデータを知ることができます.
1 typedef struct Snakebody
2 {
3     int x, y;          //     
4     struct Snakebody *next;//          
5 }Snakebody;           //  typedef  Snakebody    struct Snakebody
 
3.食べ物の座標を記録します.
1 typedef struct Snakexy
2 {
3     int x;
4     int y;
5 }Snakexy; //      
 
4.初期画面とゲーム地図を図のように描きます.
 1 #include
 2 #define HEIGHT  20  //      
 3 #define WIDTH   40  //      
 4 #define PRINTF  printf("■");
 5 #define LINE    printf("
"); 6 #define EMPTY printf(" "); // 7 void Front(); // 8 void DeawMap(); // 9 10 void Front() 11 { 12 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_BLUE);// 13 MoveCursor(18, 15); 14 printf(" ......"); 15 for (int i = 0; i <= 3000000000; i++) {} 16 system("cls");// 17 } 18 void DeawMap() 19 { 20 for (int i = 0; i < WIDTH; i++)PRINTF LINE // 21 for (int i = 1; i < HEIGHT - 1; i++) // 22 { 23 for (int j = 0; j < WIDTH; j++) 24 { 25 if (j == 0 || j == WIDTH - 1 || j == WIDTH - 10) 26 { 27 PRINTF 28 if (j == WIDTH - 1)LINE 29 } 30 else EMPTY 31 } 32 } 33 for (int i = 0; i < WIDTH; i++)PRINTF LINE // 34 }
Set Consolie TextAttribute()関数は、API設定フォントの色と背景色の関数です.パラメータテーブルには2つの属性(属性間用、仕切り)が使用されていますが、システム()とは異なり、SetConsolie TextAttribute()は界面の様々な色を変えることができます.
 
5.蛇の体を初期化し、最初は頭だけではなく、体をいくつか作らなければなりません.
 1 Snakebody *Phead = NULL;    //            
 2 Snakebody *Phead_1 = NULL;  //    
 3 Snakebody *Pbady = NULL;    //    
 4 void ISnake();             //     
 5 void ISnake()
 6 {
 7     for (int i = 0; i < 5; i++)//           
 8     {
 9         Pbady = (Snakebody*)malloc(sizeof(Snakebody));//    
10         Pbady->x = 5 - i;
11         Pbady->y = 5;
12         if (Phead == NULL)
13         {
14             Phead = Pbady;
15         }
16         else
17         {
18             end->next = Pbady;
19         }
20         Pbady->next = NULL;
21         end = Pbady;
22     }
23     Phead_1 = Phead;
24     while (Phead_1->next != NULL)//    
25     {
26         MoveCursor(Phead_1->x, Phead_1->y);
27         PRINTF
28             Phead_1 = Phead_1->next;
29     }
30 }
 
6.食べ物を作り、ランダムに食べ物を作り、体と体重が合うと再びランダムに食べ物を作る.
 1 #include
 2 int sum = 0;     //    
 3 Snakexy * Food = NULL;          //      
 4 void FoodRand();    //    
 5 void FoodRand()
 6 {
 7     srand((int)time(0));
 8     int x = rand() % 27 + 2;//     
 9     int y = rand() % 17 + 2;
10     Phead_1 = Phead;
11     for (int i = 0; i <= 200; i++)
12     {
13         if (Phead_1->x == x && Phead_1->y == y)
14         {
15             x = rand() % 27 + 2;
16             y = rand() % 17 + 2;
17         }
18         else
19         {
20             Phead_1 = Phead_1->next;
21         }
22         if (Phead_1->next == NULL)
23         {
24             break;
25         }
26     }
27     MoveCursor(x, y);
28     PRINTF
29         Food = (Snakexy*)malloc(sizeof(Snakexy));
30     Food->x = x;
31     Food->y = y;
32     MoveCursor(33, 5);
33     printf("  ");
34     Showf();
35     sum++;
36     SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);//  
37 }
rand関数は、[m,n]の範囲内の乱数numを生成する場合、intnum=rand()%(n-m+1)+mを利用する疑似乱数を取得する機能です.
 
7.ゲームの更新と一時停止は、回車を押してゲームを一時停止することができます.
 1 int JudgeDirection = 4;   //    
 2 void ControlMove();    //       
 3 void ControlMove()
 4 {
 5     if (GetAsyncKeyState(VK_UP) && 0x8000)
 6     {
 7         if (JudgeDirection == 2)
 8         {
 9         }
10         else
11         {
12             JudgeDirection = 1;
13         }
14     }
15     if (GetAsyncKeyState(VK_DOWN) && 0x8000)
16     {
17         if (JudgeDirection == 1)
18         {
19         }
20         else
21         {
22             JudgeDirection = 2;
23         }
24     }
25     if (GetAsyncKeyState(VK_RIGHT) && 0x8000)
26     {
27         if (JudgeDirection == 3)
28         {
29         }
30         else
31         {
32             JudgeDirection = 4;
33         }
34     }
35     if (GetAsyncKeyState(VK_LEFT) && 0x8000)
36     {
37         if (JudgeDirection == 4)
38         {
39         }
40         else
41         {
42             JudgeDirection = 3;
43         }
44     }
45     if (GetAsyncKeyState(VK_RETURN) && 0x0D)//    
46     {
47         while (1)
48         {
49             if (GetAsyncKeyState(VK_RETURN) && 0x0D)//         
50             {
51                 break;
52             }
53         }
54     }
55 }
Get Arcync KeyState()は、ユーザーが現在キーボード上のキーを押したかどうかを確認します.
 
8.スコアと難易度を表示し、スコアと難易度を更新します.
 1 int sum = 0;     //    
 2 int Hard = 0;     //    
 3 void Showf();                   //       
 4 void Showf()
 5 {
 6     SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_BLUE);//  
 7     MoveCursor(33, 5);
 8     printf("  :%d", sum);
 9     MoveCursor(33, 6);
10     printf("  :%d", Hard);
11 }
 
9.カーソルを移動して、ゲームが点滅しない理由は、一度の地図を描いてからカーソルの点で目標点を更新することです.
1 void MoveCursor(int x, int y); //    
2 void MoveCursor(int x, int y)//      (           )
3 {
4     COORD pos = { x * 2,y };
5     HANDLE output = GetStdHandle(STD_OUTPUT_HANDLE);//            
6     SetConsoleCursorPosition(output, pos); //      
7 }
COORDはWindows APIで定義されている構造体です.
 
10.食べ物を食べたかどうかチェックし、壁にぶつかったかどうか、自分にぶつかったかどうかを確認します.
 1 void Jfood();     //        
 2 void Jwall();     //        
 3 void Jsnake();     //          
 4 void Jfood()
 5 {
 6     Phead_1 = Phead;
 7     if (Phead_1->x == Food->x&&Phead_1->y == Food->y)
 8     {
 9         FoodRand();
10         JudgeSum += 1;
11         if (JudgeSum == 5)
12         {
13             JudgeSum = 0;//  JudgeSum  5     
14             Hard += 1;
15             Pause -= 20000000;//         20000000
16         }
17         while (Phead_1->next != NULL)
18         {
19             Phead_1 = Phead_1->next;
20         }
21         Snakebody *S = (Snakebody*)malloc(sizeof(Snakebody));
22         S->x = Food->x;
23         S->y = Food->y;
24         S->next = NULL;
25         Phead_1->next = S;
26         ControlMove();
27         MoveCursor(Phead_1->x, Phead_1->y);
28         PRINTF
29     }
30     //             
31 }
32 void Jwall()
33 {
34     if (Phead->x == 0 || Phead->x == 29 || Phead->y == 0 || Phead->y == 19)
35     {
36         MoveCursor(10, 20);
37         SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);//    
38         printf("  ,      ,    !              ");
39         system("pause>nul");
40         exit(0);
41     }
42 }
43 void Jsnake()
44 {
45     Phead_1 = Phead->next;
46     while (Phead_1->next != NULL)
47     {
48         if ((Phead->x == Phead_1->x) && (Phead->y == Phead_1->y))
49         {
50             MoveCursor(10, 20);
51             SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);//    
52             printf("  ,      ,    !          ");
53             system("pause>nul");
54             exit(0);
55         }
56         Phead_1 = Phead_1->next;
57     }
58 }
 
11.ゲームサイクル
 1 void Move();     //    
 2 void Move()
 3 {
 4     while (1)
 5     {
 6         Phead_1 = Phead;
 7         while (Phead_1->next->next != NULL)
 8         {
 9             Phead_1 = Phead_1->next;
10         }
11         Phead_1->next = NULL;
12         for (int i = 0; i < Pause; i++) {}
13         ControlMove();
14         MoveCursor(Phead_1->x, Phead_1->y);
15         EMPTY
16             //       
17             Snakebody *Phead_2 = (Snakebody*)malloc(sizeof(Snakebody));
18         if (*PJ == 1)
19         {
20             Phead_2->x = Phead->x;
21             Phead_2->y = Phead->y - 1;
22         }
23         if (*PJ == 2)
24         {
25             Phead_2->x = Phead->x;
26             Phead_2->y = Phead->y + 1;
27         }
28         if (*PJ == 3)
29         {
30             Phead_2->x = Phead->x - 1;
31             Phead_2->y = Phead->y;
32         }
33         if (*PJ == 4)
34         {
35             Phead_2->x = Phead->x + 1;
36             Phead_2->y = Phead->y;
37         }
38         Phead_2->next = Phead;
39         Phead = Phead_2;
40         MoveCursor(Phead_2->x, Phead_2->y);
41         PRINTF
42             Jfood();
43         Jwall();
44         Jsnake();
45         MoveCursor(40, 20);
46     }
47 }
 
12.メモリを解放する
 1 void Free();                    //    
 2 void Free()
 3 {
 4     while (Phead->next != NULL)
 5     {
 6         Phead = Phead->next;
 7         free(Phead);
 8     }
 9     free(Phead);
10 }
 
付録:完全コード
  1 #include
  2 #include
  3 #include
  4 #define HEIGHT  20  //      
  5 #define WIDTH   40  //      
  6 #define PRINTF  printf("■");
  7 #define LINE    printf("
"); 8 #define EMPTY printf(" "); 9 typedef struct Snakebody 10 { 11 int x, y;// 12 struct Snakebody *next;// 13 }Snakebody;// 14 typedef struct Snakexy 15 { 16 int x; 17 int y; 18 }Snakexy; // 19 int sum = 0; // 20 int JudgeSum = 0; // 21 int Hard = 0; // 22 int Pause = 200000000; // ( ) 23 int JudgeDirection = 4; // 24 int * PJ = &JudgeDirection; // 25 Snakebody *Phead = NULL; // 26 Snakebody *Phead_1 = NULL; // 27 Snakebody *Pbady = NULL; // 28 Snakebody *end = NULL; // 29 Snakexy * Food = NULL; // 30 void Front(); // 1 31 void Jfood(); // 1 32 void Jwall(); // 1 33 void Jsnake(); // 1 34 void ISnake(); // 1 35 void DeawMap(); // 1 36 void FoodRand(); // 1 37 void ControlMove(); // 1 38 void MoveCursor(int x, int y); // 1 39 void Move(); // 1 40 void Showf(); // 1 41 void Free(); // 42 int main() 43 { 44 Front(); 45 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN);// 46 DeawMap(); 47 Showf(); 48 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);// 49 MoveCursor(34, 10); 50 printf(""); 51 MoveCursor(31, 11); 52 printf(" ←↓→ "); 53 MoveCursor(31, 12); 54 printf(""); 55 MoveCursor(31, 13); 56 printf(" , 5 "); 57 MoveCursor(31, 14); 58 printf(" ( )"); 59 ISnake(); 60 FoodRand(); 61 MoveCursor(40, 20); 62 Move(); 63 return 0; 64 } 65 void Front() 66 { 67 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED | FOREGROUND_BLUE);// 68 MoveCursor(18, 15); 69 printf(" ......"); 70 for (int i = 0; i <= 3000000000; i++) {} 71 system("cls"); 72 } 73 void DeawMap() 74 { 75 for (int i = 0; i < WIDTH; i++)PRINTF LINE // 76 for (int i = 1; i < HEIGHT - 1; i++) // 77 { 78 for (int j = 0; j < WIDTH; j++) 79 { 80 if (j == 0 || j == WIDTH - 1 || j == WIDTH - 10) 81 { 82 PRINTF 83 if (j == WIDTH - 1)LINE 84 } 85 else EMPTY 86 } 87 } 88 for (int i = 0; i < WIDTH; i++)PRINTF LINE // 89 } 90 void MoveCursor(int x, int y)// ( ) 91 { 92 /* COORD Windows API 93 * typedef struct _COORD 94 * { 95 * SHORT X; 96 * SHORT Y; 97 * } COORD; 98 * */ 99 COORD pos = { x * 2,y }; 100 HANDLE output = GetStdHandle(STD_OUTPUT_HANDLE);// 101 SetConsoleCursorPosition(output, pos); // 102 } 103 void FoodRand() 104 { 105 srand((int)time(0)); 106 int x = rand() % 27 + 2; 107 int y = rand() % 17 + 2; 108 Phead_1 = Phead; 109 for (int i = 0; i <= 200; i++) 110 { 111 if (Phead_1->x == x && Phead_1->y == y) 112 { 113 x = rand() % 27 + 2; 114 y = rand() % 17 + 2; 115 } 116 else 117 { 118 Phead_1 = Phead_1->next; 119 } 120 if (Phead_1->next == NULL) 121 { 122 break; 123 } 124 } 125 MoveCursor(x, y); 126 PRINTF 127 Food = (Snakexy*)malloc(sizeof(Snakexy)); 128 Food->x = x; 129 Food->y = y; 130 MoveCursor(33, 5); 131 printf(" "); 132 Showf(); 133 sum++; 134 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY);// 135 } 136 void ControlMove() 137 { 138 if (GetAsyncKeyState(VK_UP) && 0x8000) 139 { 140 if (JudgeDirection == 2) 141 { 142 } 143 else 144 { 145 JudgeDirection = 1; 146 } 147 } 148 if (GetAsyncKeyState(VK_DOWN) && 0x8000) 149 { 150 if (JudgeDirection == 1) 151 { 152 } 153 else 154 { 155 JudgeDirection = 2; 156 } 157 } 158 if (GetAsyncKeyState(VK_RIGHT) && 0x8000) 159 { 160 if (JudgeDirection == 3) 161 { 162 } 163 else 164 { 165 JudgeDirection = 4; 166 } 167 } 168 if (GetAsyncKeyState(VK_LEFT) && 0x8000) 169 { 170 if (JudgeDirection == 4) 171 { 172 } 173 else 174 { 175 JudgeDirection = 3; 176 } 177 } 178 if (GetAsyncKeyState(VK_RETURN) && 0x0D) 179 { 180 while (1) 181 { 182 if (GetAsyncKeyState(VK_RETURN) && 0x0D) 183 { 184 break; 185 } 186 } 187 } 188 } 189 void ISnake() 190 { 191 for (int i = 0; i < 5; i++) 192 { 193 Pbady = (Snakebody*)malloc(sizeof(Snakebody)); 194 Pbady->x = 5 - i; 195 Pbady->y = 5; 196 if (Phead == NULL) 197 { 198 Phead = Pbady; 199 } 200 else 201 { 202 end->next = Pbady; 203 } 204 Pbady->next = NULL; 205 end = Pbady; 206 } 207 Phead_1 = Phead; 208 while (Phead_1->next != NULL) 209 { 210 MoveCursor(Phead_1->x, Phead_1->y); 211 PRINTF 212 Phead_1 = Phead_1->next; 213 } 214 } 215 void Move() 216 { 217 while (1) 218 { 219 Phead_1 = Phead; 220 while (Phead_1->next->next != NULL) 221 { 222 Phead_1 = Phead_1->next; 223 } 224 Phead_1->next = NULL; 225 for (int i = 0; i < Pause; i++) {} 226 ControlMove(); 227 MoveCursor(Phead_1->x, Phead_1->y); 228 EMPTY 229 // 230 Snakebody *Phead_2 = (Snakebody*)malloc(sizeof(Snakebody)); 231 if (*PJ == 1) 232 { 233 Phead_2->x = Phead->x; 234 Phead_2->y = Phead->y - 1; 235 } 236 if (*PJ == 2) 237 { 238 Phead_2->x = Phead->x; 239 Phead_2->y = Phead->y + 1; 240 } 241 if (*PJ == 3) 242 { 243 Phead_2->x = Phead->x - 1; 244 Phead_2->y = Phead->y; 245 } 246 if (*PJ == 4) 247 { 248 Phead_2->x = Phead->x + 1; 249 Phead_2->y = Phead->y; 250 } 251 Phead_2->next = Phead; 252 Phead = Phead_2; 253 MoveCursor(Phead_2->x, Phead_2->y); 254 PRINTF 255 Jfood(); 256 Jwall(); 257 Jsnake(); 258 MoveCursor(40, 20); 259 } 260 } 261 void Jfood() 262 { 263 Phead_1 = Phead; 264 if (Phead_1->x == Food->x&&Phead_1->y == Food->y) 265 { 266 FoodRand(); 267 JudgeSum += 1; 268 if (JudgeSum == 5) 269 { 270 JudgeSum = 0; 271 Hard += 1; 272 Pause -= 20000000; 273 } 274 while (Phead_1->next != NULL) 275 { 276 Phead_1 = Phead_1->next; 277 } 278 Snakebody *S = (Snakebody*)malloc(sizeof(Snakebody)); 279 S->x = Food->x; 280 S->y = Food->y; 281 S->next = NULL; 282 Phead_1->next = S; 283 ControlMove(); 284 MoveCursor(Phead_1->x, Phead_1->y); 285 PRINTF 286 } 287 // 288 } 289 void Jwall() 290 { 291 if (Phead->x == 0 || Phead->x == 29 || Phead->y == 0 || Phead->y == 19) 292 { 293 MoveCursor(10, 20); 294 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);// 295 printf(" , , ! "); 296 system("pause>nul"); 297 exit(0); 298 } 299 } 300 void Jsnake() 301 { 302 Phead_1 = Phead->next; 303 while (Phead_1->next != NULL) 304 { 305 if ((Phead->x == Phead_1->x) && (Phead->y == Phead_1->y)) 306 { 307 MoveCursor(10, 20); 308 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY | FOREGROUND_RED);// 309 printf(" , , ! "); 310 system("pause>nul"); 311 exit(0); 312 } 313 Phead_1 = Phead_1->next; 314 } 315 } 316 void Showf() 317 { 318 SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_BLUE);// 319 MoveCursor(33, 5); 320 printf(" :%d", sum); 321 MoveCursor(33, 6); 322 printf(" :%d", Hard); 323 } 324 void Free() 325 { 326 while (Phead->next != NULL) 327 { 328 Phead = Phead->next; 329 free(Phead); 330 } 331 free(Phead); 332 }