Assignment #3 Solution

Exercise 1: Linked lists




Let consider the following template of linked lists




template <typename T




class LinkedList{




private:




Declare a structure for the list struct ListNode



{




T value;




struct ListNode *next;




};




ListNode *head;




// List head pointer



public:




LinkedList(void) // Constructor



{ head = NULL; }




LinkedList(T);




~LinkedList(void); // Destructor




void appendNode(T);




T& top();




T& pop_front();




bool empty();




void insertNode(T);




void deleteNode(T, bool);




void displayList(void);




int count(T);




int length();




1
void sortBySelection();




void sortByInsertion();




ListNode *getNode(int);




T& get(int);




void clear();




void reverse();




};




Write an algorithm and a C++ program for each of the following methods for this




LinkedList class:




LinkedList(T info): the constructor to create a linked a list which first node contains the value info and the next pointer is null.



~LinkedList(): a destructor that remove all elements of the linked list.



void appendNode(T): a method to append a node at the end of the linked list.



T& top(): to get the first element of the linked list.



T& pop_front(): to remove the first node of the linked list and to return its value.



bool empty(): to test if the linked list is empty or no.



void insertNode(T info): to insert a node in the beginning of the linked list.



void deleteNode(T info, bool removeAll): to delete a node from the linked list, if removeAll is false, all occurrence of info will be removed, otherwise, only the first occurrence of info will be removed.



void displayList(void): to display all elements of the linked list



int count(T val): to count the occurrence of val in the linked list.



int length(): to count the number of nodes in the linked list.



ListNode *getNode(int i): to get the i-th node of the linked list



T& get(int i): to get element of the i-th node of the linked list.



void clear(): to remove all elements of the linked list



void sortBySelection(): to sort the linked list using the principle of sorting by selection.









2




void sortByInsertion(); to sort the linked list using the principle of sorting by insertion.



void reverse(): to reverse the elements of the linked list. Please, do not use an intermediary linked list to reverse the current linked list.



Hint: some method can reuse other methods, like for example you can reuse the method clear() in the destructor, and void insertNode(T info) in the constructor LinkedList(T).




Exercise 2: Dynamic arrays




Let consider the following template of dynamic arrays




template <typename T




Class DynamicArray{




T *array;




int size; //current size of the array




int capacity; // the total capacity to be allocated for the array




public:




DynamicArray(int Capacity); //Constructor




DynamicArray(); // Desctructor void add(T elem);



void remove(T elem);




};




Complete the constructor



public DynamicArray::DynamicArray(int Capacity){































3




}




Complete the desctructor to destroy the array. DynamicArray:: ~ DynamicArray(){












}




Complete the function add to insert an elem in the dynamic array. void DynamicArray::add(T elem){










































}




Complete the function remove to search for an element and to delete it from the dynamic array.



void DynamicArray::remove(T elem){




















































} // End of remove













4




Exercise 3: Stacks




Implement the stacks using the two data structures dynamic array and linked lists. You can reuse the linked list class in the exercise 1 and the template of dynamic arrays in the exercise 2. For that purpose, you have to create a class called Stack_DynamicArray for the dynamic arrays based implementation, and another class called Stack_LinkedList for the linked lists based implementation.




Exercise 4: Queues




Implement the queues using the three data structures dynamic arrays, circular dynamic arrays and linked lists. You can reuse the linked list class in the exercise 1 and the template of dynamic arrays in the exercise 2. For that purpose, you have to create a class called Queue_DynamicArray for the dynamic arrays based implementation, another class called Queue_Circular_DynamicArray for the circular dynamic arrays implementation, and another class called Queue_LinkedList for the linked lists based implementation.













































































































5