Implementacja "Multipurpose" linked list w czystym C

To nie jest do końca pytanie techniczne, ponieważ Wiem, że C jest wystarczająco dużo, aby robić rzeczy, które muszę zrobić (mam na myśli, w kategoriach nie "pozwalając językowi wejść w drogę"), więc to pytanie jest w zasadzie pytaniem "w jakim kierunku iść".

Sytuacja jest taka: obecnie biorę udział w kursie zaawansowanych algorytmów i ze względu na "dorastanie jako programiści", jestem zobowiązany do używania czystego C do realizacji zadań praktycznych (działa dobrze: prawie każdy mały błąd robisz faktycznie zmusza cię do całkowitego zrozumienia, co robisz, aby to naprawić). W trakcie implementacji napotykam oczywiście problem konieczności wdrożenia "podstawowych" struktur danych od podstaw: właściwie nie tylko połączonych list, ale także stosów, drzew itp.

Skupiam się na listach w tym temacie, ponieważ zazwyczaj jest to struktura, której używam w programie, albo jako struktura "główna", albo jako struktura "pomocnicza" dla innych większych (dla przykład, drzewo skrótów, które rozwiązuje konflikty za pomocą listy połączonej).

Wymaga to, aby lista przechowywała elementy wielu różnych typów. zakładam tutaj jako założenie, że nie chcę ponownie kodować listy dla każdego typu. Więc mogę wymyślić te alternatywy:

    Nie jest to jednak możliwe, ponieważ nie jest to możliwe.]}
  • Tworzenie tylko jednej listy, ale posiadanie UNII jako 'element type', zawierającej wszystkie typy elementów, których użyję w programie (łatwiejsze do debugowania; marnuje miejsce, jeśli elementy nie są wszystkie o tej samej wielkości)
  • używanie makra preprocesora do regeneracji kodu dla każdego typu, w stylu SGLIB , 'naśladowanie'C++' S STL (creative solution; nie marnuje miejsca; elementy mają wyraźny Typ, którym są, gdy są zwracane; każda zmiana w kodzie listy może być naprawdę dramatyczna)
  • Twój pomysł / rozwiązanie

Aby wyjaśnić pytanie: który z powyżej jest najlepiej?

PS: ponieważ jestem zasadniczo w kontekście akademickim, jestem również bardzo zainteresowany poglądem ludzi pracujących z czystym C w branży. Rozumiem, że większość czystych programistów C znajduje się w obszarze urządzeń wbudowanych, gdzie nie sądzę, aby ten rodzaj problemu, z którym się borykam, był powszechny. Jeśli jednak ktoś wie, jak to się robi "w realnym świecie", byłbym bardzo zainteresowany Twoją opinią.

Author: Bill the Lizard, 2009-04-10
Source

9 answers

A void * jest trochę uciążliwy w powiązanej liście, ponieważ trzeba zarządzać jej alokacją oddzielnie do samej listy. Jedną z metod, których używałem w przeszłości, jest posiadanie struktury o zmiennej wielkości, takiej jak: 

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char payload[1];  // or use different type for alignment.
} tNode;

Teraz zdaję sobie sprawę, że to nie wygląda o zmiennej wielkości, ale przyporządkujmy strukturę w ten sposób: 

typedef struct {
    char Name[30];
    char Addr[50];
} tPerson;
tNode *node = malloc (sizeof (tNode) - 1 + sizeof (tPerson));

Teraz masz węzeł, który, dla wszystkich zamiarów i celów, wygląda tak: 

typedef struct _tNode {
    struct _tNode *prev;
    struct _tNode *next;
    int payloadType;
    char Name[30];
    char Addr[50];
} tNode;

Lub w formie graficznej (gdzie [n] oznacza n bajtów): 

+----------------+
|    prev[4]     |
+----------------+
|    next[4]     |
+----------------+
| payloadType[4] |                
+----------------+                +----------+
|   payload[1]   | <- overlap ->  | Name[30] |
+----------------+                +----------+
                                  | Addr[50] |
                                  +----------+

To znaczy, zakładając, że wiesz, jak poprawnie zaadresować ładunek. Można to zrobić w następujący sposób: 

