我试图通过链表添加3个多项式，并设法在c++中创建以下程序，该程序适用于某些情况，但不适用于所有情况。问题是，我无法找出程序给出错误输出的测试用例(因为所有用例在hackerrank上都不可见)。如对错误来源有任何更正或帮助，我们将不胜感激。
我基本上把3个链表作为输入，并将它们的系数对应于从0到100的每个幂(幂范围的极限是0到100)，并把它们放在一个新的链表中(头部节点head_node_final)，然后输出它。
我得到正确ans的标准案例:
输入:
2 //2 terms in 1st linked list
1 1 // 1*x
2 10 // 10x^2
2 //2 terms in 2nd linked list
1 0 //1
10 2 // 10x^2
2 //2 terms in 3rd linked list
10 2 //10x^2
1 3 // 1x^3
输出:
(1,3)+(30,2)+(1,1)+(1,0) // x^3+30x^2+x+1
代码:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
class node
{
public:
int power;
int coefficient;
node *next;
};
int main()
{
int n1;
cin >> n1;
node *head_node1 = new node();
int inp_coefficient1;
cin >> inp_coefficient1;
head_node1->coefficient = inp_coefficient1;
int inp_power1;
cin >> inp_power1;
head_node1->power = inp_power1;
node *value = head_node1;
for (int i1 = 1; i1 <= n1; i1++)
{
if (i1 != n1)
{
cin >> inp_coefficient1;
cin >> inp_power1;
node *value_new = new node();
value_new->coefficient = inp_coefficient1;
value_new->power = inp_power1;
value->next = value_new;
value = value->next;
}
else
{
value->next = NULL;
}
}
int n2;
cin >> n2;
node *head_node2 = new node();
int inp_coefficient2;
cin >> inp_coefficient2;
head_node2->coefficient = inp_coefficient2;
int inp_power2;
cin >> inp_power2;
head_node2->power = inp_power2;
value = head_node2;
for (int i2 = 1; i2 <= n2; i2++)
{
if (i2 != n2)
{
cin >> inp_coefficient2;
cin >> inp_power2;
node *value_new = new node();
value_new->coefficient = inp_coefficient2;
value_new->power = inp_power2;
value->next = value_new;
value = value->next;
}
else
{
value->next = NULL;
}
}
int n3;
cin >> n3;
node *head_node3 = new node();
int inp_coefficient3;
cin >> inp_coefficient3;
head_node3->coefficient = inp_coefficient3;
int inp_power3;
cin >> inp_power3;
head_node3->power = inp_power3;
value = head_node3;
for (int i3 = 1; i3 <= n3; i3++)
{
if (i3 != n3)
{
cin >> inp_coefficient3;
cin >> inp_power3;
node *value_new = new node();
value_new->coefficient = inp_coefficient3;
value_new->power = inp_power3;
value->next = value_new;
value = value->next;
}
else
{
value->next = NULL;
}
}
node *head_node_final = new node();
node *value_final = head_node_final;
for (int power_counter = 100; power_counter >= 0; power_counter--)
{
node *node_value1 = head_node1;
while (node_value1 != NULL && node_value1->power != power_counter)
{
node_value1 = node_value1->next;
}
int node_1_return;
if (node_value1 == NULL)
{
node_1_return = 0;
}
if (node_value1 != NULL)
{
node_1_return = node_value1->coefficient;
}
node *node_value2 = head_node2;
while (node_value2 != NULL && node_value2->power != power_counter)
{
node_value2 = node_value2->next;
}
int node_2_return;
if (node_value2 == NULL)
{
node_2_return = 0;
}
if (node_value2 != NULL)
{
node_2_return = node_value2->coefficient;
}
node *node_value3 = head_node3;
while (node_value3 != NULL && node_value3->power != power_counter)
{
node_value3 = node_value3->next;
}
int node_3_return;
if (node_value3 == NULL)
{
node_3_return = 0;
}
if (node_value3 != NULL)
{
node_3_return = node_value3->coefficient;
}
if ((node_1_return + node_2_return + node_3_return) != 0)
{
value_final->power = power_counter;
value_final->coefficient = (node_1_return + node_2_return + node_3_return);
value_final->next = new node();
value_final = value_final->next;
}
if (power_counter == 0)
{
value_final = NULL;
}
}
node *new_value_final = head_node_final;
while (new_value_final->next != NULL)
{
cout << "(" << new_value_final->coefficient << "," << new_value_final->power << ")";
if (new_value_final->next->next != NULL)
{
cout << "+";
}
new_value_final = new_value_final->next;
}
return 0;
}
程序对给定的输入产生正确的输出。
但是你的输入有一个错别字。第三行你把幂和系数搞混了。在这里看到的:
2 //2 terms in 1st linked list
1 1 // 1*x
2 10 // 10x^2 ************ Error: Should be 10 2 ************
2 //2 terms in 2nd linked list
1 0 //1
10 2 // 10x^2
2 //2 terms in 3rd linked list
10 2 //10x^2
1 3 // 1x^3
如果你纠正了这个错误，那么你的程序将显示
(1,3)+(30,2)+(1,1)+(1,0)
。
所以，你的程序基本上是工作的。
但是设计很差，代码质量很低。大量的重复。一切都修好了。没有灵活性。你应该写很多很多注释，然后你会发现自己的问题。
列表的实现似乎是错误的。对于这个问题，使用列表也是一个错误的设计。
但是也许老师告诉你使用列表。也许，甚至不使用现有的std::list，重新发明轮子，创建自己的列表实现。
我不会在这里展示列表实现。在网络上有大量的实现。请看这里的例子。还有很多很多。
如果我们讨论的是设计，就没有必要存储所有给定的术语。幂项应该只有一项，系数应该立即加起来。有了这样的设计，你马上就会得到一个解决方案，std::map将是有用的。
我创建了一个示例(您不能使用它，因为它不包含列表)，基于该方法使用更高级的c++。你可以从中吸取一些灵感。
生成的代码相当紧凑，易于使用。
#include <iostream>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
// Any other number also possible, or event a number given by a user possible
constexpr unsigned int numberOfPolynomials = 3u;
// Here we store a polynomial, consisting of terms
struct Polynomial {
// Powers and its coefficients sortet from large to small
std::map<int,int,std::greater<int>> terms{};
// Overwrite extractor operator. Read a complete polynomial from any stream
friend std::istream& operator >> (std::istream& is, Polynomial& p) {
// First read the number of terms in the polynomial
size_t numberOfTerms{}; is >> numberOfTerms;
p.terms.clear(); // Delete old data
// Read all terms. As given by input
for (size_t index{}; index < numberOfTerms; ++index) {
// Read coefficiend and power from stream
int coefficient{}; int power{}; is >> coefficient >> power;
// Add new coefficient for this power
p.terms[power] += coefficient;
}
return is;
}
// Output all terms in thsi polynomial in the required format
friend std::ostream& operator << (std::ostream& os, const Polynomial& p) {
bool printPlus{};
for (const auto& [power, coefficent] : p.terms)
std::cout << (std::exchange(printPlus, true) ? "+" : "") << '(' << coefficent << ',' << power << ')';
return os;
}
// Add 2 polynomials. Just the coefficients for the relevant powers will be added
Polynomial operator + (const Polynomial& other) const {
Polynomial result{*this};
for (const auto& [power, coefficient] : other.terms) result.terms[power] += coefficient;
return result;
}
};
// Some driver / test code
int main() {
// Here we will store all polynomial that should be read. Anynumber ispossible.
std::vector<Polynomial> polynomials(numberOfPolynomials);
// Read polynomials from std::cin
for (Polynomial& polynomial : polynomials)
std::cin >> polynomial;
// Sum all up
Polynomial sum = std::accumulate(polynomials.begin(), polynomials.end(), Polynomial{});
// Show result of the addition
std::cout << sum;
return 0;
}