Struktury danych

Wprowadzenie

Struktury danych, to po prostu struktury, które mogą przechowywać pewne dane. Innymi słowy używamy ich do przechowywania zestawu powiązanych danych.

W Pythonie istnieją cztery podstawowe struktury danych: lista, krotka, słownik i zbiór. Zobaczymy, jak używać każdą z nich i jak one mogą nam ułatwić życie.

Lista

Lista to struktura, która zawiera uporządkowany zestaw obiektów, czyli na przykład jakąś sekwencję. Łatwo sobie to wyobrazić za pomocą listy zakupów, na której masz zapisane rzeczy do kupienia. Jedyna różnica jest taka, że na liście zakupów zazwyczaj rzeczy wpisuje się jedną pod drugą, zaś w Pythonie rozdziela się przecinkami.

Lista powinna być zawarta w nawiasach kwadratowych, żeby uświadomić Pythonowi, że właśnie o listę nam chodzi. Do stworzonej listy można w dowolnej chwili dodawać lub usuwać elementy, albo ją przeszukiwać. Ponieważ możemy dodawać i usuwać elementy, mówimy, że lista jest zmiennym typem danych.

Szybkie wprowadzenie do obiektów i klas

Mimo, że jak dotąd zwlekałem z omawianiem obiektów i klas, teraz przydałoby się małe wyjaśnienie, żebyś mógł lepiej zrozumieć, o co chodzi z listami. Reszty dowiesz się w odpowiednim rozdziale.

Lista jest przykładem użycia obiektów i klas. Gdy tworzymy zmienną i przypisując jej, powiedzmy, liczbę 5, to można powiedzieć, że tworzymy obiekt i klasy (typu) int.

Klasa może też mieć metody, czyli charakterystyczne funkcje, których można użyć tylko przy operowaniu obiektem danej klasy. Na przykład dla klasy list istnieje metoda append, która pozwala na dopisywanie elementów na końcu listy. Na przykład mojalista.append('rzecz') doda słowo rzecz na koniec lity mojalista. Zauważ, że używaną metodę zapisuje się po kropce.

Klasa może mieć także pola, które są po prostu zmiennymi zdefiniowanymi specjalnie dla danej klasy. Możesz ich używać tylko w odniesieniu do konkretnych obiektów tej klasy. Do pól dostajemy się również za pomocą kropki, na przykład: mojalista.pole.

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: lista.py

# To moja lista zakupów:
lista = ['jabłko', 'mango', 'marchew', 'kiwi']

print 'Mam', len(lista), 'rzeczy do kupienia.'

print 'Te rzeczy to:',
for i in lista:
    print i,

print '\nMuszę jeszcze kupić ryż.'
lista.append('ryż')
print 'Teraz moja lista to:', lista

print 'Posortuję moją listę.'
lista.sort()
print 'Posortowana lista to:', lista

print 'Pierwsza rzecz, jaką muszę kupić, to', lista[0]
rzecz = lista[0]
del lista[0]
print 'Kupiłem', rzecz
print 'Moja lista teraz to:', lista

Rezultat:

$ python lista.py
Mam 4 rzeczy do kupienia.
Te rzeczy to: jabłko mango marchew kiwi

Muszę jeszcze kupić ryż.
Teraz moja lista to: ['jabłko', 'mango', 'marchew', 'kiwi', 'ryż']
Posortuję moją listę.
Posortowana lista to: ['jabłko', 'kiwi', 'mango', 'marchew', 'ryż']
Pierwsza rzecz, jaką muszę kupić, to jabłko
Kupiłem jabłko
Moja lista teraz to: ['kiwi', 'mango', 'marchew', 'ryż']

Jak to działa:

Zmienna lista jest listą zakupów kogoś wybierającego się do sklepu. Przechowujemy tam jedynie słowa oznaczające przedmioty do kupienia, ale tak naprawdę lista może zawierać cokolwiek, nawet liczby czy inne listy.

Użyliśmy też pętli for...in... do przejścia po wsztkich elementach listy. W tym momencie mógłbyś zauważyć, że lista jest sekwencją. Ale sekwencje poznasz trochę później.

Zauważ, że na końcu polecenia print użyliśmy przecinka, aby Python zakończył spacją, a nie przejściem do nowej linii, jak to robi zazwyczaj.

Następnie dodaliśmy obiekt do listy metodą append, po czym sprawdziliśmy, czy to podziałało, po prostu każąc wypisać nową zawartość listy na ekran.

Po tym wszystkim posortowaliśmy listę za pomocą metody sort. Ważne jest to, że wynik powstaje przez przestawianie obiektów wewnątrz tej samej listy. Innymi słowy, żaden nowy obiekt nie zostaje stworzony, zmienia się tylko kolejność elementów na liście, co nazywamy sortowaniem w miejscu.

Zamiast sortowania w miejscu, można by stworzyć nową listę zawierającą te same elementy w innej kolejności. Do wykonania takiej operacji można wykorzystać funkcję sorted:

posortowana = sorted(lista)

Istotna różnica jest taka, że posortowana jest nowym obiektem, a stara lista pozostaje nienaruszona.

Z tego przykładu widać, że lista jest typem zmiennym, czyli obiekty tej klasy można modyfikować. W przypadku innych typów, jak krotka (tuple) czy napis (str), dysponujemy tylko tym drugim sposobem sortowania. Mówimy, że są to typy niezmienne, przez co rozumiemy, że obiekt tej klasy, raz stworzony, nie może być zmieniony.

Gdy kupiliśmy już jakąś rzecz z listy, chcemy tę pozycję usunąć. Używamy do tego polecenia del — chcemy wyrzucić pierwszy element, więc piszemy del lista[0] (pamiętając, że Python zaczyna liczyć od 0).

Jeśli chcesz poznać wszystkie metody dostępne dla klasy list, wpisz help(list).

Krotka

Krotek używamy do zbierania razem obiektów. Pomyśl o nich, jak o listach pozbawionych rozległej funkcjonalności, jaką daje klasa list. Jedną z najważniejszych cech krotek jest ich niezmienność. Nie można ich modyfikować.

Krotkę definiuje się przez wypisanie jej elementów i przedzielenie ich przecinkami. Można opcjonalnie zamknąć krotkę w nawias.

Krotki zazwyczaj używa się w sytuacjach, gdy w wyrażeniu lub funkcji zdefiniowanej przez użytkownika można spokojnie założyć, że zestaw (krotka) danych nie ulegnie zmianie.

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: krotka.py

zoo = ('pyton', 'słoń', 'pingwin') # Pamiętaj, że nawiasy są opcjonalne.
print 'Liczba zwierząt w zoo:', len(zoo)

nowe_zoo = ('małpa', 'wielbłąd', zoo)
print 'Liczba klatek w nowym zoo:', len(nowe_zoo)
print 'Wszystkie zwierzęta w nowym zoo to:', nowe_zoo
print 'Zwierzęta sprowadzone ze starego zoo to:', nowe_zoo[2]
print 'Ostatnim zwierzęciem sprowadzonym ze starego zoo jest', nowe_zoo[2][2]
print 'Liczba zwierząt w nowym zoo:',len(nowe_zoo)-1+len(nowe_zoo[2])

Rezultat:

$ python krotka.py
Liczba zwierząt w zoo: 3
Liczba klatek w nowym zoo: 3
Wszystkie zwierzęta w nowym zoo to: ('małpa', 'wielbłąd', ('pyton', 'słoń', 'pingwin'))
Zwierzęta sprowadzone ze starego zoo to: ('pyton', 'słoń', 'pingwin')
Ostatnim zwierzęciem sprowadzonym ze starego zoo jest pingwin
Liczba zwierząt w nowym zoo: 5

Jak to działa:

Zmienna zoo odnosi się do krotki złożonej ze zwierząt. Jak widać, dzięki funkcji len możemy sprawdzić długość krotki. To dodatkowo pokazuje, że krotka jest sekwencją.

Z powodu zamknięcia starego zoo, przenosimy zwierzęta do nowego. Dlatego też krotka nowe_zoo zawiera kilka zwierząt, które były już tam wcześniej, a także zwierzęta przeniesione ze starego zoo. Wracając do rzeczywistości, zauważ, że krotka w krotce nie traci swojej tożsamości.

