Lista de matriz circular en c -- ampo con circular-list camp codereview Relacionados El problema

Circular array list in C


2
vote

problema

Español

Ahora tengo esta lista basada en la matriz circular en C. Circularity Permite presionar / aparecer en ambos extremos de la lista en el tiempo de amortización constante. La inserción / eliminación de las ubicaciones aleatorias se ejecuta en un tiempo lineal, pero lo optimizé un poco: Supongamos que estamos insertando un elemento en la ubicación arbitraria. Podemos cambiar los elementos de la izquierda una posición a la izquierda, o los elementos correctos una posición a la derecha. Esta implementación elegirá la opción que minimizó la cantidad de turnos. Entonces, ¿qué crees?

list.h :

  #ifndef LIST_H #define LIST_H  #include <stdbool.h> #include <stdlib.h>  #ifdef  __cplusplus extern "C" { #endif      typedef struct list_t list_t;      /***************************************************************************     * Allocates the new, empty list with initial capacity.                     *     ***************************************************************************/       list_t* list_t_alloc(size_t initial_capacity);      /***************************************************************************     * Inserts the element to in front of the head of the list. Returns true if *     * operation was successful.                                                *     ***************************************************************************/       bool    list_t_push_front(list_t* p_list, void* p_element);      /***************************************************************************     * Appends the element to the tail of the list. Returns true if operation   *     * was successful.                                                          *      ***************************************************************************/       bool    list_t_push_back(list_t* p_list, void* p_element);      /***************************************************************************     * Inserts the element into the list before index'th element. Returns true  *     * if operation was successful.                                             *      ***************************************************************************/       bool    list_t_insert(list_t* p_list, size_t index, void* p_element);      /***************************************************************************     * Returns the amount of elements stored in the list.                       *      ***************************************************************************/       size_t  list_t_size(list_t* p_list);      /***************************************************************************     * Returns the index'th element of the list. Returns NULL if the index is   *     * out of range.                                                            *      ***************************************************************************/       void*   list_t_get(list_t* p_list, size_t index);      /***************************************************************************     * Sets the index'th element of the list. Returns the old value. If the     *     * index is out of range, returns NULL.                                     *      ***************************************************************************/       void*   list_t_set(list_t* p_list, size_t index, void* p_new_value);      /***************************************************************************     * Removes and returns the front element of the list. If list is empty,     *     * returns NULL.                                                            *      ***************************************************************************/       void*   list_t_pop_front(list_t* p_list);      /***************************************************************************     * Removes and returns the last element of the list. If list is empty,      *     * returns NULL.                                                            *     ***************************************************************************/       void*   list_t_pop_back(list_t* p_list);      /***************************************************************************     * Removes the element at index 'index' from the list and returns the       *     * it. If the list is empty or the index is out of range, returns NULL.     *      ***************************************************************************/       void*   list_t_remove_at(list_t* p_list, size_t index);      /***************************************************************************     * Returns true if the list contains the specified element using the        *     * equality function. Returns false otherwise.                              *      ***************************************************************************/       bool    list_t_contains(list_t* p_list,                              void* p_element,                             bool (*p_equals_function)(void*, void*));      /***************************************************************************     * Clears this list. The client programmer is responsible for memory-       *     * managing the contents.                                                   *      ***************************************************************************/       void    list_t_clear(list_t* p_list);      /***************************************************************************     * Clears and deallocates the list.                                         *     ***************************************************************************/       void    list_t_free(list_t* p_list);  #ifdef  __cplusplus } #endif  #endif  /* LIST_H */   

