Question

Create a C++ project. Download and add the attached .h and .cpp to the project. Write an implementation file to implement the namespace declared in the attached CSCI361Proj5.h. Name the implementation file as YourNameProj5.cpp and add it to the project. Run the project to see your grade.

.h file:

// Provided by:   ____________(your name here)__________
// Email Address: ____________(your email address here)________
// FILE: link.h
// PROVIDES: A toolkit of 14 functions for manipulating linked lists. Each
// node of the list contains a piece of data and a pointer to the next node.
// The type of the data is defined as Node::Item in a typedef statement.
// The complete type definitions used by the toolkit are:
//
//   struct Node                   Item may be any of the C++ built-in types
//   {                             (int, char, etc.), or a class with a default
//       typedef _____ Item;       constructor, an assignment operator,
//       Item data;                and a test for equality (x == y).
//       Node *link;
//   };
//
// FUNCTIONS in the linked list toolkit:
//   size_t list_length(Node* head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The value returned is the number of nodes in the linked
//     list. The list itself is unaltered.
//
//   void list_head_insert(Node*& head_ptr, const Node::Item& entry)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the head of the linked list; head_ptr now points to the head of the new,
//     longer linked list.
//
//   void list_insert(Node* previous_ptr, const Node::Item& entry)
//     Precondition: previous_ptr points to a node in a linked list.
//     Postcondition: A new node containing the given entry has been added
//     after the node that previous_ptr points to.
//
//   Node* list_search(Node* head_ptr, const Node::Item& target)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The pointer returned points to the first node containing
//     the specified target in its data member. If there is no such node, the
//     null pointer is returned. The list itself is unaltered.
//
//   Node* list_locate(Node* head_ptr, size_t position)
//     Precondition: head_ptr is the head pointer of a linked list, and
//     position > 0.
//     Postcondition: The pointer returned points to the node at the specified
//     position in the list. (The head node is position 1, the next node is
//     position 2, and so on). If there is no such position, then the null
//     pointer is returned. The list itself is unaltered.
//
//   void list_head_remove(Node*& head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The head node has been removed and returned to the heap;
//     head_ptr is now the head pointer of the new, shorter linked list.
//
//   void list_remove(Node* previous_ptr)
//     Precondition: previous_ptr points to a node in a linked list, and this
//     is not the tail node of the list.
//     Postcondition: The node after previous_ptr has been removed from the
//     linked list.
//
//   void list_clear(Node*& head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: All nodes of the list have been returned to the heap,
//     and the head_ptr is now NULL.
//
//   void list_copy(Node* source_ptr, Node*& head_ptr)
//     Precondition: source_ptr is the head pointer of a linked list.
//     Postcondition: head_ptr is the head pointer for
//     a new list that contains the same items as the list pointed to by
//
//   size_t list_occurrences(Node* head_ptr, const Node::Item& target)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: The return value is the count of the number of times
//     target appears as the data portion of a node on the linked list.
//     The linked list itself is unchanged.
//
//   void list_tail_attach(Node*& head_ptr, const Node::Item& entry)
//     Precondition: head_ptr is the head pointer of a linked list.
//     Postcondition: A new node containing the given entry has been added at
//     the tail of the linked list; if this happens to be the first node of
//     the linked list, then head_ptr now points to this node (otherwise
//     head_ptr is unchanged).
//
//   void list_tail_remove(Node*& head_ptr)
//     Precondition: head_ptr is the head pointer of a linked list, with at
//     least one node.
//     Postcondition: The tail node has been removed and returned to the heap;
//     if the list is now empty, then head_ptr is null; otherwise head_ptr
//     is unchanged.
//
//   Node* list_copy_front(Node* source_ptr, size_t n)
//     Precondition: source_ptr is the head pointer of a linked list
//     Postcondition: The value returned is the head pointer for
//     a new list that contains copies of the first n nodes from the list
//     that source_ptr points to. If there less than n nodes in source list,
//     just copy all nodes and done

// DYNAMIC MEMORY usage by the toolkit:
//   If there is insufficient dynamic memory, then the following functions call
//   new_handler before any changes are made to the list that head_ptr points
//   to : list_head_insert, list_insert, list_copy, list_piece, list_tail_attach,
//   list_copy_front

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <stdlib.h> // Provides size_t
namespace FHSULINKEDLIST
{
    struct Node
    {
        typedef int Item;
        Item data;
        Node *link;
    };
    
