Linked Lists and Binary Search Trees

Linked Lists and Binary Search Trees

In this assignment, you are to write and test C++ code as described below (use a separate program for each part).

Part 1

Let xHead, yHead and zHead be the head pointers of 3 linked lists of integers (called X-list, Y-list and Z-list, respectively, from here). X-list and Y-list are each sorted (in non-decreasing order) in itself and each may be empty. Z-list is initially empty (i.e., zHead initially contains the null pointer). Develop and test a recursive C++ function called SortedMergeRecur that combines the nodes in X-list and Y-list into Z-list such that, after calling the function, Z-list is a sorted list (in non-decreasing order) containing all the nodes initially contained in X-list and Y-list  –  X-list and Y-list should both be empty after the call.

Other specifications/requirements:

Each node of the list has the following structure:

struct Node
{
   int data;
   Node *link;
};

The function should:
Not use any global variables or static local variables.
Not use any looping constructs (for, while, do-while, …).
Be directly (not indirectly) recursive.
Not create any new nodes, destroy any existing nodes or copy/replace the data item of any node.
Not make temporary copies of the data involved using any other storage structures (arrays, stacks, queues, etc.).
Use (if ever needed) no more than a small number of pointers to hold certain link addresses.
Not make temporary copies of the entire list’s link addresses wholesale.
Z-list should be sorted at all times as it “grows” from an empty list to one that contains all the nodes originally contained in X-list and Y-list.
What this means is that you should not, for instance, attempt to first append all the nodes in X-list to Z-list, then append all the nodes in Y-list to Z-list, and finally use a sorting algorithm of some kind to sort the nodes in Z-list.
Your Tasks
Read the description thoroughly and carefully to understand exactly what SortedMergeRecur is meant to do and the IMPORTANT requirements you must meet when implementing the function.
Fill in the prototype for SortedMergeRecur in the supplied header file (llcpInt.h).
Fill in the definition for SortedMergeRecur in the supplied implementation file (llcpImp.cpp).
Test/debug your code using the supplied tester file (Assign06P1.cpp) and Makefile.
Do make to compile or re-compile.
Do make go (after successful compilation or re-compilation) to test with result output to terminal.
Program will (display some error messages and) abort on the first detection of an incorrect outcome (associated with a certain test case).
If the program hangs, it typically means your code has led to an infinite loop. Regardless, you should do Ctrl-c to get out of the hanged state.
If you need to identify which specific test case causes the program to hang or quit abruptly (“bomb out” due to segmentation fault, for instance), uncomment the DebugShowCase line (Line 77 in Assign06P1.cpp as supplied), then re-compile the program and re-run the test.
Do make gogo (after successful compilation or re-compilation) to test with result (excluding progress-logging messages) output to file (a6p1test.out).
(The a6p1test.out included in the Supplied Files was generated by compiling and running the program on the CS Linux server. Expect the test cases to be different if another system is used since the algorithm used for the pseudo-random number generator vary from system to system.)

Part 2

Complete the program (involving binary search tree and has some parts intentionally left out) contained in the supplied files.

Specific Requirements

The definition for binary search tree should be the one used in class (which is different than that adopted by the textbook authors).
Class definition: Textbook definition:
A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items: A BST is a binary tree that (if not empty) also follows two storage rules regarding its nodes’ items:
For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than the item in n For any node n of the tree, every item in n’s left subtree (LST), if not empty, is less than or equal the item in n
For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n For any node n of the tree, every item in n’s right subtree (RST), if not empty, is greater than the item in n
bst_insert must be iterative (NOTrecursive).
bst_remove and bst_remove_max must use the algorithm described by the textbook authors, appropriately adapted for the difference in tree definition above (and summarized in Slides 14 through 20 of Lecture Note 320BinarySearchTrees).
Your Tasks
In btNode.h: provide prototypes for bst_insert, bst_remove and bst_remove_max.
In btNode.cpp: provide definition (implementation) for bst_insert, bst_remove and bst_remove_max.
Test/debug your implementation with the help of the supplied Makefile:
Do make go (after successful compilation or re-compilation) to test with result output to terminal.
Program will (display some error messages and) abort on the first detection of an incorrect outcome (associated with a certain test case).
Do make gogo (after successful compilation or re-compilation) to test with result (excluding progress-logging messages) output to file (a6p2.out).
The sample output contained in the supplied files was generated by compiling and running the program on the CS Linux server. Expect the test cases to be different if another system is used since the algorithm used for the pseudo-random number generator vary from system to system.

