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 |
©2019 mgr Jerzy Wałaszek |
ProblemNależy wyszukać na liście element zawierający największą/najmniejszą wartość. |
Problem ten rozwiązujemy w sposób podobny do wyszukiwania największego/najmniejszego elementu tablicy. Jeśli lista jest pusta, zwracamy adres zerowy. W przeciwnym razie zapamiętujemy pierwszy element listy. Przeglądamy listę od elementu drugiego do końca. Jeśli istnieje kolejny element listy, to sprawdzamy, czy jego pole data zawiera wartość większą/mniejszą od pola data elementu zapamiętanego. Jeśli tak, to zapamiętujemy ten element i przechodzimy w pętli do jego następnika. Gdy osiągniemy koniec listy, zwracamy adres elementu zapamiętanego.
head | – | adres pierwszego elementu listy |
adres elementu listy, który największą wartość w polu data
p max | – | wskaźnik elementu z największą wartością w polu data |
p | – | wskaźnik elementu listy |
K01: | p max ← head | ustawiamy p max na pierwszy element listy |
K02: | Jeśli head = nil, to idź do K07 | w przypadku listy pustej, kończymy |
K03: | p ← (head→next) | w p umieszczamy adres następnika pierwszego elementu listy |
K04: | Dopóki p ≠ nil, wykonuj K05...K06 | w pętli przetwarzamy elementy listy |
K05: | Jeśli (p→data) > (p max→data), to p max ← p | jeśli bieżący element ma większą wartość, to zapamiętujemy go |
K06: | p ← (p→next) | przechodzimy do następnika |
K07: | Zakończ z wynikiem p max |
Uwaga, jeśli mamy wyszukać element o wartości najmniejszej, to
zmieniamy kierunek nierówności
W poniższej tabelce znajdują się przykładowe funkcje wyznaczania wartości maksymalnej na liście. Po lewej stronie dla listy jednokierunkowej, po prawej stronie dla listy dwukierunkowej.
Pascal | ||
function l_max(head : PslistEl) : PslistEl; var p, pmax : PslistEl; begin pmax := head; if head <> nil then begin p := head^.next; while p <> nil do begin if p^.data > pmax^.data then pmax := p; p := p^.next; end; end; l_max := pmax; end; |
function l_max(var L : dlistVar) : PdlistEl; var p, pmax : PdlistEl; begin pmax := L.head; if L.head <> nil then begin p := L.head^.next; while p <> nil do begin if p^.data > pmax^.data then pmax := p; p := p^.next; end; end; l_max := pmax; end; |
|
C++ | ||
slistEl * l_max(slistEl * head) { slistEl * p, * pmax; pmax = head; if(head) for(p = head->next; p; p = p->next) if(p->data > pmax->data) pmax = p; return pmax; } |
dlistEl * l_max(dlistVar & L) { dlistEl * p, * pmax; pmax = L.head; if(L.head) for(p = L.head->next; p; p = p->next) if(p->data > pmax->data) pmax = p; return pmax; } |
|
Basic | ||
Function l_max(head As slistEl Ptr) As slistEl Ptr Dim As slistEl Ptr p, pmax pmax = head If head Then p = head->next While p If p->data > pmax->data Then pmax = p p = p->next Wend End If l_max = pmax End Function |
Function l_max(ByRef L As dlistVar) As dlistEl Ptr Dim As dlistEl Ptr p, pmax pmax = L.head If L.head Then p = L.head->next While p If p->data > pmax->data Then pmax = p p = p->next Wend End If l_max = pmax End Function |
Uwaga:
Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich. |
Program wykorzystuje obiekt listy
dwukierunkowej, w którym dodaliśmy metodę max oraz zmodyfikowaliśmy
nieco metodę printl. Tworzona jest lista |
Pascal// Wyszukiwanie największego elementu // Data: 18.02.2012 // (C)2019 mgr Jerzy Wałaszek //----------------------------------- program dlist_max; // Definicje typów //---------------- type PdlistEl = ^dlistEl; // wskaźnik do elementów listy // Element listy //-------------- dlistEl = record next : PdlistEl; // następnik prev : PdlistEl; // poprzednik data : char; end; // Definicja obiektu listy dwukierunkowej //--------------------------------------- dlist = object public head : PdlistEl; // początek listy tail : PdlistEl; // koniec listy count : cardinal; // licznik elementów constructor init; destructor destroy; procedure printl; procedure push_front(v : char); procedure push_back(v : char); procedure insert_before(e : PdlistEl; v : char); procedure insert_after(e : PdlistEl; v : char); procedure remove(e : PdlistEl); procedure pop_front; procedure pop_back; function max : PdlistEl; end; //--------------------------------------------- // Definicje metod obiektu listy dwukierunkowej //--------------------------------------------- // Inicjuje pola zmiennej listy //----------------------------- constructor dlist.init; begin head := nil; tail := nil; count := 0; end; // Usuwa elementy listy //--------------------- destructor dlist.destroy; begin while count > 0 do pop_front; end; // Procedura wyświetla zawartość elementów listy //---------------------------------------------- procedure dlist.printl; var p : PdlistEl; begin write(count:3, ' : '); p := head; while p <> NIL do begin write(p^.data); p := p^.next; end; writeln; end; // Procedura dodaje nowy element na początek listy //------------------------------------------------ procedure dlist.push_front(v : char); var p : PdlistEl; begin new(p); // tworzymy nowy element p^.data := v; p^.prev := nil; p^.next := head; head := p; inc(count); if p^.next <> nil then p^.next^.prev := p else tail := p; end; // Procedura dodaje nowy element na koniec listy //---------------------------------------------- procedure dlist.push_back(v : char); var p : PdlistEl; begin new(p); // tworzymy nowy element p^.data := v; p^.next := nil; p^.prev := tail; tail := p; inc(count); if p^.prev <> nil then p^.prev^.next := p else head := p; end; // Procedura dodaje nowy element przed wybranym //--------------------------------------------- procedure dlist.insert_before(e : PdlistEl; v : char); var p : PdlistEl; begin if e = head then push_front(v) else begin new(p); p^.data := v; p^.next := e; p^.prev := e^.prev; inc(count); e^.prev^.next := p; e^.prev := p; end; end; // Procedura dodaje nowy element za wybranym //------------------------------------------ procedure dlist.insert_after(e : PdlistEl; v : char); var p : PdlistEl; begin if e = tail then push_back(v) else begin new(p); p^.data := v; p^.next := e^.next; p^.prev := e; inc(count); e^.next^.prev := p; e^.next := p; end; end; // Procedura usuwa wybrany element z listy //---------------------------------------- procedure dlist.remove(e : PdlistEl); begin dec(count); if e^.prev <> nil then e^.prev^.next := e^.next else head := e^.next; if e^.next <> nil then e^.next^.prev := e^.prev else tail := e^.prev; dispose(e); end; // Procedura usuwa element z początku listy //----------------------------------------- procedure dlist.pop_front; begin if count > 0 then remove(head); end; // Procedura usuwa element z końca listy //-------------------------------------- procedure dlist.pop_back; begin if count > 0 then remove(tail); end; // Wyszukuje element o największej wartości //----------------------------------------- function dlist.max : PdlistEl; var p, pmax : PdlistEl; begin pmax := head; if head <> nil then begin p := head^.next; while p <> nil do begin if p^.data > pmax^.data then pmax := p; p := p^.next; end; end; max := pmax; end; //--------------- // Program główny //--------------- var L : dlist; p : PdlistEl; i : integer; begin Randomize; L.init; for i := 1 to 40 do L.push_back(char(65 + random(26))); L.printl; p := L.max; L.insert_before(p, '.'); L.insert_after(p, '.'); L.printl; L.destroy; end. |
C++// Wyszukiwanie największego elementu // Data: 18.02.2012 // (C)2019 mgr Jerzy Wałaszek //----------------------------------- #include <iostream> #include <iomanip> #include <cstdlib> #include <ctime> using namespace std; // Element listy //-------------- struct dlistEl { dlistEl * next; // następnik dlistEl * prev; // poprzednik char data; }; // Definicja obiektu listy dwukierunkowej //--------------------------------------- class dlist { public: dlistEl * head; // początek listy dlistEl * tail; // koniec listy unsigned count; // licznik elementów dlist(); // konstruktor ~dlist(); // destruktor void printl(); void push_front(char v); void push_back(char v); void insert_before(dlistEl * e, char v); void insert_after(dlistEl * e, char v); void remove(dlistEl * e); void pop_front(); void pop_back(); dlistEl * max(); }; //------------------------------------ // Metody obiektu listy dwukierunkowej //------------------------------------ // Inicjuje pola zmiennej listy //----------------------------- dlist::dlist() { head = tail = NULL; count = 0; } // Usuwa listę z pamięci //---------------------- dlist::~dlist() { while(count) pop_front(); } // Wyświetla zawartość elementów listy //---------------------------------------------- void dlist::printl() { dlistEl * p; cout << setw(3) << count << ": "; p = head; while(p) { cout << p->data; p = p->next; } cout << endl; } // Dodaje nowy element na początek listy //------------------------------------------------ void dlist::push_front(char v) { dlistEl * p; p = new dlistEl; p->data = v; p->prev = NULL; p->next = head; head = p; count++; if(p->next) p->next->prev = p; else tail = p; } // Dodaje nowy element na koniec listy //---------------------------------------------- void dlist::push_back(char v) { dlistEl * p; p = new dlistEl; p->data = v; p->next = NULL; p->prev = tail; tail = p; count++; if(p->prev) p->prev->next = p; else head = p; } // Dodaje nowy element przed wybranym //----------------------------------- void dlist::insert_before(dlistEl * e, char v) { dlistEl * p; if(e == head) push_front(v); else { p = new dlistEl; p->data = v; p->next = e; p->prev = e->prev; count++; e->prev->next = p; e->prev = p; } } // Dodaje nowy element za wybranym //-------------------------------- void dlist::insert_after(dlistEl * e, char v) { dlistEl * p; if(e == tail) push_back(v); else { p = new dlistEl; p->data = v; p->next = e->next; p->prev = e; count++; e->next->prev = p; e->next = p; } } // Usuwa wybrany element z listy //------------------------------ void dlist::remove(dlistEl * e) { count--; if(e->prev) e->prev->next = e->next; else head = e->next; if(e->next) e->next->prev = e->prev; else tail = e->prev; delete e; } // Usuwa element z początku listy //------------------------------- void dlist::pop_front() { if(count) remove(head); } // Usuwa element z końca listy //---------------------------- void dlist::pop_back() { if(count) remove(tail); } // Wyszukuje element o największej wartości //----------------------------------------- dlistEl * dlist::max() { dlistEl * p, * pmax; pmax = head; if(head) for(p = head->next; p; p = p->next) if(p->data > pmax->data) pmax = p; return pmax; } //--------------- // Program główny //--------------- int main() { dlist L; dlistEl * p; int i; srand(time(NULL)); for(i = 0; i < 40; i++) L.push_back(65 + rand() % 26); L.printl(); p = L.max(); L.insert_before(p, '.'); L.insert_after(p, '.'); L.printl(); return 0; } |
Basic' Wyszukiwanie największego elementu ' Data: 18.02.2012 ' (C)2019 mgr Jerzy Wałaszek '----------------------------------- ' Element listy '-------------- Type dlistEl next As dlistEl Ptr ' następnik prev As dlistEl Ptr ' poprzednik data As String * 1 End Type ' Typ obiektowy listy dwukierunkowej '----------------------------------- Type dlist head As dlistEl Ptr ' początek listy tail As dlistEl Ptr ' koniec listy count As UInteger ' licznik elementów Declare Constructor() Declare Destructor() Declare Sub printl() Declare Sub push_front(v As String) Declare Sub push_back(v As String) Declare Sub insert_before(e As dlistEl Ptr, v As String) Declare Sub insert_after(e As dlistEl Ptr, v As String) Declare Sub remove(e As dlistEl Ptr) Declare Sub pop_front() Declare Sub pop_back() Declare Function max() As dlistEl Ptr End Type '--------------- ' Program główny '--------------- Dim L As dlist Dim p As dlistEl Ptr Dim i As Integer Randomize For i = 1 To 40: L.push_back(Chr(65 + Int(Rnd() * 26))): Next L.printl() p = L.max() L.insert_before(p, ".") L.insert_after(p, ".") L.printl() End ' Konstruktor listy '------------------ Constructor dlist() head = 0 tail = 0 count = 0 End Constructor ' Usuwa listę z pamięci Destructor dlist() While count > 0 pop_front() Wend End Destructor ' Procedura wyświetla zawartość elementów listy '---------------------------------------------- Sub dlist.printl() Dim p As dlistEl Ptr Print Using "### : ";count; p = head while p Print p->Data; p = p->next Wend Print End Sub ' Procedura dodaje nowy element na początek listy '------------------------------------------------ Sub dlist.push_front(v As String) Dim p As dlistEl Ptr p = New dlistEl p->data = v p->prev = 0 p->next = head head = p count += 1 If p->next Then p->next->prev = p Else tail = p End If End Sub ' Procedura dodaje nowy element na koniec listy '---------------------------------------------- Sub dlist.push_back(v As String) Dim p As dlistEl Ptr p = New dlistEl p->data = v p->next = 0 p->prev = tail tail = p count += 1 If p->prev Then p->prev->next = p Else head = p End If End Sub ' Procedura dodaje nowy element przed wybranym '--------------------------------------------- Sub dlist.insert_before(e As dlistEl Ptr, v As String) Dim p As dlistEl Ptr If e = head Then push_front(v) Else p = New dlistEl p->data = v p->next = e p->prev = e->prev count += 1 e->prev->next = p e->prev = p End If End Sub ' Procedura dodaje nowy element za wybranym '------------------------------------------ Sub dlist.insert_after(e As dlistEl Ptr, v As String) Dim p As dlistEl Ptr If e = tail Then push_back(v) Else p = New dlistEl p->data = v p->next = e->next p->prev = e count += 1 e->next->prev = p e->next = p End If End Sub ' Procedura usuwa wybrany element z listy '---------------------------------------- Sub dlist.remove(e As dlistEl Ptr) count -= 1 If e->prev Then e->prev->next = e->next Else head = e->next End If If e->next Then e->next->prev = e->prev Else tail = e->prev End If Delete e End Sub ' Procedura usuwa element z początku listy '----------------------------------------- Sub dlist.pop_front() If count > 0 Then remove(head) End Sub ' Procedura usuwa element z końca listy '-------------------------------------- Sub dlist.pop_back() If count > 0 Then remove(tail) End Sub ' Wyszukuje element o największej wartości '----------------------------------------- Function dlist.max() As dlistEl Ptr Dim As dlistEl Ptr p, pmax pmax = head If head Then p = head->next While p If p->data > pmax->data Then pmax = p p = p->next Wend End If max = pmax End Function |
Wynik: |
40 : OMIHMSYOTLPQABOJRIRDCMNFSLEHWBHOAIZFOSFS 42 : OMIHMSYOTLPQABOJRIRDCMNFSLEHWBHOAI.Z.FOSFS |
Zaproponuj podobny algorytm dla listy cyklicznej.
![]() |
Zespół Przedmiotowy |
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.