Структуре података

Листе

Запитајмо се како бисмо у програму могли представити списак имена кошаркаша у једном тиму? Нека је то наша кошаркашка репрезентација која је 2016. играла на Олимпијади. Претпоставићемо да сваки играч има свој редни број и то од 1 до 12.

_images/kosarkasi.jpg

Један могући начин би био да уведемо пуно засебних променљивих:

Међутим, оваква репрезентација података није згодна јер не можемо једноставно да одговоримо на разна интересантна питања о кошаркашима (на пример, колико укупно има играча, ко носи број који се уноси са улаза, који број носи неки дати играч и слично). Бољи начин да представимо списак играча је да употребимо листу.

Појединачни чланови листе називају се и елементи. Елементи листе могу бити ниске (као у овом примеру), али и бројеви, друге листе и било шта друго. Чак је могуће у исту листу поставити елементе различитог типа (додуше, то нећемо често користити). Као пример листе бројева, формирајмо листу висина ових кошаркаша.

Листу дефинишемо тако што између угластих заграда (заграда [ и ]) наводимо елементе раздвојене зарезима. Приметимо да је ова листа имена кошаркаша била веома дугачка, тако да смо је прегледности ради разбили у више редова (зато смо на крају редова који се настављају морали навести косе црте \). Листа висина је била краћа, па смо све елементе навели у истом реду.

Издвајање елемената листе

Ниске и листе имају доста заједничког (ниска се у неку руку може схватити као листа карактера). Елементима листе приступа се на основу њихове позиције тј. индекса. Бројање креће од нуле, па је првом елементу листе могуће приступити са igraci[0]. Негативни индекси упућују на бојање од краја (с десна на лево), па је последњем елементу могуће приступити помоћу igraci[-1]. Елементима између позиција a и b укључујући позицију a, али искључујући позицију b могуће је приступити помоћу igraci[a:b]. Употребимо ово да решимо неколико задатака о нашим играчима.

Играч са датим бројем дреса

Познат је списак играча у тиму. Они носе дресове са бројевима од 1 па на даље. Напиши програм који за дати број дреса одређује играча који игра под тим редним бројем.

Пошто се уносе бројеви од 1 до дужине листе, а индекси се крећу од 0 па до претходника дужине листе, након учитавања броја дреса приступиће се елементу листе чији је индекс за 1 мањи од броја дреса.

Начин да се избегне ово померање индекса за 1 био би да се у листу путника на почетно место убаци неки вештачки елемент (на пример, празна ниска).

Играчи са датим бројевима дреса

Испиши имена играча са бројевима дреса 2, 3 и 4, као и име играча који има највећи број дреса у тиму.

Када би се дресови бројали од 0, као што се броје индекси листе, потребно би било издвојити елементе у распону [2:5] (то обухвата тачно индексе 2, 3 и 4). Пошто се места броје од 1, потребно је вредности наведене у распону умањити за 1 тј. употребити распон [1:4]. Последњи играч тј. последњи елемент листе се увек налази на позицији -1.

Ако исправиш програм како треба, требало би да добијеш одговоре ['Марко Симоновић', 'Богдан Богдановић', 'Никола Калинић'] и Стефан Бирчевић.

Ако је на прво место у листи играча уписана празна листа, напиши програм који одређује играче са бројевима 7, 8 и 9, као и претпоследњег играча у тиму.

Ако урадиш све како треба, требало би да добијеш одговоре ['Немања Недовић', 'Мирослав Радуљица', 'Милош Теодосић'] и Владимир Штимац.

Претрага листе

Проналажење најмање позиције (индекса) на којој се налази неки тражени елемент може се урадити коришћењем методе index, као што је то приказано у наредном задатку.

Број дреса датог играча

Који број дреса носи Никола Јокић?

Кроз овај задатак можемо илустровати претрагу листе, тј. проналажење индекса (позиције) у листи на којој се налази тражени елемент. Један начин да се то уради је помоћу методе index која враћа индекс (подсетимо се, индекси се броје од 0) првог појављивања траженог елемента тј. проузрокује грешку ако се тај елемент не налази у листи.

Ако листу не допунимо празним елементом на позицији 0, пошто се у авиону седишта броје од 1, а индекси од 0, пронађени индекс је потребно увећати за 1.

