Sorted Order Help

[Schmitty27]

Hello thar,

I'm working on a problem that needs to input data into a list in sorted order. So far I'm getting some output, but it ignores some of my inserts, (ie "Hammy" in this case) and the output is not sorted.

I've looked at this for a while but I can't seem to find what I'm doing wrong, part of me believes its in one of my if statements, I'll denote it in the code.

Any help would be appriciated!

#include <iostream>
#include <string>

using namespace std;

struct Node
{
    string value;
    struct Node * next;
};

class List
{
public:
    List()
    {
        cout << "Creating a new list..." << endl;
        top = new Node;
        top->value = "INVALID";
        top->next = NULL;
        end = NULL;
        count = 0;
    }
    int getCount()
    {
        return count;
    }

        void deleteIt(string data)
    {
        Node *x = top;
        Node *prev = NULL;

        while (x != NULL){
            if (x->value != data){
                prev = x;
                x = x->next;
            }

            else if (x->value == data){

                prev->next = x->next;
                delete x;
                count --;
                return;

    }
        }
    }

    
        void SortInsert(string data)
    {
        
        
        Node *tmp = new Node;
        Node *prev = NULL;
        Node *x = top->next;

        tmp->next = NULL; 
        x = top;

if (x == NULL) 
{
  top = tmp;
}
else
{
  while (x != NULL) 
  {
    if (x->next == NULL) 
    {
      x->next = tmp;
      
      break;
    }
    else if (data < x->value)  // THIS STATEMENT
    {
      
      tmp->value = data;
      tmp->next = x->next;
      x->next = tmp;
      count ++;
      break;
    }
    x = x->next;
  }
}
        } 

       

    

    void print()
    {
        Node *x = top;
        bool header = true;
        cout << "Here is the list: " << endl;
        while (x != NULL)
        {
            if (!header)
                cout << x->value << endl;
            else
                header = false;
            x = x->next;
        }
        cout << "End of list" << endl;
    }
    bool has(string what)
    {
        Node *x = top;
        bool header = true;
        while (x != NULL)
        {
            if (!header)
            {
                if (x->value == what)
                    return true;
            }
            else
                header = false;
            x = x->next;
        }
        return false;
    }    

private:
    Node *top;
    Node *end;
    int count;
};

int main()
{
    List myList;
    /*myList.insert("Adam");
    myList.insert("Betty");
    myList.insert("Betty");
    myList.insert("Charlie");
    myList.deleteIt("Charlie");*/
    myList.SortInsert("Hammy");
    myList.SortInsert("Brian");
    myList.SortInsert("Albert");
    myList.SortInsert("Freefall");    

    cout << "There are " << myList.getCount() <<
        " item(s) in the list" << endl;
    myList.print();
    if (myList.has("Adam"))
        cout << "The list does contain Adam" << endl;
    if (myList.has("Betty"))
        cout << "The list does contain Betty" << endl;
    if (myList.has("Charlie"))
        cout << "The list does contain Charlie" << endl;
    if (myList.has("Steve"))
        cout << "The list does contain Steve" << endl;


}

[JRM]

I am learning C++ myself.
looking at this initially, you are using "struct" which has been depreciated in C++ syntax.

Secondly, your sort method (I could be wrong about this!) seems that it could give erronous output since ( I believe) it works on comparing ascii value of the names. I'm sure ther are names that could add up to the same value , but be completly different. You give no value to the ORDER of the indiviual ascii values.

Thats my take on the code . Hopefully someone with more experience can chime in.

[Schmitty27]

Thanks for the advice. We're kinda restriced due to our professor's guidelines we kinda have to make it work with what he gave us.

I'll keep trying to get this to work.

[vijayan121]

a. you do not need a sentinal node (with the value "INVALID") at the beginning of the list
b. if the value you are trying to insert compares less than the value in a node, you need to insert *before* not after the node
c. in more than one place, you are forgetting to initialize/modify values

// ...
// ...
class List
{
  public:
      List()
      {
          cout << "Creating a new list..." << endl;
          /* *** removed, no need for sentinal node
              top = new Node;
              top->value = "INVALID";
              top->next = NULL;
          */
          top = NULL ; // *** added
          end = NULL;
          count = 0;
      }
      // ...
     // ...
      void SortInsert(string data)
      {
          Node *tmp = new Node;
          Node *prev = NULL;
          // Node *x = top->next; // ***  removed, no sentinal node

          tmp->value = data ;  // *** added
          tmp->next = NULL;
          Node* x = top; // *** modified

          if (x == NULL)
          {
            top = end = tmp; // *** modified
            ++count ; // *** added
          }
          else
          {
            while (x != NULL)
            {
              if (data < x->value)  // THIS STATEMENT
              {
                // *** modified as data<x->value, add *before* not after x
                //tmp->value = data;  // *** removed
                tmp->next = x ; // *** modified
                if( prev != NULL ) prev->next = tmp; // *** modified
                else top = tmp ; // *** modified
                count ++;
                break;
              }
              else if (x->next == NULL)
              {
                x->next = tmp;
                end = tmp ; // *** added
                ++count ;  // *** added
                break;
              }
              else
              {
                prev = x ; // *** added
                x = x->next;
              }
            }
          }
        }

      void print()
      {
          Node *x = top;
          //bool header = true; // *** removed, no sentinal node
          cout << "Here is the list: " << endl;
          while (x != NULL)
          {
              //if (!header) // *** removed
              cout << x->value << endl;
              //else // *** removed
                  //header = false; // *** removed
              x = x->next;
          }
          cout << "End of list" << endl;
      }
   // ...
  // ...
  private:
      Node *top;
      Node *end;
      int count;
};