Thread: help with nodeType function?

> how to insert data with the insertinorder if the list is empty?
Well if the list is empty, then the list is just the node you create.

> void IPlist::insertInOrder(string address)
There are two serious problems with this.
1. you create a new node each time around the while loop.
2. you keep searching, even after you've found the place to insert.

At the start of main, have something like this

Code:

ip.display();  // should be empty!
ip.insertInOrder("b"); // initial
ip.display(); // 1 element
ip.insertInOrder("a"); // at start
ip.display();
ip.insertInOrder("d"); // at end
ip.display();
ip.insertInOrder("a"); // already present, increment count
ip.display();

Then single step through the code with the debugger, making sure everything points to where it should. Say for example you insert "b" OK, but when you come to print it, it's gone, then you've found a bug. Backtrack through the code to find out where you "lost" it.

The while loop just finds the place to insert into the list.

I usually use two pointers, next and prev

Code:

prev = NULL
next = head of list
while ( search is false ) {
  prev = next;
  next = next->next;
}
// insert

There are several cases to worry about
next and prev both null - the list is empty
prev is null - insert at the head of the list
next is null - insert at the tail of the list
otherwise, insert between prev and next

With less than 3 minutes effort on your part - nope - try harder.

*shrug*

All the //!! bits are things I've changed

Code:

#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;

struct node
{
   string IPaddress;
   int count;
   node *link;
};

class IPlist
{
   // contains an ordered list of IP addresses and a count of each
   // occurrence
   public:

    IPlist();  // default constructor
               // creates a new empty list

    ~IPlist(); // destructor - reallocates all dynamic memory of list

    bool empty() const; 
               // precondition : none
               // postcondition : returns true if list is empty 
               //                 and otherwise false

    void insertInOrder(string address);
               // precondition : list is ordered and address is not in list
               // postcondition : list is ordered and contains address

    void display() const; 
               // precondition : none
               // postcondition : the list has been displayed 
               // one record per line, tab-separated
               // with heading IPaddress Count
    private:
    
       node *list;
};

    IPlist::IPlist()
    // default constructor
    // creates a new empty list
{
    list=NULL;
}

    IPlist::~IPlist() 
    // destructor - reallocates all dynamic memory of list
{
    //!! delete [] list;
    //!! Walk the list and delete each node
    node *head = list;
    while ( head ) {
        node *temp = head->link;
        delete head;
        head = temp;
    }
}

    bool IPlist::empty() const 
    // precondition : none
    // postcondition : returns true if list is empty 
    //                 and otherwise false
{
         return list==NULL;
}
               

    void IPlist::insertInOrder(string address)
// precondition : list is ordered and address is not in list
// postcondition : list is ordered and contains address
{
    node *next = list, *prev = NULL;
    // find the right place
    while ( next != NULL && next->IPaddress < address ) {
        prev = next;
        next = next->link;
    }

    // create a new node (make it a class with a constructor)
    node *newnode = new node;
    newnode->IPaddress = address;
    newnode->count = 1;
    newnode->link = NULL;

    // check cases
    if ( next == NULL && prev == NULL ) {
        // empty list
        list = newnode;
    } else
    if ( prev == NULL ) {
        // new head of list, next being the old head
        newnode->link = next;
        list = newnode;
    } else
    if ( next == NULL ) {
        // new tail of list, prev being the last of the current list
        prev->link = newnode;
    } else {
        // in the middle
        newnode->link = prev->link;
        prev->link = newnode;
    }
}

    void IPlist::display() const
               // precondition : none
               // postcondition : the list has been displayed 
               // one record per line, tab-separated
               // with heading IPaddress Count
{
   node *current=list;
   cout<<"IPaddress   Count "<<endl; //!!
   while(current!=NULL)
   {
       cout<<current->IPaddress<<"   "<<current->count<<endl; //!!
       current=current->link;
   }
   cout << endl; //!!
}               

int main()
{
    IPlist ip;
    if (ip.empty())
    {
      cout << "empty works" << endl;
    }

    ip.display();  // should be empty!
    ip.insertInOrder("b"); // initial
    ip.display(); // 1 element
    ip.insertInOrder("a"); // at start
    ip.display();   
    ip.insertInOrder("d"); // at end
    ip.display();

    return EXIT_SUCCESS;
}

My results

Code:

$ ./a.exe
empty works
IPaddress   Count

IPaddress   Count
b   1

IPaddress   Count
a   1
b   1

IPaddress   Count
a   1
b   1
d   1