‚Multipurpose‘ verkettete Liste Umsetzung in reinem C

https://stackoverflow.com/questions/736307

09-09-2019
|

Frage

Dies ist nicht gerade eine technische Frage, da ich C Art genug kennen die Dinge, die ich brauche, um (ich meine, in Bezug auf die nicht ‚im Stich gelassen die Sprache bekommen im Weg‘) zu tun, so dass diese Frage ist im Grunde ein ‚welche Richtung nehmen‘ Frage.

Situation ist: Ich derzeit eine erweiterte Algorithmen natürlich und im Interesse des "aufwächst als Programmierer nehme ich verpflichtet ist, reine C zu verwenden, um die praktischen Aufgaben zu implementieren (es funktioniert gut: so ziemlich jeder kleinen Fehlers, den Sie macht tatsächlich zwingt Sie vollständig zu verstehen, was Sie damit tun, es zu beheben). Im Zuge der Umsetzung laufe ich offensichtlich in das Problem, die ‚Basis‘ Datenstrukturen von Grund auf neu zu implementieren. Eigentlich nicht nur verkettete Listen, sondern auch stapelt, Bäume, etc.

ich auf Listen in diesem Thema bin konzentriert, weil es in der Regel eine Struktur mich viel in dem Programm am Ende mit, entweder als ‚Haupt‘ Struktur oder als ‚Helfer‘ Struktur für andere Größere (zum Beispiel ein Hash Baum, die Konflikte durch die Verwendung einer verknüpften Liste löst).

Dies erfordert, dass die Liste speichert Elemente aus vielen verschiedenen Arten. ich hier als Prämisse gehe davon aus, dass ich nicht wollen, die Liste erneut Code für jede Art. Also, ich kann mit diesen Alternativen kommen:

eine Liste von void-Zeiger zu machen (ein bisschen unelegant, härter zu debuggen)
Machen nur eine Liste, sondern eine Vereinigung als ‚Elementtyp‘, die alle Elementtypen, die ich im Programm (einfacher zu debuggen verwenden; Abfälle Raum, wenn Elemente nicht alle gleich groß sind )
ein Präprozessormakro Mit dem Code für jede Art, die im Stil von SGLIB ‚Imitieren‘ C ++ 's zu regenerieren STL (kreative Lösung, keinen Platz verschwenden; Elemente haben den expliziten Typ sie tatsächlich sind, wenn sie zurückgebracht werden; jede Änderung in der Liste Code kann wirklich dramatisch sein )
Ihre Idee / Lösung

Um die Frage klar zu machen: die eine der oben ist am besten

PS: Da ich im Grunde in einem akademischen Kontext bin, bin ich auch in der Sicht von Menschen mit reinem C arbeiten da draußen in der Industrie sehr interessiert. Ich verstehe, dass die meist reine C-Programmierer in dem Embedded-Geräte-Bereich ist, wo ich nicht glaube, diese Art von Problem, das ich bin vor üblich. wenn jemand da draußen weiß jedoch, wie es gemacht wird ‚in der realen Welt‘, würde ich Ihre Meinung nach sehr interessiert sein.

Lösung

Ein void * ist ein bisschen wie ein Schmerz in einer Liste verknüpft, da Sie verwalten müssen, um es Zuordnung ist separat in die Liste selbst. Ein Ansatz, den ich in der Vergangenheit verwendet habe, ist, hat eine ‚variable Größe‘ Struktur wie:

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

Jetzt erkenne ich, dass nicht aussehen mit variabler Größe, aber lassen Sie uns eine Struktur zuordnen so:

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

Jetzt haben Sie einen Knoten, der für alle Absichten und Zwecke, wie folgt aussieht:

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

oder in graphischer Form (wo [n] bedeutet n Bytes):

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

Das heißt, vorausgesetzt, Sie wissen, wie die Nutzlast korrekt zu adressieren. Dies kann wie folgt:

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");

Die Gussleitung einfach wirft die Adresse des payload Zeichens (in dem tNode Typ) eine Adresse des tatsächlichen tPerson Nutzlast Typs sein.

Mit dieser Methode können Sie ein beliebiges Nutzdatentyp Sie in einem Knoten mögen tragen, auch unterschiedliche Payload-Typen in jedem Knoten , ohne den verschwendeten Speicherplatz einer Gewerkschaft. Diese Verschwendung kann mit dem folgenden zu sehen:

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

, wo 96 Bytes verschwendet wird jedes Mal, wenn Sie speichern einen Integer-Typen in der Liste (für eine 4-Byte-Ganzzahl).

Der Payload-Typ in der tNode ermöglicht es Ihnen, leicht zu erkennen, welche Art von Nutzlast dieser Knoten trägt, so können Sie Ihren Code entscheiden, wie es zu verarbeiten.

: Sie können etwas entlang der Linien von verwenden

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

oder (wahrscheinlich besser):

typedef enum {
    PAYLOAD_UNKNOWN,
    PAYLOAD_MANAGER,
    PAYLOAD_EMPLOYEE,
    PAYLOAD_CONTRACTOR
} tPayLoad;

Andere Tipps

My $ .002:

eine Liste von void-Zeiger zu machen (ein bisschen diselegant, härter zu debuggen)

Das ist nicht so eine schlechte Wahl, IMHO, wenn Sie in C schreiben Sie müssen API-Methoden hinzufügen könnten die Anwendung zu ermöglichen, eine print () Methode zur Vereinfachung der Fehlersuche zu liefern. Ähnliche Verfahren könnten aufgerufen werden, wenn (beispielsweise) Gegenstände zu erhalten hinzugefügt oder aus der Liste entfernt. (Für verkettete Listen, ist dies in der Regel nicht notwendig, aber für komplexere Datenstrukturen - Hash-Tabellen, zum Beispiel.) - es manchmal lebensrettend sein kann)

nur eine Liste zu machen, sondern eine Vereinigung als ‚Elementtyp‘, die alle Elementtypen, die ich in dem Programm verwenden (einfacher zu debuggen; Abfälle Raum, wenn Elemente nicht alle gleich groß sind)

Ich würde dies wie die Pest meiden. (Na ja, du hast fragen.) Mit einem manuell konfiguriert, Compiler-Abhängigkeit von der Datenstruktur zu den darin enthaltenen Typen ist die schlechteste aller Welten. Auch hier IMHO.

Mit einem Präprozessormakro den Code für jede Art, die im Stil von SGLIB (sglib.sourceforge.net), ‚Nachahmung‘ C ++ 's STL (kreative Lösung zu regenerieren; nicht Raum verschwenden; Elemente haben den expliziten Typen sie tatsächlich sind, wenn sie zurückgebracht werden;)

Intriguing Idee, aber da ich SGLIB weiß es nicht, ich kann nicht sagen, viel mehr als das.

Ihre Idee / Lösung

würde ich mit der ersten Wahl gehen.

Ich habe dies in der Vergangenheit getan haben, in unserem Code (die seit in C umgewandelt wurde ++), und zu der Zeit, entschied sich für die void * Ansatz. Ich habe gerade diese Flexibilität -. Wir waren fast immer einen Zeiger in der Liste zu speichern sowieso, und die Einfachheit der Lösung und Benutzerfreundlichkeit es überwog (für mich) die negativen Seiten zu den anderen Ansätzen

Davon abgesehen, gab es eine Zeit, wo es einige böse Fehler verursacht, die schwierig zu debuggen war, so ist es definitiv keine perfekte Lösung. Ich denke, es ist immer noch die, die ich nehmen würde, aber, wenn ich das jetzt wieder tun wurde.

ein Präprozessormakro Verwendung ist die beste Option. Die Linux-Kernel verkettete Liste ist eine ausgezeichnete eine eficient Implementierung eines zirkular-linked Liste in C. Ist sehr tragbar und einfach zu bedienen. Hier eine Standalone-Version von Linux-Kernel 2.6.29 list.h Kopf .

Die FreeBSD / OpenBSD sys / Warteschlange ist eine weitere gute Option für eine generische Makro basiert verknüpften Liste

Ich habe nicht C in Jahren codiert aber GLib eine große zu schaffen“, behauptet Satz von Utility-Funktionen für Strings und gemeinsame Datenstrukturen“, unter denen Listen verknüpft sind.

Auch wenn es verlockend, über die Lösung dieser Art von Problem zu denken, die Techniken einer anderen Sprache mit, sagen wir, Generika, es ist selten ein Gewinn in der Praxis. Es gibt wahrscheinlich einige Dosen-Lösungen, die es richtig die meiste Zeit bekommen (und sagen Sie in ihrer Dokumentation, wenn sie es falsch ist), dass die Verwendung von möglicherweise den Punkt der Zuweisung verpassen, also würde ich zweimal darüber nachdenken. Für eine sehr geringe Anzahl von Fällen kann es ohne weiteres möglich sein, Ihre eigene Rolle, aber für ein Projekt von einer vernünftigen Größe, es ist nicht wahrscheinlich die Debuggen Mühe wert sein.

Vielmehr Wenn in Sprache x Programmierung, sollten Sie die Idiome der Sprache x verwenden. Java nicht schreiben, wenn Sie Python verwenden. Nicht C schreiben, wenn Sie Schema verwenden. Nicht C ++ schreiben, wenn Sie C99 verwenden.

Ich, werde ich wahrscheinlich so etwas wie Pax Vorschlag am Ende mit, aber eigentlich eine Vereinigung von char [1] und void * und int, die gemeinsamen Fällen bequem zu machen (und ein enumed Typ Flag)

(ich würde wahrscheinlich auch eine Fibonacci Baum am Ende der Umsetzung, nur dazu führen, dass klingt ordentlich, und man kann nur RB-Bäume so oft implementieren, bevor es es ist Geschmack verliert, auch wenn es besser ist für die häufigsten Fälle würde es wird verwendet für).

Bearbeiten basierend auf Ihrem Kommentar, es sieht aus wie Sie einen ziemlich guten Fall für die Verwendung einer Dose Lösung haben. Wenn Ihr Lehrer es erlaubt, und die Syntax bietet es sich wohl fühlt, geben Sie ihm einen Whirl.

Dies ist ein gutes Problem. Es gibt zwei Lösungen Ich mag:

Dave Hanson C Schnittstellen und Realisierungen eine Liste von void * verwendet Zeiger, was für mich gut genug ist.
Für meine Schüler schrieb ich eine awk Skript typspezifischen Liste Funktionen zu erzeugen. Im Vergleich zu Präprozessormakros, erfordert es einen zusätzlichen Build-Schritt, aber der Betrieb des Systems ist wesentlich transparenter für Programmierer ohne viel Erfahrung. Und es hilft wirklich, den Fall für parametrischen Polymorphismus zu machen, die sie später in ihrem Lehrplan zu sehen.

Hier ist, was eine Reihe von Funktionen wie folgt aussieht:
```
int      lengthEL (Explist *l);
Exp*     nthEL    (Explist *l, unsigned n);
Explist *mkEL     (Exp *hd, Explist *tl);
```
Der awk-Skript ist ein 150-Linie Schrecken; sucht es C-Code für typedefs und erzeugt einen Satz von Listenfunktionen für jedes. Es ist sehr alt; Ich könnte wahrscheinlich besser jetzt tun: -)

Ich würde nicht einer Liste der Gewerkschaften die Tageszeit (oder Platz auf meiner Festplatte) geben. Es ist nicht sicher, und es ist nicht erweiterbar, so dass Sie auch nur void * verwenden können und mit ihm getan werden.

Eine Verbesserung gegenüber ihm eine Liste von void * zu machen wäre ihm eine Liste von Strukturen werden zu machen, die einen void * und einige Meta-Daten zu enthalten, was die void * Punkte, einschließlich der Art, Größe, etc.

Weitere Ideen:. Einbetten ein Perl oder Lisp-Interpreter

Oder gehen Sie auf halbem Wege: Verbindung mit der Perl-Bibliothek und es sich um eine Liste von Perl SVs oder etwas machen

Ich würde wahrscheinlich mit der Leere gehen * mich nähern, aber es kam mir der Gedanke, dass Sie Ihre Daten als XML speichern können. Dann kann die Liste nur noch ein char * für Daten (die Sie bei Bedarf analysieren würde für was auch immer Unter Elemente, die Sie benötigen) ....

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow