# Improvement of sparse polynomial multiplication

1. Problem Description:
The improvement of the multiplication of sparse current polynomials
2. Problem analysis and algorithm design:
The basic idea is to create a structure node to store the coefficient (int), index (int), and a next pointer of each item.
After entering two linked lists A and B:
1. When the exponents are equal, the coefficients are formed; if the added coefficients are not 0, they are stored in the linked list C;
2. If the exponent is not equal, if the exponent of A is less than that of B, all the coefficients and exponents in the node of A are stored in the linked list C;
3. On the contrary, the coefficients and indexes in the nodes of B are all stored in the chain table C;
4. When the last several items of a linked list are more than one, they are also saved in linked list C.
3. Algorithm implementation
```//The improvement of the multiplication of sparse current polynomials

#include<stdio.h>
#include<stdlib.h>

typedef struct ployNode* mul_ploy;

mul_ploy get_tail_point(mul_ploy root);
mul_ploy createList(mul_ploy root);

/****************************************
*The structure of storing polynomials
*exp :  index
*para :  coefficient
*next :  Pointer to the next structure
*****************************************/
struct ployNode
{
int exp;
int para;
mul_ploy next;
};

/****************************************
*****************************************/
mul_ploy get_tail_point(mul_ploy root)
{
while (root->next != NULL)
root = root->next;
return root;
}

/****************************************
*Input the index and coefficient, and put them into the chain list
*root :  Existing list to put
*****************************************/
mul_ploy createList(mul_ploy root)
{
int exp;
int para;
mul_ploy new_node = (mul_ploy)malloc(sizeof(struct ployNode));
new_node->exp = exp;
new_node->para = para;
new_node->next = NULL;
mul_ploy tail = get_tail_point(root);
tail->next = new_node;
}

/****************************************
*Sort from large to small
*new_ploy :  Element node to insert
*****************************************/
{
{
}
else
{
while (temp != NULL)
{
if (temp->exp < new_poly->exp)
{
temp_pre->next = new_poly;
new_poly->next = temp;
break;
}
else
{
if (temp->exp == new_poly->exp)
{
temp->para += new_poly->para;
free(new_poly);
break;
}
else
{
temp_pre = temp;
temp = temp->next;
}

}

}
if (temp == NULL)
{
temp_pre->next = new_poly;
}
}
}

/****************************************
*Polynomial multiplication
*first :  First polynomial
*second :  Another polynomial
*****************************************/
mul_ploy multiply(mul_ploy first, mul_ploy second)
{
if (first == NULL || second == NULL)
return NULL;

int count = 0;

while (first)
{
while (second)
{
mul_ploy new_poly = (mul_ploy)malloc(sizeof(struct ployNode));

new_poly->exp = first->exp + second->exp;
new_poly->para = first->para * second->para;
if (new_poly->para == 0)
free(new_poly);
else
{
if (count)
{
}
else
{
free(new_poly);
count++;
}
}
}
}