Wyszukiwanie dwóch najmniejszych elementów

W tym rozdziale pokażemy prosty algorytm, który w jednym przebiegu wyznaczy na liście dwa najmniejsze elementy. Do implementacji listy wykorzystamy klasę listy dwukierunkowej TdoubleList z poprzedniego rozdziału. Lista dwukierunkowa została wybrana ze względu na efektywne wykonanie operacji usuwania elementów, które wykonuje docelowy algorytm Huffmana. Wyszukiwanie elementów będziemy realizowali wg pola key, w którym powinna być umieszczona wartość całkowita określająca wagę danego elementu listy.

Dane wejściowe

list  - lista zawierająca co najmniej dwa elementy
list.front  - adres pierwszego elementu listy
list.back  - adres ostatniego elementu listy, nieużywany w algorytmie
list.counter  - licznik elementów listy, nieużywany w algorytmie.
item  - element listy
item.next  - adres następnego elementu na liście
item.prev  - adres poprzedniego elementu na liście, nieużywany w algorytmie
item.key  - pole klucza elementu, wg którego wyszukujemy dwa elementy najmniejsze

Dane wyjściowe

p1,p2  - wskaźniki dwóch różnych elementów listy, które zawierają najmniejszą wartość w polu klucza, przy czym p1→key ≤ p2→key

Dane pomocnicze

p  - wskaźnik porównywanych elementów listy

Lista kroków

K01: p1 ← lista.front;  p2 ← lista.front→next W p1 i p2 umieszczamy adresy dwóch pierwszych elementów listy
K02: Jeśli p1→key > p2→key, to zamień p1 ↔ p2 Porządkujemy wskaźniki, tak aby p1 wskazywał najmniejszy element.
K03: p ← lista.front→next→next W p umieszczamy adres trzeciego elementu listy.
K04: Dopóki p wskazuje jakiś element, wykonuj kroki K05...K08 Rozpoczynamy pętlę przeglądającą kolejne elementy listy począwszy od trzeciego.
K05:     Jeśli p→key ≥ p2→key, to idź do kroku K08 Jeśli bieżący element p nie jest mniejszy od większego z p1 i p2, kontynuujemy przeglądanie.
K06:     p2 ← p W przeciwnym razie zapamiętujemy ten element.
K07:     Jeśli p1→key > p2→key, to zamień p1 ↔ p2 Porządkujemy wskaźniki, aby p1 zawsze wskazywał element mniejszy
K08:     p ← p→next Przechodzimy do kolejnego elementu listy i kontynuujemy pętlę K04
K09: Zakończ  

       Program

Opisany algorytm jest zaimplementowany jako funkcja składowa klasy TdoubleList o nazwie find2min(p1,p2). Zwróć uwagę na sposób przekazania parametrów p1 i p2 - przez referencję, dzięki czemu funkcja może zwrócić w nich adresy znalezionych elementów listy.

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P014

#include <iostream>

using namespace std;

// deklaracja typu elementu listy
//-------------------------------

struct TlistElement
{
  TlistElement * next, * prev;
  int key;
};

// deklaracja typu klasy listy dwukierunkowej
//-------------------------------------------

class TdoubleList
{
  private:

    TlistElement * front, * back;
    unsigned cnt;

  public:
           
// konstruktor
//------------

    TdoubleList()
    {
      front = back = NULL;
      cnt  = 0;
    }
    
// destruktor
//-----------

    ~TdoubleList()
    {
      TlistElement * p;
      
      while(front)
      {
        p = front->next;
        delete front;
        front = p;
      }              
    }

// Zwraca długość listy
//---------------------

    unsigned size()
    {
      return cnt;
    }

// Dodaje element na początku listy i zwraca jego adres
//-----------------------------------------------------

    TlistElement * push_front(TlistElement * p)
    {
      p->next = front; p->prev = NULL;
      if(front) front->prev = p;
      front = p;
      if(!back) back = front;
      cnt++;
      return front;
    }
    
// Dodaje element na końcu listy i zwraca jego adres
//--------------------------------------------------

    TlistElement * push_back(TlistElement * p)
    {
      if(back) back->next = p;
      p->next = NULL; p->prev = back;
      back = p;
      if(!front) front = back;
      cnt++;
      return back;
    }
    
// Dodaje element p1 za elementem p2 i zwraca adres p1
//----------------------------------------------------

    TlistElement * insert(TlistElement * p1, TlistElement * p2)
    {
      p1->next = p2->next; p1->prev = p2;
      p2->next = p1;
      if(p1->next) p1->next->prev = p1;
      else back = p1;
      cnt++;
      return p1;
    }
    
// Usuwa element z początku listy i zwraca adres usuniętego elementu
//------------------------------------------------------------------