list.c :

  #include "list.h" #include <stdbool.h> #include <stdlib.h>  typedef struct list_t {     void** p_table;     size_t size;     size_t capacity;     size_t head;     size_t mask; } list_t;  static const size_t MINIMUM_CAPACITY = 16;  static size_t max(size_t a, size_t b) {     return a < b ? b : a; }  static size_t fix_initial_capacity(size_t initial_capacity) {     size_t ret = 1;      initial_capacity = max(initial_capacity, MINIMUM_CAPACITY);      while (ret < initial_capacity) ret <<= 1;      return ret; }  list_t* list_t_alloc(size_t initial_capacity) {     list_t* p_ret = malloc(sizeof(*p_ret));      if (!p_ret) return NULL;      initial_capacity = fix_initial_capacity(initial_capacity);      p_ret->p_table = malloc(sizeof(void*) * initial_capacity);      if (!p_ret->p_table)     {         free(p_ret);         return NULL;     }      p_ret->capacity = initial_capacity;     p_ret->mask     = initial_capacity - 1;     p_ret->head     = 0;     p_ret->size     = 0;      return p_ret; }  static bool ensure_capacity_before_add(list_t* p_list) {     void** p_new_table;     size_t i;     size_t new_capacity;      if (p_list->size < p_list->capacity) return true;      new_capacity = 2 * p_list->capacity;     p_new_table  = malloc(sizeof(void*) * new_capacity);      if (!p_new_table) return false;      for (i = 0; i < p_list->size; ++i)      {         p_new_table[i] = p_list->p_table[(p_list->head + i) & p_list->mask];     }      free(p_list->p_table);     p_list->p_table  = p_new_table;     p_list->capacity = new_capacity;     p_list->mask     = new_capacity - 1;     p_list->head     = 0;      return true; }  bool list_t_push_front(list_t* p_list, void* p_element) {     if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;      p_list->head = (p_list->head - 1) & p_list->mask;     p_list->p_table[p_list->head] = p_element;     p_list->size++;     return true; }  bool list_t_push_back(list_t* p_list, void* p_element) {     if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;      p_list->p_table[(p_list->head + p_list->size) & p_list->mask] = p_element;     p_list->size++;     return true; }  bool list_t_insert(list_t* p_list, size_t index, void* p_element) {     size_t elements_before;     size_t elements_after;     size_t i;     size_t head;     size_t mask;     size_t size;      if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;     if (index > p_list->size)                return false;      elements_before = index;     elements_after  = p_list->size - index;     head            = p_list->head;     mask            = p_list->mask;     size            = p_list->size;      if (elements_before < elements_after)      {         /* Move preceding elements one position to the left. */         for (i = 0; i < elements_before; ++i)         {             p_list->p_table[(head + i - 1) & mask] =             p_list->p_table[(head + i) & mask];         }          head = (head - 1) & mask;         p_list->p_table[(head + index) & mask] = p_element;         p_list->head = head;     }     else     {         /* Move the following elements one position to the right. */         for (i = 0; i < elements_after; ++i)         {             p_list->p_table[(head + size - i) & mask] =             p_list->p_table[(head + size - i - 1) & mask];         }          p_list->p_table[(head + index) & mask] = p_element;     }      p_list->size++;     return true; }  size_t list_t_size(list_t* p_list)  {     return p_list ? p_list->size : 0; }  void* list_t_get(list_t* p_list, size_t index) {     if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      return p_list->p_table[(p_list->head + index) & p_list->mask]; }  void* list_t_set(list_t* p_list, size_t index, void* p_new_value)  {     void* p_ret;      if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      p_ret = p_list->p_table[(p_list->head + index) & p_list->mask];     p_list->p_table[(p_list->head + index) & p_list->mask] = p_new_value;     return p_ret; }  void* list_t_pop_front(list_t* p_list) {     void* p_ret;      if (!p_list)           return NULL;        if (p_list->size == 0) return NULL;      p_ret = p_list->p_table[p_list->head];     p_list->head++;     p_list->size--;     return p_ret; }  void* list_t_pop_back(list_t* p_list) {     void* p_ret;      if (!p_list)           return NULL;     if (p_list->size == 0) return NULL;      p_ret = p_list->p_table[(p_list->head + p_list->size - 1) & p_list->mask];     p_list->size--;     return p_ret; }  void* list_t_remove_at(list_t* p_list, size_t index) {     void* p_ret;     size_t head;     size_t mask;     size_t elements_before;     size_t elements_after;     size_t i;     size_t j;      if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      head = p_list->head;     mask = p_list->mask;      p_ret = p_list->p_table[(head + index) & mask];      elements_before = index;     elements_after  = p_list->size - index - 1;      if (elements_before < elements_after)     {         /* Move the preceding elements one position to the right. */         for (i = 0, j = elements_before; i < elements_before; ++i, --j)         {             p_list->p_table[(head + j) & mask] =             p_list->p_table[(head + j - 1) & mask];         }          p_list->head = (head + 1) & mask;     }     else     {         /* Move the following elements one position to the left. */         for (i = 0; i < elements_after; ++i)          {             p_list->p_table[(head + index + i) & mask] =             p_list->p_table[(head + index + i + 1) & mask];         }     }      p_list->size--;     return p_ret; }  bool list_t_contains(list_t* p_list,                          void* p_element,                         bool (*p_equals_function)(void*, void*)) {     size_t i;      if (!p_list)            return false;     if (!p_equals_function) return false;      for (i = 0; i < p_list->size; ++i)      {         if (p_equals_function(p_element,                                p_list->p_table[(p_list->head + i) &                                p_list->mask]))         {             return true;         }     }      return false; }  void list_t_clear(list_t* p_list) {     if (!p_list) return;      p_list->head = 0;     p_list->size = 0; }  void list_t_free(list_t* p_list) {     if (!p_list) return;      free(p_list->p_table);     free(p_list); }   

