logo Use CA10RAM to get 10%* Discount.
Order Nowlogo
(5/5)

CS 202 – Assignment #9 Design and implement three C++ classes;

INSTRUCTIONS TO CANDIDATES
ANSWER ALL QUESTIONS

 

CS 202 – Assignment #9

Purpose: Learn to about linked lists

Points: 150

Assignment:

Design and implement three C++ classes;

• linkedListType, that defines the basic

properties of a linked list

• unorderedLinkedList, derived from the

class linkedListType class

• orderedLinkedList, derived from the

class linkedListType class

Two mains will be provided; one that uses the 

linkedListType class (indirectly) and the 

unorderedLinkedList class, and another that

uses the the linkedListType class (indirectly) and

unorderedLinkedList class.

The class hierarchy is shown as follows:

linkedListType<myType>

unorderedLinkedList<myType> orderedLinkedList<myType>

Submission:

● All files must compile and execute on Ubuntu and compiler with C++11.

● Submit source files

◦ Note, do not submit the provided main (we have it).

● Once you submit, the system will score the project and provide feedback.

◦ If you do not get full score, you can (and should) correct and resubmit.

◦ You can re-submit an unlimited number of times before the due date/time.

● Late submissions will be accepted for a period of 24 hours after the due date/time for any 

given lab. Late submissions will be subject to a ~2% reduction in points per an hour late.

If you submit 1 minute - 1 hour late -2%, 1-2 hours late -4%, … , 23-24 hours late -50%. 

This means after 24 hours late submissions will receive an automatic 0.

● Linked List Structure

We will use the following node structure definition.

template <class myType> 

struct nodeType {

myType info; 

nodeType<myType> *link; 

};

● Linked List Class

The linked list class will implement the functions.

linkedListType<myType>

#count: int

#*first: nodeType<myType>

#*last: nodeType<myType>

+linkedListType()

+linkedListType(const linkedListType<myType>&)

+~linkedListType()

+initializeList(): void

+isEmptyList() const: bool

+print() const: void

+reversePrint() const: void

+length() const: int

+destroyList(): void

+front() const: myType

+back() const: myType

+firstPtr() const: nodeType<myType> *

+search(const myType&) const = 0: bool (abstract)

+insert(const myType&) = 0: void (abstract)

+insertLast(const myType&) = 0: void (abstract)

+deleteNode(const myType&) = 0: void (abstract)

-copyList(const linkedListType<myType>&): void

-recursiveReversePrint(nodeType<myType> *) const: void

Linked List Type → Function Descriptions

• The linkedListType() constructor should initialize the list to an empty state (first =

NULL, last = NULL, count = 0). The initializeList() function may be used. The 

linkedListType(const linkedListType<myType>&) copy constructor should create 

a new, deep copy from the passed list.

• The ~linkedListType() destructor should linked list (releasing the allocated 

memory). The destroyList() function may be used.

• The initializeList() function should initialize the list to an empty state (first = 

NULL, last = NULL, count = 0). If the list is not empty, all current items should 

be deleted.

• The isListEmpty() function should determine whether the list is empty, returning 

true if the list is empty and false otherwise.

• The print() function should print all data elements of the linked list. Refer to the 

examples for formatting. The reversePrint() function should print all elements of 

the linked list in reverse order. The reversePrint() function must use the 

recursiveReversePrint(nodeType<Type> *) to provide a recursive 

implementation. Refer to the examples for formatting.

• The length() function should return the number of nodes in the list.

• The destroyList() function should delete all the nodes from the list (including 

ensuring that first = NULL, last = NULL, count = 0, when done).

• The front() function should return the first element of the list. The function must 

ensure that list exists. The back() function should return the last element of the 

list. The function must ensure that list exists. If the list is empty, the function 

should return NULL.

• The firstPtr() function should return a copy of the first pointer.

• The search(const myType&), insert(const myType&), insertLast(const myType&), 

and deleteNode(const myType&) functions are abstract in the linkedListType class 

and no implemented is required in this class. However, an inheriting class must 

provide implementations.

● Unordered Linked List Class

The unordered linked list class will implement the functions.

unorderedLinkedList<Type>

<no class variables>

+search(const myType&) const: bool

+insert(const myType&): void

+insertLast(const myType&): void

+deleteNode(const myType&): void

In the unorderedLinkedList class, we will need to access the protected class variables in 

the linkedListType class. The following statements should be included in the class 

definition.

protected:

using linkedListType<myType>::count;

using linkedListType<myType>::first;

using linkedListType<myType>::last;

This is required in order for the derived class to recognize the inherited protected 

variables (from the base class) when a template is used.

