- Questions The Included Makefile Will Help You Compile Your Files Make List Utils Will Attempt To Compile List Utils C 1 (119.47 KiB) Viewed 44 times
#include <limits.h>
#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"
const size_t DEFAULT_CAPACITY = 4;
bool add_capacity(list *t);
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 (!arr) {
return NULL;
}
t->arr = arr;
t->capacity = capacity;
t->size = 0;
return t;
}
list *list_init_arr(size_t n, const int a[n]) {
list *t = malloc(sizeof(list));
int *arr = malloc(n * sizeof(int));
if (!arr) {
return NULL;
}
t->arr = arr;
memcpy(t->arr, a, n * sizeof(int));
t->capacity = n;
t->size = n;
return t;
}
list *list_copy(const list *other) {
list *t = malloc(sizeof(list));
int *arr = malloc(other->capacity *
sizeof(int));
if (!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);
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);
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);
}
The file 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;
};
/**
* 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 */
The file Makefile:
# Makefile for Assignment 5
list_demo : list.o list_utils.o list_demo.c
gcc -o list_demo list_demo.c list.o
list_utils.o
stack_demo : stack.o stack_utils.o stack_demo.c
gcc -o stack_demo stack_demo.c stack.o
stack_utils.o
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 list_demo *.o
Questions The included Makefile will help you compile your files. make list_utils.. Will attempt to compile list_utils.c make list _demo will attempt to compile list_demo.c and its dependencies. make steck_utils.. Will attempt to compile stack_utils.c make stack_demo will attempt to compile stack_deno.c and its dependencies. 1. list Swap Create the files list_utils.h and list_utils. All of your code for Questions through 3 should go into these two files. Create a function ist swap bool list_swap(list *t, size_t i, size_t n) that swaps the elements located at the indexes i and j of the list pointed to by t and returns true if the swap was successful. For example, if t is a pointer to the list: (11, 12, 13, 14, 15) then list_swap(t, 3, 1) modifies the list so that it becomes [11, 14, 13, 12, 15] Special cases The function should return false if one or both of the indexes are not valid for the list 2. list_add_all Create a function list_add_all bool list_add_all(list *dest, const list src) that adds all of the elements in list pointed to by src to the end of the list pointed to by dest. For example, if dest is a pointer to the list: (1, 2, 3) and sre is a pointer to the list: [10, 11, 12) then list_add_all (dest, src) should change dest so that it is the list: [1, 2, 3, 10, 11, 12] Your function should not use a loop nor call list_add to add the elements from sre Instead, use mencpy to copy the elements Special cases If dest IS NULL, then your function should do nothing and return false If src IS NULL (and dest is not NULL ), then your function should do nothing and return true Your function should return false if memory for the added elements cannot be successfully allocated
3. list_sublist Create a function list_sublist: list *list_sublist(const list *t, size_t start, size_t stop) that returns a sublist of the list pointed to by t . The sublist contains the elements of t starting at index start up to but not including stop The returned pointer is a pointer to a new list object, but the list does not have its own independent array of elements; instead, its internal pointer arr points at an element in the list t. For example, if t is a pointer to the list: [11, 12, 13, 14, 15] then list *sub = list_sublist(t, 1, 4) returns the sublist [12, 13, 14] list_set(sub, 0, 100) modifies the sublist sub so that it becomes [100, 13, 14) and the change in sub is reflected in the original list t: [11, 100, 13, 14, 15] Functions that change the size of the sublist result in undefined behaviour (for example, adding or removing an element of the sublist probably does not correctly modify the original list). This behavior differs from Java's sublist method where the sublist can be safely used to modify the original list. Special cases start must be a valid index for the argument list. stop must be a valid index for the argument list, or it must be equal to the size of the argument list. If either index is out of range then the method should return NULL -