SLOŽENE STRUKTURE PODATAKA (1)

TORKE I LISTE

U svim programima koje smo do sada pisali, podatke smo čuvali u pojedinačnim promenljivima. To su bili obično pojedinačni brojevi ili eventualno kraći delovi teksta (npr. ime ili prezime). Elementarni podaci koje smo do sada sretali bili su celi brojevi (tipa int), realni brojevi (tipa float), logičke vrednosti (tipa bool) i niske (tipa str). U mnogim realnim primenama imamo potrebu da u programu zapamtimo, a kasnije i obradimo veće količine podataka. U tim situacijama korišćenje pojedinačnih promenljivih za pamćenje svakog pojedinačnog podataka nije praktično ili čak nije moguće i potrebno je koristiti strukture podataka koje nam omogućavaju da pomoću jedne promenljive predstavimo čitave kolekcije podataka, koje se sastoje od više vrednosti nekog jednostavnijeg tipa. U zavisnosti od podataka koje želimo da sačuvamo i operacija koje sa njima želimo da sprovedemo, biramo koju od nekoliko različitih vrsta struktura podataka koje imamo na raspolaganju treba da upotrebimo.

Zapitajmo se kako bismo u programu mogli predstaviti spisak imena košarkaša u jednom timu? Neka je to naša košarkaška reprezentacija,  Pretpostavićemo da svaki igrač ima svoj redni broj i to od 1 do 12.

Jedan mogući način bi bio da uvedemo puno zasebnih promenljivih:

igrac1 = "Nikola Jokić"

igrac2 = "Bogdan Bogdanović"

igrac3 = "Nemanja Bjelica"

igrac4 = "Vasilije Micić"

...

Međutim, ovakav prikaz podataka nije zgodan jer ne možemo jednostavno da odgovorimo na razna interesantna pitanja o košarkašima (na primer, koliko ukupno ima igrača, ko nosi broj koji se unosi sa ulaza, koji broj nosi neki dati igrač i slično). Bolji način da predstavimo spisak igrača je da upotrebimo torku ili listu. Na primer, torku imena košarkaša možemo definisati na sledeći način:

igraci = ("Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović", "Marko Gudurić", "Marko Simonović", "Vladimir Lučić", "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić","Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov")

Zapis oblika (35, 128) se u matematici naziva uređeni par, zapis oblika (250, 120, 310) uređena trojka, zapis oblika (135, 22, 83, 57) uređena četvorka itd. Kada dužina nije poznata, kaže se uređena n-torka (uređena entorka), ali u programiranju je odomaćeno kraće ime - torka.

Dakle, torku definišemo tako što između običnih malih zagrada  ( i ) navodimo elemente razdvojene zarezima. Primetimo da je lista imena košarkaša veoma dugačka, tako da smo je preglednosti radi razbili u više redova. Iako u opštem slučaju nije dopušteno deliti naredbe na više linija, to je moguće ako je sadržaj tih linija okružen nekim zagradama (pošto je u prvoj liniji otvorena zagrada (, nakon čitanja prve automatski se čitaju i druga i treća i četvrta linija, sve dok se ne naiđe na zatvorenu zagradu )).

Definisanje liste bi se razlikovalo od definisanja torke samo po tome što bi se umesto običnih malih zagrada (...) upotrebile uglaste zagrade  [...].

igraci = ["Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović", "Marko Gudurić", "Marko Simonović", "Vladimir Lučić", "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić", "Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov"]

Suštinska razlika između torke i liste je to što je torka imutabilna što znači da joj ne možemo menjati vrednosti kada je jednom definišemo. Sa druge strane, liste dopuštaju da im menjamo pojedinačne elemente, uklanjamo elemente, dodajemo nove i slično. Sve operacije u kojima se vrši analiza sadržaja biće identične bez obzira da li se radi o listi ili o torki i opisaćemo ih u sledećoj lekciji (iako ćemo u primerima koristiti torke, sve one se na potpuno isti način mogu primeniti i na liste). Operacije u kojima se vrši promena su specifične za liste i nije ih moguće sprovesti nad torkama i njih ćemo opisati zasebno.

Pojedinačni članovi torke ili liste nazivaju se i elementi. Elementi mogu biti niske (kao u ovom primeru), ali i brojevi, druge torke ili liste i bilo šta drugo. Čak je moguće u istu torku tj. listu postaviti elemente različitog tipa. Kao primer torke brojeva, formirajmo torku visina ovih naših košarkaša.

