Member Avatar for Ajantis

Hey people :)

My final exam is now approaching and I am practicing hard.
I've come accross this task which I have no clue how to solve.
It is about solving a polynomial through a linked list - and I really don't know how to even start. Can somebody help a little? Just show me the way how to do it? :) I'd appriciate it.

1.4. Linked lists
2.A polynomial can be represented by a sorted linked list.
3.public class Polynomial {
4.private SortedLinkedList<Term> poly;
5.// constructors and other methods
6.}
7.Where the Term defines the representation of the polynomial term:
8.public class Term implements Comparable<Term>{
9.private double coeff; // coefficient
10.private int exp; // exponent
11.// constructors and other accessor methods
12.}
13.For example,
14.p(x) = 10 x100 + 5 x20 + 3x + 10
15.xp(x) = 10 x101 + 5 x21 + 3 x2 + 10x
16.Write a static method for the class Polynomial to do the polynomial multiplication by x:
17.public static Polynomial xPolynomial ( Polynomial p )
18.Tip: Followings are some public methods provided by these methods.
19.
20.LinkedList:
21.// ******************PUBLIC OPERATIONS*********************
22.// boolean isEmpty( ) --> Return true if empty; else false
23.// LinkedListIterator zeroth( ) --> Return position to prior to first
24.// LinkedListIterator first( ) --> Return first position
25.// void insert( x, p ) --> Insert x after current iterator position p
26.SortedLinkedList:
27.// void insert( x ) --> Insert x
28.// void insert( x, p ) --> Insert x (ignore p)
29.LinkedListIterator:
30.// void advance( ) --> Advance
31.// boolean isValid( ) --> True if at valid position in list
32.// AnyType retrieve --> Return item in current position

polynomial multiplication and addition in the same prog.

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

struct node
{
 signed int coe;
 int pow;
 node *next;
}*start1,*start2,*root,*add_res,*mul_res;

void disp(node *cur)
{
   while(cur!=NULL)
   {
    printf("%dx%d ",cur->coe,cur->pow);
    cur=cur->next;
   }
}

void ins(node **root,int c,int p)
{
  node *temp=new node;
  node *cur=new node;
  cur=*root;
  temp->coe=c;
  temp->pow=p;
  temp->next=NULL;
  int flag=0;
  if(*root==NULL)
  {
   *root=temp;
  }
  else
  {
  //flag=0 for ordinary insertion
  //flag=1 for multiplication
  //without flag, the result will be 2x2 + 3x2
  // and not 5x2(co-eff wont get added for same powers)
   while(cur->next!=NULL && flag==0)
   {
       if(p==cur->pow)
       {
	cur->coe=cur->coe + c;
	flag=1;
       }
	   cur=cur->next;
   }
   if(p==cur->pow && flag==0)   // this is used for multiplication
	cur->coe=cur->coe + c; //addition wont pass into this
   else if(flag==0)                        //condition
     cur->next=temp;
  }

}

void create()
{
 char ch;
 int c,p;
 for(int i=1;i<=2;i++)
 {
  printf("Enter for polynomial %d (decreasing power order)",i);
  ch='c';
  // press s after giving i/p
  while(ch!='s')
  {
   printf("\nCo-eff (space) Power  :");
   scanf("%d %d",&c,&p);
   if(i==1)
    ins(&start1,c,p);
   else if(i==2)
    ins(&start2,c,p);
   scanf("%s",&ch);
  }
  root=NULL;
 }
 printf("Poly 1 \n");
 disp(start1);
 printf("Poly 2 \n");
 disp(start2);
}
void mul()
{
 node *cur1=start1,*cur2=start2;
 while(cur2!=NULL)
 {
   while(cur1!=NULL)
   {
    //multiply co-eff and add the powers
    ins(&mul_res,cur1->coe * cur2->coe,cur1->pow + cur2->pow);
    cur1=cur1->next;
   }
  cur2=cur2->next;
  cur1=start1;
 }
printf("\n\nThe MUL res is \n");
disp(mul_res);
}
void add()
{
 node *cur1=start1;
 node *cur2=start2;

 while(cur1!=NULL && cur2!=NULL)
 {
   int k;
   if(cur1->pow == cur2->pow)
   {
    k=cur1->coe + cur2->coe;
    ins(&add_res,k,cur1->pow);
    cur1=cur1->next;
    cur2=cur2->next;
   }
   else if(cur1->pow > cur2->pow)
    {
   ins(&add_res,cur1->coe,cur1->pow);
     cur1=cur1->next;
    }
   else if(cur2->pow > cur1->pow)
    {
     ins(&add_res,cur2->coe,cur2->pow);
     cur2=cur2->next;
    }
 }
// insert the remaining elements of cur2
if(cur1==NULL)
{
 while(cur2!=NULL)
 {
     ins(&add_res,cur2->coe,cur2->pow);
     cur2=cur2->next;
 }
}
// insert the remaining elements of cur1
else
 while(cur1!=NULL)
 {
     ins(&add_res,cur1->coe,cur1->pow);
     cur1=cur1->next;
 }
 printf("\n\nThe ADD res is \n");
 disp(add_res);
}


void main()
{
start1=NULL;
start2=NULL;
add_res=NULL;
mul_res=NULL;
clrscr();
create();
add();
mul();
getch();
}

the output looks like :

Enter for polynomial 1 (decreasing power order)
Co-eff (space) Power :2 3
w

Co-eff (space) Power :4 2
w

Co-eff (space) Power :8 0
s
Enter for polynomial 2 (decreasing power order)
Co-eff (space) Power :3 3
w

Co-eff (space) Power :5 1
w

Co-eff (space) Power :2 0
s
Poly 1
2x3 4x2 8x0
Poly 2
3x3 5x1 2x0

The ADD res is
5x3 4x2 5x1 10x0

The MUL res is
6x6 12x5 48x3 10x4 40x1 8x2 16x0

commented: He did not ask for the code. Just little guidance on how to solve the problem. It is against the spirit of this forums to hand out code like this +0
commented: Question is about solving polynomial equation, not about polynomial multiplication/addition +0

Show how the polynomial
4x5 - 3x3 + 2x2 - 1
could be implemented as an array and as a linked list

Please do.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.