Question

RE-POSTED - Computer Science staff, I need this question answered. It will determine a pass or a fail. Its very imortant that this and the other questions posted are answered 100% Thank you.

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.

Find the error(s) in the following code: (8, 9) template <class type> class strange 33. //Line //Line 2 Hi strange<int> sl; strange( type> s2; //Line 3 //Line 4

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 <string>
#include <iostream>

using namespace std; //needed 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 <= size){
       newNode = new Node; //new node
       newNode->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 < pos-1; i++){
               // Check that p points to a node
               // Note using exception handling should throw an exception here
               if(p == NULL){
                   return;
               }
               p = p->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 << "["; //Nice format!
   // Traverse the list
   while (p != NULL){
       cout << p -> data; // Print data
       p = p -> next; // Go to next node
       if (p != NULL){
           cout << ","; // Print a comma unless at the end of the list
       }
   }
   cout << "]"; // Don't print a newline - it might not be wanted
}

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 <iostream>
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 <class Type>

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

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 <class Type>

void LinkedList<Type>::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<int> creates a linked list of ints, and

LinkedList<string> 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