Puede encontrar todo lo necesario para ejecutar la demostración aquí .

Original en ingles

Now I have this circular array-based list in C. Circularity allows pushing/popping to the both ends of the list in constant amortized time. Inserting/removing at random locations runs in linear time, yet I optimized it a little bit: Suppose we are inserting an element at arbitrary location. We can shift the left elements one position to the left, or the right elements one position to the right. This implementation will choose the option that minimized the amount of shifts. So, what do you think?

list.h:

#ifndef LIST_H #define LIST_H  #include <stdbool.h> #include <stdlib.h>  #ifdef  __cplusplus extern "C" { #endif      typedef struct list_t list_t;      /***************************************************************************     * Allocates the new, empty list with initial capacity.                     *     ***************************************************************************/       list_t* list_t_alloc(size_t initial_capacity);      /***************************************************************************     * Inserts the element to in front of the head of the list. Returns true if *     * operation was successful.                                                *     ***************************************************************************/       bool    list_t_push_front(list_t* p_list, void* p_element);      /***************************************************************************     * Appends the element to the tail of the list. Returns true if operation   *     * was successful.                                                          *      ***************************************************************************/       bool    list_t_push_back(list_t* p_list, void* p_element);      /***************************************************************************     * Inserts the element into the list before index'th element. Returns true  *     * if operation was successful.                                             *      ***************************************************************************/       bool    list_t_insert(list_t* p_list, size_t index, void* p_element);      /***************************************************************************     * Returns the amount of elements stored in the list.                       *      ***************************************************************************/       size_t  list_t_size(list_t* p_list);      /***************************************************************************     * Returns the index'th element of the list. Returns NULL if the index is   *     * out of range.                                                            *      ***************************************************************************/       void*   list_t_get(list_t* p_list, size_t index);      /***************************************************************************     * Sets the index'th element of the list. Returns the old value. If the     *     * index is out of range, returns NULL.                                     *      ***************************************************************************/       void*   list_t_set(list_t* p_list, size_t index, void* p_new_value);      /***************************************************************************     * Removes and returns the front element of the list. If list is empty,     *     * returns NULL.                                                            *      ***************************************************************************/       void*   list_t_pop_front(list_t* p_list);      /***************************************************************************     * Removes and returns the last element of the list. If list is empty,      *     * returns NULL.                                                            *     ***************************************************************************/       void*   list_t_pop_back(list_t* p_list);      /***************************************************************************     * Removes the element at index 'index' from the list and returns the       *     * it. If the list is empty or the index is out of range, returns NULL.     *      ***************************************************************************/       void*   list_t_remove_at(list_t* p_list, size_t index);      /***************************************************************************     * Returns true if the list contains the specified element using the        *     * equality function. Returns false otherwise.                              *      ***************************************************************************/       bool    list_t_contains(list_t* p_list,                              void* p_element,                             bool (*p_equals_function)(void*, void*));      /***************************************************************************     * Clears this list. The client programmer is responsible for memory-       *     * managing the contents.                                                   *      ***************************************************************************/       void    list_t_clear(list_t* p_list);      /***************************************************************************     * Clears and deallocates the list.                                         *     ***************************************************************************/       void    list_t_free(list_t* p_list);  #ifdef  __cplusplus } #endif  #endif  /* LIST_H */ 

list.c:

#include "list.h" #include <stdbool.h> #include <stdlib.h>  typedef struct list_t {     void** p_table;     size_t size;     size_t capacity;     size_t head;     size_t mask; } list_t;  static const size_t MINIMUM_CAPACITY = 16;  static size_t max(size_t a, size_t b) {     return a < b ? b : a; }  static size_t fix_initial_capacity(size_t initial_capacity) {     size_t ret = 1;      initial_capacity = max(initial_capacity, MINIMUM_CAPACITY);      while (ret < initial_capacity) ret <<= 1;      return ret; }  list_t* list_t_alloc(size_t initial_capacity) {     list_t* p_ret = malloc(sizeof(*p_ret));      if (!p_ret) return NULL;      initial_capacity = fix_initial_capacity(initial_capacity);      p_ret->p_table = malloc(sizeof(void*) * initial_capacity);      if (!p_ret->p_table)     {         free(p_ret);         return NULL;     }      p_ret->capacity = initial_capacity;     p_ret->mask     = initial_capacity - 1;     p_ret->head     = 0;     p_ret->size     = 0;      return p_ret; }  static bool ensure_capacity_before_add(list_t* p_list) {     void** p_new_table;     size_t i;     size_t new_capacity;      if (p_list->size < p_list->capacity) return true;      new_capacity = 2 * p_list->capacity;     p_new_table  = malloc(sizeof(void*) * new_capacity);      if (!p_new_table) return false;      for (i = 0; i < p_list->size; ++i)      {         p_new_table[i] = p_list->p_table[(p_list->head + i) & p_list->mask];     }      free(p_list->p_table);     p_list->p_table  = p_new_table;     p_list->capacity = new_capacity;     p_list->mask     = new_capacity - 1;     p_list->head     = 0;      return true; }  bool list_t_push_front(list_t* p_list, void* p_element) {     if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;      p_list->head = (p_list->head - 1) & p_list->mask;     p_list->p_table[p_list->head] = p_element;     p_list->size++;     return true; }  bool list_t_push_back(list_t* p_list, void* p_element) {     if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;      p_list->p_table[(p_list->head + p_list->size) & p_list->mask] = p_element;     p_list->size++;     return true; }  bool list_t_insert(list_t* p_list, size_t index, void* p_element) {     size_t elements_before;     size_t elements_after;     size_t i;     size_t head;     size_t mask;     size_t size;      if (!p_list)                             return false;     if (!ensure_capacity_before_add(p_list)) return false;     if (index > p_list->size)                return false;      elements_before = index;     elements_after  = p_list->size - index;     head            = p_list->head;     mask            = p_list->mask;     size            = p_list->size;      if (elements_before < elements_after)      {         /* Move preceding elements one position to the left. */         for (i = 0; i < elements_before; ++i)         {             p_list->p_table[(head + i - 1) & mask] =             p_list->p_table[(head + i) & mask];         }          head = (head - 1) & mask;         p_list->p_table[(head + index) & mask] = p_element;         p_list->head = head;     }     else     {         /* Move the following elements one position to the right. */         for (i = 0; i < elements_after; ++i)         {             p_list->p_table[(head + size - i) & mask] =             p_list->p_table[(head + size - i - 1) & mask];         }          p_list->p_table[(head + index) & mask] = p_element;     }      p_list->size++;     return true; }  size_t list_t_size(list_t* p_list)  {     return p_list ? p_list->size : 0; }  void* list_t_get(list_t* p_list, size_t index) {     if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      return p_list->p_table[(p_list->head + index) & p_list->mask]; }  void* list_t_set(list_t* p_list, size_t index, void* p_new_value)  {     void* p_ret;      if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      p_ret = p_list->p_table[(p_list->head + index) & p_list->mask];     p_list->p_table[(p_list->head + index) & p_list->mask] = p_new_value;     return p_ret; }  void* list_t_pop_front(list_t* p_list) {     void* p_ret;      if (!p_list)           return NULL;        if (p_list->size == 0) return NULL;      p_ret = p_list->p_table[p_list->head];     p_list->head++;     p_list->size--;     return p_ret; }  void* list_t_pop_back(list_t* p_list) {     void* p_ret;      if (!p_list)           return NULL;     if (p_list->size == 0) return NULL;      p_ret = p_list->p_table[(p_list->head + p_list->size - 1) & p_list->mask];     p_list->size--;     return p_ret; }  void* list_t_remove_at(list_t* p_list, size_t index) {     void* p_ret;     size_t head;     size_t mask;     size_t elements_before;     size_t elements_after;     size_t i;     size_t j;      if (!p_list)               return NULL;     if (index >= p_list->size) return NULL;      head = p_list->head;     mask = p_list->mask;      p_ret = p_list->p_table[(head + index) & mask];      elements_before = index;     elements_after  = p_list->size - index - 1;      if (elements_before < elements_after)     {         /* Move the preceding elements one position to the right. */         for (i = 0, j = elements_before; i < elements_before; ++i, --j)         {             p_list->p_table[(head + j) & mask] =             p_list->p_table[(head + j - 1) & mask];         }          p_list->head = (head + 1) & mask;     }     else     {         /* Move the following elements one position to the left. */         for (i = 0; i < elements_after; ++i)          {             p_list->p_table[(head + index + i) & mask] =             p_list->p_table[(head + index + i + 1) & mask];         }     }      p_list->size--;     return p_ret; }  bool list_t_contains(list_t* p_list,                          void* p_element,                         bool (*p_equals_function)(void*, void*)) {     size_t i;      if (!p_list)            return false;     if (!p_equals_function) return false;      for (i = 0; i < p_list->size; ++i)      {         if (p_equals_function(p_element,                                p_list->p_table[(p_list->head + i) &                                p_list->mask]))         {             return true;         }     }      return false; }  void list_t_clear(list_t* p_list) {     if (!p_list) return;      p_list->head = 0;     p_list->size = 0; }  void list_t_free(list_t* p_list) {     if (!p_list) return;      free(p_list->p_table);     free(p_list); } 

