Code: //********************************************************* // Header file
ID: 3844515 • Letter: C
Question
Code:
//********************************************************* // Header file LabListP.h for the ADT list. // Pointer-based implementation. // The first "position" in a list is position = 1, // as implemented in the insert(), remove(), retrieve(), // and private ptrTo() methods. //*********************************************************
//********************************************************* // The "typedef" below must be configured for the type // of data stored in each node in the list //********************************************************* //typedef desired - type - of - list - item ListItemType; typedef int SortListItemType;
class SortListClass { public: // constructors and destructor: SortListClass(); // default constructor ~SortListClass(); // destructor
SortListClass(const SortListClass& existingList); // copy constructor SortListClass& operator=(const SortListClass& rhs); // assignment operator
// list operations: bool isEmpty() const; int getLength() const;
// Methods return true if successful, false otherwise // bool insert(int position, SortListItemType& newItem); bool insert(SortListItemType& newItem);
bool remove(int position); bool retrieve(int position, SortListItemType& dataItem) const; void PrintsortList(); int find(SortListItemType& dataItem) const; void SortListClass::deleteItem(int deleteItem); void DestoryNode(); private: struct SortListNode { SortListItemType item; SortListNode *next; };
int size; // number of items in list
SortListNode *head; // pointer to linked list of items SortListNode *last; SortListNode *ptrTo(int position) const; // Returns a pointer to the node at position (1 .. k) in list };
//******************************************************* // Implementation file LabListP.cpp for the ADT list. // Pointer-based implementation. //******************************************************* #include "SortLabListP.h" // header file #include <cstddef> // for NULL #include <cassert> // for assert() #include <iostream> using namespace std; SortListClass::SortListClass() : size(0), head(nullptr), last(nullptr) { // *this = existingList; }
SortListClass::~SortListClass() // Destructor { bool success;
while (!isEmpty()) { success = remove(1); // Repeatedly delete item 1 } }
bool SortListClass::isEmpty() const { return bool(size == 0); }
int SortListClass::getLength() const { return size; }
/*// assignment operator: Make DEEP copy SortListClass& SortListClass::operator=(const SortListClass& rhs) { // TODO // Similar to Copy Constructor, except // - Avoid self-assignments such as “X = X;” // - Delete existing this-instance content before // making this-instance a copy of the rhs instance return(*this); } */
// Copy Constructor: Make DEEP copy SortListClass::SortListClass(const SortListClass& existingList): size(existingList.size) { if (existingList.head == NULL) head = NULL; // original list is empty
else { // copy first node head = new SortListNode; assert(head != NULL); // check allocation
head->item = existingList.head->item;
// copy rest of list SortListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list // origPtr points to nodes in original list for (SortListNode *origPtr = existingList.head->next; origPtr != NULL; origPtr = origPtr->next) { newPtr->next = new SortListNode; // link new node to end of list assert(newPtr->next != NULL); newPtr = newPtr->next;
newPtr->item = origPtr->item; // copy the data newPtr->next = NULL; } } //return(*this); }
// ---------------------------------------------------------------------- // Locates a specified node in a linked list. // Precondition: position is the number of the desired node. // Postcondition: Returns a pointer to the desired node. // If position < 1 or position > size (the number of nodes in the list), // returns NULL. // ----------------------------------------------------------------------
SortListClass::SortListNode *SortListClass::ptrTo(int position) const { if ((position < 1) || (position > size)) return NULL;
else // count from the beginning of the list { SortListNode *cur = head;
for (int skip = 1; skip < position; ++skip) cur = cur->next;
return cur; } }
bool SortListClass::retrieve(int position, SortListItemType& dataItem) const { bool success = bool( (position >= 1) && (position <= size) ); success = true; if (success) { // get pointer to node, then data in node SortListNode *cur = ptrTo(position);
dataItem = cur->item; }
return(success); }
bool SortListClass::insert(SortListItemType& newItem) { SortListNode *prev = NULL; SortListNode *cur = head; while ((cur != NULL) && (newItem > cur->item)) { prev = cur; cur = cur->next; } // create new node and place newItem in it SortListNode *newPtr = new SortListNode; newPtr->item = newItem; newPtr->next = cur; if (prev == NULL) head = newPtr; // insert new node to right of previous node else prev->next = newPtr; size++; return(0); }
int SortListClass::find(SortListItemType& dt) const { SortListNode *cur; bool found = false; cur = head; int cnt = 0; while (cur != NULL) { if (cur->item == dt) return cnt; else { cnt++; cur = cur->next; } } return false; }
bool SortListClass::remove(int position) { SortListNode *cur; bool success = bool((position >= 1) && (position <= size)); if (success) { --size; if (position == 1) { // delete the first node from the list cur = head; // save pointer to node head = head->next; } else { SortListNode *prev = ptrTo(position - 1); // delete the node after the node // to which prev points cur = prev->next; // save pointer to node prev->next = cur->next; }
// return node to system cur->next = NULL; // safety - remove node from list delete cur; cur = NULL; // safety } return(success); }
----------------------------------------------------------------------------------------
//LabListMain.cpp // LabListRandom // CSC 2430 Lab Assignment // Written by: // Date:
#include <iostream> #include <iomanip> #include <cstddef> #include <limits> using namespace std;
#include "SortLabListP.h"
void printListClass(char listname[], const SortListClass& lst) { cout << listname << ": length=" << lst.getLength() << " items" << endl;
int numitems = lst.getLength(); for (int i = 1; i <= numitems; ++i) { int val; if (lst.retrieve(i, val)) cout << setw(3) << i << ": " << setw(5) << val << endl; else cout << "Cannot retrieve item from position " << i << endl; } cout << endl; }
int main() {
// setup const int N = 10; // number of items, used only to create initial list of values const int RANGE = 32768; // value range. Set to INT_MAX for a list of values from 0 .. 32767
// Prepare random number generator with initial seed value // and discard the first few data items in the sequence srand(3); for (int i = 0; i < 10; ++i) rand();
///////////////////////////////////////////////// // Greeting cout << "Linked List Lab: Implemented by Mike Tindall" << endl; cout << "Randomly generate list of " << N << " values in range 0-" << RANGE - 1 << " and convert into a sorted list" << endl << endl;
///////////////////////////////////////////////// // Create initial "by position" data value list SortListClass listbyposition;
for (int i = 1; i <= N; ++i) { int val = rand() % RANGE; // produce next random number value listbyposition.insert( val); // Put val into list at position i }
// Output initial data list printListClass("listbyposition", listbyposition);
system("pause"); return(0); }
Code:
//********************************************************* // Header file LabListP.h for the ADT list. // Pointer-based implementation. // The first "position" in a list is position = 1, // as implemented in the insert(), remove(), retrieve(), // and private ptrTo() methods. //*********************************************************
//********************************************************* // The "typedef" below must be configured for the type // of data stored in each node in the list //********************************************************* //typedef desired - type - of - list - item ListItemType; typedef int SortListItemType;
class SortListClass { public: // constructors and destructor: SortListClass(); // default constructor ~SortListClass(); // destructor
SortListClass(const SortListClass& existingList); // copy constructor SortListClass& operator=(const SortListClass& rhs); // assignment operator
// list operations: bool isEmpty() const; int getLength() const;
// Methods return true if successful, false otherwise // bool insert(int position, SortListItemType& newItem); bool insert(SortListItemType& newItem);
bool remove(int position); bool retrieve(int position, SortListItemType& dataItem) const; void PrintsortList(); int find(SortListItemType& dataItem) const; void SortListClass::deleteItem(int deleteItem); void DestoryNode(); private: struct SortListNode { SortListItemType item; SortListNode *next; };
int size; // number of items in list
SortListNode *head; // pointer to linked list of items SortListNode *last; SortListNode *ptrTo(int position) const; // Returns a pointer to the node at position (1 .. k) in list };
//******************************************************* // Implementation file LabListP.cpp for the ADT list. // Pointer-based implementation. //******************************************************* #include "SortLabListP.h" // header file #include <cstddef> // for NULL #include <cassert> // for assert() #include <iostream> using namespace std; SortListClass::SortListClass() : size(0), head(nullptr), last(nullptr) { // *this = existingList; }
SortListClass::~SortListClass() // Destructor { bool success;
while (!isEmpty()) { success = remove(1); // Repeatedly delete item 1 } }
bool SortListClass::isEmpty() const { return bool(size == 0); }
int SortListClass::getLength() const { return size; }
/*// assignment operator: Make DEEP copy SortListClass& SortListClass::operator=(const SortListClass& rhs) { // TODO // Similar to Copy Constructor, except // - Avoid self-assignments such as “X = X;” // - Delete existing this-instance content before // making this-instance a copy of the rhs instance return(*this); } */
// Copy Constructor: Make DEEP copy SortListClass::SortListClass(const SortListClass& existingList): size(existingList.size) { if (existingList.head == NULL) head = NULL; // original list is empty
else { // copy first node head = new SortListNode; assert(head != NULL); // check allocation
head->item = existingList.head->item;
// copy rest of list SortListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list // origPtr points to nodes in original list for (SortListNode *origPtr = existingList.head->next; origPtr != NULL; origPtr = origPtr->next) { newPtr->next = new SortListNode; // link new node to end of list assert(newPtr->next != NULL); newPtr = newPtr->next;
newPtr->item = origPtr->item; // copy the data newPtr->next = NULL; } } //return(*this); }
// ---------------------------------------------------------------------- // Locates a specified node in a linked list. // Precondition: position is the number of the desired node. // Postcondition: Returns a pointer to the desired node. // If position < 1 or position > size (the number of nodes in the list), // returns NULL. // ----------------------------------------------------------------------
SortListClass::SortListNode *SortListClass::ptrTo(int position) const { if ((position < 1) || (position > size)) return NULL;
else // count from the beginning of the list { SortListNode *cur = head;
for (int skip = 1; skip < position; ++skip) cur = cur->next;
return cur; } }
bool SortListClass::retrieve(int position, SortListItemType& dataItem) const { bool success = bool( (position >= 1) && (position <= size) ); success = true; if (success) { // get pointer to node, then data in node SortListNode *cur = ptrTo(position);
dataItem = cur->item; }
return(success); }
bool SortListClass::insert(SortListItemType& newItem) { SortListNode *prev = NULL; SortListNode *cur = head; while ((cur != NULL) && (newItem > cur->item)) { prev = cur; cur = cur->next; } // create new node and place newItem in it SortListNode *newPtr = new SortListNode; newPtr->item = newItem; newPtr->next = cur; if (prev == NULL) head = newPtr; // insert new node to right of previous node else prev->next = newPtr; size++; return(0); }
int SortListClass::find(SortListItemType& dt) const { SortListNode *cur; bool found = false; cur = head; int cnt = 0; while (cur != NULL) { if (cur->item == dt) return cnt; else { cnt++; cur = cur->next; } } return false; }
bool SortListClass::remove(int position) { SortListNode *cur; bool success = bool((position >= 1) && (position <= size)); if (success) { --size; if (position == 1) { // delete the first node from the list cur = head; // save pointer to node head = head->next; } else { SortListNode *prev = ptrTo(position - 1); // delete the node after the node // to which prev points cur = prev->next; // save pointer to node prev->next = cur->next; }
// return node to system cur->next = NULL; // safety - remove node from list delete cur; cur = NULL; // safety } return(success); }
----------------------------------------------------------------------------------------
//LabListMain.cpp // LabListRandom // CSC 2430 Lab Assignment // Written by: // Date:
#include <iostream> #include <iomanip> #include <cstddef> #include <limits> using namespace std;
#include "SortLabListP.h"
void printListClass(char listname[], const SortListClass& lst) { cout << listname << ": length=" << lst.getLength() << " items" << endl;
int numitems = lst.getLength(); for (int i = 1; i <= numitems; ++i) { int val; if (lst.retrieve(i, val)) cout << setw(3) << i << ": " << setw(5) << val << endl; else cout << "Cannot retrieve item from position " << i << endl; } cout << endl; }
int main() {
// setup const int N = 10; // number of items, used only to create initial list of values const int RANGE = 32768; // value range. Set to INT_MAX for a list of values from 0 .. 32767
// Prepare random number generator with initial seed value // and discard the first few data items in the sequence srand(3); for (int i = 0; i < 10; ++i) rand();
///////////////////////////////////////////////// // Greeting cout << "Linked List Lab: Implemented by Mike Tindall" << endl; cout << "Randomly generate list of " << N << " values in range 0-" << RANGE - 1 << " and convert into a sorted list" << endl << endl;
///////////////////////////////////////////////// // Create initial "by position" data value list SortListClass listbyposition;
for (int i = 1; i <= N; ++i) { int val = rand() % RANGE; // produce next random number value listbyposition.insert( val); // Put val into list at position i }
// Output initial data list printListClass("listbyposition", listbyposition);
system("pause"); return(0); }
LabListP h and LabListP.cpp Defines and implements ListClass, a class containing a "by position linked list of nodes. The LabListP.cpp file is completely implemented except for the assignment operator method. LabListMain.cppo An initial version of the main program for this assignment which: a. creates a ListClass variable named "listbyposition" b. creates and inserts a collection of random data values into consecutive positions in this list prints out the list. Create a Visual Studio solution project for this lab using these three source files. After creating an empty Console-application project, copy the three source files into the project subdirectory (that's the inner subdirectory with the solution) and use the menu "Project/Add Existing files" to select them into the project. The project solution should correctly build and execute, with output similar to: Linked List Lab Implemented by Mike Tindall Randomly generate list of 10 values in range 0-32767 and convert into a sorted list list by position length 10 items 1 5409 2 28233 3: 2023 4: 17152 5: 21578 6: 2399 7: 23863 8: 16025 9: 8489 10: 19718 Change the initial main program to print out your own name (instead of your instructors name).
Explanation / Answer
//.h file , added method declaration for operator+
//SortLabListP.h
//*********************************************************
// Header file LabListP.h for the ADT list.
// Pointer-based implementation.
// The first "position" in a list is position = 1,
// as implemented in the insert(), remove(), retrieve(),
// and private ptrTo() methods.
//*********************************************************
//*********************************************************
// The "typedef" below must be configured for the type
// of data stored in each node in the list
//*********************************************************
//typedef desired - type - of - list - item ListItemType;
typedef int SortListItemType;
class SortListClass
{
public:
// constructors and destructor:
SortListClass(); // default constructor
~SortListClass(); // destructor
SortListClass(const SortListClass& existingList); // copy constructor
SortListClass& operator=(const SortListClass& rhs); // assignment operator
// list operations:
bool isEmpty() const;
int getLength() const;
// Methods return true if successful, false otherwise
// bool insert(int position, SortListItemType& newItem);
bool insert(SortListItemType& newItem);
bool remove(int position);
bool retrieve(int position, SortListItemType& dataItem) const;
void PrintsortList();
int find(SortListItemType& dataItem) const;
void SortListClass::deleteItem(int deleteItem);
void DestoryNode();
//added by chegg EQ
SortListClass operator+=(SortListClass &obj);
private:
struct SortListNode
{
SortListItemType item;
SortListNode *next;
};
int size; // number of items in list
SortListNode *head; // pointer to linked list of items
SortListNode *last;
SortListNode *ptrTo(int position) const;
// Returns a pointer to the node at position (1 .. k) in list
};
-----------------------------------------------------------------
//SortLabListP.cpp
//*******************************************************
// Implementation file LabListP.cpp for the ADT list.
// Pointer-based implementation.
//*******************************************************
#include "SortLabListP.h" // header file
#include <cstddef> // for NULL
#include <cassert> // for assert()
#include <iostream>
using namespace std;
SortListClass::SortListClass()
: size(0), head(nullptr), last(nullptr)
{
// *this = existingList;
}
SortListClass::~SortListClass() // Destructor
{
bool success;
while (!isEmpty())
{
success = remove(1); // Repeatedly delete item 1
}
}
bool SortListClass::isEmpty() const
{
return bool(size == 0);
}
int SortListClass::getLength() const
{
return size;
}
// assignment operator: Make DEEP copy
SortListClass& SortListClass::operator=(const SortListClass& rhs)
{
// TODO
// Similar to Copy Constructor, except
// - Avoid self-assignments such as “X = X;”
// - Delete existing this-instance content before
// making this-instance a copy of the rhs instance
head = rhs.head;
last = rhs.last;
size = rhs.size;
return(*this);
}
// Copy Constructor: Make DEEP copy
SortListClass::SortListClass(const SortListClass& existingList) : size(existingList.size)
{
if (existingList.head == NULL)
head = NULL; // original list is empty
else
{
// copy first node
head = new SortListNode;
assert(head != NULL); // check allocation
head->item = existingList.head->item;
// copy rest of list
SortListNode *newPtr = head; // new list pointer
// newPtr points to last node in new list
// origPtr points to nodes in original list
for (SortListNode *origPtr = existingList.head->next;
origPtr != NULL;
origPtr = origPtr->next)
{
newPtr->next = new SortListNode; // link new node to end of list
assert(newPtr->next != NULL);
newPtr = newPtr->next;
newPtr->item = origPtr->item; // copy the data
newPtr->next = NULL;
}
}
//return(*this);
}
// ----------------------------------------------------------------------
// Locates a specified node in a linked list.
// Precondition: position is the number of the desired node.
// Postcondition: Returns a pointer to the desired node.
// If position < 1 or position > size (the number of nodes in the list),
// returns NULL.
// ----------------------------------------------------------------------
SortListClass::SortListNode *SortListClass::ptrTo(int position) const
{
if ((position < 1) || (position > size))
return NULL;
else // count from the beginning of the list
{
SortListNode *cur = head;
for (int skip = 1; skip < position; ++skip)
cur = cur->next;
return cur;
}
}
bool SortListClass::retrieve(int position, SortListItemType& dataItem) const
{
bool success = bool((position >= 1) && (position <= size));
success = true;
if (success)
{
// get pointer to node, then data in node
SortListNode *cur = ptrTo(position);
dataItem = cur->item;
}
return(success);
}
bool SortListClass::insert(SortListItemType& newItem)
{
SortListNode *prev = NULL; SortListNode *cur = head;
while ((cur != NULL) && (newItem > cur->item))
{
prev = cur;
cur = cur->next;
}
// create new node and place newItem in it
SortListNode *newPtr = new SortListNode; newPtr->item = newItem;
newPtr->next = cur;
if (prev == NULL) head = newPtr;
// insert new node to right of previous node
else prev->next = newPtr;
size++;
return(0);
}
int SortListClass::find(SortListItemType& dt) const
{
SortListNode *cur;
bool found = false;
cur = head;
int cnt = 0;
while (cur != NULL)
{
if (cur->item == dt)
return cnt;
else
{
cnt++;
cur = cur->next;
}
}
return false;
}
bool SortListClass::remove(int position)
{
SortListNode *cur;
bool success = bool((position >= 1) && (position <= size));
if (success)
{
--size;
if (position == 1)
{
// delete the first node from the list
cur = head; // save pointer to node
head = head->next;
}
else
{
SortListNode *prev = ptrTo(position - 1);
// delete the node after the node
// to which prev points
cur = prev->next; // save pointer to node
prev->next = cur->next;
}
// return node to system
cur->next = NULL; // safety - remove node from list
delete cur;
cur = NULL; // safety
}
return(success);
}
--------------------------------------------------------------------------
//main.cpp
//LabListMain.cpp
// LabListRandom
// CSC 2430 Lab Assignment
// Written by:
// Date:
#include <iostream>
#include <iomanip>
#include <cstddef>
#include <limits>
using namespace std;
#include "SortLabListP.h"
void printListClass(char listname[], const SortListClass& lst)
{
cout << listname << ": length=" << lst.getLength() << " items" << endl;
int numitems = lst.getLength();
for (int i = 1; i <= numitems; ++i)
{
int val;
if (lst.retrieve(i, val))
cout << setw(3) << i << ": " << setw(5) << val << endl;
else
cout << "Cannot retrieve item from position " << i << endl;
}
cout << endl;
}
int main()
{
// setup
const int N = 10; // number of items, used only to create initial list of values
const int RANGE = 32768; // value range. Set to INT_MAX for a list of values from 0 .. 32767
// Prepare random number generator with initial seed value
// and discard the first few data items in the sequence
srand(3);
for (int i = 0; i < 10; ++i)
rand();
/////////////////////////////////////////////////
// Greeting
cout << "Linked List Lab: Implemented by Mike Tindall" << endl;
cout << "Randomly generate list of " << N << " values in range 0-" << RANGE - 1 <<
" and convert into a sorted list" << endl << endl;
/////////////////////////////////////////////////
// Create initial "by position" data value list
SortListClass listbysorted,list1;
for (int i = 1; i <= N; ++i)
{
int val = rand() % RANGE; // produce next random number value
listbysorted.insert(val); // Put val into list at position i
}
// Output initial data list
printListClass("listbysorted", listbysorted);
//check = operator
list1 = listbysorted;
//print sorted list
/*for (int i = 1; i <= N; ++i)
{
int val = rand() % RANGE; // produce next random number value
listbyposition.insert(val); // Put val into list at position i
}*/
// Output initial data list
printListClass("list1 assigned with listbysorted", list1);
system("pause");
return(0);
}
--------------------------------------------------------------------------------------------------------------------------------
//function inserts elements in ascending order and checked assignment operator working
listbysorted: length=10 items
1: 2023
2: 2399
3: 5409
4: 8489
5: 16025
6: 17152
7: 19718
8: 21578
9: 23863
10: 28233
list1 assigned with listbysorted: length=10 items
1: 2023
2: 2399
3: 5409
4: 8489
5: 16025
6: 17152
7: 19718
8: 21578
9: 23863
10: 28233
. .