Linked List help

[stevo356]

Hi guys, I'm both new here, and new to c++ so be gentle!

Over the past short time we've been looking at c++ on our course, but I don't believe it has been taught too well, and I'm struggling to understand what should really be basic concepts? An assignment we've been issued with asks us to enter the details of 40 hills randomly in the form of a linked list (so the details would automatically be inserted randomly). Then further to that, the linked list trasnferred into an array then sorted. (displayed in the cout)

The problem I'm having is I don't know where to start - I've used and modified code from an earlier lab session, but I'm at my wits end trying to understand it and work out how to do what I want.

Here is the code from my header file to show the struct I've setup, but I've no idea how to take it to the level that's expected of me.

If anyone can help or provide any pointers I'd be very greatful - as I'm really hoping to do well in learning c++ beyond this assisgnemt.

#include <iostream>
using namespace std;

                //define a node as a structure
struct Hills{       //a structure that can be 
    int hillsize;
    int gridref;
    int distanceFromHome;
    bool climbed;   //thought of as a simple class
    Hills *link;    //All fields are public
};


class LinkedList{   //now declare the class
private:
    Hills *head;        //pointer to the first node
    Hills *last;        //pointer to the last node
    int count;      //number of nodes
public:
    LinkedList();       //constructor 

    void insertNodeAtStart(int newinfo);    // inserts a node at start of list
    void insertNodeAtEnd(int newinfo);      // inserts a node at end of list
    int getNodeCount();  //returns the number of nodes
    Hills* getFirst();   //returns the pointer to the 
                      //the first node - the value of "head"
    void deleteFirstNode(); //deletes the first node in the list 

    bool findNumber(int number);  //Q6 see if "number" is in the list
    void deleteNode(int number);  //Q7 delete a node with "number" as its data 

};  //end of class declarations. REMEMBER THE SEMICOLON

Thanks in advance

[stevo356]

Just to add, I can get the thing to output one of the variables from the struct, but no more, thats the particular point where i'm sturggling a bit.

[Ancient Dragon]

The next step is to write the implementation c++ code for each of the methods you have in that class. Here's a start:

#include "hills.h" // or whatever you named the file you posted

// constructor
LinkedList::LinkedList()
{
    // initialize the class variables
    head = 0;
    tail = 0;
    count = 0;
}

[stevo356]

Yeah, I've made some of the file as follows, the problem is though, I can't work out how to pass all the values from the struct in the header file. I've tried various things, to no avail.

So at the moment, all I can seem to pass is hillsize.

#include "LinkedList1.h"   

LinkedList::LinkedList(){   //constructor
    head = NULL;
    last = NULL;
    count = 0;
}

void LinkedList:: insertNodeAtStart(int newInfo){
    Hills *nextNode;            
    nextNode = new Hills;       
    Hills->hillsize = newInfo;  

    nextNode->link = head;  

    head = nextNode;    

    count++;            

    if(last == NULL){   
        last = nextNode;    
    }               
}

void LinkedList:: insertNodeAtEnd(int newInfo){
    Hills *endNode;         
    endNode = new Hills;
    endNode->hillsize = newInfo;
    endNode->link = NULL; 

    count++;
    if(head == NULL){       
        head = endNode;     
        last = endNode;
    }
    else{                       
        last->link = endNode;   
        last = endNode;         
    }                           
}

int LinkedList::getNodeCount(){return count;}

Hills* LinkedList::getFirst(){return head;}

void LinkedList::deleteFirstNode(){
    if(count > 0){
        Hills *temp = head; 

        head = head->link;  

        delete temp;        
        count--;
    }
    else{
        cout<<"There are no nodes to delete."<<endl;
    }

}


bool LinkedList::findNumber(int number){  
    Hills *current;     
    current = head;     

    for (int i=1; i<=count; i++){        
        if(current->hillsize == number){    
            return true;    
        }
        current = current->link;    
    }
    return false;   
}

[Ancient Dragon]

Just pass the entire struct

