Lab 8 - part 2

Lab 8 - part 2 - Searching a Linked List

In the previous Activity, you learned to create linked lists. In this activity, you will learn to search a linked list to locate a particular node. 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 to the fact that we do not modify the linked list, we don't pass the head pointer 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. The following program is the modified version of P15_1.cpp that now includes the search function.

// P15_2.cpp - Program to demonstrate the function search.
#include <iostream>
#include <cstddef>
#include <string>

using namespace std;

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

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);

cout << "List contains:" << endl;
show_list(head);

    string target;
    cout << "Enter an item to search for" << endl;
    cin >> target;
    NodePtr result = search(head, target);
    if (result == NULL)
       cout << target << " is not on the list." << endl;
    else
       cout << target << " is on the list." << endl;

return 0;
}

NodePtr search(NodePtr head, string target)
{
// Point to the head node
NodePtr here = head;

    // If the list is empty nothing to search
    if (here == NULL)
    {
        return NULL;
    }
    // Search for the item
    else
    {
        // while you have still items and you haven't found the target yet
        while (here-> item != target && here->link != NULL)
            here = here->link;
        // Found the target, return the pointer at that location
        if (here-> item == target)
            return here;
        // Search unsuccessful, return Null
        else
            return NULL;
    }
}

void head_insert(NodePtr& head, string an_item, int a_number)
{
NodePtr temp_ptr;
temp_ptr = new Node;

temp_ptr -> item = an_item;
temp_ptr -> count = a_number;

temp_ptr->link = head;
head = temp_ptr;
}

void show_list(NodePtr& head)
{
NodePtr here = head;

    while (here != NULL)
    {
        cout << here -> item << endl;
        here = here ->link;
    }
}

Exercise 15.2
Modify the above program to include the expiration date, then give the users a search choice. Provide two search options:
1) item, the way it is done in the program, and
2) expiration date

Back to part 1 on to part 3