§ 21. Структуры даных

21.1. Паняцце пра структуры даных

У інфарматыцы структура даных —  праграмная адзінка, якая дазваляе захоўваць і апрацоўваць даныя, а таксама забяспечвае іх эфектыўнае выкарыстанне. Даныя пры гэтым павінны быць аднатыпнымі або лагічна звязанымі.

Розныя віды структур даных падыходзяць для розных задач; некаторыя з іх маюць вузкую спецыялізацыю, іншыя з’яўляюцца ўніверсальнымі  (прыклад 21.1).

Пры распрацоўцы праграмнага забеспячэння складанасць рэалізацыі і якасць работы праграм істотна залежаць не толькі ад выбару алгарытму, але і ад правільнага выбару структур даных. Адны і тыя ж даныя можна захаваць у структурах, якія патрабуюць рознага аб’ёму памяці, а алгарытмы работы з рознымі структурамі даных могуць мець розную эфектыўнасць. Структура даных, якая найбольш падыходзіць для рашэння пэўнай задачы,  дазваляе выконваць вялікую колькасць розных аперацый, выкарыстоўваючы як мага меншы аб’ём рэсурсаў.

Ніводная прафесійная праграма сёння не пішацца без выкарыстання структур даных, таму шмат якія з іх змяшчаюцца ў стандартных бібліятэках сучасных моў праграміравання (напрыклад, STL для С++).

Структура даных уяўляе сабой набор значэнняў даных, адносіны паміж імі, а таксама функцыі і (ці) аперацыі, якія могуць быць ужыты да даных.

Структуры даных класіфікуюць па розных прыметах. У прыклад 21.2 прыведзена класіфікацыя структур даных па арганізацыі ўзаемасувязей паміж элементамі.

Далей будуць разгледжаны некаторыя лінейныя структуры даных.

Прыклад 21.1. Прыклады некаторых структур даных:

  1. Масіў (вектар у C++) — самая простая і шырока выкарыстоўваемая структура даных.
  2. Запіс (структура ў С++) — сукупнасць элементаў даных рознага тыпу. Змяшчае пастаянную колькасць элементаў, якія называюць палямі.
  3. Звязны спіс (Linked List) уяўляе сабой набор звязаных вузлоў, кожны з якіх захоўвае ўласна даныя і спасылку на наступны вузел. У рэальным жыцці звязны спіс можна ўявіць у выглядзе цягніка, кожны вагон якога можа змяшчаюць некаторы груз ці пасажыраў і пры гэтым можа быць звязаны з іншым вагонам.
  4. Граф — сукупнасць вяршынь (вузлоў) і сувязей паміж імі (кантаў). У рэальным жыцці па такім прынцыпе пабудаваны сацыяльныя сеткі: вузлы — гэта людзі, а канты — іх адносіны.
  5. Мноства — сукупнасць даных, значэнні якіх не паўтараюцца,  рэалізацыя матэматычнага аб’екта мноства, за выключэннем таго, што мноства ў праграміраванні канечная.

Прыклад 21.2. Класіфікацыя структур даных.

•        Лінейныя:

    • масіў;
    • спіс;
    • звязаны спіс;
    • стэк;
    • чарга;
    • хэш-табліца.

•        Іерархічныя:

    • двайковыя дрэвы;
    • n-арныя дрэвы;
    • іерархічны спіс.

•        Сеткавыя:

    • •неарыентаваны граф;
    • •арыентаваны граф.

•        Таблічныя:

    • •табліца рэляцыйнай базы даных;
    • •двухмерны масіў.