You can find everything needed for running the demonstration here.

     

Lista de respuestas

1
 
vote
vote
La mejor respuesta
 

error

En pop_front() , usted hace esto:

  p_list->head++;   

pero debería haber sido esto:

  p_list->head = (p_list->head + 1) & p_list->mask;   

Hiciste esto correctamente en todos los otros lugares, por lo que debes haberte perdido este.

Loop ligeramente confuso

En remove_at() , tiene este bucle:

      /* Move the preceding elements one position to the right. */     for (i = 0, j = elements_before; i < elements_before; ++i, --j)     {         p_list->p_table[(head + j) & mask] =         p_list->p_table[(head + j - 1) & mask];     }   

Este bucle es correcto, pero un poco confuso para mí porque tiene dos variables de bucle. Creo que podría eliminar el i VARIABLE y SOLO UTILICE j Me gusta esto:

      /* Move the preceding elements one position to the right. */     for (j = elements_before; j > 0; --j)     {         p_list->p_table[(head + j) & mask] =         p_list->p_table[(head + j - 1) & mask];     }   

Capacidad

No sé si me gusta el hecho de que siempre está redondeando la capacidad de una potencia de 2. Por un lado, hace que el cálculo del índice sea rápido. Por otro lado, si alguien quería una lista con una capacidad fija, podría usar hasta el doble de la memoria requerida.

