Lists and Vectors

Submission

Due Date

By Friday 7 December 2018 23:42

Directory Hierarchy

Create your git repository (replace john.smith by your own login).

$ git clone git@git.cri.epita.net:p/2022-spe-tp/tp06-john.smith

It must contain the following files and directories:

pw_06_lists_vectors/
- AUTHORS
- lists/
  - list.c
  - list.h
- vectors/
  - vector.c
  - vector.h

The AUTHORS file must contain the following information.

AUTHORS

First Name
Family Name
Login
Email Address

The last character of your AUTHORS file must be a newline character.

For instance:

AUTHORS

$ cat AUTHORS
John
Smith
john.smith
john.smith@epita.fr
$ # Command prompt ready for the next command...

Be careful, if you do not follow all the given instructions, no point will be given to your answers.

Lists

Introduction

Linked lists are common data structures that come in many flavors. We will approach this new concept by using external allocations and sentinels.

External Allocation: List functions are not responsible for memory allocation/deallocation. All operations receive existing elements to be inserted or return disconnected elements.
Sentinel: A sentinel is a fake element that is the first element of the list. An empty list is then a single sentinel and not a NULL pointer.

As a result:

Operations that affect the head of the list do not need to take a double pointer nor returns a new head. We just need to update the next field of the sentinel.
Operations never use malloc() nor free() and the user can use its own allocation scheme.

Provided Files

The `list.h` File

list.h

#ifndef _LIST_H_
#define _LIST_H_

struct list
{
  struct list *next;
  int data;
};

// Initialize the sentinel of an empty list.
void list_init(struct list *list);

// Return true if the list is empty.
// Otherwise, return false.
// Do not forget that there is always a sentinel.
// So the list is empty if the sentinel does not point to a next element.
int list_is_empty(struct list *list);

// Return the length of the list (sentinel excluded).
size_t list_len(struct list *list);

// Insert 'elm' in front of the list, that is just after the sentinel.
// Note that 'elm' is already an existing element.
// You just have to insert it.
void list_push_front(struct list *list, struct list *elm);

// Extract the first element (not the sentinel) of the list.
// This operation removes the element from the list and returns it
// (the caller is responsible for freeing it).
// If the list is empty, the function returns NULL.
struct list *list_pop_front(struct list *list);

// Search for the first element that contains 'value' and return it
// (without removing it from the list).
// The function returns NULL if the value is not in the list.
struct list *list_find(struct list *list, int value);

// Search for the first element that is not smaller than 'value'
// and return the element that comes just before.
struct list *list_lower_bound(struct list *list, int value);

// Return true if the list is sorted in increasing order.
// Otherwise, return false.
int list_is_sorted(struct list *list);

// Insert 'elm' in the sorted list (keeping the list sorted).
// Note that 'elm' is already an existing element.
// You just have to insert it.
void list_insert(struct list *list, struct list *elm);

// Reverse the elements of the list (except for the sentinel).
void list_rev(struct list *list);

// Split the list in half and put the second half in 'second'.
// 'second' is an empty list (just a sentinel).
void list_half_split(struct list *list, struct list *second);

#endif

The `list.c` File

list.c

#include <stdlib.h>
#include "list.h"

void list_init(struct list *list)
{
    // TODO
}

int list_is_empty(struct list *list)
{
    // TODO
}

size_t list_len(struct list *list)
{
    // TODO
}

void list_push_front(struct list *list, struct list *elm)
{
    // TODO
}

struct list *list_pop_front(struct list *list)
{
    // TODO
}

struct list *list_find(struct list *list, int value)
{
    // TODO
}

struct list *list_lower_bound(struct list *list, int value)
{
    // TODO
}

int list_is_sorted(struct list *list)
{
    // TODO
}

void list_insert(struct list *list, struct list *elm)
{
    // TODO
}

void list_rev(struct list *list)
{
    // TODO
}

void list_half_split(struct list *list, struct list *second)
{
    // TODO
}

Implementation

Complete the list.c file. Just replace the TODO comments by your own code. (This file must not contain a main function.)

You will submit only the list.c and list.h files.

You have to test the functions on your own. Here are some tips:

You can use the following function to print a list:

void print_list(struct list *list)
{
    printf("list_is_empty() = %s\n", list_is_empty(list) ? "yes" :  "no");
    printf("list_is_sorted() = %s\n", list_is_sorted(list) ? "yes" :  "no");
    printf("list_len() = %zu\n", list_len(list));

    int line = 1;

    printf("[");
    if (list->next)
    {
        goto pastfst;
        while (list->next)
        {
            line += printf(";");

            if (line > 72)
            {
                printf("\n ");
                line = 1;
            }

            pastfst:
            line += printf(" %2d", list->next->data);
            list = list->next;
        }
    }

    printf(" ]\n");
}

You can use the list_insert_sort() function below, which implements an insertion sort, in order to test your list_is_empty(), list_pop_front() and list_insert() functions.

void list_insert_sort(struct list *list)
{
    if (list_is_empty(list))
        return;

    struct list fake_head = { 0, 0 };

    while (!list_is_empty(list))
    {
        struct list *elm = list_pop_front(list);
        list_insert(&fake_head, elm);
    }

    list->next = fake_head.next;
}

To avoid allocating and freeing elements manually, you can use an array of elements. For example:

struct list sentinel = { NULL, 0 };
struct list elements[SIZE];
struct list *list = &sentinel;

Vectors

Introduction

Vectors are wrappers around arrays. They provide a contiguous growable array type.

Here is the structure of a vector:

struct vector
{
    size_t capacity;
    size_t size;
    int *data;
};

capacity: The total number of elements that can be stored in the data array. In other words, it is the length of the data array.
size: The number of actual elements within the vector. In other words, it is the number of used cells within the array.
data: An array of elements. In this specific case, it is an array of integers.

Our goal is to make vectors grow automatically. When adding an element to the vector, if the number of used cells (the size) is equal to the capacity, we can use realloc() in order to increase the length of the array. A common strategy to minimize the number of reallocations is to double the capacity of the vector each time reallocations are required.

For instance, a vector with capacity 8 and size 0 would be an empty vector. Inserting 8 or fewer elements into the vector will not affect its capacity (only its size). But if the vector's size is increased to 9, the capacity will be doubled and the memory reallocated.

Provided Files

The `vector.h` File

vector.h

#ifndef _VECTOR_H_
#define _VECTOR_H_

#include <stdlib.h>

struct vector
{
    size_t capacity;
    size_t size;
    int *data;
};

// Create a new vector.
// The initial capacity is 1.
// The initial size is 0.
// If there is not enough memory, the program prints
// "Not enough memory!" and exits with the error code 1.
// (Use the errx() function of the standard library.)
// Be careful, you have to allocate two memory spaces.
// - The memory space that holds the 'struct vector' variable.
// - The memory space that holds the data.
struct vector *vector_new();

// Delete a vector.
// Free all the allocated memory.
// After this instruction, the vector can no longer be used.
void vector_free(struct vector *v);

// Double the capacity of a vector.
// (Use the realloc() function of the standard library.)
// If there is not enough memory, the program prints
// "Not enough memory!" and exits with the error code 1.
// (Use the errx() function of the standard library.)
void double_capacity(struct vector *v);

// Append x at the end of a vector.
// According to the size of the vector,
// you may multiply its capacity by two.
// (Use the double_capacity() function.)
void vector_push(struct vector *v, int x);

// Remove and return the last element of a vector.
// - If the vector is not empty, the last element
//   is removed from the vector, its value is stored in x,
//   and the function returns true (1).
// - Otherwise the function returns false (0).
int vector_pop(struct vector *v, int *x);

// Get the value at the i index.
// - If the i index is not out of bound,
//   the i-index element is stored in x,
//   and the function returns true (1).
// - Otherwise the function returns false (0).
int vector_get(struct vector *v, size_t i, int *x);

// Insert x in the vector at the i-index position.
// The i index must be between 0 and v->size (included).
// According to the size of the vector,
// you may multiply its capacity by two.
// (Use the double_capacity() function.)
// If the i index is out of bound, do nothing.
void vector_insert(struct vector *v, size_t i, int x);

// Remove and return the i-index element of a vector.
// - If the i index is not out of bound,
//   the i-index element is removed, its value is stored in x,
//   and the function returns true (1).
// - Otherwise the function returns false (0).
int vector_remove(struct vector *v, size_t i, int *x);

#endif

The `vector.c` File

vector.c

#include <err.h>
#include "vector.h"

struct vector *vector_new()
{
    // TODO
}

void vector_free(struct vector *v)
{
    // TODO
}

void double_capacity(struct vector *v)
{
    // TODO
}

void vector_push(struct vector *v, int x)
{
    // TODO
}

int vector_pop(struct vector *v, int *x)
{
    // TODO
}

int vector_get(struct vector *v, size_t i, int *x)
{
    // TODO
}

void vector_insert(struct vector *v, size_t i, int x)
{
    // TODO
}

int vector_remove(struct vector *v, size_t i, int *x)
{
    // TODO
}

Implementation

Complete the vector.c file. Just replace the TODO comments by your own code. (This file must not contain a main function.)

You will submit only the list.c and list.h files.

You have to test the functions on your own. This time, no tips are given.

Lists and Vectors

Submission

Due Date

Directory Hierarchy

Lists

Introduction

Provided Files

The list.h File

The list.c File

Implementation

Vectors

Introduction

Provided Files

The vector.h File

The vector.c File

Implementation

The `list.h` File

The `list.c` File

The `vector.h` File

The `vector.c` File