CS2134 Homework 7 Solved

Programming Part:

1.   Add the following methods[2] to the List class:

(a)   The copy constructor, List( const List & rhs ). This method must take O(n) time.

(b)   The destructor, ∼List( ). This method must take O(n) time.

(c)    The method front( ). It performs as stated in www.cplusplus.com/reference/forward_list/forward_list/front/ This method must take O(1) time.

(d)   The method merge( List & alist). It performs as stated in www.cplusplus.com/reference/forward_list/forward_list/merge/

(e)   The method remove adjacent duplicates( ). The method removes any element if it is adjacent to a node containing the same item[3]. Thus if the list contained a,a,a,b,b,c,c,c,c afterwards it would contain a,b,c. If the list contains a,b,a,b,a then afterwards it contains a,b,a,b,a (i.e. no change, since no items adjacent to each other were the same).

(f)    The method remove if( Predicate pred ) that performs as stated in www.cplusplus.com/reference/forward_list/forward_list/remove_if/ This method must run in O(n) time. Your method should call your method erase after.

A simplified version of the List class is in a file simple-list.cpp. We will test your code by including it in a driver program that uses the methods you implemented. You must test your code by writing and executing your own driver. Remember to hand in your driver code for any programming assignment.

2.   Efficiently implement[4] a queue class called Queue using a singly linked list, with no header node or tail node(i.e.

nodes that contain no data). Your class should have the methods: front, back, empty, enqueue, dequeue.

3.   (Extra Credit) Suppose that a doubly linked list class, Dlist is implemented with both a head and a tail node. Write a method[5] to remove all nodes containing x.

template<class Object

void DList::remove(const Object & x)

A simplified version of the DList class is in a file simple-doubly-linked-list.cpp.

Written Part:

1.   For the programming questions in 1 (except 1a)

•   draw pictures showing how the links change (or don’t change) for programming questions

•   provide the pseudo code for the methods

2.   For the static array implementation of the ADT stack with array size MAX = 4, show the conceptual representation of the contents of the stack for each line of code below:

Stack<char s;

s.push(’a’);

s.push(’b’);

s.push(’d’);

s.pop();

s.push(’c’);

s.pop();

s.pop();

3.   For the linked list implementation of the ADT stack, show the conceptual representation of the contents of the stack for each line of code below:

Stack<char s;

s.push(’a’);

s.push(’b’);

s.push(’d’);

s.pop();

s.push(’c’);

s.pop();

s.pop();

4.   For your linked list implementation of the ADT queue, show the conceptual representation of the contents of the stack for each line of code below:

Queue<char q;

q.enqueue(’a’);

q.enqueue(’b’);

q.enqueue(’d’);

q.dequeue();

q.enqueue(’c’);

q.dequeue();

q.dequeue();

5.   For your dynamic array implementation of the ADT queue where it initial size of the array is 4, show the conceptual representation of the contents of the stack for each line of code below:

Queue<char q;

q.enqueue(’a’);

q.enqueue(’b’);

q.enqueue(’c’);

q.dequeue();

q.enqueue(’d’);

q.dequeue();

q.dequeue();

q.enqueue(’e’);

q.enqueue(’f’);

q.enqueue(’g’);

q.enqueue(’h’);