Simulierte einköpfige Tabelle
Lineare Tabelle:
Lineare Tabellen (auch sequentielle Tabellen genannt) sind die grundlegendsten, einfachsten und am häufigsten verwendeten Datenstrukturen.
Die Beziehung zwischen Datenelementen in einer linearen Tabelle ist eine Eins-zu-Eins-Beziehung, dh mit Ausnahme der ersten und letzten Datenelemente sind andere Datenelemente mit dem Ende verbunden.
Die logische Struktur linearer Tabellen ist einfach, die einfach zu implementieren und zu bedienen ist.
In praktischen Anwendungen werden lineare Tabellen in Form von speziellen linearen Tabellen wie Stapeln, Warteschlangen und Saiten verwendet.
Die grundlegenden Eigenschaften der linearen Struktur sind:
1. In der Sammlung muss ein einzigartiges "erstes Element" sein;
2. Es muss ein einzigartiges "letztes Element" in der Sammlung geben;
3. Mit Ausnahme des letzten Elements gibt es einen einzigartigen Nachfolger (neuester Artikel).
4. Mit Ausnahme des ersten Elements gibt es ein einzigartiges Frontantrieb (vorderes Stück).
Linked List: Linked List
Eine verknüpfte Liste ist eine nicht kontinuierliche und nichtsequentielle Speicherstruktur auf einer physischen Speichereinheit. Die logische Reihenfolge der Datenelemente lautet, dass jedes Datenelement, das über die Zeigerverbindungsreihenfolge in der verlinkten Liste implementiert wurde, in einem "Linkpunkt" enthalten ist.
Ein Link ist ein Objekt einer Klasse, und dieser Typ kann als Link bezeichnet werden. In der verknüpften Liste gibt es viele ähnliche Links, und jeder Link enthält ein Feld, auf das als nächstes auf den nächsten Link verwiesen wird.
Das verknüpfte Listenobjekt selbst enthält einen Verweis auf den ersten Linkknoten. (Wenn es keine Ersten gibt, kann es nicht gefunden werden)
Eine verknüpfte Liste kann nicht direkt auf Datenelemente wie ein Array zugreifen (unter Verwendung von Untersuchungen), muss jedoch mit der Beziehung zwischen Daten positioniert werden, dh auf den nächsten Link, auf den der Linkknoten verwiesen wird, und dann auf die nächste, bis auf die erforderlichen Daten zugegriffen wird und die zeitliche Komplexität des Insertierens und das Löschen der erforderlichen Daten an der Spezifikation des Kopfes, das angegeben ist, und die Ausgabe des Spezifikationsnoduss, und das Auseinanderstellen des Referenzs. Diese Operationen erfordern einen Durchschnitt, wenn die Hälfte der Knoten in der verknüpften Liste mit einer Effizienz von O (n) gesucht wird.
Single -verknüpfte Liste:
Eine lineare Tabelle wird durch "Sequenz von Knoten" dargestellt und als lineare verknüpfte Liste bezeichnet (einzelne verknüpfte Liste)
Es handelt sich um eine Kettenzugriffsdatenstruktur, die eine Reihe von Speichereinheiten mit willkürlichen Adressen verwendet, um Datenelemente in einer linearen Tabelle zu speichern. (Dieser Satz von Speicherzellen kann entweder kontinuierlich oder diskontinuierlich sein)
Die Struktur des Linkknotens:
Datenfelddaten, die Knotenwerte speichern; Zeigerfeld (Kettenfeld), das als nächstes die Knotenreferenz speichert
Die verknüpfte Liste verknüpft die N -Knoten der linearen Tabelle in ihrer logischen Reihenfolge über die Linkdomäne jedes Knotens.
Eine verknüpfte Liste mit nur einem Linkfeld pro Knoten wird als einzelne Linkliste bezeichnet. In einer Richtung gibt es nur Hinweise auf nachfolgende Knötchen.
/*** Single Linked List: Header Insertion -Methode und zuerst beenden* Die linke Seite der verknüpften Liste wird als Kettenkopf bezeichnet und die rechte Seite wird als Kettenschwanz bezeichnet. * Die Header -Einfügungsmethode zum Erstellen einer einzigen verknüpften Liste wird erhalten, indem das rechte Ende der verknüpften Liste als festgelegt angezeigt wird, und die verknüpfte Liste erstreckt sich weiterhin nach links. * Das erste, was aus der Header Insertion -Methode kommt, ist der Tail -Knoten * @Author Stone */ öffentliche Klasse SinglelinkedList <T> {private link <t> zuerst; // Der erste Knoten public SingLelinkedList () {} public boolean isempty () {return first == null; } public void InsertFirst (t data) {// In den Kopf des Kettenverbifts einfügen <T> newlink = new Link <T> (Daten); newlink.next = zuerst; // Der nächste des neuen Knotens zeigt auf den vorherigen Knoten first = newlink; } public link <T> deleteFirst () {// Den Kettenheader -Link <T> temp = First; First = First.Next; // Ändern Sie den ersten Knoten, um die Temperatur zurückzugeben. } public link <T> find (t t) {link <T> find = First; while (find! = null) {if (! find.data.equals (t)) {find = find.Next; } else {break; }} return find; } public link <T> delete (t t) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <T> temp = First; First = First.Next; // Ändern Sie den ersten Knoten in den nächsten Knoten zurück. }} Link <t> p = zuerst; Link <T> q = zuerst; while (! P.Data.equals (t)) {if (p.Next == null) {// Melden Sie sich bis zum Ende der Kette an, aber nicht zurückgegebener Null; } else {q = p; p = P.Next; }} Q.Next = P.Next; Rückkehr p; } public void displayList () {// transip system.out.println ("list (first-> last):"); Link <T> current = First; while (current! = null) {current.displaylink (); current = current.Next; }} public void displayListeverse () {// Inverse Traversal Link <T> p = zuerst, q = first.Next, t; Während (q! = null) {// Zeiger umgekehrt ist, ist die durchquerte Datenreihenfolge rückwärts t = q.Next; // no3 if (p == zuerst) {// Wenn es der ursprüngliche Header ist, sollte der .Next des Kopfes leer sein. P.Next = null; } Q.Next = p; // no3 -> no1 Zeiger reverse p = q; // Start ist umgekehrt q = t; // No3 starten} // In der obigen Schleife oben, zuerst.Next ist leer, und wenn Q null ist und die Schleife nicht ausführt, ist P das ursprüngliche Datenelement. Nach der Inversion wird P an erster zugeordnet = P; DisplayList (); } Klasse Link <T> {// Link Point t Data; // Datenfeldverbindung <T> Weiter; // nachfolgende Zeiger, Knotenketten -Domänenverbindung (t data) {this.data = data; } void displayLink () {System.out.println ("Die Daten ist" + data.toString ()); }} public static void main (String [] args) {SingleLinkedList <Ganzzahl> list = new SinglelinkedList <Grapier> (); list.insertfirst (33); list.insertfirst (78); list.insertfirst (24); list.insertfirst (22); list.insertfirst (56); list.displayList (); list.deletefirst (); list.displayList (); System.out.println ("find:" + list.find (56)); System.out.println ("find:" + list.find (33)); System.out.println ("Finden Sie:" + list.delete (99)); System.out.println ("Finden Sie:" + list.delete (24)); list.displayList (); System.out.println ("--- reverse ----"); LIST.DISPLAYLISTREWERSE (); }}Liste (zuerst-> zuletzt): Die Daten sind 56 Die Daten sind 22 Die Daten sind 24 Die Daten sind 78 Die Daten sind 33 Liste (zuerst-> zuletzt). Finden Sie: linked_list.singLelinkedList$Link@17dfafd1 (zuerst-> zuletzt): Die Daten sind 22 Die Daten sind 78 Die Daten sind 33 --- umgekehrt --- Liste (zuerst-> zuletzt): Die Daten sind 33 Die Daten sind 78 Die Daten sind 22
Einzelverleihungsliste: Tail Insertion -Methode, wieder zuerst heraus - Wenn das linke Ende der verknüpften Liste festgelegt ist, wird die verknüpfte Liste weiterhin nach rechts erstreckt, diese Methode zur Festlegung einer verknüpften Liste wird als Schwanzinsertionsmethode bezeichnet.
Beim Erstellen einer verknüpften Liste mit Tail Insertion -Methode ist der Kopfzeiger behoben, so
Das erste, was aus der Schwanzinsertionsmethode kommt, ist der Kopfknoten.
öffentliche Klasse SinglelinkedList2 <T> {private link <t> head; // Der erste Knoten public SingLelinkedList2 () {} public boolean isempty () {return head == null; } public void InsertLast (t data) {// link <T> newlink = new Link <T> (Daten); if (head! = null) {link <T> nextp = head.Next; if (nextp == null) {head.next = newlink; } else {link <T> reck = null; while (NextP! NextP = NextP.Next; } rard.next = newlink; }} else {head = newLink; }} public link <T> deletElast () {// den Schwanz des Kettenverbinds löschen <T> p = Kopf; Link <T> q = Kopf; while (P.Next! Wenn die Schleife endet, ist Q gleich dem vorletzten Ende der Kette q = p; p = P.Next; } // löschen Q.Next = null; Rückkehr p; } public link <T> find (t t) {link <T> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.Next; } else {break; }} return find; } public link <T> delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <T> temp = head; Head = Head.Next; // Ändern Sie den ersten Knoten, um die Temperatur zurückzugeben. }} Link <T> p = Kopf; Link <T> q = Kopf; while (! P.Data.equals (t)) {if (p.Next == null) {// bedeutet, dass die Rückkehr NULL am Ende der Kette nicht gefunden wurde; } else {q = p; p = P.Next; }} Q.Next = P.Next; Rückkehr p; } public void displayList () {// Travel System.out.println ("List (head-> last):"); Link <T> current = Kopf; while (current! = null) {current.displaylink (); current = current.Next; }} public void displayListeverse () {// Inverse Traversal Link <T> p = head, q = head.Next, t; while (q! = null) {// Der Zeiger ist umgekehrt, und die durchquerte Datenreihenfolge ist rückwärts t = q.Next; // no3 if (p == Kopf) {// Wenn es der ursprüngliche Header ist, sollte der .Next des Kopfes leer sein. P.Next = null; } Q.Next = p; // no3 -> no1 Zeiger reverse p = q; // Start ist umgekehrt q = t; // No3 Start} // In der obigen Schleife oben ist Head.next leer, wenn q null ist und die Schleife nicht ausführt, ist P das ursprüngliche Datenelement. Nach der Inversion wird P dem Kopfkopf = P zugeordnet; DisplayList (); } Klasse Link <T> {// Link Point t Data; // Data Domain Link <T> Weiter; // Folgezeiger, Knotenketten -Domänenverbindung (t data) {this.data = data; } void displayLink () {System.out.println ("Die Daten ist" + data.toString ()); }} public static void main (String [] args) {SingleLinkedList2 <Integer> list = new SinglelinkedList2 <Grapier> (); list.insertLast (33); list.insertLast (78); list.insertLast (24); list.insertLast (22); list.insertLast (56); list.displayList (); list.Deletelast (); list.displayList (); System.out.println ("find:" + list.find (56)); System.out.println ("find:" + list.find (33)); System.out.println ("Finden Sie:" + list.delete (99)); System.out.println ("Finden Sie:" + list.delete (78)); list.displayList (); System.out.println ("---- reverse -----"); LIST.DISPLAYLISTREWERSE (); }}Liste (Head-> Last): Die Daten sind 33 Die Daten sind 78 Die Daten sind 24 Die Daten sind 22 Die Daten sind 56 Liste (Head-> Last): Die Daten sind 33 Die Daten sind 78 Die Daten sind 24 Die Daten sind 22 Finden: null find: linked_list.singLelinked2$Link@4b71bbc9 links delete find: null delete: null delete: null deletee Finden: linked_list.singLelinkedList2$Link@17dfafd1 Liste (Kopf-> Last): Die Daten sind 33 Die Daten sind 24.
Simulieren Sie eine doppelt geendete verknüpfte Liste, um Stack und Warteschlangen mit verknüpften Listen zu implementieren
Doppelte Linkedliste:
Die doppelt geendete verlinkte Liste ist der herkömmlichen verlinkten Liste sehr ähnlich. Es wird nur ein neues Attribut hinzugefügt - dh eine Referenz auf den letzten Link ist hinten.
Auf diese Weise wird das Einfügen am Ende der Kette sehr einfach. Ändern Sie einfach den nächsten Heck in den neu hinzugefügten Knoten, ohne nach dem letzten Knoten zu suchen. Daher gibt es InsertFirst und InsertLast
Beim Löschen des Kettenheaders müssen Sie nur den Referenzpunkt ändern. Beim Löschen des Kettenschwanzes müssen Sie den nächsten Knoten des vorletzten Knotens leeren.
Es ist keine Bezugspunkte darauf, daher wird eine Schleife benötigt, um die Operation zu lesen
/ *** Doppeltege-Link-Liste* @author stone*/ public class zweiendpointlist <t> {privater Link <T> Kopf; // Erster Knoten Private Link <T> hinten; // Heckzeiger public TwoendpointList () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isempty () {return head == null; } public void InsertFirst (t data) {// Einfügen in den Kopf des Ketten -Links <T> newlink = new Link <T> (Daten); newlink.next = head; // Der nächste des neuen Knotens zeigt auf den vorherigen Knoten head = newlink; } public void InsertLast (t data) {// link <T> newlink = new Link <T> (Daten); if (head == null) {rard = null; } if (ard! } else {head = newlink; Head.Next = hinten; } reck = newlink; // Wenn Sie das nächste Mal einfügen, fügen Sie von hinten ein} public t Deletehead () {// den Kettenheader löschen if (isEmpty ()) return null; Link <T> temp = Kopf; Head = Head.Next; // Ändern Sie den ersten Knoten in den nächsten Knoten if (head == null) {<span style = "White-Space: PRE"> </span> rard = head; } return temp.data; } public t find (t t) {if (isEmpty ()) {return null; } Link <T> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.Next; } else {break; }} if (find == null) {return null; } return find.data; } public t delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <T> temp = head; Head = Head.Next; // Ändern Sie den ersten Knoten in den nächsten Knoten return temp.data; }} Link <T> p = Kopf; Link <T> q = Kopf; while (! P.Data.equals (t)) {if (p.Next == null) {// Geben Sie an, dass die Rückkehr NULL am Ende der Kette nicht gefunden wurde; } else {q = p; p = P.Next; }} Q.Next = P.Next; Return P.Data; } public void displayList () {// Travel System.out.println ("List (head-> last):"); Link <T> current = Kopf; while (current! = null) {current.displaylink (); current = current.Next; }} public void displayListeverse () {// Inverse traversal if (isEmpty ()) {return; } Link <t> p = Kopf, q = head.next, t; while (q! = null) {// Der Zeiger ist umgekehrt, und die durchquerte Datenreihenfolge ist rückwärts t = q.Next; // no3 if (p == Kopf) {// Wenn es der ursprüngliche Kopf ist, sollte der .Next des Kopfes leer sein. P.Next = null; } Q.Next = p; // no3 -> no1 Zeiger reverse p = q; // Start ist umgekehrt q = t; // No3 Start} // In der obigen Schleife oben ist Head.next leer, und wenn Q null ist und die Schleife nicht ausführt, ist P das ursprüngliche Datenelement. Nach der Inversion wird P dem Kopfkopf = P zugeordnet; DisplayList (); } Klasse Link <T> {// Link -Knoten -t -Daten; // Data Domain Link <T> Weiter; // Folgezeiger, Knotenketten -Domänenverbindung (t data) {this.data = data; } void displayLink () {System.out.println ("Die Daten ist" + data.toString ()); }} public static void main (String [] args) {TwoendPointList <GanzEger> list = new TwoendPointList <GanzEger> (); list.insertLast (1); list.insertfirst (2); list.insertLast (3); list.insertfirst (4); list.insertLast (5); list.displayList (); list.deleteHead (); list.displayList (); System.out.println ("find:" + list.find (6)); System.out.println ("find:" + list.find (3)); System.out.println ("Finden Sie:" + list.delete (6)); System.out.println ("Finden Sie:" + list.delete (5)); list.displayList (); System.out.println ("--- reverse ----"); LIST.DISPLAYLISTREWERSE (); }}LISTE (Kopf-> letztes): Die Daten sind 4 Die Daten sind 2 Die Daten sind 1 Die Daten sind 3 Die Daten sind 5 Liste (Kopf-> letzt
Verwenden Sie verknüpfte Listen, um den Stapel zu implementieren, und verwenden Sie die einzelne verknüpfte Liste, bevor Sie ihn einfügen.
Diese Klasse verwendet eine doppelt geendete verknüpfte Liste, um zu implementieren:
öffentliche Klasse LinkStack <T> {private TwoendPointList <T> -Daten; public linkStack () {datas = new TwoendPointList <T> (); } // In den Stack public void push (t data) {datas.insertFirst (Daten); } // Legen Sie den Stack public t pop () {return datas.deletehead () heraus; } // Überprüfen Sie die Oberseite des Stack public t peek () {return datas.peekhead (); } // Ob der Stack leer ist, public boolean isEmpty () {return datas.isempty (); } public static void main (String [] args) {linkStack <GanzEger> stack = new linkStack <GeNeger> (); für (int i = 0; i <5; i ++) {stack.push (i); } für (int i = 0; i <5; i ++) {Integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } für (int i = 0; i <6; i ++) {Integer pop = stack.pop (); System.out.println ("Pop:" + pop); } System.out.println ("----"); für (int i = 5; i> 0; i--) {stack.push (i); } für (int i = 5; i> 0; i--) {Integer peek = stack.peek (); System.out.println ("Peek:" + Peek); } für (int i = 5; i> 0; i--) {Integer pop = stack.pop (); System.out.println ("Pop:" + pop); }}}Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 Peek: 4 Pop: 4 Pop: 3 Pop: 2 Pop: 1 Pop: 1 Pop: 0 Pop: NULL ---
Die verknüpfte Listen-Implementierungswarteschlange wird mithilfe einer doppelten verlinkten Liste implementiert:
Public Class LinkQueue <T> {private TwoendPointList <T> -Liste; public linkQueue () {list = new TwoendPointList <T> (); } // Einfügen des Schwanzes der Warteschlange public void Insert (t data) {list.insertLast (data); } // Entfernen Sie den Kopf des Teams public t remove () {return list.deletehead (); } // Sehen Sie sich den Leiter des Teams public t peek () {return list.peekhead () an; } public boolean isempty () {return list.iseMpty (); } public static void main (String [] args) {linkQueue <GeNeger> queue = new linkQueue <GanzEger> (); für (int i = 1; i <5; i ++) {queue.insert (i); } für (int i = 1; i <5; i ++) {Integer peek = queue.peek (); System.out.println ("Peek:" + Peek); } für (int i = 1; i <5; i ++) {Integer remove = queue.remove (); System.out.println ("entfernen:" + entfernen); } System.out.println ("----"); für (int i = 5; i> 0; i--) {queue.insert (i); } für (int i = 5; i> 0; i--) {Integer peek = queue.peek (); System.out.println ("peek2:" + peek); } für (int i = 5; i> 0; i--) {Integer remove = queue.remove (); System.out.println ("entfernen:" + entfernen); }}}Peek: 1 Peek: 1 Peek: 1 Peek: 1 Peek: 1 Entfernen: 1 Entfernen Sie: 2 Entfernen: 3 Entfernen: 4 --- Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Peek2: 5 Entfernen: 5 Entfernen: 4 Entfernen: 3 Entfernen: 2 Entfernen: 1 1