## Search This Blog

Simplicity is the ultimate sophistication.” — Leonardo da Vinci
Contact me: sreramk360@gmail.com

## Friday, 27 March 2015

### polynomial multiplication and addition implementation

Implementation of polynomial multiplication and addition using linked list

/*
polynomial multiplication and addition implementation
*/

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

enum BOOL {FALSE, TRUE};
typedef int BOOL; // the more obvious choice would be char, but int is more
// time efficient as it uses a basic memory unit optimal for the
// particular processor design, by default

struct NODE;
typedef struct NODE Node;
typedef Node* PtrNode;
typedef PtrNode List;
typedef PtrNode Position;
typedef List Polynomial;
struct polyTerm {
int degree; // the power of the taken term
int coeff; // the coefficient of the term
};
typedef struct polyTerm DataType; // this is a default data type

struct NODE{ // single link list node
DataType data;
PtrNode next;
};
// vital ones>>>>>>>>>>>>>>>>>>>>>>>>>
PtrNode NewPoly() // returns the List's header
{
PtrNode tempNode =  malloc(sizeof(Node));
tempNode->next = NULL;
return tempNode;
}
Position NewNode()
{
// to do: add code to create the other parts of
// the memory to be allocated.
return malloc(sizeof(Node)); // for old compilers,
// explicit type conversion like (Node) is needed to be
//used.
}

void Delete(PtrNode node)
{
// to do: add code to clear the other parts of
// the dynamically allocated memory
free(node);
}

void DeleteList(List L)
{
PtrNode tempNode = L->next, tempNode2;
while (tempNode != NULL)
{
tempNode2 = tempNode->next;
Delete(tempNode);
tempNode = tempNode2;
}
L->next = NULL;
}

void FreeList(List L)
{
DeleteList(L);
free(L);
}

void Insert ( List L, DataType data, Position pos)
{
Position tempPos;
tempPos = NewNode(); // creates and allocates memory space
if(tempPos == NULL)
{
fprintf(stderr, "error: request for allocation of memory using function \"malloc\" rejected");
return;
}
tempPos->data = data;
tempPos->next = pos->next;
pos->next = tempPos;
}

//*****************************************************
void DisplayElement(DataType element)
{

// to do: add display code here
printf("%dx^%d", element.coeff, element.degree);
}
void Display (List L)
{

Position pos = L->next;
if(pos == NULL)
return;
while (pos != NULL)
{
DisplayElement(pos->data);
if(pos->next != NULL)
printf(" + ");
pos = pos->next;
}
}

Polynomial AddPolynomial(const Polynomial p1, const Polynomial p2)
{
Polynomial retPoly = NewPoly();
Position p_1 = p1->next, p_2 = p2->next, top = retPoly;
DataType tempTerm;
while (p_1 && p_2)
{
if(p_1->data.degree > p_2->data.degree)
{
Insert(retPoly, p_1->data, top);
p_1 = p_1->next;
}
else if(p_1->data.degree < p_2->data.degree)
{
Insert(retPoly, p_2->data, top);
p_2 = p_2->next;
}
else if(p_1->data.degree == p_2->data.degree)
{
tempTerm.degree = p_1->data.degree;
tempTerm.coeff = p_1->data.coeff + p_2->data.coeff;
Insert(retPoly, tempTerm, top);
p_1 = p_1->next;
p_2 = p_2->next;
}
top = top->next;
}
if(p_1 != NULL)
for(;p_1; p_1 = p_1->next, top = top->next)
Insert(retPoly, p_1->data, top);
else if (p_2 != NULL)
for(;p_2; p_2 = p_2->next, top= top->next)
Insert(retPoly, p_2->data, top);
return retPoly;

}
DataType multyplyTerms(DataType t1, DataType t2)
{
DataType t3;
t3.coeff  = t1.coeff * t2.coeff;
t3.degree = t1.degree + t2.degree;
return t3;
}

Polynomial PolyMultiply(const Polynomial p1, const Polynomial p2)
{ /// the runtime of this function is O(M^2 + MN)
Polynomial retPol = NewPoly();
Polynomial P_1 = p1->next, P_2 = p2->next, top = retPol;
DataType tempData;
while(P_1)
{
top = retPol;
P_2 = p2->next;
while (P_2)
{
tempData = multyplyTerms(P_1->data, P_2->data);
while(top->next && top->next->data.degree > tempData.degree)
top = top->next;// this loop terminates when the data field in the next iteration
// is either equal to or lesser the the current

if(top->next == NULL) // if top->next is null, terms just get inserted at the top
{ // this does not occur when P_1 != p1->next. but for that condition being false,
// insertion happens consecutively
Insert(retPol, tempData, top);
top = top->next;
}
else if(top->next->data.degree != tempData.degree)
{ // checks for the equality of degree. If they are not equal, the term just gets inserted
Insert(retPol, tempData, top);
top = top->next;
}
else // this condition is executed when top->next->data.degree == tempData.degree
top->next->data.coeff = tempData.coeff + top->next->data.coeff; // just add terms of same power
P_2 = P_2->next;
}
P_1 = P_1->next;
}
return retPol;
}
Polynomial GetPoly(const char* txt)
{
Polynomial p = NewPoly();
Polynomial top = p;
char ch = '\0';
DataType temp;
printf(txt);
while (ch != 'n' && ch != 'N')
{
printf("\n enter coefficient");
scanf("%d", &temp.coeff);
printf("\n enter power");
scanf("%d", &temp.degree);
Insert(p, temp, top);
top = top->next;
printf("\n do you want to add another term (Y/N)?");
ch = getch();
}
return p;
}
int main()
{
Polynomial P1 = GetPoly("\nenter the terms of the first polynomial:\n");
Polynomial P2 = GetPoly("\nenter the terms of the second polynomial:\n");
Polynomial P_mult = PolyMultiply(P1, P2);
printf("\nthe first polynomial:\n");
Display(P1);
printf("\nthe second polynomial:\n");
Display(P2);
printf("\n\nthe sum of the two polynomial:\n");
printf("\n\nthe product of the two polynomials:\n");
Display(P_mult);
FreeList(P1);
FreeList(P2);
FreeList(P_mult);
getch();
return 0;
}

copyright (c) 2015 K Sreram.