Board logo

標題: 資料結構 103 怪物對戰模擬(難) [打印本頁]
作者: may    時間: 2025-3-23 17:08     標題: 資料結構 103 怪物對戰模擬(難)

資料結構 103 怪物對戰模擬

1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。

2. 設計說明：
(1) 小林正在設計一個與怪物連續對戰的遊戲程式。程式讓使用者輸入一個正整數序列，代表此關卡會出現的怪物數量與其攻擊力。例如：輸入「10,20,30」，每個數字分別代表每隻怪物的攻擊力，數字之間用半形逗號（,）隔開，若輸入 n 個數字代表總共有 n 隻怪物。

(2) 請使用鏈結串列的方式，依序初始化此怪物序列。

(3) 遊戲玩家角色的 HP 血量預設為 100，玩家會從頭輪詢怪物序列，每經過一個怪物節點就扣除相對應的 HP 血量，直到玩家的 HP ≤ 0。

3. 輸入輸出：
輸入說明
一個正整數序列，代表怪物數量與其攻擊力。

輸出說明
若玩家成功通過所有怪物，輸出「game clear! hp left (剩餘血量)」。
否則，輸出「game over! dead at level (第幾回合死亡)」。

範例輸入1
10,20,30
範例輸出1
game clear! hp left 40
範例輸入2
50,50
範例輸出2
game over! dead at level 2
作者: may    時間: 2025-3-23 17:21

  1. //#include <iostream>
  2. //#include <sstream>
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. // 定義鏈結串列的節點結構
  6. struct Monster {
  7.     int attack;
  8.     Monster* next;
  9.     Monster(int atk) : attack(atk), next(nullptr) {}
  10. };

  12. // 插入新節點到鏈結串列
  13. void append(Monster*& head, int attack) {
  14.     if (!head) {
  15.         head = new Monster(attack);
  16.         return;
  17.     }
  18.     Monster* temp = head;
  19.     while (temp->next) {
  20.         temp = temp->next;
  21.     }
  22.     temp->next = new Monster(attack);
  23. }

  25. // 釋放鏈結串列記憶體
  26. void freeList(Monster* head) {
  27.     while (head) {
  28.         Monster* temp = head;
  29.         head = head->next;
  30.         delete temp;
  31.     }
  32. }

  34. int main() {
  35.     string input;
  36.     getline(cin, input);
  37.    
  38.     Monster* head = nullptr;
  39.     stringstream ss(input);
  40.     string token;
  41.    
  42.     // 讀取輸入並建立鏈結串列
  43.     while (getline(ss, token, ',')) {
  44.         append(head, stoi(token));
  45.     }
  46.    
  47.     int hp = 100;
  48.     int level = 1;
  49.     Monster* temp = head;
  50.    
  51.     // 進行怪物對戰
  52.     while (temp) {
  53.         hp -= temp->attack;
  54.         if (hp <= 0) {
  55.             cout << "game over! dead at level " << level << endl;
  56.             freeList(head);
  57.             return 0;
  58.         }
  59.         temp = temp->next;
  60.         level++;
  61.     }
  62.    
  63.     cout << "game clear! hp left " << hp << endl;
  64.     freeList(head);
  65.     return 0;
  66. }
複製代碼
回復 1# may
------------------------------------------------\
程式說明：
定義 Monster 結構：

代表怪物的鏈結串列節點，每個節點包含 attack（攻擊力）和 next 指標。

函式 append()：

用於向鏈結串列新增怪物。

函式 freeList()：

用於釋放鏈結串列的記憶體，避免記憶體洩漏。

main() 函式：

讀取輸入字串，解析並建立鏈結串列。

進行戰鬥模擬，計算玩家 HP 的變化。

若 HP ≤ 0，輸出 "game over! dead at level X"。

若成功擊敗所有怪物，輸出 "game clear! hp left Y"。

最後釋放記憶體。

這樣的設計確保了對戰過程的順序性，並且使用鏈結串列來管理怪物資料。
-------------------------------------
測資
測資 00：
輸入：
10,20,30

預期輸出：
game clear! hp left 40

測資 01：
輸入：
50,50

預期輸出：
game over! dead at level 2

測資 02：
輸入：
25,25,25,25

預期輸出：
game over! dead at level 4

測資 03：
輸入：
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5

預期輸出：
game over! dead at level 20

測資 04：
輸入：
100

預期輸出：
game over! dead at level 1

這些測資涵蓋不同情境，包括成功通關、HP 剛好歸零、過早死亡等情況。
作者: may    時間: 2025-3-23 17:44     標題: struct Monster 詳細說明

回復 2# may
struct Monster 詳細說明
  1. struct Monster {
  2.     int attack;
  3.     Monster* next;
  4.     Monster(int atk) : attack(atk), next(nullptr) {}
  5. };
複製代碼
這個 Monster 結構（struct）是用來表示怪物節點的，並且可以用於鏈結串列的實作。下面是這個結構的詳細解析。

1. 結構定義

struct Monster {
    int attack;
    Monster* next;
    Monster(int atk) : attack(atk), next(nullptr) {}
};
這是一個鏈結串列節點的結構體（struct），它包含了兩個成員變數：

int attack：
表示這隻怪物的攻擊力。

Monster* next：
這是一個指向 Monster 結構的指標，指向下一個怪物節點，用於形成鏈結串列。

2. 構造函式（Constructor）
Monster(int atk) : attack(atk), next(nullptr) {}
這是一個建構子（Constructor），當我們建立 Monster 物件時，它會自動執行以下初始化：
attack(atk)：將 atk 的值賦予 attack 變數，這表示這隻怪物的攻擊力。
next(nullptr)：將 next 設為 nullptr，表示這個節點尚未連接到其他節點，是鏈結串列中的最後一個節點。
這種初始化方式稱為「成員初始化列表（Member Initialization List）」，比起在函式內部用 this->attack = atk; 更高效，因為它直接在物件建立時初始化成員變數。

3. 如何使用 Monster 結構
這個 Monster 結構通常會與**鏈結串列（Linked List）**搭配使用，例如：

(1) 建立一個怪物節點
Monster* m1 = new Monster(10);  // 建立攻擊力為 10 的怪物
new Monster(10)：這會動態分配一個 Monster 節點，並設定攻擊力為 10，next 預設為 nullptr。

(2) 連接多個怪物節點
Monster* m1 = new Monster(10);
Monster* m2 = new Monster(20);
m1->next = m2;  // 讓 m1 指向 m2，形成鏈結串列
這樣我們就建立了一個包含兩個節點的鏈結串列：

[10] → [20] → nullptr
(3) 用迴圈遍歷鏈結串列
Monster* temp = m1;
while (temp) {
    cout << "怪物攻擊力: " << temp->attack << endl;
    temp = temp->next;  // 移動到下一個節點
}
這段程式碼會遍歷整個鏈結串列，並輸出每隻怪物的攻擊力。

4. 為什麼要使用鏈結串列？
在這個怪物對戰模擬程式中，鏈結串列有以下優勢：

動態大小
可以根據輸入的怪物數量來動態分配記憶體，不浪費空間。

靈活的插入與刪除
可以輕易地新增或刪除怪物，而不需要調整陣列大小。

依序處理怪物
玩家會從第一個怪物開始戰鬥，依序扣除 HP，這正好符合鏈結串列的特性。

5. 總結
struct Monster 代表一個怪物節點，包含攻擊力 attack 和指向下一個怪物的指標 next。

Monster(int atk) 是建構子，初始化 attack，並將 next 設為 nullptr。

透過 next 指標，可以將多個 Monster 連接起來，形成鏈結串列，並用來模擬怪物的連續攻擊。

這樣的設計可以讓遊戲順利模擬怪物對戰的過程，並有效管理怪物資訊。
作者: may    時間: 2025-3-23 18:04     標題: void append(Monster*& head, int attack) 詳細解析

回復 3# may

這個函式 append() 的作用是將新的怪物節點（Monster）加到鏈結串列的尾端。以下是詳細解析其功能與運作方式。

1. 函式定義
void append(Monster*& head, int attack) {
    if (!head) {
        head = new Monster(attack);
        return;
    }
    Monster* temp = head;
    while (temp->next) {
        temp = temp->next;
    }
    temp->next = new Monster(attack);
}
參數說明：

Monster*& head：

head 是指向鏈結串列開頭的指標，使用引用（&）傳遞，確保對 head 的修改可以影響主程式中的 head 指標。

若鏈結串列為空（head == nullptr），則 head 會被指向新建的 Monster 節點。

int attack：

代表要新增的怪物攻擊力，這個值會被用來建立新的 Monster 節點。

2. append() 函式的執行步驟
(1) 檢查 head 是否為 nullptr

if (!head) {
    head = new Monster(attack);
    return;
}
如果 head 為 nullptr，表示鏈結串列目前是空的，沒有任何怪物。

這時候直接建立第一個怪物節點，並讓 head 指向這個節點。

然後結束函式執行（return;），因為新增節點已經完成。

✅ 範例

Monster* head = nullptr;  // 初始鏈結串列為空
append(head, 10);         // 新增攻擊力為 10 的怪物
結果（鏈結串列狀態）

[10] → nullptr
(2) 找到鏈結串列的最後一個節點

Monster* temp = head;
while (temp->next) {
    temp = temp->next;
}
從 head 開始遍歷鏈結串列，使用 temp 指標來移動。

只要 temp->next 不是 nullptr，表示還沒到達鏈結串列的尾端，就繼續往後走。

✅ 範例

Monster* head = nullptr;
append(head, 10);
append(head, 20);
遍歷時，head 指向 [10]，然後 temp 移動到最後一個節點 [10]。

(3) 在最後一個節點後面新增新節點
temp->next = new Monster(attack);
當 temp->next == nullptr 時，表示 temp 已經是鏈結串列的最後一個節點。

創建一個新的 Monster 節點，並讓 temp->next 指向它。

✅ 範例

append(head, 30);
鏈結串列變成：

[10] → [20] → [30] → nullptr
3. append() 完整執行範例

Monster* head = nullptr; // 初始化鏈結串列為空

append(head, 10); // 新增攻擊力為 10 的怪物
append(head, 20); // 新增攻擊力為 20 的怪物
append(head, 30); // 新增攻擊力為 30 的怪物

// 遍歷並輸出
Monster* temp = head;
while (temp) {
    cout << "怪物攻擊力: " << temp->attack << endl;
    temp = temp->next;
}
輸出結果：

怪物攻擊力: 10
怪物攻擊力: 20
怪物攻擊力: 30
4. 為什麼 head 需要用 Monster*& head（引用）？
如果 append() 的 head 參數沒有使用 &，則函式內對 head 的修改不會影響主程式的 head，導致鏈結串列無法更新。

錯誤示範（未使用 &）
cpp
複製
編輯
void append(Monster* head, int attack) {
    if (!head) {
        head = new Monster(attack); // 這裡修改的是函式內部的 head，不影響主程式
        return;
    }
}
這樣 head 仍然是 nullptr，導致鏈結串列無法建立。

5. 總結
append() 用來在鏈結串列尾端新增一個怪物節點。

如果 head 是空的（nullptr），則建立第一個節點並讓 head 指向它。

如果 head 不是空的，則找到最後一個節點，並在其後新增一個節點。

使用 Monster*& head（引用）確保 head 的修改能影響主程式。

這樣的 append() 函式可以靈活地將怪物加入對戰序列，確保遊戲的進行！
作者: may    時間: 2025-3-23 18:10     標題: void freeList(Monster* head) 詳細解析

