Multiplication and addition of univariate polynomials

  Personal problem solution ：

#include<iostream>
using namespace std;
struct Pair
{
    int x;
    int y;
    Pair() {}
    Pair(int x, int y) :x(x), y(y) {}
};
struct Node
{
    int x;// coefficient 
    int y;// Index 
    Node* next;
    Node() {}
    Node(int& a, int& b)
    {
        x = a; y = b;
        next = NULL;
    }
};
class List
{
public:
    Node* headNode;
    List() { headNode = nullptr; }
    void push_back(int a, int b)
    {
        Node* newNode = new Node(a, b);
        if (headNode == nullptr)
        {
            headNode = newNode;
            return;// Consider the case that the linked list has no elements 
        }
        Node* pMove = headNode;
        while (pMove->next)
        {
            pMove = pMove->next;
        }
        pMove->next = newNode;
    }
    void printList()
    {
        if (headNode == nullptr)
        {
            cout << 0 << " " << 0;
            return;
        }
        Node* pmove = headNode;
        while (pmove->next)
        {
            cout << pmove->x << " " << pmove->y << " ";
            pmove = pmove->next;
        }
        cout << pmove->x << " " << pmove->y;// Prevent printing more spaces 
    }
    List multiply(List& list, int i, int j)
    {
        List newlist; int k = 0; int total = i * j;
        Pair* pair = new Pair[total];
        //1. First find the sum of all the products 
        for (Node* p1 = headNode; p1 != nullptr; p1 = p1->next)
        {
            for (Node* p2 = list.headNode; p2 != nullptr; p2 = p2->next)
            {
                pair[k++] = Pair(p1->x * p2->x, p1->y + p2->y);
            }
        }
        //2. Sort 
        // Traverse the smallest element in the remaining array each time , Insert 
        for (int p = 0; p < total - 1; p++)//-> Each selection total-1 Next time 
        {
            int max_index = p;
            for (int z = p; z < total; z++)
            {
                if (pair[z].y > pair[max_index].y)
                {
                    max_index = z;
                }
            }
            if (max_index != p)
            {
                Pair temp = pair[p];
                pair[p] = pair[max_index];
                pair[max_index] = temp;
            }
        }
        //3. Put it in the list 
        Node* pmove = newlist.headNode;
        for (int q = 0; q < total; q++)
        {
            if (newlist.headNode)
            {
                if (pmove->y == pair[q].y)// Yes bug added ！！！
                {
                    //newlist.push_back(pair[q].x + pmove->x, pair[q].y);
                    pmove->x = pair[q].x + pmove->x;// Be careful : here x It may offset , So make a second judgment 
                    if (!pmove->x)
                    {
                        Node* pt = newlist.headNode;
                        Node* pbeh = newlist.headNode;
                        while (pt != pmove)
                        {
                            pbeh = pt;
                            pt = pt->next;
                        }
                        if (pt != newlist.headNode)
                        {
                            pbeh->next = pt->next;
                            delete pt;
                            pt = nullptr;
                        }
                        else
                        {
                            headNode = pt->next;
                            delete pt;
                            pt = nullptr; pbeh = nullptr;
                        }
                        pmove = pbeh;//pmove Back one 
                    }
                    continue;
                }
                else if (pmove->y > pair[q].y)
                {
                    newlist.push_back(pair[q].x, pair[q].y);
                }
            }
            else { newlist.push_back(pair[q].x, pair[q].y); pmove = newlist.headNode; continue; }
            pmove = pmove->next;
        }
        return newlist;
    }
    List add(List& list)
    {
        Node* p1 = headNode, * p2 = list.headNode;
        List newlist;
        while (p1 && p2)
        {
            if (p1->y > p2->y)
            {
                newlist.push_back(p1->x, p1->y);
                p1 = p1->next;
            }
            else if (p1->y < p2->y)
            {
                newlist.push_back(p2->x, p2->y);
                p2 = p2->next;
            }
            else//equal
            {
                if (p1->x + p2->x != 0)
                {
                    // by 0, Don't add ！！！！
                    newlist.push_back(p1->x + p2->x, p2->y);// Note that the judgment coefficient is not 0
                }
                p1 = p1->next;
                p2 = p2->next;
            }
        }
        while (p1) { newlist.push_back(p1->x, p1->y); p1 = p1->next; }
        while (p2) { newlist.push_back(p2->x, p2->y); p2 = p2->next; }
        return newlist;
    }
};
int main()
{
    int i, j; cin >> i;
    List y1, y2, y3, y4;//y3 It's the product of ,y4 Is the result of addition 
    for (int k = i; k > 0; k--)
    {
        int x, y; cin >> x >> y;
        y1.push_back(x, y);
    }
    cin >> j;
    for (int k = j; k > 0; k--)
    {
        int x, y; cin >> x >> y;
        y2.push_back(x, y);
    }
    y3 = y1.multiply(y2, i, j);
    y4 = y1.add(y2);
    y3.printList();
    cout << endl;
    y4.printList();
    cout << endl;
    return 0;
}

Official solutions and ideas ： 

In fact, it can be based on the first data read in each line , then malloc Using arrays is the most convenient .

