0

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

4
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by Rashakil Fol
-3

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

Votes + Comments
Question is about solving polynomial equation, not about polynomial multiplication/addition
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

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

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.