Download the A5.zip file containing some C code that you require for this assignment. Extract the contents into your assignment directory; you should find the following files:
The list and stack implementations are slightly modified versions of those discussed during the lectures. In particular, their header files include the full definitions of the list struct, stack struct, and node struct. This allows you to create new functions that operate on lists and stacks without changing the provided code. Also, the add_capacity function is declared in list.h so that you can use the function in Question 2.
The included Makefile will help you compile your files.
1. list_remove_all
Edit the files list_utils.h and list_utils.c. All of your code for Questions 1 and 2 should go into these files. You should add an include guard in the header file.
Create a function list_remove_all:
bool list_remove_all(list *t, int elem)
that removes all occurrences of elem from the list. true is returned if elem is successfully removed from the list, and false is returned otherwise.
The function should remove all occurrences of elem by iterating over the list exactly once so that the worst-case complexity of the function is in O(n) where n is the number of elements in the list.
Your function should not call the function list_remove because this results in the worst-case complexity being in O(n22) (can you see why?).
Given the list
[4, 3, 2, 1, 2, 3, 4]
removing all occurrences of 5 leaves the list unchanged and returns false (because 5 does not occur in the list).
Given the list
[4, 3, 2, 1, 2, 3, 4]
removing all occurrences of 4 changes the list to
[3, 2, 1, 2, 3]
and returns true.
Given the list
[4, 4, 4, 4, 4, 3, 4]
removing all occurrences of 4 changes the list to
[3]
and returns true.
Special cases
If t is NULL, then your function should do nothing and return false.
2. list_insertm
Create a function list_insertm
bool list_insertm(list *t, size_t index, int elem, size_t m)
that inserts m copies of the value elem into the list pointed at by t starting at the index index. Inserting at index = size of the list is equivalent to adding at the end of the list.
If the list has sufficient capacity to hold the inserted m elements then the worst-case complexity of the function should be in O(m+n).
Your function should not call the function list_insert because this results in the worst-case complexity being in O(m+mn) when the list has sufficient capacity to hold the inserted m elements (can you see why?).
You have access to the add_capacity function which expands the capacity of a list's array.
Given the list
[4, 3, 2, 1, 2, 3, 4]
inserting m = 5 copies of elem = -1 at index index = 3 modifies the list t so that it becomes:
[4, 3, 2, -1, -1, -1, -1, -1, 1, 2, 3, 4]
Special cases
If t is NULL, then your function should do nothing and return false.
If index is less than zero or greater than the size of t then your function should do nothing and return false.
Your function should return false if memory for the inserted elements cannot be successfully allocated.
3. stack_contains
Edit the files stack_utils.h and stack_utils.c. All of your code for Questions 3-5 should go into these files. You should add an include guard in the header file.
Create a function called stack_contains:
bool stack_contains(const stack *s, const void *val, stack_eq_func eq)
where
and returns true if the stack has an element equal to val. For example:
stack *s1 = stack_init();
stack_push(s1, "a");
stack_push(s1, "b");
stack_push(s1, "c");
the stack s1 has a string element equal to "b" but does not have a a string element equal to "z".
Our stack implementation is generic; thus, the elements are stored as void pointers. As the implementer of the stack_contains function, you do not know how the user defines equality for their element type; thus, the user must supply a pointer to a function that compares two elements for equality. You should define a typedef stack_eq_func for a pointer to an appropriate comparison function in the stack_utils.h header file (see stack.h for examples of typedef statements).
Special cases
Searching an empty stack or a non-existant stack should return false.
4. stack_equals
Create a function called stack_equals:
bool stack_equals(const stack *s1, const stack *s2, stack_eq_func eq)
where
and returns true if the stacks are equal, and false otherwise. Two stacks are equal if they contain identical sequences of equal elements; empty stacks are considered to be equal. For example, the stacks *s1 and *s2 are equal to each other, but are not equal to stack *s3:
stack *s1 = stack_init();
stack_push(s1, "a");
stack_push(s1, "b");
stack_push(s1, "c");
stack *s2 = stack_init();
stack_push(s2, "a");
stack_push(s2, "b");
stack_push(s2, "c");
stack *s3 = stack_init();
stack_push(s3, "d");
5. Create a function of type stack_eq_func
Create the function
bool eq_double(const void *val1, const void *val2)
that returns true if the double value pointed at by val1 is equal to the double value pointed at by val2, and returns false otherwise.
list.h
#ifndef LIST_H
#define LIST_H
#include < stdbool.h >
/**
* Name of the provided list type.
*/
typedef struct list list;
/**
* The list struct made visible so that other users can
* extend the functionality of the list.
*/
struct list {
/**
* The array holding the elements of the list.
*/
int *arr;
/**
* The capacity of arr.
*/
size_t capacity;
/**
* The number of elements in the list.
*/
size_t size;
};
/**
* Attempts to double the capacity of the array backing
* the list t. Returns true if the array capacity is increased,
* false otherwise.
*/
bool add_capacity(list *t);
/**
* Returns a pointer to an empty list having a default
* capacity, or null if the list could not be allocated.
*
* The returned list must be freed using list_free.
*/
list *list_init_empty(void);
/**
* Returns a pointer to an empty list having the specified
* capacity, or null if the list could not be allocated.
*
* The returned list must be freed using list_free.
*/
list *list_init(size_t capacity);
/**
* Returns a pointer to a list containing the elements
* in the specified array, or null if the list could not be allocated.
*
* The returned list must be freed using list_free.
*/
list *list_init_arr(size_t n, const int a[n]);
/**
* Returns a copy of the specified list.
*/
list *list_copy(const list *other);
/**
* Returns the number of elements in the specified list.
*/
size_t list_size(const list *t);
/**
* Returns the element at the specified index of the
* specified list. Using an invalid index produces
* undefined behavior.
*/
int list_get(const list *t, size_t index);
/**
* Sets the specified index of the specified list to the
* specified element, overwriting the existing element.
* Using an invalid index produces undefined behavior.
* The value that was overwritten is returned to the caller.
*/
int list_set(list *t, size_t index, int elem);
/**
* Adds an element to the end of the specified list,
* expanding the capacity of the list if needed. Returns
* true if the element is added to the list, and false
* if the element could not be added to the list.
*/
bool list_add(list *t, int elem);
/**
* Inserts the specified element into the specified list at
* the specified index. All existing elements, if any, starting
* at the specified index and beyond are shifted one position
* to the right. Using an invalid index produces undefined behavior
* (but note that using an index equal to the size of the list
* adds the element to the end of the list).
*
* Returns true if the element is inserted into the list, and false
* if the element could not be inserted into the list.
*/
bool list_insert(list *t, size_t index, int elem);
/**
* Removes and returns the element at the specified
* index of the specified list.
*/
int list_remove(list *t, size_t index);
/**
* Returns a null-terminated string representation of the specified list.
* The caller must free the returned string.
*/
char *list_to_string(const list *t);
/**
* Writes a null-terminated string representation of the specified list
* into the specified buffer having the specified size.
* Returns the number of characters written into the buffer
* (not including the null terminator), which is guaranteed to be
* at most bufsz-1 characters.
*/
int list_to_string2(const list *t, char *buf, size_t bufsz);
/**
* Prints a list followed by a newline to standard output.
*/
void list_print(const list *t);
/**
* Deallocates memory used by the specified list. Attempts
* to use the specified list after this function returns
* produces undefined behavior.
*/
void list_free(list *t);
#endif /* LIST_H */
list.c
#include < assert.h >
#include < limits.h >
#include < stddef.h >
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
#include "list.h"
const size_t DEFAULT_CAPACITY = 4;
list *list_init_empty(void) {
return list_init(DEFAULT_CAPACITY);
}
list *list_init(size_t capacity) {
list *t = malloc(sizeof(list));
int *arr = malloc(capacity * sizeof(int));
if (!t || !arr) {
return NULL;
}
t->arr = arr;
t->capacity = capacity;
t->size = 0;
}
list *list_init_arr(size_t n, const int a[n]) {
list *t = malloc(sizeof(list));
int *arr = malloc(n * sizeof(int));
if (!t || !arr) {
return NULL;
}
t->arr = arr;
memcpy(t->arr, a, n * sizeof(int));
t->capacity = n;
t->size = n;
}
list *list_copy(const list *other) {
list *t = malloc(sizeof(list));
int *arr = malloc(other->capacity * sizeof(int));
if (!t || !arr) {
return NULL;
}
t->arr = arr;
memcpy(t->arr, other->arr, other->size * sizeof(int));
t->capacity = other->capacity;
t->size = other->size;
return t;
}
size_t list_size(const list *t) {
return t->size;
}
int list_get(const list *t, size_t index) {
assert(index < t->size);
return t->arr[index];
}
int list_set(list *t, size_t index, int elem) {
assert(index < t->size);
int old = t->arr[index];
t->arr[index] = elem;
return old;
}
bool add_capacity(list *t) {
int *new_arr = realloc(t->arr, t->capacity * 2 * sizeof(int));
if (!new_arr) {
return false;
}
t->capacity *= 2;
t->arr = new_arr;
return true;
}
bool list_add(list *t, int elem) {
if (t->size == t->capacity) {
// out of space in the array; re-allocate the array
bool ok = add_capacity(t);
if (!ok) {
return false;
}
}
t->arr[t->size] = elem;
t->size++;
return true;
}
bool list_insert(list *t, size_t index, int elem) {
assert(index < = t->size);
if (index == t->size) {
// add to end of list
return list_add(t, elem);
}
if (t->size == t->capacity) {
// out of space in the array; re-allocate the array
bool ok = add_capacity(t);
if (!ok) {
return false;
}
}
// move all elements from position index and beyond to
// the right one position
// number of elements that need to be moved
size_t n = t->size - index;
memmove(&t->arr[index + 1], &t->arr[index], n * sizeof(int));
// insert element
t->arr[index] = elem;
t->size++;
return true;
}
int list_remove(list *t, size_t index) {
assert(index < t->size);
int old = t->arr[index];
// number of elements that need to be moved
size_t n = t->size - index - 1;
if (n > 0) {
// move the n elements starting at index+1 one position left
memmove(&t->arr[index], &t->arr[index + 1], n * sizeof(int));
}
t->size -= 1;
return old;
}
char *list_to_string(const list *t) {
if (t->size == 0) {
char *s = malloc(3);
sprintf(s, "[]");
return s;
}
char tmp[100];
sprintf(tmp, "%d", INT_MIN);
size_t max_int_len = strlen(tmp);
char *s = malloc((max_int_len + 2) * t->size + 2);
char *p = s;
size_t n = sprintf(p, "[%d", t->arr[0]);
p += n;
for (size_t i = 1; i < t->size; i++) {
n = sprintf(p, ", %d", t->arr[i]);
p += n;
}
sprintf(p, "]");
return s;
}
int list_to_string2(const list *t, char *buf, const size_t bufsz) {
if (bufsz == 0) {
return 0;
}
// max number of chars to write
const int MAX_NBUF = bufsz - 1;
// number of characters written to buf
size_t nbuf = 0;
if (t->size == 0) {
int n = snprintf(buf, bufsz, "[]");
if (nbuf > MAX_NBUF) {
return MAX_NBUF;
}
return n;
}
size_t bufrem = bufsz;
int n = snprintf(buf, bufrem, "[%d", t->arr[0]);
nbuf += n;
if (nbuf > MAX_NBUF) {
return MAX_NBUF;
}
bufrem -= n;
// advance buffer pointer for the next write
buf += n;
for (size_t i = 1; i < t->size; i++) {
n = snprintf(buf, bufrem, ", %d", t->arr[i]);
nbuf += n;
if (nbuf > MAX_NBUF) {
return MAX_NBUF;
}
buf += n;
bufrem -= n;
}
n = snprintf(buf, bufrem, "]");
nbuf += n;
bufrem -= n;
if (nbuf > MAX_NBUF) {
return MAX_NBUF;
}
return nbuf;
}
void list_print(const list *t) {
char *s = list_to_string(t);
printf("%s\n", s);
free(s);
}
void list_free(list *t) {
free(t->arr);
free(t);
}
list_utils.c
#include < stdlib.h >
#include < stdio.h >
#include < string.h >
#include "list_utils.h"
stack.h
#ifndef stack_H
#define stack_H
#include < stdbool.h >
/**
* Name of the node struct used by stack.
*/
typedef struct node node;
/**
* The node struct definition.
*/
struct node {
void *elem;
node *next;
};
/**
* Name of the stack struct.
*/
typedef struct stack stack;
/**
* The stack struct definition.
*/
struct stack {
node *top;
size_t size;
};
/**
* Pointer to function that prints an element.
*/
typedef void (*print_elem_func)(const void *elem);
/*
* Pointer to function that frees an element.
*/
typedef void (*free_elem_func)(void *elem);
stack *stack_init();
bool stack_is_empty(const stack *s);
size_t stack_size(const stack *s);
bool stack_push(stack *s, void *elem);
void *stack_pop(stack *s);
/**
* Free the memory associated with a stack. If
* free_elem is not NULL, then the memory for each element
* is also freed by calling the provided function;
* otherwise, the elements are not freed.
*/
void stack_free(stack *s, free_elem_func free_elem);
/**
* Prints the elements of the stack where each element is
* printed using the provided function. Undefined behavior
* results if print_elem is NULL.
*/
void stack_print(const stack *s, print_elem_func print_elem);
#endif // stack_H
stack.c
#include < assert.h >
#include < stdio.h >
#include < stdlib.h >
#include "stack.h"
stack *stack_init() {
// allocate the stack struct
stack *s = malloc(sizeof(stack));
if (!s) {
return NULL;
}
// initialize members for an empty list
s->top = NULL;
s->size = 0;
return s;
}
bool stack_is_empty(const stack *s) {
return s->size == 0;
}
size_t stack_size(const stack *s) {
return s->size;
}
bool stack_push(stack *s, void *elem) {
// allocate storage for a new node
node *n = malloc(sizeof(node));
if (!n) {
return false;
}
// initialize node members so that the node is in
// front of the current top node
n->elem = elem;
n->next = s->top;
// the top node in the stack is now n
s->top = n;
s->size++;
return true;
}
void *stack_pop(stack *s) {
assert(!stack_is_empty(s));
// get a pointer to the top node so that we can free the node later
node *top = s->top;
// get the element to return to the caller
void *elem = top->elem;
// pop the element by moving the top pointer to the next node
s->top = top->next;
s->size--;
// free the old top node
free(top);
return elem;
}
void stack_free(stack *s, free_elem_func free_elem) {
// free all nodes by iterating over all nodes and freeing
// nodes as they are visited
node *n = s->top;
while (n) {
node *next = n->next;
if (free_elem) {
(*free_elem)(n->elem);
}
free(n);
n = next;
}
// free the stack
free(s);
}
/* iterative version of print
void stack_print(const stack *s) {
printf("TOP, ");
node *n = s->top;
while (n) {
printf("%d, ", n->elem);
n = n->next;
}
printf("BOTTOM\n");
}
*/
void print_rec(const node *n, print_elem_func print_elem);
void stack_print(const stack *s, print_elem_func print_elem) {
printf("TOP, ");
print_rec(s->top, print_elem);
printf("BOTTOM\n");
}
/**
* Recursive helper function to demonstrate recursion
* on a linked structure.
*
* Prints the elements in all of the nodes starting at
* the specified node n.
*/
void print_rec(const node *n, print_elem_func print_elem) {
// base case
if (!n) {
return;
}
// n not NULL, recursive case
// print the element in n
(*print_elem)(n->elem);
printf(", ");
// then print the remaining elements
print_rec(n->next, print_elem);
}
stack_utils.c
#include < stdlib.h >
#include < stdio.h >
#include < string.h >
#include "stack_utils.h"
Makefile
# Makefile for Assignment 5
list_utils.o : list_utils.h list_utils.c
gcc -c list_utils.c
stack_utils.o : stack_utils.h stack_utils.c
gcc -c stack_utils.c
list.o : list.c list.h
gcc -c list.c
stack.o : stack.c stack.h
gcc -c stack.c
clean :
rm *.o