CS 3305: Data Structures Fall 2021Assignment 3 – Linked-Lists 100 points Note 1: If you re-upload...

Question

CS 3305: Data Structures Fall 2021Assignment 3 – Linked-Lists 100 points    Note 1: If you re-upload the files, you must re-upload ALL files as the system keeps the most recent uploaded submission only. No zip files!  Note 2: Never hard-code test data in the test program, unless explicitly stated in the assignment. Always allow the user to enter the test data using menu option.   The goal of this assignment is to reinforce the concept of linked lists in C++. In particular, the assignment is to implement additional linked list functions in class node1.h provided by the textbook authors.  Read the slides and chapter 5 from the textbook and understand the discussion of linked lists and the implementation of the linked list toolkit container class (section 5.2).  Part 1 (20 points):   1. Download and compile files node1.h and node1.cpp. provided in the authors’ website: https:home.cs.colorado.edu/~main/chapter5/.  2. Write an interactive test program (Save it in file node1_Test.cpp) to test class node1. The test program creates a linked list of doubles (say grades) and allows the user to call any of the linked list functions implement in class node1 on the grades list. You may pre-populate the list with few values to start with or assume the grades list is initially empty. Either way, let the user know your intention in a message before you display the menu. Notice option 12 is simply to be able to see list after a change is made to it.  To make the test program more friendly, use the following menu:     XXXXXXXXXXMAIN MENU ------------------ 1. Test function std::size_list_length 2. Test function void list_head_insert 3. Test function void list_insert 4. Test function node *list_search 5. Test function const node *list_search 6. Test function node *list_locate 7. Test function const node *list_locate 8. Test function void list_head_remove 9. Test function void list_remove 10. Test function void list_clear 11. Test function void list_copy 12. Display List 13. Exit program XXXXXXXXXXEnter option number:   Part 2 (80 points):  1. Now, expand class node1 to include three more linked list functions defined as follows. (To keep the second part clean, create 2 new files named node1_New.h and node1_New.cpp)https:home.cs.colorado.edu/~main/chapter5a. Function delete_reps() that deletes all repeated values from the linked list. The function eturns a new linked list without repeated values. The original linked list is preserved as is. Thus, this function involves copying nodes to the new linked list.  . Function sort_list() that takes a linked list and sorts it in ascending order (smallest to largest) using selection sort algorithm (see below). The list may include repeated values. The function prototype would be void sort_list((node*& head_ptr);   Selection sort for this exercise works as follows:   Loop through the entire original list (while list has more nodes)   Begin 1. Find the node with the largest value in the original list. 2. Remove the node from the original list. 3. Insert the node at the head of the target list.   End;  Notice the following: after all nodes are moved to the target list, pointer head_ptr needs to point to the head node of the target list; when the loop is done, the original list should be empty due to the removal of node to the target list; and the function does not need to allocate any memory space (i.e., using the new operator).  c. Function split_list() that take a specific value in the list (say split_value) and splits the list into 2 linked lists. First linked list contains all values before the split_value; and the second list contains all the values from the first instance of the split_value and beyond. For example,  If XXXXXXXXXXList1 = {1.1, 8.0, 4.2, 7.5, 3.0, 6.5, 2.7, 3.0, 6.8, 9.9}  XXXXXXXXXXand the split value is 3.0,  Then   the result would be as follows:       List1 = {1.1, 8.0, 4.2, 7.5}       List2 = {3.0, 6.5, 2.7, 3.0, 6.8, 9.9}  For uniformity, let’s assume that the first list is called List1 and the second list is called List2. Note that if the split value is repeated in the linked list, we split the list at the first instance of the split value. Let’s also assume that we persevere the original list as is. That is, List1 is the original list name.  2. Copy your test file from part 1 and name it node1_New_Test.cpp. Modify the new test program menu to include the newly added functions (as options 13, 14, and 15, see below). The new test program still creates a linked list of doubles (say grades). Allow the user to call any of the linked list functions implement in class node1_New on the grades list. Test your code with different list of different lengths and make sure you test the code with both invalid (bad) and valid (good) data. Always test code with an empty linked list first.  13. Test function delet_reps 14. Test function sort_list 15. Test function split_list 16. Exit ProgramAlways re-display the menu after an option (other than the Exit option) is fully exercised with blank lines before and after the menu.  Do not forget to include author header in each submitted file as shown, no header, no points!   Name:        Class:     CS 3305/Section#  Term:      Fall 2021  Instructor:    Dr. Haddad  Assignment:    3Submission: Please submit all 6 files (node1.h,  node1.cpp, node1_Test.cpp, node1_New.h, node1_New_Test.cpp, and node1_New.cpp) to the assignment submission folder in D2L by the due date posted in D2L.  No zip file submission. No late submissions are accepted. Once again, please include author header block in each file - no headers, no points.  Important Note: The code must be coectly running and gives coect results in the required environment (CodeLite and GNU C++ compiler) before being uploaded.

Aditya · Accepted Answer

linkedlist
node1.cpp
node1.cpp
// Name: Aditya Thati 
// Class: CS 3305/Section# 
// Term: Fall 2021
// Instructor: Dr. Haddad 
// Assignment: 3
// FILE: node1.cxx
// IMPLEMENTS: The functions of the node class and the
// linked list toolkit (see node1.h for documentation).
// INVARIANT for the node class:
//   The data of a node is stored in data_field, and the link in link_field.
#include "node1.h"
#include     // Provides assert
#include     // Provides NULL and size_t
#include 
using namespace std;
namespace main_savitch_5
{
    size_t list_length(const node* head_ptr)
    // Library facilities used: cstdlib
    {
    const node *cursor;
    size_t answer;
    answer = 0;
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
        ++answer;
    
    return answer;
    }
    
    void list_head_insert(node*& head_ptr, const node::value_type& entry)
    {
    head_ptr = new node(entry, head_ptr);
    }
    void list_insert(node* previous_ptr, const node::value_type& entry) 
    {
    node *insert_ptr;
    
    insert_ptr = new node(entry, previous_ptr->link( ));
    previous_ptr->set_link(insert_ptr);
    }
    node* list_search(node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
    node *cursor;
   
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
        if (target == cursor->data( ))
        return cursor;
    return NULL;
    }
    const node* list_search(const node* head_ptr, const node::value_type& target) 
    // Library facilities used: cstdlib
    {
    const node *cursor;
   
    for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
        if (target == cursor->data( ))
        return cursor;
    return NULL;
    }
    node* list_locate(node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
    node *cursor;
    size_t i;
    
    assert (0 link( );
    return cursor;
    }
    const node* list_locate(const node* head_ptr, size_t position) 
    // Library facilities used: cassert, cstdlib
    {
    const node *cursor;
    size_t i;
    
    assert (0 link( );
    return cursor;
    }
    void list_head_remove(node*& head_ptr)
    {
    node *remove_ptr;
    remove_ptr = head_ptr;
    head_ptr = head_ptr->link( );
    delete remove_ptr;
    }
    void list_remove(node* previous_ptr)
    {
    node *remove_ptr;
    remove_ptr = previous_ptr->link( );
    previous_ptr->set_link( remove_ptr->link( ) );
    delete remove_ptr;
    }
    void list_clear(node*& head_ptr)
    // Library facilities used: cstdlib
    {
    while (head_ptr != NULL)
        list_head_remove(head_ptr);
    }
    void list_copy(const node* source_ptr, node*& head_ptr, node*& tail_ptr) 
    // Library facilities used: cstdlib
    {
    head_ptr = NULL;
    tail_ptr = NULL;
    // Handle the case of the empty list.
    if (source_ptr == NULL)
        return;
    
    // Make the head node for the newly created list, and put data in it.
    list_head_insert(head_ptr, source_ptr->data( ));
    tail_ptr = head_ptr;
    
    // Copy the rest of the nodes one at a time, adding at the tail of new list.
    source_ptr = source_ptr->link( ); 
    while (source_ptr != NULL)
    {
        list_insert(tail_ptr, source_ptr->data( ));
        tail_ptr = tail_ptr->link( );
        source_ptr = source_ptr->link( );
    }
    }
    void display(node*& head_ptr) 
    {
        const node *cursor;
   
        for (cursor = head_ptr; cursor != NULL; cursor = cursor->link( ))
            coutdata()>";

CS 3305: Data Structures Fall 2021 Assignment 3 – Linked-Lists 100 points Note 1: If you re-upload the files, you must re-upload ALL files as the system keeps the most recent uploaded submission only....

Solution

Answer To This Question Is Available To Download

Related Questions & Answers

Submit New Assignment