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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Wyszukiwanie największego/najmniejszego elementu listy

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy wyszukać na liście element zawierający największą/najmniejszą wartość.

Rozwiązanie

Problem ten rozwiązujemy w sposób podobny do wyszukiwania największego/najmniejszego elementu tablicy.  Zapamiętujemy adres pierwszego elementu listy. Jeśli jest to adres zerowy, to kończymy i zwracamy ten adres zerowy. W przeciwnym razie przeglądamy listę od elementu następnego do jej końca. Jeśli istnieje następny element listy, to sprawdzamy, czy jego pole data zawiera wartość większą/mniejszą od pola data elementu pod zapamiętanym adresem. Jeśli tak, to zapamiętujemy adres tego element, podmieniając adres zapamiętany poprzednio, po czym przechodzimy w pętli do jego następnika. Gdy osiągniemy koniec listy, zwracamy zapamiętany adres elementu listy.

Algorytm wyszukiwania na liście elementu największego

Wejście:

head : adres pierwszego elementu listy.

Wyjście:

Adres elementu listy, który największą wartość w polu data.

Zmienne pomocnicze:

pmax : wskaźnik elementu z największą wartością w polu data.
p : wskaźnik elementu listy.

Lista kroków:

K01: pmaxhead ; ustawiamy pmax na pierwszy element listy
K02: Jeśli head = nil, ; w przypadku listy pustej, kończymy
     to idź do kroku K07
K03: p ← (headnext) ; w p umieszczamy adres następnika
                     ; pierwszego elementu listy
K04: Dopóki p ≠ nil, ; w pętli przetwarzamy elementy listy
     wykonuj kroki K05…K06
K05:   Jeśli (pdata) > (pmaxdata), ; jeśli bieżący element
       to pmaxp ; ma większą wartość, to zapamiętujemy go
K06:   p ← (pnext) ; 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żej znajdują się przykładowe funkcje wyznaczania wartości maksymalnej na liście. W przypadku listy dwukierunkowej odwołujemy się do pola:

listahead
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;
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;
}
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
Python (dodatek)
# klasa elementu listy
# dwukierunkowej
#---------------------
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
#---------------------------
class dlistVar:

    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # Znajduje max
    def l_max(self):
        pmax = self.head
        if self.head:
            p = self.head.next
            while p:
                if p.data > pmax.data:
                    pmax = p
                p = p.next
        return pmax

Przykładowe programy

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ę l_max( ) oraz zmodyfikowaliśmy nieco metodę l_printl( ). Tworzona jest lista 30 przypadkowych znaków od A do z. Następnie na liście wyszukiwany jest pierwszy element zawierający znak o najwyższym kodzie ASCII. Znaleziony znak zostaje otoczony przy pomocy znaków > i <.
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
//---------------------------------------
  dlistVar = object
    public
      head  : PdlistEl; // początek listy
      tail  : PdlistEl; // koniec listy
      count : cardinal; // licznik elementów

      constructor init;
      destructor  destroy;
      procedure   l_print;
      procedure   l_push_front(v : char);
      procedure   l_push_back(v : char);
      procedure   l_insert_before(e : PdlistEl; v : char);
      procedure   l_insert_after(e : PdlistEl; v : char);
      procedure   l_remove(e : PdlistEl);
      procedure   l_pop_front;
      procedure   l_pop_back;
      function    l_max : PdlistEl;
  end;

//---------------------------------------------
// Definicje metod obiektu listy dwukierunkowej
//---------------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
constructor dlistVar.init;
begin
  head  := nil;
  tail  := nil;
  count := 0;
end;

// Usuwa elementy listy
//---------------------
destructor dlistVar.destroy;
begin
  while count > 0 do l_pop_front;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure dlistVar.l_print;
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 dlistVar.l_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 dlistVar.l_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 dlistVar.l_insert_before(e : PdlistEl;
                                   v : char);
var
  p : PdlistEl;