Dependiendo del caso de uso, de cualquier manera podría ser mejor. Pero en mi opinión, el uso de memoria más bajo sería más beneficioso que el alcance del rendimiento de usar un operador de módulo.

 

Bug

In pop_front(), you do this:

p_list->head++; 

but it should have been this:

p_list->head = (p_list->head + 1) & p_list->mask; 

You did this correctly in all the other places, so you must have missed this one.

Slightly confusing loop

In remove_at(), you have this loop:

    /* Move the preceding elements one position to the right. */     for (i = 0, j = elements_before; i < elements_before; ++i, --j)     {         p_list->p_table[(head + j) & mask] =         p_list->p_table[(head + j - 1) & mask];     } 

This loop is correct but a little confusing to me because you have two loop variables. I think you could remove the i variable and just use j like this:

    /* Move the preceding elements one position to the right. */     for (j = elements_before; j > 0; --j)     {         p_list->p_table[(head + j) & mask] =         p_list->p_table[(head + j - 1) & mask];     } 

Capacity

I don't know if I like the fact that you are always rounding up the capacity to a power of 2. On the one hand, it makes the index calculation fast. On the other hand, if someone wanted a list with a fixed capacity, you might use up to double the memory required.

Depending on the use case, either way might be better. But in my opinion, lower memory usage would be more beneficial than the performance hit from using a modulo operator.

 
 

Relacionados problema

2  Anillo realmente básico / tampón circular en Java  ( Really basic ring circular buffer in java ) 
Necesitaba una forma sencilla de ejecutar pruebas en los últimos N Bytes de datos recibidos de un zócalo, y un tampón de anillo parecía ser la forma más efi...

2  ADT STACK con una lista enlazada doblemente circular  ( Adt stack with a doubly circular linked list ) 
He logrado implementar un yes1 con una lista circularmente vinculada. Me gustaría saber si hay cosas que podría haber hecho mejor o, debería mejorar. yes...

4  Lista enlazada circular  ( Circular linked list ) 
Por favor revise esto: #include <iostream> using namespace std; template <class T> struct Node { T data; Node * next; Node(T data) : data(data), nex...

3  Sin límites, alto rendimiento (?), Genérico, Safe-Safe (?), BlackedCircularue  ( Unbounded high performance generic thread safe batchedcircularqueue ) 
Esta es una estructura de datos que escribí: Es una cola circular en primer lugar (un anillo); se ha eliminado / estampado: devuelve una matriz de un tam...

5  Produciendo cada cadena de una longitud dada usando alguna gama de caracteres  ( Producing every string of a given length using some range of characters ) 
desde que era un niño que quería entender cómo funcionan los programas de fuerza bruta. No he podido dar sentido a ninguno de los ejemplos a lo largo de Inter...

1  Deque implementado utilizando una matriz circular  ( Deque implemented using a circular array ) 
Encontré un tutorial sobre la implementación de un deque usando una matriz circular . Cambié la implementación, pero no estoy seguro de si es correcto o no. ...

3  SPOJ Class Leader usando la lista circular enlazada  ( Spoj class leader using circular linked list ) 
He resuelto una pregunta SPOJ LEADER CLASE . Para cada caso de prueba hay n estudiantes y se le dará un documento al estudiante m y ahora comienza el jue...

15  CircularListcursor: un cursor circular eficiente en cualquier lista  ( Circularlistcursor an efficient circular cursor on any list ) 
He decidido crear mi propio CircularListCursor , porque quería una abstracción y un 9988777655544338 no podría dar lo suficiente en mi opinión. También est...

5  Compare dos listas para ver si una es una rotación del otro  ( Compare two lists to see if one is a rotation of the other ) 
Pasando una lista de la pregunta de la entrevista común, esta fue la siguiente. ¿Alguna sugerencia sobre el rendimiento y la mejora? ¿Cuál sería una mejor imp...

12  Anillo circular  ( Circular ringbuffer ) 
Estoy tratando de meterme en las cosas, y pensé que sería una buena idea tratar de implementar un búfer circular. He definido mi estructura como esta: ty...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos