Я начал экспериментировать с (void *) в C, чтобы работать с динамическими типами данных, то есть обойти необходимость передачи определенного типа данных.
Я реализовал этот двусвязный список на C и постарался сделать его универсальным, чтобы он мог хранить данные любого типа (примитивные и непримитивные). Я буду рад получить отзывы и идеи о том, как улучшить мою реализацию. в рамках моего пути изучения этого предмета я пытаюсь создать мини-библиотеку общих структур данных, таких как стеки, связанные списки, двоичные деревья и т. д., которые будут работать с любым типом.
вот реализация моего двусвязного списка. Я получил тип данных «Динамический» (я не уверен, что это правильный термин), попросив пользователя предоставить конструктор, деструктор и функцию сравнения для объектов, которые он хотел бы сохранить в списке. LinkedList.h
/*
Implements doubly linked list.
---------- ---------- ----------
| HEAD | <------> | NODE | <------> | TAIL |
---------- ---------- ----------
The linked list is generic and may hold any kind of data (from the same type!) given a proper constructor function for that type.
Created by: @BAxBI as part of General DataStructure library for C.
*/
#ifndef __LINKED__LIST_H_
#define __LINKED__LIST__H_
#include <stdlib.h>
/*
@brief Linked List item.
*/
typedef void * LItem;
/*
@brief Constant Linked List item.
*/
typedef const void * CLItem;
/*
@brief Linked List type.
*/
typedef struct LList * LList;
/*
Creates a new empty linked list
@param ctor Pointer to a constructor function for an element in the list.
@param dtor Pointer to a destructor function for an element in the list.
@param compare Pointer to a comparison function between two elements in the list
@param print Pointer to a print function of an element in the list.
@return Pointer to an emty linked list
*/
LList new_linked_list(LItem (*ctor)(LItem),void (*dtor)(LItem), int (*compare)(LItem, LItem), void (*print)(LItem));
/*
Adds a node to the head of the list.
@param list The list to add the element to.
@param item A pointer to the item to add to the list.
*/
void add_node(LList list, LItem item);
/*
Deletes the first occurrence of an item in the list.
@param list The list to delete the item from.
@param item The item to delete.
*/
void delete_node(LList list, LItem item);
/*
Destroys a linked list and frees all the allocated memory.
@param list The linked list to destroy.
*/
void destroy_linked_list(LList list);
/*
Gets an element from the Linked List.
@param list The list to get the element from.
@param element The element to get from the list.
@return The element from the list if exist NULL otherwise
*/
LItem get_element_from_LList(LList list, LItem element);
/*
Gets the number of elements in the linked list.
@param list The list the check its number of elements.
@return The number of elements in the linked list.
*/
size_t get_No_elem_LList(LList list);
/*
Prints the linked list (if given a print function to print a single element!)
@param list The linked list to be printed.
*/
void print_list(LList list);
#endif
LinkedList.c
#include #include #include "LinkedList.h" typedef struct Node{ struct Node *prev_node; структура узла *next_node; LItem node_content; }Узел; struct LList { Узел *head; Узел *хвост; size_t Нет элементов; // Функции, предоставляемые клиентом. LItem (*ctor)(LItem); пустота (*dtor)(LItem); int (*сравнить)(LItem, LItem); недействительным (* печать) (LItem); }; LList new_linked_list(LItem (*ctor)(LItem),void (*dtor)(LItem), int (*compare)(LItem, LItem), void (*print)(LItem)){ LList new_llist = calloc(1, sizeof (структура LList)); если (!new_llist){ вернуть NULL; } new_llist->head = NULL; new_llist->хвост = NULL; new_llist->НетЭлементов = 0; new_llist->ctor = ctor; new_llist->dtor = dtor; new_llist->сравнить = сравнить; new_llist->печать = печать; вернуть новый_список; } void add_node(LList list, LItem item){ Node *new_node = (Node *)malloc(sizeof(Node)); если (!new_node) вернуть; новый_узел->следующий_узел = NULL; новый_узел->предыдущий_узел = NULL; new_node->node_content = list->ctor(item); /* Пустой список*/ if(!list->head){ list->head = new_node; список->хвост = новый_узел; } else { new_node->next_node = list->head; список->голова->предыдущий_узел = новый_узел; список->голова = новый_узел; } список->НетЭлементов++; } /* Удаляет первое вхождение узла в связанном списке */ void delete_node(LList list, LItem item){ Node *ptr = list->head; while(ptr != NULL){ if(list->compare(ptr->node_content, item) == 0){ /* Первый удаляемый узел */ if(!ptr->prev_node){ list->head = указатель->следующий_узел; } else if(ptr->prev_node && ptr->next_node){ ptr->next_node->prev_node = ptr->prev_node; ptr->предыдущий_узел->следующий_узел = ptr->следующий_узел; } else { ptr->prev_node->next_node = NULL; } if(list->dtor){ list->dtor(ptr->node_content); } бесплатно (указатель); список->НетЭлементов--; возвращаться; } ptr = ptr->next_node; } } void destroy_linked_list(LList list){ Node *ptr = list->head; while(ptr != NULL){ Узел *tmp = ptr; ptr = ptr->следующий_узел; if(list->dtor){ list->dtor(tmp->node_content); } бесплатно(tmp); } бесплатно (список); } size_t get_No_elem_LList(список LList){ вернуть список->NoElements; } LItem get_element_from_LList(список LList, элемент LItem){ Узел *ptr = list->head; if(!list->head){ printf("Список пуст!\n"); } while(ptr!=NULL){ if(list->compare(ptr->node_content, element) == 0){ return ptr->node_content; } ptr = ptr->next_node; } printf("Искомый элемент отсутствует в связанном списке.\n"); вернуть НУЛЬ; } void print_list(LList list){ if(!list->print) { printf("Предоставленный связанный список не имеет функции печати\n"); возвращаться; } if (!list->head) { printf("Список пуст!\n"); возвращаться; } Узел *ptr = list->head; в то время как (ptr) { список-> печать (ptr-> node_content); if(ptr->next_node){ printf(" "); } else{ printf(" ---> "); } ptr = ptr->next_node; } printf("\033[0;31m"); /* Red */
printf("NULL\n");
printf("\033[0m"); /* Reset */
}
3 Answers
I’ll be glad to have some feedback and ideas on how to improve my implementation.
Overall, A good presentation, yet any linked-list module needs to consider large scale usage.
Bug: Incomplete linking update
On deletion of the 1st node, code does list->head = ptr->next_node;, but does not update the 2nd nodes .prev_node member.
General thought: when a node is deleted, both the left node (or LList) and right node (or LList) need pointer updates, that’s 2 links, never 1.
Only works with pointers
«work with any kind of type» and «asking the user to provide constructor, destructor and comparison function for the objects …» —> With typedef void * LItem;, user can only use with object pointer types. No pointer type checking is expected against void *.
Name space
LinkedList.h declares __LINKED__LIST_H_, LItem, CLItem, LList, add_node, ..., print_list.
Rather then scatter names, consider
DLList.h declares __DLList_H_, DLList_Item, const DLList_Item, DLList, DLList_add, ..., DLList_print.
Casting *alloc()
Casting the result of *alloc() not needed. Be uniform.
LList new_llist = calloc(1, sizeof(struct LList)); // OP did not cast here.
// Node *new_node = (Node *)malloc(sizeof(Node));
Node *new_node = malloc(sizeof(Node));
Allocation failures not detectable by caller
Consider returning a value.
//void add_node(LList list, LItem item){
// Node *new_node = (Node *)malloc(sizeof(Node));
// if (!new_node) return;
// Return error flag
bool add_node(LList list, LItem item){
Node *new_node = (Node *)malloc(sizeof(Node));
if (!new_node) return true;
...
return false;
}
Use const when able
// size_t get_No_elem_LList(LList list){
// return list->NoElements;
// }
size_t get_No_elem_LList(const LList list){
return list->NoElements;
}
Omit console specialized code from print_list()
Delete:
printf("\033[0;31m"); /* Red */
printf("\033[0m"); /* Reset */
get_element_from_LList() error return
get_element_from_LList() returns NULL when item not found, yet NULL may be a valid object added to the list. Now caller does not distinguish success from failure.
I suppose caller could first try get_No_elem_LList(), yet I would prefer a different get interface, something the results in a LItem and a success indication.
Use alternative than printf() to indicate errors
For general purpose list list code, the functions (aside from print_list()) should not call *printf().
Instead pass back to caller an error indication.
Why double linked list??
Tail access nor node deletion from the fail never occurs.
What was the point of a double linked list?
No success indication
I’d expect delete_node() to return something to indicate success/failure.
Asymmetric functions
.dtor is OK to be NULL with if(list->dtor){ list->dtor(ptr->node_content); }.
No such NULL test with new_node->node_content = list->ctor(item);
Documentation in .h file does not discuss this.
Consider instead with new_linked_list() to NULL test once, rather than repeatedly.
// new_llist->dtor = dtor;
new_llist->dtor = dtor ? dtor : dummy_function_that_does_nothing;
Why struct LList??
Why code LList and struct LList? One is enough.
// LList new_llist = calloc(1, sizeof(struct LList));`
LList new_llist = calloc(1, sizeof(LList));`
Even better, allocate to the size of the referenced object, not type.
LList new_llist = calloc(1, sizeof new_llist[0]); // или LList new_llist = calloc(1, sizeof *new_llist);
Включать LinkedList.h первый
Порядок включения не должен иметь значения, но для xxx.cпервое включение должно быть xxx.h. Это прекрасный тест, который xxx.h не полагается на другие включаемые файлы. xxx.h должен сам включать все необходимые включаемые файлы.
// #include <stdlib.h>
// #include <stdio.h>
// #include "LinkedList.h"
#include "LinkedList.h"
#include <stdlib.h>
#include <stdio.h>
Отсутствует пример кода
Рассмотрим main.c который показывает пример использования.
Терпеть destroy_linked_list(NULL)
Как только free(NULL) все в порядке, рассмотрите возможность добавления NULL тест. Это упрощает использование вызывающей стороной destroy_linked_list().
void destroy_linked_list(LList list){
if (list) {
...
}
**Сравните функцию с константными аргументами**
Как LItem это скрытый тип указателя (yech), используйте const поэтому та же функция, используемая для qsort() здесь можно использовать.
// int (*compare)(LItem, LItem);
int (*compare)(const LItem, const LItem);
Включить несоответствие защиты:
#ifndef __LINKED__LIST_H_ #define __LINKED__LIST__H_
Эти два макроса должны быть идентичны!
я не вижу необходимости в <stdlib.h> в шапке — что я пропустил?<stdlib.h> это излишество только для size_t — предпочитать <stddef.h>.
я не фанат typedefs, которые скрывают указатели:
typedef void * LItem; typedef const void * CLItem; typedef struct LList * LList;
Указательность этих типов важна для кода, который их использует.
new_linked_list() использует calloc() для обеспечения хранения с нулевой инициализацией, но затем все равно перезаписывает все элементы. Это пустая трата по сравнению с простым использованием malloc(). (Помните, что нулевое значение всех байтов не делает переносимый нулевой указатель).
add_node() не имеет возможности указать, удалось это или нет. Это может привести к серьезной поломке.
delete_node() не сообщает программе, был ли запрошенный элемент найден и удален; это может быть полезно.
Здесь не нужно лить:
Node *new_node = (Node *)malloc(sizeof(Node));
Возвращение из malloc это void*который можно преобразовать в любой указатель объекта в C. Кроме того, я рекомендую использовать sizeof с выражением, которое соответствует правопреемнику:
Node *new_node = malloc(sizeof *new_node);
Здесь это имеет небольшое преимущество, но гораздо большее, когда присваивается переменная, объявление которой находится далеко.
Стоит рассмотреть узел «фиктивная голова», чтобы мы могли объединить случай «пустого списка». Это обменяет небольшой объем памяти на значительное упрощение кода.
В delete_node()это выглядит как хороший кандидат на for:
Node *ptr = list->head; while (ptr != NULL) { ⋮ ptr = ptr->next_node; }
Встраивание escape-кодов для терминала в выходные данные (printf("\033[0;31m")) явно не переносим и может препятствовать передаче в другие программы. Если вы хотите, чтобы программы использовали возможности терминала, используйте termcap или ncurses для генерации кодов для действительный устройство вывода.
ответил 28 апр в 10:36
Тоби Спейт
Тоби Спейт
Я думаю, что ваш код очень четкий и лаконичный. Однако ваше наименование не дает понять, что на самом деле это двусвязный список. Так что я бы предпочел DLList, DLItem и так далее. Возможно это просто WIP, но ваш DLList реализация не завершена, отсутствует дифференциация между головным и задним доступами.
Ваши комментарии к документации просто вводят повторение. Оставьте их подальше. Пример:
/*
Adds a node to the head of the list.
@param list The list to add the element to.
@param item A pointer to the item to add to the list.
*/
void add_node(LList list, LItem item);
Слово add встречается 4 раза. Слово list появляется 6 раз. Слово node эффективно повторяется 5 раз, считая также item и element, потому что комментарий не является однородным. В 2 случаях используется node в 3 других случаях он использует item соответственно element.
Чтобы улучшить это, вы можете включить свои комментарии в именовании переменных. Например: LItem item_to_add.
Здесь у нас есть случай, о котором упоминалось в предыдущем ответе. Указательная природа LItem скрыт в typedef. Если бы это было не так, звездочка перед именем переменной сделала бы ненужным документировать это. item является указателем.
Свободный пользователь