Algorytmy i Struktury Danych - Usuwanie duplikatów z listy

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(n²), 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: pc ← head ; jako element bieżący przyjmujemy
     ; pierwszy element listy
K02: Dopóki pc ≠ nil, 
     wykonuj kroki K03…K11
K03:   p ← pc ; zawsze będziemy testowali następnik
K04:   Dopóki p→next ≠ nil, ; dopóki istnieje
       wykonuj kroki K05…K10  ; następnik
K05:     Jeśli p→next→data ≠ pc→data, ; sprawdzamy, 
         to idź do kroku K10 ; czy jest duplikatem
K06:     r ← p→next ; zapamiętujemy adres następnika
K07:     p→next ← r→next ; wyłączamy następnik z listy
K08:     Usuń z pamięci element o adresie r
K09:     Kontynuuj pętlę z kroku K04
K10:     p ← p→next ; przesuwamy się do następnika
K11:   pc ← pc→next ; kolejny element bieżący
K12: Zakończ

Pascal

// dla listy jednokierunkowej
procedure l_unigue(head : PSLel);
var
  p, pc, r : PSLel;
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;

C++

// dla listy jednokierunkowej
void l_unique(SLel * head)
{
  SLel * 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;
  }
}

Basic

' dla listy jednokierunkowej
Sub l_unique(head As SLel Ptr)
  Dim As SLel 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

Python (dodatek)

# dla listy jednokierunkowej

# 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

    # usuwa duplikaty
    def l_unique(self):
        pc = self.head
        while pc:
            p = pc
            while p.next:
                if p.next.data == pc.data:
                    r = p.next
                    p.next = r.next
                    r = None
                else:
                    p = p.next
        pc = pc.next

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.
l_remove(L, e) : usuwa element e z listy.

Lista kroków:

K01: pc ← L.head ; jako element bieżący przyjmujemy
     ; pierwszy element listy
K02: Dopóki pc ≠ nil, 
     wykonuj kroki K03…K06
K03:   p ← pc ; zawsze będziemy testowali następnik
K04:   Dopóki p→next ≠ nil, ; dopóki istnieje następnik
       wykonuj krok K05
K05:     Jeśli p→next→data ≠ pc→data, ; jeśli następnik
         to l_remove(L, p→next) ; jest duplikatem, usuwamy go
         inaczej p ← p→next ; inaczej przesuwamy się do
         ; kolejnego elementu listy
K06:   pc ← pc→next ; kolejny element bieżący
K07: Zakończ

Pascal

// dla listy dwukierunkowej
procedure l_unigue(var L : DLvar);
var
  p, pc : PDLel;
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;

C++

// dla listy dwukierunkowej
void l_unique(DLvar & L)
{
  DLel * 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;
  }
}

Basic

' dla listy dwukierunkowej
Sub l_unique(ByRef L As DLvar)
  Dim As DLel 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

Python (dodatek)

# dla listy dwukierunkowej


# klasa elementu listy
class DLel:


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


# klasa listy
class DLvar:


    def __init__(self):
        self.head = None
        self.tail = None
        self.count = 0

    # usuwa e z listy
    def l_remove(self, e):
        self.count -= 1
        if e.prev:
            e.prev.next = e.next
        else:
            self.head = e.next
        if e.next:
            e.next.prev = e.prev
        else:
            self.tail = e.prev
        e = None

    # usuwa duplikaty
    def l_unique(self):
        pc = self.head
        while pc:
            p = pc
            while p.next:
                if p.next.data == pc.data:
                    self.l_remove(p.next)
                else:
                    p = p.next
            pc = pc.next

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ę 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.

Pascal

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

program slist_unique;

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

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

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

  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_unique;
  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ść 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;

// Usuwa duplikaty z listy
//------------------------
procedure SLvar.l_unique();
var
  p, pc, r : PSLel;
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 : SLvar; // lista
  i : integer;
begin
  randomize;

  L.init;       // inicjujemy obiekt

  for i := 1 to 40 do
    L.l_push_front(char(65+random(26)));
  L.l_print;
  L.l_unique;
  L.l_print;
  L.destroy;
end.

C++

// Usuwanie duplikatów z listy jednokierunkowej
// Data: 20.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_unique();
};

// 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; // zapamiętujemy początek

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

// Usuwa duplikaty z listy
//------------------------
void SLvar::l_unique()
{
  SLel * 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()
{
  SLvar L;
  int i;

  srand (time(NULL));

  for(i = 0; i < 40; i++)
    L.l_push_front(65+rand()% 26);
  L.l_print();
  L.l_unique();
  L.l_print();

  return 0;
}

Basic

' Usuwanie duplikatów z listy jednokierunkowej
' Data: 20.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_unique()
End Type

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

Dim L As SLvar
Dim i As Integer

Randomize

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

' Usuwa duplikaty z listy
'------------------------
Sub SLvar.l_unique()
  Dim As SLel 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

Python (dodatek)

# Usuwanie duplikatów z listy jednokierunkowej
# Data: 18.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


    # Usuwa duplikaty z listy
    def l_unique(self):
        pc = self.head
        while pc:
            p = pc
            while p.next:
                if p.next.data == pc.data:
                    r = p.next
                    p.next = r.next
                else:
                    p = p.next
            pc = pc.next


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

sl = SLvar()
for i in range(40):
    sl.l_push_front(chr(random.randrange(65, 91)))
sl.l_print()
sl.l_unique()
sl.l_print()

Wynik:

40 : ZUCDFARPEXJJZQJXEMLGXRXOOSAQRPVWJLWRYTVP
21 : ZUCDFARPEXJQMLGOSVWYT

do podrozdziału do strony

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, w której każda wartość danych jest reprezentowana tylko jeden raz.

Elementy pomocnicze:

p, r : wskaźniki elementu listy.

Lista kroków:

K01: p ← head ; rozpoczynamy od pierwszego elementu listy
K02: Dopóki p ≠ nil  p→next ≠ nil, ; dopóki istnieje
     wykonuj kroki K03…K08 ; element i jego następnik
K03:   Jeśli p→data ≠ p→next→data, ; sprawdzamy, 
       to idź do kroku K08 ; czy następnik jest duplikatem
K04:   r ← p→next ; jeśli tak, usuwamy go
K05:   p→next ← r→next
K06    Usuń element o adresie r
K07:   Kontynuuj pętlę z kroku K02
K08:   p ← p→next ; jeśli nie, przechodzimy do następnika
K09: Zakończ

Pascal

procedure l_unique(head : PSLel);
var
  p, r : PSLel;
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;

C++

void l_unique(SLel * head)
{
  SLel * 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;
}

Basic

Sub l_unique(head As SLel Ptr)
  Dim As SLel 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

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

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

    # Usuwanie duplikatów z listy
    # posortowanej
    def l_unique(self):
        p = self.head
        while p and p.next:
            if p.data == p.next.data:
                r = p.next
                p.next = r.next
                r = None
            else:
                p = p.next

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 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.

Pascal

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

program slist_unique;

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

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

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

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

// Usuwa duplikaty z listy
//------------------------
procedure SLvar.l_unique();
var
  p, r : PSLel;
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   : SLvar; // 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.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.l_print;
  L.l_unique;
  L.l_print;
  L.destroy;
end.

C++

// Usuwanie duplikatów z uporządkowanej
// listy jednokierunkowej
// Data: 20.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_unique();
};

// 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; // zapamiętujemy początek

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

// Usuwa duplikaty z listy
//------------------------
void SLvar::l_unique()
{
  SLel * 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()
{
  SLvar 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.l_push_front(char(z));
    c--;
    if(!c)
    {
      if(z == 'A')
        c = 70;
      else
      {
        z--;
        c = 1+rand()%5;
      }
    }
  }
  L.l_print();
  L.l_unique();
  L.l_print();

  return 0;
}

Basic

' Usuwanie duplikatów z uporządkowanej
' listy jednokierunkowej
' Data: 20.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 SLvar
'-----------------------
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_unique()
End Type

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

Dim L As SLvar ' 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.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.l_print()
L.l_unique()
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

' Usuwa duplikaty z listy
'------------------------
Sub SLvar.l_unique()
  Dim As SLel 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

Python (dodatek)

# Usuwanie duplikatów z uporządkowanej
# listy jednokierunkowej
# Data: 18.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



    # Usuwa duplikaty z listy
    def l_unique(self):
        p = self.head
        while p and p.next:
            if p.data == p.next.data:
                r = p.next
                p.next = r.next
                r = None
            else:
                p = p.next


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

# obiekt listy jednokierunkowej
sl = SLvar()
# tworzymy listę uporządkowaną
z = ord('Z')
c = random.randrange(1, 6)
for i in range(70):
    sl.l_push_front(chr(z))
    c -= 1
    if not c:
        if z == ord('A'):
            c = 70
        else:
            z -= 1
            c = random.randrange(1, 6)
sl.l_print()
sl.l_unique()
sl.l_print()

Wynik:

70 : EEEEFFFGGGGGHHHIIIJJJKKKLMMMMMNOOOOOPPQQRRRRSSSSSTTTTTUVVVVWWXXXXYYZZZ
22 : EFGHIJKLMNOPQRSTUVWXYZ

do podrozdziału do strony

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

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.

Usuwanie duplikatów z listy

Problem

Rozwiązanie

Algorytm usuwania duplikatów z listy jednokierunkowej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm usuwania duplikatów z listy dwukierunkowej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Usuwanie duplikatów z listy posortowanej

Algorytm usuwania duplikatów z posortowanej listy jednokierunkowej

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Zadania