CMPT 125 Assignment 5
Question 1 –
Stack Class: 18 marks
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
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]
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.
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)
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]
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)
Assessment
The assignment is out of 36.
Submission
You should submit your assignment online to the CoursSys
submission server. Your solution should
consist of a single .pdf file, please read the documentation on site for
further information. The assignment is due by 11:59pm on Monday the 31st
of July.
John Edgar (johnwill@sfu.ca)