Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Pełny algorytm sortowania rozrzutowego wymaga nowej struktury danych zwanej listą. Lista zbudowana jest z ciągu elementów:
Dostęp do elementów listy nie jest swobodny. Zwykle z
i-tego elementu możemy przejść do elementu następnego
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:
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ę.
Jeśli nagłówek zawiera wartość zero, to lista nie posiada żadnego elementu. Mówimy wtedy, iż lista jest pusta.
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. |
K01: | L[x].następnik ← ngl |
K02: | L[x].poprzednik ← 0 |
K03: | Jeśli ngl ≠ 0, to L[ngl].poprzednik ← x |
K04: | ngl ← x |
K05: | Zakończ |
K01: | L[x].następnik ← 0 |
K02: | L[x].poprzednik ← 0 |
K03: | Jeśli ngl = 0, to ngl ≠ x i zakończ |
K04: | i ← ngl |
K05: | Dopóki L[i].następnik ≠ 0: wykonuj i ← L[i].następnik |
K06: | L[i].następnik ← x |
K07: | L[x].poprzednik ← i |
K08: | Zakończ |
K01: | L[x].następnik ← i |
K02: | L[x].poprzednik ←L[i].poprzednik |
K03: | L[i].poprzednik ← x |
K04: | Jeśli L[x].poprzednik
≠ 0, to L[L[x].poprzednik].następnik ← x, inaczej: ngl ← x |
K05: | Zakończ |
K01: | L[x].poprzednik ← i |
K02: | L[x].następnik ← L[i].następnik |
K03: | L[i].następnik ← x |
K04: | Jeśli L[x].następnik
≠ 0, to L[L[x].następnik].poprzednik ← x |
K05: | Zakończ |
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 |
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.
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).
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ę dwukierunkową można zapętlić w obu kierunkach otrzymując dwukierunkową listę cykliczną:
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 |
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 ©2024 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:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.