#include <iostream>
using namespace std;
typedef struct PolyNode *Polynomial;
// Node structure 
struct PolyNode
{
	int coef;// coefficient 
	int expon;// Index 
	Polynomial next;
};
void Attach(int c, int e, Polynomial *pRear)// When creating a linked list , You need to constantly modify the value of the tail pointer , So pass a pointer to the tail pointer , In order to modify the value of the tail pointer 
{
	Polynomial p;
	p = (Polynomial)malloc(sizeof(struct PolyNode));
	// Assign a value to the new node 
	p->coef = c;
	p->expon = e;
	p->next = nullptr;
	(*pRear)->next = p;
	(*pRear) = p;
}
// Read in polynomials 
Polynomial ReadPoly()
{
	Polynomial rear,p,t;
	p = (Polynomial)malloc(sizeof(struct PolyNode));// The short node of the linked list  
	p->next = nullptr;
	rear = p;
	int termNumber;
	int c, e;
	cout << " Enter the number of terms of the polynomial ：";
	cin >> termNumber;
	cout << " Enter the coefficients and exponents of the polynomial ：";
	while (termNumber--)
	{
		cin >> c >> e;
		Attach(c,e,&rear);
	}
	t = p;
	p = p->next;
	free(t);// Delete the temporarily generated short node 
	return p;
}
// Multiplication of polynomials 
Polynomial Mult(Polynomial p1, Polynomial p2)
{
	Polynomial t1, t2, p,rear,t;
	int c, e;
	if (!p1 || !p2)
	{
		return nullptr;
	}
	t1 = p1; 
	t2 = p2;
	p = (Polynomial)malloc(sizeof(struct PolyNode));
	p->next = nullptr;
	rear = p;
	// First use p1 The first term of times p2, obtain p
	while (t2)
	{
		Attach(t1->coef*t2->coef, t1->expon + t2->expon, &rear);
		t2 = t2->next;
	}
	t1 = t1->next;
	while (t1)
	{
		t2 = p2;
		rear = p;// Give Way rear Point to empty header 
		while (t2)
		{
			c = t1->coef*t2->coef;
			e = t1->expon + t2->expon;
			while (rear->next&&rear->next->expon > e)
			{
				rear = rear->next;
			}
			if (rear->next&&rear->next->expon == e)
			{
				if (rear->next->coef + c)
					rear->next->coef += c;// If the coefficients do not add up to 0, Then the sum of the assignment coefficients 
				// If the coefficients add up to 0, Delete the node 
				else
				{
					t = rear->next;
					rear->next = t->next;
					free(t);
				}
			}
			// Insert a new node 
			else
			{
				t = (Polynomial)malloc(sizeof(struct PolyNode));
				t->coef = c;
				t->expon = e;
				t->next = rear->next;
				rear->next = t;
				rear = rear->next;
			}
			t2 = t2->next;
		}
		t1 = t1->next;
	}
	t2 = p;
	p = p->next;
	free(t2);
	return p;
}
// Add polynomials 
Polynomial Add(Polynomial p1, Polynomial p2)
{
	Polynomial front, rear, temp,t1,t2;
	t1 = p1; t2 = p2;// use t1,t2 Instead of p1,p2, Prevent changes p1,p2 The original value of 
	rear = (Polynomial)malloc(sizeof(struct PolyNode));// Tail pointer 
	rear->next = nullptr;
	front = rear;// Empty header node 
	while (t1&&t2)
	{
		if (t1->expon == t2->expon)
		{
			int sum = t1->coef + t2->coef;
			if (sum)
			{
				Attach(sum, t1->expon, &rear);
			}
			t1 = t1->next;
			t2 = t2->next;
		}
		else if (t1->expon > t2->expon)
		{
			Attach(t1->coef, t1->expon, &rear);
			t1 = t1->next;
		}
		else
		{
			Attach(t2->coef, t2->expon, &rear);
			t2 = t2->next;
		}
	}
	while (t1)
	{
		Attach(t1->coef, t1->expon, &rear);
		t1 = t1->next;
	}
	while (t2)
	{
		Attach(t2->coef, t2->expon, &rear);
		t2 = t2->next;
	}
	temp = front;
	front = front->next;
	free(temp);
	return front;
}
// Print polynomials 
void PrintPoly(Polynomial p)
{
	int flag = 0;// Auxiliary adjustment format output 
	if (!p)
	{
		cout << 0 << " " << 0 << endl;
		return;
	}
	while (p)
	{
		if (!flag)
			flag = 1;
		else
			cout << "  ";
		cout << p->coef << ' ' << p->expon;
		p = p->next;
	}
	cout << endl;
}
int main()
{
	Polynomial p1,p2,ps,pp;
	p1 = ReadPoly();
	p2 = ReadPoly();
	ps = Add(p1, p2);
	pp = Mult(p1, p2);
	PrintPoly(p1);
	PrintPoly(p2);
	PrintPoly(ps);
	PrintPoly(pp);
	return 0;
}

Tortured for a long time bug 

① A comma cannot be followed by a variable that becomes a pointer

The old question , A comma cannot be followed by a variable that becomes a pointer , After the changes

 ② Temporary variables do not return references ！！

 ③ Enter details ： Enter one group at a time , So don't take 2

 ④ In limine pmove The assignment is NULL, And will not follow headNode After inserting the node , And change pmove Value ！！！！！！—> Lead to the problem of cross-border access .

 ⑤ careful ：

 ⑥ Polynomials after merging , Remember to judge , Whether the coefficient is 0, The consolidation factor is 0 To delete a node , Remember to step back .