    // FUNCTIONS for the linked list toolkit
    size_t list_length(const Node* head_ptr);
    void list_head_insert(Node*& head_ptr, const Node::Item& entry);
    void list_insert(Node* previous_ptr, const Node::Item& entry);
    Node* list_search(Node* head_ptr, const Node::Item& target);
    Node* list_locate(Node* head_ptr, size_t position);
    void list_head_remove(Node*& head_ptr);
    void list_remove(Node* previous_ptr);
    void list_clear(Node*& head_ptr);
    void list_copy(Node* source_ptr, Node*& head_ptr);
    size_t list_occurrences(Node* head_ptr, const Node::Item& target);
    void list_tail_attach(Node*& head_ptr, const Node::Item& entry);
    void list_tail_remove(Node*& head_ptr);
    Node* list_copy_front(Node* source_ptr, size_t n);
}

#endif

.cpp file:

// This is the grader file of project 5

#include <iostream>
#include "CSCI361Proj5.h"

using namespace std;
using namespace FHSULINKEDLIST;

int test1(); // test list head insert, list head remove, list insert, list remove, list clear, and list length, 5 points
int test2(); // test list search, list occurrence and list located functions. 1 point
int test3(); // test list tail attach, and list tail remove functions 2 points
int test4(); // test list copy function, and list front copy front functions 2 point

int main()
{
    int totalScore = 0;
    
    cout <<"Let's see your grade. \n\n";
    system("pause");
    cout << endl;
    
    int score = test1();
    if(score == 0)
    {
        cout << "Basic insert function failed. No test will continue. Your score is 0.\n End testing program!\n";
        system("pause");
        return 0;
    }
    
    totalScore += score;
    cout << "Your points so far is " << totalScore << "\n\n";
    system("pause");
    cout << endl;
    
    score = test2();
    if(score == 0)
        cout << "Test 2 failed\n";
    else
        cout << "Test 2 passed\n";
    totalScore += score;
    cout << "Your points so far is " << totalScore << "\n\n";
    system("pause");
    cout << endl;
    
    score = test3();
    if(score == 0)
        cout << "Test 3 failed\n";
    else
        cout << "Test 3 passed\n";
    totalScore += score;
    cout << "Your points so far is " << totalScore << "\n\n";
    system("pause");
    cout << endl;
    
    score = test4();
    if(score == 0)
        cout << "Test 4 failed\n";
    else
        cout << "Test 4 passed\n";
    totalScore += score;
    cout << "Your points so far is " << totalScore << "\n\n";
    system("pause");
    cout << endl;
    
    
    cout << "If you turn in your program to Dr. Zeng now, your will get " << totalScore << " out of 10\n";
    cout << "Dr. Zeng will read your program, check your program style\n and decide if you will get 1 less point\n";
    
    system("pause");
    return 0;
}

int test1()
{
    Node* list = NULL; // an empty list
    list_head_insert(list, 0); // list contains one element 0;
    if(list == NULL || list->data != 0 || list->link != NULL)
    {
        cout << "list_head_insert function doesn't work for empty list\n";
        return 0;
    }
    
    list_head_insert(list, 1);
    list_head_insert(list, 2); // now list contains 2, 1, 0
    if(list->data != 2 || list->link->data != 1 || list->link->link->data != 0)
    {
        cout << "list_head_insert function doesn't work for non-empty list\n";
        return 0;
    }
    
    cout << "list_head_insert function passes the test\n";
    
    if(list_length(list) != 3)
    {
        cout << "list_length function is wrong\n";
        return 0;
    }
    
    list_head_remove(list); // now list contains 1, 0
    if(list->data != 1 || list->link->data != 0)
    {
        cout << "list_head_remove function doesn't work\n";
        return 0;
    }
    
    list_head_remove(list);
    list_head_remove(list); // now list is empty
    
    if(list != NULL)
    {
        cout << "list_head_remove function doesn't work for one node list\n";
        return 0;
    }
    
    if(list_length(list) != 0)
    {
        cout << "list_length function is wrong for empty list";
        return 0;
    }
    
    cout << "list_head_remove passes the test\n";
    cout << "list_length passes the test\n";
    
    int i;
    for(i = 1; i <= 10; i++)
        list_head_insert(list, i);
    // now list contains 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
    list_clear(list);
    if(list != NULL)
    {
        cout << "list_clear function is not correct\n";
        return 0;
    }
    
    cout << "list_clear function passes the test\n";
    
    list_head_insert(list, 1); // now list contains 1
    for(i = 2; i <= 4; i++)
        list_insert(list, i);
    // now list contains 1, 4, 3, 2
    if(list_length(list) != 4 || list->data != 1 || list->link->data != 4 || list->link->link->data != 3)
    {
        cout << "list_insert function is wrong\n";
        return 0;
    }
    
    cout << "list_insert function passes the test\n";
    
    Node* cursor = list->link; // cursor points to 4
    list_remove(cursor); // now list contains 1, 4, 2
    if(list_length(list) != 3 || list->data != 1 || list->link->data != 4 || list->link->link->data != 2)
    {
        cout << "list_remove function is wrong\n";
        return 0;
    }
    
    cout << "list_remve function passes the test\n";
    
    return 5;
}