Рецимо и да је проверу да ли елемент припада листи могуће извршити коришћењем оператора in (на пример, "Бобан Марјановић" in igraci), о чему ће више бити речи у поглављу о гранању.

Путници на датим седиштима у авиону

Ево једног веома сличног задатка за вежбу.

Познат је списак имена путника у авиону. Седишта су нумерисана од 1 па надаље. Ако стјуардеса унесе број седишта, напиши програм који одређује име путника на том седишту. Након тога испиши имена путника која седе на прва четири, као и на последња два седишта, као и број седишта на којем седи Мика Микић.

_images/putnici_u_avionu.jpg

Да бисмо олакшали бројање, на првом месту у листи је постављен вештачки елемент (празна листа).

Функције за рад са листама

Функцијом len израчунавамо дужину листе, функцијом sum израчунавамо збир елемената листе, функцијом min најмањи елемент у листи, а функцијом max највећи.

Ове функције можемо употребити да једноставно решимо разне практичне задатке.

Просечна оцена

Дате су оцене из неколико предмета. Израчунај просечну оцену.

Победнички скок

На Олимпијским играма у Рију наша атлетичарка Ивана Шпановић је скакала редом 6,95m, затим у наредне две серије преступила, а затим скакала, 6,91m, 7,08m и 7,05m. Одреди дужину скока (у метрима) који јој је донео бронзану медаљу.

_images/spanovic.jpg

Наравно, програм ако је исправан треба да испише 7.08.

Најмања оцена

Ако се зна да су оцене из природних наука последње три у листи оцена, израчунај Горанову најмању оцену из тих предмета.

Распон температура

Време се често мења и дешава се да се у једној недељи смењују и хладни и топли дани. Ако су дате су температуре у подне у данима током једне недеље, одреди колики је распон температура тј. разлика између највише и најниже подневне температуре.

_images/termometar.jpg

Надовезивање листи

Две листе можемо надовезати (спојити у једну) коришћењем операције + (аналогно надовезивању ниски).

Висине девојчица и дечака у одељењу

Познате су висине девојчица и висине дечака у једном одељењу. Направи листу свих висина и израчунај затим број и просечну висину свих ђака.

Сортирање листе

Елементе листе је веома једноставно уредити од најмањег до највећег (па и обратно, од највећег до најмањег).

Најјефтинији за динар

Дате су цене три производа. Ко купи сва три, најјефтинији ће добити за динар. Колико ће платити?

Један начин је да сортирамо листу од три цене тако да цене у листи буду уређене од најмање до највеће, а затим да први елемент листе (цену најјефтинијег производа) заменимо са 1 и на крају саберемо елементе листе.

Рецимо и да смо задатак могли решити и без сортирања.

Три најјефтинија и најскупља производа

Дата је листа цена производа. Колико коштају три најјефтинија, а колико три најскупља производа?

Сортирање имена ученика

Наставница треба да у дневник унесе имена ученика, међутим, од педагога је добила списак ученика који није сортиран. Напиши програм који помаже наставници да добије ученике сортиране по абецедном реду.

Напоменимо да овакво сортирање може имати проблем са нашим карактерима ćđščž.

Распакивање листе

Ако знамо дужину листе, могуће је на лак начин именовати сваки њен елемент тј. сместити сваки елемент у посебну променљиву. На пример, претпоставимо да листа математичари садржи пуна имена четири велика математичара: Ренеа Декарта, Жозефа Луја Лагранжа, Карла Фридриха Гауса и Леонарда Ојлера. Направимо четири посебне променљиве dekart, lagranz, gaus и ojler које ће садржати пуна имена одговарајућих математичара.

Један начин да се то уради је да се помоћу индекса приступи појединачним елементима листе.

Међутим, постоји и једноставнији начин да се постигне исти ефекат.

Пошто и листа са десне и листа са леве стране имају по четири елемента, онда се првој променљивој са леве стране додељује први елемент листе са десне стране, другој променљивој, други елемент листе и тако даље. Овај поступак називамо распакивање листе.

Скупови

