13 - Template C++ Advance

Please Only answer assignment if your code is 100%. When pasteing your code use text so I may copy and paste into visual studio. The code and questions must be answered 100% correct and works. Thank you.

Programming Assignment

Convert the int linked list class to a template class. Use attached files: LinkedList.h and LinkedList.cpp.

Test your linked list template by writing a test program that creates an int linked list and a string linked list, and uses each of the LinkedList methods at least once.

LinkedList.cpp

// Implementation of the LinkedList class

//#include "Stdafx.h" #include "LinkedList.h" #include #include

using namespace std; /eeded for cout, cin to be recognised

// Default constructor LinkedList::LinkedList(){ head = NULL; size = 0; //Don't forget to do this!!! }

/* Copy constructor to copy an existing list. Note that the compile * will generate a copy constructor automatically. However, this * constructor only creates a SHALLOW COPY (so would only copy the * size and head variables). In this case this would NOT CREATE A * NEW LIST, just a new reference to one list. It is therefore * necessary to write a constructor that makes a DEEP COPY.*/

/* Also note the parameter. C++ functions use pass-by-value by * default. This means that the functions make copies of the given * arguments. This is inefficient (particularly for large objects). * Therefore it is normal to pass the address (using &) of the parameter, * but, if the parameter should not be changed, it is good practice to * make it const, which prevents it from being changed.*/ LinkedList::LinkedList(const LinkedList& lst){ if (lst.head == NULL){ head = NULL; size = 0; } else{ // Copy first node and assign head /* OK, what's with the '->'? The -> operator accesses the attribute * or method of the object (or struct) that is refererred to by a * pointer. So "head -> data" is the contents of the data variable * of the object that head points to. Note that this is synonomous * with "(*head).data" but the latter syntax is ugly and confusing and * is therefore rarely used. */ head = new Node; head->data = lst.head->data; /* Now copy the rest of the list. To do this we'll need to create two * temporary pointers, one to go through the old list, one node at a * time, and one to keep pace in the new list, creating new nodes. */ Node *pNewNode = head; Node *pOldNode = lst.head->next; // Repeat until the entire list is copied while (pOldNode != NULL){ pNewNode->next = new Node; pNewNode = pNewNode->next; pNewNode->data = pOldNode->data;; pOldNode = pOldNode->next; } pNewNode->next = NULL; size = lst.size; } }

/* The destructor is responsible for deleting any memory that was dynamically * allocated by an object. If there is no such memory no destructor needs to * be created (the compiler automatically creates one). Because this class * uses pointers to create new Nodes it is necessary to write a destructor. * Destructors are identified by the '~' preceding the class name. There can * be only one destructor for a class, and it cannot have parameters. */ LinkedList::~LinkedList(){ removeAll(); }

/**************************************************************************/ // LinkedList Operations

// Adds a node to the start of the list, making it the new head void LinkedList::add(int x){ Node *p = new Node; //temporary node // Assign appropriate values to the new node p -> data = x; p -> next = head; // Make the head point to the new node head = p; size++; }

// Inserts a new node at the given position (or index) in the list void LinkedList::insertAt(int pos, int x){ Node *p; Node *newNode; // Check that pos is a valid index if (pos data = x;

// Deal with case when item is to be inserted at the head of the list if (pos == 0){ newNode->next = head; head = newNode; }// if(pos == 0) else{ p = head; // Move to position BEFORE insertion point for(int i = 0; i next; }//for // Insert node newNode->next = p->next; p->next = newNode; }//else (pos != 0) size++; }//else (pos >= size) do nothing }

// Removes the first node containing the given data, returns true // iff data is found (and deleted). bool LinkedList::remove(int x){ Node *p = head; Node *temp; // Check to see if the list exists if (head == NULL){ return false; } // Check to see if target is at the head of the list else if (head->data == x){ head = head->next; delete p; //currently assigned head size--; return true; } // Otherwise iterate through list else{ while(p->next != NULL){ // Check next node for target if(p->next->data == x){ temp = p->next; p->next = p->next->next; size--; delete temp; return true; } p = p->next; } } return false; }

// Empties the list by deleting each node, starting at the head void LinkedList::removeAll(){ Node *p = head; // Traverse the list deleting nodes while (p!= NULL){ head = head->next; // Mustn't "lose" the next node delete p; // De-allocate memory p = head; // Go to next node } head = NULL; size = 0; }

// Prints the entire list (head first) to the screen. /* Note that there is some debate about whether or not this type of * method belongs in a class. The argument (briefly) is that a class * shouldn't be responsible for its own display as it cannot foresee * how it is to be displayed. */ void LinkedList::printList(){ Node *p = head; cout data; // Print data p = p -> next; // Go to next node if (p != NULL){ cout

LinkedList.h

// Header file for linked list class

class LinkedList{ public: // Constructors and Destructors /* Generally every class should have at least two construtors, a * default constructor and a copy constructor that creates a copy * of the given object*/ LinkedList(); //default construtor LinkedList(const LinkedList& lst); //copy constructor /* Every class should have a destructor, which is responsible for * cleaning up any dynamic memory allocation performed by the class. * Note the special syntax for the destructor */ ~LinkedList();//destructor // PRE: // POST: A new node containing the given data is inserted at the front // of the list // PARAM: data is the data to be stored void add(int data);

// PRE: // POST: A new node containing the given data is inserted at the given // position in the list // PARAM: pos specifies the (index) position to insert the new node // data is the data to be stored void insertAt(int pos, int data); // PRE: // POST: The first incidence of the given data is removed from the list. // Returns true if data is found (and removed), false otherwise // PARAM: data specifies the data to be removed from the list bool remove(int data ); // PRE: // POST: Empties the list, freeing up dynaically allocated memory // PARAM: void removeAll();

// PRE: // POST: Prints the contents of the list to the screen, in order // PARAM: void printList();

private: /* A struct contains data variable (which are accessed using dot * notation in the same way that object methods or attributes are * accessed). Structs cannot have methods.*/ // List node struct Node { int data; //list data Node *next; //pointer to next item in the list };

Node *head; //Pointer to the first node in the list int size; //Records the number of nodes in the list };

template_test.cpp

#include "LinkedList.h"

#include using namespace std;

int main() {

//Add your test code here system("pause"); return 0;

}

Resources that help:

Creating a Template

C++ allows a programmer to create templates that can be instantiated. A template allows objects to be created that can store (or use) data of any type.

In this lab you will convert the int linked list class to a template class. Use attached files:

LinkedList.h

LinkedList.cpp

To convert the class to a template class you must:

Put the entire class (the .h file class definition, and the .cpp file method implementations) in one .h file. For this lab, put the entire class into LinkedList.h

Preface the template class definition and each template member function implementation with this line: template

The class qualifier (LinkedList::) that appears before a method name in each implementation, should be replaced by LinkedList::

Whenever the type that the class contains (int in our case) is referred to it should be replaced with the word Type

For example here is the add method before and after these changes:

void LinkedList::add(int x){ 

 Node *p = new Node; //temporary node 

 // Assign appropriate values to the new node 

 p -> data = x; 

 p -> next = head; 

 // Make the head point to the new node 

 head = p; 

} 

and the "templated" version

template  

void LinkedList::add(Type x){ 

 Node *p = new Node; //temporary node 

 // Assign appropriate values to the new node 

 p -> data = x; 

 p -> next = head; 

 // Make the head point to the new node 

 head = p; 

} 

To use your linked list template class in a program you need to specify what type is to be stored:

LinkedList creates a linked list of ints, and

LinkedList creates a linked list of strings

Testing

Test your linked list template by writing a test program in template_test.cpp that creates an int linked list and a string linked list, and uses each of the LinkedList methods at least once.

Additional Resource

https://www.youtube.com/watch?v=gefYtPeLB7o