Question

In: Computer Science

Here is a C++ class definition for an abstract data type LinkedList of string objects. Implement...

Here is a C++ class definition for an abstract data type LinkedList of string objects. Implement each member function in the class below. Some of the functions we may have already done in the lecture, that's fine, try to do those first without looking at your notes. You may add whatever private data members or private member functions you want to this class.

#include

#include

typedef std::string ItemType;

struct Node {

ItemType value;

Node *next;

};

class LinkedList {

private:

Node *head;

public:

//default constructor

LinkedList() : head(nullptr) { }

//copy constructor

LinkedList (const LinkedList& rhs);

//Destroys all the dynamically allocated memory in the list.

~LinkedList ();

// assignment operator

const LinkedList& operator= (const LinkedList& rhs);

// Inserts val at the rear of the list

void insertToRear (const ItemType &val);

// Prints the LinkedList

void printList () const;

// Sets item to the value at position i in this LinkedList and return true, returns false if there is no element I

bool get (int i, ItemType& item) const;

// Reverses the LinkedList

void reverseList ();

//Prints the LinkedList in reverse order

void PrintReverse() const;

//Appends the values of other onto the end of this LinkedList.

void append (const LinkedList &other);

//Exchange the contents of this LinkedList with the other one.

void swap (LinkedList &other);

//Returns the number of items in the Linked List.

int size() const;

};

When we don't want a function to change a parameter representing a value of the type stored in the LinkedList, we pass that parameter by constant reference. Passing it by value would have been perfectly fine for this problem, but we chose the const reference alternative because that will be more suitable after we make some generalizations in a later problem.

The get function enables a client to iterate over all elements of a LinkedList. In other words, this code fragment

LinkedList 1s;

1s.insertToRear("Carl");

1s.insertToRear("Hariette");

1s.insertToRear("Eddie");

1s.insertToRear("Laura");

1s.insertToRear("Judy");

1s.insertToRear("Steve");

for (int k = 0; k < 1s.size (); k++)

{

string x;

1s.get(k, x);

court << x << endl;

}

must write

Carl

Hariette

Eddie

Laura

Judy

Steve

The printList and printReverse functions enables a client to print elements of a LinkedList. In other words, this code fragment:

LinkedList 1s;

1s.insertToRear("Cory");

1s.insertToRear("Topanga");

1s.insertToRear("Shawn");

1s.insertToRear("Eric");

1s. printList ();

1s.printReverse ();

must write

Cory Topanga Shawn Eric

Eric Shawn Topanga Cory

You should have one space between after each item printed with an additional newline after the last item. Here is an example of the append function:

LinkedList e1;

e1.insertToRear("devoe");

e1.insertToRear("biv");

e1.insertToRear("bell");

LinkedList e2;

e2.insertToRear("Big Boi");

e2.insertToRear("Andre");

e1.append(e2); // adds contents of e2 to the end of e1

string s;

assert(e1.size() == 5 && e1.get(3, s) && s == "Big Boi");

assert(e2.size() == 2 && e2.get(1, s) && s == "Andre");

Here is an example of the reverseList function:

LinkedList e1;

e1.insertToRear("Norm");

e1.insertToRear("Cliff");

e1.insertToRear("Carla");

e1.insertToRear("Sam");

e1.reverseList(); // reverses the contents of e1

string s;

assert(e1.size() == 4 && e1.get(0, s) && s == "Sam");

Here's an example of the swap function:

LinkedList e1;

e1.insertToRear("D");

e1.insertToRear("C");

e1.insertToRear("B");

e1.insertToRear("A");

LinkedList e2;

e2.insertToRear("Z");

e2.insertToRear("Y");

e2.insertToRear("X");

e1.swap(e2); // exchange contents of e1 and e2

string s;

assert(e1.size() == 3 && e1.get(0, s) && s == "Z");

assert(e2.size() == 4 && e2.get(2, s) && s == "B");

When comparing items, just use the == or != operators provided for the string type by the library. These do case-sensitive comparisons, and that's fine.

(MUST BE A singly linked list not doubly)