Ако знамо имена свих фудбалера који су давали голове током једне ревијалне утакмице и то редом, како су давали голове можемо једноставно одредити скуп свих фудбалера који су се уписали у листу стрелаца. Наиме, ако формирамо скуп на основу имена стрелаца аутоматски ће бити уклоњени дупликати.

Скуп дефинишемо тако што између витичастих заграда (заграда { и }) наводимо елементе раздвојене зарезима. Елементи скупа у овом примеру су биле ниске, а можемо разматрати и скупове елемената другог типа (на пример, скупове бројева).

Скуп од листе/ниске

Ако су елементи скупа чланови неке листе, можемо лако од листе добити скуп (коришћењем функције set као у следећем програму).

И од ниске можемо једноставно добити скуп карактера које она садржи (опет помоћу функције set).

Скуповне операције

У језику Python можемо веома једноставно израчунати унију, пресек и разлику скупова. Ако су A и B скупови, онда је A | B њихова унија, A & B њихов пресек, а A - B њихова разлика. Провери да ли се сећаш ових операција из математике тако што ћеш решити наредни тест.

    Ако је A = {3, 6, 7}, а B = {3, 4, 5}, повежи скуповне операције са њиховим резултатима. Feedback that is displayed if things are incorrectly matched--is optional
  • A & B
  • {3}
  • A | B
  • {3, 4, 5, 6, 7}
  • A - B
  • {6, 7}
  • B - A
  • {4, 5}
  • (A - B) | (B - A)
  • {4, 5, 6, 7}

Прикажимо како се скуповне операције могу употребити у решењима неколико задатака.

Девојчице које тренирају два спорта

Један скуп садржи девојчице из одељења које тренирају ритмичку гимнастику, а други оне које тренирају одбојку. Одреди скуп девојчица које тренирају оба спорта, скуп девојчица које тренирају бар један од њих и скуп девојчица које тренирају само одбојку.

Сугласници

Сугласници се по месту изговора могу бити предњонепчани (Ј, Љ, Њ, Ћ, Ђ, Ш, Ж, Ч, Џ) и задњонепчани К, Г, Х. По звучности, сугласници се деле на звучне (Б, Г, Д, Ђ, Ж, З, Џ), безвучне (П, К, Т, Ћ, Ш, С, Ч, Ф, Х, Ц), и сонанте(М, В, Р, Л, Н, Љ, Њ, Ј).

  • Који сугласници су истовремено и звучни и предњонепчани?
  • Који безвучни сугласници нису задњонепчани?
  • Који сугласници су сонанти или звучни?

Поправи наредни код тако да исправно решава овај задатак. Програм након покретања треба да испише наредне резултате.

{'Ђ', 'Џ', 'Ж'}
{'Ч', 'Ћ', 'Ш', 'Т', 'П', 'Ф', 'С', 'Ц'}
{'Џ', 'З', 'Д', 'Ђ', 'Ј', 'Л', 'Н', 'М', 'Г', 'Р', 'Б', 'Љ', 'Њ', 'Ж', 'В'}

Панграми

Панграми су реченице које садрже сва слова неке абецеде или азбуке. Пожељно је да панграми буду што краћи. Панграми се обично користе да би се приказали фонтови на рачунарима (јер корисник кроз веома кратак текст може видети како изгледају сва слова). Најчувенији панграм на енглеском језику је the quick brown fox jumps over the lazy dog. Неки од панграма на српском језику су и следеће реченице:

  • Фијуче ветар у шибљу, леди пасаже и куће иза њих и гунђа у оџацима.
  • Ниџо, чежњиво гледаш фотељу, а Ђура и Мика хоће позицију себи.
  • Дебљој згужвах смеђ филц — њен шкрт џепчић.

Напиши програм који за дату реченицу проверава да ли је панграм тако што исписује број различитих слова која се у њој јављају.

Дефинисаћемо скуп малих слова ћирилице и пронаћи ћемо пресек тог скупа и скупа слова која се јављају у реченици (у којој су помоћу lower() сва слова претворена у мала).

Торке

