Algorithme - Les listes contiguës et chaînées
Warum Listen?
Im Alltag findet man häufig Listen wie:- Personen in einem Wartezimmer.
- Studenten, die in einem Fachgebiet eingeschrieben sind.
- Autos warten auf die rote Ampel.
- etc.
Was sind die Merkmale einer Liste?
- Sie werden nacheinander verarbeitet.
- Von beiden Enden begrenzt < Kopf> und < queue>.
- Es ist möglich, Elemente hinzuzufügen oder zu entfernen.
- Dynamische Struktur (Größe variiert).
1 - Zusammenhängende Darstellung
Wir haben gesehen, dass wir eine Liste mit einem Array T[1..max] darstellen können, aber ihre Struktur ist statisch (ihre Größe ist zu dem Zeitpunkt festgelegt, an dem wir das in der Deklaration definieren).
| Listentyp: Artikel { T: array[1..lmax] von element length: 0..lmax } |
Die wichtigsten Operationen
- Le parcours
- Prozedurpfad(L:list)Startfür i von 1 bis L.lengthfaireprocess(L.T[i])finfaireEnde
- Löschung (siehe: s Löschen eines Elements aus einer zusammenhängenden Liste).
- Die Einfügung (siehe: Einfügen eines Elements in eine Liste contiguous).
Die Vorteile
- Direkter Zugriff.
- Löschen und Einfügen am Ende der Liste.
- Einfache Implementierung.
Cons
- Sie müssen wissen, wie man die Länge ändert.
- Löschungen und Einfügungen beinhalten Offsets.
2- Vertretung verkettet
Es besteht aus einer Sequenz von Links (Blöcken) und jeder Link besteht aus zwei Feldern:- Ein Elementfeld.
- Ein Adressfeld, das auf Folgendes verweist.
L: Zeiger auf den ersten Link.
Eine leere verknüpfte Liste wird durch L=null.
| ptr type: link pointer Linktyp: article { Tal; element link: ptr } chainlisted< type: link/span> var L: chainlisted |
Die wichtigsten Operationen
- Der Kurs.
- Prozedurpfad(L:list)Nach oben
pp := L.link // Kopf de L
solange pp != null
fairetreat(L.T[i])
pp := *pp.linkfinfaireFin
- Unterdrückung(siehe: Einfügen und Löschen eines Elements in einer verknüpften Liste.).
- Insertion(siehe: Einfügen und Löschen eines Elements in einer verknüpften Liste.).
Vorteile
- Sequenzieller Pfad.
- Link entfernt.
- Einfügen eines Links.
Cons
- Indirekter Zugriff auf ein Element, Sie müssen über i-1-Links gehen, um die ith maillon.
- Verlust von Speicherplatz für Links.