int test2()
{
    Node* list = NULL; // an empty linked list
    int i;
    for(i = 1; i <= 5; i++)
    {
        if(i%2 == 0)
            list_head_insert(list, i-1);
        else
            list_head_insert(list, i);
    } // now list contains 5, 3, 3, 1, 1
    
    if(list_search(list, 2) != NULL)
    {
        cout << "list_search function doesn't work for not found case\n";
        return 0;
    }
    
    if(list_search(list, 3) != list->link)
    {
        cout << "list_search function doesn't work for found case\n";
        return 0;
    }
    
    cout << "list_search function passes the test\n";
    
    if(list_occurrences(list, 3) != 2 || list_occurrences(list, 5) != 1 || list_occurrences(list, 2) != 0)
    {
        cout << "list_occurrences function doesn't work\n";
        return 0;
    }
    
    cout << "list_occurrences function passes the test\n";
    
    if(list_locate(list, 2) != list_search(list, 3) || list_locate(list, 6) != NULL)
    {
        cout << "list_locate function doesn't work\n";
        return 0;
    }
    
    cout << "list_locate function passes the test\n";
    
    return 1;
}

int test3() // test list tail attach, and list tail remove functions 2 points
{
    Node* list = NULL; // an empty list
    list_tail_attach(list, 0); // list contains one element 0;
    if(list == NULL || list->data != 0 || list->link != NULL)
    {
        cout << "list_tail_attach function doesn't work for empty list\n";
        return 0;
    }
    
    list_tail_attach(list, 1);
    list_tail_attach(list, 2); // now list contains 0, 1, 2
    if(list->data != 0 || list->link->data != 1 || list->link->link->data != 2)
    {
        cout << "list_tail_attach function doesn't work for non-empty list\n";
        return 0;
    }
    
    cout << "list_tail_attach function passes the test\n";
    
    list_tail_remove(list); // now list contains 0, 1
    if(list->data != 0 || list->link->data != 1 || list_length(list) != 2)
    {
        cout << "list_head_remove function doesn't work\n";
        return 0;
    }
    
    list_tail_remove(list);
    list_tail_remove(list); // now list is empty
    
    if(list != NULL)
    {
        cout << "list_tail_remove function doesn't work for one node list\n";
        return 0;
    }
    
    cout << "list_tail_remove function passes the test\n";
    
    return 2;
    
}

