Heim  >  Artikel  >  Ist eine linear verknüpfte Liste eine verknüpfte Speicherstruktur einer linearen Liste?

Ist eine linear verknüpfte Liste eine verknüpfte Speicherstruktur einer linearen Liste?

(*-*)浩
(*-*)浩Original
2019-10-24 09:50:3414159Durchsuche

Entsprechend der Komplexität der Beziehung zwischen den einzelnen Datenelementen in der Datenstruktur werden Datenstrukturen im Allgemeinen in zwei Haupttypen unterteilt: lineare Strukturen und nichtlineare Strukturen.

Ist eine linear verknüpfte Liste eine verknüpfte Speicherstruktur einer linearen Liste?

Eine lineare verknüpfte Liste ähnelt, wie der Name schon sagt, einer Kettenliste Der Unterschied besteht darin, dass eine lineare Sequenztabelle einen kontinuierlichen Bereich im Speicher öffnen muss, sodass der Status der im Speicher gespeicherten Daten kontinuierlich ist, während die Speicherung der linear verknüpften Liste im Speicher zufällig ist. und die Verbindung zwischen den Daten basiert auf einem Zeiger. (Empfohlenes Lernen: Web-Frontend-Video-Tutorial)

Wenn eine nicht leere Datenstruktur die folgenden zwei Bedingungen erfüllt:

① Hat und hat nur ein Wurzelknotenpunkt;

②Jeder Knoten hat höchstens einen Antezedens und höchstens eine Konsequenz. Die Datenstruktur wird als lineare Struktur oder auch als lineare Tabelle bezeichnet. Daher sind lineare Listen, Stapel und Warteschlangen sowie lineare verknüpfte Listen alle lineare Strukturen, während Binärbäume nichtlineare Strukturen sind.

Eine lineare Tabelle mit einer verknüpften Speicherstruktur. Sie verwendet eine Reihe von Speichereinheiten mit beliebigen Adressen, um Datenelemente in der linearen Tabelle zu speichern. Logisch benachbarte Elemente müssen nicht physisch benachbart sein und es kann nicht zufällig darauf zugegriffen werden. . Im Allgemeinen durch Knoten beschrieben: Knoten (stellt Datenelemente dar) = Datendomäne (Bild von Datenelementen) + Zeigerdomäne (gibt den Speicherort nachfolgender Elemente an)

In der Kettenspeicherstruktur wird die Datenstruktur gespeichert Der Speicherplatz ist möglicherweise diskontinuierlich und die Speicherreihenfolge jedes Datenknotens stimmt möglicherweise nicht mit der logischen Beziehung zwischen Datenelementen überein. Die logische Beziehung zwischen Datenelementen wird durch das Zeigerfeld bestimmt. Mit der Kettenspeichermethode können sowohl lineare als auch nichtlineare Strukturen dargestellt werden.

Im Allgemeinen sind in der verknüpften Speicherstruktur einer linearen Liste die Speichersymbole jedes Datenknotens diskontinuierlich, und die Positionsbeziehung und die logische Beziehung jedes Knotens im Speicherraum sind ebenfalls inkonsistent. Bei einer linear verknüpften Liste können Sie vom Kopfzeiger aus beginnen und entlang der Zeiger jedes Knotens zu allen Knoten in der verknüpften Liste scannen.

Erstellen Sie eine lineare verknüpfte Liste. Dabei handelt es sich um einen Prozess, bei dem Verknüpfungspunkte dynamisch generiert und diese wiederum mit der verknüpften Liste verknüpft werden. Der Zeiger des ersten Verknüpfungspunkts der linear verknüpften Liste sei eine Liste.

Wenn der erste Verknüpfungspunkt generiert wird, ist die verknüpfte Liste leer. Senden Sie den Verknüpfungspunkt einfach direkt an die Liste. Jedes Mal, wenn ein Datenelement abgerufen wird, wird ein Verknüpfungspunkt für das Datenelement generiert. Während die Dateninformationen des abgerufenen Datenelements an das Datenfeld des neuen Knotens gesendet werden, wird das Zeigerfeld des neuen Knotens auf NULL gesetzt. Anschließend wird das Zeigerfeld des neuen Knotens auf NULL gesetzt. Der Knoten wird am Ende der verknüpften Liste eingefügt.

Im folgenden Algorithmus werden Zeichenfolgen Zeile für Zeile aus einer Datei namens data.txt als Datenelemente einer linear verknüpften Liste gelesen. Der Algorithmus lautet wie folgt:

LinkList creatList() {
    LinkList r, p, list = NULL;
    char data[ 100 ];
 
    FILE *f = fopen( "data.txt", "rb" );
    while( fgets( data, 100, f ) )
    {
        p = ( LinkList )malloc( sizeof( LNode ) );
        if( p != NULL ){
            strcpy( p->data, data );
            p->link = NULL;
 
            if( list == NULL )
                list = p;
            else
                r->link = p;
            r = p;
        }
    }
    fclose( f );
 
    return list;
}

Das obige ist der detaillierte Inhalt vonIst eine linear verknüpfte Liste eine verknüpfte Speicherstruktur einer linearen Liste?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Vorheriger Artikel:Was ist BDO?Nächster Artikel:Was ist BDO?