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 |
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
pmax | : | wskaźnik elementu z największą wartością w polu data |
p | : | wskaźnik elementu listy |
K01: | pmax ← head | ustawiamy pmax na pierwszy element listy |
K02: | Jeśli head = nil, to idź do kroku 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 kroki K05…K06 |
w pętli przetwarzamy elementy listy |
K05: | Jeśli (p→data) > (pmax→data), to pmax ← 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 pmax |
Uwaga, jeśli mamy wyszukać element o wartości najmniejszej, to zmieniamy kierunek nierówności w kroku K05.
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; |
|
|
||
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 40 przypadkowych znaków od A do Z. Następnie na liście wyszukiwany jest element zawierający znak o najwyższym kodzie ASCII. Znaleziony znak zostaje otoczony kropkami. |
Pascal// Wyszukiwanie największego elementu // Data: 18.02.2012 // (C)2020 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. |
// Wyszukiwanie największego elementu // Data: 18.02.2012 // (C)2020 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)2020 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 |
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.