elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Recuerda que debes registrarte en el foro para poder participar (preguntar y responder)


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [SRC-C99] Listas doblemente enlazadas (varias funciones).
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [SRC-C99] Listas doblemente enlazadas (varias funciones).  (Leído 2,742 veces)
BlackZeroX
Wiki

Desconectado Desconectado

Mensajes: 3.158


I'Love...!¡.


Ver Perfil WWW
[SRC-C99] Listas doblemente enlazadas (varias funciones).
« en: 15 Enero 2013, 07:01 am »

Son varias funciones para tratar a las listas, Absténganse de entregar a sus maestros este código si no lo llegan a comprender lo "básico". NO INCLUÍ las funciones de ordenamiento debido a que tienen un problema, seguro se me paso alguno... igual no es nada del otro mundo (fue cuando incluí la macro LIST_INTEGRAL_RELATIONSHIP).

list.h
Código
  1. #ifndef LIST_H_INCLUDED
  2. #define LIST_H_INCLUDED
  3.  
  4. /** \autor Ortega Avila Miguel Angel (BlackZeroX).
  5.  *
  6.  * \website http://infrnagelux.sytes.net/
  7.  * \copileft El presente código se da de manera gratuita sin ningún derecho a venta.
  8.  * \note muchas de las funciones aqui presentadas "inútiles" como:
  9.  * list_before()
  10.  * list_after()
  11.  * list_getlist()
  12.  * Note que esta ultima solo esta activa mientras este declarada la macro.
  13.  *
  14.  * http://foro.elhacker.net/programacion_cc/srcc99_para_que_dejen_de_preguntar_por_las_listas-t380839.0.html
  15.  *
  16.  */
  17.  
  18. #include <stdbool.h>
  19. #include <stdlib.h>
  20. #include <stddef.h>
  21. #include <stdint.h>
  22.  
  23. #ifndef LIST_INTEGRAL_RELATIONSHIP
  24. /** \brief Al declarar LIST_INTEGRAL_RELATIONSHIP se reduce considerablemente la velocidad
  25.  * en el proceso list_sort() debido a que se actualizan TODOS los miembros list de la estructura
  26.  * struct list_item de cada elemento; De igual manera aumenta la seguridad de no eliminar o hacer
  27.  * operaciones indebidas entre elementos.
  28.  *
  29.  */
  30. ///#define LIST_INTEGRAL_RELATIONSHIP /**< Comentar/descomentar */
  31. #endif
  32.  
  33. #define LIST_SIZE_ITEM sizeof(struct list_item)
  34.  
  35. struct list;
  36. typedef void*               list_value_t; ///typedef uintptr_t            list_value_t;
  37. typedef struct list*        list_t;
  38.  
  39. /** \brief Definición callback que se encarga de crear un duplicado de un elemento de lista.
  40.  * \param item: Valor a duplicar.
  41.  *
  42.  * \return Retorna el elemento list_value_t duplicado del parámetro value.
  43.  *
  44.  */
  45. typedef list_value_t (*list_callback_clone_item)
  46. (const list_value_t value);
  47.  
  48. /** \brief Definición de callback que se encarga de destruir la memoria asignada al list_value_t.
  49.  *
  50.  * \param item: Puntero a la estructura que se le pretende liberar su valor asignado debe liberarse solo el miembro value.
  51.  *
  52.  */
  53. typedef
  54. void(*list_callback_release_item)
  55. (const list_value_t value);
  56.  
  57. /** \brief Definición de callback que se encarga comparar dos list_value_t.
  58.  *
  59.  * \param value1: list_value_t que se comparara con value2.
  60.  * \param value2: list_value_t que se comparara con value1.
  61.  * \return Retorna el resultado de la comparación.
  62.  * LIST_CMP_LESS_THAT: Si value1 < value2.
  63.  * LIST_CMP_EQUAL: Si value1 == value2.
  64.  * LIST_CMP_GREATER_THAT: Si value1 > value2.
  65.  *
  66.  */
  67. typedef
  68. enum list_cmp(*list_callback_compare_item)
  69. (const list_value_t value1,
  70. const list_value_t value2);
  71.  
  72. enum list_cmp {
  73.    LIST_CMP_EQUAL          = 1,    /**< */
  74.    LIST_CMP_LESS_THAT      = 2,    /**< */
  75.    LIST_CMP_GREATER_THAT   = 4     /**< */
  76. };
  77.  
  78. enum list_sort {
  79.    LIST_SORT_ASC,  /**< */
  80.    LIST_SORT_DESC  /**< */
  81. };
  82.  
  83. struct list_item {
  84.    list_value_t        value;  /**< Valor del item actual. */
  85.    struct list_item    *prev;  /**< Apuntador al item derecho. */
  86.    struct list_item    *next;  /**< Apuntador al item izquierdo. */
  87.    #ifdef LIST_INTEGRAL_RELATIONSHIP
  88.    list_t              list;   /**< Apuntador a los datos generales de la lista. */
  89.    #endif
  90. };
  91.  
  92.  
  93. struct list {                       /**< Estructura que guarda la información generalizada de una lista de datos */
  94.    struct list_item    *first;     /**< Primer elemento agregado a la lista */
  95.    struct list_item    *last;      /**< Ultimo elemento agregado a la lista */
  96.    #ifdef LIST_INTEGRAL_RELATIONSHIP
  97.    size_t              size;       /**< Cantidad de elementos */
  98.    #endif
  99.    list_callback_clone_item    clone_item;     /**< Puntero a la función callback que realiza las acciones CLONE, RELEASE y COMPARE */
  100.    list_callback_release_item  release_item;   /**< Puntero a la función callback que realiza las acciones CLONE, RELEASE y COMPARE */
  101.    list_callback_compare_item  compare_item;   /**< Puntero a la función callback que realiza las acciones CLONE, RELEASE y COMPARE */
  102. };
  103.  
  104. /** \brief Obtiene el item siguiente al inicado.
  105.  *
  106.  * \param item: Item pivote en la lista.
  107.  * \return Retorna el struct list_item * siguiente al indicado; NULL si no hay ningun item.
  108.  *
  109.  */
  110. struct list_item*
  111. list_after(struct list_item *item);
  112.  
  113. /** \brief Crea una nueva lista de elementos list_value_t.
  114.  *
  115.  * \param clone_item: Apuntador a la función callback que retornara la copia del valor a asignar.
  116.  * \param release_item: Apuntador a la función callback que liberara la copia del valor duplicado en el list_callback_clone_item.
  117.  * \param clone_item: Apuntador a un proceso callback que se encarga de comparar los struct list_item *.
  118.  * \return Retorna la nueva cola de datos queue_t que deberá ser destruida con list_release().
  119.  *
  120.  */
  121. list_t
  122. list_allocator(list_callback_clone_item clone_item,
  123.               list_callback_release_item release_item,
  124.               list_callback_compare_item compare_item);
  125.  
  126. /** \brief Agrega n cantidad de elementos repetidos (value) a la lista, reemplazando los existentes.
  127.  *
  128.  * \param list: Lista en la que se agregara value n veces.
  129.  * \param n: Cantidad de valores a agregar a la lista.
  130.  * \param value: Valor a agregar n veces a la lista.
  131.  * \return Retorna el primer elemento agregado; NULL si no se a agregado ningun elemento.
  132.  *
  133.  */
  134. struct list_item*
  135. list_assign(list_t list,
  136.            size_t n,
  137.            list_value_t value);
  138.  
  139. /** \brief Obtiene el ultimo elemento de una lista.
  140.  *
  141.  * \param list: Lista de la cual se obtendrá el ultimo elemento struct list_item *.
  142.  * \return Devuelve el ultimo struct list_item * de la lista.
  143.  *
  144.  */
  145. struct list_item*
  146. list_back(list_t list);
  147.  
  148. /** \brief Obtiene el item anterior al inicado.
  149.  *
  150.  * \param item: Item pivote en la lista.
  151.  * \return Retorna el struct list_item * anterior al indicado; NULL si no hay ningun item.
  152.  *
  153.  */
  154. struct list_item*
  155. list_before(struct list_item *item);
  156.  
  157. /** \brief Obtiene el primer elemento de una lista.
  158.  *
  159.  * \param list: Lista de la cual se obtendrá su primer elemento struct list_item *.
  160.  * \return Devuelve el primer struct list_item * de la lista.
  161.  *
  162.  */
  163. struct list_item*
  164. list_begin(list_t list);
  165.  
  166. /** \brief Remueve/Libera TODOS los elementos de la lista.
  167.  *
  168.  * \param list: Puntero a la struct list que se limpiara.
  169.  * \return Retorna la cantidad de elementos removidos de la lista.
  170.  *
  171.  */
  172. size_t
  173. list_clear(list_t list);
  174.  
  175. /** \brief Función que clona por completo una lista.
  176.  *
  177.  * \param list: Lista que será clonada.
  178.  * \return Retorna una nueva lista que deberá ser liberada con list_release().
  179.  *
  180.  */
  181. list_t
  182. list_clone(list_t list);
  183.  
  184. /** \brief Copia los elementos de una lista a otra.
  185.  *
  186.  * \param list: Lista a la que pertenece el item pasado por el parámetro dst.
  187.  * \param dst: Elemento pivote en donde se se ubicaran los elementos a copiar desde src.
  188.  * \param src: Elemento pivote de una lista que se le clonaran sus elementos para agregarlos en la lista destino dst.
  189.  * \param n: Cantidad máxima de elementos que copiaran.
  190.  * \return Retorna la cantidad de elementos agregados en la lista dst.
  191.  *
  192.  */
  193. size_t
  194. list_copy(list_t list,
  195.          struct list_item *dst,
  196.          struct list_item *src,
  197.          size_t n);
  198.  
  199. /** \brief Verifica si una lista esta vacia.
  200.  *
  201.  * \param list: Lista que se verificara.
  202.  * \return Retorna:
  203.  *  true: si la lista esta vacia.
  204.  *  false: Si contiene por lo menos un elemento.
  205.  *
  206.  */
  207. bool
  208. list_empty(list_t list);
  209.  
  210.  
  211. /** \brief Elimina un struct list_item * de su lista.
  212.  *
  213.  * \param list: Lista a la que pertenece el item.
  214.  * \param item: Elemento que se eliminara/liberara de su lista.
  215.  *
  216.  */
  217. void
  218. list_erase(list_t list,
  219.           struct list_item *item);
  220.  
  221. /** \brief Libera la memoria un struct list_item * NO RELACIONADA con una lista (miembro list debe ser igual a NULL).
  222.  *
  223.  * \param item: Elemento que se eliminara/liberara de su lista.
  224.  * \param callback_release_value: Callback a la función que esta encargada de liberar la memoria del miembro value.
  225.  *
  226.  */
  227. void
  228. list_release_item(struct list_item *item,
  229.                  list_callback_release_item callback_release_value);
  230.  
  231. /** \brief Remueve la relación que tiene el elemento con su lista madre (Usar con cuidado).
  232.  *
  233.  * \param list: Lista a la que se le extraerá el elemento.
  234.  * \param item: Elemento que se extraerá de su lista.
  235.  * \return Retorno el valor pasado en el parámetro item si se extrajo correctamente, de lo contrario retorna NULL.
  236.  *
  237.  *
  238.  * \code
  239.  * void
  240.  * list_release_item(struct list_item *item,
  241.  *                   list_callback_release_item callback_release_value) {
  242.  *     if (!item)
  243.  *         return;
  244.  *
  245.  *     if (callback_release_value)
  246.  *         callback_release_value(item->value);
  247.  * #ifdef LIST_INTEGRAL_RELATIONSHIP
  248.  *     free(list_extract(NULL, item));
  249.  * #else
  250.  *     free(list_extract(NULL, item));
  251.  * #endif
  252.  * }
  253.  * \endcode
  254.  *
  255.  */
  256. struct list_item*
  257. list_extract(list_t list, struct list_item *item);
  258.  
  259. /** \brief Busca un valor a partir de un pivote indicado dentro de una lista.
  260.  *
  261.  * \param list: Lista a la que pertenecen los elementos (incluye parámetro item).
  262.  * \param item: Elemento pivote desde el cual se empezara a buscar el valor indicado en value.
  263.  * si es NULL iniciara desde el inicio de la lista.
  264.  * \param value: Valor a buscar en la lista a partir de el pivote indicado.
  265.  * \return Retorna NULL si no se a encontrado dentro de la lista en caso
  266.  * contrario retorna el elemento .
  267.  *
  268.  */
  269. struct list_item*
  270. list_findnext(list_t list,
  271.              struct list_item *item,
  272.              list_value_t value);
  273.  
  274.  
  275. /** \brief Busca un valor a partir de un pivote indicado dentro de una lista.
  276.  *
  277.  * \param list: Lista a la que pertenecen los elementos.
  278.  * \param item: Elemento pivote desde el cual se empezara a buscar el valor indicado en value,
  279.  * si es NULL iniciara a buscar desde el final de la lista.
  280.  * \param value: Valor a buscar en la lista antes de el pivote indicado.
  281.  * \return Retorna NULL si no se a encontrado dentro de la lista en caso
  282.  * contrario retorna el puntero al item.
  283.  */
  284. struct list_item*
  285. list_findprev(list_t list,
  286.              struct list_item *item,
  287.              list_value_t value);
  288.  
  289. #ifdef LIST_INTEGRAL_RELATIONSHIP
  290. /** \brief Obtiene la lista a la cual pertenece un item.
  291.  *
  292.  * \param item: elemento a consultar.
  293.  * \return Devuelve la lista a la cual pertenece dicho item; NULL si no pertenece a ninguna lista.
  294.  *
  295.  */
  296. list_t
  297. list_getlist(struct list_item *item);
  298. #endif
  299.  
  300. /** \brief Mezcla dos listas generando una nueva lista que deberá ser liberada con list_release().
  301.  *
  302.  * \param list1: Los elementos de esta lista se agregaran al inicio.
  303.  * \param list2: Los elementos de esta lista se agregaran al seguidos de los de list1.
  304.  * \return Retorna una nueva lista que  contendrán  las copias de las dos listas espesificadas.
  305.  *
  306.  */
  307. list_t
  308. list_join(list_t list1,
  309.          list_t list2);
  310.  
  311. /** \brief Agrega un valor al final de la lista.
  312.  *
  313.  * \param list: lista a la cual se le agregara un elemento nuevo.
  314.  * \param value: Valor a agregar a la lista.
  315.  * \return Retorna el puntero al item en la lista, NULL si fallo.
  316.  *
  317.  */
  318. struct list_item*
  319. list_pushback(list_t list,
  320.              list_value_t value);
  321.  
  322. /** \brief Agrega un elemento struct list_item al final de la lista (No crea un duplicado del elemento).
  323.  *
  324.  * \param list: lista a la cual se le agregara un elemento nuevo.
  325.  * \param item: Puntero al elemento struct list_item a relacionar con la lista.
  326.  * \return Retorna el puntero al item en la lista (el retorno es igual a el parámetro item), NULL si fallo.
  327.  *
  328.  */
  329. struct list_item*
  330. list_pushback_item (list_t list,
  331.                    struct list_item *item);
  332.  
  333. /** \brief Agrega un valor al inicio de la lista.
  334.  *
  335.  * \param list: Lista a la cual se le agregara un elemento nuevo.
  336.  * \param value: Valor a agregar a la lista.
  337.  * \return Retorna el puntero al item en la lista.
  338.  *
  339.  */
  340. struct list_item*
  341. list_pushfront(list_t list,
  342.               list_value_t value);
  343.  
  344. /** \brief Agrega un elemento struct list_item al inicio de la lista (No crea un duplicado del elemento).
  345.  *
  346.  * \param list: lista a la cual se le agregara un elemento nuevo.
  347.  * \param item: Puntero al elemento struct list_item a relacionar con la lista.
  348.  * \return Retorna el puntero al item en la lista (el retorno es igual a el parámetro item), NULL si fallo.
  349.  *
  350.  */
  351. struct list_item*
  352. list_pushfront_item (list_t list,
  353.                     struct list_item *item);
  354.  
  355. /** \brief Agrega un valor en la lista después de un elemento indicado como pivote.
  356.  *
  357.  * \param list: lista en la que se agregara.
  358.  * \param pivot: Elemento pivote que esta dentro de una lista, si el valor es NULL value se agregara al final de la lista.
  359.  * \param value: Valor a agregar a la lista después del pivote.
  360.  * \return Retorna el puntero al item en la lista, NULL si fallo.
  361.  *
  362.  */
  363. struct list_item*
  364. list_pushnext(list_t list,
  365.              struct list_item *pivot,
  366.              list_value_t value);
  367.  
  368. /** \brief Agrega un elemento struct list_item después de un elemento indicado como pivote (No crea un duplicado del elemento).
  369.  *
  370.  * \param list: lista en la que se agregara.
  371.  * \param pivot: Elemento pivote que esta dentro de una lista, si el valor es NULL itemnew se agregara al final de la lista.
  372.  * \param itemnew: Puntero al elemento struct list_item a relacionar con la lista.
  373.  * \return Retorna el puntero al item en la lista (el retorno es igual a el parámetro itemnew), NULL si fallo.
  374.  *
  375.  */
  376. struct list_item*
  377. list_pushnext_item(list_t list,
  378.                   struct list_item *pivot,
  379.                   struct list_item *itemnew);
  380.  
  381.  
  382. /** \brief Agrega un elemento en la lista antes de un elemento indicado.
  383.  *
  384.  * \param list: lista en la que se agregara.
  385.  * \param pivot: Elemento pivote que esta dentro de una lista, si el valor es NULL value se agregara al final de la lista.
  386.  * \param value: Valor a agregar a la lista antes del pivote.
  387.  * \return Retorna el puntero al item en la lista, NULL si fallo.
  388.  *
  389.  */
  390. struct list_item*
  391. list_pushprev(list_t list,
  392.              struct list_item *pivot,
  393.              list_value_t value);
  394.  
  395. /** \brief Agrega un elemento struct list_item antes de un elemento indicado como pivote (No crea un duplicado del elemento).
  396.  *
  397.  * \param list: lista en la que se agregara.
  398.  * \param pivot: Elemento pivote que esta dentro de una lista, si el valor es NULL itemnew se agregara al final de la lista.
  399.  * \param itemnew: Puntero al elemento struct list_item a relacionar con la lista.
  400.  * \return Retorna el puntero al item en la lista (el retorno es igual a el parámetro itemnew), NULL si fallo.
  401.  *
  402.  */
  403. struct list_item*
  404. list_pushprev_item(list_t list,
  405.                   struct list_item *pivot,
  406.                   struct list_item *itemnew);
  407.  
  408. /** \brief Destruye una lista, los elementos también son liberados.
  409.  *
  410.  * \param list: Puntero a la struct list a destruir.
  411.  */
  412. void
  413. list_release(list_t list);
  414.  
  415. /** \brief Obtiene la cantidad de elementos en la lista.
  416.  *
  417.  * \param list: Lista de la cual se retornaran la cantidad de elementos almacenados en ella.
  418.  * \return Retorna la cantidad de elementos en la lista.
  419.  *
  420.  */
  421. size_t
  422. list_size(list_t list);
  423.  
  424. /** \brief Intercambia los elementos de cada lista.
  425.  *
  426.  * \param list1: Lista involucrada que se cambiaran los elementos con list2.
  427.  * \param list2: Lista involucrada que se cambiaran los elementos con list1.
  428.  * \return Retorna TRUE si no hubo errores y FALSE si no se puedo intercambiar los elementos.
  429.  *
  430.  */
  431. void
  432. list_swap(list_t list1,
  433.          list_t list2);
  434.  
  435. #endif // LIST_H_INCLUDED
  436.  
  437.  