One zip file that contains your solution to thee problem. The zip file must contain only the files LinkedList.h, LinkedList.cpp, and main.cpp. The header file LinkedList.h will contain all the code from the top of this specification (includes, typedef, struct Node, class LinkedList) and proper guards, while the C++ file LinkedList.cpp will contain the LinkedList member functions you will write. If you don't finish everything you should return dummy values for your missing definitions. The main file main.cpp can have the main routine do whatever you want because we will rename it to something harmless, never call it, and append our own main routine to your file. Our main routine will thoroughly test your functions. You'll probably want your main routine to do the same. Your code must be such that if we insert it into a suitable test framework with a main routine and appropriate #include directives, it compiles. (In other words, it must have no missing semicolons, unbalanced parentheses, undeclared variables, etc.)

Solutions

Expert Solution

//LinkedList.h

#pragma once

#include <iostream>

#include <string>

using namespace std;

typedef string ItemType;

struct Node{

ItemType value;

Node *next;

};

class LinkedList{

private:

Node * head;

public:

// default constructor

LinkedList() : head(nullptr) { }

// copy constructor

LinkedList(const LinkedList& rhs);

// Destroys all the dynamically allocated memory

// in the list.

~LinkedList();

// assignment operator

const LinkedList& operator=(const LinkedList& rhs);

// Inserts val at the rear of the list

void insertToRear(const ItemType &val);

// Prints the LinkedList void

void printList() const;

// Sets item to the value at position i in this

// LinkedList and return true, returns false if

// there is no element i

bool get(int i, ItemType& item) const;

// Reverses the LinkedList

void reverseList();

// Prints the LinkedList in reverse order

void printReverse() const;

// Appends the values of other onto the end of this

// LinkedList.

void append(const LinkedList &other);

// Exchange the contents of this LinkedList with the other

// one.

void swap(LinkedList &other);

// Returns the number of items in the Linked List.

int size() const;

};

-----------------------------------------------

//LinkedList.cpp

#include"Oct_26_LinkeList.h"

// copy constructor

LinkedList::LinkedList(const LinkedList& rhs)

{

Node *cur = rhs.head;

while (cur != NULL)

{

insertToRear(cur->value);

}

}

// Destroys all the dynamically allocated memory

// in the list.

LinkedList::~LinkedList()

{

Node *cur = head, *tmp;

while (cur != NULL)

{

tmp = cur->next;

delete cur;

cur = tmp;

}

}

// assignment operator

const LinkedList& LinkedList::operator=(const LinkedList& rhs)

{

Node *cur = rhs.head;

while (cur != NULL)

{

insertToRear(cur->value);

}

return *this;

}

// Inserts val at the rear of the list

void LinkedList::insertToRear(const ItemType &val)

{

Node *cur = head,*newNode;

newNode = new Node;

newNode->value = val;

newNode->next = NULL;

if (head == NULL)

{

head = newNode;

}

else

{

while (cur->next != NULL)

cur = cur->next;

cur->next = newNode;

}

}

// Prints the LinkedList void

void LinkedList::printList() const

{

Node *cur = head;

while (cur != NULL)

{

cout << cur->value << " ";

cur = cur->next;

}

}

// Sets item to the value at position i in this

// LinkedList and return true, returns false if

// there is no element i

bool LinkedList::get(int i, ItemType& item) const

{

Node *cur = head;

int count = 0;

while (cur != NULL)

{

if (count == i)

{

item = cur->value;

return true;

}

cur = cur->next;

++count;

}

return false;

}

// Reverses the LinkedList

void LinkedList::reverseList()

{

Node *cur = head;

Node *prev = NULL, *next = NULL;

while (cur != NULL)

{

next = cur->next;

cur->next = prev;

prev = cur;

cur = next;

}

head = prev;

}

// Prints the LinkedList in reverse order

void LinkedList::printReverse() const

{

int n = size();

Node *cur = head;

ItemType *arr = new ItemType[n];

for (int i = 0; i < n; i++)

{

arr[i] = cur->value;

cur = cur->next;

}

cout << "Linked list in reverse order: ";

for (int i = n-1; i >=0; i--)

{

cout << arr[i] << " ";

}

cout << endl;

}

// Appends the values of other onto the end of this

// LinkedList.

void LinkedList::append(const LinkedList &other)

{

Node *cur = other.head;

while (cur != NULL)

{

insertToRear(cur->value);

cur = cur->next;

}

}