visine = (198, 197, 198, 198, 203, 203, 210, 208, 213, 221, 213, 212)

Dvočlane torke (uređeni parovi) i višečlane torke ( uređene trojke, četvorke itd.) se najčešće koriste za grupisanje tek nekoliko pojedinačnih podataka. Na primer, poziciju figure na šahovskoj tabli možemo predstaviti pomoću uređenog para koji čini oznaka vrste (slova od a do h) i oznaka kolone (broja od 1 do 8). Na primer, ("b", 6). Slično, pozicije na geografskoj karti se opisuju pomoću geografske širine i dužine tj. pomoću para realnih brojeva. Tako se grad Pariz nalazi na poziciji koja se može opisati pomoću para (48.8566, 2.3522). Vreme možemo predstaviti pomoću uređene trojke koju čine sat, minut i sekund (na primer, (7, 25, 37)).

Za grupisanje većeg broja podataka češće se koriste liste, pogotovo ako nije unapred poznato koliko takvih podataka može biti tj. ako se broj podataka može izmeniti tokom rada programa. Na primer, ako želimo da predstavimo ocene učenika češće bismo upotrebili listu, jer učenik može da dobije još neku ocenu, pa je listu njegovih ocena potrebno proširiti, što nije moguće ako se ocene predstave torkom.

Izdvajanje elemenata

Elementima torke (ili liste) pristupa se na osnovu njihove pozicije tj. indeksa. Brojanje kreće od nule. Prvi element liste se nalazi na poziciji 0, drugi na poziciji 1 i tako dalje. 

Na primer, elementi u listi a = [3, 7, 4, 2, 5] se broje na sledeći način

Indeks             0 1 2 3 4

Vrednost         3 7 4 2 5

Zato je prvom elementu moguće pristupiti sa a[0] i vrednost toga izraza je 3 (jer se na poziciji 0 u listi nalazi broj 3), drugom elementu sa a[1] i vrednost tog izraza je 7 i tako dalje.

Negativni indeksi upućuju na brojanje od kraja (s desna na levo), pa -1 označava poslednji element, -2 pretposlednji i tako dalje.

Indeks             -5 -4 -3 -2 -1

Vrednost          3  7  4   2   5

Zato je poslednjem elementu moguće pristupiti pomoću a[-1], pretposlednjem pomoću a[-2] itd.

Još jedna korisna operacija je izdvajanje dela torke tj. liste. Elementima između pozicija x i y uključujući poziciju x, ali isključujući poziciju y moguće je pristupiti pomoću a[x:y].

Na primer, ime[1:4] izdvaja elemente imena na pozicijama 1, 2 i 3 (raspon [1:4] je poluotvoren tj. pozicija 1 je uračunata, a pozicija 4 nije). Ako je a = [3, 7, 4, 2, 5] tada je a[1:4] lista čija je vrednost [7, 4, 2]. Ako se izostavi broj iza dvotačke, izdvajaju se elementi do kraja. Na primer a[2:] je lista koja ima vrednost [4, 2, 5].

Primer:

Poznat je spisak igrača u timu. Oni nose dresove sa brojevima od 1 pa na dalje. Napiši program koji za dati broj dresa određuje igrača koji igra pod tim rednim brojem.

Pošto se unose brojevi od 1 do dužine torke (ili liste), a indeksi se kreću od 0 pa do prethodnika dužine torke, nakon učitavanja broja dresa pristupiće se elementu čiji je indeks za 1 manji od broja dresa.

igraci = ("Stefan Jović", "Vasilije Micić", "Bogdan Bogdanović",

          "Marko Gudurić", "Marko Simonović", "Vladimir Lučić",

          "Stefan Birčević", "Nemanja Bjelica", "Nikola Jokić",

          "Boban Marjanović", "Miroslav Raduljica", "Nikola Milutinov")

dres = int(input("Broj dresa: "))

print(igraci[dres - 1])

Zadatak za vežbu:

Odgovori na sledeća pitanja:

1. Zbog čega se uvode složene strukture podataka?

2. U čemu je razlika između torke i liste?

3. visine = (198, 197, 198, 198, 203, 203, 210, 208, 213, 221, 213, 212)

   Šta će biti vrednosti  sledećih izraza:
   visine[2:6], visine[4:8], visine[5:], visine[0], visine[-3]