verkettete Liste

[Schreiber2]

Hallo,

ich möchte gerne eine Struktur definieren, welches als variable eine verkettete Liste besitzt.(Ich hoffe das ist soweit überhaupt möglich).

Nun verstehe ich das Konzept einer Liste noch nicht so richtig. Ich glaube, dass eine Liste etwas ähnliches ist wie ein Array. Nur dass es nicht nur die Daten speichert, sonder zu jeder datei auch einen Pointer.

Aber wie erstelle ich so etwas und wohin muss der pointer zeigen??

Danke

[icarus2]

Also auf Wikipedia werden linked lists erklärt.

Aber ich versueche es mal möglichst einfach und kurz zu erklären.

In einer verketteten List hast du verschiedene Knoten. Ein Knoten enthält einen Wert (z.B. einen Intergerwert wie 10) und einen Zeiger auf das nächste Element in der Liste.

Du hast z.B. 3 Knoten mit Werten 1, 4, 5.
Dann definierst du den Anfangsknoten mit Wert 1. Dieser Anfangsknoten zeigt auf den Knoten mit Wert 4. Dieser Wiederum auf den Knoten mit Wert 5. Das ganze sieht dann etwa so aus:
1 --> 4 --> 5

So eine Liste ist also Linear.

Zur Implementierung:
Du kannst dir z.B. eine structure definiere, die in etwa so aussieht:

struct Knoten
{
	Knoten* naechster_knoten; // Zeigt auf den nächsten Knoten in der Liste (null, wenn es kein weiteres Element mehr gibt)
	int value; // Der Wert, der in diesem Knoten gespeichert ist
}

Wenn du nun eine verkettete List in deiner Datenstruktur haben möchtest, dann brauchst du nur das Anfangselement, also sowas wie

struct DeineDatenstruktur
{
	Knoten* anfangs_knoten; // Der Knoten, der auf das erste Element in der Liste zeigt
	// Der Rest deiner Datenstruktur
}

Die restlichen Knoten brauchst du nicht explizit zu speichern in deiner Datenstruktur. Du erreichst alle anderen Knoten, in dem du (mehrfach) auf naechstes_element zugreifst.

Einfügen und entfernen kannst du nun ganz leicht, indem du die Zeiger umhängst. Ich hoffe, dass die Erklärung einigermassen verständlich ist.

[Schreiber2]

Hallo,

heisst das jetzt erstmal, dass es diese Datenstruktur nicht in C gibt, und ich diese selbst definieren muss?

[icarus2]

Schreiber2 schrieb:

Hallo,

heisst das jetzt erstmal, dass es diese Datenstruktur nicht in C gibt, und ich diese selbst definieren muss?

Ich kann eigentlich kein C, sondern nur C++. Aber soweit ich weiss gibt es keine gereischen Datenstrukturen in C. Da muss man meistens die Datenstruktur selber implementieren.
Mögliche Implementierungen findest du sicher viele über Google.

[SeppJ]

Schreiber2 schrieb:

Hallo,

heisst das jetzt erstmal, dass es diese Datenstruktur nicht in C gibt, und ich diese selbst definieren muss?

Ja. Wobei du natürlich nicht der erste wärest, der das täte. Falls du es nicht selber implementieren willst, kannst du daher auch fertiges finden.

[Schreiber2]

Ok danke dir.
Aber ich denke, dass es so gehen müsste, wie du oben geschrieben hast.

Aber dennoch habe ich noch eine Frage:

in deiner zweiten Ausführung schreibst du:

struct DeineDatenstruktur
{
    Knoten* anfangs_knoten; // Der Knoten, der auf das erste Element in der Liste zeigt
    // Der Rest deiner Datenstruktur
}

Ist das tatsächlich ein Knoten, welcher auf das erste Element der liste zeigt?
Das ist doch nur ein Pointer mit dem Namen anfangs_knoten, welcher auf einen Knoten zeigen soll??

Also ich bin noch sehr neu in C und habe nicht so viel erfahrung.

Grüsse

[icarus2]

Du kannst mehrere Zeiger auf Orte in deiner Liste haben. Zum Beispiel noch einen zweiten Zeiger auf das letzte Element in der Liste, damit du schnell ans Ende der Liste einfügen kannst (sonst musst du dafür die ganze Liste durchlaufen).

Du musst aber IMMER einen Zeiger auf das erste Element behalten. Der Grund dafür ist, dass du in der Liste nur von links nach rechts wandern kannst, aber nicht umgekehrt. Das sieht man sofort, wenn man die Richtung der Pfeile betrachtet.

Falls du von links nach rechts und von rechts nach links wandern können möchtest, dann kannst du das mit einer doppelt verketteten Liste erreichen.

[Schreiber2]

Ok, ich glaube ich verstehe in etwa was du meinst:)