Możemy odnieść się do pojedynczego elementu krotki poprzez podanie pozycji tego elementu w nawiasach kwadratowych, zupełnie jak przy listach. Nazywamy to operatorem indeksowania. Uzyskujemy trzeci element w krotce nowe_zoo przez wpisanie nowe_zoo[2] oraz trzeci element w trzecim elemencie tej krotki dzięki nowe_zoo[2][2]. Gdy tylko zrozumiesz, o co tu chodzi, zauważysz, że to bardzo proste.

Nawiasy
Pomimo, że są opcjonalne, wolę jednak zawsze używać nawiasów, aby było oczywiste, że używam krotki, szczególnie, że to zapobiega dwuznaczności. Na przykład, print 1, 2, 3 oraz print (1, 2, 3) mają różne znaczenia. Za pierwszym razem pokażą się trzy cyfry, za drugim krotka (złożona z trzech cyfr).

Krotka pusta lub z 1 elementem
Krotkę pustą tworzy się za pomocą pustej pary nawiasów: pusta = (), zaś krotka z jednoelementowa to już większy problem. Aby ją stworzyć, musisz użyć przecinka po pierwszym (i jedynym) jej elemencie. Dzięki temu Python nie uzna jej po prostu za obiekt w nawiasie. Czyli musisz napisać na przykład samotnik = (2, ), gdy chcesz uzyskać krotkę, w której jest tylko 2.

Uwaga dla programujących w Perlu
Listy w listach nie tracą swojej tożsamości. Nie są one spłaszczane, jak w Perlu. To samo odnosi się do krotki w krotce, krotki w liście, listy w krotce itd. Dla Pythona to po prostu obiekty przechowywane w innym obiekcie, to wszystko.

Słownik

Słownik jest jak książka adresowa, w której możesz znaleźć czyjś adres czy telefon znając jedynie nazwisko tej osoby. W słowniku kojarzymy klucze (nazwy) z wartościami (szczegółami). Zauważ, że klucz musi być unikalny. Nie możesz być pewien, że uzyskałeś właściwe dane, jeżeli nagle znalazłeś w książce telefonicznej dwie osoby o identycznym imieniu i nazwisku.

Dla kluczy możesz użyć tylko niezmiennych obiektów (na przykład ciągów znaków), ale wartości mogą być dowolne. Innymi słowy, to oznacza, że kluczami muszą być proste obiekty.

W słowniku obowiązuje następująca notacja: s = {klucz1 : wartość1, klucz2 : wartość2}. Jak widzisz, między kluczem a wartością jest dwukropek, zaś między parami są przecinki. Wszystko jest zamknięte w nawiasach klamrowych.

Pamiętaj, że pary klucz–wartość w słowniku nie są w żaden sposób posegregowane. Jeżeli chcesz mieć je poukładane w jakimś szczególnym porządku, musisz to zrobić ręcznie. (Ta klasa nie posiada metody sort — przyp. tłum)

Słowniki są obiektami klasy dict.

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: slownik.py

# "ka" to skrót od "k"siążka "a"dresowa

ka = { 'Swaroop'   : '[email protected]',
       'Larry'     : '[email protected]',
       'Matsumoto' : '[email protected]',
       'Spammer'   : '[email protected]'
    }

print "Adres Swaroopa:", ka['Swaroop']

# Usuwanie pary klucz-wartość.
del ka['Spammer']

print '\nKontaktów w książce adresowej jest %d.\n' % len(ka)

for imie, adres in ka.items():
    print '%s ma adres %s' % (imie, adres)

# Dodawanie pary klucz-wartość.
ka['Guido'] = '[email protected]'

if 'Guido' in ka:
    print "\nAdres Guido:", ka['Guido']

Rezultat:

$ python slownik.py
Adres Swaroopa: [email protected]

Kontaktów w książce adresowej jest 3.

Swaroop ma adres [email protected]
Matsumoto ma adres [email protected]
Larry ma adres [email protected]

Adres Guido: [email protected]

Jak to działa:

Tworzymy słownik ka używając już wcześniej omówionej notacji. Następnie docieramy do jednej z wartości używając klucza jako operatora indeksowania, tak jak w listach lub krotkach. Zobacz, jakie to proste.

Możemy usuwać wpisy ze słownika za pomocą starego, dobrego polecenia del — po prostu określamy słownik i klucz, który razem z odpowiednią wartością ma zostać usunięty. Samej wartości nie musimy wcale znać przy tej operacji.

Następnie używamy metody items, która zwraca nam krotki, z której każda składa się z dwóch elementów — pierwszy to klucz, a drugi to wartość. Dzięki for...in... przypisujemy te pary do zmiennych, odpowiednio imie i adres, po czym wypisujemy je w bloku for.

Możemy dodać nową parę klucz–wartość po prostu używając operatora indeksowania do oznaczenia klucza i przypisania mu wartości, tak jak zrobiliśmy to dla Guido w powyższym przykładzie.

Możemy sprawdzić, czy dana para istnieje, za pomocą operatora in.

Jeśli chcesz poznać wszystkie metody dostępne dla klasy słowników, wpisz help(dict).

Argumenty słów kluczowych a słowniki
Tak przy okazji, jeżeli używałeś argumentów słów kluczowych w swoich funkcjach, to już używałeś słowników! Pomyśl — para klucz–wartość jest określona przez ciebie w liście parametrów w definicji funkcji, a gdy ty uzyskujesz dostęp do zmiennych w swojej funkcji, działa to jak używanie klucza przy uzyskiwaniu wartości w słowniku (co w terminologii kompilatora nazywa się tablica symboli).

Sekwencje

Listy, krotki i ciągi znaków to przykłady sekwencji, ale czym są sekwencje i co jest w nich takiego specjalnego?

Główne cechy to to, że posiadają testy zawartości (czyli wyrażenia in i not in) oraz że ich elementy są zindeksowane (ponumerowane), dzięki czemu można uzyskać dostęp osobno do dowolnego z nich.

Wymienione wcześniej trzy typy sekwencji — lista, krotka i ciąg znaków, mogą być dodatkowo pocięte, dzięki czemu możemy uzyskać dostęp do określonej ich części.

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: sekwencja.py

lista = ['jabłko', 'mango', 'marchew', 'kiwi']
imie = 'Swaroop'

# Indeksowanie lub "Subskrypcja".
print 'Rzecz 0 to', lista[0]
print 'Rzecz 1 to', lista[1]
print 'Rzecz 2 to', lista[2]
print 'Rzecz 3 to', lista[3]
print 'Rzecz -1 to', lista[-1]
print 'Rzecz -2 to', lista[-2]
print 'Litera 0 to', imie[0]

# Cięcie listy.
print 'Rzeczy od 1 do 3 to', lista[1:3]
print 'Rzeczy od 2 do końca to', lista[2:]
print 'Rzeczy od 1 do -1 to', lista[1:-1]
print 'Rzeczy od początku do końca to', lista[:]

# Cięcie ciągu znaków.
print 'Litery od 1 do 3 to', imie[1:3]
print 'Litery od 2 do końca to', imie[2:]
print 'Litery od 1 do -1 to', imie[1:-1]
print 'Litery od początku do końca to', imie[:]

Rezultat:

$ python sekwencja.py
Rzecz 0 to jabłko
Rzecz 1 to mango
Rzecz 2 to marchew
Rzecz 3 to kiwi
Rzecz -1 to kiwi
Rzecz -2 to marchew
Litera 0 to S
Rzeczy od 1 do 3 to ['mango', 'marchew']
Rzeczy od 2 do końca to ['marchew', 'kiwi']
Rzeczy od 1 do -1 to ['mango', 'marchew']
Rzeczy od początku do końca to ['jabłko', 'mango', 'marchew', 'kiwi']
Litery od 1 do 3 to wa
Litery od 2 do końca to aroop
Litery od 1 do -1 to waroo
Litery od początku do końca to Swaroop

Jak to działa:

Najpierw używamy indeksów do uzyskania poszczególnych elementów sekwencji. Można to też nazywać subskrypcją. Gdy tylko przy sekwencji podasz numer w nawiasach kwadratowych, uzyskasz element z pozycji, której numer podałeś. Pamiętaj, że Python liczy od 0, dlatego lista[0] to pierwszy element, a lista[3] to czwarty.

Indeks może też być ujemny, wtedy liczenie zaczyna się od końca sekwencji. Dlatego lista[-1] to ostatni element, a lista[-2] to przedostatni.

Operacja cięcia jest wykonywana przez podanie obiektu do pocięcia, a następnie dwóch liczb w nawiasie kwadratowym, przedzielonych dwukropkiem. Zauważ, że to jest bardzo podobne do indeksowania, tylko pamiętaj, że liczby są opcjonalne, ale dwukropek nie.

Pierwsza liczba (przed dwukropkiem) w operacji cięcia oznacza pozycję startową, zaś druga (za dwukropkiem) wyznacza dokąd cięcie ma zostać wykonane. Jeżeli nie ma pierwszej liczby, to Python zacznie ciąć od początku. Gdy nie ma drugiej, to tnie aż do końca. Zauważ, że cięcie zaczyna się równo z pozycją startową, ale kończy się przed pozycją końcową. To znaczy, że pozycja startowa jest zawarta w wyciętym fragmencie, ale pozycja końcowa już nie jest.

W związku z tym, lista[1:3] zwraca elementy 1 i 2, ale nie zwraca już trzeciego, zaś lista[:] zwraca kopię sekwencji.

Możesz także podać trzeci argument, którym jest krok cięcia (domyślnie 1).

>>> lista = ['jabłko', 'mango', 'marchew', 'kiwi']
>>> lista[::1]
['jabłko', 'mango', 'marchew', 'kiwi']
>>> lista[::2]
['jabłko', 'marchew']
>>> lista[::3]
['jabłko', 'kiwi']
>>> lista[::-1]
['kiwi', 'marchew', 'mango', 'jabłko']

Jak widzisz, gdy krok wynosi 2, uzyskujemy elementy numer 0, 2, ..., zaś gdy wynosi 3, uzyskujemy elementy numer 0, 3, ... itd.

Wypróbuj różne kombinacje używając interpretera w czasie rzeczywistym, czyli nie poprzez plik, tylko bezpośrednio go włączając. Najlepsze jest to, że możesz dokładnie to samo robić na każdym typie sekwencji, czy to lista, czy krotka, czy ciąg znaków!

Zbiór

Zbiory to nieuporządkowane zestawy prostych obiektów. Używamy ich, gdy fakt występowania elementu jest istotniejszy niż jego położenie albo ilość powtórzeń.

Zbiory możesz testować pod kątem występowania danego elementu, sprawdzać czy to jest podzbiór innego zbioru, szukać części wspólnej zbiorów i tak dalej.

Przykład:

>>> bri = set(['brazylia', 'rosja', 'indie'])
>>> 'indie' in bri
True
>>> 'usa' in bri
False
>>> bric = bri.copy()
>>> bric.add('chiny')
>>> bric.issuperset(bri)
True
>>> bri.remove('rosja')
>>> bri & bric # ALBO bri.intersection(bric)
set(['brazylia', 'indie'])

Jak to działa:

Ten przykład nie wymaga omawiania, gdyż użyte w nim są jedynie proste techniki matematyczne uczone w szkole. (Jedynie dla tych, którzy nie są zbyt biegli w języku angielskim: set — zbiór, superset — nadzbiór, intersection — przekrój zbiorów (część wspólna zbiorów). — przyp. tłum.)

Odniesienia

Gdy tworzysz obiekt i przypisujesz go do zmiennej, zmienna jedynie odnosi się do tego obiektu, a nie reprezentuje go. Tak, nazwa zmiennej jedynie wskazuje miejsce w pamięci komputera, w którym znajdują się określone dane. Nazywamy to bindowaniem (wiązaniem) nazwy z obiektem.

Właściwie, to nie masz się czym przejmować, ale z odniesieniami może powstać pewien drobny problem, o którym powinieneś wiedzieć.

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: odniesienie.py

print 'Proste Przypisywanie'
lista = ['jabłko', 'mango', 'marchew', 'kiwi']
mojalista = lista # mojalista to tylko inna nazwa dla tej samej zmiennej!

del lista[0] # Kupiłem pierwszą rzecz, więc ją usuwam z listy.

print 'Lista zakupów:', lista
print 'Moja lista:', mojalista
# Obydwie listy będą zawierać dokładnie to samo, czyli trzy pozycje.
# W żadnej z nich nie pojawi się "jabłko", bo dotyczą tego samego obiektu.

print 'Kopiowanie za pomocą pełnego cięcia'
mojalista = lista[:] # Stwórz kopię za pomocą pełnego cięcia...
del mojalista[0] # Usuń pierwszą rzecz...

print 'Lista zakupów:', lista
print 'Moja lista:', mojalista
# Teraz te listy będą się różniły.

Rezultat:

$ python odniesienie.py
Proste Przypisywanie
Lista zakupów: ['mango', 'marchew', 'kiwi']
Moja lista: ['mango', 'marchew', 'kiwi']
Kopiowanie za pomocą pełnego cięcia
Lista zakupów: ['mango', 'marchew', 'kiwi']
Moja lista: ['marchew', 'kiwi']

Jak to działa:

Większość wyjaśniłem już w komentarzach.

Pamiętaj, że jak chcesz zrobić kopię jakiejś złożonej zmiennej (nie prostej, jak ciąg znaków), to musisz użyć operacji pełnego cięcia. Jeżeli zamiast tego po prostu przypiszesz zmiennej inną nazwę, obydwie nazwy będą się odnosić do tego samego obiektu, więc możesz sobie napytać biedy, jak nie będziesz ostrożny.

Uwaga dla programujących w Perlu
Pamiętaj, że przypisanie wyrażenia do listy nie tworzy kopii! Zawsze do skopiowania sekwencji potrzebna jest operacja pełnego cięcia.

Więcej o ciągach znaków

Już wcześniej omówiliśmy dogłębnie ciągi znaków, więc co jeszcze można dodać? Cóż... Czy wiedziałeś, że to też są obiekty i również mają swoje metody, jak na przykład sprawdzanie, czy w danym tekście jest określone słowo?

Wszystkie ciągi znaków, jakie używasz, mają przypisaną klasę str. Pokażę ci teraz kilka ciekawych metod dla tej klasy. Więcej znajdziesz w help(str).

Przykład:

#!/usr/bin/env python
# -*- coding: utf-8 -*-
# Nazwa pliku: str_metody.py

imie = 'Swaroop' # To obiekt klasy str.

if imie.startswith('Swa'):
    print 'Tak, to imię zaczyna się od "Swa"'

if 'a' in imie:
    print 'Tak, to imię zawiera literę "a"'

if imie.find('war') != -1:
    print 'Tak, w tym imieniu jest ciąg "war"'

separator = '_*_'
mojalista = ['Brazylia', 'Rosja', 'Indie', 'Chiny']
print separator.join(mojalista)

Rezultat:

$ python str_metody.py
Tak, to imię zaczyna się od "Swa"
Tak, to imię zawiera literę "a"
Tak, w tym imieniu jest ciąg "war"
Brazylia_*_Rosja_*_Indie_*_Chiny

Jak to działa:

Tu widzimy wiele metod w akcji. Metoda startswith sprawdza, czy tekst się zaczyna od podanego ciągu znaków. Operator in sprawdza, czy dany ciąg znaków znajduje się w tym tekście.

Metoda find sprawdza pozycję podanego ciągu znaków w tekście. Zwraca ona -1, gdy nic nie znajdzie. Klasa str ma też ciekawą metodę join, która łączy elementy sekwencji w jeden długi ciąg znaków, używając podanego ciągu jako separatora.

Podsumowanie

Przestudiowaliśmy dokładnie różne wbudowane struktury danych Pythona. Będą one niezbędne przy pisaniu programów o sensownych rozmiarach.

Teraz, gdy już mamy opanowane wiele z podstaw Pythona, zobaczymy, jak zaprojektować i stworzyć Pythonowy program z prawdziwego zdarzenia.