// Exchange the contents of this LinkedList with the other

// one.

void LinkedList::swap(LinkedList &other)

{

Node *cur = head, *cur1 = other.head,*prev=NULL,*prev1=NULL,*temp;

ItemType tmp;

//get size of two lists

int n1 = size(), n2 = other.size();

int n = n1 < n2 ? n1 : n2;

if (n1 == n2)

n = n1;

//swap contents fro two lists

for (int i = 0; i < n; i++)

{

tmp = cur->value;

cur->value = cur1->value;

cur1->value = tmp;

prev = cur;

cur = cur->next;

prev1 = cur1;

cur1 = cur1->next;

}

if (n1 > n)

{

Node *tmp;

while (cur != NULL)

{

other.insertToRear(cur->value);

prev->next = cur->next;

temp = prev->next;

prev->next = NULL;

delete temp;

prev = cur->next;

cur = cur->next;

}

}

if (n2 > n)

{

while (cur != NULL)

{

insertToRear(cur1->value);

prev1->next = cur1->next;

temp = prev->next;

prev1->next = NULL;

delete temp;

prev1 = cur1->next;

cur1 = cur1->next;

}

}

}

// Returns the number of items in the Linked List.

int LinkedList::size() const

{

Node *cur = head;

int count = 0;

while (cur != NULL)

{

++count;

cur = cur->next;

}

return count;

}

---------------------------------------------------

//main.cpp and output ( it wil not have any error )

#include<iostream>

#include<string>

#include<assert.h>

#include"Oct_26_LinkeList.h"

using namespace std;

int main()

{

LinkedList ls;

ls.insertToRear("Carl");

ls.insertToRear("Hariette");

ls.insertToRear("Eddie");

ls.insertToRear("Laura");

ls.insertToRear("Judy");

ls.insertToRear("Steve");

for (int k = 0; k < ls.size(); k++)

{

string x;

ls.get(k, x);

cout << x << endl;

}

LinkedList e1;

e1.insertToRear("devoe");

e1.insertToRear("biv");

e1.insertToRear("bell");

LinkedList e2;

e2.insertToRear("Big Boi");

e2.insertToRear("Andre");

e1.append(e2); // adds contents of e2 to the end of e1

string s;

assert(e1.size() == 5 && e1.get(3, s) && s == "Big Boi");

assert(e2.size() == 2 && e2.get(1, s) && s == "Andre");

//Here is an example of the reverseList function :

LinkedList e;

e.insertToRear("Norm");

e.insertToRear("Cliff");

e.insertToRear("Carla");

e.insertToRear("Sam");

e.reverseList(); // reverses the contents of e1

//string s;

s.clear();

assert(e.size() == 4 && e.get(0, s) && s == "Sam");

LinkedList e3;

e3.insertToRear("D");

e3.insertToRear("C");

e3.insertToRear("B");

e3.insertToRear("A");

LinkedList e4;

e4.insertToRear("Z");

e4.insertToRear("Y");

e4.insertToRear("X");

e3.swap(e4); // exchange contents of e3 and e4

//string s;

s.clear();

assert(e3.size() == 3 && e3.get(0, s) && s == "Z");

assert(e4.size() == 4 && e4.get(2, s) && s == "B");

}

/*output

Carl

Hariette

Eddie

Laura

Judy

Steve

*/


Related Solutions

