Algorytmy i Struktury Danych - Wyszukiwanie największego elementu listy

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.

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:

p_max	–	wskaźnik elementu z największą wartością w polu data
p	–	wskaźnik elementu listy

Lista kroków:

K01:	p_max ← head	ustawiamy p_max 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 ) > ( 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 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;
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

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

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

Na początek: podrozdziału strony

Zaproponuj podobny algorytm dla listy cyklicznej.

Na początek: podrozdziału strony

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.

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

Wyszukiwanie największego/najmniejszego elementu listy

Problem