4. verkettete Liste

verkettete Liste

  • S

    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.

    0
  • I

    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.

    0
  • S

    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?

    0
  • C

    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.

    0
  • S

    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

    0
  • C

    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)

    0

  • 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.

    0
  • S

    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.

    0

  • 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.

    0
  • ?

    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.

    0
  • S

    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

    0
  • C

    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.

    0
Anmelden zum Antworten