Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Usuwanie duplikatów z listy

SPIS TREŚCI
Tematy pomocnicze
Podrozdziały

Problem

Należy usunąć z listy wszystkie duplikaty.

Rozwiązanie

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 kroki K03…K11
K03:   ppc ; zawsze będziemy testowali następnik
K04:   Dopóki (pnext) ≠ nil, ; dopóki istnieje
       wykonuj kroki K05…K10  ; następnik
K05:     Jeśli ((pnext)→data) ≠ (pcdata), ; sprawdzamy,
         to idź do kroku K10 ; czy jest duplikatem
K06:     r ← (pnext) ; zapamiętujemy adres następnika
K07:     (pnext) ← (rnext) ; wyłączamy następnik z listy
K08:     Usuń z pamięci element o adresie r
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

Pascal
// dla listy jednokierunkowej
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;
C++
// dla listy jednokierunkowej
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;
  }
}
Basic
' dla listy jednokierunkowej
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
Python (dodatek)
# dla listy jednokierunkowej

# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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
                    del r
                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: pcL.head ; jako element bieżący przyjmujemy
                 ; pierwszy element listy
K02: Dopóki pc ≠ nil,
     wykonuj kroki K03…K06
K03:   ppc ; zawsze będziemy testowali następnik
K04:   Dopóki (pnext) ≠ nil, ; dopóki istnieje następnik
       wykonuj krok K05
K05:     Jeśli ((pnext)→data) ≠ (pcdata), ; jeśli następnik
         to l_remove(L,(pnext)) ; jest duplikatem, usuwamy go
         inaczej p ← (pnext) ; inaczej przesuwamy się do
                              ; kolejnego elementu listy
K06:   pc ← (pcnext) ; kolejny element bieżący
K07: Zakończ

Pascal
// dla listy dwukierunkowej
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;
C++
// dla listy dwukierunkowej
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;
  }
}
Basic
' dla listy dwukierunkowej
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
Python (dodatek)
# dla listy dwukierunkowej

# klasa elementu listy
class dlistEl:
    def __init__(self,data):
        self.next = None
        self.prev = None
        self.data = data

# klasa listy
class dlistVar:
    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
        del e

    # 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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slistVar
//------------------------------------

  slistVar = object
    public
      head : PslistEl;  // 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 slistVar
//------------------------

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function slistVar.l_len : cardinal;
var
  c : cardinal;
  p : PslistEl;
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 slistVar.l_print;
var
  p : PslistEl;
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 slistVar.l_push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slistVar.l_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 slistVar.l_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 : slistVar; // 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 slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slistVar
//------------------------------------

class slistVar
{
  public:
    slistEl * head;

    slistVar();  // konstruktor
    ~slistVar(); // destruktor
    unsigned l_len();
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    void l_unique();
};

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

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

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

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

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
void slistVar::l_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 slistVar::l_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()
{
  slistVar 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slist
'------------------------------
Type slistVar
  head As slistEl 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 slistVar
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 slistVar()
  head = 0
End Constructor

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

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

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

  Dim c As UInteger
  Dim p As slistEl 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 slistVar.l_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 slistVar.l_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 slistVar.l_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
Python (dodatek)
# Usuwanie duplikatów z listy jednokierunkowej
# Data: 18.05.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------------------------

import random

# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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 = slistEl(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
            del p
 
    # 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
                    del r
                else:
                    p = p.next
            pc = pc.next

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

L = slistVar()
for i in range(40):
    L.l_push_front(chr(65+random.randrange(26)))
L.l_print()
L.l_unique()
L.l_print()
Wynik:
40 : ZUCDFARPEXJJZQJXEMLGXRXOOSAQRPVWJLWRYTVP
21 : ZUCDFARPEXJQMLGOSVWYT

Na początek:  podrozdziału   strony 

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) obrazek (pnext) ≠ nil, ; dopóki istnieje
     wykonuj kroki K03…K08 ; element i jego następnik
K03:   Jeśli (pdata) ≠ ((pnext)→data), ; sprawdzamy,
       to idź do kroku K08 ; 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

Pascal
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;
C++
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;
}
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
Python (dodatek)
# klasa elementu listy
#---------------------
class slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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
                del r
            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
  PslistEl = ^slistEl;

  slistEl =  record
    next  : PslistEl;
    data  : char;
  end;

// Definicja typu obiektowego slistVar
//------------------------------------

  slistVar = object
    public
      head : PslistEl;  // 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 slistVar
//------------------------

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

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

// Funkcja oblicza liczbę elementów listy
//---------------------------------------
function slistVar.l_len : cardinal;
var
  c : cardinal;
  p : PslistEl;
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 slistVar.l_print;
var
  p : PslistEl;
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 slistVar.l_push_front(v : char);
var
  p : PslistEl;
begin
  new(p);
  p^.next := head;
  p^.data := v;
  head    := p;
end;

// Procedura usuwa pierwszy element
//---------------------------------
procedure slistVar.l_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 slistVar.l_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   : slistVar; // 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 slistEl
{
  slistEl * next;
  char data;
};

// Definicja typu obiektowego slistVar
//------------------------------------

class slistVar
{
  public:
    slistEl * head;

    slistVar();  // konstruktor
    ~slistVar(); // destruktor
    unsigned l_len();
    void l_print();
    void l_push_front(char v);
    void l_pop_front();
    void l_unique();
};

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

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

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

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

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

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

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

// Procedura usuwa pierwszy element
//---------------------------------
void slistVar::l_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 slistVar::l_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()
{
  slistVar 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 slistEl
  next As slistEl Ptr
  data As String * 1
End Type

' Typ obiektowy slistVar
'-----------------------
Type slistVar
  head As slistEl 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 slistVar ' 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 slistVar()
  head = 0
End Constructor

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

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

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

  Dim c As UInteger
  Dim p As slistEl 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 slistVar.l_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 slistVar.l_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 slistVar.l_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
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 slistEl:
    def __init__(self,data):
        self.next = None
        self.data = data

# klasa listy jednokierunkowej
#-----------------------------
class slistVar:

    # 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 = slistEl(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
            del p

    # 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
                del r
            else:
                p = p.next

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

L = slistVar() # obiekt listy jednokierunkowej

# tworzymy listę uporządkowaną

z = ord('Z')
c = 1+random.randrange(5)
for i in range(70):
    L.l_push_front(chr(z))
    c -= 1
    if not c:
        if z == ord('A'):
            c = 70
        else:
            z -= 1
            c = 1+random.randrange(5)
L.l_print()
L.l_unique()
L.l_print()
Wynik:
70 : EEEEFFFGGGGGHHHIIIJJJKKKLMMMMMNOOOOOPPQQRRRRSSSSSTTTTTUVVVVWWXXXXYYZZZ
22 : EFGHIJKLMNOPQRSTUVWXYZ

Na początek:  podrozdziału   strony 

Zadania

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

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2024 mgr Jerzy Wałaszek

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.