int test4()
{
    Node* list = NULL; // an empty list
    Node* copy = NULL;
    copy = list_copy_front(list, 3);
    if(copy != NULL)
    {
        cout << "list_copy_front function doesn't work for copying empty list\n";
        return 0;
    }
    for(int i = 1; i <= 4; i++)
        list_tail_attach(list, i);
    // list contains 1, 2, 3, 4
    
    copy = list_copy_front(list, 3);
    if(list_length(copy) != 3 || copy->data != 1 || copy->link->data != 2 || copy->link->link->data != 3 )
    {
        cout << "list_copy_front function doesn't work\n";
        return 0;
    }
    
    copy->link->data = 100;
    if(list->link->data == 100)
    {
        cout << "list_copy_front function doesn't work.\n";
        return 0;
    }
    list_clear(copy);
    copy = list_copy_front(list, 6);
    if(list_length(copy) != 4)
    {
        cout << "list_copy_front function doesn't work\n";
        return 0;
    }
    
    cout << "list_copy_front passes the test\n";
    
    list_clear(list);
    for(int i = 1; i <= 3; i++)
        list_head_insert(list, i);
    // list contains 3, 2, 1
    
    list_copy(list, copy);
    if(list_length(copy) != 3 || copy->data != 3 || copy->link->data != 2 || copy->link->link->data != 1 )
    {
        cout << "list_copy function doesn't work\n";
        return 0;
    }
    
    cout << "list_copy function passes the test\n";
    
    return 2;
    
}

Answer 1

// CSCI361Proj5.h

// Provided by: ____________(your name here)__________
// Email Address: ____________(your email address here)________
// FILE: link.h
// PROVIDES: A toolkit of 14 functions for manipulating linked lists. Each
// node of the list contains a piece of data and a pointer to the next node.
// The type of the data is defined as Node::Item in a typedef statement.
// The complete type definitions used by the toolkit are:
//
// struct Node Item may be any of the C++ built-in types
// { (int, char, etc.), or a class with a default
// typedef _____ Item; constructor, an assignment operator,
// Item data; and a test for equality (x == y).
// Node *link;
// };
//
// FUNCTIONS in the linked list toolkit:
// size_t list_length(Node* head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The value returned is the number of nodes in the linked
// list. The list itself is unaltered.
//
// void list_head_insert(Node*& head_ptr, const Node::Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the head of the linked list; head_ptr now points to the head of the new,
// longer linked list.
//
// void list_insert(Node* previous_ptr, const Node::Item& entry)
// Precondition: previous_ptr points to a node in a linked list.
// Postcondition: A new node containing the given entry has been added
// after the node that previous_ptr points to.
//
// Node* list_search(Node* head_ptr, const Node::Item& target)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The pointer returned points to the first node containing
// the specified target in its data member. If there is no such node, the
// null pointer is returned. The list itself is unaltered.
//
// Node* list_locate(Node* head_ptr, size_t position)
// Precondition: head_ptr is the head pointer of a linked list, and
// position > 0.
// Postcondition: The pointer returned points to the node at the specified
// position in the list. (The head node is position 1, the next node is
// position 2, and so on). If there is no such position, then the null
// pointer is returned. The list itself is unaltered.
//
// void list_head_remove(Node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The head node has been removed and returned to the heap;
// head_ptr is now the head pointer of the new, shorter linked list.
//
// void list_remove(Node* previous_ptr)
// Precondition: previous_ptr points to a node in a linked list, and this
// is not the tail node of the list.
// Postcondition: The node after previous_ptr has been removed from the
// linked list.
//
// void list_clear(Node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: All nodes of the list have been returned to the heap,
// and the head_ptr is now NULL.
//
// void list_copy(Node* source_ptr, Node*& head_ptr)
// Precondition: source_ptr is the head pointer of a linked list.
// Postcondition: head_ptr is the head pointer for
// a new list that contains the same items as the list pointed to by
//
// size_t list_occurrences(Node* head_ptr, const Node::Item& target)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: The return value is the count of the number of times
// target appears as the data portion of a node on the linked list.
// The linked list itself is unchanged.
//
// void list_tail_attach(Node*& head_ptr, const Node::Item& entry)
// Precondition: head_ptr is the head pointer of a linked list.
// Postcondition: A new node containing the given entry has been added at
// the tail of the linked list; if this happens to be the first node of
// the linked list, then head_ptr now points to this node (otherwise
// head_ptr is unchanged).
//
// void list_tail_remove(Node*& head_ptr)
// Precondition: head_ptr is the head pointer of a linked list, with at
// least one node.
// Postcondition: The tail node has been removed and returned to the heap;
// if the list is now empty, then head_ptr is null; otherwise head_ptr
// is unchanged.
//
// Node* list_copy_front(Node* source_ptr, size_t n)
// Precondition: source_ptr is the head pointer of a linked list
// Postcondition: The value returned is the head pointer for
// a new list that contains copies of the first n nodes from the list
// that source_ptr points to. If there less than n nodes in source list,
// just copy all nodes and done