list.c
Código
  1. #include "include/List.h"
  2.  
  3. /** \brief callback predeterminado que se encarga de crear un duplicado del queue_value_t para el stack_item_t.
  4.   *
  5.   * \param value: queue_value_t que se asignara.
  6.   * \return Debe retornarse el queue_value_t a asignar al stack_item_t que se esta creando.
  7.   *
  8.   */
  9. list_value_t
  10. list_callback_clone_item_default(const list_value_t value) {
  11.    return value;
  12. }
  13.  
  14.  
  15. /** \brief callback predeterminado que se encarga de destruir la memoria asignada al stack_item_t.
  16.   *
  17.   * \param value: queue_value_t que se liberara.
  18.   *
  19.   */
  20. void
  21. list_callback_release_item_default(const list_value_t value) {
  22.    /// none code
  23. }
  24.  
  25.  
  26. /** \brief callback predeterminado que se encarga comparar dos list_value_t.
  27.   *
  28.   * \param value1: se comparara con value2.
  29.   * \param value2: se comparara con value1.
  30.   * \return Retorna el resultado de la comparación.
  31.   * LIST_CMP_LESS_THAT: Si value1 < value2.
  32.   * LIST_CMP_EQUAL: Si value1 == value2.
  33.   * LIST_CMP_GREATER_THAT: Si value1 > value2.
  34.   *
  35.   */
  36. enum list_cmp
  37. list_callback_compare_item_default(const list_value_t value1,
  38.                                   const list_value_t value2) {
  39.    if (value1 > value2) {
  40.        return LIST_CMP_GREATER_THAT;
  41.    } else if (value1 < value2) {
  42.        return LIST_CMP_LESS_THAT;
  43.    }
  44.    return LIST_CMP_EQUAL;
  45. }
  46.  
  47. struct list_item*
  48. list_after(struct list_item *item) {
  49.    return item ? item->next : NULL;
  50. }
  51.  
  52. list_t
  53. list_allocator(list_callback_clone_item       clone_item,
  54.               list_callback_release_item     release_item,
  55.               list_callback_compare_item     compare_item) {
  56.    list_t list = malloc(sizeof (struct list));
  57.    list->first = list->last = NULL;
  58. #ifdef LIST_INTEGRAL_RELATIONSHIP
  59.    list->size = 0;
  60. #endif //LIST_INTEGRAL_RELATIONSHIP
  61.    list->clone_item = clone_item ? clone_item : list_callback_clone_item_default;
  62.    list->release_item = release_item ? release_item : list_callback_release_item_default;
  63.    list->compare_item = compare_item ? compare_item : list_callback_compare_item_default;
  64.    return list;
  65. }
  66.  
  67. void
  68. list_allocator_array(list_t *array,
  69.                     size_t n,
  70.                     list_callback_clone_item       clone_item,
  71.                     list_callback_release_item     release_item,
  72.                     list_callback_compare_item     compare_item) {
  73.    for (register size_t i = 0; i < n; ++i)
  74.        array[i] = list_allocator(clone_item, release_item, compare_item);
  75. }
  76.  
  77. struct list_item*
  78. list_assign(list_t list,
  79.            size_t n,
  80.            list_value_t value) {
  81.    struct list_item *ret = NULL;
  82.  
  83.    if (!list)
  84.        return NULL;
  85.  
  86.    list_clear(list);
  87.    ret = (n > 0) ? list_pushback(list, value) : NULL;
  88.  
  89.    for (register size_t i = 1; i < n; i++)
  90.        list_pushback(list, value);
  91.  
  92.    return ret;
  93. }
  94.  
  95. struct list_item*
  96. list_back(list_t list) {
  97.    return list ? list->last : NULL;
  98. }
  99.  
  100. struct list_item*
  101. list_before(struct list_item *item) {
  102.    return item ? item->prev : NULL;
  103. }
  104.  
  105. struct list_item*
  106. list_begin(list_t list) {
  107.    return list ? list->first : NULL;
  108. }
  109.  
  110. size_t
  111. list_clear(list_t list) {
  112.    struct list_item *item = NULL;
  113.    size_t     ret = 0;
  114.    while((item = list->first) != NULL) {
  115.        list_erase(list, item);
  116.        ++ret;
  117.    }
  118.    return ret;
  119. }
  120.  
  121. list_t
  122. list_clone(list_t list) {
  123.    list_t ret = NULL;
  124.    struct list_item *item = NULL;
  125.  
  126.    if (!list)
  127.        return NULL;
  128.  
  129.    ret = list_allocator(list->clone_item, list->release_item, list->compare_item);
  130.  
  131.    for (item = list_begin(list); item != NULL; item = list_after(item))
  132.        list_pushback(ret, item->value);
  133.  
  134.    return ret;
  135. }
  136.  
  137. size_t
  138. list_copy(list_t list,
  139.          struct list_item *dst,
  140.          struct list_item *src,
  141.          size_t n) {
  142.    size_t ret = 0;
  143.  
  144.    if (!(dst && src)) return 0;
  145. #ifdef LIST_INTEGRAL_RELATIONSHIP
  146.    if (!(dst->list && dst->list == list)) return 0;
  147. #endif //LIST_INTEGRAL_RELATIONSHIP
  148.  
  149.    while (n > 0 && src != NULL) {
  150.        list_pushback(list, src->value);
  151.        src = src->next;
  152.        --n; ++ret;
  153.    }
  154.  
  155.    return ret;
  156. }
  157.  
  158. bool
  159. list_empty(list_t list) {
  160.    return  list && list->first && list->last ? true : false;
  161. }
  162.  
  163. void
  164. list_erase(list_t list,
  165.           struct list_item *item) {
  166.    if (!(item && list)) return;
  167. #ifdef LIST_INTEGRAL_RELATIONSHIP
  168.    else if (item->list != list) return;
  169. #endif //LIST_INTEGRAL_RELATIONSHIP
  170.    if (list && list->release_item)
  171.        list->release_item(item->value);
  172.  
  173.    free(list_extract(list, item));
  174. }
  175.  
  176. void
  177. list_release_item(struct list_item *item,
  178.                  list_callback_release_item callback_release_value) {
  179.    if (!item)
  180.        return;
  181.  
  182.    if (callback_release_value)
  183.        callback_release_value(item->value);
  184. #ifdef LIST_INTEGRAL_RELATIONSHIP
  185.    free(list_extract(NULL, item));
  186. #else
  187.    free(list_extract(NULL, item));
  188. #endif // LIST_INTEGRAL_RELATIONSHIP
  189. }
  190.  
  191. struct list_item*
  192. list_extract(list_t list,
  193.             struct list_item *item) {
  194.    if (!item) return NULL;
  195. #ifdef LIST_INTEGRAL_RELATIONSHIP
  196.    else if (item->list != list) return NULL;
  197. #endif // LIST_INTEGRAL_RELATIONSHIP
  198.  
  199.    if (list) {
  200.        if (list->first == item) list->first = item->next;
  201.        if (list->last == item) list->last = item->prev;
  202.  
  203.    } else if (item->prev || item->next) {
  204.        return NULL;
  205.    }
  206.    if (item->prev) item->prev->next = item->next;
  207.    if (item->next) item->next->prev = item->prev;
  208.    item->prev = NULL;
  209.    item->next = NULL;
  210. #ifdef LIST_INTEGRAL_RELATIONSHIP
  211.    --(list->size);
  212.    item->list = NULL;
  213. #endif // LIST_INTEGRAL_RELATIONSHIP
  214.    return item;
  215. }
  216.  
  217. struct list_item*
  218. list_findnext(list_t list,
  219.              struct list_item *item,
  220.              list_value_t value) {
  221.  
  222.    if (!list) return NULL;
  223.    else if (!list->compare_item) return NULL;
  224.    if (!item) item = list->first;
  225. #ifdef LIST_INTEGRAL_RELATIONSHIP
  226.    else if (item->list != list) return NULL;
  227. #endif // LIST_INTEGRAL_RELATIONSHIP
  228.  
  229.    struct list_item   *now = item;
  230.  
  231.    do {
  232.        if ((list->compare_item)(now->value, value) & LIST_CMP_EQUAL)
  233.            return now;
  234.        now = now->next;
  235.    } while (now);
  236.  
  237.    return NULL;
  238. }
  239.  
  240. struct list_item*
  241. list_findprev(list_t list,
  242.              struct list_item *item,
  243.              list_value_t value) {
  244.    if (!list) return NULL;
  245.    else if (!list->compare_item) return NULL;
  246.    if (!item) item = list->last;
  247. #ifdef LIST_INTEGRAL_RELATIONSHIP
  248.    else if (item->list != list) return NULL;
  249. #endif // LIST_INTEGRAL_RELATIONSHIP
  250.  
  251.    struct list_item   *now = item;
  252.  
  253.    do {
  254.        if ((list->compare_item)(now->value, value) & LIST_CMP_EQUAL)
  255.            return now;
  256.        now = now->prev;
  257.    } while (now);
  258.  
  259.    return NULL;
  260. }
  261.  
  262. #ifdef LIST_INTEGRAL_RELATIONSHIP
  263. list_t
  264. list_getlist(struct list_item *item) {
  265.    if (!item) return NULL;
  266.    return item->list;
  267. }
  268. #endif // LIST_INTEGRAL_RELATIONSHIP
  269.  
  270. list_t
  271. list_join(list_t list1,
  272.          list_t list2) {
  273.    list_t              list = list_clone(list1);
  274.    struct list_item    *item = NULL;
  275.  
  276.    for (item = list_begin(list2); item != NULL; item = list_after(item))
  277.        list_pushback(list, item->value);
  278.    return list;
  279. }
  280.  
  281. struct list_item*
  282. list_pushback(list_t list,
  283.              list_value_t value) {
  284.    struct list_item   *itemnew = NULL;
  285.  
  286.    if (list && !list->clone_item)
  287.        return NULL;
  288.  
  289.    itemnew = malloc(LIST_SIZE_ITEM);
  290. #ifdef LIST_INTEGRAL_RELATIONSHIP
  291.    itemnew->list = NULL;
  292. #endif
  293.  
  294.    if (list_pushback_item(list, itemnew) != itemnew) {
  295.        free(itemnew);
  296.        return NULL;
  297.    }
  298.  
  299.    itemnew->value = (list->clone_item)(value);
  300.  
  301.    return list->last;
  302. }
  303.  
  304. struct list_item*
  305. list_pushback_item (list_t list,
  306.                    struct list_item *item) {
  307. #ifdef LIST_INTEGRAL_RELATIONSHIP
  308.    if (!(list && item && !item->list))
  309.        return NULL;
  310. #else
  311.    if (!(list && item))
  312.        return NULL;
  313. #endif // LIST_INTEGRAL_RELATIONSHIP
  314.  
  315.    if (!(list->first && list->last)) {
  316.        list->first = item;
  317.        item->prev = NULL;
  318.    } else {
  319.        list->last->next = item;
  320.        item->prev = list->last;
  321.    }
  322.  
  323.    item->next = NULL;
  324. #ifdef LIST_INTEGRAL_RELATIONSHIP
  325.    ++(list->size);
  326.    item->list = list;
  327. #endif // LIST_INTEGRAL_RELATIONSHIP
  328.    list->last = item;
  329.  
  330.    return item;
  331. }
  332.  
  333. struct list_item*
  334. list_pushfront(list_t list,
  335.               list_value_t value) {
  336.    struct list_item   *itemnew = NULL;
  337.  
  338.    if (list || !list->clone_item)
  339.        return NULL;
  340.  
  341.    itemnew = malloc(LIST_SIZE_ITEM);
  342. #ifdef LIST_INTEGRAL_RELATIONSHIP
  343.    itemnew->list = NULL;
  344. #endif // LIST_INTEGRAL_RELATIONSHIP
  345.  
  346.    if (list_pushfront_item(list, itemnew) != itemnew) {
  347.        free(itemnew);
  348.        return NULL;
  349.    }
  350.    itemnew->value = (list->clone_item)(value);
  351.  
  352.    return list->first;
  353. }
  354.  
  355. struct list_item*
  356. list_pushfront_item(list_t list,
  357.                    struct list_item *item) {
  358. #ifdef LIST_INTEGRAL_RELATIONSHIP
  359.    if (!(list && item && !item->list))
  360.        return NULL;
  361. #else
  362.    if (!(list && item))
  363.        return NULL;
  364. #endif // LIST_INTEGRAL_RELATIONSHIP
  365.  
  366.    if (!(list->first && list->last)) {
  367.        list->last = item;
  368.        item->next = NULL;
  369.    } else {
  370.        list->first->prev = item;
  371.        item->next = list->first;
  372.    }
  373.  
  374.    item->prev = NULL;
  375.  
  376. #ifdef LIST_INTEGRAL_RELATIONSHIP
  377.    ++(list->size);
  378.    item->list = list;
  379. #endif // LIST_INTEGRAL_RELATIONSHIP
  380.  
  381.    list->first = item;
  382.  
  383.    return item;
  384. }
  385.  
  386. struct list_item*
  387. list_pushnext(list_t list,
  388.              struct list_item *pivot,
  389.              list_value_t value) {
  390.    if (!list) return NULL;
  391.    if (!pivot) pivot = list->last;
  392. #ifdef LIST_INTEGRAL_RELATIONSHIP
  393.    else if (pivot->list != list) return NULL;
  394. #endif // LIST_INTEGRAL_RELATIONSHIP
  395.  
  396.    struct list_item *itemnew = malloc(LIST_SIZE_ITEM);
  397.  
  398.    if (list_pushnext_item(list, pivot, itemnew) != itemnew) {
  399.        free(itemnew);
  400.        return NULL;
  401.    }
  402.  
  403.    itemnew->value = (list->clone_item)(value);
  404.  
  405.    return itemnew;
  406. }
  407.  
  408. struct list_item*
  409. list_pushnext_item(list_t list,
  410.                   struct list_item *pivot,
  411.                   struct list_item *itemnew) {
  412.  
  413.    if (!(list && itemnew)) return NULL;
  414.    if (!pivot) pivot = list->last;
  415. #ifdef LIST_INTEGRAL_RELATIONSHIP
  416.    else if (pivot->list != list) return NULL;
  417. #endif // LIST_INTEGRAL_RELATIONSHIP
  418.  
  419.    if (pivot) {
  420.        if (!pivot->next)
  421.            return list_pushback_item(list, itemnew);
  422.        pivot->next->prev = itemnew;
  423.        itemnew->next = pivot->next;
  424.        pivot->next = itemnew;
  425.        itemnew->prev = pivot;
  426. #ifdef LIST_INTEGRAL_RELATIONSHIP
  427.        ++(itemnew->list->size);
  428.        itemnew->list = pivot->list;
  429. #endif // LIST_INTEGRAL_RELATIONSHIP
  430.        return itemnew;
  431.    } else {
  432.        return list_pushback_item(list, itemnew);
  433.    }
  434.  
  435.    return NULL;
  436. }
  437.  
  438. struct list_item*
  439. list_pushprev(list_t list,
  440.              struct list_item *pivot,
  441.              list_value_t value) {
  442.  
  443.    if (!list) return NULL;
  444.    if (!pivot) pivot = list->first;
  445. #ifdef LIST_INTEGRAL_RELATIONSHIP
  446.    else if (pivot->list != list) return NULL;
  447. #endif // LIST_INTEGRAL_RELATIONSHIP
  448.  
  449.    struct list_item *itemnew = malloc(LIST_SIZE_ITEM);
  450.  
  451.    if (list_pushprev_item(list, pivot, itemnew) != itemnew) {
  452.        free(itemnew);
  453.        return NULL;
  454.    }
  455.  
  456.    itemnew->value = (list->clone_item)(value);
  457.  
  458.    return itemnew;
  459. }
  460.  
  461. struct list_item*
  462. list_pushprev_item(list_t list,
  463.                   struct list_item *pivot,
  464.                   struct list_item *itemnew) {
  465.  
  466.    if (!(list && itemnew)) return NULL;
  467.    if (!pivot) pivot = list->first;
  468. #ifdef LIST_INTEGRAL_RELATIONSHIP
  469.    else if (pivot->list != list) return NULL;
  470. #endif // LIST_INTEGRAL_RELATIONSHIP
  471.  
  472.    if (pivot) {
  473.        if (!pivot->prev)
  474.            return list_pushfront_item(list,itemnew);
  475.        pivot->prev->next = itemnew;
  476.        itemnew->prev = pivot->prev;
  477.        pivot->prev = itemnew;
  478.        itemnew->next = pivot;
  479. #ifdef LIST_INTEGRAL_RELATIONSHIP
  480.        itemnew->list = pivot->list;
  481.        ++(itemnew->list->size);
  482. #endif // LIST_INTEGRAL_RELATIONSHIP
  483.        return itemnew;
  484.    } else {
  485.        return list_pushfront_item(list,itemnew);
  486.    }
  487.  
  488.    return NULL;
  489. }
  490.  
  491. void
  492. list_release(list_t list) {
  493.    list_clear(list);
  494.    free(list);
  495. }
  496.  
  497. void
  498. list_release_array(list_t *array,
  499.                   size_t n) {
  500.    for (register size_t i = 0; i < n; ++i)
  501.        list_release(array[i]);
  502. }
  503.  
  504. size_t
  505. list_size(list_t list) {
  506. #ifdef LIST_INTEGRAL_RELATIONSHIP
  507.    return list ? list->size : 0;
  508. #else
  509.    size_t ret = 0;
  510.    struct list_item *item = list ? list->first : NULL;
  511.    while (item) {
  512.        ++ret;
  513.        item = item->next;
  514.    }
  515.    return ret;
  516. #endif // LIST_INTEGRAL_RELATIONSHIP
  517. }
  518.  
  519. void
  520. list_swap(list_t list1,
  521.          list_t list2) {
  522.    if (!(list1 && list2)) return;
  523.    struct list tmp = *list2;
  524.    *list2 = *list1;
  525.    *list1 = tmp;
  526. #ifdef LIST_INTEGRAL_RELATIONSHIP
  527.    for (struct list_item *item = list_begin(list1); item != NULL; item = list_after(item))
  528.        item->list = list1;
  529.    for (struct list_item *item = list_begin(list2); item != NULL; item = list_after(item))
  530.        item->list = list2;
  531. #endif // LIST_INTEGRAL_RELATIONSHIP
  532. }
  533.  

