This is what i\'ve got so far, please correct if something is wrong and help me
ID: 3699904 • Letter: T
Question
This is what i've got so far, please correct if something is wrong and help me to finish this program.
Solution.h
#pragma once
#include
typedef int ListItem;
#define INVALID_LIST_ITEM (-1)
//
// TODO !!!
//
/*
Use this header to declare your classes. Do the actual function implementation in Solution.cpp.
It's not really necessary but it's a good habit for larger projects.
Ideally we'd put each class in its own header and source but these should be pretty simple and short.
*/
class List
{
//
// TODO !!!
//
List();
~List();
unsigned int GetSize();
bool AppendItem(ListItem);
bool PrependItem(ListItem);
ListItem GetItemAt(unsigned int);
void DeleteItemAt(unsigned int);
void Print();
/*
This is the abstract class from which our list implementations will derive.
You should add a constructor, destructor, and the following functions:
unsigned int GetSize() - returns the size of the list
bool AppendItem(ListItem) - adds the passed-in item to the end of the list. returns whether the append succeeded
bool PrependItem(ListItem) - adds the passed-in item to the beginning of the list. returns whether the prepend succeeded
ListItem GetItemAt(unsigned int) - returns the list item at the passed-in index or INVALID_LIST_ITEM for a bad index
void DeleteItemAt(unsigned int) - deletes the list item at the passed-in index
void Print() - prints out each item in the list from start to finish.
- this is the only function in List with an actual implementation.
- It should print out "I'm a list. My size is #", where '#' is the size of the list, followed by a newline.
*** Note that your function signatures might require certain other keywords such as const, virtual (hint, hint), etc. ***
*** In this and the following classes, make things public, protected, or private as appropriate. ***
*/
};
class ArrayList
{
//
// TODO !!!
//
public:
ArrayList(unsigned int);
~ArrayList();
void AppendItem(int);
void PrependItem(int);
void Print();
/*
ArrayList derives from List and implements it using a static array.
The constructor should take an unsigned int specifying the capacity of the array.
AppendItem and PrependItem should fail if the array is full.
Print should call the base Print function and then print the contents of the list in the format " [0, 1, 2, 3]"
(' ' is the tab character in case there's some other crazy, C++ way to do that and you're not familiar with my terminology).
Even though ListItem is typedef'd to be easy to change, you can assume for the print function that it's going to stay int.
*/
};
class LinkedList
{
//
// TODO !!!
//
/*
LinkedList derives from List and implements it using a linked list.
The constructor takes no arguments.
AppendItem and PrependItem really shouldn't fail unless you run out of memory or an asteroid destroys the earth.
Print should call the base Print function and then print the contents of the list in the format " [0, 1, 2, 3]"
(' ' is the tab character in case there's some other crazy, C++ way to do that and you're not familiar with my terminology).
Even though ListItem is typedef'd to be easy to change, you can assume for the print function that it's going to stay int.
*/
};
_____________________________________________________________________________________________________
Solution.cpp
#include "Solution.h"
//
// TODO !!!
//
/*
Put your actual implemetation in this file. See Solution.h for details.
*/
_________________________________________________________________________
mainTest.cpp
#include
#include
#include "Solution.h"
//
// TODO !!!
//
int main()
{
ArrayList a1 = ArrayList(10);
ArrayList a2 = ArrayList(5);
LinkedList l1 = LinkedList();
List *lists[] = {
&a1,
&a2,
&l1,
nullptr
};
int index = 0;
List *list = lists[0];
while(list != nullptr)
{
printf("GetSize: %d ", list->GetSize());
printf("AppendItem %s ", list->AppendItem(5) ? "succeeded" : "failed");
printf("AppendItem %s ", list->AppendItem(3) ? "succeeded" : "failed");
printf("AppendItem %s ", list->PrependItem(7) ? "succeeded" : "failed");
printf("GetSize: %d ", list->GetSize());
printf("AppendItem %s ", list->AppendItem(0) ? "succeeded" : "failed");
printf("AppendItem %s ", list->PrependItem(6) ? "succeeded" : "failed");
printf("AppendItem %s ", list->AppendItem(9) ? "succeeded" : "failed");
printf("AppendItem %s ", list->PrependItem(8) ? "succeeded" : "failed");
printf("GetSize: %d ", list->GetSize());
printf("GetItemAt: %d ", list->GetItemAt(4));
printf("GetItemAt: %d ", list->GetItemAt(8));
list->Print();
list = lists[++index];
}
printf("press enter to exit ");
getc(stdin);
return 0;
}
Explanation / Answer
//List.h
#pragma once
#include <stdio.h>
#include <vector>
typedef int ListItem;
#define INVALID_LIST_ITEM (-1)
class List
{
public:
List();
~List();
unsigned int GetSize();
virtual bool AppendItem(ListItem item);
virtual bool PrependItem(ListItem item);
virtual ListItem GetItemAt(unsigned int i);
virtual void DeleteItemAt(unsigned int i);
virtual void Print();
private:
std::vector<ListItem> items_;
};
class ArrayList : public List {
public:
ArrayList(unsigned int capacity);
bool AppendItem(ListItem item) override;
bool PrependItem(ListItem item) override;
ListItem GetItemAt(unsigned int i) override;
void DeleteItemAt(unsigned int i) override;
void Print() override;
private:
static unsigned int CAPACITY;
static unsigned int ITEMS_COUNT;
static ListItem* ITEMS;
};
struct Node {
ListItem data_;
Node* next_;
Node(ListItem data)
{
data_ = data;
}
};
class LinkedList : public List {
public:
Node* head;
Node* tail;
bool AppendItem(ListItem item) override;
bool PrependItem(ListItem item) override;
ListItem GetItemAt(unsigned int i) override;
void DeleteItemAt(unsigned int i) override;
void Print() override;
private:
unsigned int node_count_=0;
};
//List.cpp
#include "List.h"
#include <iostream>
#include <array>
using ::List;
using ::ArrayList;
using ::LinkedList;
List::List()
{}
List::~List()
{}
unsigned int List::GetSize()
{
return items_.size();
}
bool List::AppendItem(ListItem item)
{
auto old_size = items_.size();
items_.emplace_back(item);
return items_.size() > old_size;
}
bool List::PrependItem(ListItem item)
{
auto old_size = items_.size();
items_.insert(items_.begin(), item);
return items_.size() > old_size;
}
ListItem List::GetItemAt(unsigned int i)
{
return items_.at(i);
}
void List::DeleteItemAt(unsigned int i)
{
items_.erase(items_.begin() + i);
}
void List::Print()
{
std::cout << "I'm a list. My size is " << items_.size() << std::endl;
std::cout << "[ ";
for (const unsigned int item : items_)
{
std::cout << item + " ";
}
std::cout << " ]";
}
ArrayList::ArrayList(unsigned int capacity)
{
CAPACITY = capacity;
ITEMS = new ListItem[CAPACITY];
ITEMS_COUNT = 0;
}
bool ArrayList::AppendItem(ListItem item)
{
if (ITEMS_COUNT == CAPACITY)
return false;
ITEMS[ITEMS_COUNT] = item;
ITEMS_COUNT++;
return true;
}
bool ArrayList::PrependItem(ListItem item)
{
if (ITEMS_COUNT == CAPACITY)
return false;
for (unsigned int i = ITEMS_COUNT; i > 0; i++)
{
ITEMS[i] = ITEMS[i - 1];
}
ITEMS[0] = item;
return true;
}
ListItem ArrayList::GetItemAt(unsigned int i)
{
return ITEMS[i];
}
void ArrayList::DeleteItemAt(unsigned int i)
{
for (unsigned int start = i; start < ITEMS_COUNT-1; start++)
{
ITEMS[i] = ITEMS[i + 1];
}
ITEMS_COUNT--;
}
void ArrayList::Print()
{
std::cout << "I'm a list. My size is " << ITEMS_COUNT << std::endl;
std::cout << "[ ";
for (unsigned int i = 0; i < ITEMS_COUNT; i++)
{
std::cout << ITEMS[i] << " ";
}
std::cout << " ]";
}
bool LinkedList::AppendItem(ListItem item)
{
Node* temp = new Node(item);
if (!temp)
return false;
if (!head)
{
head = temp;
tail = temp;
}
else
{
tail->next_ = temp;
tail = temp;
}
node_count_++;
return true;
}
bool LinkedList::PrependItem(ListItem item)
{
Node* temp = new Node(item);
if (!temp)
return false;
if (!head)
{
head = temp;
tail = temp;
}
{
temp->next_ = head;
head = temp;
}
node_count_++;
return true;
}
ListItem LinkedList::GetItemAt(unsigned int i)
{
Node* tmp = head;
for (unsigned int index = 1; index <= i; index++)
{
tmp = tmp->next_;
}
return tmp->data_;
}
void LinkedList::DeleteItemAt(unsigned int i)
{
Node* tmp = head;
for (unsigned int index = 0; index < i; index++)
{
tmp = tmp->next_;
}
tmp->next_ = tmp->next_->next_;
}
void LinkedList::Print()
{
if (!head)
return;
Node* tmp = head;
std::cout << "I'm a list. My size is " << node_count_++ << std::endl;
std::cout << "[ ";
while (tmp)
{
std::cout << tmp->data_ << " ";
}
std::cout << " ]";
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.