Board logo

標題: 資料結構 105 多項式的鏈結串列表示與相加 [打印本頁]
作者: may    時間: 2025-3-31 10:27     標題: 資料結構 105 多項式的鏈結串列表示與相加

資料結構 105 多項式的鏈結串列表示與相加
1. 題目說明：
請依下列題意進行作答，使輸出值符合題意要求。
[attach]20862[/attach]
[attach]20863[/attach]
2. 設計說明：
(1) 一個二元多項式是由多個項組成的，每個項包含三個整數：係數、x 的指數和 y 的指數。需要使用鏈結串列（Linked list）來實作這個多項式的儲存和操作，並完成以下功能：

多項式的鏈結表示：每個節點（或稱為「項」）應包含係數 a、x 的指數 b 和 y 的指數 c，以及指向下一個節點的指針。每一項定義如下：ax^by^c

多項式是由多個「項」組合而成，當使用者輸入一列整數資料代表一個多項式，其中每三個整數代表「一項」。如果新項的 x 和 y 指數已經存在於多項式中，則應將它們的係數相加。

例如：輸入「4 4 0 -5 2 1 2 2 1」，代表為多項式：4x^4y^0-3x^2y^1

多項式相加：實作一個方法來相加兩個多項式，並返回一個新的多項式作為結果。

格式化輸出：輸出結果先依照 x 的指數降冪排序，再依照 y 的指數降冪排序。如果係數是負數，則其前面不應顯示加號。

提示：請利用鏈結串列（Linked list）來實作，有指標的程式語言可利用指標方式實作，有物件導向的程式語言可利用類別來實作。

3. 輸入輸出：
輸入說明
第 1 列：輸入一個正整數 N（2 ≤ N ≤ 10），代表有 N 個二元多項式相加。
第 2~N+1 列：每一列代表一個多項式，每一項有三個整數 a、b、c，所有整數間以一個半形空白間隔。若有 M 組 a、b、c 代表多項式有 M 項。

輸出說明
逐列呈現 N 個二元多項式，並計算所有多項式相加的結果。

註：

多項式的呈現順序，先以 x 的指數降冪排序，再以 y 的指數降冪排序。
次方請以「^」符號表示。例如[attach]20864[/attach]： 則顯示「10x^5y^4+3x^5y^1-6x^4y^4+1x^3y^0」。
若係數為負數，則其前面不應顯示加號；若係數為 0，則不顯示該項；若係數非 0，則一律顯示係數值。
範例輸入1
2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
範例輸出1
3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
範例輸入2
3
1 1 0 5 4 3 2 1 0
3 3 3 2 2 2 -1 1 0
3 2 1 -1 1 0 1 0 0 3 0 0
範例輸出2
5x^4y^3+3x^1y^0
3x^3y^3+2x^2y^2-1x^1y^0
3x^2y^1-1x^1y^0+4x^0y^0
Sum:5x^4y^3+3x^3y^3+2x^2y^2+3x^2y^1+1x^1y^0+4x^0y^0
作者: may    時間: 2025-4-7 22:19

回復 1# may
  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <map>
  4. //#include <sstream>
  5. //#include <algorithm>
  6. #include <bits/stdc++.h>
  7. using namespace std;

  9. // 定義每一項結構
  10. struct Term {
  11.     int coef; // 係數
  12.     int xExp; // x 的指數
  13.     int yExp; // y 的指數
  14. };

  16. // 比較函式：先比 x 降冪，再比 y 降冪
  17. bool compare(const Term &a, const Term &b) {
  18.     if (a.xExp != b.xExp)
  19.         return a.xExp > b.xExp;
  20.     return a.yExp > b.yExp;
  21. }

  23. // 印出一個多項式
  24. void printPolynomial(const map<pair<int, int>, int> &poly) {
  25.     vector<Term> terms;

  27.     for (auto it : poly) {
  28.         if (it.second != 0) {
  29.             terms.push_back({it.second, it.first.first, it.first.second});
  30.         }
  31.     }

  33.     // 排序：先比 x 再比 y（都為降冪）
  34.     sort(terms.begin(), terms.end(), compare);

  36.     bool first = true;
  37.     for (auto &t : terms) {
  38.         if (!first && t.coef > 0)
  39.             cout << "+";
  40.         cout << t.coef << "x^" << t.xExp << "y^" << t.yExp;
  41.         first = false;
  42.     }

  44.     if (terms.empty()) cout << "0"; // 若全部為 0，顯示 0
  45.     cout << endl;
  46. }

  48. int main() {
  49.     int N;
  50.     cin >> N;
  51.     cin.ignore(); // 清除換行字元

  53.     vector<map<pair<int, int>, int>> polys(N); // 每個多項式都用一個 map 存

  55.     // 逐列讀取每一個多項式
  56.     for (int i = 0; i < N; i++) {
  57.         string line;
  58.         getline(cin, line);
  59.         istringstream iss(line);

  61.         int a, b, c;
  62.         while (iss >> a >> b >> c) {
  63.             polys[i][{b, c}] += a;
  64.         }
  65.     }

  67.     // 輸出每個多項式
  68.     for (int i = 0; i < N; i++) {
  69.         printPolynomial(polys[i]);
  70.     }

  72.     // 計算總和
  73.     map<pair<int, int>, int> total;
  74.     for (int i = 0; i < N; i++) {
  75.         for (auto it : polys[i]) {
  76.             total[it.first] += it.second;
  77.         }
  78.     }

  80.     cout << "Sum:";
  81.     printPolynomial(total);

  83.     return 0;
  84. }
複製代碼
作者: may    時間: 2025-4-7 22:55

回復 2# may
解說（搭配上面的程式碼）：
資料結構設計
使用 map<pair<int,int>, int>：

pair<int,int> 存的是 (x 指數, y 指數)

int 是這一項的係數

多項式相加
相同 (x, y) 指數的項目會自動相加（因為是用 map 儲存）

如果有重複的 (x, y)，就會直接相加進 map 裡

排序輸出
把 map 裡面的內容丟進 vector

排序規則是：先比 x 降冪，再比 y 降冪

輸出格式
第一項前面不加 +

後面項目若是正的就加 +，負的自動顯示 -

次方使用 x^、y^ 格式呈現

範例輸入：

2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
對應輸出：

3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
作者: may    時間: 2025-4-7 23:02     標題: 問題一:關鍵程式碼解說

回復 3# may
  1. for (auto it : poly) {
  2.         if (it.second != 0) {
  3.             terms.push_back({it.second, it.first.first, it.first.second});
  4.         }
  5.     }
複製代碼
-------------------------------------
背景說明：
poly 是一個 map<pair<int, int>, int>：

每一項的 key 是 pair<int, int>（代表 x 的指數 和 y 的指數）

每一項的 value 是 int（代表這一項的 係數）
例如:
poly[{2, 1}] = 3; // 表示 3x^2y^1
poly[{1, 3}] = -4; // 表示 -4x^1y^3
--------------------------------------
for 迴圈解釋：
for (auto it : poly)
這行是 C++ 的範圍式 for 迴圈（range-based for loop），會把 poly map 中的每一筆資料逐一取出：

it 的型別其實是 pair<pair<int, int>, int>
因為：

key 是 pair<int, int>（代表指數：x, y）

value 是 int（代表係數）
-----------------------------
條件篩選：if (it.second != 0)
it.second 是這一項的「係數」

若係數是 0，就不處理它（因為 0 不需要顯示在多項式中）

若不是 0，就加入 terms 向量中
-------------------------
重點：加入 terms 向量
terms.push_back({it.second, it.first.first, it.first.second});
這句的意思是把這項轉成 Term 結構並加入 terms 向量中。

it.second // 係數 coef

it.first.first // x 的指數 xExp

it.first.second // y 的指數 yExp

也就是：
Term t;
t.coef = it.second;
t.xExp = it.first.first;
t.yExp = it.first.second;
terms.push_back(t);
整段功能總結：
這段程式碼的功能是：
把多項式中「係數不為 0」的項目轉換成 Term 結構，並儲存到 terms 向量中，準備後續排序與輸出。
---------------------------
舉個例子（假設 poly 裡面資料是這樣）：
poly = {
    {{2, 1}, 3},
    {{1, 3}, -4},
    {{0, 0}, 0}  // 這項會被略過
};
則這段程式執行完後：
terms = {
    {3, 2, 1},   // 3x^2y^1
    {-4, 1, 3}   // -4x^1y^3
};
作者: may    時間: 2025-4-7 23:09     標題: 測資

回復 4# may
測資:
測資 00：
2
3 2 1 -4 1 3 8 0 0
7 2 1 -2 1 4 5 1 3
預期輸出：
3x^2y^1-4x^1y^3+8x^0y^0
7x^2y^1-2x^1y^4+5x^1y^3
Sum:10x^2y^1-2x^1y^4+1x^1y^3+8x^0y^0
測資 01：
3
1 1 0 5 4 3 2 1 0
3 3 3 2 2 2 -1 1 0
3 2 1 -1 1 0 1 0 0 3 0 0
預期輸出：
5x^4y^3+3x^1y^0
3x^3y^3+2x^2y^2-1x^1y^0
3x^2y^1-1x^1y^0+4x^0y^0
Sum:5x^4y^3+3x^3y^3+2x^2y^2+3x^2y^1+1x^1y^0+4x^0y^0
測資 02：
2
2 1 1 4 2 2 1 0 0
-2 1 1 -1 0 0
預期輸出：
4x^2y^2+2x^1y^1+1x^0y^0
-2x^1y^1-1x^0y^0
Sum:4x^2y^2
測資 03：
4
1 3 2 2 2 2
-1 3 2 3 1 1
5 0 0
-3 1 1 -2 2 2
預期輸出：
1x^3y^2+2x^2y^2
-1x^3y^2+3x^1y^1
5x^0y^0
-2x^2y^2-3x^1y^1
Sum:0x^3y^2+0x^2y^2+0x^1y^1+5x^0y^0
Sum:5x^0y^0
測資 04：
3
5 5 5 -3 2 2
1 5 5 -1 2 2
2 1 1 3 0 0
預期輸出：
5x^5y^5-3x^2y^2
1x^5y^5-1x^2y^2
2x^1y^1+3x^0y^0
Sum:6x^5y^5-4x^2y^2+2x^1y^1+3x^0y^0



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