Solution

 Assign06P1.cpp

 #include “llcpInt.h”

#include <iostream>

#include <cstdlib>

#include <ctime>

using namespace std;

voidSeedRand();

intBoundedRandomInt(intlowerBound, intupperBound);

intListLengthCheck(Node* head, intwhatItShouldBe);

bool match(Node* head, constintprocInts[], intprocSize);

voidShowArray(constint a[], int size);

voidDebugShowCase(intwhichCase, inttotalCasesToDo,

constint caseValues1[], int caseSize1,

constint caseValues2[], int caseSize2);

voidInsertSortedNonDec(int array[], int& used, intnewValue);

voidCombineSortedNonDec(constint array1[], constint array2[], int array3[],

int used1, int used2) ;

int main()

{

inttestCasesToDo = 990000,

testCasesDone = 0,

loSize = 0,

hiSize = 10,

loValue = -9,

hiValue = 9;

int used1,

used2,

used3,

intCount,

newInt,

iLenChk1;

int *intArr1 = 0,

*intArr2 = 0,

*intArr3 = 0;

Node *headX = 0,

*headY = 0,

*headZ = 0;

SortedMergeRecur(headX, headY, headZ);

cout<< “================================” <<endl;

if (headX == 0 &&headY == 0 &&headZ == 0)

cout<< “passed test on empty List X & Y” <<endl;

else

{

cout<< “failed test on empty List X & Y … 1 or more of the 3 lists  not empty” <<endl;

exit(EXIT_FAILURE);

}

// SeedRand(); // disabled for reproducible result

do

{

++testCasesDone;

used1 = BoundedRandomInt(loSize, hiSize);

used2 = BoundedRandomInt(loSize, hiSize);

used3 = used1 + used2;

if (used1 > 0) intArr1 = new int [used1];

if (used2 > 0) intArr2 = new int [used2];

if (used3 > 0) intArr3 = new int [used3];

intCount = 0;

while (intCount< used1)

{

newInt = BoundedRandomInt(loValue, hiValue);

InsertSortedNonDec(intArr1, intCount, newInt);

InsertSortedUp(headX, newInt);

}

intCount = 0;

while (intCount< used2)

{

newInt = BoundedRandomInt(loValue, hiValue);

InsertSortedNonDec(intArr2, intCount, newInt);

InsertSortedUp(headY, newInt);

}

CombineSortedNonDec(intArr1, intArr2, intArr3, used1, used2);

//DebugShowCase(testCasesDone, testCasesToDo, intArr1, used1, intArr2, used2);

SortedMergeRecur(headX, headY, headZ);

if (headX != 0 || headY != 0)

{

cout<< “ListX and/or ListY not empty …” <<endl;

cout<< “test_case – ListX: “;

ShowArray(intArr1, used1);

cout<< ”            ListY: “;

ShowArray(intArr2, used2);

exit(EXIT_FAILURE);

}

iLenChk1 = ListLengthCheck(headZ, used3);

if (iLenChk1 != 0)

{

if (iLenChk1 == -1)

{

cout<< “ListZ node-count error … too few” <<endl;

cout<< “test_case – ListX: “;

ShowArray(intArr1, used1);

cout<< ”            ListY: “;

ShowArray(intArr2, used2);

cout<< “#expected: ” << used3 <<endl;

cout<< “#returned: ” <<FindListLength(headZ) <<endl;

}

else

{

cout<< “ListZ node-count error … too many (circular list?)” <<endl;

cout<< “test_case – ListX: “;

ShowArray(intArr1, used1);

cout<< ”            ListY: “;

ShowArray(intArr2, used2);

cout<< “#expected: ” << used3 <<endl;

cout<< “returned # is higher (may be infinite)” <<endl;

}

exit(EXIT_FAILURE);

}

if ( !match(headZ, intArr3, used3) )

{

cout<< “List Z Contents error … mismatch found in value or order” <<endl;

cout<< “initial X: “;

ShowArray(intArr1, used1);

cout<< “initial Y: “;

ShowArray(intArr2, used2);

cout<< “ought2b Z: “;

ShowArray(intArr3, used3);

cout<< “outcome Z: “;

ShowAll(cout, headZ);

exit(EXIT_FAILURE);

}

if (testCasesDone<= 5 || testCasesDone % 45000 == 0)

{

cout<< “================================” <<endl;

clog<< “testing case ” <<testCasesDone

<<” of ” <<testCasesToDo<<endl;

clog<< “================================” <<endl;

cout<< “test case ” <<testCasesDone

<<” of ” <<testCasesToDo<<endl;

cout<< “initial X: “;

ShowArray(intArr1, used1);

cout<< “initial Y: “;

ShowArray(intArr2, used2);

cout<< “ought2b Z: “;

ShowArray(intArr3, used3);

cout<< “outcome Z: “;

ShowAll(cout, headZ);

}

ListClear(headX, 1); // in case not empty

ListClear(headY, 1); // in case not empty

ListClear(headZ, 1);

delete [] intArr1;

delete [] intArr2;

delete [] intArr3;

intArr1 = intArr2 = intArr3 = 0;

}

while (testCasesDone<testCasesToDo);

cout<< “================================” <<endl;

cout<< “test program terminated normally” <<endl;

cout<< “================================” <<endl;

return EXIT_SUCCESS;

}

/////////////////////////////////////////////////////////////////////

// Function to seed the random number generator

// PRE:  none

// POST: The random number generator has been seeded.

/////////////////////////////////////////////////////////////////////

voidSeedRand()

{

srand( (unsigned) time(NULL) );

}

/////////////////////////////////////////////////////////////////////

// Function to generate a random integer between

// lowerBound and upperBound (inclusive)

// PRE:  lowerBound is a positive integer.

//       upperBound is a positive integer.

//       upperBound is larger than lowerBound

//       The random number generator has been seeded.

// POST: A random integer between lowerBound and upperBound

//       has been returned.

/////////////////////////////////////////////////////////////////////

intBoundedRandomInt(intlowerBound, intupperBound)

{

return ( rand() % (upperBound – lowerBound + 1) ) + lowerBound;

}

/////////////////////////////////////////////////////////////////////

// Function to check # of nodes in list against what it should be

// POST: returns

//          -1 if # of nodes is less than what it should be

//           0 if # of nodes is equal to  what it should be

//           1 if # of nodes is more than what it should be

/////////////////////////////////////////////////////////////////////

intListLengthCheck(Node* head, intwhatItShouldBe)

{

int length = 0;

while (head != 0)

{

++length;

if (length >whatItShouldBe) return 1;

head = head->link;

}

return (length <whatItShouldBe) ? -1 : 0;

}

bool match(Node* head, constintprocInts[], intprocSize)

{

intiProc = 0;

while (head != 0)

{

if (iProc == procSize) return false;

if (head->data != procInts[iProc]) return false;

++iProc;

head = head->link;

}

return true;

}

voidShowArray(constint a[], int size)

{

for (int i = 0; i < size; ++i)

cout<< a[i] << ”  “;

cout<<endl;

}

voidDebugShowCase(intwhichCase, inttotalCasesToDo,

constint caseValues1[], int caseSize1,

constint caseValues2[], int caseSize2)

{

cout<< “test case ” <<whichCase

<<” of ” <<totalCasesToDo<<endl;

cout<< “given X: “;

ShowArray(caseValues1, caseSize1);

cout<< “given Y: “;

ShowArray(caseValues2, caseSize2);

}

voidInsertSortedNonDec(int array[], int& used, intnewValue)

{

intprobeIndex = used;

while (probeIndex> 0 && array[probeIndex – 1] >newValue)

{

array[probeIndex] = array[probeIndex – 1];

–probeIndex;

}

array[probeIndex] = newValue;

++used;

}

voidCombineSortedNonDec(constint array1[], constint array2[], int array3[],

int used1, int used2)

{

int array1Index = 0, array2Index = 0, array3Index = 0;

while (array1Index < used1 && array2Index < used2)

{

if (array1[array1Index] < array2[array2Index])

array3[array3Index++] = array1[array1Index++];

else

array3[array3Index++] = array2[array2Index++];

}

while (array1Index < used1)

array3[array3Index++] = array1[array1Index++];

while (array2Index < used2)

array3[array3Index++] = array2[array2Index++];

}

llcpImp.cpp

#include <iostream>

#include <cstdlib>

#include “llcpInt.h”

using namespace std;

intFindListLength(Node* headPtr) {

int length = 0;

while (headPtr != 0) {

++length;

headPtr = headPtr->link;

}

return length;

}

boolIsSortedUp(Node* headPtr) {

if (headPtr == 0 || headPtr->link == 0) // empty or 1-node

return true;

while (headPtr->link != 0) // not at last node

{

if (headPtr->link->data <headPtr->data)

return false;

headPtr = headPtr->link;

}

return true;

}

voidInsertAsHead(Node*&headPtr, int value) {

Node *newNodePtr = new Node;

newNodePtr->data = value;

newNodePtr->link = headPtr;

headPtr = newNodePtr;

}

voidInsertAsTail(Node*&headPtr, int value) {

Node *newNodePtr = new Node;

newNodePtr->data = value;

newNodePtr->link = 0;

if (headPtr == 0)

headPtr = newNodePtr;

else {

Node *cursor = headPtr;

while (cursor->link != 0) // not at last node

cursor = cursor->link;

cursor->link = newNodePtr;

}

}

voidInsertSortedUp(Node*&headPtr, int value) {

Node *precursor = 0, *cursor = headPtr;

while (cursor != 0 && cursor->data < value) {

precursor = cursor;

cursor = cursor->link;

}

Node *newNodePtr = new Node;

newNodePtr->data = value;

newNodePtr->link = cursor;

if (cursor == headPtr)

headPtr = newNodePtr;

else

precursor->link = newNodePtr;

///////////////////////////////////////////////////////////

/* using-only-cursor (no precursor) version

Node *newNodePtr = new Node;

newNodePtr->data = value;

//newNodePtr->link = 0;

//if (headPtr == 0)

//   headPtr = newNodePtr;

//else if (headPtr->data >= value)

//{

//   newNodePtr->link = headPtr;

//   headPtr = newNodePtr;

//}

if (headPtr == 0 || headPtr->data >= value)

{

newNodePtr->link = headPtr;

headPtr = newNodePtr;

}

//else if (headPtr->link == 0)

//   head->link = newNodePtr;

else

{

Node *cursor = headPtr;

while (cursor->link != 0 && cursor->link->data < value)

cursor = cursor->link;

//if (cursor->link != 0)

//   newNodePtr->link = cursor->link;

newNodePtr->link = cursor->link;

cursor->link = newNodePtr;

}

////////////////// commented lines removed //////////////////

Node *newNodePtr = new Node;

newNodePtr->data = value;

if (headPtr == 0 || headPtr->data >= value)

{

newNodePtr->link = headPtr;

headPtr = newNodePtr;

}

else

{

Node *cursor = headPtr;

while (cursor->link != 0 && cursor->link->data < value)

cursor = cursor->link;

newNodePtr->link = cursor->link;

cursor->link = newNodePtr;

}

*/

///////////////////////////////////////////////////////////

}

boolDelFirstTargetNode(Node*&headPtr, int target) {

Node *precursor = 0, *cursor = headPtr;

while (cursor != 0 && cursor->data != target) {

precursor = cursor;

cursor = cursor->link;

}

if (cursor == 0) {

cout<< target << ” not found.” <<endl;

return false;

}

if (cursor == headPtr) //OR precursor == 0

headPtr = headPtr->link;

else

precursor->link = cursor->link;

delete cursor;

return true;

}