// DYNAMIC MEMORY usage by the toolkit:
// If there is insufficient dynamic memory, then the following functions call
// new_handler before any changes are made to the list that head_ptr points
// to : list_head_insert, list_insert, list_copy, list_piece, list_tail_attach,
// list_copy_front

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <stdlib.h> // Provides size_t

namespace FHSULINKEDLIST
{
struct Node
{
typedef int Item;
Item data;
Node *link;
};

// FUNCTIONS for the linked list toolkit
size_t list_length(const Node* head_ptr);
void list_head_insert(Node*& head_ptr, const Node::Item& entry);
void list_insert(Node* previous_ptr, const Node::Item& entry);
Node* list_search(Node* head_ptr, const Node::Item& target);
Node* list_locate(Node* head_ptr, size_t position);
void list_head_remove(Node*& head_ptr);
void list_remove(Node* previous_ptr);
void list_clear(Node*& head_ptr);
void list_copy(Node* source_ptr, Node*& head_ptr);
size_t list_occurrences(Node* head_ptr, const Node::Item& target);
void list_tail_attach(Node*& head_ptr, const Node::Item& entry);
void list_tail_remove(Node*& head_ptr);
Node* list_copy_front(Node* source_ptr, size_t n);
}

#endif

// end of CSCI361Proj5.h

// CSCI361Proj5.cpp

#include "CSCI361Proj5.h"