Nun soll ich eine Struktur definieren, welche bel. viele Zeichen in einer Liste speichern kann und davon bel. viele.

Nun verstehe ich nicht so ganz, wie das gemeint ist.

könnte unsere Struktur dann etwa so aussehen:

struct DeineDatenstruktur
{
    Knoten* anfangs_knoten; 

int AnzahlDerListen;
int LängeDerListen;

}

Aber das scheint mir nicht richtig zu sein. Da aus dieser Struktur doch später einzelne "objekte" entstehen sollen. Diese brauchen ja keine AnzahlDerListen zu besitzen!
Auf der anderen Seite soll die Struktur bel. viele solcher Listen speichern. Ich kann ja schlecht bel. viele "Knoten", d.h. Listen deklarieren.

Dürfte man in solch eine Struktur z.B. eine schleife einbauen? Wahrscheinlich auch nicht!

Wie löst man dieses Problem denn?Ich weis echt nicht mehr weiter.

[icarus2]

Wie siehts mit deinem Kenntnissen aus? Weisst du wie man mit Pointern umgeht und weisst du wie man Speicher alloziert usw? Das sind nämlich die Grundlagen für eine verkettete Liste.

Schau dir mal das hier an: http://codingfreak.blogspot.com/2009/08/implementation-of-singly-linked-list-in.html
Ich glaube das erklärt ganz gut wie man eine verkettete Liste implementieren kann (habs jetzt selber nicht duchgelsen aber sieht auf den ersten Blick nicht schlecht aus). Falls du etwas nicht verstehst kannst du hier natürlich nachfragen. Dann können wir konkret etwas erklären.

[Schreiber2]

wow vielen Dank für deinen Link. Das hilft mir sehr.

Nun zu meinem ersten Problem.
Ich habe in etwa folgendes gemacht:

#include<stdio.h>

struct Knoten{

char Zeichen;
struct Knoten *nächster Knoten;
};

struct Knoten *head;
head=NULL;

Dies soll nun erstmal meine Liste sein. Daraufhin wollte ich den head pointer auf NULL setzen, wie ihr oben seht. Genau an dieser Stelle meldet sich der Compiler mit einem Fehler.

Er gibt die Fehlermeldung: 'head does not name a type'

Zwar ist head ja kein type, aber es soll doch nur der Pointer auf die Konstante NULL zeigen.??
Auf der seite steht es doch auch so.

Seht ihr den Fehler vielleicht?

[CStoll]

Ja, der Fehler ist, daß du keine Anweisungen global in den Raum werfen darfst - die sind nur innerhalb von Funktionsdefinitionen erlaubt. Auf globaler Ebene darfst du nur Deklarationen und Definitionen stehen haben.

[Schreiber2]

Super danke!! Also habe ich nun das ganze in die Main Funktion gesetzt und es funktioniert:)

Nun habe ich noch eine konkrete Frage zu einer Notation:

in dem Link steht so etwas wie:

for(i=1;i<loc;i++)  
           {  
               prev_ptr=cur_ptr;     
               cur_ptr=cur_ptr->Next;  
           }  

           temp=(struct Node *)malloc(sizeof(struct Node));

Also ich kenne den *-Operator. Aber nicht in diesem Kontext. Was bedeutet es, wenn ich ein * nach einer Struktur notiere, also genauer:
temp=(struct Node *)...
Hat das was mit der malloc funktion zu tun? habe im internet etwas ähnliches gesehen mit malloc. Aber leider ohne erklärung.

Viele Grüsse

[CStoll]

diese Konstruktion nennt sich "Typecast" oder "Typumwandlung" - das besagt, daß du den Rückgabewert der malloc()-Funktion in einen struct Node* (Zeiger auf einen Knoten) umwandelst.
(malloc() liefert einen void* (Zeiger auf irgendwas) zurück, ein C-Compiler könnte den zwar afaik implizit umwandeln, aber es ist immer besser dazuzusagen, was du eigentlich beabsichtigst)

[Wutz]

Das ist C++ Aberglaube.
Der Code wird nicht lesbarer dadurch, dass man Typecasts verwendet.
Ein Typecast ist für den Compiler bestimmt, damit der klarkommt. Und für meinen Programmcodeerstellung ist der Compiler ein Hilfsmittel, dass mich unterstützen soll und nicht ich das Hilfsmittel.
Ein C Compiler benötigt keinen Cast für void*, dazu gibt es ja void* überhaupt.
Ein C++ Compiler benötigt diesen Cast, aber auch nur, weil C++ Leute malloc verwenden anstatt des new.

[Schreiber2]

Klasse! Jede eurer Antworten hilft mir so sehr weiter!!
ich bin noch sehr neu in der Materie und ihr macht das wirklich sehr verständlich.

Nun habe ich eine etwas allgemeinere Frage:

