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.
Ziel ist es, diese Beispiele aus der Praxis darzustellen und in der Informatik zu verarbeiten.

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).
Representation

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


      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
              faire
                  treat(L.T[i])
                  pp := *pp.link
              finfaire
            Fin


        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.