ZuoTi.Pro
Question

Problem: Implement an interface that manipulates a list of strings. You will be provided with the...

Problem: Implement an interface that manipulates a list of strings. You will be provided with the following files (see below):

• StringList.h containing a class declaration, set up for a linked list representation.

• Driver.cpp containing a main function you can use to test your implementation.

You will be responsible for providing the StringList.cpp file, including the implementation of the StringList member functions (described below):

StringList and ~StringList: creates an empty list, and deallocates all the nodes in the list, respectively.

count: returns the total number of strings (nodes) in the list. Any duplicate strings should be counted.

push_front(string) Adds a new node containing the string to the front of the list.

push_back(string) Adds a new node containing the string to the end of the list.

pop_front() removes the first node, if the list is not empty (else does nothing).

display(): displays the strings in the list to the screen, one string per line.

remove(StringNode *m) removes the node that m points to from the linked list. This function must be private. Does nothing if m is not pointing to a node in the list.

maximum(): returns a pointer to the node containing the string that would come last in alphabetical (ascii) ordering. Does not change the list! Returns NULL if the list is empty. This function must be private.

sort(): Here is the algorithm you must use for implementing the sort function:

1. Define a StringNode * to be the head of a new list (make it the empty list). This should be a local variable (not a class member).

2. Repeat until the original list is empty:

a. Find the maximum string in the original list and remove that node from the original list. Call functions you have already defined to do this.

b. Insert this node into the proper position in the new list (at the front).

3. make the old head pointer (now empty) point to the new list!

Input/Output:

Use the provided Driver.cpp file to test your code. I recommend trying to implement one or two functions at a time, and testing them, rather than implementing all the functions and then trying to debug them all at once.

NOTES:

• This program must be done in a Linux or Unix environment, using a command line compiler like g++. Do not use codeblocks, eclipse, or Xcode to compile.

• Put your code in a file named StringList.cpp.

• Your StringList.cpp file must compile with the (unchanged) provided files.

• You may re-use code from the NumberList class (source: book/slides/website).

//StringList.h: Represents a list of strings. Supports adding and removing strings, displaying and sorting strings, removing the maximum and count of the number of strings in the list.

#include <string>
using namespace std;

class StringList
{
  private:
    struct StringNode          // the Nodes of the linked list
    {
        string data;           // data is a string
        StringNode *next;      // points to next node in list
    };
    
    StringNode *head;           // the head pointer
    void remove(StringNode *);
    StringNode * maximum();  //Note: use the following function header:
                             //StringList::StringNode * StringList:: maximum()

  public:
    StringList();
    ~StringList();
    
    int count();
    void push_front(string);
    void push_back(string);
    void pop_front();
    void display();
    void sort();
    
    //for testing, called from the Driver:
    void removeNode (int i) {
        StringNode *p = head;
        while (i>0) {p=p->next; i--;}
        remove(p);
    }
    string maxElem() {
        StringNode *p = maximum();
        return p->data;
    }
};

//Driver.cpp: a demo driver for StringList.

#include<iostream>
#include<iomanip>
using namespace std;

#include "StringList.h"

int main()
{
    //testing StringList
    StringList slist;
    
    string movie1 = "Star Wars";
    string movie2 = "Fargo";
    string movie3 = "Back to the Future";
    string movie4 = "Titanic";

    // Testing add/display/count
    cout << "Testing push_front/display/count: " << endl;
    cout << "count is: " << slist.count() << endl;

    slist.push_front(movie1);
    slist.display();
    cout << "count is: " << slist.count() << endl;
    
//    slist.push_front(movie2);
//    slist.display();
//    cout << "count is: " << slist.count() << endl;
//    
//    slist.push_back(movie3);
//    slist.push_back(movie4);
//    slist.display();
//    cout << "count is: " << slist.count() << endl;
//    
//    // Testing remove
//    cout << endl;
//    cout << "Testing remove: " << endl;
//    cout << "remove at 0" << endl;
//    slist.removeNode(0);
//    slist.display();
//    cout << "count is: " << slist.count() << endl;
//  
//    cout << "remove at 2 " << endl;
//    slist.removeNode(2);
//    slist.display();
//    cout << "count is: " << slist.count() << endl;
//
//
//    // Testing maximum
//    cout << endl;
//    cout << "Testing maximum: " << endl;
//
//    cout << "Test maximum 1: " << endl;
//    slist.display();
//    cout << "maximum: " << slist.maxElem() << endl;
//    
//    cout << "Test maximum 2: " << endl;
//    slist.push_front(movie4);
//    slist.display();
//    cout << "maximum: " << slist.maxElem() << endl;
//    
//    cout << "Test maximum 3: " << endl;
//    slist.push_front(movie2);
//    slist.display();
//    cout << "maximum: " << boolalpha << slist.maxElem() << endl;
//
//    //Testing sort and display
//    cout << endl;
//    cout << "Testing sort/display: " << endl;
//    slist.sort();
//    slist.display();
//
//    cout << endl;
//    cout << "Testing sort/display after add: " << endl;
//    slist.push_front("Jurassic Park");
//    slist.display();
//    cout << "now sorted: " << endl;
//    slist.sort();
//    slist.display();
//    
    
}
engineering   Computer-Science   
0 0
Add a comment Improve this question Transcribed image text
Next > < Previous
Sort answers by oldest

