Usuwanie z listy duplikatów


Tematy pokrewne   Podrozdziały
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
  Usuwanie duplikatów z listy posortowanej
Zadanie

Problem

Usunąć z listy wszystkie duplikaty.

 

 

Zadanie można rozwiązać w sposób następujący. Jeśli lista nie jest pusta, rozpoczynamy przeglądanie od pierwszego elementu. Nazwijmy go elementem bieżącym. Dla każdego kolejnego elementu bieżącego przechodzimy listę wzdłuż jego następników. Jeśli natrafimy na element, który w polu data zawiera tę samą daną co element bieżący, to usuwamy ten element i kontynuujemy przeglądanie. Po przeglądnięciu całej listy zostaną z niej usunięte wszystkie duplikaty elementu bieżącego. Operację kontynuujemy z następnym elementem bieżącym, aż wykorzystamy wszystkie elementy listy. Algorytm ma klasę złożoności obliczeniowej O(n2), gdzie n oznacza liczbę elementów listy.


Algorytm usuwania duplikatów z listy jednokierunkowej

Wejście
head  –  adres pierwszego elementu listy
Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:
p,r  –  wskaźniki elementu listy
pc  – wskaźnik elementu bieżącego
Lista kroków:
K01: pchead; ; jako element bieżący przyjmujemy pierwszy element listy
K02: Dopóki pc ≠ nil, wykonuj K03...K11  
K03:     ppc ; zawsze będziemy testowali następnik
K04:     Dopóki (pnext) ≠ nil, wykonuj K05...K10 ; dopóki istnieje następnik
K05:         Jeśli ((pnext)→data) ≠ (pcdata), to idź do K10 ; sprawdzamy, czy jest duplikatem
K06:         r ← (pnext) ; zapamiętujemy adres następnika
K07:         (pnext) ← (r→next) ; wyłączamy następnik z listy
K08:         Usuń z pamięci element o adresie r ; zwalniamy pamięć zajętą przez element
K09:         Kontynuuj pętlę z kroku K04  
K10:         p ← (pnext) ; przesuwamy się do następnika
K11     pc ← (pcnext) ; kolejny element bieżący
K12: Zakończ  

 

Lazarus
procedure l_unigue(head : PslistEl);
var
  p,pc,r : PslistEl;
begin
  pc := head;
  while pc <> nil do
  begin
    p := pc;
    while p^.next <> nil do
      if p^.next^.data = pc^.data then
      begin
        r := p^.next;
        p^.next := r^.next;
        dispose(r);
      end
      else p := p^.next;
    pc := pc^.next;
  end;
end;
Code::Blocks
void l_unique(slistEl * head)
{
  slistEl * p, * pc, * r;
  pc = head;
  while(pc)
  {
    p = pc;
    while(p->next)
      if(p->next->data == pc->data)
      {
        r = p->next;
        p->next = r->next;
        delete r;
      }
      else p = p->next;
    pc = pc->next;
  }
}
Free Basic
Sub l_unique(head As slistEl Ptr)
  Dim As slistEl Ptr p, pc, r
  pc = head
  While pc
    p = pc
    While p->next
      If p->next->data = pc->data Then
        r = p->next
        p->next = r->next
        Delete r
      Else
        p = p->next
      End If
    Wend
    pc = pc->next
  Wend
End Sub

 

Algorytm usuwania duplikatów z listy dwukierunkowej

Wejście

L  –  zmienna obsługująca listę dwukierunkową
Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:
p  –  wskaźniki elementu listy
pc  – wskaźnik elementu bieżącego
Lista kroków:
K01: pcL.head; ; jako element bieżący przyjmujemy pierwszy element listy
K02: Dopóki pc ≠ nil, wykonuj K03...K06  
K03:     ppc ; zawsze będziemy testowali następnik
K04:     Dopóki (pnext) ≠ nil, wykonuj K05 ; dopóki istnieje następnik
K05:         Jeśli ((pnext)→data) ≠ (pcdata), to l_remove(L,(pnext))
        inaczej p ← (pnext)
; jeśli następnik jest duplikatem, usuwamy go
; inaczej przesuwamy się do kolejnego elementu listy
K06     pc ← (pcnext) ; kolejny element bieżący
K07: Zakończ  

 

Lazarus
procedure l_unigue(var L : dlistVar);
var
  p,pc : PdlistEl;
begin
  pc := head;
  while pc <> nil do
  begin
    p := pc;
    while p^.next <> nil do
      if p^.next^.data = pc^.data then
        l_remove(L,p^.next)
      else
        p := p^.next;
    pc := pc^.next;
  end;
end;
Code::Blocks
void l_unique(dlistVar & L)
{
  dlistEl * p, * pc;
  pc = L.head;
  while(pc)
  {
    p = pc;
    while(p->next)
      if(p->next->data == pc->data)
        l_remove(L,p->next);
      else
        p = p->next;
    pc = pc->next;
  }
}
Free Basic
Sub l_unique(ByRef L As dlistVar)
  Dim As dlistEl Ptr p, pc
  pc = L.head
  While pc
    p = pc
    While p->next
      If p->next->data = pc->data Then
        l_remove(L,p->next)
      Else
        p = p->next
      End If
    Wend
    pc = pc->next
  Wend
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ę o długości 40 elementów, które zawierają losowo litery od A do Z. Następnie usuwa z niej wszystkie duplikaty. Program wykorzystuje obiekt listy jednokierunkowej.

 

Lazarus
// Usuwanie duplikatów z listy jednokierunkowej
// Data: 20.02.2012
// (C)2012 mgr Jerzy Wałaszek
//---------------------------------------------

program slist_unique;

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

// Usuwa duplikaty z listy
//------------------------
procedure slist.unique();
var
  p,pc,r : PslistEl;
begin
  pc := head;
  while pc <> nil do
  begin
    p := pc;
    while p^.next <> nil do
      if p^.next^.data = pc^.data then
      begin
        r := p^.next;
        p^.next := r^.next;
        dispose(r);
      end
      else p := p^.next;
    pc := pc^.next;
  end;
end;

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

var
  L : slist;    // obiekt listy jednokierunkowej
  i : integer;
begin
  randomize;    // inicjujemy generator pseudolosowy

  L.init;       // inicjujemy obiekt

  for i := 1 to 40 do L.push_front(char(65 + random(26)));
  L.printl;
  L.unique;
  L.printl; 
  L.destroy;
end.
Code::Blocks
// Usuwanie duplikatów z listy jednokierunkowej
// Data: 20.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 unique();
};

// 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()
{
  unsigned i;
  slistEl * p = head;

  cout << size() << " : ";
  for(i = 1; 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; // zapamiętujemy początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element z pamięci
  }
}

// Usuwa duplikaty z listy
//------------------------
void slist::unique()
{
  slistEl * p, * pc, * r;
  pc = head;
  while(pc)
  {
    p = pc;
    while(p->next)
      if(p->next->data == pc->data)
      {
        r = p->next;
        p->next = r->next;
        delete r;
      }
      else p = p->next;
    pc = pc->next;
  }
}

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

int main()
{
  slist L;
  int i;

  srand(time(NULL));

  for(i = 0; i < 40; i++) L.push_front(65 + rand() % 26);
  L.printl();
  L.unique();
  L.printl();

  return 0;
}
Free Basic
' Usuwanie duplikatów z listy jednokierunkowej
' Data: 20.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 unique()
End Type

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

Dim L As slist
Dim i As Integer

Randomize

For i = 1 To 40
  L.push_front(Chr(65 + Int(Rnd() * 26)))
Next
L.printl()
L.unique()
L.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

' Usuwa duplikaty z listy
'------------------------
Sub slist.unique()
  Dim As slistEl Ptr p, pc, r
  pc = head
  While pc
    p = pc
    While p->next
      If p->next->data = pc->data Then
        r = p->next
        p->next = r->next
        Delete r
      Else
        p = p->next
      End If
    Wend
    pc = pc->next
  Wend
End Sub
Wyniki
40 : ZUCDFARPEXJJZQJXEMLGXRXOOSAQRPVWJLWRYTVP
21 : ZUCDFARPEXJQMLGOSVWYT

 

Usuwanie duplikatów z listy posortowanej

Jeśli lista jest posortowana, to duplikaty sąsiadują ze sobą. W takim przypadku nie musimy dla każdego kolejnego elementu przeglądać listy do końca. Postępujemy w sposób następujący:

Rozpoczynamy od pierwszego elementu listy. Dopóki jego następnik jest duplikatem, usuwamy go z listy, po czym przechodzimy do następnika i całą procedurę powtarzamy, aż do osiągnięcia końca listy.

Ten algorytm posiada liniową klasę złożoności obliczeniowej O(n).

 

Algorytm usuwania duplikatów z posortowanej listy jednokierunkowej

Wejście

head  –  adres początku listy. Lista musi być posortowana.
Wyjście:

lista, na której każda wartość danych jest reprezentowana tylko jeden raz

Elementy pomocnicze:
p,r  –  wskaźniki elementu listy
Lista kroków:
K01: phead ; rozpoczynamy od pierwszego elementu listy
K02: Dopóki (p ≠ nil) (pnext) ≠ nil, wykonuj K03...K08 ; dopóki istnieje element i jego następnik
K03:     Jeśli (pdata) ≠ ((pnext)→data), to idź do K08 ; sprawdzamy, czy następnik jest duplikatem
K04:     r ← (pnext) ; jeśli tak, usuwamy go
K05:     (pnext) ← (rnext)  
K06     Usuń element o adresie r  
K07:     Kontynuuj pętlę z kroku K02  
K08:     p ← (pnext) ; jeśli nie, przechodzimy do następnika
K09: Zakończ  

 

Lazarus
procedure l_unique(head : PslistEl);
var
  p,r : PslistEl;
begin
  p := head;
  while (p <> nil) and (p^.next <> nil) do
    if p^.data = p^.next^.data then
    begin
      r := p^.next;
      p^.next := r^.next;
      dispose(r);
    end
    else p := p^.next;
end;
Code::Blocks
void l_unique(slistEl * head)
{
  slistEl * p, * r;
  p = head;
  while(p && p->next)
    if(p->data == p->next->data)
    {
      r = p->next;
      p->next = r->next;
      delete r;
    }
    else p = p->next;
}
Free Basic
Sub l_unique(head As slistEl Ptr)
  Dim As slistEl Ptr p, r
  p = head
  While (p <> 0) AndAlso (p->next <> 0)
    If p->data = p->next->data Then
      r = p->next
      p->next = r->next
      Delete r
    Else
      p = p->next
    End If
  Wend
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 uporządkowaną listę o długości 70 elementów, które zawierają losową ilość liter od A do Z. Następnie usuwa z niej wszystkie duplikaty. Program wykorzystuje obiekt listy jednokierunkowej.

 

Lazarus
// Usuwanie duplikatów z uporządkowanej listy jednokierunkowej
// Data: 20.02.2012
// (C)2012 mgr Jerzy Wałaszek
//------------------------------------------------------------

program slist_unique;

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

// Usuwa duplikaty z listy
//------------------------
procedure slist.unique();
var
  p,r : PslistEl;
begin
  p := head;
  while (p <> nil) and (p^.next <> nil) do
    if p^.data = p^.next^.data then
    begin
      r := p^.next;
      p^.next := r^.next;
      dispose(r);
    end
    else p := p^.next;
end;

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

var
  L   : slist;    // obiekt listy jednokierunkowej
  i,c : integer;
  z   : char;
begin
  randomize;    // inicjujemy generator pseudolosowy

  L.init;       // inicjujemy obiekt

  // tworzymy listę uporządkowaną

  z := 'Z'; c := 1 + random(5);
  for i := 1 to 70 do
  begin
    L.push_front(char(z));
    dec(c);
    if c = 0 then
    begin
      if z = 'A' then
        c := 70
      else
      begin
        dec(z);
        c := 1 + random(5);
      end;
    end;
  end;
  L.printl;
  L.unique;
  L.printl;
  L.destroy;
end.
Code::Blocks
// Usuwanie duplikatów z uporządkowanej listy jednokierunkowej
// Data: 20.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 unique();
};

// 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()
{
  unsigned i;
  slistEl * p = head;

  cout << size() << " : ";
  for(i = 1; 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; // zapamiętujemy początek

  if(p)
  {
    head = p->next;   // nowy początek
    delete p;         // usuń element z pamięci
  }
}

// Usuwa duplikaty z listy
//------------------------
void slist::unique()
{
  slistEl * p, * r;
  p = head;
  while(p && p->next)
    if(p->data == p->next->data)
    {
      r = p->next;
      p->next = r->next;
      delete r;
    }
    else p = p->next;
}

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

int main()
{
  slist L;     // obiekt listy jednokierunkowej
  int i,c;
  char z;

  srand(time(NULL));  // inicjujemy generator pseudolosowy

  // tworzymy listę uporządkowaną

  z = 'Z'; c = 1 + rand() % 5;
  for(i = 0; i < 70; i++)
  {
    L.push_front(char(z));
    c--;
    if(!c)
    {
      if(z == 'A')
        c = 70;
      else
      {
        z--;
        c = 1 + rand() % 5;
      }
    }
  }
  L.printl();
  L.unique();
  L.printl();

  return 0;
}
Free Basic
' Usuwanie duplikatów z uporządkowanej listy jednokierunkowej
' Data: 20.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 unique()
End Type

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

Dim L As slist    ' obiekt listy jednokierunkowej
Dim As Integer i,c,z

Randomize         ' inicjujemy generator pseudolosowy

' tworzymy listę uporządkowaną

z = Asc("Z"): c = 1 + Int(Rnd * 5)
For i = 1 To 70
  L.push_front(Chr(z))
  c -= 1
  If c = 0 Then
    If z = Asc("A") Then
      c = 70
    Else
      z -= 1
      c = 1 + Int(Rnd * 5)
    End If
  End If
Next
L.printl()
L.unique()
L.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

' Usuwa duplikaty z listy
'------------------------
Sub slist.unique()
  Dim As slistEl Ptr p, r
  p = head
  While (p <> 0) AndAlso (p->next <> 0)
    If p->data = p->next->data Then
      r = p->next
      p->next = r->next
      Delete r
    Else
      p = p->next
    End If
  Wend
End Sub
Wyniki
70 : EEEEFFFGGGGGHHHIIIJJJKKKLMMMMMNOOOOOPPQQRRRRSSSSSTTTTTUVVVVWWXXXXYYZZZ
22 : EFGHIJKLMNOPQRSTUVWXYZ

 

Zadanie

  1. Napisz podobny program dla listy dwukierunkowej
  2. Zaproponuj podobny algorytm dla listy cyklicznej. Napisz odpowiedni program.

 

 


   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