Неколико појединачних података можемо груписати коришћењем уређених парова или уређених n-торки. На пример, позицију фигуре на шаховској табли можемо представити помоћу уређеног пара који чини ознака врсте (слова од a до h) и ознака колоне (броја од 1 до 8). На пример, ("b", 6). Слично, позиције на географској карти се описују помоћу географске ширине и дужине тј. помоћу пара реалних бројева. Тако се град Париз налази на позицији која се може описати помоћу пара (48.8566, 2.3522). Време можемо представити помоћу уређене тројке коју чине сат, минут и секунд (на пример, (7, 25, 37)).

Као што ћемо видети, торке су веома сличне листама. Главна разлика је то што се у листе могу додавати елементи, док су торке фиксиране дужине и једном када направимо торку нема начина да се она промени (не постоји начин да јој се додају, уклоне нити промене елементи).

Индексирање и распакивање торки

Индексирање парова врши се на исти начин као индексирање листа (на позицији 0 налази се први елемент торке, на позицји 1 други и тако даље). Слично као и код листе и торке се могу распаковати.

Географске координате

Уређени пар садржи географске координате града Париза. Напиши програм који одређује и посебно исписује његову географску ширину и географску дужину.

_images/geografske_koordinate.jpg

Коришћењем распакивања, претходни задатак смо могли да решимо и на следећи начин.

Враћање торки из функције

Као што смо већ раније поменули, торке могу бити веома корисне да би се вратило више вредности из функције. Размотримо наредни пример.

Конверзија угла у степене и минуте

Напиши функцију која за угао дат у облику децималног броја степени одређује њему најближи угао дат у степенима и минутима. Употреби га да одредиш колико степени и минута има угао \(36,2^\circ\).

Приметимо да се приликом прихватања резултата врши распакивање торке тј. да се променљивима stepeni и minuta додељују редом први и други елемент уређеног пара који је функција вратила.

Листе торки

Торке могу да буду елементи листе. Направимо, на пример, листу која садржи податке о месецима током једне године која није преступна. За сваки месец знамо назив и број дана и те податке ћемо организовати помоћу уређене двојке (на пример, ("април", 30)).

Дани у месецу

Помоћну променљиву mesec није било неопходно користити. Поправи индексе у наредном програму тако да ради исто као и претходни.

Речници

Листе нам дају могућност да организујемо податке за које је познат неки редослед и у којима сваки податак има свој редни број (на пример, листу смо употребили да организујемо имена путника у авиону или податке о месецима у години) и приступ елементима листе врши се на основу њиховог индекса (редног броја, тј. позиције). Међутим, често подаци представљају неко пресликавање у којем на основу датог кључа желимо да приступимо вредности која је придружена том кључу. На пример, на основу шифре производа приступамо његовој цени, на основу ЈМБГ грађана приступамо његовом имену, на основу броја банковног рачуна приступамо салду (износу новца) на том рачуну и слично. У тим ситуацијама уместо листе много је боље користити речнике (каже се и мапе или асоцијативне низове).

Дефинисање и коришћење речника

Цене аутомобила

Аутомобили у каталогу имају придружене цене и ми желимо да у нашем програму можемо да одредимо цену аутомобила на основу његовог модела. Напиши програм који на основу унетог модела аутомобила (ниска) одређује његову цену (цео број).

_images/sajam_automobila.jpg

Кључна одлука за ефикасно решење овог задатка је да каталог цена аутомобила представимо помоћу речника.

У претходном примеру модели аутомобила су кључеви који се пресликавају у цене аутомобила које су вредности. Кључеви су биле ниске, а вредности цели бројеви, што је чест случај.

Звучни и безвучни сугласници

Звучни и безвучни сугласници јављају се у паровима. Звучни сугласници су БГДЂЖЗЏ (можеш их лакше запамтити помоћу првих слова реченице Баба грди деду: “Ђаволе живи зашто џандрљаш”?) Њихови безвучни парови су редом ПКТЋШСЧ. Napiши програм који за дати звучни сугласник одређује његов безвучни пар.

Поправи наредни програм тако што ћеш попунити речник одговарајућим паровима сугласника. Ако све урадиш како треба, требало би да добијеш 7 зелених поља (сваки сугласник мора да прође тест). Користи велика слова ћирилице.

Географске координате градова

У наредном примеру вредности у речнику су уређени парови.

Познате су географске координате неколико главних европских градова. За дато име града одреди њене географске координате. Одреди посебно географску дужину и посебно географску ширину.