Create the chunklist class in c++ with the methods stated in the picture. Chunkl
ID: 3786517 • Letter: C
Question
Create the chunklist class in c++ with the methods stated in the picture. Chunklist is like a regular linked list, except each node contains a little fixed size array of elements instead of just a single element. Each node also contains its own "size" int to know how fullitis. The ChunkList will have the following features... The Chunktist object contains a head pointer to the first chunk, atail pointerto the last chunk and an int to track the logical size of the whole collection. When the size ofthe list is 0, the head and tailpointers are null. head size 16 next next next next size Each chunk contains a fixed size ItemTypeDarray, an int to track how fullthe chunk is, and a next pointer. There should be a constant ARRAY SLZE.8 that defines the fixed size of the array of each chunk. Elements should be added to the array starting at its 0index Elements in each little array should be kept in a contiguous block starting at 0(this will require shifting elements around in the little array at times) You may want to test ARRAY SIZE set to smaller values, but turn it in with ARRAY SLZE set to 8. The empty collection should be implemented as null head and tail pointers. Only allocate chunks when actually needed. ChunkList should implement the following methods similar to those describe on pages 136-138: o Make Empty o isFull (refers to the entire list, not an individual chunk node) o GetLength (refers to the total number of element, not the number of chunk nodes) o Puttem o Deleteltem o ResetList o GetNextltem The Puttem operation should add new elements at the end of the overall collection -ie, new elements should always go into the tailchunk. If the tail chunk is full, a new chunkshould be added and become the new tail. We are not going to trouble ourselves shifting things around to use empty space in chunks in the middle of the list. WeTlonly look at the tail chunk. The Deleteltem operation should look through each chunk array until the target element is found. Since the Chunklist can potentially have duplicates of the same elements, Deleteltem should just delete the first instance of the element. If the chunk node is empty after found removing the element, then the entire chunk should be removed from the link list. Do not use a dummynode because (a) it does not help the code much, and (b) dummy nodes are lame. Keep a single "size" variable for the whole list that stores the total number of cient data elements stored in the list. Similarly, keep a separate size in each chunkto know how full it is.Explanation / Answer
PROGRAM CODE:
/*
* ChunkList.cpp
*
* Created on: 04-Feb-2017
* Author: kasturi
*/
#include <iostream>
using namespace std;
#define ARRAY_SIZE 8
//strut to define each chunk
template <typename ItemType>
struct Chunk
{
ItemType values[ARRAY_SIZE];
int size;
Chunk *next;
};
//chunklist class
template <typename ItemType>
class ChunkList
{
private:
Chunk<ItemType> *head;
Chunk<ItemType> *tail;
int size;
public:
//constructor for the class
ChunkList()
{
head = NULL;
tail = NULL;
size = 0;
}
//Makes the entire list empty
void MakeEmpty()
{
head = NULL;
tail = NULL;
size = 0;
}
//returns true if all the chunks are full
bool isFull()
{
Chunk<ItemType> *temp = head->next;
while(temp != NULL)
{
if(temp->size < ARRAY_SIZE)
return false;
temp = temp->next;
}
return true;
}
//returns the sum of number of items in all the chunks
int GetLength()
{
//Chunk *temp = tail;
int length = 0;
while(tail != NULL)
{
length += tail->size;
tail = tail->next;
}
return length;
}
//returns the item at the given index
ItemType GetItem(int index)
{
int counter = 1;
Chunk<ItemType> *temp = head->next;
while(temp != NULL)
{
for(int i=0; i<temp->size; i++)
{
if(index == counter)
return temp->values[i];
else
{
counter++;
}
}
temp = temp->next;
}
return NULL;
}
//inserts the item to the tail
void PutItem(ItemType item)
{
if(head == NULL)
{
head = new Chunk<ItemType>;
head->size = 0;
head->values[head->size++] = item;
tail = new Chunk<ItemType>;
tail->size = 0;
tail->values[tail->size++] = item;
head->next = tail;
}
else if(tail->size < ARRAY_SIZE)
{
tail->values[tail->size++] = item;
}
else
{
Chunk<ItemType> *newChunk = new Chunk<ItemType>;
newChunk->size = 0;
newChunk->values[newChunk->size++] = item;
tail->next = newChunk;
tail = tail->next;
size++;
}
}
//deletes the first occurrence of the given item from the list
bool DeleteItem(ItemType item)
{
Chunk<ItemType> *temp = head->next;
while(temp != NULL)
{
for(int i=0; i<temp->size; i++)
{
if(temp->values[i] == item)
{
for(int j = i; j<temp->size-1; j++)
temp->values[j] = temp->values[j+1];
temp->size--;
return true;
}
}
temp = temp->next;
}
return false;
}
//prints the entire list to the console
//only for debugging
void printList()
{
int counter = 1;
Chunk<ItemType> *temp = head->next;
while(temp != NULL)
{
cout<<"Chunk "<<counter<<": ";
for(int i=0; i<temp->size; i++)
cout<<temp->values[i]<<" ";
cout<<endl;
counter++;
temp = temp->next;
}
}
//resets the current list with another list
void ResetList(ChunkList &list)
{
this->head = list.head;
this->tail = list.tail;
this->size = list.size;
}
//returns the next item to the given index
ItemType GetNextItem(int index)
{
return GetItem(index+1);
}
};
int main()
{
ChunkList<int> list;
for(int i=0; i<10; i++)
list.PutItem(i);
cout<<"After adding 0-9 ";
list.printList();
list.DeleteItem(3);
cout<<" After deleting 3 ";
list.printList();
int item = list.GetItem(4);
cout<<" Get item 4: "<<item;
ChunkList<int> list2;
list2.ResetList(list);
cout<<" New List ";
list2.printList();
cout<<" Next Item to 4 in new list: "<<list2.GetNextItem(4);
return 0;
}
OUTPUT:
After adding 0-9
Chunk 1: 0 1 2 3 4 5 6 7
Chunk 2: 8 9
After deleting 3
Chunk 1: 0 1 2 4 5 6 7
Chunk 2: 8 9
Get item 4: 4
New List
Chunk 1: 0 1 2 4 5 6 7
Chunk 2: 8 9
Next Item to 4 in new list: 5
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.