Homework Answers

Answer #1

// StringList.h

#include <string>

using namespace std;

class StringList

{

private:

    struct StringNode          // the Nodes of the linked list

    {

        string data;           // data is a string

        StringNode *next;      // points to next node in list

    };

    StringNode *head;           // the head pointer

    void remove(StringNode *);

    StringNode * maximum(); //Note: use the following function header:

                             //StringList::StringNode * StringList:: maximum()

public:

    StringList();

    ~StringList();

    int count();

    void push_front(string);

    void push_back(string);

    void pop_front();

    void display();

    void sort();

    //for testing, called from the Driver:

    void removeNode (int i) {

        StringNode *p = head;

        while (i>0) {p=p->next; i--;}

        remove(p);

    }

    string maxElem() {

        StringNode *p = maximum();

        return p->data;

    }

};

//end of StringList.h

// StringList.cpp

#include "StringList.h"

#include <iostream>

StringList::StringList()

{

               head = NULL;

}

StringList::~StringList()

{

               while(head != NULL)

               {

                              StringNode *node = head;

                              head = head->next;

                              delete(node);

               }

}

void StringList:: remove(StringNode *node)

{

               if(head != NULL)

               {

                              if(head == node)

                              {

                                             StringNode *temp = head;

                                             head = head->next;

                                             delete(temp);

                              }else{

                                             StringNode *curr = head;

                                             StringNode *prev = NULL;

                                             while(curr != NULL)

                                             {

                                                            if(curr == node)

                                                            {

                                                                           prev->next = curr->next;

                                                                           delete(curr);

                                                                           break;

                                                            }

                                                            prev = curr;

                                                            curr = curr->next;

                                             }

                              }

               }

}

StringList::StringNode * StringList:: maximum()

{

               if(head == NULL)

                              return NULL;

               StringNode *curr = head->next;

               StringNode *maxNode = head;

               while(curr != NULL)

               {

                              if(curr->data.compare(maxNode->data) > 0)

                                             maxNode = curr;

                              curr = curr->next;

               }

               return maxNode;

}

int StringList::count()

{

               int n=0;

               StringNode *curr = head;

               while(curr != NULL)

               {

                              n++;

                              curr = curr->next;

               }

               return n;

}

void StringList:: push_front(string data)

{

               StringNode *node = new StringNode;

               node->data = data;

               node->next = head;

               head = node;

}

void StringList:: push_back(string data)

{

               if(head == NULL)

                              push_front(data);

               else

               {

                              StringNode *node = new StringNode;

                              node->data = data;

                              node->next = NULL;

                              StringNode *curr = head;

                              while(curr->next != NULL)

                                             curr = curr->next;

                              curr->next = node;

               }

}

void StringList:: pop_front()

{

               if(head != NULL)

               {

                              StringNode *temp = head;

                              head = head->next;

                              delete(temp);

               }

}

void StringList:: display()

{

               if(head == NULL)

                              cout<<"List is Empty"<<endl;

               else

               {

                              cout<<"List : "<<endl;

                              StringNode *node = head;

                              while(node != NULL)

                              {

                                             cout<<node->data<<endl;

                                             node = node->next;

                              }

               }

}

void StringList:: sort()

{

               StringNode *new_head = NULL;

               while(head != NULL)

               {

                              StringNode *maxNode = maximum();

                              StringNode *newNode = new StringNode;

                              newNode->data = maxNode->data;

                              newNode->next = new_head;

                              new_head = newNode;

                              remove(maxNode);

               }

               head = new_head;

}

//end of StringList.cpp

//Driver.cpp

#include<iostream>

#include<iomanip>

using namespace std;

#include "StringList.h"

int main()

{

    //testing StringList

    StringList slist;

    string movie1 = "Star Wars";

    string movie2 = "Fargo";

    string movie3 = "Back to the Future";

    string movie4 = "Titanic";

    // Testing add/display/count

    cout << "Testing push_front/display/count: " << endl;

    cout << "count is: " << slist.count() << endl;

    slist.push_front(movie1);

    slist.display();

    cout << "count is: " << slist.count() << endl;

    slist.push_front(movie2);

    slist.display();

    cout << "count is: " << slist.count() << endl;

    slist.push_back(movie3);

    slist.push_back(movie4);

    slist.display();

    cout << "count is: " << slist.count() << endl;

    // Testing remove

    cout << endl;

    cout << "Testing remove: " << endl;

    cout << "remove at 0" << endl;

    slist.removeNode(0);

    slist.display();

    cout << "count is: " << slist.count() << endl;

    cout << "remove at 2 " << endl;

    slist.removeNode(2);

    slist.display();

    cout << "count is: " << slist.count() << endl;

    // Testing maximum

    cout << endl;

    cout << "Testing maximum: " << endl;

    cout << "Test maximum 1: " << endl;

    slist.display();

    cout << "maximum: " << slist.maxElem() << endl;

    cout << "Test maximum 2: " << endl;

    slist.push_front(movie4);

    slist.display();

    cout << "maximum: " << slist.maxElem() << endl;

    cout << "Test maximum 3: " << endl;

    slist.push_front(movie2);

    slist.display();

    cout << "maximum: " << boolalpha << slist.maxElem() << endl;

    //Testing sort and display

    cout << endl;

    cout << "Testing sort/display: " << endl;

    slist.sort();

    slist.display();

    cout << endl;

    cout << "Testing sort/display after add: " << endl;

    slist.push_front("Jurassic Park");

    slist.display();

    cout << "now sorted: " << endl;

    slist.sort();

    slist.display();

}

