20171113:Practical:C:Lists:Vectors:Queues : Différence entre versions
(→Header) |
(→Implementation) |
||
Ligne 354 : | Ligne 354 : | ||
* Remove operations (pop and extract) fails only if the vector is empty (nothing to remove) | * Remove operations (pop and extract) fails only if the vector is empty (nothing to remove) | ||
* As a bonus, you can handle a shrink case where the size is less than half of the capacity after a remove operation (in that case you will divide the capacity by two). | * As a bonus, you can handle a shrink case where the size is less than half of the capacity after a remove operation (in that case you will divide the capacity by two). | ||
+ | |||
+ | You are responsible to write your own tests. | ||
+ | |||
+ | == Queue == | ||
+ | |||
+ | For this part we want to implement traditional FIFO queues using linked lists. | ||
+ | |||
+ | The most efficient queue implementation use single link circular lists. The entry point of the list is the ''last'' element (the last pushed element) and its next field points to the ''first'' element (the oldest in the queue), after that elements are linked from oldest to most recent. We don't use a sentinel here, but we have an external structure containing the entry point and the size of the queue. Here is the structure: | ||
+ | |||
+ | <source lang="C"> | ||
+ | /* standard linked lists */ | ||
+ | struct list { | ||
+ | struct list *next; | ||
+ | void *data; | ||
+ | }; | ||
+ | |||
+ | /* | ||
+ | * queue container: replace sentinel and add abstraction | ||
+ | */ | ||
+ | struct queue { | ||
+ | struct list *store; | ||
+ | size_t size; | ||
+ | }; | ||
+ | </source> |
Version du 8 novembre 2017 à 08:49
Sommaire
Introduction/Assignements
This week will dive into lists constructions: linked lists, vectors and queues (implemented using linked lists).
The tutorial directory (in your GIT) will have the following form:
- 20171113_lists:
- linked_lists
- vectors
- queues
See the exercises for the detailed content.
Linked Lists
- Directory:
- linked_lists
- list.h
- list.c
- linked_lists
Presentation
Linked list is a classical recursive data structure (see this week lecture) that comes in many flavor. We choose a practical approach using external allocation and sentinel.
- External Allocation: all list functions are not responsible for memory allocations nor memory releases. All operations directly receive pre-constructed list cells (for insertion) and returns (disconnected) cells.
- Sentinel: all lists will always contain an empty fake cell at the beginning (before all other cells). An empty list is thus a single sentinel and not a NULL pointer.
The principal impacts on the implementation are:
- Operations that modify the list head don't need to take a double pointer nor returns a new head, just update the next field of the sentinel cell.
- Operations never use malloc(3) nor free(3) (and similar functions) and the client can use its own allocation scheme.
- Searching and elements access is done using an iterator pattern (similar to C++ iterator).
- Searching, inserting and removing can be implemented by composition of simple functions.
Header
Here is the full list header describing the requested functions:
/* * list.h : Linked lists */ #ifndef EPITA_IP_LIST_H_ #define EPITA_IP_LIST_H_ /* Simply linked list of integers */ struct list { struct list *next; int data; }; /* * Standard operations * We're working with sentinels and external allocation * This means that our lists always have a fake head (the sentinel) * and all allocations (and free) are performed by the caller, not the operation */ /* * list_init(list) * initialise the sentinel node list */ void list_init(struct list *list); /* * list_is_empty(list) * returns true if the list is empty * remember, we have a sentinel thus a list always has at least one node, * the list is empty if this node doesn't have a next. */ int list_is_empty(struct list *list); /* * list_len(list) * returns the length of the list (don't count the sentinel) */ size_t list_len(struct list *list); /* * list_push_front(list, elm) * attach elm in front of list, that is after the sentinel. * Note that elm is already a node, you just have to attach it. */ void list_push_front(struct list *list, struct list *elm); /* * list_pop_front(list) * Extract the first element (not the sentinel) of list. * This operation detaches the element from the list and returns it (caller is * responsible for freeing it.) * If the list is empty, the function returns NULL. */ struct list* list_pop_front(struct list *list); /* * list_find(list, value) * search for the first node containing value and returns (without detaching it) * the corresponding list node. The function returns NULL if the value is not * present in the list. */ struct list* list_find(struct list *list, int value); /* * list_lower_bound(list, value) * search for the first element not smaller than value in list * returns the pointer to the cell BEFORE this element */ struct list* list_lower_bound(struct list *list, int value); /* * list_is_sorted(list) * check whether the list is sorted in increasing order */ int list_is_sorted(struct list *list); /* * list_insert(list, elm) * insert elm in the sorted list (keeping the list sorted) * Like list_push_front, elm is already a list node. */ void list_insert(struct list *list, struct list *elm); /* * More algorithms */ /* * list_rev(list) * reverse the list using the same nodes (just move them) and the same sentinel. */ void list_rev(struct list *list); /* * list_half_split(list, second) * 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 /* EPITA_IP_LIST_H_ */
Implementation
- Implement all functions from list.h in the file list.c
Each function is described by the comment in the header, you can add functions not listed in this header but the must be marked as static since they must not be exported. The file list.c must not contain a main function.
Here are some notes on the implementation:
- list_init(list) takes the node used as sentinel and set the next pointer to NULL
- list_is_empty(list): a list is empty if the next pointer of the sentinel is NULL
- list_len(list): the number of nodes without the sentinel
- list_push_front(list, elm): elm is a list node containing the new value, you'll attach it after the sentinel
- list_pop_front(list) detaches the element after the sentinel and returns it
- list_lower_bound(list, value) returns a pseudo list where the element before the bound serves as a sentinel, such that insert can be implemented with lower bound and push front.
- list_half_split(list, second) can be implemented with only pass and without computing the length
Testing
In order to test, you'll write another C file where you test operations one by one. The tests are your responsibility, but here are some useful trick.
In order to display the list, here is an example of a printing function for lists (beware, it contains a goto):
void print_list(struct list *list) { int line = printf("["); if (list->next) { goto pastfst; while (list->next) { line += printf(";"); if (line > 72) { printf("\n "); line = 1; } pastfst: line += printf(" %d", list->next->data); list = list->next; } } printf(" ]\n"); }
While testing you must take care of allocation/free, if you're looking for a nice strategy, you can try to use an array of node …
A way to test your sorted insertion function is to implement an insertion sort, here is the function:
void list_insert_sort(struct list *list) { if (list_is_empty(list)) // nothing to do return; struct list fake_head = {0,0}; // temporary head while (!list_is_empty(list)) { struct list *elm = list_pop_front(list); list_insert(&fake_head, elm); } list->next = fake_head.next; // reattach the sorted list to its sentinel }
Vectors
- Directory:
- vectors
- vector.h
- vector.c
- vectors
Vectors are wrappers around arrays in order to provide list like operations. The vector structure contains an array, its capacity and the current number of cells used in the array.
The structure look like this:
struct vector { size_t capacity, size; int *data; };
capacity is the number of cell in data (the array of integers) and size is the number of used cells.
One interesting approach is to make vectors grow automatically: when adding an element to the vector, if the number of used cells is equal to the capacity, you can use realloc(3) in order to obtain a bigger array. A common strategy to avoid to much resizing is to double the capacity each time we need to resize. Here is an example of usage of realloc(3) in order to double the size of data:
// returns false if something goes wrong (realloc fails) int double_vector_size(struct vector *vect) { int *tmp = realloc(vect->data, 2 * vect->capacity * sizeof (int)); if (tmp == NULL) { // oups no more memory ? warn("realloc of data fails"); return 0; } vect->data = tmp; vect->capacity *= 2; return 1; }
Header
The following file describes the API of vectors:
/* * vector.h : Simple vector implementation */ # ifndef EPITA_IP_VECTOR_H_ # define EPITA_IP_VECTOR_H_ # include <stdlib.h> struct vector { size_t capacity, size; int *data; }; /* * vector_init(list, value): initializes vect with a storage of capacity integers * returns false (0) if allocation fails * true (!=0) otherwise */ int vector_init(struct vector *vect, size_t capacity); /* * vector_make(capacity) create an empty vector * with initial storage size capacity * returns NULL if something goes wrong (allocations) */ struct vector* vector_make(size_t capacity); /* * vector_push_back(vect, x) add x at the end of vect * if vect is full increase capacity * returns false (0) if something goes wrong * true (!=0) otherwise */ int vector_push_back(struct vector *vect, int x); /* * vector_pop_back(vect, &x) get the last element of vect * remove the element * store result in x * return true (!=0) if size > 0 * return false (0) otherwise */ int vector_pop_back(struct vector *vect, int *x); /* * vector_push_front(vect, x) add x at the beginning of vect * if vect is full increase capacity * returns false (0) if something goes wrong * true (!=0) otherwise */ int vector_push_front(struct vector *vect, int x); /* * vector_pop_front(vect, &x) get the first element of vect * remove the element * store result in x * return true (!=0) if size was > 0 before pop * return false (0) otherwise */ int vector_pop_front(struct vector *vect, int *x); /* * vector_insert_at(vect, pos, x) add x in pos cell of vect * returns true (!=0) if pos <= size of vect * returns false (0) otherwise * returns false also if something goes wrong * vector_insert_at(v, v->size, x) is equivalent to vector_push_back(v, x) * vector_insert_at(v, 0, x) is equivalent to vector_push_front(v, x) * if vect is full increase capacity */ int vector_insert_at(struct vector *vect, size_t pos, int x); /* * vector_extract_at(vect, pos, &x) get the pos element of vect * remove the element * store result in x * return false (0) if size == 0 or pos >= size * vector_extract_at(v, v->size - 1, &x) is equivalent to vector_pop_back(v, &x) * vector_extract_at(v, 0, &x) is equivalent to vector_pop_front(v, &x) */ int vector_extract_at(struct vector *vect, size_t pos, int *x); /* * vector_clone(vect) create a complete copy of vect * both storage contains the same elements but are not at the same memory place * returns NULL if something goes wrong */ struct vector* vector_clone(struct vector *vect); # endif
Implementation
- In the file vector.c, implement all the function described in the header vector.h
Some notes:
- As for the previous exercise, you can add functions not in the header as long as they are marked static
- You will need some auxiliary functions for growing storage or shifting array elements
- In all cases of insertion (push and insert), the operation can fail if the growing operation fails
- Remove operations (pop and extract) fails only if the vector is empty (nothing to remove)
- As a bonus, you can handle a shrink case where the size is less than half of the capacity after a remove operation (in that case you will divide the capacity by two).
You are responsible to write your own tests.
Queue
For this part we want to implement traditional FIFO queues using linked lists.
The most efficient queue implementation use single link circular lists. The entry point of the list is the last element (the last pushed element) and its next field points to the first element (the oldest in the queue), after that elements are linked from oldest to most recent. We don't use a sentinel here, but we have an external structure containing the entry point and the size of the queue. Here is the structure:
/* standard linked lists */ struct list { struct list *next; void *data; }; /* * queue container: replace sentinel and add abstraction */ struct queue { struct list *store; size_t size; };