Table à liaison simple simulée
Tableau linéaire:
Les tables linéaires (également appelées tables séquentielles) sont les structures de données les plus basiques, les plus simples et les plus couramment utilisées.
La relation entre les éléments de données dans une table linéaire est une relation un à un, c'est-à-dire, à l'exception des premier et des derniers éléments de données, d'autres éléments de données sont connectés à la fin.
La structure logique des tables linéaires est simple, ce qui est facile à implémenter et à utiliser.
Dans les applications pratiques, des tables linéaires sont utilisées sous la forme de tables linéaires spéciales telles que des piles, des files d'attente et des chaînes.
Les caractéristiques de base de la structure linéaire sont:
1. Il doit y avoir un "premier élément" unique dans la collection;
2. Il doit y avoir un "dernier élément" unique dans la collection;
3. À l'exception du dernier élément, il y a un successeur unique (dernier élément);
4. À l'exception du premier élément, il y a un lecteur avant unique (pièce avant).
Liste liée: liste liée
Une liste liée est une structure de stockage non continu et non séquentielle sur une unité de stockage physique. L'ordre logique des éléments de données est que chaque élément de données implémenté via l'ordre du lien du pointeur dans la liste liée est contenu dans un "point de lien".
Un lien est un objet d'une classe, et ce type peut être appelé lien. Il existe de nombreux liens similaires dans la liste liée, et chaque lien contient un champ suivant référencé au lien suivant.
L'objet Liste Linked contient lui-même une référence au premier nœud de lien. (S'il n'y a pas d'abord, il ne peut pas être localisé)
Une liste liée ne peut pas accéder directement aux éléments de données comme un tableau (à l'aide des indices), mais doit être positionné avec la relation entre les données, c'est-à-dire accéder au lien suivant référencé par le nœud de liaison, puis la suivante, jusqu'à ce que les données requises soient accessibles et que la complexité temporelle de l'inserting et de la suppression des données requises à la tête soit O (1), car la seule référence pointant est nécessaire pour trouver, dédouer le nœud spécifié, et inspecter le point de référence pour trouver, dédouer, dédouer le nœud spécifié, et inspecter les informations de la référence pour trouver, dédouer, Delete the Specifined Node, et INSERTER THE SPECIFIED POINT ESPOSITIVE, DELIQUE, DELLET Ces opérations nécessitent une moyenne de recherche de la moitié des nœuds dans la liste liée, avec une efficacité de O (n).
Liste unique liée:
Une table linéaire est représentée par "séquence de nœuds" et est appelée liste linéaire (liste liée)
Il s'agit d'une structure de données d'accès à la chaîne, en utilisant un ensemble d'unités de stockage avec des adresses arbitraires pour stocker des éléments de données dans une table linéaire. (Cet ensemble de cellules de mémoire peut être continu ou discontinu)
La structure du nœud de liaison:
Données de champ de données qui stocke les valeurs de nœud; champ de pointeur (champ de chaîne) qui stocke la référence de nœud suivant
La liste liée relie les n nœuds de la table linéaire dans leur ordre logique via le domaine de liaison de chaque nœud.
Une liste liée avec un seul champ de lien par nœud est appelée une seule liste de liens. Dans une direction, il n'y a que des références aux nodules ultérieurs.
/ ** * Liste liée unique: méthode d'insertion d'en-tête et première sortie * Le côté gauche de la liste liée est appelé la tête de chaîne et le côté droit est appelé la queue de chaîne. * La méthode d'insertion d'en-tête pour créer une seule liste liée est obtenue en affichant l'extrémité droite de la liste liée comme fixe, et la liste liée continue de s'étendre à gauche. * La première chose qui vient de la méthode d'insertion d'en-tête est le nœud de queue * @author Stone * / classe publique SingleLinkedList <T> {Link privé <T> First; // Le premier nœud public singleLinkedList () {} public boolean isEmpty () {return first == null; } public void insertFirst (t data) {// insérer dans la tête du lien de chaîne <T> newLink = new Link <T> (data); newLink.next = premier; // Le prochain nœud pointe vers le nœud précédent First = NewLink; } lien public <T> DeleteFirst () {// Supprimer le lien d'en-tête de chaîne <T> temp = premier; premier = first.next; // modifie le premier nœud à la température de retour; } lien public <T> find (t t) {link <t> find = premier; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return trouver; } lien public <T> delete (t t) {if (isEmpty ()) {return null; } else {if (first.data.equals (t)) {link <t> temp = premier; premier = first.next; // modifie le premier nœud en la température de retour du nœud suivant; }} Lien <T> p = premier; Lien <T> q = premier; while (! p.data.equals (t)) {if (p.next == null) {// Inscrivez-vous à la fin de la chaîne mais non retrouvé de retour null; } else {q = p; p = p.Next; }} q.next = p.next; Retour p; } public void DisplayList () {// transip system.out.println ("list (premier -> dernier):"); Link <T> current = premier; while (current! = null) {current.displayLink (); courant = current.next; }} public void DisplayListreverSe () {// lien de traversée inverse <T> p = premier, q = first.next, t; tandis que (q! = null) {// pointeur est inversé, l'ordre de données traversé est en arrière t = q.next; // no3 if (p == premier) {// Quand c'est l'en-tête d'origine, le .Next de la tête doit être vide p.Next = null; } q.next = p; // no3 -> no1 pointeur inverse p = q; // Démarrer est inversé Q = T; // no3 start} // Dans la boucle si dans la boucle ci-dessus, d'abord.next est vide, et lorsque q est nul et ne exécute pas la boucle, p est l'élément de données la plupart d'origine. Après l'inversion, P est affecté à First First = P; displayList (); } class link <T> {// lien point t data; // lien de champ de données <T> Suivant; // Pointer ultérieur, lien de domaine de chaîne de nœud (TATA T) {this.data = data; } void displayLink () {System.out.println ("Les données sont" + data.toString ()); }} public static void main (String [] args) {singleLinkedList <Integer> list = new singleLinkedList <Neger> (); 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 ("Delete Find:" + list.delete (99)); System.out.println ("Delete Find:" + list.delete (24)); list.displayList (); System.out.println ("--- Reverse ----"); list.displayListreverSe (); }}Imprimer
Liste (premier -> Dernier): Les données sont 56 Les données sont 22 Les données sont 24 Les données sont 78 Les données sont 33 LISTE (premier -> dernier): Les données sont 22 Les données sont 24 Les données sont 78 Les données sont 33 Rechercher: Null Find: Linked_List.SingleLinkedList$Link@4b71bbc9 Delete: Null Delete Find: Linked_list.SingleLinkedList$Link@17dfafd1 (premier -> dernier): Les données sont 22 Les données sont 78 Les données sont 33 --- Liste inversée --- (premier -> Dernier): les données sont 33 Les données sont 78 Les données sont 22
Liste liée unique: Méthode d'insertion de queue, de retour en premier - Si l'extrémité gauche de la liste liée est corrigée, la liste liée continue de s'étendre à droite, cette méthode d'établissement d'une liste liée est appelée méthode d'insertion de queue.
Lors de la création d'une liste liée avec une méthode d'insertion de queue, le pointeur de tête est corrigé, donc un pointeur de queue doit être configuré pour s'étendre à droite de la liste liée.
La première chose qui vient de la méthode d'insertion de queue est le nœud de tête.
classe publique SingleLinkedList2 <T> {Link privé <T> Head; // Le premier nœud public singleLinkedList2 () {} public boolean isEmpty () {return head == null; } public void insertlast (t data) {// insérer link <t> newLink = new Link <T> (data); if (head! = null) {link <t> nextp = head.next; if (nextp == null) {head.next = newLink; } else {link <t> arrière = null; while (nextp! = null) {rear = nextP; NextP = nextP.Next; } rear.next = newLink; }} else {head = newLink; }} lien public <T> Deletelast () {// Supprimer la queue du lien de chaîne <T> P = Head; Lien <t> q = tête; tandis que (p.Next! = null) {// Le nœud suivant de p n'est pas vide, q est égal au P actuel (c'est-à-dire que est le précédent et P est le suivant). Lorsque la boucle se termine, q est égal à l'avant-dernière extrémité de la chaîne q = p; p = p.Next; } // supprimer q.next = null; Retour p; } lien public <T> find (t t) {link <t> find = head; while (find! = null) {if (! find.data.equals (t)) {find = find.next; } else {break; }} return trouver; } lien public <T> delete (t t) {if (isEmpty ()) {return null; } else {if (head.data.equals (t)) {link <t> temp = head; head = head.next; // modifie le premier nœud à la température de retour; }} Lien <T> p = tête; Lien <t> q = tête; while (! p.data.equals (t)) {if (p.next == null) {// signifie que le retour null n'a pas été trouvé à la fin de la chaîne; } else {q = p; p = p.Next; }} q.next = p.next; Retour p; } public void displayList () {// Travel System.out.println ("list (head -> dernier):"); Link <T> current = head; while (current! = null) {current.displayLink (); courant = current.next; }} public void DisplayListreverSe () {// lien de traversée inverse <T> p = tête, q = head.next, t; tandis que (q! = null) {// Le pointeur est inversé, et l'ordre de données traversé est en arrière t = q.next; // no3 if (p == tête) {// Quand c'est l'en-tête d'origine, le .Next de la tête doit être vide p.Next = null; } q.next = p; // no3 -> no1 pointeur inverse p = q; // Démarrer est inversé Q = T; // no3 start} // Dans la boucle si dans la boucle ci-dessus, head.next est vide, lorsque q est nul et n'exécute pas la boucle, p est l'élément de données le plus d'origine. Après l'inversion, P est affecté à la tête de tête = P; displayList (); } class link <T> {// lien point t data; // lien de domaine de données <T> Suivant; // Pointeur successif, lien de domaine de chaîne de nœud (T data) {this.data = data; } void displayLink () {System.out.println ("Les données sont" + data.toString ()); }} public static void main (String [] args) {singleLinkedList2 <Integer> list = new singleLinkedList2 <Integer> (); 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 ("Delete Find:" + list.delete (99)); System.out.println ("Delete Find:" + list.delete (78)); list.displayList (); System.out.println ("---- Reverse -----"); list.displayListreverSe (); }}Imprimer
Liste (Head -> Dernier): Les données sont 33 Les données sont 78 Les données sont 24 Les données sont 22 Les données sont 56 Liste (Head -> Last): Les données sont 33 Les données sont 78 Les données sont 24. Les données sont 22 Rechercher: Null Find: Linked_List.SingleLinkedList2$Link@4b71bbc9 Delete Find: Null Delete Rechercher: Linked_list.SingleLinkedList2$Link@17dfafd1 List (Head -> Last): Les données sont 33 Les données sont 24. Les données sont 22 --- Liste inverse --- (Head -> Last): Les données sont 22 Les données sont 24 Les données sont 33 33
Simulez une liste liée à double extrémité pour implémenter la pile et les files d'attente avec des listes liées
Liste liée à double extrémité:
La liste liée à double extrémité est très similaire à la liste liée traditionnelle. Il n'a qu'un nouvel attribut ajouté - c'est-à-dire qu'une référence au dernier lien est arrière.
De cette façon, l'insertion à la fin de la chaîne deviendra très facile. Changez simplement le prochain de l'arrière vers le nœud nouvellement ajouté, sans boucle pour rechercher le dernier nœud, donc il y a un insertFirst et un insertlast
Lors de la suppression de l'en-tête de chaîne, il vous suffit de modifier le point de référence; Lorsque vous supprimez la queue de chaîne, vous devez vider le nœud suivant du nœud avant-dernier.
Aucune référence ne pointe, donc une boucle est nécessaire pour lire l'opération
/ ** * Liste liée à double extrémité * @Author Stone * / Classe publique TwoDenDpointList <T> {Link privé <T> Head; // First nœud lien privé <T> arrière; // Pointeur de queue publique TwoDendPointList () {} public t peekhead () {if (head! = null) {return head.data; } return null; } public boolean isEmpty () {return head == null; } public void insertFirst (t data) {// insérer à la tête de la chaîne link <t> newLink = new Link <T> (data); newlink.next = tête; // Le prochain nœud pointe vers la tête du nœud précédent = newLink; } public void insertlast (t data) {// insérer link <t> newLink = new Link <T> (data); if (head == null) {arrière = null; } if (arrière! = null) {rear.next = newLink; } else {head = newLink; head.next = arrière; } arrière = newLink; // La prochaine fois que vous insérez, insérez à partir de l'arrière} public t Deletehead () {// Supprimer l'en-tête de la chaîne if (isEmpty ()) renvoie null; Lien <T> temp = head; head = head.next; // modifie le premier nœud pour être le nœud suivant if (head == null) {<span style = "white-space: pre"> </span> arrière = tête; } retour temp.data; } public t find (t t) {if (isEmpty ()) {return null; } Lien <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; // Modifie le premier nœud au nœud suivant Temp.Data; }} Lien <T> p = tête; Lien <t> q = tête; tandis que (! } else {q = p; p = p.Next; }} q.next = p.next; retour p.data; } public void displayList () {// Travel System.out.println ("list (head -> dernier):"); Link <T> current = head; while (current! = null) {current.displayLink (); courant = current.next; }} public void displayListreverSe () {// Inverse Traversal if (isEmpty ()) {return; } Lien <T> p = tête, q = head.next, t; tandis que (q! = null) {// Le pointeur est inversé, et l'ordre de données traversé est en arrière t = q.next; // no3 if (p == tête) {// Quand c'est la tête d'origine, le .Next de la tête doit être vide p.Next = null; } q.next = p; // no3 -> no1 pointeur inverse p = q; // Démarrer est inversé Q = T; // no3 start} // Dans la boucle si dans la boucle ci-dessus, head.next est vide, et lorsque q est nul et n'exécute pas la boucle, p est l'élément de données la plupart d'origine. Après l'inversion, P est affecté à la tête de tête = P; displayList (); } class link <T> {// link nœud t data; // lien de domaine de données <T> Suivant; // Pointeur successif, lien de domaine de chaîne de nœud (T data) {this.data = data; } void displayLink () {System.out.println ("Les données sont" + data.toString ()); }} public static void main (String [] args) {TwoDenDpointList <Integer> list = new TwoDenDpointList <Integer> (); 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 ("Delete Find:" + list.delete (6)); System.out.println ("Delete Find:" + list.delete (5)); list.displayList (); System.out.println ("--- Reverse ----"); list.displayListreverSe (); }}Imprimer
Liste (Head -> Dernier): Les données sont 4 Les données sont 2 Les données sont 1 Les données sont 3 Les données sont 5 Liste (Head -> En dernier): Les données sont 2 Les données sont 1 La liste des données est 3.
Utilisez des listes liées pour implémenter la pile et utilisez la liste liée unique avant de l'insérer.
Cette classe utilise une liste liée à double extrémité pour implémenter:
classe publique LinkStack <T> {private TwoEndPointList <T> Datas; public linkstack () {dataS = new TwoDenDpointList <T> (); } // mis dans la pile public void push (t data) {datas.insertFirst (data); } // éteignez la pile public t pop () {return datas.deletehead (); } // Vérifiez le haut de la pile public t peek () {return dataS.PeekHead (); } // si la pile est vide publique booléen isEmpty () {return dataS.Isempty (); } public static void main (String [] args) {linkstack <nteger> stack = new LinkStack <Integer> (); pour (int i = 0; i <5; i ++) {stack.push (i); } pour (int i = 0; i <5; i ++) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); } pour (int i = 0; i <6; i ++) {entier pop = stack.pop (); System.out.println ("pop:" + pop); } System.out.println ("----"); pour (int i = 5; i> 0; i--) {stack.push (i); } pour (int i = 5; i> 0; i--) {Integer peek = stack.Peek (); System.out.println ("Peek:" + peek); } pour (int i = 5; i> 0; i--) {entier pop = stack.pop (); System.out.println ("pop:" + pop); }}}Imprimer
PEEEK: 4 PEEEK: 4 PEEEK: 4 PEEEK: 4 PEEEK: 4 PEEEK: 4 POP: 4 POP: 3 POP: 2 POP: 1 POP: 1 POP: 0 POP: NULL --- PEEEK: 1 PEEEK: 1 PEEEK: 1 PEEEK: 1 POP: 1 POP: 1 POP: 2 POP: 3 POP: 4 POP: 5
La file d'attente d'implémentation liée est implémentée à l'aide d'une liste liée à double extrémité:
classe publique LinkQueue <T> {Liste privée TwoDnPointList <T>; public linkQueue () {list = new TwoDenDpointList <T> (); } // insérer la queue de la file d'attente publique void insert (t data) {list.insertLast (data); } // Supprimez la tête de l'équipe publique T dislète () {return list.deletehead (); } // Affichez la tête de l'équipe publique t peek () {return list.PeekHead (); } public boolean isEmpty () {return list.isempty (); } public static void main (String [] args) {linkqueue <nteger> queue = new linkQueue <Integer> (); for (int i = 1; i <5; i ++) {queue.insert (i); } pour (int i = 1; i <5; i ++) {Integer peek = queue.Peek (); System.out.println ("Peek:" + peek); } pour (int i = 1; i <5; i ++) {Integer retire = queue.remove (); System.out.println ("Supprime:" + Supprimer); } System.out.println ("----"); pour (int i = 5; i> 0; i--) {queue.insert (i); } pour (int i = 5; i> 0; i--) {Integer peek = queue.Peek (); System.out.println ("Peek2:" + peek); } pour (int i = 5; i> 0; i--) {Integer retire = queue.Remove (); System.out.println ("Supprime:" + Supprimer); }}}Imprimer
PEEEK: 1 PEEEK: 1 PEEEK: 1 PEEEK: 1 PEEEK: 1 Retirer: 1 Retirer: 2 Retirer: 3 Retirer: 4 --- Peek2: 5 Peek2: 5 Peek2: 5 PEEK2: 5 PEEK2: 5 Retirer: 5 Retirer: 4 Retirer: 3 Retirer: 2 Retirer: 1