Meine Aufgabenstellung lautet in etwa:
-Implementieren Sie eine Datenstruktur, welche bel. viele und bel. lange Zeichenketten speichert.
-Verwenden sie dazu als generische Datenstruktur eine Liste.
Zusätzlich
-implementieren sie danach diese operationen....usw.

Ich verstehe nicht so genau, was man da genau erwartet.
Heißt das, dass meine Quelldatei nur aus einer struct komponente bestehen soll?
Also z.B. obige Liste nochmal einbetten in eine Struktur usw.
Oder soll ich ein richtiges ausführbares Programm schreiben, d.h. mit main Funktion usw... for schleifen etc.

[Wutz]

Du sollst eine Datenstruktur entwerfen, die sowohl (Nutz)Daten speichern kann und gleichzeitig auch als Element in einer Liste dienen kann.
Genaugenommen ist dies nicht unbedingt eine verkettete Liste, der Begriff Liste ist nicht eindeutig definiert und braucht nicht unbedingt verkettet sein (einen Verweis auf Nachfolger und/oder Vorgänger enthalten).
Solche Aufgabenstellungen sind sehr beliebt bei Lehrveranstaltungen, im praktischen Umgang meist ineffizient.
Die Aktionen, die du dann darauf anwenden sollst, sollten dann einen (wie auch immer gearteten) Verweis auf diese "Strukturliste" bekommen, d.h. die Funktionen erhalten einen entsprechenden Zeiger.

Strenggenommen geht sowas auch ohne Verkettung, also z.B.

typedef struct {
char **elems;
size_t z;
} Liste;

void addiereNeuesElement(Liste *l,char *s)
{
  l->elems=realloc(l->elems,++l->z*sizeof*l->elems);
  strcpy(l->elems[l->z-1]=malloc(strlen(s)+1),s);
}

void ausgabe(Liste *l)
{
  size_t i=l->z;
  while( i-- )
    puts(l->elems[i]);
}

void aufraeumen(Liste *l)
{
  while( l->z-- )
    free( l->elems[l->z] );
  free( l->elems );
}

int main()
{
  Liste liste={0};
  addiereNeuesElement(&liste,"eins");
  addiereNeuesElement(&liste,"zwei");
  addiereNeuesElement(&liste,"drei");
  ausgabe(&liste);
  aufraeumen(&liste);
  return 0;
}

Du kannst ja mal versuchen (und dann mit o.g. schnell hingeworfener nichtverketteter Variante vergleichen), wie man eine Sortierung (nachträglich) für deine Strukturliste hinbekommt.

[DirkB]

Schreiber2 schrieb:

Oder soll ich ein richtiges ausführbares Programm schreiben, d.h. mit main Funktion usw... for schleifen etc.

Das wirst du zum testen sowieso machen müssen.

[Schreiber2]

Hallo,

Zunächst nochmal eine kleine Nachfrage bezüglich der Definition von "Datenstruktur". Ich glaube ich habe das immer noch nicht so ganz verstanden.
Laut Wikipedia ist eine Datenstruktur ein Objekt zur Speicherung von Daten.
Aber im weiteren macht Wikipedia eine weitergehende Beschreibung von Datenstruktur:
nämlich heißt es dort, dass auch die Verwaltung und Verknüpfung von Daten entscheidende Voraussetzung einer jeden Datenstruktur ist.
Das muss meiner Kenntnis nach die main Methode und die darin verwendeten Funktionen miteinschließen.

Das würde insgesamt bedeuten, dass das Gesamtpaket erst die Datenstruktur ausmacht, d.h. mein ganzes Programm.
Ist also ein Programm, welches Daten abspeichert, verwaltet usw. = Datenstruktur?

Grüsse

[CStoll]

zum ersten Teil: Zur Datenstruktur gehören die Objekte/Datentypen und die Funktionen, die mit diesen Objekten direkt arbeiten müssen - bei einer Liste z.B. die struct's Knoten und Liste und Funktionen wie insert_to_list() oder remove_from_list(), die letztlich dafür sorgen, daß die Knoten korrekt zusammengehängt werden.
Die main() und andere "externe" Funktionen, die die Liste nur als geschlossenes Gebilde betrachten und an die Verwaltungsfunktonen übergeben, gehören nicht zur Datenstruktur - das sind die Anwender, die damit umgehen wollen.

Zum zweiten: Die vorletzte Zeile deines Codes ist - wie der Compiler dir auch mitteilen wollte - syntaktischer Unsinn. Die eigentliche Verwaltung der Listen-Elemente spielt sich komplett in den insert()-, remove()- etc Funktionen ab, dein Hauptprogrmm benötigt nur ein struct Liste dieListe; , die an diese Funktionen weitergereicht wird, um die gestellte Aufgrabe zu lösen.