Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Listy
 Lists

SPIS TREŚCI
Podrozdziały

Budowa listy

Pełny algorytm sortowania rozrzutowego wymaga nowej struktury danych zwanej listą. Lista zbudowana jest z ciągu elementów:

obrazek

Dostęp do elementów listy nie jest swobodny. Zwykle z i-tego elementu możemy przejść do elementu następnego (i + 1) lub do elementu poprzedniego (i - 1).  O takiej strukturze danych mówimy, że jest sekwencyjna.

Każdy element listy oprócz swoich danych zawiera dwa dodatkowe pola.

Pola te umożliwiają przesuwanie się odpowiednio wprzód i wstecz listy.

Zawartość pół następnika i poprzednika zależy od sposobu realizacji listy w pamięci komputera. Jeśli elementy listy będą tworzone dynamicznie w pamięci pobieranej od systemu operacyjnego, to wtedy pola te będą zawierały adresy elementu następnego i poprzedniego. Taki sposób tworzenia list jest w ogólnym przypadku najlepszy, jednakże dla nas posiada on pewną istotną niedogodność - pobieranie pamięci dla każdego nowego elementu listy wymaga wywołania odpowiednich funkcji systemowych, co zajmuje drogocenny czas. Dlatego wykorzystamy nieco inny sposób.

Poszczególne elementy listy będziemy tworzyli w tablicy (podobnie jak drzewa i stogi w algorytmie sortowania stogowego). Dzięki temu nie tracimy czasu na przydzielanie pamięci dla kolejnych elementów listy. W przypadku tablicy pola następnika i poprzednika wskazują indeksy odpowiednich elementów. Umówmy się, iż pierwszy element tablicy ma indeks o wartości 1. Wartość 0 nie wskazuje zatem żadnego elementu i możemy wykorzystać ją do zaznaczania końców listy:

Ostatni element listy zawiera wartość zero w polu następnika - nie istnieje element następny.

Pierwszy element listy zawiera wartość zero w polu poprzednika - nie istnieje element poprzedni.

Kolejność elementów na liście nie ma nic wspólnego z ich kolejnością w tablicy i może być zupełnie różna:

obrazek

Lista oprócz samych elementów zawierających dane budowana jest często z dodatkowym elementem zwanym nagłówkiem. Nagłówek zawiera jedynie indeks pierwszego elementu listy. Jest to jakby wejście, brama, poprzez którą wchodzimy na listę.

obrazek

Jeśli nagłówek zawiera wartość zero, to lista nie posiada żadnego elementu. Mówimy wtedy, iż lista jest pusta.

Na początek:  podrozdziału   strony 

Dodawanie elementu do listy

Naszym zadaniem jest dołączenie do listy kolejnego elementu. Przy wykonywaniu tej operacji mogą wystąpić różne sytuacje, które postaramy się tutaj dokładnie przedstawić w postaci listy kroków. Umówmy się, iż będziemy stosowali następujące oznaczenia:

L[ ] - tablica, której elementy są elementami listy. Pierwszy indeks wynosi 1.
x - indeks wstawianego na listę elementu, x ∈ N
ngl - nagłówek listy, ngl ∈ N
i - zmienna przechowująca indeksy kolejno przeglądanych elementów listy, i ∈ N

Każdy element listy ma następujące pola:

następnik - zawiera indeks następnego elementu na liście, nastepnik ∈ C
poprzednik - zawiera indeks poprzedniego elementu na liście, poprzednik ∈ C
dane - dane o dowolnej strukturze, które przechowuje element listy.

Dodawanie elementu na początek listy

K01: L[x].następnikngl
K02: L[x].poprzednik ← 0
K03: Jeśli ngl ≠ 0,
to L[ngl].poprzednikx
K04: nglx
K05: Zakończ

Dodawanie elementu na koniec listy

K01: L[x].następnik ← 0
K02: L[x].poprzednik ← 0
K03: Jeśli ngl = 0,
to nglx
i zakończ
K04: ingl
K05: Dopóki L[i].następnik ≠ 0:
    wykonuj i ← L[i].następnik
K06: L[i].następnikx
K07: L[x].poprzedniki
K08: Zakończ

Dodawanie elementu przed i-tym elementem listy

K01: L[x].następniki
K02: L[x].poprzednik ←L[i].poprzednik
K03: L[i].poprzednikx
K04: Jeśli L[x].poprzednik ≠ 0,
to L[L[x].poprzednik].następnikx,
inaczej: nglx
K05: Zakończ

Dodawanie elementu za i-tym elementem listy

K01: L[x].poprzedniki
K02: L[x].następnik ← L[i].następnik
K03: L[i].następnikx
K04: Jeśli L[x].następnik ≠ 0,
to L[L[x].następnik].poprzednikx
K05: Zakończ
Na początek:  podrozdziału   strony 

Usuwanie elementu z listy

Z listy będziemy usuwali element o indeksie i. Fizycznie usunięty element zostanie w tablicy, lecz nie będzie go w łańcuchu elementów tworzących listę. Operacja usuwania elementu z listy nie jest potrzebna przy sortowaniu elementów za pomocą algorytmów sortowania rozrzutowego, podajemy ją jednak dla kompletności wykładu.

K01: Jeśli L[i].poprzednik ≠ 0,
to L[L[i].poprzednik].następnik ← L[i].następnik
inaczej ngl ← L[i].następnik
K02: Jeśli L[i].następnik ≠ 0,
to L[L[i].następnik].poprzednik ← L[i].poprzednik
K03: Zakończ
Na początek:  podrozdziału   strony 

Rodzaje list

Jeśli element listy posiada zdefiniowane pole następnika i poprzednika, to po liście zbudowanej z takich elementów możemy poruszać się w obu kierunkach - zarówno w przód jak i wstecz. Lista nosi nazwę dwukierunkowej.

obrazek

Na liście dwukierunkowej zdefiniowane są wszystkie opisane poprzednio operacje wstawiania i usuwania elementu.

Jeśli elementy listy mają zdefiniowane tylko pole następnika, to po liście można poruszać się tylko w jednym kierunku. Lista nosi nazwę jednokierunkowej. W wielu sytuacjach taki uproszczony rodzaj listy jest zupełnie wystarczający (patrz - przykłady programów).

obrazek

Na liście jednokierunkowej zdefiniowana jest operacja wstawiania elementu na początku listy, na końcu listy oraz po i-tym elemencie.

Jeśli pole następnika ostatniego elementu listy wskazuje pierwszy element, to lista staje się jednokierunkową listą cykliczną. Po liście możemy się poruszać w kółko bez końca.

obrazek

Listę dwukierunkową można zapętlić w obu kierunkach otrzymując dwukierunkową listę cykliczną:

obrazek

Na początek:  podrozdziału   strony 

Przykładowe programy

Prezentowane programy demonstrują przykładowe zastosowania list. Generują one 19 3-literowych wyrazów zbudowanych z liter A, B i C wybieranych losowo. Następnie tworzą trzy listy wyrazów rozpoczynających się kolejno na literę A, B i C.

Wynik:
Demonstracja zastosowania list
------------------------------
  (C)2005 mgr Jerzy Walaszek

3-literowe teksty losowe:

 BCA BCC BCB AAB CAC CBA BBB CBC BCC BBB BCB ABA BBB ABC CAC BCB ACC ACB ACC

Na litere A : ACC ACB ACC ABC ABA AAB

Na litere B : BCB BBB BCB BBB BCC BBB BCB BCC BCA

Na litere C : CAC CBC CBA CAC

Zwróć uwagę, iż program umieszcza na listach teksty w kolejności odwrotnej do ich występowania w ciągu wejściowym. Dzieje się tak dlatego, iż zastosowaliśmy najprostszy wariant - dołączanie elementu na początek listy. Zatem nowe elementy pojawiają się na liście przed elementami już na niej umieszczonymi. Jeśli chcesz zachować kolejność elementów na liście taką samą jak w ciągu wejściowym, to ciąg wejściowy należy przeglądać od końca.

C++
// Przykład zastosowania list
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

#include <iostream>
#include <cstdlib>
#include <time.h>

using namespace std;

const int MAXN = 19;

