Scalanie dwóch list posortowanych


Tematy pokrewne
Listy
Podstawowe pojęcia dotyczące list
Reprezentacja list w pamięci komputera
Operacje na listach jednokierunkowych
Operacje na listach dwukierunkowych
Operacje na listach cyklicznych jednokierunkowych
Liniowe przeszukiwanie listy
Przeszukiwanie liniowe z wartownikiem listy dwukierunkowej
Wyszukiwanie największego/najmniejszego elementu listy
Zliczanie elementów listy
Usuwanie z listy duplikatów
Odwracanie listy jednokierunkowej
Podział listy jednokierunkowej na dwie listy
Scalanie dwóch list posortowanych
Sortowanie listy jednokierunkowej przez scalanie
Sortowanie przez wstawianie z wykorzystaniem listy jednokierunkowej
Sortowanie szybkie listy dwukierunkowej
Samoorganizujące się listy
Haszowanie z wykorzystaniem list jednokierunkowych
Zbiory rozłączne – implementacja listowa

Problem

Posortować rosnąco elementy listy względem zawartości ich pól danych.

 

 

Problem rozwiązujemy rekurencyjnie. Jeśli dana lista posiada więcej niż jeden element, to dzielimy ją na dwie podlisty, każdą z podlist sortujemy tym samym algorytmem, po czym obie listy scalamy w jedną listę. W efekcie lista zostanie posortowana.

Algorytm ma klasę złożoności obliczeniowej O(nlogn), jednakże wymaga dosyć dużo dodatkowej pamięci na tworzone listy pośrednie – O(n), zatem nie nadaje się do sortowania zbyt dużych list,


Algorytm scalania dwóch jednokierunkowych list posortowanych w jednokierunkową listę posortowaną

Wejście
h1,h2  –  adresy początków scalanych list
h  –  adres pustej listy
Wyjście:

listy wskazywane przez h1 i h2 zostaną scalone w listę wskazywaną przez h.

Elementy pomocnicze:
p  –  wskaźnik elementów listy h3
Lista kroków:
K01: l_push_front(h3,0) ; wstaw na listę h3 fałszywy element
K02: ph ; p wskazuje fałszywy element listy h
K03: Dopóki (h1 ≠ nil) (h2 ≠ nil), wykonuj K04...K10 ; dopóki scalane listy obie nie są puste, scalamy ich elementy w pętli
K04:     Jeśli (h1data) > (h2data), to idź do K08 ; wybieramy mniejszy element
K05:     (pnext) ← h1 ; wstawiamy go na koniec listy h3
K06:     h1 ← (h1next) ; wybrany element usuwamy z jego listy
K07:     Idź do K10  
K08:     (pnext) ← h2  
K09:     h2 ← (h2next)  
K10:     p ← (pnext) ; przechodzimy do dodanego elementu
K11 Dopóki h1 ≠ nil, wykonuj K12...K14 ; do h3 dodajemy końcówkę listy h1, jeśli pozostały elementy
K12     (pnext) ← h1  
K13:     h1 ← (h1next)  
K14     p ← (pnext)  
K15: Dopóki h2 ≠ nil, wykonuj K16...K18 ; do h3 dodajemy końcówkę listy h2, jeśli pozostały elementy
K16:     (pnext) ← h2  
K17:     h2 ← (h2next)  
K18:     p ← (pnext)  
K19: l_pop_front(h) ; usuwamy z h fałszywy element
K20: Zakończ  

 

Lazarus
procedure l_merge(var h1,h2,h : PslistEl);
var
  p : PslistEl;
begin
  l_push_front(h,0);
  p := h;
  while (h1 <> nil) and (h2 <> nil) do
  begin
    if h1^.data > h2^.data then
    begin
      p^.next := h2;
      h2 := h2^.next;
    end
    else
    begin
      p^.next := h1;
      h1 := h1^.next;
    end;
    p := p^.next;
  end;
  while h1 <> nil do
  begin
    p^.next := h1;
    h1 := h1^.next;
    p := p^.next;
  end;
  while h2 <> nil do
  begin
    p^.next := h2;
    h2 := h2^.next;
    p := p^.next;
  end;
  l_pop_front(h);
end;
Code::Blocks
void l_merge(slistEl * & h1, slistEl * & h2, slistEl * & h)
{
  slistEl * p;
  l_push_front(h,0);
  p = h;
  while(h1 && h2)
  {
    if(h1->data > h2->data)
    {
      p->next = h2;
      h2 = h2->next;
    }
    else
    {
      p->next = h1;
      h1 = h1->next;
    }
    p = p->next;
  }
  while(h1)
  {
    p->next = h1;
    h1 = h1->next;
    p  = p->next;
  }
  while(h2)
  {
    p->next = h2;
    h2 = h2->next;
    p  = p->next;
  }
  l_pop_front(h);
}
Free Basic
Sub l_merge(ByRef h1 As slistEl Ptr, ByRef h2 As slistEl Ptr, ByRef h As slistEl Ptr)
  Dim p As slistEl Ptr
  l_push_front(h,0)
  p = h
  While (h1 <> 0) AndAlso (h2 <> 0)
    If h1->data > h2->data Then
      p->next = h2
      h2 = h2->next
    Else
      p->next = h1
      h1 = h1->next
    End If
    p = p->next
  Wend
  While h1
    p->next = h1
    h1 = h1->next
    p  = p->next
  Wend
  While h2
    p->next = h2
    h2 = h2->next
    p  = p->next
  Wend
  l_pop_front(h)
End Sub

 

Program

Ważne:

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 tworzy dwie listy uporządkowane i scala je w jedną listę uporządkowaną. Program wykorzystuje obiekt listy jednokierunkowej.

 

Lazarus
// Scalanie dwóch posortowanych list jednokierunkowych
// Data: 25.02.2012
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------------------------

program slist_merge;

// Typ elementów listy
//--------------------
type
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slist
//---------------------------------

  slist = object
    public
      head : PslistEl;  // początek listy

      constructor init;
      destructor destroy;
      function   size : cardinal;
      procedure  printl;
      procedure  push_front(v : char);
      procedure  pop_front;
      procedure  merge(var l1,l2 : slist);
  end;

//---------------------
// Metody obiektu slist
//---------------------

// Konstruktor - inicjuje pole head
//---------------------------------
constructor slist.init;
begin
  head := nil;
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor slist.destroy;
begin
  while head <> nil do pop_front;
end;

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function slist.size : cardinal;
var
  c : cardinal;
  p : PslistEl;
begin
  c := 0;
  p := head;
  while p <> nil do
  begin
    inc(c);
    p := p^.next;
  end;
  size := c;
end;

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
procedure slist.printl;
var
  p : PslistEl;
begin
  write(size,' : ');
  p := head;
  while p <> nil do
  begin
    write(p^.data);
    p := p^.next;
  end;
  writeln;
end;

// Procedura dołączania na początek listy
//---------------------------------------
procedure slist.push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slist.pop_front;
var
  p : PslistEl;
begin
  p := head;
  if p <> nil then
  begin
    head := p^.next;
    dispose(p);
  end;
end;

// Scala dwie obce listy
//----------------------
procedure slist.merge(var l1,l2 : slist);
var
  p : PslistEl;
