This part of the assignment aims at providing you with a programming exercise in
ID: 3599745 • Letter: T
Question
This part of the assignment aims at providing you with a programming exercise involving linked list, stack, queue, and the STL.
You are to study and complete this supplied partial program that does the following:
Use the STL stack template class to develop a custom queue class (named cnPtrQueue).
Further information on implementing a queue using 2 stacks is available here.
The cnPtrQueue has member variable numItems (that keeps track of the number of items in the queue), which should be helpful for implementing the member function size() (for inspecting the number of items in the queue).
Use the cnPtrQueue to perform a breadth-first (level) traversal of a linked list of linked lists data structure and process (print) the data items stored in the structure.
Further information on linked list of linked lists and level traversal using queue is available here.
Test your completed program with at least the supplied the test input file (a5p2_test.in) : make test (or, if you prefer to do it "manually", ./a5p2 auto < a5p2_test.in > a5p2_test.out). The correct output should look as follows:
Dynamic memory for 0 CNodes freed
Dynamic memory for 1 PNodes freed
11
11
Dynamic memory for 1 CNodes freed
Dynamic memory for 1 PNodes freed
11 12 13 14
11 12 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 PNodes freed
21 22 23 24
21 22 23 24
Dynamic memory for 0 CNodes freed
Dynamic memory for 4 CNodes freed
Dynamic memory for 2 PNodes freed
11 12 13 14
11 12 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 PNodes freed
11 12 13 14 21 41 42
11 21 41 12 42 13 14
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 CNodes freed
Dynamic memory for 4 PNodes freed
21 22 23 24 31 51 52
21 31 51 22 52 23 24
Dynamic memory for 0 CNodes freed
Dynamic memory for 4 CNodes freed
Dynamic memory for 1 CNodes freed
Dynamic memory for 0 CNodes freed
Dynamic memory for 2 CNodes freed
Dynamic memory for 5 PNodes freed
Your Tasks
Study the supplied files - how they all relate to each other.
Fill in the "holes" intentionally left:
Implementation of cnPtrQueue in cnPtrQueue.cpp.
Function body of ShowAll_BF in nodes_LLoLL.cpp.
You are to put the cnPtrQueue (NOT the STL queue) to use here.
(You will earn little or no credit if you use the STL queue).
Test the "holes-filled-in" program.
#include "nodes_LLoLL.h"
#include <cstdlib>
using namespace std;
using namespace CS3358_FA17_A5P2;
void Build_cList(int argc, CNode*& cListHead);
void Build_pList(int argc, PNode*& pListHead);
int main(int argc, char* argv[])
{
PNode* head_LLoLL = 0;
char reply;
do
{
Build_pList(argc, head_LLoLL);
ShowAll_DF(head_LLoLL, cout);
cout << endl;
ShowAll_BF(head_LLoLL, cout);
cout << endl;
Destroy_pList(head_LLoLL);
if (argc < 2)
cout << "Another? (n = no, others = yes) ";
cin >> reply;
}
while (reply != 'n' && reply != 'N');
return EXIT_SUCCESS;
}
void Build_cList(int argc, CNode*& cListHead)
{
int oneInt;
char reply;
CNode* cListTail = cListHead;
if (argc < 2)
cout << "Add cList data? (n = no, others = yes) ";
cin >> reply;
while (reply != 'n' && reply != 'N')
{
if (argc < 2)
cout << "Enter cList data (int): ";
cin >> oneInt;
CNode* cNodePtr = new CNode;
cNodePtr->data = oneInt;
cNodePtr->link = 0;
if (cListTail == 0)
cListHead = cListTail = cNodePtr;
else
{
cListTail->link = cNodePtr;
cListTail = cNodePtr;
}
if (argc < 2)
cout << "Add more cList data? (n = no, others = yes) ";
cin >> reply;
}
}
void Build_pList(int argc, PNode*& pListHead)
{
char reply;
PNode* pListTail = pListHead;
if (argc < 2)
cout << "Add cList to pList? (n = no, others = yes) ";
cin >> reply;
while (reply != 'n' && reply != 'N')
{
CNode* cListHead = 0;
Build_cList(argc, cListHead);
PNode* pNodePtr = new PNode;
pNodePtr->data = cListHead;
pNodePtr->link = 0;
if (pListTail == 0)
pListHead = pListTail = pNodePtr;
else
{
pListTail->link = pNodePtr;
pListTail = pNodePtr;
}
if (argc < 2)
cout << "Add more cList to pList? (n = no, others = yes) ";
cin >> reply;
}
}
Explanation / Answer
#include "nodes_LLoLL.h"
#include <cstdlib>
using namespace std;
using namespace CS3358_FA17_A5P2;
void Build_cList(int argc, CNode*& cListHead);
void Build_pList(int argc, PNode*& pListHead);
int main(int argc, char* argv[])
{
PNode* head_LLoLL = 0;
char reply;
do
{
Build_pList(argc, head_LLoLL);
ShowAll_DF(head_LLoLL, cout);
cout << endl;
ShowAll_BF(head_LLoLL, cout);
cout << endl;
Destroy_pList(head_LLoLL);
if (argc < 2)
cout << "Another? (n = no, others = yes) ";
cin >> reply;
}
while (reply != 'n' && reply != 'N');
return EXIT_SUCCESS;
}
void Build_cList(int argc, CNode*& cListHead)
{
int oneInt;
char reply;
CNode* cListTail = cListHead;
if (argc < 2)
cout << "Add cList data? (n = no, others = yes) ";
cin >> reply;
while (reply != 'n' && reply != 'N')
{
if (argc < 2)
cout << "Enter cList data (int): ";
cin >> oneInt;
CNode* cNodePtr = new CNode;
cNodePtr->data = oneInt;
cNodePtr->link = 0;
if (cListTail == 0)
cListHead = cListTail = cNodePtr;
else
{
cListTail->link = cNodePtr;
cListTail = cNodePtr;
}
if (argc < 2)
cout << "Add more cList data? (n = no, others = yes) ";
cin >> reply;
}
}
void Build_pList(int argc, PNode*& pListHead)
{
char reply;
PNode* pListTail = pListHead;
if (argc < 2)
cout << "Add cList to pList? (n = no, others = yes) ";
cin >> reply;
while (reply != 'n' && reply != 'N')
{
CNode* cListHead = 0;
Build_cList(argc, cListHead);
PNode* pNodePtr = new PNode;
pNodePtr->data = cListHead;
pNodePtr->link = 0;
if (pListTail == 0)
pListHead = pListTail = pNodePtr;
else
{
pListTail->link = pNodePtr;
pListTail = pNodePtr;
}
if (argc < 2)
cout << "Add more cList to pList? (n = no, others = yes) ";
cin >> reply;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.