Algorytmy i Struktury Danych - Podział listy jednokierunkowej na dwie listy

Problem rozwiązujemy przez wybieranie z początku rozdzielanej listy kolejnych elementów i wprowadzanie ich raz na jedną, a raz na drugą listę docelową.

Algorytm podziału listy jednokierunkowej na dwie podlisty

Wejście:

h : adres pierwszego elementu dzielonej listy.
h₁, h₂ : adresy pustych list.

Wyjście:

Lista wskazywana przez h zostanie podzielona na dwie podlisty wskazywane przez h₁ i h₂. Podlisty będą zawierały połowę elementów pierwotnej listy.

Elementy pomocnicze:

p₁, p₂ : wskaźniki elementów list.
s : selektor listy, zmienna logiczna.
l_pop_front(x) : usuwa element z początku listy x.
l_push_front(x, e) : wstawia element e na początek listy x.

Lista kroków:

l_split(h, h₁, h₂)

K01: s ← false ; selektor wybiera raz jedną, a raz drugą listę h₁ i h₂K02: l_push_front(h₁, 0) ; na liście h₁ umieszczamy fałszywy element
K03: l_push_front(h₂, 0) ; na liście h₂ umieszczamy fałszywy element
K04: p₁← h₁ ; wskaźnik elementów pierwszej listy docelowej
K05: p₂ ← h₂; wskaźnik elementów drugiej listy docelowej
K06: Dopóki h ≠ nil, 
     wykonuj kroki K07…K14
K07:   Jeśli s = true, ; zgodnie z selektorem wybieramy listę docelową
       to idź do kroku K11
K08:   p₁→next ← h ; dodajemy pierwszy element listy h do h₁K09:   p₁ ← p₁→next ; przemieszczamy wskaźnik na dodany element
K10:   Idź do kroku K13
K11:   p₂→next ← h ; dodajemy pierwszy element listy h do h₂K12:   p₂ ← p₂→next ; przemieszczamy wskaźnik na dodany element
K13:   h ← h→next ; usuwamy z listy h pierwszy element, 
       ; który już do niej nie należy
K14:   s ← ¬ s ; zmieniamy wartość selektora na przeciwną
K15: p₁→next ← nil ; zamykamy listę h₁K16: p₂→next ← nil ; zamykamy listę h₂K17: l_pop_front(h₁) ; usuwamy fałszywe elementy z początkuK18: l_pop_front(h₂) ; obu list h₁ i h₂
K19: Zakończ

Uwaga: Jeśli liczba elementów pierwotnej listy h jest nieparzysta, to w h₁ powstanie lista dłuższa o 1 element od listy h₂.

Fałszywe elementy ułatwiają konstrukcję algorytmu – dzięki nim listy nie są puste i można ich adresy przypisać bezpośrednio wskaźnikom p₁ i p₂. W przeciwnym razie musielibyśmy modyfikować algorytm dla pierwszego wstawianego na listę elementu. A tak zawsze dodajemy jedynie następnik elementu, który już na liście się znajduje. Na końcu algorytmu po prostu usuwamy dodane elementy i otrzymujemy właściwe listy.

Pascal

procedure l_split(var h, h1, h2 : PSLel);
var
  p1, p2 : PSLel;
  s : boolean;
begin
  s := false;
  l_push_front(h1, 0);
  l_push_front(h2, 0);
  p1 := h1;
  p2 := h2;
  while h <> nil do
  begin
    if s then
    begin
      p2^.next := h;
      p2 := p2^.next;
    end
    else
    begin
      p1^.next := h;
      p1 := p1^.next;
    end;
    h := h^.next;
    s := not s;
  end;
  p1^.next := nil;
  p2^.next := nil;
  l_pop_front(h1);
  l_pop_front(h2);
end;

C++

void l_split(SLel * & h, 
             SLel * & h1, 
             SLel * & h2)
{
  SLel * p1, * p2;
  bool s = false;
  l_push_front(h1, 0);
  l_push_front(h2, 0);
  p1 = h1;
  p2 = h2;
  while(h)
  {
    if(s)
    {
      p2->next = h;
      p2 = p2->next;
    }
    else
    {
      p1->next = h;
      p1 = p1->next;
    }
    h = h->next;
    s = !s;
  }
  p1->next = p2->next = NULL;
  l_pop_front(h1);
  l_pop_front(h2); 
}

Basic

Sub l_split(ByRef  h As SLel Ptr, _
            ByRef h1 As SLel Ptr, _
            ByRef h2 As SLel Ptr)
  Dim As SLel Ptr p1, p2
  Dim As Integer s = 0
  l_push_front(h1, 0)
  l_push_front(h2, 0)
  p1 = h1
  p2 = h2
  While h
    If s = 0 Then
      p1->next = h
      p1 = p1->next
    Else
      p2->next = h
      p2 = p2->next
    End If
    h = h->next
    s = s Xor 1
  Wend
  p1->next = 0
  p2->next = 0
  l_pop_front(h1)
  l_pop_front(h2)
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


    # Rozdziela na dwie listy
    def l_split(self, h1, h2):
        s = False
        h1.l_push_front(0)
        h2.l_push_front(0)
        p1 = h1.head
        p2 = h2.head
        while self.head:
            if s:
                p2.next = self.head
                p2 = p2.next
            else:
                p1.next = self.head
                p1 = p1.next
            self.head = self.head.next
            s = not s
        p1.next = None
        p2.next = None
        h1.l_pop_front()
        h2.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 listę zawierającą kolejne znaki alfabetu od A do Z, a następnie rozdziela ją na dwie podlisty. Program wykorzystuje obiekt listy jednokierunkowej.

Pascal

// Podział listy jednokierunkowej na dwie podlisty
// Data: 25.02.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------------

program slist_split;

// 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_split(var l1, l2 : SLvar);
  end;

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

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

// Dokonuje podziału listy
//------------------------
procedure SLvar.l_split(var l1, l2 : SLvar);
var
  p1, p2 : PSLel;
  s : boolean;
begin
  s := false;
  l1.l_push_front(#0);
  l2.l_push_front(#0);
  p1 := l1.head;
  p2 := l2.head;
  while head <> nil do
  begin
    if s then
    begin
      p2^.next := head;
      p2 := p2^.next;
    end
    else
    begin
      p1^.next := head;
      p1 := p1^.next;
    end;
    head := head^.next;
    s := not s;
  end;
  p1^.next := nil;
  p2^.next := nil;
  l1.l_pop_front();
  l2.l_pop_front();
end;

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

var
  L, L1, L2 : SLvar; // obiekty list
  i : char;

begin
  L.init; // inicjujemy obiekty
  L1.init;
  L2.init;
  for i := 'Z' downto 'A' do
    L.l_push_front(i);
  L.l_print;
  writeln;
  L.l_split(L1, L2); // dzielimy L, wynik w L1 i L2
  L1.l_print; // wyświetlamy L1
  L2.l_print; // wyświetlamy L2
  L1.destroy; // usuwamy listy z pamięci
  L2.destroy;
end.

C++

// Podział listy jednokierunkowej na dwie podlisty
// Data: 25.02.2012
// (C)2020 mgr Jerzy Wałaszek
//------------------------------------------------

#include <iostream>

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_split(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;
  }
}

// Dokonuje podziału listy
//------------------------
void SLvar::l_split(SLvar & l1, SLvar & l2)
{
  SLel * p1, * p2;
  bool s = false;
  l1.l_push_front(0);
  l2.l_push_front(0);
  p1 = l1.head;
  p2 = l2.head;
  while(head)
  {
    if(s)
    {
      p2->next = head;
      p2 = p2->next;
    }
    else
    {
      p1->next = head;
      p1 = p1->next;
    }
    head = head->next;
    s = !s;
  }
  p1->next = p2->next = NULL;
  l1.l_pop_front();
  l2.l_pop_front();
}

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

int main()
{
  SLvar L, L1, L2; // obiekty list jednokierunkowych
  char i;
  for(i = 'Z'; i >= 'A'; i--)
    L.l_push_front(i);
  L.l_print();
  cout << endl;
  L.l_split(L1, L2); // dzielimy L, wynik w L1 i L2
  L1.l_print(); // wyświetlamy L1
  L2.l_print(); // wyświetlamy L2

  return 0;
}

Basic

' Podział listy jednokierunkowej na dwie podlisty
' 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 SLvar
  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_split(ByRef l1 As SLvar, _
                      ByRef l2 As SLvar)
End Type

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

Dim As SLvar L, L1, L2 ' obiekty list jednokierunkowych
Dim i As Integer

For i = Asc ("Z") To Asc ("A") Step-1
  L.l_push_front(Chr(i))
Next
L.l_print()
Print
L.l_split(L1, L2) ' dzielimy L, wynik w L1 i L2
L1.l_print() ' wyświetlamy L1
L2.l_print() ' wyświetlamy L2
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

' Dokonuje podziału listy
'------------------------
Sub SLvar.l_split(ByRef l1 As SLvar, _
                     ByRef l2 As SLvar)
  Dim As SLel Ptr p1, p2
  Dim As Integer s = 0
  l1.l_push_front(Chr(0))
  l2.l_push_front(Chr(0))
  p1 = l1.head
  p2 = l2.head
  While head
    If s = 0 Then
      p1->next = head
      p1 = p1->next
    Else
      p2->next = head
      p2 = p2->next
    End If
    head = head->next
    s = s Xor 1
  Wend
  p1->next = 0
  p2->next = 0
  l1.l_pop_front()
  l2.l_pop_front()
End Sub

Python (dodatek)

# Podział listy jednokierunkowej
# na dwie podlisty
# Data: 22.05.2024
# (C)2024 mgr Jerzy Wałaszek
# -------------------------------


# 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


    # Dokonuje podziału listy
    def l_split(self, x1, x2):
        s = False
        x1.l_push_front("0")
        x2.l_push_front("0")
        p1 = x1.head
        p2 = x2.head
        while self.head:
            if s:
                p2.next = self.head
                p2 = p2.next
            else:
                p1.next = self.head
                p1 = p1.next
            self.head = self.head.next
            s = not s
        p1.next = None
        p2.next = None
        x1.l_pop_front()
        x2.l_pop_front()


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

# obiekty list jednokierunkowych
sl  = SLvar()
sl1 = SLvar()
sl2 = SLvar()
for i in reversed(range(26)):
    sl.l_push_front(chr(65 + i))
sl.l_print()
print()
# dzielimy L, wynik w L1 i L2
sl.l_split(sl1, sl2)
sl1.l_print()  # wyświetlamy L1
sl2.l_print()  # wyświetlamy L2

Wynik:

26 : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

13 : A C E G I K M O Q S U W Y
13 : B D F H J L N P R T V X Z

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.

Podział listy jednokierunkowej na dwie listy

Problem

Rozwiązanie