CMPT 125 Assignment 5 Solution
You are to implement a Stack class with a LinkedList object as its
underlying data structure. The LinkedList class header file is shown below. Please read the
question carefully and only do what you are asked to – note that I am not asking you to implement the LinkedList
methods described in the LinkedList
header file that is shown below.
#include "Node.h"
class LinkedList{
private:
Node* head;
Node* tail;
// PRE:
// PARAM: current = node to
be searched
// target = value to be searched for
// POST: recursive helper
method for LLsearch
int searchHelper(Node*
current, int target);
public:
// Default (and only
constructor)
LinkedList();
// Destructor
~LinkedList();
// PRE:
// POST: Returns 1 if list
is empty, 0 otherwise
int empty();
// PRE:
// PARAM: value = value to
be appended
// POST: Adds a new element
to the tail of list
void
append(int value);
// PRE:
// PARAM: value = value to
be inserted
// POST: Adds a new element
to the head of list
void
prepend(int value);
// PRE: list is non-empty
// POST: Removes element
from head of list, and returns value
int removeHead();
// PRE: list is non-empty
// POST: Removes element
from tail of list, and returns value
int removeTail();
// PRE:
// POST: prints list
elements from head to tail
void
print();
// PRE:
// PARAM: list = list to be
inserted at end of calling object
// POST: concatenates list with
calling object and frees memory
// associated with list parameter
void
concatenate(LinkedList & list);
// PRE:
// PARAM: target = value to
be searched for
// POST: returns true if
target is in list, false otherwise
bool
search(int target);
};
a) Write a
C++ class definition for a Stack
class that stores integers as it would appear in the stack.h file. Your stack is to be
implemented by using a LinkedList
object to store the data. The Stack
class should have the following methods: [8 marks]
§
default
constructor - creates an empty stack
§
empty –
returns 1 if the stack is empty, 0 otherwise
§
push –
inserts its single integer parameter on the stack
§
pop –
removes and returns the integer at the top of the stack
Methods and attributes should
be made public or private as appropriate
#include "LinkedList.h"
class Stack{
private:
LinkedList ls;
public:
// Default (and
only constructor)
Stack();
// PRE:
// POST:
Returns 1 if stack is empty, 0 otherwise
bool empty();
// PRE:
// PARAM: value
= value to be inserted
// POST: Adds a
new element to the top of the stack
void push(int value);
// PRE: stack
is non-empty
// POST:
Removes and returns element from top of stack
int pop();
};
b) Write the
method implementations for each of the Stack
methods discussed in part (a) as they would appear in the stack.cpp file. Note that, as stated previously, that the stack is
to be implemented by using the LinkedList class
defined above – and you are to write the method implementations for the Stack
class not the LinkedList class. [10 marks]
#include "Stack.h"
// Default (and only constructor)
Stack::Stack()
{
}
// Destructor
Stack::~Stack()
{
}
// PRE:
// POST: Returns 1 if stack is empty, 0 otherwise
bool Stack::is_empty()
{
return
ls.empty();
}
// PRE:
// PARAM: value = value to be inserted
// POST: Adds a new element to the top of the stack
void Stack::push(int
value)
{
ls.prepend(value);
}
// PRE: queue is non-empty
// POST: Removes and returns element from top of stack
int Stack::pop()
{
return
ls.remove_head();
}
Question 2 –
Partition: 5 marks
Write an algorithm in
pseudo-code that partitions any array of integers around a pivot value. The algorithm
should organize the array such that all the elements less than or equal to the
pivot have indexes less than the index of the pivot element and all the
elements greater than the pivot have indexes greater than the index of the
pivot element. Your algorithm should use the first element of the array as the
pivot value. Your algorithm should run
in O(n) time.
e.g. If arr
= {6,1,7,5,8,9,3,2} its contents should be arranged so that: {values <= 6, 6, values > 6}, note that there are
many such arrays: {1,5,3,2,6,7,8,9},
{,1,2,5,3,6,9,7,8}, etc.
There are a number of different ways of achieving this.
Here is one, which uses two pointers to move inwards swapping items that are in
the wrong half of the array (elements less than pivot should be on the left,
elements greater than the pivot on the right). Note that the last thing it does
is put the pivot value in the correct position. A slightly less efficient, but
conceptually simpler, version would start by putting the pivot value in exactly
the right place.
// PRE: n > 0
// PARAM: arr
is array to be partitioned, n is length of arr
// POST: elements of arr are partitioned around the pivot value: {<pivot,
pivot, >pivot}
// pivot value is chosen as the first
value in the array
partition(arr[], int n)
small = 1
big = n-1
pivot = arr[0]
//
Swap values that are in wrong half of the array
while(small < big)
if(arr[small] > pivot)
//
Find value to swap with arr[small]
while(arr[big] > pivot and big
> small)
big--
end while
swap(arr, small, big) // swaps
elements at indexes small and big
big—
end if
small++
end while
//
Put pivot in correct position
if(arr[bit] > pivot)
swap(arr, 0, big-1);
else
swap(arr, 0, big);
end if
Question 3 –
Reverse List: 5 marks
Assume that a C LL_t struct
has the definition shown below.
typedef struct {
node_t*
head;
} LL_t;
And the node_t struct
has this definition.
typedef struct _node{
int data;
struct _node* next;
} node_t;
Write a C function to reverse the
nodes in a linked list. Your function should have the prototype shown below.
The contents of the list should be reversed by manipulating pointers in the
list, not by swapping values in nodes. The list should remain well formed after
the function has executed. Your function should not call any other linked list
functions – which is why they are not detailed in the question. [5 marks]
void LLreverse(LL_t* list)
Here is the conceptually simplest version of reverse. Repeatedly
go to the last node in the old list and make it the next node in a new list.
The biggest issue with this is that it is O(n2).
// PRE:
// PARAM: list = list that to be reversed
// POST: reverses the nodes in the list
void LLreverse(LL_t* list)
{
if(list->head != NULL){
node_t* temp_head = NULL;
node_t* temp_next= NULL;
node_t* current = list->head;
int tail = 0;
// Find
number of nodes in list
while(current->next != NULL){
tail++;
current = current->next;
}
// Make
new head
temp_head = current;
temp_next = temp_head;
tail--;
// Repeatedly insert end of list onto new list
for(; tail >= 0; tail--){
current = list->head;
//
Go to tail
for(int j = 0; j < tail; j++){
current = current->next;
}
temp_next->next = current;
temp_next = temp_next->next;
}
current->next = NULL;
list->head = temp_head;
}
}
And here is a more elegant recursive version that is O(n).
// PRE:
// PARAM: list = list that to be reversed
// POST: reverses the nodes in the list
void LLreverse2(LL_t*
list)
{
if(list->head != NULL){
LLreverse_list(list,
list->head);
}
}
// PRE:
// PARAM: list = list that to be reversed
// POST: helper function for reverse2
node_t* LLreverse_list(LL_t*
list, node_t* current)
{
// Reached tail
if(current->next == NULL){
list->head = current;
return current;
}
else{
node_t* parent = LLreverse_list(list,
current->next);
parent->next = current;
current->next = NULL;
return current;
}
}
Question 4 – Cycles: 8 marks
A cycle in a reference
structure such as a linked list occurs when a pointer in a node points to an
upstream or parent node. A linked list that contains a cycle is badly formed
as, for example, a traversal of the list results in an infinite loop. The
diagram below gives an example of a list that contains a cycle.
head-->17-->23-->42-->67-->71
Assume that a C LL_t struct
has the definition shown below.
typedef struct {
node_t*
head;
} LL_t;
And the node_t struct
has this definition.
typedef struct _node{
int data;
struct _node* next;
} node_t;
a) Write a
C code fragment that creates a cycle in the list by assigning the next pointer
of the n-th
node the address of the m-th node in the list. Assume that n and m are integers that
are declared and assigned values prior to your code fragment. [3 marks]
I don't have much to say about the code below, other than
it does what is stated above. I've included the declaration and assignment of n
and m.
int n = 5;
int m = 2;
node_t* nth = ll->head;
node_t* mth = ll->head;
for(int i = 1; i < n; i++){
nth = nth->next;
}
for(int i = 1; i < m; i++){
mth = mth->next;
}
nth->next = mth;
b) Write a
C function that returns 1 if its list parameter contains a cycle and 0 if it
does not. Your function should have the prototype shown below. Your function
should not use call any other linked list functions – which is why they are not
detailed in the question. [5 marks]
int LLcycle(LL_t* list)
There are a number of different ways of doing this.
You may have noted that this question did not require that the list be well
formed at the end of the process so a solution that trashes the list is
acceptable. A common solution is to store the addresses of nodes in another
data structure and check for duplicates. The version below uses two pointers
that traverse the list. One pointer is slow and the other is fast. If there is
a cycle the fast pointer will eventually catch up with the slow pointer.
// PRE:
// PARAM: list = list to check for a cycle
// POST: returns 1 if list contains a cycle, 0 otherwise
int LLcycle(LL_t* list)
{
if(list->head == NULL || list->head->next == NULL){
return 0;
}
node_t* slow = list->head->next;
node_t* fast = list->head->next->next;
if (fast == NULL) return 0;
while(fast != slow){
fast = fast->next;
if (fast == NULL) return 0;
fast = fast->next;
if (fast == NULL) return 0;
slow = slow->next;
}
return 1;
}
John Edgar (johnwill@sfu.ca)