Need to complete insert function
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Need to complete insert function

  1. #1
    Join Date
    Mar 2017
    Posts
    7

    Need to complete insert function

    Need to create the insert function all other code is complete and cant be changed, struggling to get this to work at all, have tried creating a node however got no further, any help would be great, the more detailed the better

    This is the part i need to complete
    Code:
    // Insert the given string into the linked-list such that the
    // entries in the linked-list are in alphabetical order
    bool List::insert(const char *string_p)
    {
      // Please write the list insert function
      return SUCCESS;
    }
    FULL CODE
    Code:
      
    #include <iostream>
    #include <string>
    
    using std::string;
    using std::cout;
    using std::endl;
    
    #define SUCCESS 0
    #define FAIL    1
    
    // Represents an entry object in the linked-list
    class ListEntry
    {
      public:
        explicit     ListEntry();
        explicit     ListEntry(const char *string_p);
                     ~ListEntry();
        string       getData();
        void         setData(const char* string_p);
        void         setData(string string);
        ListEntry   *getNext();
        ListEntry   *getPrevious();
        ListEntry   *prev_p;   // pointer to previous entry in the linked-list
        ListEntry   *next_p;   // pointer to next entry in the linked-list
    
      private:
        string          data;      // entry's string
    };
    
    // Represents the linked-list object
    class List
    {
      public:
        List();
        ~List();
    
        bool printForward();
        bool printReverse();
        bool insert(const char *string_p);
    
      private:
        int        entryCount;  // number of entries present in the linked-list
        ListEntry *head_p;      // pointer to the first entry in the list
        ListEntry *tail_p;      // pointer to the last entry in the list
    };
    
    // ListEntry constructor
    ListEntry::ListEntry()
    {
      this->prev_p = NULL;
      this->next_p = NULL;
      return;
    }
    
    // ListEntry constructor
    ListEntry::ListEntry(const char *string_p)
    {
      this->data   = string_p;
      this->prev_p = NULL;
      this->next_p = NULL;
      return;
    }
    
    // List entry destructor 
    ListEntry::~ListEntry()
    {
      return;
    }
    
    // Return the stored string object
    string ListEntry::getData()
    {
      return this->data;
    }
    
    // Set the internal string data from a char*
    void ListEntry::setData(const char* string_p)
    {
      this->data = string_p;
    }
    
    // Set the internal string data from a string
    void ListEntry::setData(string string)
    {
      this->data = string;
    }
     
    // Returns reference to the next entry in the list
    ListEntry *ListEntry::getNext()
    {
      return this->next_p;
    }
    
    // Returns reference to the previous entry in the list
    ListEntry *ListEntry::getPrevious()
    {
      return this->prev_p;
    }
    
    // List constructor
    List::List()
    {
      this->entryCount = 0;
      this->head_p     = NULL;
      this->tail_p     = NULL;
    }
    
    // List destructor
    List::~List()
    {
      // Delete all entries in the list
      ListEntry *entry_p   = this->head_p;
      ListEntry *current_p = this->head_p;
    
      while (entry_p != NULL)
      {
        current_p = entry_p; 
        entry_p = entry_p->getNext();
        delete current_p;
      }
     }
    
    // Output linked list in order from head to tail
    // printing out the string data from each list entry
    bool List::printForward()
    {
      ListEntry *entry_p = this->head_p;
      int count = 0;
    
      cout << "FORWARD: " << this->entryCount << " entries\n";
      while (entry_p != NULL)
      {
        cout << entry_p->getData() << " ";
    
        if (++count % 5 == 0 || entry_p == this->tail_p)
        {
          cout << endl;
        }
    
        entry_p = entry_p->getNext();
      }
    
      return SUCCESS;
    }
    
    // Output linked list in reverse order from tail to head
    // printing out the string data from each list entry
    bool List::printReverse()
    {
      ListEntry *entry_p = this->tail_p;
      int count = 0;
    
      cout << "REVERSE: " << this->entryCount << " entries\n";
      while (entry_p != NULL)
      {
        cout << entry_p->getData() << " ";
    
        if (++count % 5 == 0 || entry_p == this->head_p)
        {
          cout << endl;
        }
    
        entry_p = entry_p->getPrevious();
      }
    
      return SUCCESS;
    }
    
    // Insert the given string into the linked-list such that the
    // entries in the linked-list are in alphabetical order
    bool List::insert(const char *string_p)
    {
      // Please write the list insert function
      return SUCCESS;
    }
    
    int main(int argc, char **argv)
    {
      (void) argc;
      (void) argv;
    
      const char *places[] = { "Aberdeen", "Bakewell", "Cocking", "Dogdyke",
                               "Eastbourne", "Farranfadda", "Gaggin", "Hadfield",
                               "Irnham", "Jameston", "Kendal", "Langley",
                               "Malmesbury", "Netherhampton", "Ogmore", "Pant",
                               "Quedgeley", "Ramsbottom", "Sallynoggin",
                               "Talla Bheith Forest", "Upchurch", "Victoria Bridge",
                               "Wacton", "Xeroxillington", "Yelling", "Zetland" };
      
      unsigned char indexes[] = { 1, 14, 17, 3, 22, 0, 5, 18, 24, 11, 4, 6, 13, 21,
                                  2, 12, 25, 19, 10, 16, 7, 9, 23, 15, 20, 8 };
    
    
      List placesList;
    
      // Insert every word in the places array into the
      // linked-list.
      cout << "INSERT:\n";
      for (unsigned int count = 0; count < sizeof(indexes); count++)
      {
        cout << places[indexes[count]] << " ";
    
        //Add a new line for console readability
        if( count > 0 && count % 5 == 0)
        {
          cout << endl;
        }
    
        placesList.insert(places[indexes[count]]);
      }
      cout << endl;
    
      // print out the list in alphabetical order
      placesList.printForward();
      cout << endl;
    
      // print out the list in reverse alphabetical order
      placesList.printReverse();
      cout << endl;
    
      return SUCCESS;
    }

  2. #2
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,925

    Re: Need to complete insert function

    Do you know how the linked-list is designed and how it works?
    Do you know how to iterate through the list?
    Do you know how to compare the strings?
    Victor Nijegorodov

  3. #3
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,582

    Re: Need to complete insert function

    The list is doubly linked with next and previous pointers. So to insert an item into the list so that it maintains a required ascending sorted order, you simply traverse the list from the head until the value of the node at entry->next is greater than the value to be inserted. When this is true then you insert the new element after the current node - adjusting all pointers as needed and the list count. There are a couple of edge conditions to consider - the list is empty, the value of the first element in the list is greater than the insert value and entry->next is NULL.

    Note that current good practice is to use nullptr rather than NULL to signify that a node pointer doesn't point to another valid node.
    Last edited by 2kaud; March 31st, 2017 at 12:50 PM.
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  4. #4
    Join Date
    Mar 2017
    Posts
    7

    Re: Need to complete insert function

    Quote Originally Posted by VictorN View Post
    Do you know how the linked-list is designed and how it works?
    Do you know how to iterate through the list?
    Do you know how to compare the strings?
    I understand how the linked list is designed and works, however I do not understand how to iterate through the list or compare the strings, sorry im very basic in c++ coding.

  5. #5
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,925

    Re: Need to complete insert function

    Quote Originally Posted by bobby118 View Post
    I understand how the linked list is designed and works, however I do not understand how to iterate through the list or compare the strings, sorry im very basic in c++ coding.
    Well, now 2kaud explained you both these "problems". So try to implement it in code!
    Victor Nijegorodov

  6. #6
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,582

    Re: Need to complete insert function

    I do not understand how to iterate through the list
    Look at how printForward() is coded. That iterates through the linked list starting at the head.

    or compare the strings
    As the data is of type string, comparison is very easy. If entry_p is a pointer to a list node and you want to test for equality to say variable s1 which is of type string then
    Code:
    string s1 = "test";
    ...
    if (entry_p->getData() == s1) {
      //statements for equality true here
    }
    all other code is complete and cant be changed
    Is this code that you're written or has this been provided?
    Last edited by 2kaud; March 31st, 2017 at 12:57 PM. Reason: Spelling
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  7. #7
    Join Date
    Mar 2017
    Posts
    7

    Re: Need to complete insert function

    This has been provided so it needs to maintain that form, I see the code to iterate through the list is
    Code:
     	                ListEntry *entry_p = this->head_p;
    			cout << "ALPHA: " << this->entryCount << " entries\n";
    				while (entry_p != NULL)
    				{
    					cout << entry_p->getData() << " ";
    		
    					if (++count % 5 == 0 || entry_p == this->tail_p)
    					{
    						cout << endl;
    					}
    		
    					entry_p = entry_p->getNext();
    				}

  8. #8
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,925

    Re: Need to complete insert function

    Quote Originally Posted by bobby118 View Post
    This has been provided so it needs to maintain that form, I see the code to iterate through the list is
    Code:
     	                ListEntry *entry_p = this->head_p;
    			cout << "ALPHA: " << this->entryCount << " entries\n";
    				while (entry_p != NULL)
    				{
    					cout << entry_p->getData() << " ";
    		
    					if (++count % 5 == 0 || entry_p == this->tail_p)
    					{
    						cout << endl;
    					}
    		
    					entry_p = entry_p->getNext();
    				}
    What could/should mean this line? The left part of it?
    Victor Nijegorodov

  9. #9
    Join Date
    Mar 2017
    Posts
    7

    Re: Need to complete insert function

    I understand that there is a std::sort() function that could sort through the words, however for the if statement it would need to compare the entrys and put it to the front or back of the list if its alphabetical.

  10. #10
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,582

    Re: Need to complete insert function

    This has been provided
    Well it's not the best way of coding this in modern c++. It could do with updating to use current c++ good practice....

    I see the code to iterate through the list
    Good. Now do you understand it? So now you can attempt to code insert().
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  11. #11
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,582

    Re: Need to complete insert function

    Quote Originally Posted by bobby118 View Post
    I understand that there is a std::sort() function that could sort through the words, however for the if statement it would need to compare the entrys and put it to the front or back of the list if its alphabetical.
    To insert the words alphabetically into the list, you don't need the sort() function. I explained how to insert to ascending order in post #3. What don't you understand about that?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  12. #12
    Join Date
    Mar 2017
    Posts
    7

    Re: Need to complete insert function

    I understand what it supposed to do, and that it needs to compare the values, however im not sure how to code this in C++, even this is very basic i dont know how to code this

  13. #13
    2kaud's Avatar
    2kaud is offline Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    5,582

    Re: Need to complete insert function

    What have you covered in your lessons? What book are you using? Has your teacher not covered list insertion in class?
    All advice is offered in good faith only. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/

    C, C++ Compiler: Microsoft VS2017.2

  14. #14
    VictorN's Avatar
    VictorN is offline Super Moderator Power Poster
    Join Date
    Jan 2003
    Location
    Wallisellen (ZH), Switzerland
    Posts
    18,925

    Re: Need to complete insert function

    Quote Originally Posted by bobby118 View Post
    I understand what it supposed to do, and that it needs to compare the values, however im not sure how to code this in C++, even this is very basic i dont know how to code this
    Now you should learn how and where to get any useful info about what you seem to need...
    The first step - use google search like https://www.google.ch/webhp?sourceid...mpare+string&*
    The next step - try to find the more useful info applying to your concrete problem (in your case there would be the first three links)
    And finally - find the proper documentation together with the appropriate sample code!
    Victor Nijegorodov

  15. #15
    Join Date
    Mar 2017
    Posts
    7

    Re: Need to complete insert function

    Our teacher has not covered this at all, we have only been taught very basic c++

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This a Codeguru.com survey!


On-Demand Webinars (sponsored)