Applications of linked lists and binary search trees

Linked Lists and Binary Search Trees

Solution

 Assign06P1.cpp

 #include “llcpInt.h”

#include

#include

#include

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<< “================================” <

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

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

else

{

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

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 …” <

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” <

cout<< “test_case – ListX: “;

ShowArray(intArr1, used1);

cout<< ” ListY: “;

ShowArray(intArr2, used2);

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

cout<< “#returned: ” <

}

else

{

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

cout<< “test_case – ListX: “;

ShowArray(intArr1, used1);

cout<< ” ListY: “;

ShowArray(intArr2, used2);

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

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

}

exit(EXIT_FAILURE);

}

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

{

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

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<< “================================” <

clog<< “testing case ” <

<<” of ” <

clog<< “================================” <

cout<< “test case ” <

<<” of ” <

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

cout<< “================================” <

cout<< “test program terminated normally” <

cout<< “================================” <

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

}

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<

}

voidDebugShowCase(intwhichCase, inttotalCasesToDo,

constint caseValues1[], int caseSize1,

constint caseValues2[], int caseSize2)

{

cout<< “test case ” <

<<” of ” <

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

#include

#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 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.” <

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<data << ” “;

headPtr = headPtr->link;

}

outs<

}

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

if (headPtr == 0) {

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

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

} else {

minValue = maxValue = headPtr->data;

while (headPtr->link != 0) {

headPtr = headPtr->link;

if (headPtr->data

minValue = headPtr->data;

else if (headPtr->data >maxValue)

maxValue = headPtr->data;

}

}

}

doubleFindAverage(Node* headPtr) {

if (headPtr == 0) {

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

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

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” <

}

// 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

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