bool DelNodeBefore1stMatch(Node*&headPtr, int target) {

if (headPtr == 0 || headPtr->link == 0 || headPtr->data == target)

return false;

Node *cur = headPtr->link, *pre = headPtr, *prepre = 0;

while (cur != 0 && cur->data != target) {

prepre = pre;

pre = cur;

cur = cur->link;

}

if (cur == 0)

return false;

if (cur == headPtr->link) {

headPtr = cur;

delete pre;

} else {

prepre->link = cur;

delete pre;

}

return true;

}

voidShowAll(ostream& outs, Node* headPtr) {

while (headPtr != 0) {

outs<<headPtr->data << ”  “;

headPtr = headPtr->link;

}

outs<<endl;

}

voidFindMinMax(Node* headPtr, int&minValue, int&maxValue) {

if (headPtr == 0) {

cerr<< “FindMinMax() attempted on empty list” <<endl;

cerr<< “Minimum and maximum values not set” <<endl;

} else {

minValue = maxValue = headPtr->data;

while (headPtr->link != 0) {

headPtr = headPtr->link;

if (headPtr->data <minValue)

minValue = headPtr->data;

else if (headPtr->data >maxValue)

maxValue = headPtr->data;

}

}

}

doubleFindAverage(Node* headPtr) {

if (headPtr == 0) {

cerr<< “FindAverage() attempted on empty list” <<endl;

cerr<< “An arbitrary zero value is returned” <<endl;

return 0.0;

} else {

int sum = 0, count = 0;

while (headPtr != 0) {

++count;

sum += headPtr->data;

headPtr = headPtr->link;

}

return double(sum) / count;

}

}

voidListClear(Node*&headPtr, intnoMsg) {

int count = 0;

Node *cursor = headPtr;

while (headPtr != 0) {

headPtr = headPtr->link;

delete cursor;

cursor = headPtr;

++count;

}

if (noMsg)

return;

clog<< “Dynamic memory for ” << count << ” nodes freed” <<endl;

}

// definition of SortedMergeRecur

voidSortedMergeRecur(Node*& x, Node*& y, Node*& z) {

if (x == 0 && y == 0) // if bothe empty, stop

return;

else {

// to insert at end

Node* toInsert = NULL;

// if x is not null and y is null or x is not greater than y

if (x!= 0 && (y == 0 || x->data <= y->data)) {

toInsert = x;

x = x->link;

} else { //if x is null or y is not greater than x

toInsert = y;

y = y->link;

}

// if inserting into empty list

if (z == 0) {

// set z

z = toInsert;

toInsert->link = 0;

SortedMergeRecur(x, y, z);

} else {

// get reference to last element

Node* prev = z;

// insert

z->link = toInsert;

toInsert->link = 0;

// merge sort

SortedMergeRecur(x, y, z->link);

// restore z to previous

z = prev;

}

}

}

llcpInt.h 

#ifndef LLCP_INT_H

#define LLCP_INT_H

#include <iostream>

struct Node

{

int data;

Node *link;

};

intFindListLength(Node* headPtr);

boolIsSortedUp(Node* headPtr);

voidInsertAsHead(Node*&headPtr, int value);

voidInsertAsTail(Node*&headPtr, int value);

voidInsertSortedUp(Node*&headPtr, int value);

boolDelFirstTargetNode(Node*&headPtr, int target);

bool   DelNodeBefore1stMatch(Node*&headPtr, int target);

voidShowAll(std::ostream& outs, Node* headPtr);

voidFindMinMax(Node* headPtr, int&minValue, int&maxValue);

doubleFindAverage(Node* headPtr);

voidListClear(Node*&headPtr, intnoMsg = 0);

// prototype of SortedMergeRecur

voidSortedMergeRecur(Node*& x, Node*& y, Node*& z);

#endif