An Instance Of Polynomial Using Link List

1.    User Requirement

Designs a Link List based Polynomial and provide operations on it such as creating polynomial, add, fix or remove items, calculating and outputting polynomial. Calculating should include multiplication at least.

2.    User Requirement analysis

A polynomial has many items and items with same power can shrink into one item. So the polynomial can be stored and sorted by power order.

The polynomial should provide operations. It includes most base operations of Link List such as inserting or removing. Sum of the polynomial may be optional.

The insert or arithmetic operations may produce the item change or calculate, so the item should also provide base input/output and arithmetic operations.

3.    Design

Because the polynomial stores items with a list, it can be inherited from an abstract date type (ADT) List. Then add new operations to fit for users. Each item in the polynomial should have member variables to store coefficient and power. Then use Link class to link them into a list.

1)      Date structure

Base class: (ADT)

//list abstract class

template <class Elem>

class List

{

       public:

              //reinitial the list

              virtual void clear()=0;

              //insert an element at the front of the right partition

              virtual bool insert(const Elem&)=0;

              //append an element at the end of the right partition

              virtual bool append(const Elem&)=0;

              //remove the first element of right partition

              virtual bool remove(Elem&)=0;

              //place fence at list start,making left partition empty

              virtual void setStart()=0;

              //place fence at list end,making right partition empty

              virtual void setEnd()=0;

              //move fence one step left,no change if already at start

              virtual void prev()=0;

              //move fence one step right,no change if already at end

              virtual void next()=0;

              //return length of left partition

              virtual int leftLength() const=0;

              //return length of right partition

              virtual int rightLength() const=0;

              //if pos or more elements are in the list,set the size

              //of left partition to pos and return true.Otherwise ,

              //do nothing and return false

              virtual bool setPos(int pos)=0;

              //return in first parameter the first element of the

              //right partition.return true if successful,false if

              //the right partition is empty

              virtual bool getValue(Elem&) const=0;

              //print the contents of the list

              virtual void print()=0;

};

It describes the basic operations on a List.

 

Node class: (generic design)

template <class T1,class T2>

class Elem

{

       public:

              T1 power;

              T2 coeffi;

 

              Elem();

              Elem operator+(const Elem& e1);

              Elem operator*(const Elem& e1);

              Elem& operator=(const Elem& e2);

              Elem& operator+=(const Elem& e2);

};

The items in polynomial provide some operations. The operands of Addition operator must have same power.

 

Link class: (generic design)

template<class Elem>

class Link

{

      public:

          Elem element;    //Value for this node

          Link *next;           //Pointer to next node in list

}；

The class Link linked all elements in a polynomial. For generic design, users can define their element class. Because items in polynomial have fixed structure, and items should provide operations, users had better to use this node class.

 

Polynomial class: (generic design)

Member variable definitions:

template <class Elem>

class Polyno:public List<Elem>

{

       public:

              std::string name;

       private:

              Link<Elem>* head;

              Link<Elem>* tail;

              Link<Elem>*       fence;

 

              int leftcnt;

              int rightcnt;

}；

Instruction:

“name”: refers to the polynomial name such as letter ‘f’ in ‘f(x)’, it do not have any relationship with other operations except output.

“head”, ”tail”, ”fence”: pointers to the storage of node. head point to the head node, and first node in the polynomial is head->next.

“leftcnt”, ”rightcnt”: refer to the number of elements in the polynomial left or right of fence.

Member function declaration:

template <class Elem>

class Polyno:public List<Elem>

{

       private:

              void init();

              void removeall();

       public:

              Polyno();

              Polyno(Polyno&);

              ~Polyno();

              void clear();

              bool insert(const Elem&);

              //sorting store,append is the same as insert

              bool append(const Elem& it);

              bool remove(Elem&);

              void setStart();

              void setEnd();

              void prev();

              void next();

              int leftLength() const;

              int rightLength() const;

              bool setPos(int pos);

              bool getValue(Elem& it)const;

              //set value at current position

              virtual bool setValue(const Elem& it);

              Polyno operator +(Polyno&);

              Polyno operator *(Polyno&);

              Polyno& operator =(Polyno);

              bool operator ==(Polyno&);

              void print() ;

};

most of the member function can be known by the name.

init() , removeall() : private member function, designed for other member function only.

insert(), append() : add an element into the polynomial. The polynomial used sorted storage, there is no different between these two functions. Any element to be inserted will be checked and the program determines where to insert or whether to need combination.

remove() : remove the item fence->next. Because locate fence is complex and remove may destroy data, user should beware.

setValue() : set fence->next value. It is mainly for combine items with same power.

clear() : delete all items in the polynomial and initial it.

print() : output polynomial with the form f(x)=(-3)x^(-6)+7+8x^9+(-17)x^16   Each negative numbers will be with parentheses and the whole polynomial will be printed in ascend order.