Implement a program as an object using a class (abstract data type) in C++ that does...
Implement a program as an object using a class (abstract data type) in C++ that does the following: 1) reads the firstName, lastName and 3 test scores of at least five students. 2) calculate student test score totals, average, letter grade for each student. 3) Display the results in a table format showing firstName, lastName, test1, test2, test3, total, average, letterGrade, of all the students. 3 files .h, .cpp, main.cpp create an object that can hold records. must get records...
Write a c++ class definition for an abstract data type describing a bookstore inventory. Each book...
Write a c++ class definition for an abstract data type describing a bookstore inventory. Each book has the following attributes: Book Title (character string); Book Author (character string); Book Price (Floating point number having two decimal places); Count of books on hand (int); The member functions are as follows: A constructor that is used to initialize all four elements of the structure to values inputted by the user; A function that displays in a readable tabular form the contents of...
Assume you have created the following data definition class: public abstract class Organization { private String...
Assume you have created the following data definition class: public abstract class Organization { private String name;    private int numEmployees;    public static final double TAX_RATE = 0.01;    public String getName() { return this.name; }    public int getNumEmployees() { return this.numEmployees; }         public abstract double calculateTax() {       return this.numEmployees * TAX_RATE;    } } In your own words, briefly (1-2 sentences) explain why the data definition class will not compile. Then, write modified code that...
1. Implement the stack abstract data type. Write it as a separate class called Stack. For...
1. Implement the stack abstract data type. Write it as a separate class called Stack. For simplicity the data type to be stored in the stack is String but you can also use generic type. 2. Test your class implementation by calling push() and pop(). If the stack is empty (size equals zero) pop() should return null and print that “stack is empty”. If stack is full (size equals max) push() returns false and prints that “stack is full”. This...
Week 3 In-Class Exercise C++ Payroll Design a PayRoll class that is an abstract data type...
Week 3 In-Class Exercise C++ Payroll Design a PayRoll class that is an abstract data type for payroll. It has data members for an employee’s hourly pay rate, number of hours worked, and total pay for the week. Your class must include the following member functions: a constructor to set the hours and pay rate as arguments, a default constructor to set data members to 0, member functions to set each of the member variables to values given as an...
c++ programming 1.1 Class definition Define a class bankAccount to implement the basic properties of a...
c++ programming 1.1 Class definition Define a class bankAccount to implement the basic properties of a bank account. An object of this class should store the following data:  Account holder’s name (string)  Account number (int)  Account type (string, check/savings/business)  Balance (double)  Interest rate (double) – store interest rate as a decimal number.  Add appropriate member functions to manipulate an object. Use a static member in the class to automatically assign account numbers. 1.2 Implement...
Consider the following definition of a doubly linked-list: class LinkedList{ public: LinkedList():head(0), tail(0){} ~LinkedList(); void reverse();...
Consider the following definition of a doubly linked-list: class LinkedList{ public: LinkedList():head(0), tail(0){} ~LinkedList(); void reverse(); //reverses the order of elements in the linked list void insert(int value); private: struct Node{ int data; Node* next; Node* prev; }; Node* head; Node* tail; //Add your helper function here that recursively reverses the order of elements in the linked list }; Write the declaration of a helper function in the class provided above that recursively reverses the order of elements in the...
Java - Write an abstract class called Shape with a string data field called colour. Write...
Java - Write an abstract class called Shape with a string data field called colour. Write a getter and setter for colour. Write a constructor that takes colour as the only argument. Write an abstract method called getArea()
import java.util.LinkedList; public class StudentLinkedList { public static void main(String[] args) { LinkedList<Student> linkedlist = new...
import java.util.LinkedList; public class StudentLinkedList { public static void main(String[] args) { LinkedList<Student> linkedlist = new LinkedList<Student>(); linkedlist.add(new Student("Ahmed Ali", 20111021, 18, 38, 38)); linkedlist.add(new Student("Sami Kamal", 20121021, 17, 39, 35)); linkedlist.add(new Student("Salem Salim", 20131021, 20, 40, 40)); linkedlist.add(new Student("Rami Mohammed", 20111031, 15, 35, 30)); linkedlist.add(new Student("Kim Joe", 20121024, 12, 32, 32)); linkedlist.addFirst(new Student("Hadi Ali", 20111025, 19, 38, 39)); linkedlist.addLast(new Student("Waleed Salim", 20131025, 10, 30, 30)); linkedlist.set(0, new Student("Khalid Ali", 20111027, 15, 30, 30)); linkedlist.removeFirst(); linkedlist.removeLast(); linkedlist.add(0, new Student("John Don",...
Using STL stack class, implement in C++ the following pseudocodefunctioncheckBraces(aString: string) that checks for...
Using STL stack class, implement in C++ the following pseudocode functioncheckBraces(aString: string) that checks for balanced braces { } in a given string /arithmetic expressions. Write a main() program to test the function.// Checks the string aString to verify that braces match.// Returns true if aString contains matching braces, false otherwise.checkBraces(aString: string): boolean{aStack = a new empty stackbalancedSoFar = truei =0// Tracks character position in stringwhile (balancedSoFar and i < length of aString) {ch = character at position i in...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT