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

©2019 mgr Jerzy Wałaszek
I LO w Tarnowie

Scalanie dwóch list posortowanych

SPIS TREŚCI
Tematy pomocnicze

Problem

Należy posortować rosnąco elementy listy względem zawartości ich pól danych.

Rozwiązanie

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(log n), 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:

h 1, h 2  –  adresy początków scalanych list
h  –  adres pustej listy

Wyjście:

listy wskazywane przez h 1 i h 2 zostaną scalone w listę wskazywaną przez h.

Zmienne pomocnicze:

p  –  wskaźnik elementów listy h 3

Lista kroków:

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

Pascal
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;
C++
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);
}
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

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 tworzy dwie listy uporządkowane i scala je w jedną listę uporządkowaną. Program wykorzystuje obiekt listy jednokierunkowej.
Pascal
// Scalanie dwóch posortowanych list jednokierunkowych
// Data: 25.02.2012
// (C)2019 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.
C++
// Scalanie dwóch posortowanych list jednokierunkowych
// Data: 25.02.2012
// (C)2019 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;
}
Basic
' Scalanie dwóch posortowanych list jednokierunkowych
' Data: 25.02.2012
' (C)2019 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
Wynik:
30 : AAAAAAAAAAAAAAAAAAAAAABBCDEEFF
40 : BCCDDDEFGHHIIIJJJKKLMMNNOOOPQRSSSTTTUUUV

70 : AAAAAAAAAAAAAAAAAAAAAABBBCCCDDDDEEEFFFGHHIIIJJJKKLMMNNOOOPQRSSSTTTUUUV
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
©2019 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.