0

For a class project in my Object Oriented Programming class, we have been tasked with writing a program that creates a Polynomial Data Type. The Polynomial is to be a singly linked list of Nodes that contain a term.

A term and a node containing said term would be like the following:

struct Term {
        double coefficient;
        unsigned int exponent;
    };

struct Node {
        Term term;
        Node* next;
    };

I have a class called Polynomial that has some methods for creating and manipulating the polynomial:

class Polynomial {

    public:
        Polynomial();
        ~Polynomial();
        void addTerm(Term term);
        unsigned int degree();
        double coefficientFor(unsigned int exponent);
        void clear();

    private:
        Node* Head;
    };

We are to construct the Polynomial to have an initial term that has a value of 0:

Polynomial::Polynomial()
    {
        Term term_construct;
        term_construct.coefficient = 0;
        term_construct.exponent = 0;

        Head->term = term_construct;
        Head->next = NULL;
    }

My problem is no arising with the addTerm method. The method takes a term and then inserts a node with that term into the singly linked list. But there is a catch. The linked list must be ordered in descending order based on the exponent of the term that is passed into the method.

This is all I have so far:

void Polynomial::addTerm(Term term)
    {
        Node* Temp = new Node;
        Temp->term = term;
        Temp->next = NULL;

        
    }

For example, if terms with exponents 6, 7, 3, and 2 were entered, then the head node would contain the term with exponent = 7, the next node would have exponent = 6, and so on.

Also, if a term is entered that has an exponent that is equivalent to an exponent of another existing term, instead of adding the term to the list, the coefficient of the two terms must be added together. If the coefficient is equal to 0 after adding the two terms together, the node must be deleted from the linked list.

I have always struggled with understanding linked lists and how to implement them. But with the additional requirements for adding the Nodes to the linked list, I have become completely lost in what I am doing.

Can anyone help lead me down the right path?

ParkerHarrelson123
  • 49
  • 1
  • 7
  • Iterate the list until either you find a smaller term or the end of the list, then link the new term between the previous term in the list and the term after it. – user4581301 Feb 25 '21 at 18:49
  • The best trick I know of for getting a grip on linked lists (and other graph data structures) is to draw a lot of pictures. When you can visualize the problem, usually the problem becomes clear. God willing, so does the solution. – user4581301 Feb 25 '21 at 18:51
  • Solve this one problem at a time. It may be easier to write a function that takes a reference to a node as a parameter and removes the subsequent node so you can use it for all your removal needs. Then you call this `remove_next` function instead of embedded removal code inside your term-merging case. – user4581301 Feb 25 '21 at 18:55
  • Why allocate a new object before you're sure it's needed? You still can allocate the `Node` later, if actually needed. In your cast I'd simply iterate though the list until you find the node where the exponent of the term of the next element is smaller or equal than the exponent of the term you're trying to insert. At this point you've got all options without starting the iteration again: Insert a new element and add the term to an existing element (possibly removing it). Of course insertion at the front of the list is a special case... – fabian Feb 25 '21 at 18:57
  • Side note: See the **Alternative Using Pointer To Pointer** discussed [at this link](https://stackoverflow.com/a/22122095/4581301) for a way to simplify the amount of book-keeping and special cases required to remove a node form a singly linked list. If you keep a pointer to the previous node's next pointer, you keep the insertion point of your new node (or removal point) and the node after it at the same time. This also abstracts away the need for special cases to handle the list's head pointer because the head pointer is nothing but a next pointer with a different name. – user4581301 Feb 25 '21 at 19:02
  • Another good trick tis to make use of [aggregate initialization](https://en.cppreference.com/w/cpp/language/aggregate_initialization). `Node* Temp = new Node{term, NULL};` saves a few lines of typing and set you up for stuff like `(*linkp) = new Node{term, (*linkp)->next};`, turning inserting a node into a one-liner. – user4581301 Feb 25 '21 at 19:06

0 Answers0