Lineares Messgerät ist eine lineare Struktur, eine begrenzte Sequenz mit dem gleichen Datenelement vom Typ n (n ≥ 0).
1. Array
Das Array hat obere und untere Grenzen, und die Elemente des Arrays sind in den oberen und unteren Grenzen kontinuierlich.
Das schematische Diagramm des Arrays von 10,20,30, 40, 50 50 lautet wie folgt:
Merkmale von Array : Die Daten sind kontinuierlich.
Das etwas kompliziertere Array ist mehrdimensionales Array und dynamisches Array. Für die C -Sprache wird das mehrdimensionale Array auch durch ein dimensionales Array realisiert. Für das dynamische Array ist es ein Array der Kapazität der Indexgruppe, die dynamisch wachsen kann. Vektor;
Zweitens ist eine verlinkte Liste <BR /> eine verlinkte Liste (einzelne verknüpfte Liste) ist eine Art verknüpfter Liste.
Das schematische Diagramm einer einzigen verknüpften Liste lautet wie folgt:
Der Kopf des Kopfes ist leer, der Nachfolgerknoten des Kopfes ist "Knoten 10" (Knoten der Daten 10) und der Nachfolgerknoten von "Knoten 10" "Knoten 20" (Daten mit Daten 10). ..
Einzelkette Löschenknoten
Löschen Sie "Knoten 30"
Vor dem Löschen: Der Nachfolgeknoten von "Knoten 20" ist "Knoten 30" und der Nachfolgeknoten von "Knoten 30" "Knoten 40".
Nach dem Löschen: Der Nachfolgerknoten von "Knoten 20" ist "Knoten 40".
Einzeln verlinkte Liste hinzugefügte Knoten hinzugefügt
Fügen Sie "Knoten 15" zwischen "Knoten 10" und "Knoten 20" hinzu
Vor dem Hinzufügen: Der Nachfolgeknoten von "Knoten 10" ist "Knoten 20".
Nach dem Hinzufügen: Der Nachfolgeknoten von "Knoten 10" lautet "Knoten 15" und der Nachfolgeknoten von "Knoten 15" "Knoten 20".
Das Merkmal einer einzelnen verknüpften Liste ist, dass die Link -Richtung des Knotens ein Weg ist.
Drittens zwei mit der Leuchten gelinkte Liste
Die zwei -Way -Linked List (Dual Linked List) ist eine Art verknüpfter Liste. Wie eine einzige verknüpfte Liste besteht auch die Doppelkettenliste aus Knoten. Ausgehend von jedem Knoten in der beiden verknüpften Liste können Sie problemlos auf die vorderen Knoten und nachfolgenden Knoten zugreifen. Im Allgemeinen konstruieren wir alle eine zweiwegen rund verknüpfte Liste.
Das schematische Diagramm der doppelt verknüpften Liste lautet wie folgt:
Der Header ist leer, der Nachfolgerknoten des Kopfes ist "Knoten 10" (Knoten der Daten 10); Nachfolger Der Knoten ist "Knoten 10"; .
Doppelkettenwache löschen Knoten
Löschen Sie "Knoten 30"
Vor dem Löschen: Der Nachfolgerknoten von "Knoten 20" ist "Knoten 30" und der Vornode von "Knoten 30" "Knoten 20". Der Nachfolgerknoten von "Knoten 30" ist "Knoten 40" und der Vornode von "Knoten 40" "Knoten 30".
Nach dem Löschen: Der Nachfolgeknoten von "Knoten 20" ist "Knoten 40" und der Vornode von "Knoten 40" "Knoten 20".
Doppelverknüpfungsliste Hinzufügen von Knoten Hinzufügen von Knoten
Fügen Sie "Knoten 15" zwischen "Knoten 10" und "Knoten 20" hinzu
Vor dem Hinzufügen: Der Nachfolgeknoten von "Knoten 10" ist "Knoten 20" und der vorherige Knoten von "Knoten 20" "Knoten 10".
Nach dem Hinzufügen: Der Nachfolgeknoten von "Knoten 10" lautet "Knoten 15" und der Vornode von "Knoten 15" ist "Knoten 10". Der Nachfolgerknoten von "Knoten 15" ist "Knoten 20" und der vorherige Knoten von "Knoten 20" "Knoten 15".
Die Implementierung der Doppelkettenliste wird nachstehend eingeführt, und die drei Implementierungen von C/C ++/Java werden jeweils eingeführt.
1. C Implementieren Sie eine doppelt verknüpfte Liste
Implementieren Sie den Code Two -Way -verknüpften Listendatei (double_link.h)
#Ifndef_double_link_h#define_double_link_h // Erstellen Sie eine "Zwei -Way -Linked -Liste". Erfolg, zurück in den Kopf; Erfolg, ansonsten kehren Sie zu -1extern in Destroy_dlink () zurück; Kehren Sie für Leere zurück; extern int dlink_is_eMpty (); Erfolg, kehren Sie zum Knotenzeiger zurück. Extern void* dlink_get (int index); Erfolg, kehren Sie zum Knotenzeiger zurück. extern void* dlink_get_first (); Erfolg, kehren Sie zum Knotenzeiger zurück. extern void* dlink_get_last (); Erfolg, ansonsten return -1. extern int dlink_insert (int index, void *pval); Erfolg, ansonsten return -1. extern int dlink_insert_first (void *pval); Erfolg, ansonsten return -1. extern int dlink_append_last (void *pval); Erfolg, ansonsten kehren Sie zu -1extern int dlink_delete zurück (int Index). Erfolg, ansonsten kehren Sie zu -1extern zurück in dlink_delete_first (); Erfolg, ansonsten zurück zu -1extern int dlink_delete_last ();#endif
Double_link.c in einer mit zwei Wegen verknüpften Liste
#include <stdio.h> #include <malloc.h>/*** c Lingle's Zwei -Way -verknüpfte Liste können beliebige Daten speichern. ** @Author SkyWang* @Date 2013/11/07*/// 3 -way -Listenknoten typedef struct_node {stroct tag_node*prev; Beachten Sie, dass der Wert des Kopfes den Elementwert nicht speichert! Überschneidung Überschneidung Statischer Knoten *phead = null; Statische Int Count = 0; // Erstellen Sie einen neuen "Knoten". Erfolg, kehren Sie zum Knotenzeiger zurück. Statischer Knoten *create_node (void *pval) {node *pnode = null; "); Null return;} // Der Standard, der erste Knoten und der letztere Knoten von Pnode Punkt auf seinen eigenen pnode-> prew = pnode-> next = pnode; // Der Wert des Knotens ist pvalpnode-> p = PVAL; / Erstellen Sie eine "Zwei -Wege -Liste". Erfolg, ansonsten return -1. int create_dlink () {// das Header PHED = CREATE_NODE (null); Return count == 0;} // kehre zu der "Zwei -Way -Linked List" zurück. node (node (int index) {ifx <0 || index> = count) {printf ("%S fehlgeschlagen! Index aus gebunden!/n", __func __); if (index <= (count/2)) {int i = 0; Suche int j = 0; Knoten "statischer Knoten * g et_first_node () () return get_node (0);} // den statischen Knoten" Letzter Knoten "abrufen in der wegen verlinkten Liste ". Erfolg, Return Node Value; void * dlink_get (int index) {node * pindex = get_node (index); 1 个元素的值 ”void* dlink_get_first () {return dlink_get (0);} // 获取 双向链表中最后 双向链表中最后 1 个元素的值” void* dlink_get_last () {return dlink_get (count- 1);} // Fügen Sie "PVAL" in die Indexposition ein. Erfolg, ansonsten return -1. int dlink_insert (int index, void * pval) {// den Header if (index == 0) einfügen dlink_insert_first (pvalt (pval); // den Knotenknoten abrufen, der der zu eingefügten Position entspricht; if! pindex) return -1; // 创建 "节点" Knoten *pnode = create_node (pval); if (! pnode) return -1; pnode-> prep = pindex-> pre; pnode-> next = pindex; pindex; -> Prev-> Next = Pnode; {Node *PNOD E = CREATE_NODE (PVAL); ++; ; Weg verlinkte Liste ". Erfolg, ansonsten return -1. int dlink_delete (int index) {node *pindex = get_node (index); > Weiter-> prev = pindex-> pre; pindex-> pre-> next = pindex-> next; free (pindex); count-; return 0;} // 删除第一个节点 int dlink_delete_first () {return return dlink_delete (0);} // einen Knoten int dlink_delete_last () {return dlink_delete (count-);} // ressit "Zwei-Way-Linked-Liste". Erfolg, ansonsten return -1. int destroy_dlink () {if (! phad) {printf ("%s fehlgeschlagen! Dlink ist null!/n", __func __); ;Zwei -Way -verknüpfter Listen -Testprogramm (dlink_test.c)
#Include <stdio.h> #include "double_link.h"/*** c Sprache zum Implementieren eines zwei -Way -verknüpften Listen -Testprogramms. ** (01) int_test ()* Demonstrieren "int data" in einer zweiwayverlinkten Liste. * (02) string_teest ()* Demonstrieren "Strine -Daten" in einer mit zwei Wegen verknüpften Liste. * (03) Object_TEEST ()* Demonstrieren Sie das "Objekt" in einer mit zwei Wegen verlinkten Liste. ** @Author Skywang* @date 2013/11/07* /// Zwei-Way-Listen-Operation int data void int_teest () {int iarr [4] = {10, 20, 30, 40}; n -----%s ------ ", __func __); create_dlink (); // Erstellen Sie eine mit zwei Wege verlinkte Liste dlink_insert (0, & iiarr [0]); // Einfügen die Daten dlink_insert einfügen (0, & & IG & & IG & & IG & & & 1]); Data printf ("dlink_is_empty () =%d/n", dlink_is_eMpty ()); Die Größe der beiden verlinkten Liste der beiden verlinkten Liste int i; ) dlink_get (i); zwanzig "," dreißig "," Fringf ("/n ----%s ----%s--/n", __func __); 0, Sarr [0]); Zwei -Way -verlinkte Liste; n ", dlink_size ()); // Die Größe der beiden verknüpften Liste // Drucken Sie alle Daten in der in der beiden verknüpften Liste; char *p; int sz = dlink_size (); for (i = 0; tag_stu {int id; char name [20];} stu; {40, {40, {40, {40, "Dan"},};#Define arr_stu_size ", __func __); create_dlink (); // Erstellen einer zwei -Way -Linked List dlink_insert (0, & arr_stu [0] ); "dlink_is_empty () =%d/n", dlink_is_empl ()); Zwei -Way -L -Liste // alle Daten in den beiden verlinkten Liste int i; ) dlink_get (i); ); String_test (); Object_test (); Zurück 0;}Auslaufergebnis
---- int_Test ---- dlink_is_empty () = 0dlink_size () = 3dlink_get (0) = 30d_get (1) = 20dlink_get 0dlink_size () = 3dlink_get (0) = Thirtydlink_get (1) = Twentydlink_get (2) = TEN -- .
2. C ++ realisiert die Doppelkettenliste
Implementieren Sie den Code Two -Way -verknüpfte Listendatei (Doublelink.h)
#IFNDEF double_link_hxx#double_link_hxx#include <ISstream> Verwenden von Namespace std; Prev, dnode *next) {this-> value = t; size (); int delete_last (); ) {// "Geschwindigkeit" erstellen. Hinweis: Es gibt keine Speicherdaten auf dem Kopf! Phead = neuer dnode <t> (); > :: ~ DoughLink () {// alle Knoten dnode <t>* ptmp; ; Kettenliste 为空 Vorlage <Klasse T> int Doublelink <T> :: is_empy () {return count == 0;} // 获取第 INDEX 位置的节点 Template <Klasse T> Dnode <T>* Doublelink <t>: : get_node (int index) {// Beurteilung Parametergültigkeit if (index <0 || index> = cout) {cout << "Node fehlgeschlagen! / Finding if (index <= count/ 2) {int i = 0; } / / Reverse Search int j = 0; ; Temple <Klasse T> Trivelink <T> :: get_first () {return get_node (0)-> Wert;} // den Wert des letzten Knotens abrufen. Indexposition vor Template <Klasse T> Int Doublelink <T> :: Insert (int Index, t t) {ifx == 0) return Insert_first (t) ;; > Prev); Template <Klasse T> Int Doublelink <T> :: Insert_fring (t) {dnode <t>* pnode = new Dnode <T> (T, PHED-> Weiter); > NEXT = PNODE; > PREV = PNODE; > NEXT-> PREV = PINDEX-> PREV; T> int doubleLink <t> :: Delete_first () {return del (0);} // 删除最后一个节点 Vorlage <Klasse T> int Doublelink <T> :: Delete_Last () {return del (count-);}; #EndifZwei -Way -verknüpfte Listen -Testdatei (dlinkest.cpp)
#Include <IoStream> #include "Doublelink.h" UserSpace std; --- "<< endl; // Erstellen Sie eine mit zwei Wegen verknüpfte Liste Doublelink <int>* pdlink = new Doubelink <int> (); PDLink-> append_last (10); << "is_empty () =" << pdlink-> is_empty () << endl; << endl; -> Get (i) << endl;} void String_test () {String Sarr [4] = {"Ten", "Twenty", "Thirty", "Vierzig"}; ---- "" << endl; Das zweite Element in Sarr in die erste PDLink-> append_last (Sarr [0]); ); () = "<< pdlink-> size () << endl; // alle Daten int sz = pdlink-> size (); für (int i = 0; i <sz; i ++)" <") = "<< pdlink-> get (i) << endl;} struct stu {int id; Zeichen name [20];}; static stu arr_stu [] = {10," Sky "}, {20 20," Jody " "}, {30," vic "}, {40," Dan "},};#arr_stu_size cout <<"/n ---- Object_test ---- "<< endl; // Erstellen Sie ein Zwei- Way Linked List Doublelink <Stu>* pdlink = new Doubelink <Stu> (); > Append_last (arr_stu [0]); zur ersten Position //, ob die mit zwei Wegen verknüpfte Liste leer ist << "is_empy () =" << Pdlink-> is_empty () << endl; = "<< pdlink-> size () << endl; // Drucken Sie alle Daten int sz = pdlink-> size () in der mit zwei Wegen verlinkten Liste; = 0; i <sz; i ++) {P. = pdlink-> get (i); main () {int_teest (); String_test (); Object_test (); Zurück 0;}Beispiel Beschreibung
Im obigen Beispiel habe ich die "Anweisung" und "Implementierung" der beiden verknüpften Liste in die Header -Datei eingerichtet. Die Programmierspezifikationen warnen uns: Die Erklärung und Implementierung des Antrags trennen, und der Betrag der Header -Datei (.H -Datei oder .hpp) enthielt nur die Anweisung und war für die Implementierung in der Implementierungsdatei (.cpp -Datei) verantwortlich!
Warum machst du das? Dies liegt daran, dass die Vorlage in der Implementierung einer zweistraßen verlinkten Liste der Vorlage angewendet wird. Einfach ausgedrückt, wenn es in Doublelink.h deklariert und in Doublelink.cpp implementiert wird; Aus bestimmten Gründen können Sie sich auf "Warum C ++ - Compiler nicht die separate Kompilierung von Vorlagen unterstützen" beziehen.
Auslaufergebnis
---- int_test ---- is_empty () = 0SIZE () = 3pdlink (0) = 30pdlink (1) = 20pdlink (2) = 10 ---- String_test ----- leer () = 0SIZE () = 3pdlink (0) = Thirtypdlink (1) = Twentypdlink (2) = zehn ---- Object_TEEST ---- IS_EMPTY () = 0SIZE () = 3PDLink (0) = [30, vic] pdlink (1) = [ 20 20, Jody] pdlink (2) = [10, Sky]
3. Java realisiert die Dual -Ketten -Liste
Doublelink.java Implementierung
/*** Javas zwei Wege verlinkte Liste. * HINWEIS: In dem Sammlungspaket von Java gibt es eine zweistraßen verlinkte Liste. / Top Headpate Dnode <T> mhead; {this.Value = value; Hinweis: Es gibt keine Speicherdaten auf dem Kopf! Mhead = neuer dnode <t> (null, null, null); Return mcount;} // Ob die verknüpfte Liste leer ist MCOUND) Neue IndexoutOfBoundSexception (); } // 反向查找 dnode <t> rnode = mhead.prev; int rindex = mcount - Index -1; für (int j = 0; j <rindex; j ++) rnode = rnode. / Erhalten Sie den Wert des Knotens der Indexposition. <t> (t, mhead, mhead.Next); T> (t, Inode.Prev, Inode); Public void InsertFirst (t t) {Insert (0, t);} // Fügen Sie den Knoten zum Ende der verknüpften Liste des öffentlichen void appendlast (t t) {dnode <t> neuer Dnode <T> (t, mhead. Prev mhead); .Next = Inode.Next; Knoten public void deletelast () {del (mcount-);}}Testprogramm (dlinkTest.java)
/*** Javas zwei Wege verlinkte Liste. * HINWEIS: In dem Sammlungspaket, das mit Java geliefert wird, gibt es eine mit zwei Wege verknüpfte Liste. Zwei-Way-Linked Table Operation Int Data private statische void int_teest () {int [] {10, 20, 30, 40}; = Neuer Doublelink <Grainer> (); Erste Position //, ob die zwei -Way -verlinkte Liste leer ist. d/n ", dlink.size ()); // Drucken Sie alle Knoten für (int i = 0; i <dlink.size (); i ++) system.out .println (" dlink ("+i+") = "+dlink.get (i));} private statische void String_test () {String [] Sarr = {" Ten "," Twenty "," Thirty ", vierzig" "}; /n ---- String_test ---- "); // Erstellen Sie eine mit zwei Wegen verknüpfte Liste Doublelink <string> dlink = new Doubelink <string> (); [1]); // Einfügen das zweite Element in Sarr einfügen in die erste Position dlink.appendlast (Sarr [0]); Die erste Position //, ob die zwei -Way -Linked -Liste leeres System ist. =%d/ n ", dlink.size ()); // Drucken Sie alle Knoten für (int i = 0; i <dlink.size (); i ++) system.out.println (" dlink ("+i+ ") ="+dlink.get (i));} // Die interne Klasse private statische Klasse Schüler {private String -ID Student (int id, String -Name) {this.id = id; ouverridepublic String toString () {"+id+", "+name+"] ";} tudent [] studers = new Student [] {New Student (10," Sky "), neuer Schüler (20," Jody "), neu, neu Student (30, "Vic"), neuer Schüler (40, "Dan"),}; Zwei-Wege-LISTE-DOUBLERINK <Studenten> DLink = neuer Doublelink <Studenten> (); Das erste Element in den Schülern von Dlink.InsertFirst (Schüler [Schüler [Schüler [2]); printf ("isempty () =%b/n", dlink.isempty ()); Knoten für (int i = 0; i <dlink.size ()); Statische void main (string [] arts) {int_test (); String_test (); Object_test (); }}Auslaufergebnis
---- int_test ---- isEmpty () = fAlsesize () = 3Dlink (0) = 30Dlink (1) = 20Dlink (2) = 10 ---- String_test —-- isEmpty () = falsesize () = 3Dlink (0) = Thirtydlink (1) = TwentyDlink (2) = Ten ---- Object_TEEST-isEmpty () = falsesize () = 3Dlink (0) = [30, Vic] Dlink (1) = [20 20) , Jody] dlink (2) = [10, Sky]
Das obige ist der gesamte Inhalt dieses Artikels.