Header file using namespace std;

template // Forward declaration of the List class class List;

template class ListNode // Facilitator class for the List class { private:

// Constructor ListNode(const DT& initData, ListNode* nextPtr);

// Data members DT dataItem; // List data item ListNode* next; // Pointer to the next list node

friend class List

; };

//--------------------------------------------------------------------

template class List { public:

// Constructor List();

// Destructor ~List();

// List manipulation functions void insert(const DT& newData); // Insert after cursor void clear(); // Clear list

// Output the list structure -- used in testing/debugging void showStructure() const;

// functions for getting recursive things going void write() const; // Output list data items void insertEnd(const DT& newData); // Insert at end void aBeforeb(); // In-lab Exercise 3

private:

// Recursive partners of the Prelab functions void writeSub(ListNode

* p) const; void insertEndSub(ListNode

*& p, const DT& newElement);

// Recursive partners of the In-lab functions void aBeforebSub(ListNode

*& p); // In-lab Exercise 3

private:

// Data members ListNode

* head; // Pointer to the beginning of the list ListNode

* cursor; // Cursor pointer };

//-------------------------------------------------------------------- // // Laboratory 8 listrec.cpp // // SOLUTION: Partial linked list implementation of the List ADT // with additional recursive linked list functions // //--------------------------------------------------------------------

//-------------------------------------------------------------------- // // Uses parts of the singly linked list implementation // (from Laboratory 6): // // - The ListNode class constructor // // - The List class constructor, destructor, insert(), clear(), and // showstructure() functions. // //--------------------------------------------------------------------

template ListNode

::ListNode(const DT& nodeDataItem, ListNode

* nextPtr)

// Creates a list node containing item elem and next pointer // nextPtr.

: dataItem(nodeDataItem), next(nextPtr) {}

//--------------------------------------------------------------------

template List

::List() // Creates an empty list. The argument is included for compatibility // with the array implementation and is ignored.

: head(0), cursor(0) {}

//--------------------------------------------------------------------

template List

:: ~List()

// Frees the memory used by a list.

{ clear(); }

//--------------------------------------------------------------------

template void List

::insert(const DT& newDataItem)

// Inserts newDataItem after the cursor. If the list is empty, then // newDataItem is inserted as the first (and only) data item in the // list. In either case, moves the cursor to newDataItem.

{ if (head == 0) // Empty list { head = new ListNode

(newDataItem, 0); cursor = head; } else // After cursor { cursor->next = new ListNode

(newDataItem, cursor->next); cursor = cursor->next; } }

//--------------------------------------------------------------------

template void List

::clear()

// Removes all the data items from a list.

{ ListNode

* p, // Points to successive nodes * nextP; // Points to next node p = head; while (p != 0) { nextP = p->next; delete p; p = nextP; }

head = 0; cursor = 0; }

//--------------------------------------------------------------------

template void List

::showStructure() const

// Outputs the data items in a list. If the list is empty, outputs // "Empty list". This operation is intended for testing and // debugging purposes only.

{ ListNode

* p; // Iterates through the list

if (head == 0) cout next) if (p == cursor) cout dataItem dataItem

//-------------------------------------------------------------------- // // Recursively implemented linked list functions used in the Prelab // Exercise // //--------------------------------------------------------------------

template void List

::write() const

// Outputs the data items in a list from beginning to end. Assumes that // objects of type DT can be output to the cout stream.

{ cout

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template void List

::writeSub(ListNode

* p) const

// Recursive partner of the write() function. Processes the sublist // that begins with the node pointed to by p.

{ if (p != 0) { cout dataItem; // Output data item writeSub(p->next); // Continue with next node

} }

//--------------------------------------------------------------------

template void List

::insertEnd(const DT& newDataItem)

// Inserts newDataItem at the end of a list. Moves the cursor to // newDataItem.

{ insertEndSub(head, newDataItem); }

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template void List

::insertEndSub(ListNode

*& p, const DT& newDataItem)

// Recursive partner of the insertEnd() function. Processes the // sublist that begins with the node pointed to by p.

{ if (p != 0) insertEndSub(p->next, newDataItem); // Continue searching for else // end of list { p = new ListNode

(newDataItem, 0); // Insert new node cursor = p; // Move cursor } }

//--------------------------------------------------------------------

template void List

::aBeforeb()

// Inserts an data item containing 'a' before each data item // containing 'b'. //The sole purpose of this function is to call aBeforebSub and //send the head as an argument. //ie. only one line of code is necessary here.

{ // add code here to call aBeforebSub()

}

// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

template void List

::aBeforebSub(ListNode

*& p)

// Recursive partner of the aBeforeb() function. Processes the sublist // that begins with the node pointed to by p.

{ //add code here to complete the function

}

• Your primary tasks for this exercise are:

  1. Alter the writeSub() function so that it prints the list in reverse.

  Steps include:

• Try to run this program. You should get the prompt: Enter a list of characters :

  Now, type "abc" and enter. You will get the following output:

  Enter a list of characters : abc a b [c] List : abc List : abc! a b c [!] Press any key to continue 

• Now, modify the writeSub() function (in the listrec.h file) so that it prints in reverse. Build and Run your program, you should get the following output:

  Enter a list of characters : abc a b [c] List : cba List : !cba a b c [!] Press any key to continue 

  Hint: If you don't get this output, try Rebuild All from the Build Menu.

• Next, create a new recursive function that will insert the character 'a' immediately before each occurence of the character 'b'. The cursor will not change.
  • add code in the listrec.h file for aBeforeb() and aBeforebSub(). The function prototypes exist, you have to add code to get them running.

• Activate the call to the aBeforeb() function (in the recursion.cpp file) by uncommenting the lines: // testList.aBeforeb(); // testList.showStructure();

• Build and run the executable. Your output will look like this:

  Enter a list of characters : abc a b [c] List : cba List : !cba a a b c [!] Press any key to continue 

• Prepare a test plan for this function that includes list containing the character 'b' at the beginning, middle, and end. A test plan form follows.

• Execute your test plan. If you discover mistakes in your implementation of the aBeforeb() function, correct them and execute your test plan again.

Test Plan for the aBeforeb Operation

Test Case	List	Expected Result	Checked
b in beginning
b in middle
b at end
multiple b's

1 x maino - + Solution Explorer to-$a Search Solution Explorer (Ctrl+;) Solution 'Project2' (1 of 1 project) 1 Project2 - References External Dependencies Header Files listrec.h Resource Files Source Files ++ recursion.cpp recursion.cpp* + x listrec.h* Project2 (Global Scope) 11 12 #include 13 #include "listrec.h" 14 using namespace std; 15 16 Elint main() 17 { 18 List testList; // Test list 19 char testData; // List data element 20 21 cout Search Solution Explorer (Ctrl+;) Solution 'Project2' (1 of 1 project) 1 Project2 - References External Dependencies Header Files listrec.h Resource Files Source Files ++ recursion.cpp recursion.cpp* + x listrec.h* Project2 (Global Scope) 11 12 #include 13 #include "listrec.h" 14 using namespace std; 15 16 Elint main() 17 { 18 List testList; // Test list 19 char testData; // List data element 20 21 cout