begin
  push_front(#0);
  p := head;
  while (l1.head <> nil) and (l2.head <> nil) do
  begin
    if l1.head^.data > l2.head^.data then
    begin
      p^.next := l2.head;
      l2.head := l2.head^.next;
    end
    else
    begin
      p^.next := l1.head;
      l1.head := l1.head^.next;
    end;
    p := p^.next;
  end;
  while l1.head <> nil do
  begin
    p^.next := l1.head;
    l1.head := l1.head^.next;
    p := p^.next;
  end;
  while l2.head <> nil do
  begin
    p^.next := l2.head;
    l2.head := l2.head^.next;
    p := p^.next;
  end;
  pop_front();
end;

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

var
  L1,L2,L3 : slist; // obiekty list jednokierunkowych
  c,i : integer;
  z   : char;

begin
  Randomize;
  L1.init;       // inicjujemy obiekty
  L2.init;
  L3.init;

  c := 1 + random(2);
  z := char(65 + random(26));

  for i := 1 to 30 do
  begin
    L1.push_front(z);
    dec(c);
    if c = 0 then
    begin
      c := 1 + random(2);
      if z > 'A' then dec(z);
    end;
  end;

  L1.printl;

  c := 1 + random(2);
  z := char(65 + random(26));

  for i := 1 to 40 do
  begin
    L2.push_front(z);
    dec(c);
    if c = 0 then
    begin
      c := 1 + random(3);
      if z > 'A' then dec(z);
    end;
  end;
  L2.printl;

  writeln;

  L3.merge(L1,L2);
  L3.printl;

  L3.destroy;
end.
Code::Blocks
// Scalanie dwóch posortowanych list jednokierunkowych
// Data: 25.02.2012
// (C)2012 mgr Jerzy Wałaszek
//----------------------------------------------------

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ elementów listy
//--------------------
struct slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slist
//---------------------------------

class slist
{
  public:
    slistEl * head;

    slist();  // konstruktor
    ~slist(); // destruktor
    unsigned size();
    void printl();
    void push_front(char v);
    void pop_front();
    void merge(slist & l1, slist & l2);
};

// Konstruktor listy
//------------------
slist::slist()
{
  head = NULL;
}

// Destruktor listy
//-----------------
slist::~slist()
{
  while(head) pop_front();
}

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
unsigned slist::size()
{
  unsigned c = 0;
  slistEl * p = head;
  while(p)
  {
    c++;
    p = p->next;
  }
  return c;
}

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void slist::printl()
{
  slistEl * p;

  cout << size() << " : ";
  for(p = head; p; p = p->next) cout << p->data;
  cout << endl;
}

// Procedura dołączania na początek listy
//---------------------------------------
void slist::push_front(char v)
{
  slistEl * p;

  p = new slistEl;
  p->next = head;
  p->data = v;
  head = p;
}

// Procedura usuwa pierwszy element
//---------------------------------
void slist::pop_front()
{
  slistEl * p = head;

  if(p)
  {
    head = p->next;
    delete p;
  }
}

// Scala dwie obce listy
//----------------------
void slist::merge(slist & l1, slist & l2)
{
  slistEl * p;
  push_front(0);
  p = head;
  while(l1.head && l2.head)
  {
    if(l1.head->data > l2.head->data)
    {
      p->next = l2.head;
      l2.head = l2.head->next;
    }
    else
    {
      p->next = l1.head;
      l1.head = l1.head->next;
    }
    p = p->next;
  }
  while(l1.head)
  {
    p->next = l1.head;
    l1.head = l1.head->next;
    p  = p->next;
  }
  while(l2.head)
  {
    p->next = l2.head;
    l2.head = l2.head->next;
    p  = p->next;
  }
  pop_front();
}

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

int main()
{
  slist L1,L2,L3; // obiekty list jednokierunkowych
  int c,i;
  char z;

  srand(time(NULL));

  c = 1 + rand() % 2;
  z = 65 + rand() % 26;

  for(i = 0; i < 30; i++)
  {
    L1.push_front(z);
    if(!--c)
    {
      c = 1 + rand() % 2;
      if(z > 'A') z--;
    }
  }

  L1.printl();

  c = 1 + rand() % 2;
  z = 65 + rand() % 26;

  for(i = 0; i < 40; i++)
  {
    L2.push_front(z);
    if(!--c)
    {
      c = 1 + rand() % 2;
      if(z > 'A') z--;
    }
  }
  L2.printl();

  cout << endl;

  L3.merge(L1,L2);
  L3.printl();

  return 0;
}
Free Basic
' Scalanie dwóch posortowanych list jednokierunkowych
' Data: 25.02.2012
' (C)2012 mgr Jerzy Wałaszek
'----------------------------------------------------

' Typ elementów listy
'--------------------
Type slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slist
'------------------------------
Type slist
  head As slistEl Ptr
  
  Declare Constructor()
  Declare Destructor()
  Declare Sub printl()
  Declare Function size() As UInteger
  Declare Sub push_front(v As String)
  Declare Sub pop_front()
  Declare Sub merge(ByRef l1 As slist, ByRef l2 As slist)
End Type

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

Dim As slist L1,L2,L3  ' obiekty list jednokierunkowych
Dim As Integer c,i,z

Randomize

c = 1 + Int(Rnd() * 2)
z = 65 + Int(Rnd() * 26)

For i = 1 To 30
  L1.push_front(Chr(z))
  c -= 1
  If c = 0 Then
    c = 1 + Int(Rnd() * 2)
    If z > 65 then z -= 1
  End If
Next

L1.printl()

c = 1 + Int(Rnd() * 2)
z = 65 + Int(Rnd() * 26)

For i = 1 To 40
  L2.push_front(Chr(z))
  c -= 1
  If c = 0 Then
    c = 1 + Int(Rnd() * 2)
    If z > 65 then z -= 1
  End If
Next

L2.printl()

Print

L3.merge(L1,L2)

L3.printl()

End

' Konstruktor listy
'-------------------
Constructor slist()
  head = 0
End Constructor

' Destruktor listy
'-----------------
Destructor slist()
  While head
    pop_front()
  Wend
End Destructor

' Procedura wyświetla zawartość elementów listy
'----------------------------------------------
Sub slist.printl()
  
  Dim p As slistEl Ptr = head
  
  Print size();" : ";
  While p
    Print p->Data;
    p = p->next
  Wend
  Print
End Sub

' Funkcja oblicza liczbę elementów listy
'---------------------------------------
Function slist.size() As UInteger

  Dim c As UInteger
  Dim p As slistEl Ptr = head

  c = 0
  While p
    c += 1
    p = p->next
  Wend
  size = c
End Function

' Procedura dołączania na początek listy
'---------------------------------------
Sub slist.push_front(v As String)

  Dim p As slistEl Ptr

  p = new slistEl
  p->next = head
  p->data = v
  head = p
End Sub

' Procedura usuwa pierwszy element
'---------------------------------
Sub slist.pop_front()

  Dim p As slistEl Ptr

  p = head      ' zapamiętujemy początek
  If p Then
    head = p->next  ' nowy początek
    Delete p     ' usuń element z pamięci
  End If
End Sub

' Scala dwie obce listy
'----------------------
Sub slist.merge(ByRef l1 As slist, ByRef l2 As slist)
  Dim p As slistEl Ptr
  push_front(Chr(0))
  p = head
  While (l1.head <> 0) AndAlso (l2.head <> 0)
    If l1.head->data > l2.head->data Then
      p->next = l2.head
      l2.head = l2.head->next
    Else
      p->next = l1.head
      l1.head = l1.head->next
    End If
    p = p->next
  Wend
  While l1.head
    p->next = l1.head
    l1.head = l1.head->next
    p  = p->next
  Wend
  While l2.head
    p->next = l2.head
    l2.head = l2.head->next
    p  = p->next
  Wend
  pop_front()
End Sub
Wyniki
30 : AAAAAAAAAAAAAAAAAAAAAABBCDEEFF
40 : BCCDDDEFGHHIIIJJJKKLMMNNOOOPQRSSSTTTUUUV

70 : AAAAAAAAAAAAAAAAAAAAAABBBCCCDDDDEEEFFFGHHIIIJJJKKLMMNNOOOPQRSSSTTTUUUV

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

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