void LinkedList:: insertNodeAtStart(struct Hills& info){

Or you could pass the items individually

void LinkedList:: insertNodeAtStart(int hillsize, int gridref, int stance, bool climbed){

[stevo356]

Thats cleared up much of my problems. However I now get this error (better than the 30 I was getting before, mind)

"c:\documents and settings\stephen mcginley\desktop\cwk\cwk\main1.cpp(17) : error C2664: 'LinkedList::insertNodeAtStart' : cannot convert parameter 1 from 'int' to 'Hills'
        No constructor could take the source type, or constructor overload resolution was ambiguous"

Here's what my main file looks like so far (well the bit that matters just now)

#include <ctime>
#include <cstdlib>
#include "LinkedList1.h"

int main(){
//
    int hillsize;
    int gridref;
                int distanceFromHome;
                bool climbed;
    srand( (unsigned int) time( NULL ));
    hillsize = (rand() % 1400) + 3000;
    //distanceFromHome = (rand() % 280) + 20;

    gridref = (rand() % 100000) +400000;

    LinkedList list;
    for (int i=0; i<40; i++){
    list.insertNodeAtStart();
    //list.insertNodeAtStart (distanceFromHome);
    //list.insertNodeAtStart (climbed);

    }

[Ancient Dragon]

you have to make the same change(s) in the class definition of the header file.

[stevo356]

Ok, i've changed the setup as suggested, when it comes to the output, it shows me 40 lines of the same thing "-84215041"

Any ideas?

[Ancient Dragon]

post current code.

[stevo356]

Header file

#include <iostream>
using namespace std;

                //define a node as a structure
struct Hills{       //a structure that can be 
    int hillsize;
    int gridref;
    int distanceFromHome;
    bool climbed;   //thought of as a simple class
    Hills *link;    //All fields are public
};


class LinkedList{   //now declare the class
private:
    Hills *head;        //pointer to the first node
    Hills *last;        //pointer to the last node
    int count;      //number of nodes
public:
    LinkedList();       //constructor 

    void insertNodeAtStart(int hillsize, int gridref, int distanceFromHome, bool climbed);  // inserts a node at start of list
    void insertNodeAtEnd(int hillsize, int gridref, int distanceFromHome, bool climbed);    // inserts a node at end of list
    int getNodeCount();  //returns the number of nodes
    Hills* getFirst();   //returns the pointer to the 
                      //the first node - the value of "head"
    void deleteFirstNode(); //deletes the first node in the list 

    bool findNumber(int number);  //Q6 see if "number" is in the list
    void deleteNode(int number);  //Q7 delete a node with "number" as its data 

};  //end of class declarations. REMEMBER THE SEMICOLON 

Class file

#include "LinkedList1.h"   

LinkedList::LinkedList(){   //constructor
    head = NULL;
    last = NULL;
    count = 0;
}

void LinkedList:: insertNodeAtStart(int hillsize, int gridref, int distanceFromHome, bool climbed){
    Hills *nextNode;            
    nextNode = new Hills;       
    //nextNode = newInfo;   

    nextNode->link = head;  

    head = nextNode;    

    count++;            

    if(last == NULL){   
        last = nextNode;    
    }               
}

void LinkedList:: insertNodeAtEnd(int hillsize, int gridref, int distanceFromHome, bool climbed){
    Hills *endNode;         
    endNode = new Hills;
    //endNode = newInfo;
    endNode->link = NULL; 

    count++;
    if(head == NULL){       
        head = endNode;     
        last = endNode;
    }
    else{                       
        last->link = endNode;   
        last = endNode;         
    }                           
}

int LinkedList::getNodeCount(){return count;}

Hills* LinkedList::getFirst(){return head;}

void LinkedList::deleteFirstNode(){
    if(count > 0){
        Hills *temp = head; 

        head = head->link;  

        delete temp;        
        count--;
    }
    else{
        cout<<"There are no nodes to delete."<<endl;
    }

}


bool LinkedList::findNumber(int number){  
    Hills *current;     
    current = head;     

    for (int i=1; i<=count; i++){        
        if(current->hillsize == number){    
            return true;    
        }
        current = current->link;    
    }
    return false;   
}



void LinkedList:: deleteNode(int number){
    bool nodeFound = false; //need this to check at the end if number node found
    if(head->hillsize == number){//special case - if it's in the first node
        deleteFirstNode();
        nodeFound = true;
    }
    else{
        if(count > 1){
            Hills *current;     //use these 2 node pointer variables to go through
            Hills *trailCurrent; //the lust checking for one with the required data
            current=head->link; //To start, set them to point to the first & second nodes 
            trailCurrent=head;
            while(current != NULL){  //while not end of list

                if(current->hillsize == number){
                    trailCurrent->link=current->link; //the node behind the one to
                                                //be deleted will now point to the 
                                                //node after the one being deleted
                    delete current;  
                    count--;      //reduce count by 1
                    cout<< " The number has been deleted "<<endl;
                    nodeFound = true;
                    break;  //current is deleted so it can't be used in "while"     
                            //condition. Use "break" to end loop immediately.  
                            //Execution continues with the statement following 
                            //the loop.
                }
                else{
                     current=current->link; //move our two node pointers up to
                     trailCurrent=trailCurrent->link; //the next set of nodes
                }
            }
        }
    }
        //if the node not found output message
    if(!nodeFound){
        cout<<"no node with that data was found."<<endl;
    }

}

Main Output file

#include <ctime>
#include <cstdlib>
#include "LinkedList1.h"

int main(){
//
    int hillsize;
    int gridref;
    srand( (unsigned int) time( NULL ));
   hillsize = (rand() % 1400) + 3000;
    //distanceFromHome = (rand() % 280) + 20;
    //climbed = (rand() % 1) + 1;
    gridref = (rand() % 100000) +400000;

    LinkedList list;
    for (int i=0; i<40; i++){
    list.insertNodeAtStart(hillsize, gridref, 0, true);
    //list.insertNodeAtStart (distanceFromHome);
    //list.insertNodeAtStart (climbed);

    }

    int noOfNodes = list.getNodeCount();
    cout <<"There are "<< noOfNodes <<" nodes in the list."<< endl;

    Hills *current;
    current = list.getFirst();
    cout <<current<< endl;
    //cout <<current->gridref<< endl;
    for (int i=2; i<=noOfNodes; i++){
        current = current->link;
        cout <<current->hillsize<< endl;
        cout <<current->gridref<<endl;
    }

    //now test the findNumber function (Q6)
    //ask the user to enter a number and see if it's in the list
    int number;
    cout<<"Enter a number you're looking for: ";
    cin>>number;
    if (list.findNumber(number)){
        cout<<number<<" is in the list."<<endl;
    }
    else{
        cout<<number<<" is not in the list."<<endl;
    }
}

[mitrmkar]

You need to randomize the hillsize and gridref values within the loop in which you initialize the list.

[stevo356]

still does the same for whatever reason. Its the only bit I've got left to fix as well:(

[Ancient Dragon]

In LinkedList:: insertNodeAtStart() you set the pointers but never set the values of the Hills structure to the value of the parameters to that function. And do the same thing with the other insert function.

void LinkedList:: insertNodeAtStart(int hillsize, int gridref, int distanceFromHome, bool climbed){
    Hills *nextNode;			
    nextNode = new Hills;		
    //nextNode = newInfo;	
    nextNode->hillsize = hillsize;
    nextNode->gridref = gridref;
    nextNode->distanceFromHome = distanceFromHome;
    nextNode->climbed = climbed;

    nextNode->link = head;	
							
    head = nextNode;	

    count++;			
	
    if(last == NULL){	
        last = nextNode;	
    }	

}

Now, the numbers in all the nodes are the same because that's the way they are initialized in main(). If you want them to be different, and I suspect you do, then you have to re-randomize them on each loop iteration

for (int i=0; i<40; i++){
        hillsize = (rand() % 1400) + 3000;
        gridref = (rand() % 100000) +400000;
        list.insertNodeAtStart(hillsize, gridref, 0, true);
    }