Verwirrung Liste C
-
verkettete liste ist doch gut weil man unbegrenzt neue elemente hinzufügen kann.
Jetzt kommt mein Professor mit folgendem :
verkettete Listen Implementierung mit FeldernBei Feldern ist doch vorher der Speicherplatz festgelegt. Was hat das
jetzt mit Liste zu tun?Danke
-
Jetzt kommt mein Professor mit folgendem :
verkettete Listen Implementierung mit Feldernkannst du vll auch ma mehr als 5 worte schreiben, um was es sich in deinem post dreht? OO
dein prof wird dir sicherlich nich nur 5 worte an den kopf gehauen haben und dann gesagt haben: ja, mach mal...
-
Es wurde mir gezeigt wie ich Felder verwenden kann um verkettete Listen zu implementieren.
-
Dieser Thread wurde von Moderator/in volkard aus dem Forum C++ in das Forum ANSI C verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
blurry33 schrieb:
Bei Feldern ist doch vorher der Speicherplatz festgelegt. Was hat das jetzt mit Liste zu tun?
Die algorithmische Spezifikation einer verketteten Liste schert sich nicht darum, ob Speicherplatz begrenzt ist oder nicht. Die Grenzen werden durch die jeweilige Implementierung festgelegt.
Bei einer Implementierung mit Zeigern bist du ebenfalls begrenzt, sei es durch die Hardware, das Betriebssystem, oder was auch immer.
Übrigens kannst du dir auch bei einer Implementierung mit Arrays die Mühe machen bei Erreichen der Arraygrenzen ein größeres Array anzulegen und dann alles umzukopieren, ähnlich wie es bei vector geschieht.
Die Implementierung mit Arrays hat neben dem Nachteil der mangelnden Flexibilität was Speicherplatz angeht aber auch entscheidende Vorteile. Bin sicher du kennst sie bereits, denn sie sind ja schließlich offensichtlich.
-
Verkettete Listen mit Arrays ist grundsätzlich möglich, und manchmal notwenidig (wenn man z.b. keinen Speichermanagment hat).
Die Idee ist: der Speicher wird durch ein Feld einer bestimmten Größen gegeben.
struct intlist { int val; struct intlist *next; struct intlist *prev; }; #define MAX_ELEMENTS 1024 struct intlist __memory__[MAX_ELEMENTS]; struct intlist *memory_pool; struct intlist *list;memory_poolzeigt auf das erste Element, welches nicht belegt ist. Von da kann man den nächsten freien Platz bekommen.listist die Liste selber.Die Idee ist, dass man
__memory__so initialisiert, dass__memory[i]->next == __memory[i+1]__undmemory_pool == __memory__gilt.int i; for(i = 0; i < MAX_ELEMENTS - 1; ++i) __memory__[i].next = __memory__[i+1]; __memory__[i].next = NULL; memory_pool = __memory__; list = NULL;Dann kann man eine mallo/freec-ähnliche Fkt schreiben:
struct intlist *get_next_free_node(struct intlist **mem) { struct intlist *ret; if(mem == NULL || *mem == NULL) /* Fehler */ return NULL; ret = *mem; *mem = (*mem)->next; return ret; } void *free_node(struct intlist **mem, struct intlist *node) { struct intlist *ret; if(mem == NULL || node == NULL) /* Fehler */ return; if(*mem == NULL) { node->next = NULL; *mem = node; return; } node->next = *mem; *mem = node; }Dann kann man eine append/delete-Fkt so schreiben:
int append_to_list(struct intlist **list, struct **mem, int val) { struct intlist *node; if(list == NULL || mem == NULL) return 0; node = get_next_free_node(mem); if(node == NULL) return 0; node->val = val; node->next = NULL; if(*list == NULL) /* empty list */ { node->prev = node; *list = node; return 1; } node->prev = (*list)->prev; node->prev->next = node; node->next->prev = node; (*list)->prev = node; return 1; } int delete_from_list(struct intlist **list, struct **mem, int pos) { int i; struct intlist *nav; if(list == NULL || mem == NULL) return 0; nav = *list; for(i = 0; i <= pos; ++i) { if(nav == NULL) /* invalid 'pos' */ return 0; nav = nav->next; } if(nav->next == NULL) /* end of list */ { nav->prev->next = NULL; (*list)->prev = nav->prev; } if(nav == *list) /* head of list */ { if(nav->next) nav->next->prev = nav->prev; *list = nav->next; } else { nav->next->prev = nav->prev; nav->prev->next = nav->next; } free_node(mem, nav); return 1; }Nach der Initialisierung kann man dann:
append_to_list(&list, &memory_pool, 4); append_to_list(&list, &memory_pool, 3); append_to_list(&list, &memory_pool, -4); append_to_list(&list, &memory_pool, 14); append_to_list(&list, &memory_pool, 65); delete_from_list(&list, &memory_pool, 2); /* Element mit -4 löschen */ ...
-
supertux schrieb:
Verkettete Listen mit Arrays ist grundsätzlich möglich, und manchmal notwenidig (wenn man z.b. keinen Speichermanagment hat).
Die Idee ist: der Speicher wird durch ein Feld einer bestimmten Größen gegeben.
//...Hab deinen Quelltext nur überflogen, aber was du da vorzeigst hat mit der Implementierung von verketteten Listen über Arrays wenig bis gar nichts zu tun.
Du verwaltest lediglich den Speicher selbst. Das ist damit nicht gemeint.
-
Mitleid schrieb:
supertux schrieb:
Verkettete Listen mit Arrays ist grundsätzlich möglich, und manchmal notwenidig (wenn man z.b. keinen Speichermanagment hat).
Die Idee ist: der Speicher wird durch ein Feld einer bestimmten Größen gegeben.
//...Hab deinen Quelltext nur überflogen, aber was du da vorzeigst hat mit der Implementierung von verketteten Listen über Arrays wenig bis gar nichts zu tun.
Du verwaltest lediglich den Speicher selbst. Das ist damit nicht gemeint.
dass ich den Speicher selber verwalte, ist mir klar (hab auch gesagt). Jetzt verstehe ich aber nicht, was genau "verketteten Listen über Arrays" zu verstehen ist.
-
supertux schrieb:
... Jetzt verstehe ich aber nicht, was genau "verketteten Listen über Arrays" zu verstehen ist.
Der Threadstarter spricht ja von Implementierung verketteter Listen mittels Feldern (also Arrays).
Diese Art der Implementierung geht etwas über das hinaus, was du aufgeschrieben hast.
Man verwaltet den Speicher (das Array) selbst. Das machst du ja auch. Es kommt aber noch hinzu, dass die Verkettung nicht über Zeiger, sondern über den Array-Index realisiert wird. Und das ist in diesem Fall das Entscheidende.
-
Mitleid schrieb:
Man verwaltet den Speicher (das Array) selbst. Das machst du ja auch. Es kommt aber noch hinzu, dass die Verkettung nicht über Zeiger, sondern über den Array-Index realisiert wird. Und das ist in diesem Fall das Entscheidende.
ach so. Das finde ich aber nicht so optimal, wenn man z.b. ein Element in der Mitte löscht, dann müsste man ein großer Block bewegen.
-
supertux schrieb:
ach so. Das finde ich aber nicht so optimal, wenn man z.b. ein Element in der Mitte löscht, dann müsste man ein großer Block bewegen.
Das muss man ja nicht.
Ich schreib mal ein Beispiel hin, damit klar wird was gemeint ist. Obwohl das schon irgendwie gut "googelbare" Grundlagen sind *hüstel* *hüstel*.
Eine verkettete Liste
35 -> 99 -> 7 -> 3
könnte dann eingebettet in Arrays so aussehen:
Ind. A1 A2 ------------ 0 - - 1 35 4 2 - - 3 - - 4 99 5 5 7 7 6 - - 7 3 0 8 - - 9 - -Wobei es sich hier um zwei Arrays der Größe 10 handelt. Ganz links steht (nur als Hilfe) der Index, in der Mitte das erste Array mit den Schlüsseln und rechts das zweite Array in welchem der Index des nächsten Schlüssels festgehalten ist. Steht als nächste Position eine 0 könnte das das Ende der Liste markieren.
Löschen wäre also nicht besonders teuer, im Gegenteil.
Vorteil der Implementierung (neben dem angesprochenen Geschwindigkeitsgewinn, weil man nicht dynamisch irgendwlechen Speicher vom BS anfordert) ist, dass man die beiden Arrays genau so auf Festplatte o.Ä. speichern kann und die Struktur gültig bleibt, was bei der Implementierung über Zeiger ja nicht der Fall ist.
Man kann in solche Arrays übrigens auch Problemlos mehrere Listen einbetten:
Liste 1: 35 -> 99 -> 7 -> 3
Liste 2: 103 -> 1 -> 8Ind. A1 A2 ------------ 0 - - 1 35 4 2 - - 3 103 6 4 99 5 5 7 7 6 1 9 7 3 0 8 - - 9 8 0Erste Liste beginnt bei A1[1], die zweite bei A1[3].