C++ 实现一元稀疏多项式计算器：链表存储与运算全解析

以下是使用 C++ 实现一元稀疏多项式计算器的逻辑结构和存储结构的分析： 逻辑结构： - 可以使用链表来存储多项式的每一项，因为多项式的项数是不确定的，且可能需要动态添加和删除项。 存储结构： - 定义一个结构体 `PolyNode` 来表示多项式的一项，包含系数和指数两个成员。 - 使用链表节点 `PolyNode` 来构建链表，存储多项式的各项。 以下是一个简单的示例代码框架： ```cpp #include <iostream> // 定义多项式的一项 struct PolyNode { int coefficient; // 系数 int exponent; // 指数 PolyNode* next; // 指向下一项的指针 }; // 创建新的多项式项节点 PolyNode* createNode(int coefficient, int exponent) { PolyNode* newNode = new PolyNode; newNode->coefficient = coefficient; newNode->exponent = exponent; newNode->next = nullptr; return newNode; } // 插入节点到链表（按指数升序） void insertNode(PolyNode*& head, int coefficient, int exponent) { PolyNode* newNode = createNode(coefficient, exponent); if (head == nullptr || exponent < head->exponent) { newNode->next = head; head = newNode; } else { PolyNode* curr = head; while (curr->next!= nullptr && curr->next->exponent < exponent) { curr = curr->next; } newNode->next = curr->next; curr->next = newNode; } } // 打印多项式 void printPoly(PolyNode* head) { PolyNode* curr = head; int count = 0; std::cout << "多项式: "; while (curr!= nullptr) { std::cout << "(" << curr->coefficient << ", " << curr->exponent << ") "; curr = curr->next; count++; } std::cout << std::endl << "项数: " << count << std::endl; } // 多项式相加 PolyNode* addPoly(PolyNode* a, PolyNode* b) { PolyNode* result = nullptr; PolyNode* currA = a; PolyNode* currB = b; while (currA!= nullptr && currB!= nullptr) { if (currA->exponent < currB->exponent) { insertNode(result, currA->coefficient, currA->exponent); currA = currA->next; } else if (currA->exponent > currB->exponent) { insertNode(result, currB->coefficient, currB->exponent); currB = currB->next; } else { int sum = currA->coefficient + currB->coefficient; if (sum!= 0) { insertNode(result, sum, currA->exponent); } currA = currA->next; currB = currB->next; } } while (currA!= nullptr) { insertNode(result, currA->coefficient, currA->exponent); currA = currA->next; } while (currB!= nullptr) { insertNode(result, currB->coefficient, currB->exponent); currB = currB->next; } return result; } // 多项式相减 PolyNode* subtractPoly(PolyNode* a, PolyNode* b) { PolyNode* result = nullptr; PolyNode* currA = a; PolyNode* currB = b; while (currA!= nullptr && currB!= nullptr) { if (currA->exponent < currB->exponent) { insertNode(result, currA->coefficient, currA->exponent); currA = currA->next; } else if (currA->exponent > currB->exponent) { insertNode(result, -currB->coefficient, currB->exponent); currB = currB->next; } else { int diff = currA->coefficient - currB->coefficient; if (diff!= 0) { insertNode(result, diff, currA->exponent); } currA = currA->next; currB = currB->next; } } while (currA!= nullptr) { insertNode(result, currA->coefficient, currA->exponent); currA = currA->next; } while (currB!= nullptr) { insertNode(result, -currB->coefficient, currB->exponent); currB = currB->next; } return result; } // 计算多项式在 x 处的值 int evaluatePoly(PolyNode* head, int x) { int result = 0; PolyNode* curr = head; while (curr!= nullptr) { int termValue = curr->coefficient * std::pow(x, curr->exponent); result += termValue; curr = curr->next; } return result; } int main() { PolyNode* polyA = nullptr; PolyNode* polyB = nullptr; // 按指数升序输入并建立多项式 A insertNode(polyA, 3, 2); insertNode(polyA, 2, 1); insertNode(polyA, 1, 0); // 按指数升序输入并建立多项式 B insertNode(polyB, 2, 2); insertNode(polyB, -1, 1); insertNode(polyB, 5, 0); std::cout << "多项式 A: "; printPoly(polyA); std::cout << "多项式 B: "; printPoly(polyB); PolyNode* sum = addPoly(polyA, polyB); std::cout << "A + B: "; printPoly(sum); PolyNode* diff = subtractPoly(polyA, polyB); std::cout << "A - B: "; printPoly(diff); int x = 2; int valueA = evaluatePoly(polyA, x); std::cout << "多项式 A 在 x = " << x << " 处的值: " << valueA << std::endl; return 0; } ``` 额外需要注意的逻辑点： 1. 在插入节点时，要确保指数的升序排列。 2. 进行多项式运算时，要处理好系数为 0 的情况。 3. 释放链表使用的内存，避免内存泄漏。 ######[AI写代码神器 | 1607点数解答 | 2025-01-09 18:29:06]