begin
  if e = head then l_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 dlistVar.l_insert_after(e : PdlistEl;
                                  v : char);
var
  p : PdlistEl;
begin
  if e = tail then l_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 dlistVar.l_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 dlistVar.l_pop_front;
begin
  if count > 0 then l_remove(head);
end;

// Procedura usuwa element z końca listy
//--------------------------------------
procedure dlistVar.l_pop_back;
begin
  if count > 0 then l_remove(tail);
end;

// Wyszukuje element o największej wartości
//-----------------------------------------
function dlistVar.l_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;
  l_max := pmax;
end;

//---------------
// Program główny
//---------------

var

  L : dlistVar;
  p : PdlistEl;
  i : integer;

begin
  Randomize;
  L.init;
  for i := 1 to 30 do
    L.l_push_back(char(65+random(58)));
  L.l_print;
  p := L.l_max;
  L.l_insert_before(p,'>');
  L.l_insert_after(p,'<');
  L.l_print;
  L.destroy;
end.
C++
// 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 dlistVar
{
  public:
    dlistEl * head; // początek listy
    dlistEl * tail; // koniec listy
    unsigned count; // licznik elementów

    dlistVar();  // konstruktor
    ~dlistVar(); // destruktor
    void l_print();
    void l_push_front(char v);
    void l_push_back(char v);
    void l_insert_before(dlistEl * e,
                         char v);
    void l_insert_after(dlistEl * e,
                        char v);
    void l_remove(dlistEl * e);
    void l_pop_front();
    void l_pop_back();
    dlistEl * l_max();
};

//------------------------------------
// Metody obiektu listy dwukierunkowej
//------------------------------------

// Inicjuje pola zmiennej listy
//-----------------------------
dlistVar::dlistVar()
{
  head  = tail = NULL;
  count = 0;
}

// Usuwa listę z pamięci
//----------------------
dlistVar::~dlistVar()
{
  while(count) l_pop_front();
}