//end of Driver.cpp

Output:

0 0
Add a comment
Know the answer?
Add Answer to:
Problem: Implement an interface that manipulates a list of strings. You will be provided with the...
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions

  • Hi, I hope I can get some help with the following exercise in C++( CPP): 1.Write...

    Hi, I hope I can get some help with the following exercise in C++( CPP): 1.Write an additional method called push_back(int) that will add an integer to the end of the list. You can modify the provided code. 2.Modify the Node class and LinkedList class so that you can access your parent node (double linked-list). /* definition of the list node class */ class Node { friend class LinkedList; private: int value; Node *pNext; public: /* Constructors with No Arguments...

  • You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided)....

    You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance from...

  • implement a doubly-linked list in C. Each node in the linked list should contain a string,...

    implement a doubly-linked list in C. Each node in the linked list should contain a string, a pointer to the previous node (or NULL), and a pointer to the next node (or NULL). The nodes should be sorted by their strings. struct node_t { char* str; struct node_t* prev; struct node_t* next; } To maintain the doubly-linked list, you should keep a pointer to the head node of the list (or NULL if the list is empty), and a pointer...

  • C++, Change the destroy_list function in the header file to a recursive destroy_list function, main is...

    C++, Change the destroy_list function in the header file to a recursive destroy_list function, main is already set. Hint: It might be helpful to modify the function so that it uses a separate recursive function to perform whatever processing is needed. //////////////////////////////////////////////////////////////header.h////////////////////////////////////////////////////////////////////////////////////////////// #ifndef HEADER_H_ #define HEADER_H_ #include using namespace std; template <class T> class LL { private:    struct LLnode    {        LLnode* fwdPtr;        T theData;    };    LLnode* head; public:    LL();    void...

  • (C++) You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class...

    (C++) You are tasked with implementing a recursive function void distanceFrom(int key) on the IntList class (provided). The function will first search through the list for the provided key, and then, recursively, change all previous values in the list to instead be their distance from the node containing the key value. Do not update the node containing the key value or any nodes after it. If the key does not exist in the list, each node should contain its distance...

  • Objectives Familiarize the student with: implementing data structures in C++; dynamic allocation of C++ objects. Scenario...

    Objectives Familiarize the student with: implementing data structures in C++; dynamic allocation of C++ objects. Scenario There are some classic data structures in computer science. One example of this that you've seen in the lectures is called the stack. In the next few exercises, we'll build yet another classic data structure, the linked list. To be exact, we'll be building the singly linked list. The building block of a singly linked list is a node, which consists of two parts:...

  • Q) Modify the class Linked List below to make it a Doubly Linked List. Name your...

    Q) Modify the class Linked List below to make it a Doubly Linked List. Name your class DoublyLinkedList. Add a method addEnd to add an integer at the end of the list and a method displayInReverse to print the list backwards. void addEnd(int x): create this method to add x to the end of the list. void displayInReverse(): create this method to display the list elements from the last item to the first one. Create a main() function to test...

  • Need this in C++ Goals: Your task is to implement a binary search tree of linked...

    Need this in C++ Goals: Your task is to implement a binary search tree of linked lists of movies. Tree nodes will contain a letter of the alphabet and a linked list. The linked list will be an alphabetically sorted list of movies which start with that letter. MovieTree() ➔ Constructor: Initialize any member variables of the class to default ~MovieTree() ➔ Destructor: Free all memory that was allocated void printMovieInventory() ➔ Print every movie in the data structure in...

  • C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of...

    C++ Assignment Project 1 - NodeList Building upon the the ListNode/List code I would like you to extend the interface of a list to have these member functions as well. struct ListNode { int element; ListNode *next; } Write a function to concatenate two linked lists. Given lists l1 = (2, 3, 1)and l2 = (4, 5), after return from l1.concatenate(l2)the list l1should be changed to be l1 = (2, 3, 1, 4, 5). Your function should not change l2and...

  • I need help and have to get this done asap: Using the following source codes provided below, create recursive functions...

    I need help and have to get this done asap: Using the following source codes provided below, create recursive functions and methods in C++ to complete the following exercises: Print the list in forward order Print the list in reverse order Print the following three lines (in this order): "The first node contains <value in first node>" "The last node contains <value in last node>" "The first node contains <value in first node>" Print the sum of all the values...

ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT