Listy
           Lists


Podrozdziały   Tematy pokrewne
 

Budowa listy

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

 

list

 

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.

 

Pole następnika wskazuje element następny na liście.

Pole poprzednika wskazuje element poprzedni na liście.

 

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:

 

list

 

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ę.

 

list

 

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

 

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:

nastepnik - 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].nastepnikngl
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].nastepnik ← 0
K02: L[x].poprzednik ← 0
K03: Jeśli ngl = 0, to nglx i zakończ
K04: ingl
K05: Dopóki L[i].nastepnik ≠ 0: wykonuj i ← L[i].nastepnik
K06: L[i].nastepnikx
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].nastepnikx,
inaczej:
    nglx
K05: Zakończ

Dodawanie elementu za i-tym elementem listy

K01: L[x].poprzedniki
K02: L[x].następnik ← L[i].nastepnik
K03: L[i].nastepnikx
K04: Jeśli L[x].nastepnik ≠ 0, to L[L[x].nastepnik].poprzednikx
K05: Zakończ

 

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].nastepnik ← L[i].nastepnik
inaczej
    ngl ← L[i].nastepnik
K02: Jeśli L[i].nastepnik ≠ 0, to L[L[i].nastepnik].poprzednik ← L[i].poprzednik
K03: Zakończ

 

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.

 

list

 

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

 

list

 

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.

 

list

 

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

 

list

 

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.

 

Efekt uruchomienia programu
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.

 

DevPascal
// 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.
Code::Blocks
// 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;
}
Free 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>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Demonstracja zastosowania list

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


...

 


Zobacz również na:

Sortowanie rozrzutowe | Sortowanie kubełkowe 1 | Sortowanie kubełkowe 2 | Sortowanie przez zliczanie | Sortowanie pozycyjne

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.