Lineare Tabelle
Lineare Tabellen sind die einfachsten und am häufigsten verwendeten Datenstrukturen. Es handelt sich um endliche Sequenzen, die aus n einzelnen Datenelementen (Knoten) bestehen. Unter ihnen ist die Zahl n der Datenelemente die Länge der Tabelle. Wenn n Null ist, wird es zu einem leeren Tisch. Eine nicht leere lineare Tabelle wird normalerweise als:
(A1, A2,…, Ai-1, Ai, Ai+1,…, an)
1. Sequentieller Speicher und Algorithmus der linearen Tabellen
Die sequentielle Speicherung einer linearen Tabelle bezieht sich auf die Speicherung der Datenelemente einer linearen Tabelle in einen Satz kontinuierlicher Speichereinheiten mit Adressen in ihrer logischen Reihenfolge. Die auf diese Weise gespeicherte lineare Tabelle wird als sequentielle Tabelle bezeichnet.
1. strukturelle Definition der Bestellentabelle
öffentliche Klasse seqlist { / * Der anfängliche Raum ist 10 * / private statische endgültige int list_size = 10; /* Array -Daten werden verwendet, um Elemente zu speichern*/ private int [] Daten; /* Die aktuelle Tabelle ist lang, die tatsächliche Anzahl der gespeicherten Elemente*/ private int Länge; } 2. Einlegen Sie den Betrieb
Der Insertionsoperation der sequentiellen Tabelle bezieht sich auf das Einsetzen eines neuen Elements zwischen dem I-1th-Element und dem I-ten Element der linearen Tabelle. Da die angrenzenden Elemente der Sequenztabelle auch in der physikalischen Struktur nebeneinander liegen, müssen ihre physikalischen Speicherbeziehungen ebenfalls entsprechende Änderungen erfahren. Sofern i = n+1 nicht, müssen alle Elemente, die aus dem i-ten Element der ursprünglichen Auftragstabelle beginnen, um 1 Position nach hinten verschoben werden.
/** * Fügen Sie ein neues Element vor der i-ten Position in den Bestellentabellenlistenknoten ein zurückkehren; } if (list.length> = list_size) {System.out.println ("Überlauf"); zurückkehren; } für (int j = list.length - 1; j> = i - 1; j -) { / * starten Sie vom letzten Element und bewegen Sie sich einzeln zurück. } /* Neues Element einfügen* / list.data [i-1] = node; / * Der Tabellenlänge 1 hinzufügen */ list.length ++; } 3. Operation löschen
Der Löschvorgang der sequentiellen Tabelle bezieht sich auf das Löschen des I-h-Elements in der Tabelle. Im Gegensatz zum Insertionsoperation verschiebt das Insertion das Element rückwärts und der Löschvorgang verschiebt das Element vorwärts.
/*** Löschen Sie das i-te Element in der Liste der Bestellentabelle und geben Sie das gelöschte Element zurück* @param List Sequence Tabelle* @param i Element Position* @return Node*/public int deletElist (SEQLIST-Liste, int i) {int node = 0; if (i <0 || i> list.length) {system.out.println ("Positionsfehler"); Return Node; } node = list.data [i-1]; für (int j = i; j <list.length; j ++) { /* Element Forward* / list.data [j-1] = list.data [j]; } list.length -; Return Node;} 4.. Inverse Order Tisch
Verwenden Sie zunächst die Hälfte der Länge der Tabelle als Häufigkeit der Schleifensteuerung, tauschen Sie das letzte Element in der Tabelle in der Reihenfolge des ersten Elements aus, tauschen Sie das zweite letzte Element in der Reihenfolge des zweiten Elements aus und so weiter, bis der Austausch abgeschlossen ist.
/*** Sequence -Tabelle Inverse* @paramlist Original Order Tabelle* @return Sequence Tabelle nach inverse*/public seqlist konvertiert (SEQList -Liste) {int node; int länge = list.length/2; für (int i = 0; i <länge; i ++) { /* symmetrische Austauschelemente* / int j = list.length - 1 - i; node = list.data [i]; list.data [i] = list.data [j]; list.data [j] = node; } Rückgabeliste; } 2. Kettenspeicher und Algorithmus der linearen Tabellen
Der Speicherplatz der Datenelemente der Kettenspeicherstruktur, die lineare Tabellen speichert, kann kontinuierlich oder diskontinuierlich sein, sodass auf die Knoten der verknüpften Liste nicht zufällig zugegriffen werden können. Die Kettenspeicherung ist eine der häufigsten Speichermethoden.
Bei Verwendung einer Kettenspeicherstruktur zur Darstellung jedes Datenelements ist zusätzlich zum Speichern der Informationen des Elements selbst eine Adresse erforderlich, die den Speicherort der nachfolgenden Elemente angibt. Die durch diese Speichermethode dargestellte lineare Tabelle wird als verknüpfte Liste bezeichnet.
5. strukturelle Definition einer einzelnen verknüpften Liste
öffentliche Klasse LinkList { /* Datenfeld* / private Zeichendaten; /* Folge Element*/ Private LinkList Weiter;} 6. Tischgebäudealgorithmus
Die Header -Insertion -Methode beginnt mit einer leeren Tabelle, liest die Daten wiederholt, generiert einen neuen Knoten, speichert die Lesedaten im Datenfeld des neuen Knotens und fügt dann den neuen Knoten auf den Kopf der aktuellen verknüpften Liste ein, bis sie endet.
/*** TABLE nach Header Insertion* @param chars Zeichenarray* @return Single Linked List*/public linkList createListf (char [] chars) {linkList -Knoten; LinkList head = null; für (char ch: chars) { /* beantragen einen neuen Knoten* / node = new linkList (); node.data = ch; /* Auf den Nachfolgeknoten verweisen*/ node.next = Kopf; head = node; } /* Zurück zum Kopfknoten* / return Head;} 7. Tail Insertion Methode Table Building Algorithmus
Die Reihenfolge der Knoten in der Header -Insertion -Tabelle ist das Gegenteil der Reihenfolge beim Eingeben. Wenn die Reihenfolge der Eingabe konsistent ist, kann die Schwanzinsertionsmethode verwendet werden.
/*** Tail Insertion -Methode zum Erstellen von Tabellen* @param chars Zeichenarray* @return Single Linked List*/public linkList createlist (char [] chars) {linkList node; LinkList head = null; LinkList app = null; für (char ch: chars) {node = new linkList (); node.data = ch; if (head == null) { /* Der neue Knoten ist der Kopfknoten* / head = node; } else { /* Der vorherige Knoten verweist auf den neuen Knoten* / ard.next = node; } /* Der Schwanz der Tabelle zeigt auf den neuen Knoten* / rard = Knoten; } /* Zurück zum Kopfknoten* / return Head;}Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.