PLEASE PROVIDE THE CORRECT CODE AND ALSO THE MAKEFILE. CSE 240 – Assignment 7 Ma
ID: 3715709 • Letter: P
Question
PLEASE PROVIDE THE CORRECT CODE AND ALSO THE MAKEFILE.
CSE 240 – Assignment 7
Maximum points: 50 pts
Topics:
? C/C++ Syntax
? Pointers
? Functions
? Dynamic Allocation of Memory
? Data Structures: Linked Lists
? Object Orientation
Linked List Specifications:
You are to create a Linked List data structure from scratch. This linked list should be Templated so that any data could be stored within it.
For a maximum of B on specifications – you can make the linked list only store Integers.
The primary goal of this assignment is to make a Linked List that you can use and re-use. The Linked List itself is the majority of the specifications grade.
Specifications Scoring Breakdown:
Templated Linked List + Josephus Problem – 100% of specifications Templated Linked List only – 80% of specifications
Integer Linked List + Josephus Problem – 80% of specifications Integer Linked List only – 70% of specifications
BIG GIANT NOTE – TEMPLATES AND FILES
When you use a templated type in C++ ALL templated code must be done in the .h file. This means that ALL of your methods will be defined in the .h file as well as your class.
You should still forward declare Classes above then Methods below.
Your .h file should have your LinkedList class and your Node class and the method definitions for both. Remember to use your :: operator correctly.
You will create a Linked List Class and a Node Class/Struct
The Linked List should contain the following methods in its public interface:
? Constructor
? Destructor
? AddToFront(T data) – create a node containing T data and add it to the front of the
list
? AddToEnd(T data) – create a node containing T data and add it to eh end of the list
? AddAtIndex(T data, int index) – create a node containing T data and add it to the
list at index, return boolean for success or failure (optional: you could also
return an integer with failure codes since this method can fail multiple ways)
? NextNode – Move the current pointer to the next node, wraps to front if it
? InsertAfterCurrent(T data) – Create a node containing T data and insert it after
? RemoveCurrent() – Delete the current item and return its contents
? RemoveAtIndex(int index) – delete the index # node in the list and return its
contents
? RemoveFromFront() – Delete first item and return its contents
? RemoveFromEnd() – Delete last item and return its contents
? RemoveFirst(T data) – find first instance of T data and remove it
? RemoveAll(T data) – find each instance of T data and remove it
? ElementExists(T data) – Returns a T/F if element exists in list
? Find(T data) – Look for data in the list, return a pointer to its node
? IndexOf(T data) – returns an index of the item in the list (zero-based)
? RetrieveFront – returns the data contained in the first node, does not delete it
? RetrieveEnd – returns the data contained in the last node, does not delete it
? Retrieve(int index) – returns the data contained in node # index, does not delete
it, returns null if index is out of bounds or data does not exist
? ToArray – Create an array from the contents of the list and return it
? Empty – Empty out the list, delete everything
? Length – How many elements are in the list
More methods private or public should be created as needed to facilitate the functionality of the Interface methods. If you feel your list needs more functionality, feel free to create it.
Node Class
? Constructor
? Destructor
? Getters & Setters
The node class should be fairly rudimentary. It should be templated so you can store anything in it.
Josephus Problem - Linked Lists
Description:
"There are people standing in a circle waiting to be executed. After the first man is executed, certain number of people are skipped and one man is executed. Then again, people are skipped and a man is executed. The elimination proceeds around the circle (which is becoming smaller and smaller as the executed people are removed), until only the last man remains, who is given freedom.
The task is to choose the place in the initial circle so that you survive (are the last one remaining)."
-- Wikipedia, http://en.wikipedia.org/wiki/Josephus_problem
Assume that the number of people, P, in the circle may be any number between zero
Assume that every Nth person around the circle is killed each turn, where N is an integer between one and twenty.
Specifications:
? Create an application in C++ that uses a linked list to represent the circle of people, numbered from 1 to P.
? Acquire the values P and N from the user at runtime via console input.
? Output the the individual that survives the mass execution.
Flash Version
? http://webspace.ship.edu/deensley/flash/JosephusProblem.html
There are several Java applet versions of this problem to check your work as you
debug.
? http://www.wou.edu/~burtonl/josephus.html
o This applet lets you choose how many people are in the circle and
Grading of Programming Assignment
The TA will grade your program following these steps:
(1) Compile the code. If it does not compile, If it does not compile you will
receive a U on the Specifications in the Rubric.
(2) The TA will read your program and give points based on the points allocated to each component, the readability of your code (organization of the code and comments), logic, inclusion of the required functions, and correctness of the implementations of each function.
Rubric:
What to Submit?
You are required to submit your solutions in a compressed format (.zip). Zip all files into a single zip file. Make sure your compressed file is labeled correctly - lastname_firstname7.zip.
For this home assignment, the compressed file MUST contain the following:
? Makefile
? README.txt – instructions for using the makefile
? lastname_firstname7.cpp – where you main/josephus problem is
? lastname_linkedList.h – where your linked list/node code is
? any other code/library files you create or use for the sake of the
assignment
No other files should be in the compressed folder.
If multiple submissions are made, the most recent submission will be graded, even if the assignment is submitted late.
Explanation / Answer
main.cpp
#include <iostream>
#include "LinkedList.h"
using namespace std;
template <class T>
void printArray(T* array, int size);
int main(){
LinkedList<int> *foo = new LinkedList<int>();
//** EMPTY TESTING **//
cout << "Test member functions on empty lists: " << endl;
cout << "Is Empty: ";
if(foo->Empty())
{
cout << "List is Empty." << endl;
} else {
cout << "List is not Empty." << endl;
}
cout << "Next Node: ";
foo->NextNode();
cout << "Remove from front: " << foo->RemoveFromFront() << endl;
cout << "Add at Index 2: ";
foo->AddAtIndex(1, 2);
cout << "AddToFront: ";
foo->AddToFront(10);
foo->toString();
cout << "RemoveFromFront: " << foo->RemoveFromFront() << endl;
cout << "toString: ";
foo->toString();
cout << "AddToEnd: ";
foo->AddToEnd(10);
cout << "RemoveFromEnd: " << foo->RemoveFromEnd()<< endl;
foo->toString();
cout << "Remove at Index 2: ";
foo->RemoveAtIndex(-1);
cout << "RemoveAll: ";
foo->RemoveAll(2);
cout << "ElementExists: " << foo->ElementExists(2)<< endl;
cout << "+========Build a list for testing: " << endl;
foo->AddToFront(4);
cout << "Add 4 to front: "; //[4]
foo->toString();
foo->AddToEnd(6);
cout << "Add 6 to end: "; //[4, 6]
foo->toString();
foo->NextNode();
foo->InsertAfterCurrent(4); //[4,6,4]
cout << "Move current to nextNode and add 4: ";
foo->toString();
foo->RemoveCurrent();
cout << "Remove current: "; //[4,4]
foo->toString();
cout << "Add 6 At Index 1: "; //[4,6,4]
foo->AddAtIndex(6,1);
foo->toString();
/* build list */
//[4,6,4]
cout << "Add 7 at index 2: ";
foo->AddAtIndex(7,2);
foo->toString();
cout << "From End: " << foo->RetrieveEnd() << endl;
cout << "Add 5 at end: ";
foo->AddToEnd(5); //[4, 6, 7, 4, 5]
foo->toString();
cout << "From End: " << foo->RetrieveEnd() << endl;
cout << "From Front: " << foo->RetrieveFront()<< endl;
cout << "Retrieve 2: " << foo->Retrieve(2) << endl;
cout << "Remove all 4's: "; foo->RemoveAll(4);
cout << "From Front: " << foo->RetrieveFront()<< endl;
foo->toString();
cout << "Insert 4 After Current: "; foo->InsertAfterCurrent(4);
foo->toString();
foo->NextNode();
cout << "Insert 11 After Current: "; foo->InsertAfterCurrent(11);
foo->toString();
foo->NextNode();
foo->NextNode();
cout << "Insert 38 After Current: "; foo->InsertAfterCurrent(38);
foo->toString();
cout << "Remove from end: " << foo->RemoveFromEnd()<< endl;
foo->toString();
cout << "Remove first 7: ";
foo->RemoveFirst(7);
foo->toString();
cout << "Remove First 31: ";
foo->RemoveFirst(31);
foo->toString();
delete foo;
return 0;
}
template <class T>
void printArray(T* array, int size)
{
cout << "Size: " << size << endl;
for(int i = 0; i < size; i++)
{
cout << *array << endl;
array += 1;
}
}
============================================================
//LinkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <stdlib.h>
#include <iostream>
template<class T>
class Node
{
private:
T data;
Node<T> *next;
public:
inline Node()
{
next = NULL;
}
inline Node(T value)
{
data = value;
next = NULL;
}
inline ~Node()
{
next = NULL;
}
/* Sets the next to point to the argument node */
inline void setNext(Node<T> *node)
{
this->next = node;
}
inline Node<T>* getNext()
{
return this->next;
}
/* returns the data of this node */
inline T getData()
{
return this->data;
}
};
template <class T>
class LinkedList
{
private:
Node<T> *head;
Node<T> *current;
Node<T> *tail;
/* Looks for data in the list, return a pointer to its node*/
Node<T>* Find(T data);
/* Returns index of first occurance of element in list */
/* Returns -1 if element not found. */
int IndexOf(T data);
/* moves "current" to the next node. Use when deleting a node, pass in the
/* the node that's being deleted */
void ifCurrent(Node<T> *removing);
void deleteNode(Node<T>* deleteMe);
public:
/* Empty Constructor */
LinkedList();
/* Data Constructor */
LinkedList(T data);
/* Destructor */
~LinkedList();
/* create a node containing T data and add it to the front of the list */
void AddToFront(T data);
/* create a node containing T data and add it to eh end of the list*/
void AddToEnd(T data);
/* create a node containing T data and add it to the list at index,
return boolean for success or failure (optional: you could also return
an integer with failure codes since this method can fail multiple ways)*/
bool AddAtIndex(T data, int index);
/* Move the current pointer to the next node, wraps to front if it
navigates past the end*/
void NextNode();
/*Create a node containing T data and insert it after wherever
the current pointer is pointing */
void InsertAfterCurrent(T data);
/* Remove current and return data */
T RemoveCurrent();
/* delete the index # node in the list and return its contents*/
T RemoveAtIndex(int index);
/* Delete first item and return its contents*/
T RemoveFromFront();
/* Delete last item and return its contents*/
T RemoveFromEnd();
/* find first instance of T data and remove it*/
void RemoveFirst(T data);
/* find each instance of T data and remove it*/
void RemoveAll(T data);
/* Returns a T/F if element exists in list*/
bool ElementExists(T data);
/* Returns the data contained in the first node */
T RetrieveFront();
/* Returns the data contained in the last node */
T RetrieveEnd();
/* Returns the data contained at the node at the given index */
T Retrieve(int index);
/* Create an array from the contents of the list and return it */
T* ToArray();
/* Empty out the list, delete everything*/
bool Empty();
/* How many elements are in the list */
int Length();
/* Prints the list in an array string: [0, 1, 2...] */
void toString();
};
template <class T>
LinkedList<T>::LinkedList()
{
head = tail = current = NULL;
}
template <class T>
LinkedList<T>::LinkedList(T data)
{
head = new Node<T>(data);
tail = current = head;
}
template <class T>
LinkedList<T>::~LinkedList()
{
Node<T> *butcher = head;
while(butcher->getNext() != NULL){
butcher = butcher->getNext();
head->setNext(NULL);
head = NULL;
head = butcher;
}
std::cout << "List deleted." << std::endl;
butcher = NULL;
}
template <class T>
void LinkedList<T>::AddToFront(T data)
{
//Create a new node with T data.
Node<T> *temp = new Node<T>(data);
//If it's empty, set all Nodes to it.
if(Empty())
{
head = tail = current = temp;
//Make the temp node with the data link to head.
//Make that new node the head.
} else {
temp->setNext(head);
head = temp;
}
}
template <class T>
void LinkedList<T>::AddToEnd(T data)
{
//If list is empty, call addToFront
if(Empty())
{
AddToFront(data);
//List is not empty, use the tail to add a new node
} else {
Node<T> *temp = new Node<T>(data);
//add new node to the end.
tail->setNext(temp);
//make the new node tail.
tail = tail->getNext();
}
}
template <class T>
bool LinkedList<T>::AddAtIndex(T data, int index)
{
/* Call AddAtEnd if this ends up just adding it
at the end. This will ensure tail behavior */
if(index == Length())
{
AddToEnd(data);
return true;
//If the index is within the range of indices..
} else if (index < Length() && index > 0) {
//Create a pointer node at head.
Node<T> *p = head;
//Create a node wth T data.
Node<T> *temp = new Node<T>(data);
//Start the counter at 1 (we're not at head)
int counter = 1;
//Move along the list until we're at the index
while(counter < index)
{
p = p->getNext();
counter++;
}
//Set Temp's next to the next node after p.
temp->setNext(p->getNext());
//p's next set to temp.
p->setNext(temp);
return true;
} else if (index = 0){
AddToFront(data);
return true;
} else {
std::cout << "Index out of bounds." << std::endl;
return false;
}
}
template <class T>
void LinkedList<T>::NextNode()
{
//If the list is empty..
if(Empty())
{
std::cout << "List is Empty." << std::endl;
} else {
//If next is null, move to head.
if(current->getNext() == NULL)
current = head;
//otherwise, move to the next node
else
current = current->getNext();
}
}
template <class T>
void LinkedList<T>::InsertAfterCurrent(T data)
{
//If list is empty just add to front.
if(Empty())
{
AddToFront(data);
//if current == tail, then add to end.
} else if (current == tail){
AddToEnd(data);
//Otherwise, Insert new node after current index.
} else {
Node<T> *temp = new Node<T>(data);
temp->setNext(current->getNext()); // set temp's next to the node after current.
current->setNext(temp); //set current's 'next' to the temp.
}
}
/* Remove current and return data */
/* Returns -1 if fails */
template <class T>
T LinkedList<T>::RemoveCurrent()
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return -1;
}
if(current->getNext() == NULL)
{
T data = current->getData();
RemoveFromEnd();
current = head;
return data;
}
if(current == head)
{
T data = current->getData();
RemoveFromFront();
current = head;
return data;
}
T data = current->getData();
//Next node to loop all the way around and stop at the node before "current".
int i = 1;
while(i < Length())
{
NextNode();
i++;
}
//Set temp equal to current's next.
Node<T>* temp = current->getNext();
//set current to temps next. cutting off temp
current->setNext(temp->getNext());
//No more temp.
temp = NULL;
NextNode(); //move to the next spot
return data;
}
/* Returns -1 if fails */
template <class T>
T LinkedList<T>::RemoveAtIndex(int index)
{
T data;
//If the index is too big or below 0
if(index >= Length() || index < 0)
{
std::cout << "Index out of bounds." << std::endl;
return -1;
}
//If the index is just the one at the end..
if(index == Length()-1){
data = RemoveFromEnd();
//If the index is 0...
} else if (index == 0)
{
data = RemoveFromFront();
//If it's greater than 0 and we got this far...
} else if (index > 0){
Node<T> *temp = head;
//move to index - 1.
for(int i = 1; i < index; i++)
{
temp = temp->getNext();
}
//Create a new pointer equal to the node to be removed.
Node<T> *removeMe = temp->getNext();
//grab the data.
data = removeMe->getData();
//move current if current is there.
ifCurrent(removeMe); // move current if he's on this node
temp->setNext(removeMe->getNext());
removeMe->setNext(NULL); //Poof. Gone.
removeMe = NULL;
} else {
std::cout << "Input not understood." << std::endl;
return -1;
}
return data;
}
/* Returns -1 if fails */
template <class T>
T LinkedList<T>::RemoveFromFront()
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return -1;
} else {
//Grab the data
T data = head->getData();
//new node at head.
Node<T> *temp = head;
ifCurrent(temp);
//move the head to the next node
head = head->getNext();
//delete the first node.
temp->setNext(NULL);
temp = NULL;
return data;
}
}
/* Returns -1 if fails */
template <class T>
T LinkedList<T>::RemoveFromEnd()
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return -1;
} else {
T data = tail->getData();
Node<T> *temp = head;
//If theres only 1 element, remove from front.
if(temp->getNext() == NULL)
{
RemoveFromFront();
return data;
}
while(temp->getNext() != tail)
{
temp = temp->getNext();
}
ifCurrent(tail);
//Element before last set's the next = to NULL.
temp->setNext(NULL);
//Move the tail back one node to temp.
tail = temp;
return data;
}
}
template <class T>
void LinkedList<T>::RemoveFirst(T data)
{
Node<T> *deleteMe = Find(data);
if(deleteMe != NULL)
{
deleteNode(deleteMe);
} else {
std::cout <<"Element does not exist" << std::endl;
}
}
template <class T>
void LinkedList<T>::RemoveAll(T data)
{
if(Empty()){
std::cout << "List is Empty." << std::endl;
} else {
while(ElementExists(data))
{
RemoveAtIndex(IndexOf(data));
}
}
}
template <class T>
bool LinkedList<T>::ElementExists(T data)
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return false;
}
//First one?
if (head->getData() == data)
{
return true;
}
//Searching...
Node<T> *temp = head;
while(temp->getNext() != NULL)
{
temp = temp->getNext();
if(temp->getData() == data){
return true;
}
}
// couldn't find it
return false;
}
template <class T>
Node<T>* LinkedList<T>::Find(T data)
{
//Empty Check:
if(Empty())
{
return NULL;
}
//Start searching:
Node<T> *temp = head;
while(temp->getNext() != NULL)
{
temp = temp->getNext();
if(temp->getData() == data)
{
return temp;
}
}
return NULL;
}
/* Returns index of first occurance of element in list */
/* Returns -1 if element not found. */
template <class T>
int LinkedList<T>::IndexOf(T data)
{
//Empty list?
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return -1;
}
//Is it the head?
if(head->getData() == data)
{
return 0;
}
//Nope, get searching...
Node<T> *temp = head;
int counter = 1;
while(temp->getNext() != NULL)
{
temp = temp->getNext();
if(temp->getData() == data)
{
return counter;
}
counter++;
}
return -1;
}
template <class T>
T LinkedList<T>::RetrieveFront()
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return 0;
}
return head->getData();
}
template <class T>
T LinkedList<T>::RetrieveEnd()
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return 0;
}
return tail->getData();
}
template <class T>
T LinkedList<T>::Retrieve(int index)
{
if(Empty())
{
std::cout << "List is Empty." << std::endl;
return 0;
}
Node<T> *p = head;
if(index == 0)
{
return head->getData();
}
while(index > 1)
{
p = p->getNext();
index--;
}
T value = p->getNext()->getData();
return value;
}
template <class T>
T* LinkedList<T>::ToArray()
{
T* array;
array = new T[Length()];
if(Empty())
{
std::cout << "This list is empty" << std::endl;
return NULL;
} else {
Node<T> *collector = head;
//T array[Length()];
for(int i = 0; i < Length(); i++)
{
array[i] = collector->getData();
collector = collector->getNext();
}
return array;
}
}
template <class T>
bool LinkedList<T>::Empty()
{
return (head==NULL ? true:false);
}
template <class T>
int LinkedList<T>::Length()
{
int counter = 0;
Node<T> *p = head;
if(p == NULL){
return 0;
}
while(p->getNext()!= NULL){
p = p->getNext(); //set p equal to what is next
counter++;
}
return counter+1; //Add one to account for indexing starting at 0.
}
template <class T>
void LinkedList<T>::ifCurrent(Node<T> *removing)
{
if(removing == current)
{
if(current->getNext() == NULL)
{
current = head;
} else {
current = current->getNext();
}
}
}
template <class T>
void LinkedList<T>::deleteNode(Node<T>* deleteMe)
{
T data = deleteMe->getData();
RemoveAtIndex(IndexOf(data));
}
template <class T>
void LinkedList<T>::toString()
{
if(Empty())
{
std::cout << "List is empty." << std::endl;
} else {
T* array = ToArray();
std::cout << "[" << *array;
array += 1;
for(int i = 1; i < Length(); i++)
{
std::cout << ", " << *array;
array += 1;
}
std::cout << "]" << std::endl;
}
}
#endif
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.