Dulces Lunas!¡.


« Última modificación: 15 Enero 2013, 09:10 am por BlackZeroX (Astaroth) » En línea

The Dark Shadow is my passion.
BlackZeroX
Wiki

Desconectado Desconectado

Mensajes: 3.158


I'Love...!¡.


Ver Perfil WWW
Re: [SRC-C99] Para que dejen de preguntar por las listas.
« Respuesta #1 en: 15 Enero 2013, 07:18 am »

Dos simples códigos de ejemplo:

Use algunos Cast para que se entienda...

Solo numeros o punteros o cualquier cosa no mayor a un sizeof(list_value_t).
Código
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include <inttypes.h>
  5. //#include "include/CSAVL.h"
  6. //#include "include/CSMap.h"
  7. #include "include/CSList.h"
  8. //#include "include/CSQueue.h"
  9. //#include "include/CScript.h"
  10. //#include "include/CSUtiles.h"
  11.  
  12. uint32_t min(uint32_t a, uint32_t b);
  13. void    swap(int32_t *a, int32_t *b);
  14. int32_t randomnumber(int32_t lower, int32_t upper);
  15. void    test();
  16.  
  17. int main() {
  18.    list_t list1 = list_allocator(NULL, NULL, NULL);
  19.    struct list_item *item = NULL;
  20.  
  21.    puts("Prueba de list_t");
  22.  
  23.    puts("Ingresando datos.");
  24.    for (uint_fast32_t i = 0; i < VALUES_TO_ADD; ++i) {
  25.        list_pushback(list1, randomnumber(0, 100));
  26.    }
  27.    puts("fin de insercion de los datos.\n");
  28.  
  29.    puts("Liberando memoria de list_t"); list_clear(list1);
  30.    printf("\n\nOK\n");
  31.    getchar();
  32.  
  33.    return EXIT_SUCCESS;
  34. }
  35.  
  36. uint32_t min(uint32_t a, uint32_t b) {
  37.    return (a<b) ? a:b;
  38. }
  39.  
  40. void swap(int32_t *a, int32_t *b) {
  41.    *a ^= *b;
  42.    *b ^= *a;
  43.    *a ^= *b;
  44. }
  45.  
  46. int32_t randomnumber(int32_t lower, int32_t upper) {
  47.    if (min(lower, upper) != lower) {
  48.        swap(&lower, &upper);
  49.    }
  50.    return lower + rand() % ((upper + 1) - lower);
  51. }
  52.  

Con estructuras:

Código
  1. struct persona_datos {
  2.    char *nombre;
  3.    char apellido[256];
  4.    unsigned edad;
  5. };
  6. long    min(uint32_t a, uint32_t b);
  7. void    swap(int32_t *a, int32_t *b);
  8. int32_t randomnumber(int32_t lower, int32_t upper);
  9. void    test();
  10.  
  11.  
  12. list_value_t
  13. callback_clone_item(const list_value_t value) {
  14.    if (!value) return NULL; /**< No hay nada que clonar */
  15.    struct persona_datos *__ptr = (struct persona_datos *)value; /**< Original */
  16.    struct persona_datos *__new = (struct persona_datos *)malloc(sizeof (struct persona_datos));
  17.    size_t __ln = 0;
  18.  
  19.    if (__ptr->nombre) { // nombre es un puntero a un array char por ello reservamos memoria.
  20.        if ((__ln = strlen(__ptr->nombre)) > 0) {
  21.            __new->nombre = (char*)malloc((__ln + 1));// * sizeof(char)); // Omitimos.
  22.            strcpy(__new->nombre, __ptr->nombre);
  23.        }
  24.    }
  25.    strcpy(__new->apellido, __ptr->apellido); // apellido e suna rray no un puntero...
  26.    __new->edad = __ptr->edad;
  27.  
  28.    return (list_value_t)__new; /**< retornamos __new. */
  29. }
  30.  
  31. void
  32. callback_release_item(const list_value_t value) {
  33.    if (!value) return; /**< No hay nada que liberar */
  34.    struct persona_datos *__ptr = (struct persona_datos *)value; /**< Original esta se creo en el callback callback_clone_item() */
  35.    free(__ptr->nombre);
  36.    free(__ptr);
  37. }
  38.  
  39. enum list_cmp
  40. callback_compare_item(const list_value_t value1,
  41.                      const list_value_t value2) {
  42.    struct persona_datos *__ptr1 = (struct persona_datos *)value1;
  43.    struct persona_datos *__ptr2 = (struct persona_datos *)value2;
  44.    /**< Comparamos las edades */
  45.    if (__ptr1->edad > __ptr2->edad) {
  46.        return LIST_CMP_GREATER_THAT;
  47.    } else if (__ptr1->edad < __ptr2->edad) {
  48.        return LIST_CMP_LESS_THAT;
  49.    }
  50.    return LIST_CMP_EQUAL;
  51. }
  52.  
  53. int main() {
  54.    list_t list1 = list_allocator(callback_clone_item,
  55.                                  callback_release_item,
  56.                                  callback_compare_item);
  57.    struct persona_datos dato = {};
  58.    char buff[256] = {}; /**< Buffer usado en miembro nombre. */
  59.  
  60.    puts("Prueba de list_t");
  61.  
  62.    puts("Ingresando datos.");
  63.    dato.nombre = buff;
  64.    for (uint_fast32_t i = 0; i < VALUES_TO_ADD; ++i) {
  65.        dato.edad = randomnumber(0, 100);
  66.        sprintf(dato.nombre, "Nombre %"PRIdFAST32, i); /**< dato.nombre apunta a un buffer de 256 caracteres */
  67.        sprintf(dato.apellido, "Apellido %"PRIdFAST32, i);
  68.        list_pushback(list1, (list_value_t)&dato);
  69.    }
  70.    puts("fin de insercion de los datos.\n");
  71.  
  72.    puts("Liberando memoria de list_t"); list_clear(list1);
  73.    printf("\n\nOK\n");
  74.    getchar();
  75.  
  76.    return EXIT_SUCCESS;
  77. }
  78.  

Dulces Lunas!¡.


« Última modificación: 15 Enero 2013, 09:09 am por BlackZeroX (Astaroth) » En línea

The Dark Shadow is my passion.
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Manejar listas doblemente enlazadas en C desde ASM
ASM
danndres 1 2,370 Último mensaje 13 Octubre 2014, 23:26 pm
por xv0
Ayuda para crear Listas doblemente enlazadas
Programación C/C++
kur79 0 1,993 Último mensaje 25 Octubre 2014, 16:35 pm
por kur79
Ayuda! Listas Doblemente Enlazadas
Programación C/C++
mordeki_99 0 1,572 Último mensaje 30 Noviembre 2015, 00:45 am
por mordeki_99
como crear funciones para listas enlazadas en c++?
Programación C/C++
KINGARZA 3 3,058 Último mensaje 14 Julio 2016, 23:52 pm
por AlbertoBSD
Programa en c++ listas doblemente enlazadas
Programación C/C++
Diosa21 0 9,636 Último mensaje 29 Marzo 2017, 19:48 pm
por Diosa21
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines