Podział listy jednokierunkowej na dwie listy


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

Daną listę jednokierunkową podzielić na dwie podlisty tak, aby w każdej z podlist było połowę elementów listy głównej.

 

 

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
h1,h2   adresy pustych list
Wyjście:

lista wskazywana przez h zostanie podzielona na dwie podlisty wskazywane przez h1 i h2. Podlisty będą miały połowę elementów pierwotnej listy.

Elementy pomocnicze:
p1,p2  –  wskaźniki elementów list
s  – selektor listy, zmienna logiczna
Lista kroków:
K01: s ← false ; selektor wybiera raz jedną, a raz drugą listę h1 i h2
K02: l_push_front(h1,0) ; na liście h1 umieszczamy fałszywy element
K03: l_push_front(h2,0) ; na liście h2 umieszczamy fałszywy element
K04: p1 h1 ; wskaźnik elementów pierwszej listy docelowej
K05: p2h2 ; wskaźnik elementów drugiej listy docelowej
K06: Dopóki h ≠ nil, wykonuj K07...K15  
K07:     Jeśli s = true, to idź do K11 ; zgodnie z selektorem wybieramy listę docelową
K08:     (p1next) ← h ; dodajemy pierwszy element h do h1
K09:     p1 ← (p1next) ; przemieszczamy wskaźnik na dodany element
K10:     Idź do K13  
K11:     (p2next) ← h ; dodajemy pierwszy element h do h2
K12:     p2 ← (p2next) ; przemieszczamy wskaźnik na dodany element
K13:     h ← (hnext) ; usuwamy z h pierwszy element, który już do niej nie należy
K14:     s ← ¬ s ; zmieniamy wartość selektora na przeciwną
K15: (p1next) ← nil ; zamykamy listę h2
K16: (p2next) ← nil ; zamykamy listę h3
K17: l_pop_front(h1) ; usuwamy fałszywe elementy z początku obu list h1 i h2
K18: l_pop_front(h2)  
K19: Zakończ  

 

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

Fałszywe elementy ułatwiają konstrukcję algorytmu – dzięki nim listy nie są puste i można ich adresy przypisać bezpośrednio wskaźnikom p1 i p2. 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.

 

Lazarus
procedure l_split(var h,h1,h2 : PslistEl);
var
  p1,p2 : PslistEl;
  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;
Code::Blocks
void l_split(slistEl * & h, slistEl * & h1, slistEl * & h2)
{
  slistEl * 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);  
}
Free Basic
Sub l_split(ByRef h As slistEl Ptr, ByRef h1 As slistEl Ptr, ByRef h2 As slistEl Ptr)
  Dim As slistEl 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

 

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 listę zawierającą kolejne znaki alfabetu od A do Z, a następnie rozdziela ją na dwie podlisty. Program wykorzystuje obiekt listy jednokierunkowej.

 

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

program slist_split;

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

// Dokonuje podziału listy
//------------------------
procedure slist.split(var l1,l2 : slist);
var
  p1,p2 : PslistEl;
  s : boolean;
begin
  s := false;
  l1.push_front(#0);
  l2.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.pop_front();
  l2.pop_front();
end;

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

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

begin
  L.init;           // inicjujemy obiekty
  L1.init;
  L2.init;

  for i := 'Z' downto 'A' do L.push_front(i);
  L.printl;
  writeln;

  L.split(L1,L2);   // dzielimy L, wynik w L1 i L2
  L1.printl;        // wyświetlamy L1
  L2.printl;        // wyświetlamy L2

  L1.destroy;       // usuwamy listy z pamięci
  L2.destroy;
end.
Code::Blocks
// Podział listy jednokierunkowej na dwie podlisty
// Data: 25.02.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------------------------

#include <iostream>

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

// Dokonuje podziału listy
//------------------------
void slist::split(slist & l1, slist & l2)
{
  slistEl * p1, * p2;
  bool s = false;
  l1.push_front(0);
  l2.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.pop_front();
  l2.pop_front();
}

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

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

  for(i = 'Z'; i >= 'A'; i--) L.push_front(i);
  L.printl();
  cout << endl;

  L.split(L1,L2);   // dzielimy L, wynik w L1 i L2
  L1.printl();      // wyświetlamy L1
  L2.printl();      // wyświetlamy L2

  return 0;
}
Free Basic
' Podział listy jednokierunkowej na dwie podlisty
' 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 split(ByRef l1 As slist, ByRef l2 As slist)
End Type

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

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

For i = Asc("Z") To Asc("A") Step - 1
  L.push_front(Chr(i))
Next
L.printl()
Print

L.split(L1,L2)     ' dzielimy L, wynik w L1 i L2
L1.printl()        ' wyświetlamy L1
L2.printl()        ' wyświetlamy L2

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

' Dokonuje podziału listy
'------------------------
Sub slist.split(ByRef l1 As slist, ByRef l2 As slist)
  Dim As slistEl Ptr p1,p2
  Dim As Integer s = 0
  l1.push_front(Chr(0))
  l2.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.pop_front()
  l2.pop_front()
End Sub
Wyniki
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

 

 


   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