namespace FHSULINKEDLIST
{
/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: The value returned is the number of nodes in the linked
* list. The list itself is unaltered.
*/
size_t list_length(const Node* head_ptr)
{
// initialize count to 0
size_t count = 0;
// loop over the list pointed by head_ptr till the end of list, counting the number of nodes in the list
while(head_ptr != NULL)
{
count++;
head_ptr = head_ptr->link;
}

return count;
}

/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: A new node containing the given entry has been added at
* the head of the linked list; head_ptr now points to the head of the new,
* longer linked list.
*/
void list_head_insert(Node*& head_ptr, const Node::Item& entry)
{
// create a new Node with entry as data
Node* node = new Node;
node->data = entry;
node->link = head_ptr; // set link of node to head_ptr
head_ptr = node; // update head_ptr to node
}

/*
* Precondition: previous_ptr points to a node in a linked list.
* Postcondition: A new node containing the given entry has been added
* after the node that previous_ptr points to.
*/
void list_insert(Node* previous_ptr, const Node::Item& entry)
{
// create a new Node with entry as data
Node *node = new Node;
node->data = entry;
node->link = previous_ptr->link; // set link of node to link of previous_ptr
previous_ptr->link = node; // update link of previous_ptr to node
}

/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: The pointer returned points to the first node containing
* the specified target in its data member. If there is no such node, the
* null pointer is returned. The list itself is unaltered.
*/
Node* list_search(Node* head_ptr, const Node::Item& target)
{
Node* curr = head_ptr; // set curr to head_ptr
// loop over the list
while(curr != NULL)
{
if(curr->data == target) // target found, exit the loop
break;
curr = curr->link;
}

return curr; // return the curr node
}

/*
* Precondition: head_ptr is the head pointer of a linked list, and
* position > 0.
* Postcondition: The pointer returned points to the node at the specified
* position in the list. (The head node is position 1, the next node is
* position 2, and so on). If there is no such position, then the null
* pointer is returned. The list itself is unaltered.
*/
Node* list_locate(Node* head_ptr, size_t position)
{
Node* curr = head_ptr; // set curr to head_ptr
size_t curr_pos = 1; // set curr_pos to 1
// loop over the list till the end of list or till node at position has been reached
while(curr != NULL && curr_pos < position)
{
curr_pos++;
curr = curr->link;
}

return curr; // return the curr node
}

/*
* Precondition: head_ptr is the head pointer of a linked list, with at
* least one node.
* Postcondition: The head node has been removed and returned to the heap;
* head_ptr is now the head pointer of the new, shorter linked list.
*/
void list_head_remove(Node*& head_ptr)
{
Node *node = head_ptr; // set node to head_ptr
head_ptr = head_ptr->link; // update head_ptr to node next to head_ptr
// delete the node
node->link = NULL;
delete node;
node = NULL;
}

/*
* Precondition: previous_ptr points to a node in a linked list, and this
* is not the tail node of the list.
* Postcondition: The node after previous_ptr has been removed from the
* linked list.
*/
void list_remove(Node* previous_ptr)
{
// set node to node after previous_node
Node *node = previous_ptr->link;
previous_ptr->link = node->link; // update previous_ptr link to node after node
// delete node
node->link = NULL;
delete node;
node = NULL;
}

/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: All nodes of the list have been returned to the heap,
* and the head_ptr is now NULL.
*/
void list_clear(Node*& head_ptr)
{
// loop over the list pointed by head_ptr deleting head_ptr until the list is empty
while(head_ptr != NULL)
{
list_head_remove(head_ptr);
}
}

/*
* Precondition: source_ptr is the head pointer of a linked list.
* Postcondition: head_ptr is the head pointer for
* a new list that contains the same items as the list pointed to by
*/
void list_copy(Node* source_ptr, Node*& head_ptr)
{
list_clear(head_ptr); // delete the current list pointed by head_ptr

// set curr_src to head of source_ptr
Node* curr_src = source_ptr;
// set curr_head to head_ptr
Node* curr_head = head_ptr;

// loop over source_ptr list
while(curr_src != NULL)
{
if(curr_head == NULL) // head_ptr is empty, insert curr_src's data at head_ptr_
{
list_head_insert(head_ptr, curr_src->data);
curr_head = head_ptr; // set curr_head to head_ptr
}
else // head_ptr is not empty
{
list_insert(curr_head,curr_src->data);// insert curr_src's data after curr_head
curr_head = curr_head->link; // set curr_head to newly inserted node
}

curr_src = curr_src->link; // move curr_src to next node in source_ptr
}
}

/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: The return value is the count of the number of times
* target appears as the data portion of a node on the linked list.
* The linked list itself is unchanged.
*/
size_t list_occurrences(Node* head_ptr, const Node::Item& target)
{
size_t count = 0; // set count to 0
Node *curr = head_ptr; // set curr to head_ptr
// loop over the list, counting the number of times target is found in iist
while(curr != NULL)
{
if(curr->data == target)
count++;
curr = curr->link;
}

return count;
}

/*
* Precondition: head_ptr is the head pointer of a linked list.
* Postcondition: A new node containing the given entry has been added at
* the tail of the linked list; if this happens to be the first node of
* the linked list, then head_ptr now points to this node (otherwise
* head_ptr is unchanged).
*/
void list_tail_attach(Node*& head_ptr, const Node::Item& entry)
{
if(head_ptr == NULL) // empty list, insert entry at head
list_head_insert(head_ptr, entry);
else
{
// set curr to head_ptr
Node* curr = head_ptr;
// loop over the list to get the last node of the list
while(curr->link != NULL)
curr = curr->link;

// create a new node after the last node
curr->link = new Node;
curr->link->data = entry; // set its data to entry
curr->link->link = NULL; // set its link to NULL
}
}

/*
* Precondition: head_ptr is the head pointer of a linked list, with at
* least one node.
* Postcondition: The tail node has been removed and returned to the heap;
* if the list is now empty, then head_ptr is null; otherwise head_ptr
* is unchanged.
*/
void list_tail_remove(Node*& head_ptr)
{
if(head_ptr->link == NULL) // list contains only 1 node, call function to remove head
list_head_remove(head_ptr);
else
{
// set curr to head_ptr and pre to node previous of curr
Node* curr = head_ptr;
Node* prev = NULL;
// loop to get the last node in curr and second last node in prev
while(curr->link != NULL)
{
prev = curr;
curr = curr->link;
}

// set link of prev to NULL
prev->link = NULL;
// delete the curr node
delete(curr);
curr = NULL;
}
}

/*
* Precondition: source_ptr is the head pointer of a linked list
* Postcondition: The value returned is the head pointer for
* a new list that contains copies of the first n nodes from the list
* that source_ptr points to. If there less than n nodes in source list,
* just copy all nodes and done
*/
Node* list_copy_front(Node* source_ptr, size_t n)
{
Node* head_ptr = NULL; // set head_ptr to null
// if number of nodes in source_ptr <= n, copy entire source_ptr list to head_ptr
if(list_length(source_ptr) <= n)
{
list_copy(source_ptr, head_ptr);
}else
{
size_t count = 0; // set count to 0
Node* curr_src = source_ptr; // set curr_src to head of source_ptr
Node* curr_head = head_ptr; // set curr_head to head_ptr

// loop over the source_ptr inserting n nodes into head_ptr
while(count < n)
{
count++; // increment count
if(curr_head == NULL) // head_ptr is empty, set curr_src's data to head_ptr
{
list_head_insert(head_ptr, curr_src->data);
curr_head = head_ptr;
}
else // non-empty head_ptr, insert curr_src's data after curr_head
{
list_insert(curr_head, curr_src->data);
curr_head = curr_head->link; // set curr_head to the last node
}

curr_src = curr_src->link;
}
}

return head_ptr;
}
}

