$24
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
