資料結構 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

管理員

Rank: 9 Rank: 9 Rank: 9

2^#

may發表於 2025-3-23 17:21 | 只看該作者

//#include <iostream>
//#include <sstream>
#include <bits/stdc++.h>
using namespace std;
// 定義鏈結串列的節點結構
struct Monster {
int attack;
Monster* next;
Monster(int atk) : attack(atk), next(nullptr) {}
};
// 插入新節點到鏈結串列
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);
}
// 釋放鏈結串列記憶體
void freeList(Monster* head) {
while (head) {
Monster* temp = head;
head = head->next;
delete temp;
}
}
int main() {
string input;
getline(cin, input);
Monster* head = nullptr;
stringstream ss(input);
string token;
// 讀取輸入並建立鏈結串列
while (getline(ss, token, ',')) {
append(head, stoi(token));
}
int hp = 100;
int level = 1;
Monster* temp = head;
// 進行怪物對戰
while (temp) {
hp -= temp->attack;
if (hp <= 0) {
cout << "game over! dead at level " << level << endl;
freeList(head);
return 0;
}
temp = temp->next;
level++;
}
cout << "game clear! hp left " << hp << endl;
freeList(head);
return 0;
}

複製代碼

回復 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

TOP

管理員

Rank: 9 Rank: 9 Rank: 9

3^#

may發表於 2025-3-23 17:44 | 只看該作者

struct Monster 詳細說明

回復 2# may
struct Monster 詳細說明

struct Monster {
int attack;
Monster* next;
Monster(int atk) : attack(atk), next(nullptr) {}
};

複製代碼

這個 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

TOP

管理員

Rank: 9 Rank: 9 Rank: 9

4^#

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

TOP

管理員

Rank: 9 Rank: 9 Rank: 9

5^#

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;，避免懸空指標。

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

May

TOP

返回列表

資料結構 103 怪物對戰模擬(難)

struct Monster 詳細說明

void append(Monster*& head, int attack) 詳細解析

void freeList(Monster* head) 詳細解析

[收藏此主題] [關注此主題的新回復]

[通過 QQ、MSN 分享給朋友]