Unordered Link List Type → Function Descriptions

• The search(const myType&) function determines whether specific item is in the 

list and returns true if the item found, and false otherwise. Since the list is 

unordered, the search must check every item in the linked list.

• The insert(const myType&) function should insert the item (passed) into the list at

the beginning and update the count.

• The insertLast(const myType&) function should insert the item (passed) into the 

list at the end and update the count.

• The deleteNode(const myType&) function should remove the item (passed) from 

the list and update the count. If the item is not found, nothing should be changed.

● Ordered Linked List Class

The unordered linked list class will implement the functions.

orderedLinkedList<myType>

<no class variables>

+search(const myType&) const: bool

+insert(const myType&): void

+insertLast(const myType&): void

+deleteNode(const myType&): void

In the orderedLinkedList class, we will need to access the protected class variables in the

linkedListType class. The following statements should be included in the class 

definition.

protected:

using linkedListType<myType>::count;

using linkedListType<myType>::first;

using linkedListType<myType>::last;

This is required in order for the derived class to recognize the inherited protected 

variables (from the base class) when a template is used.

Ordered Link List Type → Function Descriptions

• The search(const myType&) function determines whether specific item is in the 

list and returns true if the item found, and false otherwise. Since the list is 

ordered, the search should stop when it either finds the items or passes the 

possible location in the linked list.

• The insert(const myType&) function should insert the item (passed) into the list in

its appropriate position (sorted). The function should allow duplicate values.

• The insertLast(const Type&) function should use the insert(const myType&)

function in order to maintain the sorted order.

• The deleteNode(const Type&) function should remove the item (passed) from the 

list and update the count. If the item is not found, nothing should be changed. 

Since the list is ordered, the search should stop when it either finds the items or 

passes the possible location in the linked list.

Refer to the example executions for output formatting. Make sure your program includes the 

appropriate documentation. Note, points will be deducted for especially poor style or 

inefficient coding.

Error Messages

As applicable, the ordered and unodered linked lists should display error message. The 

following are some error messages.

cout << "Cannot delete from an empty list." << endl;

cout << "The item to be deleted is not in the list." << endl;

Make File:

The provided make file assumes the source file names include (linkedListType.h, 

unorderedLinkedList.h, orderedLinkedList.h).

To build the provided main for the unordered links lists;

make mainUnordered

To build the provided main for the ordered links lists;

make mainOrdered

And typing;

make

Which will create both executables.

Example Execution:

Below is an example program execution for the main.

ed-vm% ./mainUnordered

CS 202 - Assignment #9

Unordered Linked Lists

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

List 1 - Integers

Cannot delete from an empty list.

Insertions...

List 1 - Unordered: 

55 43 11 56 125 88 32 14 3 90 89 2 19 4 56 34 22 

List 1 Unordered, in reverse order: 

22 34 56 4 19 2 89 90 3 14 32 88 125 56 11 43 55 

The item to be deleted is not in the list.

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

List 2 - Integers:

List 2 length: 17

List 2 Unordered: 

22 34 56 4 19 2 89 90 3 14 32 88 125 56 11 43 55 

List 2 Unordered New Length: 14

List 2 Unordered -> With nodes removed: 0 14 32

22 34 56 4 19 2 89 90 88 125 56 11 43 55 

List 2 Unordered -> Search tests (for 14 and 90): 

List 2: item 14 was not found.

List 2: item 90 was found.

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

List 3 - Doubles:

List 3 Unordered: 

22.1 34.5 56.6 4.3 19.2 2.5 89.4 90.8 3.14 14.3 32.9 88.1 125.3 56.7 

11.5 43.8 55.2 

List 3 Unordered (reverse order): 

55.2 43.8 11.5 56.7 125.3 88.1 32.9 14.3 3.14 90.8 89.4 2.5 19.2 4.3 

56.6 34.5 22.1 

List 3 Unordered -> Search tests (for 11.5 and 19.2): 

List 3: item 11.5 was found.

List 3: item 19.2 was not found.

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

List 4 - Doubles:

List 4 Unordered (original list): 

22.1 34.5 56.6 4.3 19.2 2.5 89.4 90.8 3.14 14.3 32.9 88.1 125.3 56.7 

11.5 43.8 55.2 

List 4 Unordered Delete Testing...

The item to be deleted is not in the list.

List 4 Unordered (modified): 

56.6 4.3 19.2 2.5 89.4 90.8 14.3 32.9 88.1 125.3 56.7 11.5 

List 4 Unordered - first item: 56.6

List 4 Unordered - last item: 11.5

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

List 5 - Short's (0-4):

List is initially empty, adding 4, 3, 2, 1 and 0.

List 5 Unordered: 

4 3 2 1 0 

List 5 Unordered - first item: 4

List 5 Unordered - last item: 0

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

Lists 6 and 7 - Even Short's (2-20)

Copy of list 5 with 5, 6, 7, 8, and 9 added.

List 6 Unordered (length=10) : 4 3 2 1 0 5 6 7 8 9 

List 7 Unordered (length=10) : 4 3 2 1 0 5 6 7 8 9 

Destroying List 6 Unordered...

List 6 Unordered (should be empty): 

Initializing List 7 Unordered...

List 7 Unordered (should be empty): 

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

String List:

String List is initially empty, adding words...

String List Unordered: 

hills dog familiar big jumps a in green enters 

String List Unordered - first item: hills

String List Unordered - last item: enters

String List Unordered is now empty.

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

Game Over, thank you for playing.

ed-vm%

ed-vm%

ed-vm%

ed-vm% ./mainOrdered

CS 202 - Assignment #9

Ordered Linked Lists

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

List 1 - Integers

Cannot delete from an empty list.

Insertions...

List 1 Ordered: 

2 3 4 11 14 19 22 32 34 43 55 56 56 88 89 90 125 

List 1 Ordered, in reverse order: 

125 90 89 88 56 56 55 43 34 32 22 19 14 11 4 3 2 

The item to be deleted is not in the list.

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

List 2 - Integers:

List 2 length: 17

List 2 Ordered: 

2 3 4 11 14 19 22 32 34 43 55 56 56 88 89 90 125 

List 2 Ordered New Length: 14

List 2 Ordered -> With nodes removed: 0 14 32

2 4 11 19 22 34 43 55 56 56 88 89 90 125 

List 2 Unordered -> Search tests (for 14 and 90): 

List 2: item 14 was not found.

List 2: item 90 was found.

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

List 3 - Doubles:

List 3 Ordered: 

2.5 3.14 4.3 11.5 14.3 19.2 22.1 32.9 34.5 43.8 55.2 56.6 56.7 88.1 89.4

90.8 125.3 

List 3 Ordered (reverse order): 

125.3 90.8 89.4 88.1 56.7 56.6 55.2 43.8 34.5 32.9 22.1 19.2 14.3 11.5 

4.3 3.14 2.5 

List 3 Ordered -> Search tests (for 11.5 and 19.2): 

List 3: item 11.5 was found.

List 3: item 19.2 was not found.

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

List 4 - Doubles:

List 4 Ordered (original list): 

2.5 3.14 4.3 11.5 14.3 19.2 22.1 32.9 34.5 43.8 55.2 56.6 56.7 88.1 89.4

90.8 125.3 

List 4 Ordered Delete Testing...

The item to be deleted is not in the list.

List 4 Ordered (modified): 

2.5 4.3 11.5 14.3 19.2 32.9 56.6 56.7 88.1 89.4 90.8 125.3 

List 4 Ordered - first item: 2.5

List 4 Ordered - last item: 125.3

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

List 5 - Short's (0-4):

List is initially empty, adding 4, 3, 2, 1 and 0.

List 5 Ordered: 

0 1 2 3 4 

List 5 Ordered - first item: 0

List 5 Ordered - last item: 4

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

Lists 6 and 7 - Even Short's (2-20)

Copy of list 5 with 5, 6, 7, 8, and 9 added.

List 6 Ordered (length=10) : 0 1 2 3 4 5 6 7 8 9 

List 7 Ordered (length=10) : 0 1 2 3 4 5 6 7 8 9 

Destroying List 6 Ordered...

List 6 Ordered (should be empty): 

Initializing List 7 Ordered...

List 7 Ordered (should be empty): 

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

List 8 Ordered - Integers:

List A Ordered: 

2 4 6 8 10 12 14 

List B Ordered: 

1 3 5 7 9 11 13 15 

List C Ordered: 

List D Ordered: 

50 

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

String List:

String List is initially empty, adding words...

String List Ordered: 

a big dog enters familiar green hills in jumps 

String List Ordered - first item: a

String List Ordered - last item: jumps

String List Ordered is now empty.

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

Game Over, thank you for playing.

ed-vm%

(5/5)
Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

Ask This Question To Be Solved By Our ExpertsGet A+ Grade Solution Guaranteed

expert
Um e HaniScience

521 Answers

Hire Me
expert
Muhammad Ali HaiderFinance

602 Answers

Hire Me
expert
Husnain SaeedComputer science

863 Answers

Hire Me
expert
Atharva PatilComputer science

930 Answers

Hire Me

Get Free Quote!

317 Experts Online