Problem: Implement an interface that manipulates a list of strings. You will be
ID: 3707163 • Letter: P
Question
Problem: Implement an interface that manipulates a list of strings. You will be provided with the following files on the Tracs:
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.
add(string) Adds a new node containing the string to either the beginning OR the end of the list (your choice, pick one, use the same one every time).
remove(string) removes a node containing the given string from the linked list. Returns true if successful, otherwise false (if the string was not in the list).
display(): displays the strings in the list to the screen, one string per line.
minimum(): returns the string that would come first in alphabetical (ascii) ordering. Does not change the list!
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 minimum 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 end).
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, otherwise you may receive a score of 0.
You may re-use code from the NumberList class (source: book/slides/website). Logistics:
For this assignment you need to submit only the StringList.cpp file. You do not need a zip file, you do not need a makefile, you do not need to provide your driver.
There are two steps to the turn-in process:
Submit an electronic copy using the Assignments tool on the TRACS website for this class.
Submit a printout of the source file at the beginning of class, the next class day after the assignment is due. Please print your name on top of the front page, and staple if there is more than one page.
Note: Each member of a group must submit their own electronic copy and their own printout!! Make sure your name is written or circled on your printout.
See the assignment turn-in policy on the syllabus posted on Tracs for more details.
Here are the given files:
Explanation / Answer
Edited: Full Working Code (Fixed Sorting Bug)
=====================================================================
StringList.cpp
======================================================================
/*
* C++ Program to Implement Singly Linked List
*/
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include "StringList.h"
using namespace std;
/*
* Inserting StringNode at last
*/
void StringList::add(string str)
{
struct StringNode *temp, *s;
// creation of new node
temp = new(struct StringNode);
temp->data = str;
temp->next = NULL;
s = head;
// If list is empty, make the new StringNode as head.
if (head == NULL)
head = temp;
else { // traverse till end and insert the new StringNode.
while (s->next != NULL)
{
s = s->next;
}
//temp->next = NULL;
s->next = temp;
}
cout << "String Inserted at last" << endl;
}
/*
* Delete element at a given position
*/
bool StringList::remove(string str)
{
if (head == NULL)
{
cout << "List is empty" << endl;
return false;
}
struct StringNode *s,*ptr=NULL;
s = head;
if (head->data.compare(str) == 0) {// If matches with the head node
head = head->next;
free(s);
return true;
}
else {
while (s != NULL) // traverse the list till we reach end or till we get a match
{
if (s->data.compare(str) == 0 ) // match found
{
ptr->next = s->next;
free(s);
return true; // return position
}
ptr = s;
s = s->next;
}
}
return false; // No match found.
}
/*
* Searching an element
*/
string StringList::minimum()
{
string minstr="";
if (head == NULL)
{
cout << "List is empty" << endl;
return minstr; // returns empty string
}
struct StringNode *s;
s = head;
minstr = s->data; // We take first string as minimum string
s = s->next;
while (s != NULL) // traverse the list till we reach end or till we get a match
{
//pos++;
if (s->data.compare(minstr) < 0) // s->data string is minimum
{
minstr = s->data; // storing it to the min string.
//return pos; // return position
}
s = s->next;
}
return minstr; // No match found.
}
int StringList::count()
{
int count = 0;
if (head == NULL)
{
cout << "List is empty" << endl;
return count; // returns empty string
}
struct StringNode *s;
s = head;
while (s != NULL) // traverse the list till we reach end or till we get a match
{
count++;
s = s->next;
}
return count; // No match found.
}
/*
* Display Elements of a link list
*/
void StringList::display()
{
struct StringNode *temp;
if (head == NULL)
{
cout << "The List is Empty" << endl;
return;
}
temp = head;
cout << "The strings in the list are: " << endl;
while (temp != NULL) // Till the last element of list
{
cout << temp->data << endl;
temp = temp->next;
}
//cout << "NULL" << endl;
}
//Constructor
StringList::StringList() {
head = NULL; // Creating empty list
}
//Destructor
StringList::~StringList() {
// free all the memory space of nodes
StringNode *ptr = head; //ptr for iterator
while (head != NULL) { //iterate unitl list is empty
ptr = head->next;
free(head); // free the current node
head = ptr;
}
}
//StringList sortlist;
void StringList::sort() {
//cout << "Need to do sorting";
StringList sortlist; //making an sorted empty list
sortlist.head = NULL;
string minstr;
while (head != NULL) { //till the end of the list
minstr = minimum(); //find the minimum string from the list
sortlist.add(minstr); // add string to new sort list.
remove(minstr); // remove the min string from the list.
}
head = sortlist.head; // pointing the old head to new sortedlist .
// Make the secondlist head point to null. Otherwise it will try to free the sorted list in destructor, which is pointed by the slist
sortlist.head = NULL;
}
StringList.h
// File Name : StringList.h
//
//
// Represents a list of strings.
// Supports adding and removing strings, displaying and sorting strings,
// finding the minimum 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
public:
StringList();
~StringList();
int count();
void add(string);
bool remove(string);
void display();
string minimum();
void sort();
};
ListDriver.cpp (main function given in Question)
// File Name : ListDriver.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 add/display/count: " << endl;
cout << "count is: " << slist.count() << endl;
slist.add(movie1);
slist.display();
cout << "count is: " << slist.count() << endl;
slist.add(movie2);
slist.display();
cout << "count is: " << slist.count() << endl;
slist.add(movie3);
slist.add(movie4);
slist.display();
cout << "count is: " << slist.count() << endl;
// Testing remove
cout << endl;
cout << "Testing remove: " << endl;
bool delResult;
delResult = slist.remove(movie4);
cout << "remove result movie4 = " << boolalpha << delResult << endl;
delResult = slist.remove(movie3);
cout << "remove result movie3 = " << boolalpha << delResult << endl;
delResult = slist.remove("Not There");
cout << "remove result Not There = " << boolalpha << delResult << endl;
cout << "display after remove: " << endl;
slist.display();
cout << "count is: " << slist.count() << endl;
// Testing minimum
cout << endl;
cout << "Testing minimum: " << endl;
cout << "Test minimum 1: " << endl;
slist.display();
cout << "minimum: " << boolalpha << slist.minimum() << endl;
cout << "Test minimum 2: " << endl;
slist.add(movie4);
slist.display();
cout << "minimum: " << boolalpha << slist.minimum() << endl;
cout << "Test minimum 3: " << endl;
slist.add(movie3);
slist.display();
cout << "minimum: " << boolalpha << slist.minimum() << 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.add("Jurassic Park");
slist.display();
cout << "now sorted: " << endl;
slist.sort();
slist.display();
*/
//system("pause");
}
Sample Output Generated:
Testing add/display/count:
List is empty
count is: 0
String Inserted at last
The strings in the list are:
Star Wars
count is: 1
String Inserted at last
The strings in the list are:
Star Wars
Fargo
count is: 2
String Inserted at last
String Inserted at last
The strings in the list are:
Star Wars
Fargo
Back to the Future
Titanic
count is: 4
Testing remove:
remove result movie4 = true
remove result movie3 = true
remove result Not There = false
display after remove:
The strings in the list are:
Star Wars
Fargo
count is: 2
Testing minimum:
Test minimum 1:
The strings in the list are:
Star Wars
Fargo
minimum: Fargo
Test minimum 2:
String Inserted at last
The strings in the list are:
Star Wars
Fargo
Titanic
minimum: Fargo
Test minimum 3:
String Inserted at last
The strings in the list are:
Star Wars
Fargo
Titanic
Back to the Future
minimum: Back to the Future
Testing sort/display:
String Inserted at last
String Inserted at last
String Inserted at last
String Inserted at last
The strings in the list are:
Back to the Future
Fargo
Star Wars
Titanic
Press any key to continue . . .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.