int main()
{
  struct
  {
    unsigned int nastepnik;
    char dane[3];
  } L[MAXN+1];
  unsigned int ngl[3],i,j;

  cout << "Demonstracja zastosowania list\n"
          "------------------------------\n"
          "  (C)2005 mgr Jerzy Walaszek  \n\n"
          "3-literowe teksty losowe:\n\n";

// Tworzymy losowe ciągi 3-literowe w elementach tablicy L[]

  srand((unsigned)time(NULL));

  for(i = 1; i <= MAXN; i++)
    for(j = 0; j < 3; j++)
      L[i].dane[j] = 65 + rand() % 3;

// Wyświetlamy ciągi

  for(i = 1; i <= MAXN; i++)
    cout << " " << L[i].dane[0] << L[i].dane[1] << L[i].dane[2];
  cout << endl << endl;

// Zerujemy nagłówki list

  for(i = 0; i < 3; i++) ngl[i] = 0;

// Tworzymy listy wyrazów na A, B i C

  for(i = 1; i <= MAXN; i++)
  {
    j = L[i].dane[0] - 65;
    L[i].nastepnik = ngl[j];
    ngl[j] = i;
  }

// Odczytujemy kolejne listy i wyświetlamy je w oknie konsoli

  for(i = 0; i < 3; i++)
  {
    cout << "Na litere " << (char)(i + 65) << " :";
    j = ngl[i];
    while(j)
    {
      cout << " " << L[j].dane[0] << L[j].dane[1] << L[j].dane[2];
      j = L[j].nastepnik;
    }
    cout << endl << endl;
  }

// Gotowe, kończymy program

  cout << endl;
  return 0;
}
Pascal
// Przykład zastosowania list
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

const MAXN = 19;

// Tutaj definiujemy typ elementów listy

type

  TElement = record
    nastepnik : cardinal;
    dane      : string[3];
  end;

// Tutaj deklarujemy zmienne

var
  L   : array[1..MAXN] of TElement;
  ngl : array[0..2] of cardinal;
  i,j : cardinal;

begin
  writeln('Demonstracja zastosowania list');
  writeln('------------------------------');
  writeln('  (C)2005 mgr Jerzy Walaszek  ');
  writeln;
  writeln('3-literowe teksty losowe:');
  writeln;

// Tworzymy losowe ciągi 3-literowe w elementach tablicy L[]

  randomize;
  for i := 1 to MAXN do L[i].dane := char(65 + random(3)) +
                                     char(65 + random(3)) +
                                     char(65 + random(3));
// Wyświetlamy ciągi

  for i := 1 to MAXN do write(L[i].dane:4);
  writeln; writeln;

// Zerujemy nagłówki list

  for i := 0 to 2 do ngl[i] := 0;

// Tworzymy listy wyrazów na A, B i C

  for i := 1 to MAXN do
  begin
    j := ord(L[i].dane[1]) - 65;
    L[i].nastepnik := ngl[j];
    ngl[j] := i
  end;

// Odczytujemy kolejne listy i wyświetlamy je w oknie konsoli

  for i := 0 to 2 do
  begin
    write('Na litere ' + char(i + 65) + ' :');
    j := ngl[i];
    while j > 0 do
    begin
      write(L[j].dane:4); j := L[j].nastepnik
    end;
    writeln; writeln;
  end;

// Gotowe, kończymy program

  writeln;
  writeln('Koniec, nacisnij klawisz ENTER...');
  readln;
end.
Basic
' Przykład zastosowania list
'--------------------------------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie
'--------------------------------------------------------

CONST MAXN = 19

' Tutaj definiujemy typ elementów listy

TYPE TElement
  nastepnik AS UINTEGER
  dane      AS STRING * 3
END TYPE

' Tutaj deklarujemy zmienne

DIM L(MAXN) AS TElement
DIM AS UINTEGER  ngl(0 TO 2),i,j

PRINT "Demonstracja zastosowania list"
PRINT "------------------------------"
PRINT "  (C)2005 mgr Jerzy Walaszek  "
PRINT
PRINT "3-literowe teksty losowe:"
PRINT

' Tworzymy losowe ciągi 3-literowe w elementach tablicy L[]

RANDOMIZE

FOR i = 1 TO MAXN
  L(i).dane = CHR$(65 + INT(RND(1) * 3)) + _
              CHR$(65 + INT(RND(1) * 3)) + _
              CHR$(65 + INT(RND(1) * 3))
NEXT

' Wyświetlamy ciągi

FOR i = 1 TO MAXN:  PRINT " ";L(i).dane;: NEXT
PRINT: PRINT

' Zerujemy nagłówki list

FOR i = 0 TO 2: ngl(i) = 0: NEXT

' Tworzymy listy wyrazów na A, B i C

FOR i = 1 TO MAXN
  j = ASC(MID$(L(i).dane,1,1)) - 65
  L(i).nastepnik = ngl(j)
  ngl(j) = i
NEXT

' Odczytujemy kolejne listy i wyświetlamy je w oknie konsoli

FOR i = 0 TO 2
  PRINT "Na litere ";CHR$(i + 65);" :";
  j = ngl(i)
  WHILE j > 0
    PRINT " ";L(j).dane;
    j = L(j).nastepnik
  WEND
  PRINT: PRINT
NEXT

' Gotowe, kończymy program

PRINT
PRINT "Koniec, nacisnij dowolny klawisz..."
SLEEP
END
JavaScript
<html>
  <head>
  </head>
  <body>
    <form style="BORDER-RIGHT: #ff9933 1px outset;
                 PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset;
                 PADDING-LEFT: 4px; PADDING-BOTTOM: 1px;
                 BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px;
                 BORDER-BOTTOM: #ff9933 1px outset;
                 BACKGROUND-COLOR: #ffcc66" name="frmblistdemo">
      <h3 style="text-align: center">Demonstracja zastosowania list</h3>
      <p style="TEXT-ALIGN: center">
        (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie
      </p>
      <hr>
      <p style="TEXT-ALIGN: center">
        <input onclick="main()" type="button" value="Start" name="B1">
      </p>
      <p id="t_out" style="TEXT-ALIGN: center">...</p>
    </form>

<script language=javascript>

// Przykład zastosowania list
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

var MAXN = 19;
var ngl  = new Array();
var L    = new Array();
var i,j,t;

for(i = 1; i <= MAXN; i++) L[i] = new Object();

function main()
{

// Tworzymy losowe ciągi 3-literowe w elementach tablicy L[]

  for(i = 1; i <= MAXN; i++)
  {
    L[i].dane = "";
    for(j = 0; j < 3; j++)
      L[i].dane += String.fromCharCode(65 + Math.floor(Math.random() * 3));
  }

// Wyświetlamy ciągi

  t = "3-literowe teksty losowe:<BR><BR>";
  for(i = 1; i <= MAXN; i++) t += L[i].dane + " ";
  t += "<BR><BR>";

// Zerujemy nagłówki list

  for(i = 0; i < 3; i ++) ngl[i] = 0;

// Tworzymy listy wyrazów na A, B i C

  for(i = 1; i <= MAXN; i++)
  {
    j = L[i].dane.charCodeAt(0) - 65;
    L[i].nastepnik = ngl[j];
    ngl[j] = i;
  }

// Odczytujemy kolejne listy i wyświetlamy je w oknie konsoli

  for(i = 0; i < 3; i++)
  {
    t += "Na litere " + String.fromCharCode(i + 65) + " :";
    j = ngl[i];
    while(j)
    {
      t += " " + L[j].dane;
      j = L[j].nastepnik;
    }
    t += "<BR><BR>";
  }

// Gotowe, kończymy program

  document.getElementById("t_out").innerHTML = t;
}

</script> 

  </body>
</html>

Wynik:
Demonstracja zastosowania list
------------------------------
  (C)2005 mgr Jerzy Walaszek

3-literowe teksty losowe:

 BCA BCC BCB AAB CAC CBA BBB CBC BCC BBB BCB ABA BBB ABC CAC BCB ACC ACB ACC

Na litere A : ACC ACB ACC ABC ABA AAB

Na litere B : BCB BBB BCB BBB BCC BBB BCB BCC BCA

Na litere C : CAC CBC CBA CAC

Demonstracja zastosowania list

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

Na początek:  podrozdziału   strony 

Zobacz również na:
Sortowanie rozrzutowe | Sortowanie kubełkowe 1 | Sortowanie kubełkowe 2 | Sortowanie przez zliczanie | Sortowanie pozycyjne


Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.