    TlistElement * pop_front()
    {
      TlistElement * p;
      
      if(front)
      {
        p = front;
        front = front->next;
        if(!front) back = NULL;
        else front->prev = NULL;
        cnt--;
        return p;
      }
      else return NULL;     
    }
    
// Usuwa element z końca listy i zwraca adres usuniętego elementu
//---------------------------------------------------------------

    TlistElement * pop_back()
    {
      TlistElement * p;
      
      if(back)
      {
        p = back;
        if(p == front) front = back = NULL;
        else
        {
          back = back->prev;
          back->next = NULL;
        };
        cnt--;
        return p;
      }
      else return NULL;
    }
    
// usuwa z listy element p i zwraca adres usuniętego elementu

    TlistElement * erase(TlistElement * p)
    {
      TlistElement * p1;
      
      if(p->prev) p->prev->next = p->next;
      else front = p->next;
      if(p->next) p->next->prev = p->prev;
      else back = p->prev;
      cnt--;
      return p;
    } 

// zwraca n-ty element listy. Jeśli lista posiada mniej niż n elementów,
// zwraca NULL. Elementy numerujemy od 1.
//----------------------------------------------------------------------

    TlistElement * index(unsigned n)
    {
      TlistElement * p;
      
      if((!n) || (n > cnt)) return NULL;
      else if(n == cnt) return back;
      else if(n < cnt / 2)
      {
        p = front;
        while(--n) p = p->next;
        return p;
      }
      else
      {
        p = back;
        while(cnt > n++) p = p->prev;
        return p;
      }  
    }

// wyświetla kolejno klucze wszystkich elementów listy
//----------------------------------------------------

    void showKeys()
    {
      TlistElement * p;
      
      if(!front) cout << "Lista jest pusta." << endl;
      else
      {
        p = front;
        while(p)
        {
          cout << p->key << " ";
          p = p->next;
        }
        cout << endl;
      }
    }

// Wyszukuje na liście dwa najmniejsze elementy
//---------------------------------------------

    void find2min(TlistElement * &p1, TlistElement * &p2)
    {
      TlistElement * p;
      p1 = front; p2 = front->next;
      if(p1->key > p2->key)
      {
        TlistElement * x;
        x = p1; p1 = p2; p2 = x;
      }
      p = front->next->next;
      while(p)
      {
        if(p->key < p2->key)
        {
          p2 = p;
          if(p1->key > p2->key)
          {
            TlistElement * x;
            x = p1; p1 = p2; p2 = x;
          }      
        }
        p = p->next;
      }     
    }    
};

//************************************************************************
//**     Przykładowa aplikacja testująca utworzoną klasę TsingleList    **
//************************************************************************

main()
{
  TdoubleList dl;
  TlistElement * p1, * p2, * p;
  int i;
  
// tworzymy dwadzieścia elementów z pseudolosowymi kluczami od 0 do 99

  srand((unsigned)time(NULL));
  
  for(i = 1; i <= 20; i++)
  {
    p = new TlistElement;
    p->key = rand() % 100;
    dl.push_front(p);
  }

  dl.showKeys();
  
// wyszukujemy dwa najmniejsze elementy

  dl.find2min(p1,p2);
  
  cout << "\nmin1 = " << p1->key
       << "\nmin2 = " << p2->key << endl << endl; 

// usuwamy z listy i z pamięci oba znalezione elementy

  delete dl.erase(p1);
  delete dl.erase(p2);

  dl.showKeys();

  cout << endl << endl; 
  system("PAUSE");
}

32 21 58 35 4 85 81 48 62 9 57 16 83 45 56 28 72 91 69 96

min1 = 4
min2 = 9

32 21 58 35 85 81 48 62 57 16 83 45 56 28 72 91 69 96

Podsumowanie funkcji składowych klasy TdoubleList

Funkcja krótki opis
size() Zwraca liczbę elementów przechowywanych na liście.
push_front(p) Umieszcza element p na początku listy i zwraca jego adres.
push_back(p) Umieszcza element p na końcu listy i zwraca jego adres.
insert(p1,p2) Dodaje element p1 za elementem p2 i zwraca adres p1.
pop_front() Pobiera element z początku listy.
pop_back() Pobiera element z końca listy.
erase(p) Usuwa z listy element p i zwraca adres usuniętego elementu.
index(n) Zwraca n-ty element listy. Elementy numerujemy od 1.
showKeys() Wyświetla kolejno klucze wszystkich elementów listy.
find2min(p1,p2) Wyszukuje dwa najmniejsze elementy i zwraca ich adresy do p1 i p2

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2024 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe