Fill in the linked-list processing function InterleaveOddsAndEvensInOrigOrder fr
ID: 3918020 • Letter: F
Question
Fill in the linked-list processing function InterleaveOddsAndEvensInOrigOrder from the given file, that is to process a given linked list as follows.
Any nodes (may be odd-valued or even-valued) in the given list that cannot be interleaved (because there are no more "partners" left) should appear as the tail portion of the processed list AND in the same order as they appear in the given list.
(The a5p1test.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.)
Given file 1:
llcpImp.cpp
#include <iostream>
#include <cstdlib>
#include "llcpInt.h"
using namespace std;
int FindListLength(Node* headPtr)
{
int length = 0;
while (headPtr != 0)
{
++length;
headPtr = headPtr->link;
}
return length;
}
bool IsSortedUp(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;
}
void InsertAsHead(Node*& headPtr, int value)
{
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = headPtr;
headPtr = newNodePtr;
}
void InsertAsTail(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;
}
}
void InsertSortedUp(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;
}
*/
///////////////////////////////////////////////////////////
}
bool DelFirstTargetNode(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;
}
void ShowAll(ostream& outs, Node* headPtr)
{
while (headPtr != 0)
{
outs << headPtr->data << " ";
headPtr = headPtr->link;
}
outs << endl;
}
void FindMinMax(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;
}
}
}
double FindAverage(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;
}
}
void ListClear(Node*& headPtr, int noMsg)
{
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 InterleaveOddsAndEvensInOrigOrder
Given file 2:
llcpInt.h
#ifndef LLCP_INT_H
#define LLCP_INT_H
#include <iostream>
struct Node
{
int data;
Node *link;
};
int FindListLength(Node* headPtr);
bool IsSortedUp(Node* headPtr);
void InsertAsHead(Node*& headPtr, int value);
void InsertAsTail(Node*& headPtr, int value);
void InsertSortedUp(Node*& headPtr, int value);
bool DelFirstTargetNode(Node*& headPtr, int target);
bool DelNodeBefore1stMatch(Node*& headPtr, int target);
void ShowAll(std::ostream& outs, Node* headPtr);
void FindMinMax(Node* headPtr, int& minValue, int& maxValue);
double FindAverage(Node* headPtr);
void ListClear(Node*& headPtr, int noMsg = 0);
// prototype of InterleaveOddsAndEvensInOrigOrder of Assignment 5 Part 1
#endif
Given file 3:
Assign05P1.cpp
#include "llcpInt.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void SeedRand();
int BoundedRandomInt(int lowerBound, int upperBound);
int ListLengthCheck(Node* head, int whatItShouldBe);
bool match(Node* head, const int procInts[], int procSize);
void ShowArray(const int a[], int size);
void DebugShowCase(int whichCase, int totalCasesToDo,
const int caseValues[], int caseSize);
int main()
{
int testCasesToDo = 750000,
testCasesDone = 0,
loSize = 1,
hiSize = 25,
loValue = 0,
hiValue = 9;
int numInts,
numOdds,
numEvens,
intCount,
newInt,
iLenChk,
iOdd,
iEven,
iProc;
int *rawInts = 0,
*procInts = 0,
*rawOddInts = 0,
*rawEvenInts = 0;
Node* head = 0;
InterleaveOddsAndEvensInOrigOrder(head);
cout << "================================" << endl;
cout << "passed crash test on empty list" << endl;
// SeedRand(); // disabled for reproducible result
do
{
++testCasesDone;
numInts = BoundedRandomInt(loSize, hiSize);
numOdds = numEvens = 0;
rawInts = new int [numInts];
procInts = new int [numInts];
rawOddInts = new int [numInts];
rawEvenInts = new int [numInts];
intCount = 0;
while (intCount < numInts)
{
newInt = BoundedRandomInt(loValue, hiValue);
rawInts[intCount++] = newInt;
if (newInt % 2)
rawOddInts[numOdds++] = newInt;
else
rawEvenInts[numEvens++] = newInt;
InsertAsTail(head, newInt);
}
iOdd = iEven = iProc = 0;
if (rawInts[0] % 2)
{
while (iProc < numInts)
{
if (iOdd < numOdds)
procInts[iProc++] = rawOddInts[iOdd++];
if (iEven < numEvens)
procInts[iProc++] = rawEvenInts[iEven++];
}
}
else
{
while (iProc < numInts)
{
if (iEven < numEvens)
procInts[iProc++] = rawEvenInts[iEven++];
if (iOdd < numOdds)
procInts[iProc++] = rawOddInts[iOdd++];
}
}
// DebugShowCase(testCasesDone, testCasesToDo, rawInts, numInts);
InterleaveOddsAndEvensInOrigOrder(head);
iLenChk = ListLengthCheck(head, numInts);
if (iLenChk != 0)
{
if (iLenChk == -1)
{
cout << "Node-count error ... too few" << endl;
cout << "test_case: ";
ShowArray(rawInts, numInts);
cout << "#expected: " << numInts << endl;
cout << "#returned: " << FindListLength(head) << endl;
}
else
{
cout << "Node-count error ... too many (circular list?)" << endl;
cout << "test_case: ";
ShowArray(rawInts, numInts);
cout << "#expected: " << numInts << endl;
cout << "returned # is higher (may be infinite)" << endl;
}
exit(EXIT_FAILURE);
}
if (! match(head, procInts, numInts) )
{
cout << "Contents error ... mismatch found in value or order" << endl;
cout << "initial: ";
ShowArray(rawInts, numInts);
cout << "ought2b: ";
ShowArray(procInts, numInts);
cout << "outcome: ";
ShowAll(cout, head);
exit(EXIT_FAILURE);
}
if (testCasesDone % 10000 == 0)
{
cout << "================================" << endl;
clog << "testing case " << testCasesDone
<< " of " << testCasesToDo << endl;
clog << "================================" << endl;
// cout << "test case " << testCasesDone
// << " of " << testCasesToDo << endl;
cout << "initial: ";
ShowArray(rawInts, numInts);
cout << "ought2b: ";
ShowArray(procInts, numInts);
cout << "outcome: ";
ShowAll(cout, head);
}
ListClear(head, 1);
delete [] rawInts;
delete [] procInts;
delete [] rawOddInts;
delete [] rawEvenInts;
rawInts = procInts = rawOddInts = rawEvenInts = 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.
/////////////////////////////////////////////////////////////////////
void SeedRand()
{
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.
/////////////////////////////////////////////////////////////////////
int BoundedRandomInt(int lowerBound, int upperBound)
{
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
/////////////////////////////////////////////////////////////////////
int ListLengthCheck(Node* head, int whatItShouldBe)
{
int length = 0;
while (head != 0)
{
++length;
if (length > whatItShouldBe) return 1;
head = head->link;
}
return (length < whatItShouldBe) ? -1 : 0;
}
bool match(Node* head, const int procInts[], int procSize)
{
int iProc = 0;
while (head != 0)
{
if (iProc == procSize) return false;
if (head->data != procInts[iProc]) return false;
++iProc;
head = head->link;
}
return true;
}
void ShowArray(const int a[], int size)
{
for (int i = 0; i < size; ++i)
cout << a[i] << " ";
cout << endl;
}
void DebugShowCase(int whichCase, int totalCasesToDo,
const int caseValues[], int caseSize)
{
cout << "test case " << whichCase
<< " of " << totalCasesToDo << endl;
cout << "given list: ";
ShowArray(caseValues, caseSize);
}
make file:
llcp: llcpImp.o Assign05P1.o
g++ llcpImp.o Assign05P1.o -o a5p1
llcpImp.o: llcpImp.cpp llcpInt.h
g++ -Wall -ansi -pedantic -std=c++11 -c llcpImp.cpp
Assign05P1.o: Assign05P1.cpp llcpInt.h
g++ -Wall -ansi -pedantic -std=c++11 -c Assign05P1.cpp
go:
./a5p1
gogo:
./a5p1 > a5p1test.out
clean:
@rm -rf llcpImp.o Assign05P1.o
cleanall:
@rm -rf llcpImp.o Assign05P1.o a5p1
correct output should look like:
================================
passed crash test on empty list
================================
initial: 1 0 2 2 5 1 0 0 5 3 5 0 4 5 0 3 4 1 2 3 1
ought2b: 1 0 5 2 1 2 5 0 3 0 5 0 5 4 3 0 1 4 3 2 1
outcome: 1 0 5 2 1 2 5 0 3 0 5 0 5 4 3 0 1 4 3 2 1
================================
initial: 6 1 8 6 5 3 3 9 5 8 1 0 6 2 3 0 5 1 1
ought2b: 6 1 8 5 6 3 8 3 0 9 6 5 2 1 0 3 5 1 1
outcome: 6 1 8 5 6 3 8 3 0 9 6 5 2 1 0 3 5 1 1
================================
initial: 9 5 1 0 6 4 3 6 0 2 0 6 2 8 5 7 3 1 7 2 6 6 7 9
ought2b: 9 0 5 6 1 4 3 6 5 0 7 2 3 0 1 6 7 2 7 8 9 2 6 6
outcome: 9 0 5 6 1 4 3 6 5 0 7 2 3 0 1 6 7 2 7 8 9 2 6 6
================================
initial: 3 1 1 1
ought2b: 3 1 1 1
outcome: 3 1 1 1
================================
initial: 2 2 1
ought2b: 2 1 2
outcome: 2 1 2
================================
initial: 8 4 3 9 3
ought2b: 8 3 4 9 3
outcome: 8 3 4 9 3
================================
initial: 9 0 0 8 9 3 6 5 7 6 1 4 5 5 2 7 3 3 1 7 4
ought2b: 9 0 9 0 3 8 5 6 7 6 1 4 5 2 5 4 7 3 3 1 7
outcome: 9 0 9 0 3 8 5 6 7 6 1 4 5 2 5 4 7 3 3 1 7
================================
initial: 5 5 2 8 4 3 8 7 7 3 5 6 7 9 4 9 6 4 4 8 3 7 5 7 2
ought2b: 5 2 5 8 3 4 7 8 7 6 3 4 5 6 7 4 9 4 9 8 3 2 7 5 7
outcome: 5 2 5 8 3 4 7 8 7 6 3 4 5 6 7 4 9 4 9 8 3 2 7 5 7
================================
initial: 7 0 0 9 1 9 6 4 1 0 3 2 4
ought2b: 7 0 9 0 1 6 9 4 1 0 3 2 4
outcome: 7 0 9 0 1 6 9 4 1 0 3 2 4
================================
initial: 1 5
ought2b: 1 5
outcome: 1 5
================================
initial: 6 1 0 8 8 3 3 0
ought2b: 6 1 0 3 8 3 8 0
outcome: 6 1 0 3 8 3 8 0
================================
initial: 2 1 1
ought2b: 2 1 1
outcome: 2 1 1
================================
initial: 0 7
ought2b: 0 7
outcome: 0 7
================================
initial: 0 9 1 0 3 3 0 4 5 4 6 0 5 6 4 7
ought2b: 0 9 0 1 0 3 4 3 4 5 6 5 0 7 6 4
outcome: 0 9 0 1 0 3 4 3 4 5 6 5 0 7 6 4
================================
initial: 5 2 5 2 1 1 0 8 4 7 3 7 0 6 0 9 7 4 0 1 1 4 1 6
ought2b: 5 2 5 2 1 0 1 8 7 4 3 0 7 6 9 0 7 4 1 0 1 4 1 6
outcome: 5 2 5 2 1 0 1 8 7 4 3 0 7 6 9 0 7 4 1 0 1 4 1 6
================================
initial: 8 6 8 0 4 8 6 9 8 7 6 8 6 1
ought2b: 8 9 6 7 8 1 0 4 8 6 8 6 8 6
outcome: 8 9 6 7 8 1 0 4 8 6 8 6 8 6
================================
initial: 9 4 1 2 6 0 2 9 1 4 0 8 4 6 5 9 3 1
ought2b: 9 4 1 2 9 6 1 0 5 2 9 4 3 0 1 8 4 6
outcome: 9 4 1 2 9 6 1 0 5 2 9 4 3 0 1 8 4 6
================================
initial: 2 4 1 2 8 4 1 8 1 6 2 8 3 6 8 0
ought2b: 2 1 4 1 2 1 8 3 4 8 6 2 8 6 8 0
outcome: 2 1 4 1 2 1 8 3 4 8 6 2 8 6 8 0
================================
initial: 6 9 1 3 3 7 5 2 3
ought2b: 6 9 2 1 3 3 7 5 3
outcome: 6 9 2 1 3 3 7 5 3
================================
initial: 4 1 0 9 3 2 7 8 8 2 9 4 8 7 3 3 3 0 7 1 9 7
ought2b: 4 1 0 9 2 3 8 7 8 9 2 7 4 3 8 3 0 3 7 1 9 7
outcome: 4 1 0 9 2 3 8 7 8 9 2 7 4 3 8 3 0 3 7 1 9 7
================================
initial: 3 3 8 2 4 8 3 3 8 8 9 3 2 6 5 3 9 7 8
ought2b: 3 8 3 2 3 4 3 8 9 8 3 8 5 2 3 6 9 8 7
outcome: 3 8 3 2 3 4 3 8 9 8 3 8 5 2 3 6 9 8 7
================================
initial: 7 6 1 8 0 2 4 2 5 9
ought2b: 7 6 1 8 5 0 9 2 4 2
outcome: 7 6 1 8 5 0 9 2 4 2
================================
initial: 0 4 9 3 1
ought2b: 0 9 4 3 1
outcome: 0 9 4 3 1
================================
initial: 9 4 1 6 3 3 4 2 1 4 9 7 1 1 7 4 2 0 7 3 9 4 7 1 5
ought2b: 9 4 1 6 3 4 3 2 1 4 9 4 7 2 1 0 1 4 7 7 3 9 7 1 5
outcome: 9 4 1 6 3 4 3 2 1 4 9 4 7 2 1 0 1 4 7 7 3 9 7 1 5
================================
initial: 8 1 5 0 1 1
ought2b: 8 1 0 5 1 1
outcome: 8 1 0 5 1 1
================================
initial: 3 2 8 0 8 1 5 3 8 6 4 7
ought2b: 3 2 1 8 5 0 3 8 7 8 6 4
outcome: 3 2 1 8 5 0 3 8 7 8 6 4
================================
initial: 9 4 8 8 8 0 9 0 3 7 1 9 2 7 3 2 5 4 5 8 1
ought2b: 9 4 9 8 3 8 7 8 1 0 9 0 7 2 3 2 5 4 5 8 1
outcome: 9 4 9 8 3 8 7 8 1 0 9 0 7 2 3 2 5 4 5 8 1
================================
initial: 5 8 1 6 8 0 5
ought2b: 5 8 1 6 5 8 0
outcome: 5 8 1 6 5 8 0
================================
initial: 5 5 5 8 8
ought2b: 5 8 5 8 5
outcome: 5 8 5 8 5
================================
initial: 1 6 2
ought2b: 1 6 2
outcome: 1 6 2
================================
initial: 4 0 8 3 0 6 4 7 3 4
ought2b: 4 3 0 7 8 3 0 6 4 4
outcome: 4 3 0 7 8 3 0 6 4 4
================================
initial: 4 7
ought2b: 4 7
outcome: 4 7
================================
initial: 6 8 5 7 0 7 1 7 7 8 2 8 6 4 6 1 3 2 5 0 8
ought2b: 6 5 8 7 0 7 8 1 2 7 8 7 6 1 4 3 6 5 2 0 8
outcome: 6 5 8 7 0 7 8 1 2 7 8 7 6 1 4 3 6 5 2 0 8
================================
initial: 4 9 5 8 2 7 1 4 1 4 2 4
ought2b: 4 9 8 5 2 7 4 1 4 1 2 4
outcome: 4 9 8 5 2 7 4 1 4 1 2 4
================================
initial: 7 6 1 3
ought2b: 7 6 1 3
outcome: 7 6 1 3
================================
initial: 0 4 1 0 1 5 2 9 2 7 1
ought2b: 0 1 4 1 0 5 2 9 2 7 1
outcome: 0 1 4 1 0 5 2 9 2 7 1
================================
initial: 0 4 9 5 1 0 7 0 9 4
ought2b: 0 9 4 5 0 1 0 7 4 9
outcome: 0 9 4 5 0 1 0 7 4 9
================================
initial: 6
ought2b: 6
outcome: 6
================================
initial: 3 7 5 0 5 9 0 7 9
ought2b: 3 0 7 0 5 5 9 7 9
outcome: 3 0 7 0 5 5 9 7 9
================================
initial: 8 2 5 7 0 8 4 2 2 0 2 0 0 4
ought2b: 8 5 2 7 0 8 4 2 2 0 2 0 0 4
outcome: 8 5 2 7 0 8 4 2 2 0 2 0 0 4
================================
initial: 8 0
ought2b: 8 0
outcome: 8 0
================================
initial: 7 2 8 2 4 6 6 6 9 6 4 3
ought2b: 7 2 9 8 3 2 4 6 6 6 6 4
outcome: 7 2 9 8 3 2 4 6 6 6 6 4
================================
initial: 0 1 0 5 3 9
ought2b: 0 1 0 5 3 9
outcome: 0 1 0 5 3 9
================================
initial: 7 2 2 0 5 7 6 3 4 5 7 4 8 4 0 7 5 8 4 7 6 8 3 9 8
ought2b: 7 2 5 2 7 0 3 6 5 4 7 4 7 8 5 4 7 0 3 8 9 4 6 8 8
outcome: 7 2 5 2 7 0 3 6 5 4 7 4 7 8 5 4 7 0 3 8 9 4 6 8 8
================================
initial: 6 5 8 8 6 3 0 7 0
ought2b: 6 5 8 3 8 7 6 0 0
outcome: 6 5 8 3 8 7 6 0 0
================================
initial: 4
ought2b: 4
outcome: 4
================================
initial: 8 7 7 8 8 3 0 4 9 9 3 6 3
ought2b: 8 7 8 7 8 3 0 9 4 9 6 3 3
outcome: 8 7 8 7 8 3 0 9 4 9 6 3 3
================================
initial: 4 2 6 6 3 1 5 9 2 1 6 7 7 4 3 1 1 1 3 7 0 3 1 5 0
ought2b: 4 3 2 1 6 5 6 9 2 1 6 7 4 7 0 3 0 1 1 1 3 7 3 1 5
outcome: 4 3 2 1 6 5 6 9 2 1 6 7 4 7 0 3 0 1 1 1 3 7 3 1 5
================================
initial: 3
ought2b: 3
outcome: 3
================================
initial: 3 8 2 6 7 6 8 5 3 6 4 2 1 6 6 8 3 2 8
ought2b: 3 8 7 2 5 6 3 6 1 8 3 6 4 2 6 6 8 2 8
outcome: 3 8 7 2 5 6 3 6 1 8 3 6 4 2 6 6 8 2 8
================================
initial: 3 9 5 9
ought2b: 3 9 5 9
outcome: 3 9 5 9
================================
initial: 8 9 4 8 8 6 1 7 6 5 6 3 3 8 3 1 8 9 5
ought2b: 8 9 4 1 8 7 8 5 6 3 6 3 6 3 8 1 8 9 5
outcome: 8 9 4 1 8 7 8 5 6 3 6 3 6 3 8 1 8 9 5
================================
initial: 0 0 9 8 4 8 4 9 2 3 5 2 7 2 1 9 7 3 1 2 7 6 6 5 0
ought2b: 0 9 0 9 8 3 4 5 8 7 4 1 2 9 2 7 2 3 2 1 6 7 6 5 0
outcome: 0 9 0 9 8 3 4 5 8 7 4 1 2 9 2 7 2 3 2 1 6 7 6 5 0
================================
initial: 2 0 7 8 2 5 7 6 3 6 3
ought2b: 2 7 0 5 8 7 2 3 6 3 6
outcome: 2 7 0 5 8 7 2 3 6 3 6
================================
initial: 6 4 5
ought2b: 6 5 4
outcome: 6 5 4
================================
initial: 8 6 6 8 6 2 7 0 3 3 1 1 5 7 8 2
ought2b: 8 7 6 3 6 3 8 1 6 1 2 5 0 7 8 2
outcome: 8 7 6 3 6 3 8 1 6 1 2 5 0 7 8 2
================================
initial: 1 3 3 5
ought2b: 1 3 3 5
outcome: 1 3 3 5
================================
initial: 6 4 9 3 9 5 0 0 4 7 3 7 6 4 8 8 2 9 6
ought2b: 6 9 4 3 0 9 0 5 4 7 6 3 4 7 8 9 8 2 6
outcome: 6 9 4 3 0 9 0 5 4 7 6 3 4 7 8 9 8 2 6
================================
initial: 8 2 0 5 5 0 8 6 5 7 3 2 6 3 0 3 7 2 9 8 8 9 1 0
ought2b: 8 5 2 5 0 5 0 7 8 3 6 3 2 3 6 7 0 9 2 9 8 1 8 0
outcome: 8 5 2 5 0 5 0 7 8 3 6 3 2 3 6 7 0 9 2 9 8 1 8 0
================================
initial: 5 2 5
ought2b: 5 2 5
outcome: 5 2 5
================================
initial: 6 8 7 2 5 5 4 2 0 7 3 8 4 3 7
ought2b: 6 7 8 5 2 5 4 7 2 3 0 3 8 7 4
outcome: 6 7 8 5 2 5 4 7 2 3 0 3 8 7 4
================================
initial: 3 0 4 1 6
ought2b: 3 0 1 4 6
outcome: 3 0 1 4 6
================================
initial: 5 9 3 0 1 7 3 6 0 4 9 0 4 9 9 0 8 4 4 4 2 1
ought2b: 5 0 9 6 3 0 1 4 7 0 3 4 9 0 9 8 9 4 1 4 4 2
outcome: 5 0 9 6 3 0 1 4 7 0 3 4 9 0 9 8 9 4 1 4 4 2
================================
initial: 6 9 2 4 5 9 6 4 0 6 7 7 5 5 9 5 2 1 5 6 5 3 8 9
ought2b: 6 9 2 5 4 9 6 7 4 7 0 5 6 5 2 9 6 5 8 1 5 5 3 9
outcome: 6 9 2 5 4 9 6 7 4 7 0 5 6 5 2 9 6 5 8 1 5 5 3 9
================================
initial: 9 3 7 9 2 3 6 1 2 2 2
ought2b: 9 2 3 6 7 2 9 2 3 2 1
outcome: 9 2 3 6 7 2 9 2 3 2 1
================================
initial: 1 6 4 9 0 9
ought2b: 1 6 9 4 9 0
outcome: 1 6 9 4 9 0
================================
initial: 7 6
ought2b: 7 6
outcome: 7 6
================================
initial: 6 3 3 3 9 3 7 4 0 6 1 6
ought2b: 6 3 4 3 0 3 6 9 6 3 7 1
outcome: 6 3 4 3 0 3 6 9 6 3 7 1
================================
initial: 1 4 4 9 9 2 0 9 9 9 3 8 3 4 1 8 7 1 8 4 6 8 6 6
ought2b: 1 4 9 4 9 2 9 0 9 8 9 4 3 8 3 8 1 4 7 6 1 8 6 6
outcome: 1 4 9 4 9 2 9 0 9 8 9 4 3 8 3 8 1 4 7 6 1 8 6 6
================================
initial: 3 6 6
ought2b: 3 6 6
outcome: 3 6 6
================================
initial: 5 1 7 7 8 0 2 5 7 2
ought2b: 5 8 1 0 7 2 7 2 5 7
outcome: 5 8 1 0 7 2 7 2 5 7
================================
initial: 3 2 0 0
ought2b: 3 2 0 0
outcome: 3 2 0 0
================================
initial: 4 8 0 9 8 3 2 3 0 2 2 0 3 5 5 7 1 8 2 8 4 0 4 3
ought2b: 4 9 8 3 0 3 8 3 2 5 0 5 2 7 2 1 0 3 8 2 8 4 0 4
outcome: 4 9 8 3 0 3 8 3 2 5 0 5 2 7 2 1 0 3 8 2 8 4 0 4
================================
initial: 6 9 2 3 3 3 8 1 3 6 4 6
ought2b: 6 9 2 3 8 3 6 3 4 1 6 3
outcome: 6 9 2 3 8 3 6 3 4 1 6 3
================================
initial: 9 0 4 4 4 0 8 2 7 4 5 6 6 4 9 8 0 6 4
ought2b: 9 0 7 4 5 4 9 4 0 8 2 4 6 6 4 8 0 6 4
outcome: 9 0 7 4 5 4 9 4 0 8 2 4 6 6 4 8 0 6 4
================================
test program terminated normally
================================
Fill in the linked-list processing function InterleaveOddsAndEvensInOrigOrder from the given file, that is to process a given linked list as follows.
Explanation / Answer
main.cpp
#include "llcpInt.h"
#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
void SeedRand();
int BoundedRandomInt(int lowerBound, int upperBound);
int ListLengthCheck(Node* head, int whatItShouldBe);
bool match(Node* head, const int procInts[], int procSize);
void ShowArray(const int a[], int size);
void DebugShowCase(int whichCase, int totalCasesToDo,
const int caseValues[], int caseSize);
int main()
{
int testCasesToDo = 750000,
testCasesDone = 0,
loSize = 1,
hiSize = 25,
loValue = 0,
hiValue = 9;
int numInts,
numOdds,
numEvens,
intCount,
newInt,
iLenChk,
iOdd,
iEven,
iProc;
int *rawInts = 0,
*procInts = 0,
*rawOddInts = 0,
*rawEvenInts = 0;
Node* head = 0;
InterleaveOddsAndEvensInOrigOrder(head);
cout << "================================" << endl;
cout << "passed crash test on empty list" << endl;
// SeedRand(); // disabled for reproducible result
do
{
++testCasesDone;
numInts = BoundedRandomInt(loSize, hiSize);
numOdds = numEvens = 0;
rawInts = new int [numInts];
procInts = new int [numInts];
rawOddInts = new int [numInts];
rawEvenInts = new int [numInts];
intCount = 0;
while (intCount < numInts)
{
newInt = BoundedRandomInt(loValue, hiValue);
rawInts[intCount++] = newInt;
if (newInt % 2)
rawOddInts[numOdds++] = newInt;
else
rawEvenInts[numEvens++] = newInt;
InsertAsTail(head, newInt);
}
iOdd = iEven = iProc = 0;
if (rawInts[0] % 2)
{
while (iProc < numInts)
{
if (iOdd < numOdds)
procInts[iProc++] = rawOddInts[iOdd++];
if (iEven < numEvens)
procInts[iProc++] = rawEvenInts[iEven++];
}
}
else
{
while (iProc < numInts)
{
if (iEven < numEvens)
procInts[iProc++] = rawEvenInts[iEven++];
if (iOdd < numOdds)
procInts[iProc++] = rawOddInts[iOdd++];
}
}
// DebugShowCase(testCasesDone, testCasesToDo, rawInts, numInts);
InterleaveOddsAndEvensInOrigOrder(head);
iLenChk = ListLengthCheck(head, numInts);
if (iLenChk != 0)
{
if (iLenChk == -1)
{
cout << "Node-count error ... too few" << endl;
cout << "test_case: ";
ShowArray(rawInts, numInts);
cout << "#expected: " << numInts << endl;
cout << "#returned: " << FindListLength(head) << endl;
}
else
{
cout << "Node-count error ... too many (circular list?)" << endl;
cout << "test_case: ";
ShowArray(rawInts, numInts);
cout << "#expected: " << numInts << endl;
cout << "returned # is higher (may be infinite)" << endl;
}
exit(EXIT_FAILURE);
}
if (! match(head, procInts, numInts) )
{
cout << "Contents error ... mismatch found in value or order" << endl;
cout << "initial: ";
ShowArray(rawInts, numInts);
cout << "ought2b: ";
ShowArray(procInts, numInts);
cout << "outcome: ";
ShowAll(cout, head);
exit(EXIT_FAILURE);
}
if (testCasesDone % 10000 == 0)
{
cout << "================================" << endl;
clog << "testing case " << testCasesDone
<< " of " << testCasesToDo << endl;
clog << "================================" << endl;
// cout << "test case " << testCasesDone
// << " of " << testCasesToDo << endl;
cout << "initial: ";
ShowArray(rawInts, numInts);
cout << "ought2b: ";
ShowArray(procInts, numInts);
cout << "outcome: ";
ShowAll(cout, head);
}
ListClear(head, 1);
delete [] rawInts;
delete [] procInts;
delete [] rawOddInts;
delete [] rawEvenInts;
rawInts = procInts = rawOddInts = rawEvenInts = 0;
}
while (testCasesDone < testCasesToDo);
cout << "================================" << endl;
cout << "test program terminated normally" << endl;
cout << "================================" << endl;
return EXIT_SUCCESS;
}
void SeedRand()
{
srand( (unsigned) time(NULL) );
}
int BoundedRandomInt(int lowerBound, int upperBound)
{
return ( rand() % (upperBound - lowerBound + 1) ) + lowerBound;
}
int ListLengthCheck(Node* head, int whatItShouldBe)
{
int length = 0;
while (head != 0)
{
++length;
if (length > whatItShouldBe) return 1;
head = head->link;
}
return (length < whatItShouldBe) ? -1 : 0;
}
bool match(Node* head, const int procInts[], int procSize)
{
int iProc = 0;
while (head != 0)
{
if (iProc == procSize) return false;
if (head->data != procInts[iProc]) return false;
++iProc;
head = head->link;
}
return true;
}
void ShowArray(const int a[], int size)
{
for (int i = 0; i < size; ++i)
cout << a[i] << " ";
cout << endl;
}
void DebugShowCase(int whichCase, int totalCasesToDo,
const int caseValues[], int caseSize)
{
cout << "test case " << whichCase
<< " of " << totalCasesToDo << endl;
cout << "given list: ";
ShowArray(caseValues, caseSize);
}
llcpImp.cpp
#include <iostream>
#include <cstdlib>
#include "llcpInt.h"
using namespace std;
int FindListLength(Node* headPtr)
{
int length = 0;
while (headPtr != 0)
{
++length;
headPtr = headPtr->link;
}
return length;
}
bool IsSortedUp(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;
}
void InsertAsHead(Node*& headPtr, int value)
{
Node *newNodePtr = new Node;
newNodePtr->data = value;
newNodePtr->link = headPtr;
headPtr = newNodePtr;
}
void InsertAsTail(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;
}
}
void InsertSortedUp(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;
}
*/
///////////////////////////////////////////////////////////
}
bool DelFirstTargetNode(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;
}
void ShowAll(ostream& outs, Node* headPtr)
{
while (headPtr != 0)
{
outs << headPtr->data << " ";
headPtr = headPtr->link;
}
outs << endl;
}
void FindMinMax(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;
}
}
}
double FindAverage(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;
}
}
void ListClear(Node*& headPtr, int noMsg)
{
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;
}
void InterleaveOddsAndEvensInOrigOrder(Node* head)
/*
itPre it
curPre cur
---------------------------------------- --------
| data | data | data | data | . . . | data |
---------------------------------------- --------
| link | link | link | link | . . . | 0 |
---------------------------------------- --------
(head) (tail)
*/
{
if( head == 0 || head->link == 0 || head->link->link == 0 ) return;
Node* curPre = head;
Node* cur = head->link;
Node* itPre = cur;
Node* it = cur->link;
do
{
// see if curPre and cur are either both odd or both even
// (i.e., non-complementary)
if( (curPre->data%2 == 0) == (cur->data%2 == 0) )
{
// if so, look to see if the oddness/evenness of the
// 'it' pointer complements curPre
if( (curPre->data%2 == 0) != (it->data%2 == 0) )
{
// if so, re-arrange the list
itPre->link = it->link;
it->link = cur;
curPre->link = it;
// re-configure the pointers to the correct sequence
// for next run
cur = it;
itPre = cur;
it = cur->link;
// and increment all pointers by one node
// for next run
curPre = curPre->link;
cur = cur->link;
itPre = itPre->link;
it = it->link;
}
else
{
// if the oddness/evenness of the 'it' pointer does NOT
// complement curPre, then increment itPre and it by
// one node for the next run
itPre = itPre->link;
it = it->link;
}
}
else
{
// else curPre and cur must have complementary oddness/evenness,
// so increment all pointers by one node for next run
curPre = curPre->link;
cur = cur->link;
itPre = itPre->link;
it = it->link;
}
} while( it != 0 ); // end do-while
} // end InterleaveOddsAndEvensInOrigOrder()
llcpInt.h
#ifndef LLCP_INT_H
#define LLCP_INT_H
#include <iostream>
struct Node
{
int data;
Node *link;
};
int FindListLength(Node* headPtr);
bool IsSortedUp(Node* headPtr);
void InsertAsHead(Node*& headPtr, int value);
void InsertAsTail(Node*& headPtr, int value);
void InsertSortedUp(Node*& headPtr, int value);
bool DelFirstTargetNode(Node*& headPtr, int target);
bool DelNodeBefore1stMatch(Node*& headPtr, int target);
void ShowAll(std::ostream& outs, Node* headPtr);
void FindMinMax(Node* headPtr, int& minValue, int& maxValue);
double FindAverage(Node* headPtr);
void ListClear(Node*& headPtr, int noMsg = 0);
void InterleaveOddsAndEvensInOrigOrder(Node* head);
// prototype of InterleaveOddsAndEvensInOrigOrder of Assignment 5
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.