Algorytmy i Struktury Danych - Scalanie dwóch list posortowanych

Zadanie rozwiązujemy przy pomocy przeglądania liniowego, usuwania pierwszych elementów oraz wstawiania na koniec listy. Algorytm porównuje cyklicznie pierwsze elementy scalanych list i usuwa z nich element mniejszy, który następnie wstawia na koniec listy wynikowej. W ten sposób elementy będą posortowane rosnąco na liście wynikowej. Przeglądanie list scalanych trwa do momentu, aż w jednej z nich (lub w obu jednocześnie) skończą się elementy. W takim przypadku na koniec listy wynikowej zostają dopisane pozostałe elementy tej listy scalanej, która je posiada.

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

Wejście:

h₁, h₂ : adresy początków scalanych list.
h : adres pustej listy, na którą trafią połączone listy h₁ i h₂.

Wyjście:

Listy wskazywane przez h₁ i h₂ zostaną scalone w listę wskazywaną przez h.

Elementy pomocnicze:

p : wskaźnik ostatniego elementu listy h.
l_pop_front(L) : usuwa pierwszy element listy L.
l_push_front(L, v) : wstawia na początek listy L element o wartości v.

Lista kroków:

l_merge(h₁, h₂, h)

K01: l_push_front(h, 0) ; wstaw na listę h fałszywy element
K02: p ← h ; p wskazuje fałszywy element listy h
K03: Dopóki h₁ ≠ nil  h₂ ≠ nil, ; dopóki scalane listy obie nie są puste, 
     wykonuj kroki K04…K10 ; scalamy ich elementy w pętli
K04:   Jeśli h₁→data > h₂→data, ; wybieramy mniejszy element
       to idź do kroku K08 ; z początków list h₁, h₂
K05:   p→next ← h₁ ; wstawiamy go na koniec listy hK06:   h₁ ← h₁→next ; wybrany element usuwamy z jego listy
K07:   Idź do kroku K10
K08:   p→next ← h₂K09:   h₂ ← h₂→next
K10:   p ← p→next ; przechodzimy do dodanego elementu, 
       ; czyli do ostatniego elementu listy h
K11: Jeśli h₁ ≠ nil, ; do końca h dodajemy końcówkę listy h₁, 
     to p→next ← h₁         h₁ ← nil
K12: Jeśli h₂ ≠ nil, ; do końca h dodajemy końcówkę listy h₂, 
     to p→next ← h₂         h₂ ← nil
K13: l_pop_front(h) ; usuwamy z początku h fałszywy element
K14: Zakończ

Pascal

procedure l_merge(var h1, h2, h : PSLel);
var
  p : PSLel;
begin
  l_push_front(h, 0); // fałszywy element
  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;
  if h1 <> nil then
  begin
    p^.next := h1;
    h1 := nil;
  end;
  if h2 <> nil then
  begin
    p^.next := h2;
    h2 := nil;
  end;
  l_pop_front(h); // fałszywy element
end;

C++

void l_merge(SLel * & h1, 
             SLel * & h2, 
             SLel * & h)
{
  SLel * 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;
  }
  if(h1)
  {
    p->next = h1;
    h1 = NULL;
  }
  if(h2)
  {
    p->next = h2;
    h2 = NULL;
  }
  l_pop_front(h);
}

Basic

Sub l_merge(ByRef h1 As SLel Ptr, _
            ByRef h2 As SLel Ptr, _
            ByRef h As SLel Ptr)
  Dim p As SLel 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
  If h1 <> 0 Then
    p->next = h1
    h1 = 0
  End If
  If h2 <> 0 Then
    p->next = h2
    h2 = 0
  End If
  l_pop_front(h)
End Sub

Python (dodatek)

# klasa elementu listy
#---------------------
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
#-----------------------------
class SLvar:


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


    # Dodaje nowy element na początek
    def l_push_front(self, v):
        p = SLel(v)
        p.next = self.head
        self.head = p


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next
            p = None


    # łączy listy posortowane
    def l_merge(self, h1, h2):
        self.l_push_front(0)
        p = self.head
        while h1.head and h2.head:
            if h1.head.data > h2.head.data:
                p.next = h2.head
                h2.head = h2.head.next
            else:
                p.next = h1.head
                h1.head = h1.head.next
            p = p.next
        if h1.head:
            p.next = h1.head
            h1.head = None
        if h2.head:
            p.next = h2.head
            h2.head = None
        self.l_pop_front()

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)2020 mgr Jerzy Wałaszek
//----------------------------------------------------

program slist_merge;

// Typ elementów listy
//--------------------
type
  PSLel = ^SLel;

  SLel =  record
    next  : PSLel;
    Data: char;
  end;

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

  SLvar = object
    public
      head : PSLel;  // początek listy

      constructor init;
      destructor destroy;
      function   l_len : cardinal;
      procedure  l_print;
      procedure  l_push_front(v : char);
      procedure  l_pop_front;
      procedure  l_merge (var h1, h2 : SLvar);
  end;

//------------------------
// Metody obiektu SLvar
//------------------------

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

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

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

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

// Procedura dołączania na początek listy
//---------------------------------------
procedure SLvar.l_push_front(v : char);
var
  p : PSLel;
begin
  new(p);
  p^.next := head;
  p^.Data:= v;
  head    := p;
end;

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

// Scala dwie obce listy
//----------------------
procedure SLvar.l_merge(var h1, h2 : SLvar);
var
  p : PSLel;
begin
  l_push_front(#0);
  p := head;
  while(h1.head <> nil) and (h2.head <> nil) do
  begin
    if h1.head^.data > h2.head^.data then
    begin
      p^.next := h2.head;
      h2.head := h2.head^.next;
    end
    else
    begin
      p^.next := h1.head;
      h1.head := h1.head^.next;
    end;
    p := p^.next;
  end;
  if h1.head <> nil then
  begin
    p^.next := h1.head;
    h1.head := nil;
  end;
  if h2.head <> nil then
  begin
    p^.next := h2.head;
    h2.head := nil;
  end;
  l_pop_front();
end;

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

var
  L1, L2, L : SLvar; // listy jednokierunkowe
  c, i : integer;
  z   : char;

begin
  Randomize;
  L1.init;       // inicjujemy obiekty
  L2.init;
  L.init;
  c := 1+random(2);
  z := char(78+random(13));
  for i := 1 to 20 do
  begin
    L1.l_push_front(z);
    dec(c);
    if c = 0 then
    begin
      c := 1+random(2);
      if z > 'A' then dec(z);
    end;
  end;
  L1.l_print;
  c := 1+random (2);
  z := char(78+random(13));
  for i := 1 to 30 do
  begin
    L2.l_push_front(z);
    dec(c);
    if c = 0 then
    begin
      c := 1+random(3);
      if z > 'A' then dec(z);
    end;
  end;
  L2.l_print;
  writeln;
  L.l_merge(L1, L2);
  L.l_print;
  L.destroy;
end.

C++

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

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

using namespace std;

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

// Definicja typu obiektowego SLvar
//------------------------------------

class SLvar
{
  public:
    SLel * head;

    SLvar();  // konstruktor
    ~SLvar(); // destruktor
    unsigned l_len();
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    void l_merge(SLvar & l1, SLvar & l2);
};

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

// Destruktor listy
//-----------------
SLvar::~SLvar()
{
  while(head) l_pop_front();
}

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

// Procedura wyświetla zawartość elementów listy
//----------------------------------------------
void SLvar::l_print()
{
  SLel * p;

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

// Procedura dołączania na początek listy
//---------------------------------------
void SLvar::l_push_front(char v)
{
  SLel * p;

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

// Procedura usuwa pierwszy element
//---------------------------------
void SLvar::l_pop_front()
{
  SLel * p = head;

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

// Scala dwie obce listy
//----------------------
void SLvar::l_merge(SLvar & h1, 
                       SLvar & h2)
{
  SLel * p;
  l_push_front(0);
  p = head;
  while(h1.head && h2.head)
  {
    if(h1.head->data > h2.head->data)
    {
      p->next = h2.head;
      h2.head = h2.head->next;
    }
    else
    {
      p->next = h1.head;
      h1.head = h1.head->next;
    }
    p = p->next;
  }
  if(h1.head)
  {
    p->next = h1.head;
    h1.head = NULL;
  }
  if(h2.head)
  {
    p->next = h2.head;
    h2.head = NULL;
  }
  l_pop_front();
}

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

int main()
{
  SLvar L1, L2, L; // listy jednokierunkowe
  int c, i;
  char z;

  srand(time(NULL));

  c = 1+rand()%2;
  z = 78+rand()%13;

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

  L1.l_print();

  c = 1+rand()%2;
  z = 78+rand()%13;

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

  cout << endl;

  L.l_merge(L1, L2);
  L.l_print();

  return 0;
}

Basic

' Scalanie dwóch posortowanych list jednokierunkowych
' Data: 25.02.2012
' (C)2020 mgr Jerzy Wałaszek
'----------------------------------------------------

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

' Typ obiektowy slist
'------------------------------
Type slistvAR
  head As SLel Ptr
 
  Declare Constructor()
  Declare Destructor()
  Declare Sub l_print()
  Declare Function l_len() As UInteger
  Declare Sub l_push_front(v As String)
  Declare Sub l_pop_front()
  Declare Sub l_merge(ByRef h1 As SLvar, _
                      ByRef h2 As SLvar)
End Type

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

Dim As SLvar L1, L2, L  ' listy jednokierunkowe
Dim As Integer c, i, z

Randomize
c = 1+Int(Rnd()*2)
z = 78+Int(Rnd()*13)
For i = 1 To 20
  L1.l_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.l_print()
c = 1+Int(Rnd()*2)
z = 78+Int(Rnd()*13)
For i = 1 To 30
  L2.l_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.l_print()
Print
L.l_merge(L1, L2)
L.l_print()
End

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

' Destruktor listy
'-----------------
Destructor SLvar()
  While head
    l_pop_front()
  Wend
End Destructor

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

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

  Dim c As UInteger
  Dim p As SLel Ptr = head

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

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

  Dim p As SLel Ptr

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

' Procedura usuwa pierwszy element
'---------------------------------
Sub SLvar.l_pop_front()

  Dim p As SLel 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 SLvar.l_merge(ByRef h1 As SLvar, _
                     ByRef h2 As SLvar)
  Dim p As SLel Ptr
  l_push_front(Chr(0))
  p = head
  while(h1.head <> 0) AndAlso (h2.head <> 0)
    If h1.head->data > h2.head->data Then
      p->next = h2.head
      h2.head = h2.head->next
    Else
      p->next = h1.head
      h1.head = h1.head->next
    End If
    p = p->next
  Wend
  If h1.head <> 0 Then
    p->next = h1.head
    h1.head = 0
  End If
  If h2.head <> 0 Then
    p->next = h2.head
    h2.head = 0
  End If
  l_pop_front()
End Sub

Python (dodatek)

# Scalanie dwóch posortowanych
# list jednokierunkowych
# Data: 25.05.2024
# (C)2024 mgr Jerzy Wałaszek
# -----------------------------

import random


# klasa elementu listy
# ---------------------
class SLel:


    def __init__(self, data):
        self.next = None
        self.data = data


# klasa listy jednokierunkowej
# -----------------------------
class SLvar:


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


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


    # oblicza liczbę elementów listy
    def l_len(self):
        c = 0
        p = self.head
        while p:
            c += 1
            p = p.next
        return c


    # Wyświetla zawartość listy
    def l_print(self):
        print(self.l_len(), ": ",
              sep="", 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 = SLel(v)
        p.next = self.head
        self.head = p


    # Usuwa element z początku
    def l_pop_front(self):
        p = self.head
        if p:
            self.head = p.next


    # Scala dwie obce listy
    def l_merge(self, h1, h2):
        self.l_push_front(0)
        p = self.head
        while h1.head and h2.head:
            if h1.head.data > h2.head.data:
                p.next = h2.head
                h2.head = h2.head.next
            else:
                p.next = h1.head
                h1.head = h1.head.next
            p = p.next
        if h1.head:
            p.next = h1.head
            h1.head = None
        if h2.head:
            p.next = h2.head
            h2.head = None
        self.l_pop_front()


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

# listy jednokierunkowe
sl1 = SLvar()
sl2 = SLvar()
sl = SLvar()
c = random.randrange(1, 3)
z = random.randrange(78, 91)
for i in range(20):
    sl1.l_push_front(chr(z))
    c -= 1
    if not c:
        c = random.randrange(1, 3)
        if z > ord('A'):
            z -= 1
sl1.l_print()
c = random.randrange(1, 3)
z = random.randrange(78, 91)
for i in range(30):
    sl2.l_push_front(chr(z))
    c -= 1
    if not c:
        c = random.randrange(1, 3)
        if z > ord('A'):
            z -= 1
sl2.l_print()
print()
sl.l_merge(sl1, sl2)
sl.l_print()

Wynik:

20: DDEFFGGHIIJJKLLMMNOO
30: CDDEFGHHIJJKLMNNOOPPQRRSSTTUVV

50: CDDDDEEFFFGGGHHHIIIJJJJKKLLLMMMNNNOOOOPPQRRSSTTUVV

do podrozdziału do 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.
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.

Scalanie dwóch list posortowanych

Problem

Rozwiązanie

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

l_merge(h₁, h₂, h)

Przykładowe programy

Scalanie dwóch list posortowanych

Problem

Rozwiązanie

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

l_merge(h1, h2, h)

Przykładowe programy

l_merge(h₁, h₂, h)