回復 4# may
void freeList(Monster* head) 詳細解析
這個 freeList() 函式的功能是釋放（刪除）鏈結串列中的所有節點，以避免記憶體洩漏（memory leak）。
當我們使用 new 動態分配 Monster 節點時，這些記憶體需要手動釋放，否則程式運行時間長了會導致記憶體占用過多。

1. 函式定義
void freeList(Monster* head) {
    while (head) {
        Monster* temp = head;
        head = head->next;
        delete temp;
    }
}
參數說明
Monster* head：

head 是鏈結串列的起始節點。

這個函式會從 head 開始，逐一釋放每個節點的記憶體，直到整個鏈結串列都被刪除。

2. freeList() 的執行步驟
這個函式使用 while 迴圈逐一釋放鏈結串列中的所有節點。

(1) 檢查 head 是否為 nullptr
while (head) {
只要 head 不是 nullptr，表示鏈結串列中還有節點尚未釋放。

如果 head 一開始就是 nullptr，則代表鏈結串列已經是空的，直接跳過迴圈。

(2) 記錄當前節點，準備刪除
Monster* temp = head;
temp 是暫存指標，用來記錄當前的 head，因為 head 待會兒會被移動到下一個節點。

這樣做的目的是確保 delete temp; 不會影響到鏈結串列的遍歷。

(3) 移動 head 指標
head = head->next;
head 被移動到下一個節點，使迴圈可以繼續處理剩下的節點。

(4) 釋放當前節點的記憶體
delete temp;
這行程式碼會刪除 temp 指向的節點，釋放該節點所佔用的記憶體。

因為 head 已經指向下一個節點，所以刪除 temp 不會影響鏈結串列的遍歷。

3. freeList() 的運行示例
(1) 建立鏈結串列
Monster* head = nullptr;
append(head, 10);
append(head, 20);
append(head, 30);
現在的鏈結串列：

[10] → [20] → [30] → nullptr
(2) 釋放鏈結串列
freeList(head);
執行 freeList() 時，每個步驟如下：

temp = head（指向 [10]），head = head->next（移到 [20]），刪除 [10]

temp = head（指向 [20]），head = head->next（移到 [30]），刪除 [20]

temp = head（指向 [30]），head = head->next（變成 nullptr），刪除 [30]

head == nullptr，跳出迴圈

此時，整個鏈結串列都被刪除，程式不會有記憶體洩漏。

4. freeList() 的重要性
(1) 避免記憶體洩漏
在 C++ 中，使用 new 配置的記憶體不會自動釋放，若未使用 delete 釋放，就會導致記憶體洩漏。

freeList() 確保所有 Monster 節點的記憶體都被正確釋放。

(2) 防止程式執行時占用過多記憶體
如果沒有 freeList()，程式不斷增加怪物，最後可能會導致記憶體不足（特別是在長時間運行的遊戲或伺服器上）。

(3) 確保鏈結串列被正確清除
執行 freeList() 後，head 仍然存在，但它不再指向有效的鏈結串列（已經全部刪除）。

要注意！ head 本身沒有被設為 nullptr，如果之後嘗試使用它，可能會發生錯誤（dangling pointer）。

5. freeList() 使用後的建議
在 freeList() 之後，如果還會使用 head，最好將它設為 nullptr，避免誤用已刪除的記憶體：

freeList(head);
head = nullptr; // 避免懸空指標（dangling pointer）
這樣可以確保 head 不會指向無效的記憶體空間。

6. 總結
freeList() 逐一刪除鏈結串列中的所有 Monster 節點，避免記憶體洩漏。

使用 while 迴圈，從 head 開始釋放每個節點，直到 head == nullptr。

使用 temp 指標來記錄當前節點，確保能安全刪除它。

刪除後，將 head 移動到下一個節點，直到所有節點都被釋放。

執行 freeList() 後，建議將 head = nullptr;，避免懸空指標。

這樣的實作確保程式能夠有效管理記憶體，避免不必要的資源浪費！



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://seed.istak.org.tw/) Powered by Discuz! 7.2