// Wyświetla zawartość elementów listy
//----------------------------------------------
void dlistVar::l_print()
{
  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 dlistVar::l_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 dlistVar::l_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 dlistVar::l_insert_before(dlistEl * e,
                               char v)
{
  dlistEl * p;

  if(e == head) l_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 dlistVar::l_insert_after(dlistEl * e,
                              char v)
{
  dlistEl * p;

  if(e == tail) l_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 dlistVar::l_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 dlistVar::l_pop_front()
{
  if(count) l_remove(head);
}

// Usuwa element z końca listy
//----------------------------
void dlistVar::l_pop_back()
{
  if(count) l_remove(tail);
}

// Wyszukuje element o największej wartości
//-----------------------------------------
dlistEl * dlistVar::l_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()
{
  dlistVar L;
  dlistEl * p;
  int i;

  srand(time(NULL));
  for(i = 0; i < 30; i++)
    L.l_push_back(65+rand()%58);
  L.l_print();
  p = L.l_max();
  L.l_insert_before(p,'>');
  L.l_insert_after(p,'<');
  L.l_print();
  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 dlistVar
  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 l_print()
  Declare Sub l_push_front(v As String)
  Declare Sub l_push_back(v As String)
  Declare Sub l_insert_before(e As dlistEl Ptr,_
                              v As String)
  Declare Sub l_insert_after(e As dlistEl Ptr,_
                             v As String)
  Declare Sub l_remove(e As dlistEl Ptr)
  Declare Sub l_pop_front()
  Declare Sub l_pop_back()
  Declare Function l_max() As dlistEl Ptr
End Type

'---------------
' Program główny
'---------------

Dim L As dlistVar
Dim p As dlistEl Ptr
Dim i As Integer

Randomize
For i = 1 To 30
  L.l_push_back(Chr(65+Int(Rnd()*58)))
Next
L.l_print()
p = L.l_max()
L.l_insert_before(p,">")
L.l_insert_after(p,"<")
L.l_print()
End

' Konstruktor listy
'------------------
Constructor dlistVar()
  head  = 0
  tail  = 0
  count = 0
End Constructor

' Usuwa listę z pamięci
Destructor dlistVar()
  While count > 0
  	 l_pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub dlistVar.l_print()
  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 dlistVar.l_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 dlistVar.l_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 dlistVar.l_insert_before(e As dlistEl Ptr,_
                          v As String)

  Dim p As dlistEl Ptr

  If e = head Then
    l_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 dlistVar.l_insert_after(e As dlistEl Ptr,_
                         v As String)

  Dim p As dlistEl Ptr

  If e = tail Then
    l_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 dlistVar.l_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 dlistVar.l_pop_front()
  If count > 0 Then l_remove(head)
End Sub

' Procedura usuwa element z końca listy
'--------------------------------------
Sub dlistVar.l_pop_back()
  If count > 0 Then l_remove(tail)
End Sub

' Wyszukuje element o największej wartości
'-----------------------------------------
Function dlistVar.l_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
  l_max = pmax
End Function
Python (dodatek)
# Wyszukiwanie największego elementu
# Data: 15.05.2024
# (C)2024 mgr Jerzy Wałaszek
#-----------------------------------

import random

# klasa elementu listy
#---------------------
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy dwukierunkowej
#---------------------------
class dlistVar:

    # Konstruktor
    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # Destruktor
    def __del__(self):
        while self.count:
            self.l_pop_front()

    # Wyświetla zawartość listy
    def l_print(self):
        print("%3d: "% self.count,end="")
        p = self.head
        while p:
            print(p.data,end="")
            p = p.next
        print()

    # Dodaje nowy element na początek
    def l_push_front(self,v):
        p = dlistEl(v)
        p.next = self.head
        self.head = p
        self.count += 1
        if p.next:
            p.next.prev = p
        else:
            self.tail = p

    # Dodaje nowy element na koniec
    def l_push_back(self,v):
        p = dlistEl(v)
        p.prev = self.tail
        self.tail = p
        self.count += 1
        if p.prev:
            p.prev.next = p
        else:
            self.head = p

    # Dodaje nowy element przed
    def l_insert_before(self,e,v):
        if e is self.head:
            self.l_push_front(v)
        else:
            p = dlistEl(v)
            p.next = e
            p.prev = e.prev
            self.count += 1
            e.prev.next = p
            e.prev = p

    # Dodaje nowy element za
    def l_insert_after(self,e,v):
        if e is self.tail:
            self.l_push_back(v)
        else:
            p = dlistEl(v)
            p.next = e.next
            p.prev = e
            self.count += 1
            e.next.prev = p
            e.next = p

    # Usuwa wybrany element
    def l_remove(self,e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        del e

    # Usuwa element z początku
    def l_pop_front(self):
        if self.count:
            self.l_remove(self.head)

    # Usuwa element z końca
    def l_pop_back(self):
        if self.count:
            self.l_remove(self.tail)

    # Wyszukuje element o największej wartości
    def l_max(self):
        pmax = self.head
        if self.head:
            p = self.head.next
            while p:
                if p.data > pmax.data:
                    pmax = p
                p = p.next
        return pmax

#---------------
# Program główny
#---------------

L = dlistVar()
for i in range(30):
    L.l_push_back(chr(65+random.randrange(58)))
L.l_print()
p = L.l_max()
L.l_insert_before(p,'>')
L.l_insert_after(p,'<')
L.l_print()
Wynik:
 30 : zAUOF^iXCxfzK^uLS`rmW\nENJXykt
 32 : >z<AUOF^iXCxfzK^uLS`rmW\nENJXykt

Na początek:  podrozdziału   strony 

Zadanie

Zaproponuj podobny algorytm dla listy cyklicznej.


Na początek:  podrozdziału   strony 

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: i-lo@eduinf.waw.pl

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

Informacje dodatkowe.