Problems with Linked List and pointers

[rohanprabhu]

I've tried to implement a list within a class. I did this so that I can make 2 or more objects, where each object has a list as it's member. Here is the code to it:

struct coeffecient {
    int num;
    int den;
};

struct polynomial {
    float power;
    coeffecient coeff;
    int polarity;
};

/* Linked List definitions and implementation */

struct Node {
    polynomial info;
    Node *next;
};

class algebraList {
    public:
        Node *start, *newptr, *save, *ptr, *rear;
        
        void Insert_End(Node *np) {
            if(start == NULL) {
                start = rear = np;
            } else {
                rear->next = np;
                rear = np;
            }
        }
        
        void Display(Node *np) {
            while(np != NULL) {
                cout<<np->info.power<<" -> ";
                np = np->next;
            }
    
            cout<<"\n";
        }
        
        void additionalNode(polynomial x) {
            newptr = createNewNode(x);
            
            if(newptr != NULL) {
                cout<<"new node created..."; getch();
            } else {
                cout<<"error creating node.."; getch(); exit(1);
            }
        
            cout<<"inserting node in list..."; getch();
            Insert_End(newptr);
        }
        
        Node * createNewNode(polynomial n) {
            ptr = new Node;
            ptr->info = n;
            ptr->next = NULL;
            return ptr;
        }
};

And i accept data by:

polynomial x;

cout<<"\n Enter power for the new node: ";
cin>>x.power;
cout<<"creating new node.. "; getch();
        
listOne.additionalNode(x);

Whenever additionalNode is called, it shows 'Creating new node..', and 'new node created...' messages, as I've written in the additionalNode function [for error checking]. but, after that, when the program tries to run the Insert_End function, the program fives an error, 'The program has encountered a problem and needs to close' and closes.

Please help...

 

[shwx]

I think maybe the problem is here:

              Node *start, *newptr, *save, *ptr, *rear;

for these data members are all haven't been initialized. I am not very sure whether in C++ they will be initialized, but in java they really will be.
So you'd better try it yourself for ensurence.

good luck!

 

[Hurkyl]

As shwx said, you have not initialized your data; you have instructed the computer that, when it creates an instance of class algebraList, it's allowed to fill in the variables start, newptr, save, ptr, and rear with whatever values it feels like using at the time. (And, luckily for you, the program decided to use some values that made your program crash, so that you know there is an error!) The same is true when you construct an instance of struct Node. You need to make a constructor for your classes that initialize all the variables properly.


Now, some style points...

The variable newptr has absolutely nothing to do with the structure of the list -- it's an implementation detail of the additionalNode function. Therefore, it should not be a member of the class, but instead a local variable of the function.

Your functions createNewNode and Display have nothing to do with individual instances of class algebraList; they should be declared static, or possibly changed to global functions.

(Incidentally, I would have expected the Display function to take no argument and display the linked list; why did you write it as you did?)

I count three different styles of method names and at least two different styles of type names; if possible, you should pick a single style and use it consistent.

 

[Hurkyl]

Incidentally, if this isn't supposed an exercise in how to write linked lists, you would probably be better off using the C++ standard template library; the STL provides you with the class std::list which implements a doubly-linked list, the std::vector class which implements a resizable array, and several other container classes.

 

[rohanprabhu]

following your suggestions and critique from elsewhere, this is what I've finally arrived at:

class algebraList {
    List *start;
    List *end;
    
    public:    
    algebraList() {
        start = NULL;
        end = NULL;
    }
    
    ~algebraList() {
        List *nx = start;
        
        while(nx != NULL) {
            delete nx;
            nx = nx->next;
        }
    }        
    
    void addElement(polynomial *poly) {
        List *nx = new List;
        nx->info = *poly;
        nx->next = NULL;
        
        if(start == NULL) {
            start = end = nx;
        } else {
            end->next = nx;
            end = nx;
        }                
    }
    
    void displayList() {
        List *nx = start;
        
        while(nx != NULL) {
            cout<<nx->info.value<<endl;
            nx = nx->next;
        }
    }
};

 

[Hurkyl]

It looks reasonable, except for one (common) error in that code:

 while(nx != NULL) {
            delete nx;
            nx = nx->next;
        }

Once you've deleted the object to which nx points, you shouldn't try to access it! You have no guarantee that that memory will still contain the data you want, or that the operating system will even allow you to access it! (fortunately or unfortunately, depeding on your POV, this code will usually do what you want. But really, you want to guarantee it does what you want!)

You need to advance nx before you delete the node. (Which means you will need to make a temporary copy of the pointer to the node you want to delete)



Oh, and another incidental comment: the structure you call 'polynomial' appears to be representing a 'monomial'. (Of course, every monomial is a polynomial, but the name might be misleading to someone else reading your code)

 

[rohanprabhu]

Once you've deleted the object to which nx points, you shouldn't try to access it! You have no guarantee that that memory will still contain the data you want, or that the operating system will even allow you to access it! (fortunately or unfortunately, depeding on your POV, this code will usually do what you want. But really, you want to guarantee it does what you want!)

you were fast, but not as fast as the guys here: http://tinyurl.com/2mvdaf :p, nevermind, here is the code i modified:

~algebraList() {
    List *nx = start;
    List *np = NULL;
        
    do {
        np = nx->next;
        delete nx;
        nx = np;
    } while(np != NULL);
}

Oh, and another incidental comment: the structure you call 'polynomial' appears to be representing a 'monomial'. (Of course, every monomial is a polynomial, but the name might be misleading to someone else reading your code)

Actually, i did the current thing for only debugging purposes.. and in my real program too.. the structure 'polynomial' actually refers to a term of the polynomial only. so, the polynomials x^2, -2*x and 1 when added to an 'algebraList' will make: $x^2 - 2x + 1$

Here is the actual structure of 'polynomial':

struct coeffecient {
    int num;
    int den;
};

struct polynomial {
    int power;
    coeffecient coeff;
    /* bool polarity; */
};

oh yeah.. and btw.. thanks a lot ;)