node->prev = NULL;
node->next = NULL;
node->payloadType = PLTYP_PERSON;
tPerson *person = &(node->payload); // cast for easy changes to payload.
strcpy (person->Name, "Bob Smith");
strcpy (person->Addr, "7 Station St");

Ta linia cast po prostu rzuca adres znaku payload (w typie tNode) jako adres rzeczywistego typu tPerson ładunku.

Za pomocą tej metody można przenosić dowolny typ ładunku w węźle, nawet różne typy ładunku w każdym węźle , bez marnowania przestrzeni Unii. Marnotrawstwo to widać na po: 

union {
    int x;
    char y[100];
} u;

Gdzie 96 bajtów jest marnowanych za każdym razem, gdy zapisujesz Typ integer na liście (dla 4-bajtowej liczby całkowitej).

Typ ładunku w tNode pozwala łatwo wykryć, jaki typ ładunku niesie ten węzeł, więc Twój kod może zdecydować, jak go przetworzyć. Możesz użyć czegoś w następujący sposób: 

#define PAYLOAD_UNKNOWN     0
#define PAYLOAD_MANAGER     1
#define PAYLOAD_EMPLOYEE    2
#define PAYLOAD_CONTRACTOR  3

Lub (prawdopodobnie lepiej): 

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;
 33
Author: paxdiablo,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-10-19 00:42:17

Mój $.002:

  • Tworzenie listy void pointers (trochę diselegant; trudniej debugować)

To nie jest taki zły wybór, IMHO, jeśli musisz pisać w C. możesz dodać metody API, aby aplikacja mogła dostarczyć metodę print () dla ułatwienia debugowania. Podobne metody mogą być wywoływane, gdy (np.) elementy zostaną dodane lub usunięte z listy. (Dla list linkowanych zwykle nie jest to konieczne, ale dla bardziej złożonych struktur danych - np. tabel hashowych) -- może czasami ratujesz mi życie.)

  • Tworzenie tylko jednej listy, ale posiadanie Unii jako 'element type', zawierającej wszystkie typy elementów, których użyję w programie (łatwiejsze do debugowania; marnuje miejsce, jeśli elementy nie są wszystkie o tej samej wielkości)

Unikałbym tego jak zarazy. (Cóż, zapytałeś.) Posiadanie ręcznie skonfigurowanej zależności w czasie kompilacji od struktury danych do zawartych w niej typów jest najgorsze ze wszystkich światów. Znowu IMHO.

  • Używanie makra preprocesora do regeneruje kod dla każdego typu, w stylu SGLIB (sglib.sourceforge.net), "imitujący" C++STL (creative solution; nie marnuje miejsca; elementy mają typ jawny, jakim są, gdy są zwracane; każda zmiana w kodzie listy może być naprawdę dramatyczna)

Intrygujący pomysł, ale ponieważ nie znam SGLIB, nie mogę powiedzieć wiele więcej niż to.

  • twój pomysł / rozwiązanie

Wybrałbym pierwszy wybór.

 8
Author: Dan Breslau,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 00:22:02

Robiłem to w przeszłości, w naszym kodzie (który został przekonwertowany do C++), i w tym czasie zdecydowałem się na podejście void*. Zrobiłem to dla elastyczności - prawie zawsze przechowywaliśmy wskaźnik na liście, a prostota rozwiązania i jego użyteczność przeważyły (dla mnie) wady innych podejść.

To powiedziawszy, był jeden raz, kiedy to spowodowało jakiś paskudny błąd, który był trudny do debugowania, więc zdecydowanie nie jest to idealne rozwiązanie. Myślę, że to wciąż ta, którą bym wziął, gdybym znowu to robił.

 6
Author: Reed Copsey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 00:24:04

Używanie makra preprocesora jest najlepszą opcją. linuksowa lista linuksowa jest doskonałą, wydajną implementacją listy linkowanej w języku C. Jest bardzo przenośna i łatwa w użyciu. Tutaj samodzielna wersja jądra Linuksa 2.6.29 lista.header H.

FreeBSD / OpenBSD sys / queue jest kolejną dobrą opcją dla ogólnej listy linkowanej opartej na makrach

 6
Author: Lear,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-06-07 07:59:44

Nie kodowałem C od lat, ale GLib twierdzi, że zapewnia "duży zestaw funkcji użytkowych dla ciągów i wspólnych struktur danych", wśród których są połączone listy.

 4
Author: Sean McSomething,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 01:05:37

Chociaż kuszące jest myślenie o rozwiązaniu tego rodzaju problemu przy użyciu technik innego języka, powiedzmy generycznych, w praktyce rzadko jest to wygrana. Prawdopodobnie istnieją pewne rozwiązania w puszkach, które przez większość czasu robią to dobrze (i mówią w swojej dokumentacji, gdy się mylą), używając tego, może pominąć punkt przydziału, więc zastanowię się dwa razy. W bardzo niewielu przypadkach może być wykonalne zrolowanie własnego, ale dla projektu o dowolnej rozsądnej wielkości, jego prawdopodobnie nie będzie warte wysiłku debugowania.

Zamiast programowania w języku x, powinieneś używać idiomów języka X. nie pisz Javy, gdy używasz Pythona. Nie pisz C kiedy używasz scheme. Nie pisz C++ gdy używasz C99.

Ja sam prawdopodobnie użyłbym czegoś takiego jak sugestia Paxa, ale w rzeczywistości użyłbym Unii char [1] i void * i int, aby zwykłe przypadki były wygodne (i znacznik typu enumed)

(też bym pewnie skończył implementacja drzewa Fibonacciego, tylko dlatego, że brzmi schludnie, i możesz zaimplementować drzewa RB tyle razy, zanim straci swój smak, nawet jeśli jest to lepsze dla typowych przypadków, do których będzie używany.)

Edit: opierając się na Twoim komentarzu, wygląda na to, że masz całkiem niezły powód do używania puszkowanego rozwiązania. Jeśli twój instruktor na to pozwala, a składnia, którą oferuje, jest wygodna, daj jej wir.

 1
Author: SingleNegationElimination,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 02:06:23

To jest dobry problem. Są dwa rozwiązania, które lubię:

  • Dave Hanson Interfejsy i implementacje C używają listy wskaźników void *, co jest dla mnie wystarczające.

  • Dla moich uczniów , napisałem skrypt awk do generowania funkcji listy specyficznych dla typów. W porównaniu do makr preprocesora wymaga dodatkowego etapu kompilacji, ale działanie systemu jest znacznie bardziej przejrzyste dla programistów bez dużego doświadczenia. I to naprawdę pomaga w przypadku polimorfizmu parametrycznego, który widzą później w swoim programie nauczania.

    Oto jak wygląda jeden zbiór funkcji: 

    int      lengthEL (Explist *l);
Exp*     nthEL    (Explist *l, unsigned n);
Explist *mkEL     (Exp *hd, Explist *tl);

    Skrypt awk jest 150-liniowym horrorem; przeszukuje kod C dla typedef s i generuje zestaw funkcji list dla każdej z nich. Jest bardzo stary, teraz chyba mógłbym zrobić coś lepszego: -)

Nie podałbym listy związków o porze dnia (ani miejsca na dysku twardym). Nie jest bezpieczny i nie można go rozciągać, więc równie dobrze możesz użyć void * i skończyć z tym.
 1
Author: Norman Ramsey,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 02:45:16

Jednym z ulepszeń w stosunku do tworzenia listy void* byłoby uczynienie z niej listy struktur zawierających void * i metadanych o tym, na co wskazuje void*, w tym o jej typie, rozmiarze itp.

Inne pomysły: osadzenie interpretera Perla lub Lispa.

Lub przejdź do połowy: połącz się z biblioteką Perla i zrób z niej listę SVs Perla lub coś w tym stylu.

 0
Author: skiphoppy,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 02:19:55

Sam pewnie wybrałbym podejście void*, ale przyszło mi do głowy, że możesz przechowywać swoje dane jako XML. Wtedy lista może mieć znak * dla danych (które można analizować na żądanie dla dowolnych elementów podrzędnych, których potrzebujesz)....

 0
Author: dicroce,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-10 02:22:43