//end of CSCI361Proj5.cpp

// main.cpp
// This is the grader file of project 5

#include <iostream>
#include "CSCI361Proj5.h"

using namespace std;
using namespace FHSULINKEDLIST;

int test1(); // test list head insert, list head remove, list insert, list remove, list clear, and list length, 5 points
int test2(); // test list search, list occurrence and list located functions. 1 point
int test3(); // test list tail attach, and list tail remove functions 2 points
int test4(); // test list copy function, and list front copy front functions 2 point

int main()
{
int totalScore = 0;

cout <<"Let's see your grade. \n\n";
system("pause");
cout << endl;

int score = test1();
if(score == 0)
{
cout << "Basic insert function failed. No test will continue. Your score is 0.\n End testing program!\n";
system("pause");
return 0;
}

totalScore += score;
cout << "Your points so far is " << totalScore << "\n\n";
system("pause");
cout << endl;

score = test2();
if(score == 0)
cout << "Test 2 failed\n";
else
cout << "Test 2 passed\n";
totalScore += score;
cout << "Your points so far is " << totalScore << "\n\n";
system("pause");
cout << endl;

score = test3();
if(score == 0)
cout << "Test 3 failed\n";
else
cout << "Test 3 passed\n";
totalScore += score;
cout << "Your points so far is " << totalScore << "\n\n";
system("pause");
cout << endl;

score = test4();
if(score == 0)
cout << "Test 4 failed\n";
else
cout << "Test 4 passed\n";
totalScore += score;
cout << "Your points so far is " << totalScore << "\n\n";
system("pause");
cout << endl;

cout << "If you turn in your program to Dr. Zeng now, your will get " << totalScore << " out of 10\n";
cout << "Dr. Zeng will read your program, check your program style\n and decide if you will get 1 less point\n";

system("pause");
return 0;
}

int test1()
{
Node* list = NULL; // an empty list
list_head_insert(list, 0); // list contains one element 0;
if(list == NULL || list->data != 0 || list->link != NULL)
{
cout << "list_head_insert function doesn't work for empty list\n";
return 0;
}

list_head_insert(list, 1);
list_head_insert(list, 2); // now list contains 2, 1, 0
if(list->data != 2 || list->link->data != 1 || list->link->link->data != 0)
{
cout << "list_head_insert function doesn't work for non-empty list\n";
return 0;
}

cout << "list_head_insert function passes the test\n";

if(list_length(list) != 3)
{
cout << "list_length function is wrong\n";
return 0;
}

list_head_remove(list); // now list contains 1, 0
if(list->data != 1 || list->link->data != 0)
{
cout << "list_head_remove function doesn't work\n";
return 0;
}
list_head_remove(list);
list_head_remove(list); // now list is empty

if(list != NULL)
{
cout << "list_head_remove function doesn't work for one node list\n";
return 0;
}

if(list_length(list) != 0)
{
cout << "list_length function is wrong for empty list";
return 0;
}

cout << "list_head_remove passes the test\n";
cout << "list_length passes the test\n";

int i;
for(i = 1; i <= 10; i++)
list_head_insert(list, i);
// now list contains 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
list_clear(list);
if(list != NULL)
{
cout << "list_clear function is not correct\n";
return 0;
}
cout << "list_clear function passes the test\n";

list_head_insert(list, 1); // now list contains 1
for(i = 2; i <= 4; i++)
list_insert(list, i);
// now list contains 1, 4, 3, 2
if(list_length(list) != 4 || list->data != 1 || list->link->data != 4 || list->link->link->data != 3)
{
cout << "list_insert function is wrong\n";
return 0;
}

cout << "list_insert function passes the test\n";

Node* cursor = list->link; // cursor points to 4
list_remove(cursor); // now list contains 1, 4, 2
if(list_length(list) != 3 || list->data != 1 || list->link->data != 4 || list->link->link->data != 2)
{
cout << "list_remove function is wrong\n";
return 0;
}

cout << "list_remve function passes the test\n";

return 5;
}

int test2()
{
Node* list = NULL; // an empty linked list
int i;
for(i = 1; i <= 5; i++)
{
if(i%2 == 0)
list_head_insert(list, i-1);
else
list_head_insert(list, i);
} // now list contains 5, 3, 3, 1, 1

if(list_search(list, 2) != NULL)
{
cout << "list_search function doesn't work for not found case\n";
return 0;
}

if(list_search(list, 3) != list->link)
{
cout << "list_search function doesn't work for found case\n";
return 0;
}

cout << "list_search function passes the test\n";

if(list_occurrences(list, 3) != 2 || list_occurrences(list, 5) != 1 || list_occurrences(list, 2) != 0)
{
cout << "list_occurrences function doesn't work\n";
return 0;
}

cout << "list_occurrences function passes the test\n";

if(list_locate(list, 2) != list_search(list, 3) || list_locate(list, 6) != NULL)
{
cout << "list_locate function doesn't work\n";
return 0;
}

cout << "list_locate function passes the test\n";

return 1;
}

int test3() // test list tail attach, and list tail remove functions 2 points
{
Node* list = NULL; // an empty list
list_tail_attach(list, 0); // list contains one element 0;
if(list == NULL || list->data != 0 || list->link != NULL)
{
cout << "list_tail_attach function doesn't work for empty list\n";
return 0;
}

list_tail_attach(list, 1);
list_tail_attach(list, 2); // now list contains 0, 1, 2
if(list->data != 0 || list->link->data != 1 || list->link->link->data != 2)
{
cout << "list_tail_attach function doesn't work for non-empty list\n";
return 0;
}

cout << "list_tail_attach function passes the test\n";

list_tail_remove(list); // now list contains 0, 1
if(list->data != 0 || list->link->data != 1 || list_length(list) != 2)
{
cout << "list_head_remove function doesn't work\n";
return 0;
}

list_tail_remove(list);
list_tail_remove(list); // now list is empty

if(list != NULL)
{
cout << "list_tail_remove function doesn't work for one node list\n";
return 0;
}

cout << "list_tail_remove function passes the test\n";

return 2;

}

int test4()
{
Node* list = NULL; // an empty list
Node* copy = NULL;
copy = list_copy_front(list, 3);
if(copy != NULL)
{
cout << "list_copy_front function doesn't work for copying empty list\n";
return 0;
}
for(int i = 1; i <= 4; i++)
list_tail_attach(list, i);
// list contains 1, 2, 3, 4

copy = list_copy_front(list, 3);
if(list_length(copy) != 3 || copy->data != 1 || copy->link->data != 2 || copy->link->link->data != 3 )
{
cout << "list_copy_front function doesn't work\n";
return 0;
}

copy->link->data = 100;
if(list->link->data == 100)
{
cout << "list_copy_front function doesn't work.\n";
return 0;
}
list_clear(copy);
copy = list_copy_front(list, 6);
if(list_length(copy) != 4)
{
cout << "list_copy_front function doesn't work\n";
return 0;
}

cout << "list_copy_front passes the test\n";

list_clear(list);
for(int i = 1; i <= 3; i++)
list_head_insert(list, i);
// list contains 3, 2, 1

list_copy(list, copy);
if(list_length(copy) != 3 || copy->data != 3 || copy->link->data != 2 || copy->link->link->data != 1 )
{
cout << "list_copy function doesn't work\n";
return 0;
}

cout << "list_copy function passes the test\n";

return 2;

}

// end of main.cpp

Output: