Part 1: Enumerated Data Types

To increase program readability, C++ provides for enumerated data types. Such types allow descriptive names to be assigned an order and used in place of a sequence of integers. An enumerated data type is declared by a statement beginning with the keyword enum, followed by an identifier and then by a list of descriptive names enclosed in braces. Thus,

enum week_days {Monday, Tuesday, Wednesday, Thursday, Friday};

establishes an order among the workdays of the week. A variable of this type can then be declared by using week_days as the type within a variable declaration statement. Thus,

week_days day;

declares day to be a variable of type week_days.

Variables of enumerated data types can be used as array indices. For example, if hours_worked is declared by the statement

float hours_worked[5];

then the expression hours_worked[Tuesday] provides a more descriptive reference to the second entry in the array than hours_worked[1].

Execute the following program and explain the results.

#include

using namespace std;

enum coin_type {nickel, dime, quarter};

int main()

{

coin_type coin;

int holdings[3] = {3, 6, 2};

int total = 0;

for (coin = nickel; coin <= quarter; coin++)

{

switch (coin)

{

case nickel: total = total + (5 * holdings[coin]); break;

case dime: total = total + (10 * holdings[coin]); break;

case quarter: total = total + (25 * holdings[coin]); break;

}

}

cout << "Total holdings are " << total << " cents. ";

return 0;

}

Although enumerators are stored in memory as integers and you can use them as array subscripts, expressions like coin++ do not work the same as for integers. Instead you must convert coin++ to an equivalent expression

coin = static_cast(coin + 1)

Replace coin++ with coin = static_cast(coin + 1)in the for loop.

Part 2: Searching a Linked List

Step 1: Define a linked list

A linked list is a list constructed using pointers. A linked list is a list of nodes in which each node has a member variable that is a pointer that points to the next node in the list. It is not fixed in size and can grow and shrink while the program is running. In real life, useful dynamic variables are seldom of a simple type such as int or double. They normally are of more complex types such as struct or class. A structure may have several members. An example of a struct definition that could be used to build a linked list is shown below.

struct ListNode { string item; int count; ListNode *link; };

typedef ListNode* ListNodePtr;

Now if we use this to create a pointer variable head as: ListNodePtr head;

Then we have something that looks like this:

Step 2: Searching a Linked List

In the previous discussion, we learned to create linked lists. In this part, you will learn to search a linked list to locate a particular node and remove it (remove operation is optional).

Find the searchList.cpp from Lab 9 introduction. Fill in the missing codes.

As it is the case with every search, we should have a clear and precise idea of what we are searching for. Because structs are the building blocks of a linked list, we should search search for something that is defined as a member of the struct. For example, in the linked list that we defined in the previous activity, we could search for an item or a count. We could search for item "Jam" or a count 10. It seems that the first search is more common. In any case, a search function that searches the list for one of these two, should have two parameters. The first parameter is the linked list and the second one is the item.

NodePtr search(NodePtr head, string target_item)

Note that due the fact that we do not modify the linked list, we don't pass the list as call-by-reference.

The Pseudocode for the search function may look like this:

//Make the pointer variable here point to the head node (that is, the first node) of the linked list.

while( here is not pointing to a node containing the target_item and here is not pointing to the last node) { Make here point to the next node in the list.

}

if(the node pointed to by here contains target) return here; else return NULL:

Now suppose we want to search the linked list that we have created.

// Program to demonstrate the function search.

// filling in the blank

#include

#include

#include

using namespace std;

struct Node

{

};

typedef Node* NodePtr;

NodePtr search(NodePtr head, string an_item);

void head_insert(NodePtr& head, string an_item, int a_number);

void show_list(NodePtr& head);

int main()

{

NodePtr head = NULL;

head_insert(head, "Tea", 2);

head_insert(head, "Jam", 3);

head_insert(head, "Rolls", 10);

return 0;

}

NodePtr search(NodePtr head, string target)

{

}

void head_insert(NodePtr& head, string an_item, int a_number)

{

}

void show_list(NodePtr& head)

{

}

Part 3: Design your own linked list and member functions

Design a simple linked list class with only two member functions and a default constructor:

void add(double x);

boolean isMember(double x);

LinkedList( );

The add function adds a new node containing x to the front (head) of the list, while the isMember function tests to see if the list contains a node with the value x. Test your linked list class by adding various numbers to the list and then testing for membership.

List Copy Constructor

Add a copy constructor. Test your class by making a copy of a list and then testing membership on the copy.

List Print

Add a print member function. Test the class by starting with an empty list, adding some elements, and then printing the resulting list out.

List Member Deletion

Modify the list class you created in the previous programming challenges by adding a function to remove an item from the list, and by adding a destructor:

void remove(double x);

~LinkedList();

Test the class by adding by a sequence of instructions that mixes operations for adding items, removing items, and printing the list.

List Reverse

Adding a member function for reversing the list:

void reverse();

The member function rearranges the nodes in the list so that their order is reversed. You should do this without creating or destroying nodes.

List Search

Modify the list class include a member function

int search(double x)

that returns the position of a number x on the list. The ?rst node in the list is at position 0, the second node is at position 1, and so on. If x is not found on the list, the search would return -1. Test the new member function using an appropriate driver program.