Ang isang kinakailangang kondisyon para sa pag-iimbak ng impormasyon sa memorya ng computer ay ang kakayahang i-convert ang impormasyong ito sa isang form na angkop para sa isang computer. Kung ang kundisyong ito ay natutugunan, kinakailangan upang matukoy ang isang istraktura na partikular na angkop para sa umiiral na impormasyon, isa na magbibigay ng kinakailangang hanay ng mga kakayahan para sa pagtatrabaho dito.

Listahan ng singsing

Dito, ang istraktura ay nauunawaan bilang isang paraan ng paglalahad ng impormasyon kung saan ang isang hanay ng mga indibidwal na elemento ay bumubuo ng isang bagay na pinag-isa, na tinutukoy ng kanilang kaugnayan sa isa't isa. Kapag inayos ayon sa ilang mga patakaran at lohikal na konektado sa isa't isa, ang data ay maaaring maproseso nang napakahusay, dahil ang karaniwang istraktura para sa kanila ay nagbibigay ng isang hanay ng mga posibilidad para sa pamamahala ng mga ito - isa sa mga dahilan kung saan ang mataas na mga resulta ay nakakamit sa paglutas ng ilang mga problema.

Ngunit hindi lahat ng bagay ay kinakatawan sa isang arbitrary na anyo, at marahil ay mayroon lamang isang solong paraan ng interpretasyon para dito, samakatuwid, ang kaalaman sa lahat ng umiiral na mga istruktura ng data ay magiging isang walang alinlangan na kalamangan para sa programmer. Kaya, madalas kang kailangang pumili sa pagitan ng iba't ibang paraan ng pag-iimbak ng impormasyon, at ang pagganap ng produkto ay nakasalalay sa pagpipiliang ito.

Sa pagsasalita tungkol sa teknolohiyang hindi pang-computer, posibleng magpakita ng hindi isang solong kaso kung saan ang impormasyon ay may malinaw na istraktura. Ang isang magandang halimbawa ay ang mga aklat na may iba't ibang nilalaman. Ang mga ito ay nahahati sa mga pahina, mga talata at mga kabanata, at karaniwang may talaan ng mga nilalaman, iyon ay, isang interface para sa paggamit ng mga ito. Sa isang malawak na kahulugan, ang bawat buhay na nilalang ay may istraktura kung wala ito, ang mga organikong bagay ay halos hindi mabubuhay.

Malamang na ang mambabasa ay nakatagpo ng mga istruktura ng data nang direkta sa computer science, halimbawa, ang mga naka-built sa isang programming language. Ang mga ito ay madalas na tinutukoy bilang mga uri ng data. Kabilang dito ang: mga array, numero, string, file, atbp.

Ang mga pamamaraan ng pag-iimbak ng impormasyon, na tinatawag na "simple", i.e. hindi mahahati sa mga bahaging bahagi, ay mas mainam na pag-aralan kasama ng isang partikular na programming language, o upang malalim na suriin ang kakanyahan ng kanilang trabaho. Samakatuwid, ang mga "integrated" na istruktura lamang ang isasaalang-alang dito, ang mga binubuo ng mga simple, katulad: mga array, listahan, puno at mga graph.

Mga array.

Ang array ay isang istraktura ng data na may nakapirming at nakaayos na hanay ng mga magkakatulad na elemento (mga bahagi). Ang pag-access sa alinman sa mga elemento ng array ay isinasagawa sa pamamagitan ng pangalan at numero (index) ng elementong ito. Tinutukoy ng bilang ng mga index ang laki ng array. Halimbawa, ang one-dimensional (vectors) at two-dimensional (matrices) arrays ay madalas na nakakaharap.

Ang una ay may isang index, ang huli - dalawa. Hayaan ang isang one-dimensional na array na tawaging A, pagkatapos ay upang makakuha ng access sa i-th na elemento nito kakailanganin mong tukuyin ang pangalan ng array at ang bilang ng kinakailangang elemento: A[i]. Kapag ang A ay isang matrix, kinakatawan ito sa anyo ng isang talahanayan, ang mga elemento nito ay na-access sa pamamagitan ng pangalan ng array, pati na rin ang mga numero ng hilera at haligi sa intersection kung saan matatagpuan ang elemento: A, kung saan i ang row number, j ang column number.

Ang pagtatrabaho sa mga array ay maaaring magkakaiba sa ilang paraan sa iba't ibang programming language, ngunit ang mga pangunahing prinsipyo ay karaniwang pareho sa lahat ng dako. Sa wikang Pascal, ang pag-access sa isang one-dimensional at two-dimensional na array ay nangyayari nang eksakto tulad ng ipinapakita sa itaas, at, halimbawa, sa C++, ang isang two-dimensional na array ay dapat tukuyin tulad ng sumusunod: A[i][j]. Ang mga elemento ng array ay binibilang nang sunud-sunod. Ang programming language ay nakakaimpluwensya sa halaga kung saan nagsisimula ang pagnunumero. Kadalasan ang value na ito ay 0 o 1.

Ang mga array ng inilarawang uri ay tinatawag na static, ngunit mayroon ding mga arrays na naiiba sa kanila sa ilang partikular na paraan: dynamic at heterogenous. Ang dynamism ng dating ay nailalarawan sa pamamagitan ng variable na laki, ibig sabihin, habang isinasagawa ang programa, maaaring magbago ang laki ng dynamic na array. Ginagawa ng function na ito ang pagtatrabaho sa data na mas nababaluktot, ngunit sa parehong oras kailangan mong isakripisyo ang pagganap, at ang proseso mismo ay nagiging mas kumplikado.

Ang isang ipinag-uutos na pamantayan para sa isang static na array, tulad ng sinabi, ay ang homogeneity ng data na sabay-sabay na nakaimbak dito. Kapag hindi natugunan ang kundisyong ito, ang array ay heterogenous. Ang paggamit nito ay dahil sa mga disadvantages na umiiral sa nakaraang anyo, ngunit ito ay makatwiran sa maraming mga kaso.

Kaya, kahit na nagpasya ka sa istraktura at pumili ng isang array bilang nito, hindi pa rin ito sapat. Pagkatapos ng lahat, ang isang array ay isang pangkalahatang pagtatalaga lamang, isang genus para sa isang tiyak na bilang ng mga posibleng pagpapatupad. Samakatuwid, ito ay kinakailangan upang magpasya sa isang tiyak na paraan ng representasyon, na may pinaka-angkop na array.

Mga listahan.

Ang isang listahan ay isang abstract na uri ng data na nagpapatupad ng nakaayos na hanay ng mga halaga. Ang mga listahan ay naiiba sa mga array dahil ang kanilang mga elemento ay naa-access nang sunud-sunod, habang ang mga array ay mga random na access na istruktura ng data. Ang abstract na uri na ito ay may ilang mga pagpapatupad sa anyo ng mga istruktura ng data. Ang ilan sa mga ito ay tatalakayin dito.

Ang isang listahan (naka-link na listahan) ay isang istraktura ng data na isang may hangganan na hanay ng mga nakaayos na elemento na konektado sa isa't isa sa pamamagitan ng mga pointer. Ang bawat elemento ng istraktura ay naglalaman ng isang field na may ilang impormasyon, pati na rin ang isang pointer sa susunod na elemento. Hindi tulad ng isang array, walang random na access sa mga elemento ng isang listahan.

Iisang naka-link na listahan

Sa isa-isang naka-link na listahan sa itaas, ang unang elemento ay ang Head list (arbitrary na pangalan) at lahat ng iba pa ay tinatawag na buntot. Ang buntot ng listahan ay binubuo ng mga elemento na nahahati sa dalawang bahagi: impormasyon (field ng impormasyon) at indexical (susunod na field). Ang huling elemento, sa halip na isang pointer, ay naglalaman ng isang listahan ng terminator - nil.

Ang isang solong naka-link na listahan ay hindi masyadong maginhawa, dahil mula sa isang punto posible lamang na makarating sa susunod na punto, sa gayon ay lumipat sa dulo. Kapag, bilang karagdagan sa isang pointer sa susunod na elemento, mayroon ding isang pointer sa nauna, kung gayon ang naturang listahan ay tinatawag na dobleng naka-link.

Dobleng naka-link na listahan

Ang kakayahang sumulong at paatras ay kapaki-pakinabang para sa ilang mga operasyon, ngunit ang mga karagdagang pointer ay nangangailangan ng higit na memorya kaysa sa kinakailangan sa isang katumbas na listahan ng isahang naka-link.

Para sa dalawang uri ng mga listahang inilarawan sa itaas, mayroong subtype na tinatawag na circular list. Maaari kang gumawa ng isang pabilog na listahan mula sa isang solong naka-link na listahan sa pamamagitan ng pagdaragdag lamang ng isang pointer sa huling elemento upang ito ay tumutukoy sa una. At para sa isang dobleng konektado, dalawang pointer ang kinakailangan: sa una at huling mga elemento.

Listahan ng singsing

Bilang karagdagan sa mga uri ng mga istruktura ng listahan na isinasaalang-alang, may iba pang mga paraan upang ayusin ang data gamit ang uri ng "listahan", ngunit ang mga ito, bilang panuntunan, ay higit na katulad sa mga tinalakay, kaya aalisin ang mga ito dito.

Bilang karagdagan sa mga pagkakaiba sa mga koneksyon, ang mga listahan ay hinati sa pamamagitan ng mga paraan ng pagtatrabaho sa data. Ang ilan sa mga pamamaraang ito ay tinalakay sa ibaba.

salansan.

salansan

Ang isang stack ay nailalarawan sa pamamagitan ng katotohanan na ang mga elemento nito ay maa-access lamang mula sa isang dulo, na tinatawag na tuktok ng stack, sa madaling salita: ang isang stack ay isang istraktura ng data na gumagana ayon sa prinsipyo ng LIFO (last in - first out). Mas mainam na ilarawan ang istraktura ng data na ito sa anyo ng isang patayong listahan, halimbawa, isang stack ng ilang mga bagay, kung saan upang magamit ang isa sa mga ito kailangan mong iangat ang lahat ng mga bagay na nasa itaas nito, at maaari mo lamang ilagay isang item sa tuktok ng stack.

Sa ipinapakitang single linked list, ang mga operasyon sa mga elemento ay nangyayari nang mahigpit sa isang dulo: upang maisama ang gustong elemento sa ikalimang cell, kinakailangang ibukod ang elementong sumasakop sa posisyong ito. Kung mayroong, halimbawa, 6 na elemento, at isang partikular na elemento ang kailangan ding ipasok sa ikalimang cell, kung gayon dalawang elemento ang kailangang ibukod.

Nakapila.

Ang istraktura ng data ng Queue ay gumagamit ng prinsipyo ng organisasyon ng FIFO (First In, First Out). Sa isang kahulugan, ang pamamaraang ito ay mas patas kaysa sa kung saan gumagana ang stack, dahil ang simpleng panuntunan na pinagbabatayan ng karaniwang mga pila sa iba't ibang mga tindahan at ospital ay itinuturing na medyo patas, at tiyak na ito ang batayan ng istrukturang ito. Hayaang maging halimbawa ang obserbasyong ito. Sa mahigpit na pagsasalita, ang isang queue ay isang listahan kung saan ang mga elemento ay maaari lamang idagdag sa dulo, at maaari silang makuha mula sa kabilang panig, na tinatawag na simula ng listahan.

Nakapila

Dec

Ang Deque (double ended queue) ay isang stack na may dalawang dulo. Sa katunayan, sa kabila ng partikular na pagsasalin, ang isang deck ay maaaring tukuyin hindi lamang bilang isang two-way na pila, kundi pati na rin bilang isang stack na may dalawang dulo. Nangangahulugan ito na ang ganitong uri ng listahan ay nagbibigay-daan sa mga elemento na maidagdag sa simula at sa wakas, at ganoon din para sa operasyon ng pagkuha.

Dec

Ang istrukturang ito ay sabay na gumagana sa dalawang paraan ng pag-aayos ng data: FIFO at LIFO. Samakatuwid, maaari itong maiuri bilang isang hiwalay na yunit ng programa na nakuha sa pamamagitan ng pagbubuod ng dalawang nakaraang uri ng listahan.

Mga graph.

Ang sangay ng discrete mathematics na tumatalakay sa pag-aaral ng mga graph ay tinatawag na graph theory. Detalyadong sinusuri ng teorya ng graph ang mga kilalang konsepto, katangian, pamamaraan ng representasyon at mga lugar ng aplikasyon ng mga bagay na ito sa matematika. Kami ay interesado lamang sa mga aspeto nito na mahalaga sa programming.

Ang graph ay isang koleksyon ng mga puntos na konektado ng mga linya. Ang mga punto ay tinatawag na vertices (nodes), at ang mga linya ay tinatawag na mga gilid (arcs).

Gaya ng ipinapakita sa figure, mayroong dalawang pangunahing uri ng mga graph: nakadirekta at hindi nakadirekta. Sa una, ang mga gilid ay nakadirekta, ibig sabihin, mayroon lamang isang magagamit na direksyon sa pagitan ng dalawang konektadong vertex, halimbawa, maaari kang pumunta mula sa vertex 1 hanggang sa vertex 2, ngunit hindi sa kabaligtaran. Sa isang hindi nakadirekta na konektadong graph, maaari kang pumunta mula sa bawat vertex patungo sa bawat isa at pabalik. Ang isang espesyal na kaso ng dalawang uri na ito ay isang magkahalong graph. Ito ay nailalarawan sa pagkakaroon ng parehong oriented at unoriented na mga gilid.

Ang in-degree ng isang vertex ay ang bilang ng mga gilid na pumapasok dito, ang out-degree ay ang bilang ng mga papalabas na gilid.

Ang mga gilid ng graph ay hindi kailangang tuwid, at ang mga vertice ay tiyak na itinalaga ng mga numero, tulad ng ipinapakita sa figure. Bilang karagdagan, may mga graph na ang mga gilid ay itinalaga ng isang partikular na halaga; Kapag ang magkabilang dulo ng isang gilid ay nag-tutugma, iyon ay, ang gilid ay umalis at pumapasok sa vertex F, kung gayon ang naturang gilid ay tinatawag na isang loop.

Ang mga graph ay malawakang ginagamit sa mga istrukturang nilikha ng tao, halimbawa, sa mga network ng computer at transportasyon, at mga teknolohiya sa web. Ang mga espesyal na paraan ng representasyon ay nagpapahintulot sa graph na magamit sa computer science (sa mga computer). Ang pinakasikat sa kanila: "Adjacency Matrix", "Insidente Matrix", "Adjacency List", "Edge List". Ang unang dalawa, gaya ng ipinahihiwatig ng pangalan, ay gumagamit ng isang matrix upang kumatawan sa graph, at ang huling dalawa ay gumagamit ng isang listahan.

Mga puno.

Walang ayos na puno

Ang isang puno bilang isang bagay sa matematika ay isang abstraction mula sa mga homonymous na yunit na matatagpuan sa kalikasan. Ang pagkakapareho ng istraktura ng mga natural na puno na may mga graph ng isang tiyak na uri ay nagpapahiwatig ng pagpapalagay ng pagtatatag ng isang pagkakatulad sa pagitan nila. Namely, na may konektado at sa parehong oras acyclic (walang cycle) graphs. Ang huli sa kanilang istraktura ay talagang kahawig ng mga puno, ngunit may ilang mga pagkakaiba, halimbawa, kaugalian na ilarawan ang mga puno ng matematika na may ugat na matatagpuan sa itaas, iyon ay, ang lahat ng mga sanga ay "lumago" mula sa itaas hanggang sa ibaba. Ito ay kilala na sa kalikasan ito ay hindi sa lahat ng kaso.

Dahil ang isang puno ay mahalagang isang graph, marami sa mga kahulugan nito ay tumutugma sa huli o intuitively na magkapareho. Kaya ang root node (vertex 6) sa istraktura ng puno ay ang tanging vertex (node) na nailalarawan sa kawalan ng mga ninuno, ibig sabihin, na walang ibang vertex na tumutukoy dito, at mula sa root node mismo maaari mong maabot ang alinman sa mga umiiral na. vertices tree, na sumusunod mula sa pagiging konektado ng istrakturang ito. Ang mga node na hindi tumutukoy sa anumang iba pang mga node, sa madaling salita, ay walang mga anak, ay tinatawag na mga dahon (2, 3, 9), o mga terminal node. Ang mga elementong matatagpuan sa pagitan ng root node at ng mga dahon ay mga intermediate node (1, 1, 7, 8). Ang bawat tree node ay may isang ninuno lamang, o kung ito ay isang root node, wala ito.

Ang subtree ay isang bahagi ng puno na kinabibilangan ng root node at lahat ng descendant node nito. Kaya, halimbawa, sa figure ang isa sa mga subtree ay may kasamang ugat 8 at mga elemento 2, 1, 9.

Maaari kang magsagawa ng maraming operasyon sa isang puno, tulad ng paghahanap ng mga elemento, pagtanggal ng mga elemento at subtree, pagpasok ng mga subtree, paghahanap ng mga root node para sa ilang vertices, atbp. Isa sa pinakamahalagang operasyon ay ang pagtawid sa puno. Mayroong ilang mga paraan ng pag-aayos. Ang pinakasikat sa kanila ay: simetriko, direktang at reverse bypass. Sa panahon ng pasulong na traversal, ang mga ancestor node ay binibisita bago ang kanilang mga inapo, at sa reverse traversal, ang sitwasyon ay naaayon na nababaligtad. Sa isang simetriko traversal, ang mga subtree ng pangunahing puno ay tinitingnan nang magkakasunod.

Ang pagtatanghal ng data sa itinuturing na istraktura ay kapaki-pakinabang kung ang impormasyon ay may tahasang hierarchy. Halimbawa, ang pagtatrabaho sa data tungkol sa biological genera at species, mga titulo ng trabaho, geographic na mga bagay, atbp. ay nangangailangan ng isang hierarchically expressed na istraktura, tulad ng mga mathematical tree.

MGA URI AT ISTRUKTURA NG DATA

Mga Alituntunin para sa disiplina na "Mga Algorithm at Mga Istraktura ng Data"

Pinagsama ni O.L. Chagaeva

Inihanda ng Department of Software Tools and Systems ng Federal Educational Institution UrFU

Panimula

SA Sa mundo sa paligid natin mayroong isang malaking pagkakaiba-iba ng mga bagay, bagay, phenomena, proseso na ipinapakita sa pamamagitan ng impormasyon.

Ang bawat entity (object, phenomenon) na kinakatawan ng impormasyon ay may ilang mga katangian na katangian nito (mga katangian, palatandaan, parameter, katangian, sandali). Halimbawa, ang mga katangian ng isang materyal ay ang bigat nito, mga sukat, grado, presyo, numero ng item, atbp. Mga katangian-mga palatandaan na nagpapakilala sa naturang entity gaya ng samahan ng pagbili ay pangalan, kaakibat ng departamento, address, kasalukuyang numero ng account sa State Bank , atbp.

Ang mga katangian ng isang pisikal na entity ay ipinapakita gamit ang mga variable, na mga elementarya na yunit ng impormasyon at tinatawag na mga detalye.

Ang prop ay isang lohikal na hindi mahahati na elemento ng anumang kumplikadong hanay ng impormasyon, na nauugnay sa isang partikular na katangian ng bagay o proseso na ipinapakita ng impormasyon.

SA ng naprosesong impormasyon, ang mga detalye ay kinakatawan na parang "mga atom", kung saan ang lahat ng iba pa, mas kumplikadong mga istruktura ng pagbuo ng impormasyon ay binuo. At sa kabaligtaran, ang mga yunit ng impormasyon ng anumang kumplikado ay maaaring, sa pamamagitan ng sunud-sunod na pagkabulok sa kanilang mga sangkap na bumubuo, sa huli ay nahahati sa mga naturang bahagi - mga variable na dami na hindi maaaring higit pang lohikal na hatiin. Ang mga nasabing elementong sangkap ang magiging mga detalye.

Ang iba pang kasingkahulugan ng props na madalas makita sa panitikan ay elemento, patlang, termino, katangian iattribute.

Ang bawat prop ay may pangalan. Kapag ang algorithmizing at programming para sa layunin ng compact na pagsulat, mga pagdadaglat ay madalas na ginagamit mga pangalan ng identifier, na may mga partikular na pagpapatupad na karaniwang naglilimita sa kanilang haba, alpabeto, at saklaw. Sa ilang mga kaso, pinapayagan din na gumamit ng mga kasingkahulugan para sa mga pangalan ng mga detalye, kabilang ang mga buong pangalan na ginagamit lamang sa mga panlabas na dokumento, halimbawa, bilang mga heading ng mga column ng ulat.

Ang bawat katangian ay likas sa isang tiyak na may hangganan na hanay ng mga halaga depende sa mga katangian ng pag-aari ng bagay (phenomenon) na ipinapakita ng katangiang ito sa impormasyon. Isa itong hanay na tinatawag na klase ng mga halaga, isa, halimbawa, para sa parameter na "temperatura ng pasyente" at isa pa para sa attribute na "kasarian ng pasyente."

Ang halaga ng katangian, samakatuwid, sa bawat naibigay na sandali sa oras ay isa sa mga posisyon ng klase ng mga halaga ng katangiang ito, na, tulad ng inaasahan, ay sumasalamin sa kaukulang estado (mula sa isang hanay ng mga estado) ng pag-aari ng ang bagay (phenomenon) na nagpapakilala sa katangian. Kaya, ang kasalukuyang halaga ng variable na "temperatura ng pasyente" ay maaaring 37.4°, at ang variable na "kasarian ng pasyente" ay maaaring "lalaki". Sa madaling salita, ang value ng attribute ay ginagamit upang kumatawan sa halaga ng kaukulang property ng entity.

Mayroong ilang mga uri ng mga katangian depende sa mga uri ng mga halaga na maaari nilang magkaroon. Ang pinakakaraniwang uri ng props, gayunpaman, ay numero at teksto.

Ang mga detalye ng uri ng numero ay nagpapakilala sa dami ng mga katangian ng mga entidad na nakuha bilang resulta ng pagbibilang ng mga natural na yunit, pagsukat, pagtimbang, mga kalkulasyon batay sa iba pang dami ng data, atbp. Samakatuwid, ang mga halaga ng naturang mga detalye ay mga numero kasama ang lahat ng kanilang katangian mga katangian at katangian.

Sa mga partikular na representasyon, lumilitaw ang ilang uri ng mga numerical na dami depende sa klase ng mga numero, sistema ng numero, pag-aayos ng decimal point, packaging at iba pa; ang mga paghihigpit ay ipinapataw sa hanay ng mga numero, ang mga format para sa kanilang representasyon sa input/output at iba't ibang media, kahit na sa loob ng parehong pagpapatupad. Dahil ang lahat ng mga katangian ng uri ng numero ay aktibong ginagamit sa iba't ibang mga pagpapatakbo ng aritmetika, at karamihan sa mga ito ay karaniwang nilikha bilang isang resulta ng mga naturang operasyon, ang mga ipinahiwatig na pagkakaiba at limitasyon ay dapat palaging isaisip, pati na rin ang pangangailangan para sa isang naaangkop na aparato ng conversion.

Ang mga detalye ng uri ng teksto ay nagpapahayag, bilang panuntunan, ng mga katangian ng husay ng mga entidad at nagpapakilala sa mga pangyayari kung saan naganap ang prosesong pinag-aaralan at tiyak o

iba pang mga numerong halaga. Samakatuwid, ang mga naturang detalye ay tinatawag na mga katangian.

Ang mga halaga ng tampok ay mga pagkakasunud-sunod ng mga character (mga titik, numero, iba't ibang mga character at mga espesyal na pagtatalaga), na tinatawag na mga string, o teksto.

Ang kumpletong hanay ng lahat ng posibleng magkapares na makikilalang mga simbolo ng isang ibinigay na sistema ng impormasyon ay bumubuo sa alpabeto nito, depende sa likas na katangian ng mga gawain, ang teknikal na paraan ng pagproseso ng data na ginamit at iba pang mga kadahilanan. Bukod dito, sa iba't ibang yugto ng pagproseso at kahit sa loob ng parehong sistema ng pag-compute, posible na gumamit ng iba't ibang mga alpabeto.

Ang laki ng alpabeto (ang bilang ng iba't ibang simbolo na maaaring nasa isang digit ng halaga) at ang komposisyon nito (set) ay direktang nauugnay sa paglutas ng mga sumusunod na problema:

coding at decryption,

compact na pag-record ng mga halaga ng mga yunit ng impormasyon,

mahusay na pag-iimbak ng data, pagpapabilis ng kanilang paghahanap, paghahatid, pag-input sa mga computer,

pagtanggap ng impormasyon mula sa mga makina sa pinaka-maginhawang paraan para sa pagkonsumo,

pagbabawas ng mga gastos sa lahat ng uri ng muling pagsulat.

Samakatuwid, ang pagpili ng alpabeto ay binibigyan ng malaking kahalagahan.

Upang gumamit ng impormasyon sa algorithmization at programming, napakalaking kahalagahan ay ibinibigay sa mga konsepto tulad ng uri at istraktura ng data.

1. MGA URI NG DATA

Ang proseso ng pag-compute sa isang computer ay ipinatupad, tulad ng nalalaman, sa tulong ng mga programa at data. Ang program mismo ay tumutukoy din sa data. Samakatuwid, maaari nating sabihin na ang data ay naglalarawan ng anumang impormasyon na maaaring magamit ng isang computer. Sa kasong ito, ang impormasyon ay nauunawaan bilang anumang mga katotohanan at kaalaman tungkol sa mga bagay ng totoong mundo, mga proseso at mga relasyon at mga koneksyon sa pagitan nila. Ang lahat ng data ay nailalarawan sa pamamagitan ng isang bilang ng mga katangian (mga tampok, mga detalye), kabilang ang halaga.

Bilang karagdagan sa kahulugan, ang mga naturang tampok ay kinabibilangan ng konsepto ng "uri ng data". Ang uri ng isang datum ay tinutukoy ng hanay ng mga halaga ng datum at ang hanay ng mga operasyon na maaaring isagawa sa mga halagang ito ayon sa kanilang mga kilalang katangian. Samakatuwid, tinutukoy ng uri ng isang ibinigay na halaga ang mga pagpapatakbo na pinapayagan sa katumbas na halaga.

Ang mga programming language ay karaniwang gumagamit ng mga karaniwang uri ng data tulad ng integer, real, character, bit, pointer, atbp.

2. MGA ISTRUKTURA NG DATA

Ang isang tampok ng partikular na uri na ito ay ang pagiging simple ng organisasyon (unstructuredness).

Ang istraktura ng data ay isang koleksyon ng mga elemento ng data kung saan mayroong ilang partikular na relasyon, at ang mga elemento ng data ay maaaring alinman sa simpleng data (scalars) o mga istruktura ng data.

Kaya, ang istraktura ay maaaring tukuyin tulad ng sumusunod: S = (D, R), kung saan ang D ay ang hanay ng mga elemento ng data, ang R ay ang hanay ng mga relasyon sa pagitan ng mga elemento ng data.

Ang lahat ng mga relasyon ng isang elemento ng data sa iba ay bumubuo ng isang elemento ng relasyon na nauugnay sa kaukulang elemento ng data.

Ang isang graphical na representasyon ng isang istraktura ay dapat na sumasalamin sa mga elemento ng data at mga koneksyon nito (mga ugnayan sa pagitan ng mga ito), kaya ito ay maginhawa upang ilarawan ang istraktura bilang isang graph. Sa kasong ito, ang mga vertices ng graph ay maaaring bigyang-kahulugan bilang mga elemento ng data, at ang mga ugnayan sa pagitan ng mga elemento ng data ay tumutugma sa mga naka-orient na arko o hindi naka-orient na mga gilid (Fig. 1).

Ang isang istraktura ng data na inilarawan at kinakatawan sa ganitong paraan ay tinatawag na abstract o lohikal, dahil ito ay isinasaalang-alang nang walang pagsasaalang-alang sa representasyon nito sa memorya ng computer. Ngunit ang anumang istraktura ng data ay dapat na kinakatawan sa memorya ng makina. Ang istraktura ng data na ito ay tinatawag na pisikal na istraktura, istraktura ng imbakan, panloob na istraktura, o istraktura ng memorya.

Fig 1. Hindi nakadirekta (a) at nakadirekta (b) graph

Kaya, ang pisikal na istraktura ng data ay sumasalamin sa paraan ng data ay kinakatawan sa memorya ng computer.

Sa pangkalahatan, mayroong pagkakaiba sa pagitan ng isang lohikal na istraktura at ang kaukulang pisikal na istraktura nito, ang antas nito ay nakasalalay sa istraktura mismo at ang mga katangian ng pisikal na kapaligiran kung saan dapat itong maipakita.

Halimbawa, mula sa punto ng view ng mga programming language, ang isang two-dimensional array ay isang rectangular table, at sa memorya ito ay isang linear sequence ng mga cell, na ang bawat isa ay nag-iimbak ng halaga ng isa sa mga array elements, at ang array elements. ay inayos ayon sa mga row (o column).

Siyempre, dapat mayroong mekanismo sa pagitan ng lohikal at pisikal na istraktura na nagpapahintulot sa lohikal na istraktura na mai-mapa sa pisikal na istraktura.

Kaya, ang bawat istraktura ng data ay maaaring mailalarawan sa pamamagitan ng lohikal (abstract) at pisikal (kongkreto) na representasyon nito, pati na rin ang isang hanay ng mga operasyon sa dalawang antas ng representasyon ng istraktura (Fig. 2).

Mga operasyon sa lohikal na istraktura

Lohikal na istraktura ng data

Mga operasyon sa isang pisikal na istraktura

Istraktura ng pisikal na data

kanin. 2. Pagmamapa sa pagitan ng lohikal at pisikal na representasyon ng istruktura ng data

2.1. Pag-uuri ng mga istruktura ng data

SA Depende sa kawalan o pagkakaroon ng tahasang tinukoy na mga koneksyon sa pagitan ng mga elemento ng data, dapat na makilala ng isa ang pagitan ng mga hindi nauugnay na istruktura (mga vector, array, string, stack, queues) at mga konektadong istruktura (mga naka-link na listahan).

Ang isang mahalagang katangian ng isang istraktura ay ang pagkakaiba-iba nito - isang pagbabago sa bilang ng mga elemento at/o mga koneksyon sa pagitan ng mga elemento ng istraktura. Ang halaga ng elemento ng data ay hindi sinadya, dahil sa kasong ito ang pag-aari na ito ay magiging katangian ng lahat ng mga istruktura ng data, na may posibleng pagbubukod ng mga constant at data na nakaimbak sa ROM. Batay sa pagkakaiba-iba, ang mga static, semi-static at dynamic na istruktura ay nakikilala.

Ang isang mahalagang tampok ng istraktura ng data ay ang pagkakasunud-sunod ng mga elemento nito. Batay sa pamantayang ito, ang mga istruktura ay maaaring hatiin sa linearly ordered, o linear, at nonlinear.

Depende sa likas na katangian ng kamag-anak na pag-aayos ng mga elemento sa memorya, ang mga linear na istruktura ay maaaring nahahati sa mga istruktura na may sunud-sunod na pamamahagi ng kanilang mga elemento sa memorya (mga vector, string, array, stack, queues) at mga istruktura na may arbitrary na konektadong pamamahagi ng mga elemento sa memorya (simpleng konektado, dobleng konektado, paikot na konektado, mga listahan ng asosasyon). Ang mga halimbawa ng mga nonlinear na istruktura ay mga multi-link na listahan, mga istruktura ng puno, at mga istruktura ng pangkalahatang graph.

2.2. Ang pinakasimpleng static na istruktura

SA Ang pinakasimpleng istruktura ng data ay kadalasang kinabibilangan ng mga vector, array, record, at table. Ang mga ito ay nailalarawan sa pamamagitan ng mga sumusunod na katangian:

katatagan ng istraktura sa buong panahon ng pagkakaroon nito;

pagkakaugnay ng mga elemento at pagpapatuloy ng lugar ng memorya na inilaan para sa lahat ng mga elemento ng istraktura nang sabay-sabay at pagiging matatag ng mga relasyon sa pagitan ng mga elemento

mga istruktura na nagbibigay-daan sa iyo na ibukod ang impormasyon tungkol sa mga ugnayang ito mula sa lugar ng memorya na inilaan para sa mga elemento ng istraktura at iimbak ito, halimbawa, sa isang compact na form sa mga descriptor.

Dahil sa mga katangiang ito, ang mga vector, array, talaan at talahanayan ay itinuturing na mga static na istruktura.

2.2.1. Vector

Ang vector ay isang finite ordered set ng simpleng data, o scalar, ng parehong uri. Mula sa isang geometric na punto ng view, ang isang vector ay tumutukoy sa isang punto sa multidimensional na espasyo, ang mga coordinate kung saan ay ang mga halaga ng mga elemento ng vector.

Ang mga elemento ng vector ay nasa tanging posibleng relasyon sa isa't isa - ang relasyon ng agarang sunod. Ang mahigpit na pagkakasunud-sunod ng mga elemento ng vector ay nagbibigay-daan

bilangin ang mga ito ng magkakasunod na integer - mga indeks. Ang lohikal na istraktura ng isang vector ay ganap na inilarawan sa pamamagitan ng bilang at uri ng mga elemento nito. Halimbawa, ang int array ay isang integer array na binubuo ng 10 elemento.

Ang pinakamahalagang operasyon sa isang vector ay ang pag-access sa mga elemento nito. Kapag na-access na ang isang elemento, maaaring gawin dito ang anumang operasyon na may katuturan para sa napiling uri ng data.

Sa lohikal na antas, upang ma-access ang isang elemento ng isang vector, sapat na upang tukuyin ang pangalan ng vector at ang halaga ng index ng kaukulang elemento. Halimbawa: array + array.

Ang pisikal na istraktura ng isang vector ay isang pagkakasunud-sunod ng mga seksyon ng memorya ng pantay na haba, na tinatawag na mga patlang o mga puwang, na ang bawat isa ay idinisenyo upang mag-imbak ng isang elemento ng vector. Ang field ay maaaring ang laki ng pinakamababang addressable memory cell o tumutugma sa isang buong grupo ng magkakasunod na memory cell.

Kadalasan ang isang pisikal na istraktura ay nauugnay sa isang descriptor o header na naglalaman ng impormasyon tungkol sa pisikal na istraktura. Ang deskriptor ay kinakailangan, halimbawa, sa kaso kapag ang mga sukat ng hangganan ng vector ay kilala lamang sa yugto ng pagpapatupad ng programa.

Ang descriptor ay naka-imbak din sa memorya ng makina at isang istraktura na tinatawag na isang talaan. Para sa isang vector, karaniwang iniimbak ng descriptor ang pangalan, laki, mga halaga ng index ng hangganan, uri ng elemento, laki ng field o slot, at ang address ng unang elemento ng vector (ang field na nag-iimbak ng elementong ito).

2.2.2. Array

Ang array ay isang vector kung saan ang bawat elemento ay isang vector. Sa turn, ang mga elemento ng isang vector na isang elemento ng isang array ay maaari ding maging mga vector. Ang proseso ng paglipat mula sa elemento patungo sa elemento ng elementong ito, at iba pa, maaga o huli ay dapat magtapos sa isang scalar ng ilang uri ng data, at lahat ng scalar na elemento ng array ay dapat tumutugma sa ganitong uri (Larawan 3).

kanin. 3. Uri ng multidimensional array

Ipinapakita ng Figure 3 ang hitsura ng isang multidimensional array: ang bawat lattice node ay naglalaman ng array element. Kaya, ang sukat nito ay (3,3,2).

Tulad ng isang vector, ang pinakamahalagang elementarya na operasyon para sa isang array ay ang pag-access sa elemento nito. Sa antas ng lohikal na istraktura, ito ay isinasagawa gamit ang pangalan ng array at isang nakaayos na hanay ng mga indeks na natatanging tumutukoy sa isang elemento ng array. Halimbawa: array[i][j].

Hindi tulad ng isang vector, para sa isang pangkalahatang array ang pagbabago ng isang lohikal na istraktura sa isang pisikal na isa ay may isang mas kumplikadong anyo. Ang pagbabagong ito ay nagagawa sa pamamagitan ng proseso ng linearization na nagmamapa ng multidimensional na lohikal na istraktura ng array sa isang one-dimensional na pisikal na istraktura. Ang pisikal na istrukturang ito ay isang linearly ordered sequence ng array elements. Kaya, ang pisikal na istraktura ng isang multidimensional array ay katulad ng pisikal na istraktura ng isang vector.

Sa kabila nito, ang descriptor para sa isang multidimensional array ay iba sa descriptor para sa isang vector. Halimbawa, dapat itong mag-imbak ng impormasyon tungkol sa laki ng array at ang paraan ng pag-order ng mga elemento (sa pamamagitan ng mga row o column).

2.2.3. Itala

Ang talaan ay isang may hangganang nakaayos na hanay ng mga elemento, sa pangkalahatan ay naglalaman ng data ng iba't ibang uri.

Ang mga elemento ng isang tala ay madalas na tinatawag na mga patlang. Ang talaan ay isang pangkalahatang konsepto ng isang vector na hindi nangangailangan ng pagkakapareho o

Ang konsepto ng istruktura ng data ay napakapangunahing kaya mahirap makahanap ng simpleng kahulugan para dito. Ang gawain ay nagiging mas madali kung susubukan nating bumalangkas ng konseptong ito kaugnay ng mga uri ng data at mga variable. Tulad ng alam mo, ang isang programa ay isang pagkakaisa ng isang algorithm (mga pamamaraan, mga function) at ang data na kanilang pinoproseso. Ang data, sa turn, ay tinukoy ng mga basic at derived na uri ng data - "ideal" na mga representasyon ng mga fixed-dimensional na variable na may mga hanay ng mga kilalang operasyon sa mga ito at sa kanilang mga bahagi. Ang mga variable ay pinangalanang mga lugar ng memorya kung saan ang mga binuong uri ng data ay "nakamapang".
Sa isang programa, palaging posible na makilala ang mga pangkat ng mga hindi direktang nauugnay (sa pamamagitan ng paggamit ng data sa parehong mga pamamaraan at pag-andar) at direktang nauugnay (sa pamamagitan ng pagkakaroon ng mga relasyon sa pamamagitan ng mga pointer) na mga variable. Sa unang pagtataya, maaari silang ituring na mga istruktura ng data.

Mayroong SIMPLE (basic, primitive) na mga istruktura ng data (mga uri) at INTEGRATED (nakabalangkas, pinagsama-sama, kumplikado). Ang mga simpleng istruktura ng data ay ang mga hindi maaaring hatiin sa mga bahaging mas malaki kaysa sa mga piraso. Mula sa punto ng view ng pisikal na istraktura, ang mahalagang katotohanan ay na sa isang naibigay na arkitektura ng makina, sa isang naibigay na sistema ng programming, palagi nating masasabi nang maaga kung ano ang magiging laki ng isang naibigay na simpleng uri at kung ano ang istraktura ng pagkakalagay nito sa. magiging memorya. Mula sa isang lohikal na pananaw, ang simpleng data ay hindi mahahati na mga yunit. Ang pinagsama-sama ay ang mga istruktura ng data na ang mga bahagi ay iba pang mga istruktura ng data - simple o, sa turn, pinagsama. Ang mga pinagsama-samang istruktura ng data ay binuo ng programmer gamit ang mga tool sa pagsasama ng data na ibinigay ng mga programming language.

Depende sa kawalan o pagkakaroon ng mga tahasang tinukoy na koneksyon sa pagitan ng mga elemento ng data, dapat na makilala ng isa ang pagitan ng mga DISCONNECTED na istruktura (mga vector, array, string, stack, queues) at LINKED na istruktura (mga naka-link na listahan).

Ang isang napakahalagang katangian ng isang istraktura ng data ay ang pagkakaiba-iba nito - isang pagbabago sa bilang ng mga elemento at (o) mga koneksyon sa pagitan ng mga elemento ng istraktura. Ang kahulugan ng pagkakaiba-iba ng istraktura ay hindi sumasalamin sa katotohanan na ang mga halaga ng mga elemento ng data ay nagbabago, dahil sa kasong ito ang lahat ng mga istruktura ng data ay magkakaroon ng pag-aari ng pagkakaiba-iba. Batay sa pagkakaiba-iba, ang mga istruktura ay nakikilala: STATIC, SEMI-STATIC, DYNAMIC. Ang pag-uuri ng mga istruktura ng data batay sa pagkakaiba-iba ay ipinapakita sa Fig. 1.1. Ang mga pangunahing istruktura ng data, static, semi-static at dynamic, ay katangian ng RAM at madalas na tinatawag na operational structures. Ang mga istruktura ng file ay tumutugma sa mga istruktura ng data para sa panlabas na memorya.

kanin. 1.1. Pag-uuri ng mga istruktura ng data

Ang isang mahalagang tampok ng istraktura ng data ay ang pagkakasunud-sunod ng mga elemento nito. Batay sa tampok na ito, ang mga istruktura ay maaaring hatiin sa LINEAR AT NON-LINEAR na istruktura.

Depende sa likas na katangian ng kamag-anak na pag-aayos ng mga elemento sa memorya, ang mga linear na istruktura ay maaaring hatiin sa mga istruktura na may CONSISTENT na pamamahagi ng mga elemento sa memorya (mga vector, string, array, stack, queues) at mga istruktura na may ARBITRARY CONNECTED na pamamahagi ng mga elemento sa memorya (simpleng naka-link, dobleng naka-link na mga listahan). Ang isang halimbawa ng mga nonlinear na istruktura ay ang mga multi-link na listahan, mga puno, mga graph.

Sa mga programming language, ang konsepto ng "mga istruktura ng data" ay malapit na nauugnay sa konsepto ng "mga uri ng data". Anumang data, i.e. Ang mga constant, variable, value ng function o expression ay nailalarawan sa pamamagitan ng kanilang mga uri.

Ang impormasyon para sa bawat uri ay malinaw na kinikilala ang:

· 1) istraktura ng imbakan ng data ng tinukoy na uri, ibig sabihin. paglalaan ng memorya at kumakatawan sa data dito, sa isang banda, at pagbibigay-kahulugan sa binary na representasyon, sa kabilang banda;

· 2) ang hanay ng mga pinahihintulutang halaga na maaaring magkaroon ito o ang bagay na iyon ng inilarawang uri;

· 3) isang hanay ng mga wastong operasyon na naaangkop sa isang bagay ng inilarawang uri.

Ang DATA STRUCTURE ay isang set ng pisikal (mga uri ng data) at lohikal (algorithm, function) na magkakaugnay na mga variable at ang kanilang mga halaga.

Tandaan na ang konsepto ng isang istraktura ng data ay nauugnay hindi lamang sa mga variable na bumubuo nito, kundi pati na rin sa mga algorithm (function) na hindi lamang lohikal na ikonekta ang mga variable sa isa't isa, ngunit tinutukoy din ang mga panloob na halaga na dapat ding maging katangian. ng istruktura ng data na ito. Halimbawa, ang isang sequence ng mga positibong value na inilagay sa isang array at pagkakaroon ng variable na dimensyon (data structure) ay maaaring may null delimiter. Ang lahat ng mga operasyon para sa pagbuo at pagsuri sa limiter na ito ay ipinatupad ng mga function. Kaya, maaari nating sabihin na ang isang makabuluhang bahagi ng istraktura ng data ay "hard-wired" sa mga algorithm para sa pagproseso nito.
Ang paraan ng pagtukoy ng mga variable sa pamamagitan ng mga uri ng data na kilala sa amin ay nailalarawan sa pamamagitan ng katotohanan na, una, ang bilang ng mga variable sa programa ay naayos, at pangalawa, ang kanilang dimensyon ay hindi mababago habang tumatakbo ang programa. Kung ang mga ugnayan sa pagitan ng mga variable na ito ay higit pa o hindi gaanong pare-pareho, kung gayon ang mga istruktura ng data ay maaaring tawaging static.

STATIC DATA STRUCTURE - isang set ng isang nakapirming bilang ng mga variable ng pare-pareho ang dimensyon na may hindi nagbabago na likas na katangian ng mga koneksyon sa pagitan nila
Sa kabaligtaran, kung ang isa sa mga parameter ng istruktura ng data—ang bilang ng mga variable, ang kanilang dimensyon, o ang mga ugnayan sa pagitan ng mga ito—ay nagbabago habang tumatakbo ang programa, kung gayon ang mga naturang istruktura ng data ay tinatawag na dynamic.

DYNAMIC DATA STRUCTURE - isang hanay ng mga variable, ang bilang, dimensyon o likas na katangian ng mga relasyon sa pagitan ng mga pagbabago sa panahon ng pagpapatakbo ng programa.

Ang mga istruktura ng dinamikong data ay batay sa dalawang elemento ng programming language:

· mga dynamic na variable, ang bilang ng mga ito ay maaaring magbago at sa huli ay tinutukoy ng mismong programa. Bilang karagdagan, ang kakayahang lumikha ng mga dynamic na array ay nagpapahintulot sa amin na pag-usapan ang tungkol sa data ng mga variable na sukat;

· mga pointer na nagbibigay ng direktang kaugnayan sa pagitan ng data at ng kakayahang baguhin ang mga koneksyong ito.

Kaya, ang sumusunod na kahulugan ay malapit sa katotohanan: ang mga dynamic na istruktura ng data ay mga dynamic na variable at array na naka-link sa pamamagitan ng mga pointer.
Sa pagsasalita tungkol sa mga istruktura ng data, hindi natin dapat kalimutan na ang mga ordinaryong variable ay matatagpuan sa RAM (internal memory ng computer). Samakatuwid, ang mga istruktura ng data ay karaniwang may kinalaman din sa memorya. Gayunpaman, mayroon ding panlabas na memorya, na sa wika ay hindi direktang naa-access sa pamamagitan ng mga operator (Pascal) o mga function (C) na gumagana sa mga file. Sa binary random access mode, ang anumang file ay kahalintulad sa isang walang limitasyong direktang addressable na rehiyon ng memorya, iyon ay, mula sa punto ng view ng programa, ito ay mukhang kapareho ng regular na memorya. Naturally, maaaring kopyahin ng programa ang mga variable mula sa memorya patungo sa isang arbitrary na lokasyon sa file at likod, at samakatuwid ay ayusin ang anumang (kabilang ang mga dynamic) na istruktura ng data sa file.
Ang istruktura ng data ay isang tagapagpatupad na nag-aayos ng trabaho gamit ang data, kabilang ang pag-iimbak nito, pagdaragdag at pagtanggal, pagbabago, paghahanap, atbp. Ang istraktura ng data ay nagpapanatili ng isang tiyak na pagkakasunud-sunod ng pag-access dito. Ang istraktura ng data ay maaaring isipin bilang isang uri ng bodega o library. Kapag naglalarawan ng istraktura ng data, kailangan mong ilista ang hanay ng mga pagkilos na posible para dito at malinaw na ilarawan ang resulta ng bawat pagkilos. Tatawagin namin ang mga naturang aksyon na mga reseta. Mula sa isang programming point of view, ang isang sistema ng mga reseta ng istruktura ng data ay tumutugma sa isang hanay ng mga function na gumagana sa mga karaniwang variable.
Ang mga istruktura ng data ay pinaka-maginhawang ipinatupad sa mga object-oriented na wika. Sa kanila, ang istraktura ng data ay tumutugma sa isang klase, ang data mismo ay naka-imbak sa mga variable ng miyembro ng klase (o ang data ay na-access sa pamamagitan ng mga variable ng miyembro), at isang hanay ng mga pamamaraan ng klase ay tumutugma sa isang sistema ng mga reseta. Bilang isang patakaran, sa mga object-oriented na wika, ang mga istruktura ng data ay ipinatupad sa anyo ng isang library ng mga karaniwang klase: ito ang tinatawag na mga container class ng C++ na wika, kasama sa standard na STL class library, o mga klase na nagpapatupad ng iba't ibang mga istruktura ng data mula sa library ng Java Developer Kit ng wikang Java.
Gayunpaman, ang mga istruktura ng data ay maaaring maipatupad nang matagumpay sa mga tradisyunal na programming language tulad ng Fortran o C. Sa kasong ito, dapat kang sumunod sa isang object-oriented na istilo ng programming: malinaw na tukuyin ang isang hanay ng mga function na gumagana sa istraktura ng data, at limitahan ang pag-access sa data sa hanay lamang ng mga function na ito. Ang data mismo ay ipinatupad bilang static (hindi global) na mga variable. Kapag nagprograma sa wikang C, ang istraktura ng data ay tumutugma sa dalawang file na may mga pinagmulang teksto:
1. header, o h-file, na naglalarawan sa interface ng istruktura ng data, i.e. isang hanay ng mga prototype ng function na naaayon sa isang sistema ng mga reseta ng istruktura ng data;
2. file ng pagpapatupad, o C-file, na tumutukoy sa mga static na variable na nag-iimbak at nag-a-access ng data, at nagpapatupad din ng mga function na tumutugma sa sistema ng mga kinakailangan sa istruktura ng data
Ang istraktura ng data ay karaniwang ipinapatupad batay sa isang mas simpleng istraktura ng base na ipinatupad na, o batay sa isang array at isang hanay ng mga simpleng variable. Ang isang malinaw na pagkakaiba ay dapat gawin sa pagitan ng paglalarawan ng isang istraktura ng data mula sa isang lohikal na punto ng view at paglalarawan ng pagpapatupad nito. Maaaring magkaroon ng maraming iba't ibang mga pagpapatupad, ngunit mula sa isang lohikal na pananaw (i.e. mula sa punto ng view ng isang panlabas na gumagamit), lahat sila ay katumbas at naiiba, marahil, sa bilis lamang ng pagpapatupad ng mga tagubilin.

Ang isang kinakailangang kondisyon para sa pagbuo ng isang algorithm ay pormalisasyon ng datos, ibig sabihin. pagbabawas ng impormasyon sa ilan modelo ng impormasyon(cm." Mga modelo ng impormasyon"), inilarawan at pinag-aralan na. Kapag natagpuan ang ganitong modelo, sinasabing ito ay tinukoy abstract na istraktura ng data.

Abstract na istraktura ng data naglalarawan ng mga katangian at katangian ng isang bagay, relasyon sa pagitan ng mga elemento ng bagay, hangga't maaari mga operasyon sa isang ibinigay na bagay o klase ng mga bagay.

Isa sa mga gawain ng computer science ay ang paghahanap ng mga anyo ng representasyon ng impormasyon na maginhawa para sa pagpoproseso ng computer. Ang agham ng computer bilang isang eksaktong agham ay gumagana sa mga pormal na (mahigpit na inilarawan sa matematika) na mga bagay. Ang ganitong mga bagay - basic abstract na mga istruktura ng data ginagamit sa computer science ay:

· mga integer;

· tunay na mga numero;

· mga simbolo;

· lohikal na mga halaga.

Para sa pagpoproseso ng computer ng mga bagay na ito sa mga programming language, mayroong naaangkop mga uri ng data(cm." Mga Uri ng Data"). Ang mga pangunahing bagay ay maaaring pagsamahin sa mas kumplikadong mga istruktura sa pamamagitan ng pagdaragdag ng mga operasyon sa istraktura sa kabuuan at pag-access ng mga panuntunan sa mga indibidwal na elemento ng abstract na istraktura ng data na ito.

Ang mga abstract na istruktura ng data na ito ay kinabibilangan ng:

· mga vectors (may hangganan na array);

· mga talahanayan (matrices), at sa pangkalahatang kaso - multidimensional array;

· mga dynamic na istruktura:

Pagkakasunud-sunod ng mga simbolo, numero;

Mga pila;

mga puno;

Ang matagumpay na pagpili ng istraktura ng data ay madalas na susi sa paglikha ng isang epektibong algorithm at isang programa na nagpapatupad nito: gamit ang pagkakatulad ng mga istruktura ng data at mga tunay na bagay, makakahanap ka ng mga epektibong solusyon sa mga problema.

Tandaan na ang mga nakalistang istruktura ay umiiral anuman ang kanilang pagpapatupad sa panahon ng programming. Nagtrabaho sila sa mga istruktura ng data na ito noong ika-18 at ika-19 na siglo, noong hindi pa naimbento ang computing machine. Maaari kaming bumuo ng isang algorithm sa mga tuntunin ng isang abstract na istraktura ng data, ngunit upang ipatupad ang algorithm sa isang partikular na programming language kailangan naming makahanap ng isang paraan upang kumatawan ito sa mga tuntunin mga uri ng data At mga operator suportado ng programming language na ito (tingnan ang " Mga operator ng programming language"). Para sa representasyon ng computer ng mga abstract na istruktura, ginagamit namin mga istruktura ng datos, na isang hanay ng mga variable, posibleng may iba't ibang uri ng data, na pinagsama sa isang tiyak na paraan. Upang makabuo ng mga istruktura tulad ng vector, table, string, sequence, karamihan sa mga programming language ay may pamantayan mga uri ng data: one-dimensional array, two-dimensional array, string, file (mas madalas isang listahan), ayon sa pagkakabanggit. Organisasyon ng iba pang mga istruktura ng data, una sa lahat mga dinamikong istruktura, ang laki ng pagbabago sa panahon ng pagpapatupad ng programa, ang programmer ay kailangang ipatupad nang nakapag-iisa, gamit ang mga pangunahing uri ng data. Isaalang-alang natin ang mga naturang istruktura nang mas detalyado.

Mga listahan

Linear na listahan- isang pagkakasunud-sunod ng mga linear na nauugnay na elemento kung saan pinapayagan ang mga operasyon ng pagdaragdag ng mga elemento sa isang arbitrary na lugar sa listahan at pagtanggal ng anumang elemento. Ang isang linear na listahan ay natatanging kinilala sa pamamagitan ng isang pointer sa simula ng listahan. Ang mga karaniwang operasyon sa mga listahan ay: pagtawid sa isang listahan, paghahanap para sa isang partikular na elemento, pagpasok ng isang elemento kaagad pagkatapos o bago ang isang partikular na elemento, pagtanggal ng isang partikular na elemento, pagsasama-sama ng dalawang listahan sa isa, paghahati ng isang listahan sa dalawa o higit pang mga listahan, atbp.

Sa isang linear na listahan para sa bawat elemento maliban una, Meron dati elemento; para sa bawat elemento maliban huli, Meron susunod elemento. Kaya, ang lahat ng mga elemento ng listahan ay iniutos. Gayunpaman, ang pagproseso ng isang linear na single linked na listahan ay hindi palaging maginhawa, dahil walang posibilidad na lumipat sa kabilang direksyon - mula sa dulo ng listahan hanggang sa simula. Sa isang linear na listahan, maaari mong lampasan ang lahat ng mga elemento sa pamamagitan lamang ng paglipat ng sunud-sunod mula sa kasalukuyang elemento patungo sa susunod, simula sa una, direktang pag-access sa i ang ika- elemento ay imposible.

Halimbawa 1. Ang pagkakasunud-sunod ng mga talaan ng mga pangalan ng mga mambabasa sa computer ng librarian ay tumutukoy sa "nakaraang-susunod" na relasyon. Bilang isang patakaran, ang mga rekord mismo ay may karagdagang pag-aari - ang mga ito ay inayos ayon sa alpabeto. Ang mga operasyon ng pagdaragdag ng bagong mambabasa at, kung kinakailangan, ang pagtanggal ng luma ay ipinatupad sa listahang ito. Kung, bilang karagdagan, ang mga talaan ng mga aklat na ibinigay sa bawat mambabasa, kung gayon ito ay maginhawa upang katawanin ang bawat ganoong talaan, muli gamit ang isang listahan ng mga aklat na ibinigay.

Mga listahan ng ring- ang parehong istraktura bilang isang linear na listahan, ngunit may karagdagang koneksyon sa pagitan ng huli at unang elemento, iyon ay, ang susunod na elemento pagkatapos ng huling elemento ay ang unang elemento.

Sa isang pabilog na listahan kumpara sa isang linear lahat ng elemento ay pantay(dahil para sa bawat elemento pareho ang nauna at susunod na mga elemento ay tinukoy). Ang pagpili ng "una" at "huling" elemento sa isang listahan ng singsing ay napaka-arbitrary, dahil sa katunayan ang istraktura ng listahan ay walang tahasang inilalaan na mga elemento!

Halimbawa 2. Sa maraming laro, ang mga bata ay gumagamit ng mga counter para pumili ng pinuno, hatiin sa mga koponan, atbp. Bilang isang patakaran, ang mga counter ay mahaba, at ang mga bata (nang hindi alam ang kanilang sarili) ay nag-aayos ng isang pabilog na listahan. Ang "nakaraang-susunod" na relasyon ay tinutukoy kung aling direksyon ang binibilang ng pinuno. Ang isang karaniwang operasyon sa naturang istraktura ay ang pag-alis ng isang elemento mula sa listahan habang pinapanatili ang pabilog na istraktura nito.

Ang mga linear na listahan, kung saan ang mga pagpapatakbo ng pagpasok, pagtanggal, at pag-access sa mga halaga ng elemento ay ginaganap lamang sa mga pinakamalabas na elemento (una o huli), ay nakatanggap ng mga espesyal na pangalan.

salansan- isang espesyal na kaso ng isang linear na single linked na listahan kung saan ang dalawang operasyon ay tinukoy: pagdaragdag ng isang elemento sa tuktok ng stack (bago ang unang elemento) at pag-alis ng isang elemento mula sa tuktok ng stack (pag-alis ng unang elemento).

Halimbawa 3. Isaalang-alang natin ang problema sa pagtukoy ng balanse ng mga panaklong ng iba't ibang uri sa isang pagpapahayag ng aritmetika. Halimbawa, gusto mong suriin kung ang mga panaklong sa isang expression na naglalaman ng mga panaklong at mga square bracket ay balanse: ? Upang malutas ang problemang ito, gagamitin namin ang isang dynamic na istraktura datos salansan. Magpakita tayo ng isang algorithm para sa paglutas ng problemang ito nang sunud-sunod. Gagamitin namin ang sumusunod na notasyon:

i- numero ng nasuri na simbolo;

n- ang bilang ng mga character sa expression.

1. i = 0.

2. i = i + 1.

3. Kung in, pagkatapos ay pumunta sa hakbang (4), kung hindi, kung ang stack ay walang laman, pagkatapos ay ipapakita namin ang mensaheng "Brackets are balanced," kung hindi man ay ipinapakita namin ang mensaheng " hindi balanse ang mga bracket" Pagtatapos ng algorithm.

4. Kung i Ang ika- simbolo ay iba sa mga simbolo ng bracket, pagkatapos ay pumunta sa hakbang (2).

5. Kung i Ang ika-simbolo ay katumbas ng "(" o "[", pagkatapos ay ilagay namin ito sa stack, pumunta sa hakbang (2).

6. Kung i Ang ika-th na simbolo ay ")", pagkatapos ay suriin namin ang tuktok ng stack: kung mayroong "(" sa tuktok ng stack, pagkatapos ay alisin namin ito mula sa stack; pumunta sa hakbang (2), kung hindi, ipinapakita namin ang mensahe “ hindi balanse ang mga bracket" Pagtatapos ng algorithm.

7. Kung i Ang ika-na character ay "]", pagkatapos ay suriin namin ang tuktok ng stack: kung mayroong "[" sa tuktok ng stack, pagkatapos ay alisin namin ito mula sa stack; pumunta sa hakbang (2), kung hindi ay ipapakita namin ang mensaheng “ hindi balanse ang mga bracket" Pagtatapos ng algorithm.

Nakapila- isang espesyal na kaso ng isang linear na single linked na listahan kung saan dalawang operasyon lang ang pinapayagan: pagdaragdag ng elemento sa dulo (buntot) ng queue at pag-alis ng elemento mula sa simula (head) ng queue.

Ang konsepto ng isang pila ay talagang napakalapit sa pang-araw-araw na terminong "pila". Ang isang pila ng mga customer sa isang tindahan ay mahusay na inilarawan sa mga tuntunin ng istraktura ng data na ito.

Mga puno

Puno ay isang koleksyon ng mga elemento na tinatawag na mga node, kung saan napili ang isang elemento ( ugat), at ang natitirang mga elemento ay nahahati sa magkahiwalay na mga hanay (mga subtree), bawat isa ay isang puno, at ang ugat ng bawat subtree ay inapo ang ugat ng puno, i.e. lahat ng elemento ay magkakaugnay ng isang relasyon (ancestor–descendant). Bilang isang resulta, ang isang hierarchical na istraktura ng mga node ay nabuo. Ang mga node na walang anak ay tinatawag dahon. Ang mga sumusunod na operasyon ay tinukoy sa puno: pagdaragdag ng elemento sa puno, pag-alis ng elemento mula sa puno, pagtawid sa puno, paghahanap ng elemento sa puno.

Halimbawa 4. Ang isang puno ay ang pinaka-maginhawang istraktura ng data para sa kumakatawan sa isang puno ng pamilya, na maaaring magamit upang malutas ang mga problema sa pagtukoy ng antas ng relasyon sa pagitan ng dalawang tao.

Ginagamit din ang mga puno upang matukoy ang mga diskarte sa panalong sa mga laro (tingnan ang artikulong " Mga laro. Mga Istratehiya sa Panalong"), at para sa pagbuo ng iba't ibang modelo ng impormasyon (tingnan ang " Mga modelo ng impormasyon”).

Ang isang partikular na mahalagang papel sa computer science ay nilalaro ng tinatawag na binary puno.

Binary tree- isang espesyal na kaso ng isang puno kung saan ang bawat node ay maaaring magkaroon ng hindi hihigit sa dalawang inapo, na siyang mga ugat ng kaliwa at kanang subtree.

Kung, bilang karagdagan, ang kondisyon ay nasiyahan para sa mga node ng puno na ang lahat ng mga halaga ng mga elemento ng kaliwang subtree ay mas mababa kaysa sa halaga ng ugat ng puno, at ang lahat ng mga halaga ng mga elemento ng kanang subtree ay mas malaki kaysa sa halaga ng ugat, kung gayon ang gayong puno ay tinatawag binary search tree at idinisenyo upang mabilis na maghanap ng mga elemento. Ang algorithm ng paghahanap sa naturang puno ay gumagana tulad nito: ang hinahanap na halaga ay inihambing sa halaga ng ugat ng puno, at depende sa resulta ng paghahambing, ang paghahanap ay matatapos o magpapatuloy lamang sa kaliwa o sa kanan lamang subtree, ayon sa pagkakabanggit. Ang kabuuang bilang ng mga operasyon ng paghahambing ay hindi lalampas sa tinatawag na taas ng puno- ang maximum na bilang ng mga elemento sa landas mula sa ugat ng puno hanggang sa isa sa mga dahon. Kaya, ang taas ng puno na ipinapakita sa figure ay 4.

Mga graph

Graph ay isang hanay ng mga elemento na tinatawag mga taluktok graph kasama ang isang hanay ng mga ugnayan sa pagitan ng mga vertex na ito, na tinatawag na tadyang graph. Ang isang graphical na interpretasyon ng istruktura ng data na ito ay isang hanay ng mga punto na tumutugma sa mga vertices, ang ilang mga pares ay konektado sa pamamagitan ng mga linya o arrow na tumutugma sa mga gilid. Sa huling kaso, ang graph ay tinatawag nakatuon(tingnan din ang mga artikulo " Mga graphic na modelo"At" Mga Modelong Tabular”).

Dahil sa ang katunayan na ang mga bagay ng di-makatwirang istraktura ay maaaring ilarawan gamit ang mga graph, ang mga graph ay ang pangunahing paraan para sa paglalarawan ng mga istruktura ng mga kumplikadong bagay at ang paggana ng mga system. Halimbawa, upang ilarawan ang isang computer network, isang transport system, isang hierarchical na istraktura (isang puno ay isa sa mga uri ng graph). Mga flowchart ng algorithm (tingnan ang " Mga paraan upang magsulat ng mga algorithm”) ay mga graph din.

Kung ang bawat gilid ay bibigyan din ng isang tiyak na numero ( timbang), pagkatapos ay tinatawag ang gayong graph natimbang. Halimbawa, kapag inilalarawan ang sistema ng kalsada ng Russia gamit ang isang graph, ang haba ng kalsada (ang bigat ng gilid ng graph) na kumukonekta sa ilang mga settlement (mga vertices ng graph) ay mahalaga. Bukod dito, sa figure, ang mga haba ng kaukulang mga gilid ay hindi kailangang tumugma sa mga timbang na itinalaga sa kanila, hindi tulad ng isang mapa ng kalsada.

Halimbawa 5. Ito ay maginhawa upang malutas ang sumusunod na problema sa mga tuntunin ng isang timbang na graph. Gumagawa ang gobyerno ng Russia ng isang plano na magtayo ng mga modernong highway na nag-uugnay sa mga lungsod na may populasyon na higit sa isang milyong tao. Anong uri ng mga kalsada ang dapat itayo upang mula sa alinmang naturang lungsod ang isa ay makarating sa alinmang iba pa sa pamamagitan ng mga bagong highway, at ang kabuuang haba ng mga kalsada ay magiging minimal?

Ang problemang ito sa teorya ng graph ay may simple at eksaktong solusyon. Maaari naming simulan ang pagpaplano ng network ng kalsada, simula sa anumang lungsod, halimbawa, St. Petersburg. Ikonekta natin ito sa pinakamalapit na milyon-plus na lungsod. Susunod, sa bawat hakbang, ang pinakamaikling kalsada ay idinagdag sa umiiral na network, na maaaring kumonekta sa isang lungsod na hindi pa konektado sa network sa isa sa mga lungsod na kasama na sa network. Ang bilang ng mga kalsada ay magiging mas mababa ng isa kaysa sa bilang ng mga lungsod.

Ang isang abstract na istraktura ng data - isang graph - ay maaaring katawanin sa isang programa sa maraming paraan, i.e. gamit ang iba't ibang uri ng data. Halimbawa, ang isang graph ay maaaring ilarawan gamit ang isang listahan ng mga gilid, na tumutukoy sa bawat gilid na may isang pares ng mga vertex at, opsyonal, isang timbang. Ang imbakan ng tabular graph ay naging pinakalaganap (tingnan ang " Mga Modelong Tabular"), tinatawag din adjacency matrix, ibig sabihin. isang two-dimensional array, sabihin A, kung saan para sa isang hindi timbang na graph (o 1), kung ang gilid sa pagitan ng mga vertices i At j umiiral, at (o 0) kung hindi man. Para sa isang weighted graph A[i][j Ang ] ay katumbas ng bigat ng katumbas na gilid, at ang kawalan ng gilid sa ilang mga problema ay madaling tinutukoy ng infinity. Para sa mga hindi direktang graph, ang adjacency matrix ay palaging simetriko tungkol sa pangunahing dayagonal ( i = j). Gamit ang adjacency matrix, madaling suriin kung may gilid sa graph na nagkokonekta sa isang vertex i may tuktok j. Ang pangunahing kawalan nito ay ang adjacency matrix ay nangangailangan na ang dami ng memorya ay sapat upang maiimbak N 2 mga halaga para sa isang graph na naglalaman ng N vertices, kahit na may mas kaunting mga gilid sa graph kaysa sa N 2 .

Kapag nagpapaliwanag ng konsepto mga istruktura ng datos Maaari mong gamitin ang sumusunod na paglalarawan.

Kapag nilulutas ang anumang problema, kailangang makipagtulungan datos at pagsasagawa ng mga operasyon sa kanila. Ang hanay ng mga operasyong ito para sa bawat gawain, sa pangkalahatan, ay iba. Gayunpaman, kung ang isang tiyak na hanay ng mga operasyon ay madalas na ginagamit upang malutas ang iba't ibang mga problema, kung gayon ito ay kapaki-pakinabang na makabuo ng isang paraan upang ayusin ang data na nagbibigay-daan sa iyo upang maisagawa ang mga partikular na operasyong ito nang mahusay hangga't maaari. Matapos maimbento ang gayong pamamaraan, kapag nilulutas ang isang tiyak na problema, maaari nating ipagpalagay na mayroon tayong "itim na kahon" (tatawagin natin itong istraktura ng data), tungkol sa kung saan kilala na ang data ng ilang uri ay nakaimbak dito, at maaaring magsagawa ng ilang operasyon sa data na ito. Nagbibigay-daan ito sa iyo na makatakas mula sa mga detalye at tumuon sa mga partikular na tampok ng gawain. Sa loob (i.e., sa isang computer) ang "itim na kahon" na ito ay maaaring ipatupad sa iba't ibang paraan, ngunit ang isa ay dapat magsikap para sa pinaka mahusay (mabilis at memory-efficient) na pagpapatupad hangga't maaari.

Ang pamantayang pang-edukasyon ng estado ay nagbibigay para sa pag-aaral ng iba't ibang istruktura ng data kapwa sa pangunahing kurso ng elementarya at sa mataas na paaralan. Sa basic school programming course, binabanggit ng Sample Program ang mga chain ng character (strings), numero, listahan, puno, at graph bilang mga naprosesong bagay. Gayunpaman, sa mga praktikal na gawain, isang array lamang ang binanggit mula sa data ng isang kumplikadong istraktura (tingnan ang artikulong " Array Operations"). Sa pangunahing paaralan, tila makatuwirang pag-aralan muna ang natitirang mga istruktura kapag gumagawa ng mga graphical at iba pang mga modelo (tingnan ang seksyon IV ng encyclopedia).

Ang isang tinatayang programa para sa isang dalubhasang paaralan ay nagsasangkot ng pagtatrabaho sa mga numero, matrice, string, listahan, at puno. Bilang isang simpleng paglalarawan ng pagtatrabaho sa mga listahan, maaari mong piliing ayusin ang stack gamit ang isang one-dimensional na array at isang integer variable na tumuturo sa tuktok ng stack ("ang ibaba" ng stack ay palaging nasa unang elemento ng array ). Bilang karagdagan sa problema ng pagsuri sa mga panaklong para sa balanse na ibinigay sa artikulo, maaari mong pag-aralan ang pagpapatakbo ng isang stack calculator gamit ang halimbawa ng isang algorithm para sa pag-convert ng isang arithmetic expression sa reverse Polish notation ( postfix recording) mula sa nakasanayan natin infix pagtatala at karagdagang pagkalkula ng halaga ng isang arithmetic expression.

Ang isang binary tree ay maaari ding madaling ilarawan sa memorya ng computer gamit ang isang one-dimensional array, na ang unang elemento ng array ay nag-iimbak ng ugat ng puno, at ang mga inapo ng tree node ay naka-imbak sa i-th elemento ng array ay matatagpuan sa 2 i-m at (2 i+ 1)th elemento, ayon sa pagkakabanggit. Kung ang isang node ay walang inapo, ang katumbas na elemento ay magiging katumbas ng, halimbawa, 0. Recursive tree traversal procedure t at ang pag-print ng mga elemento nito sa kasong ito ay magiging ganito:

procedure order(i:integer);

kung t[i]<> 0 pagkatapos

Mababasa mo ang tungkol sa pagpapatupad ng mga listahan at array gamit ang mga dynamic na variable, halimbawa, sa classic na aklat ni N. Wirth na "Algorithms and Data Structures."

Kasama rin sa programa para sa dalubhasang paaralan ang mga graph algorithm. Sa partikular, binabanggit nito ang paghahanap ng pinakamaikling landas sa isang graph. Para sa isang walang timbang na graph, maaaring malutas ang problemang ito, halimbawa, gamit ang algorithm na "breadth-first search", kapag unang minarkahan ang mga vertex ng graph na konektado ng isang gilid sa orihinal na vertex, pagkatapos ay ang lahat ng vertex na konektado sa mga minarkahan, atbp . Para sa isang timbang na graph, ang algorithm ng Dijkstra ay kadalasang ginagamit (tingnan, halimbawa, ang artikulo ni E.V. Andreeva "Olympiads in Informatics. Paths to the Top", "Informatics" No. 8/2002). Ang kaalaman sa naturang mga algorithm ay kinakailangan upang matagumpay na malutas ang mga problema sa Olympiad sa computer science. Kaya, sa IV federal district stage ng All-Russian Olympiad sa Informatics noong 2007, ang problemang "Trenches and Trenches" ay iminungkahi, na ang solusyon ay bumagsak sa paghahanap ng pinakamaikling landas sa isang weighted graph.

Sa una, ang proseso ng programming ay kasangkot sa programmer na sumulat ng lahat ng mga algorithm nang direkta sa machine language. Ang diskarte na ito ay idinagdag sa mahirap nang gawain ng pagbuo ng mga algorithm at masyadong madalas na nagresulta sa mga error na kailangang matuklasan at itama [isang proseso na kilala bilang pag-debug] bago maituring na kumpleto ang gawain.

Ang unang hakbang tungo sa pagpapadali ng gawain ng programming ay ang paghinto sa paggamit ng mga numero upang direktang magsulat ng mga tagubilin at operand sa anyo kung saan ginagamit ang mga ito sa makina. Para sa layuning ito, kapag bumubuo ng mga programa, ang mnemonic notation ng iba't ibang mga command ay nagsimulang malawakang gamitin sa halip na ang kanilang hexadecimal na representasyon. Halimbawa, sa halip na ang digital code para sa load register command, ang programmer ay maaari na ngayong sumulat ng LOD, at sa halip na ang code para sa copy register command sa memorya, ang programmer ay maaaring gumamit ng mnemonic STO. Para sa pagsusulat ng mga operand, ang mga panuntunan ay binuo ayon sa kung saan ang programmer ay maaaring magtalaga ng mga mapaglarawang pangalan sa ilang mga lugar ng memorya [madalas na tinatawag na mga identifier] at gamitin ang mga ito kapag nagsusulat ng mga tagubilin ng programa sa halip na ang mga address ng kaukulang memory cell. Ang ganitong mga identifier ay karaniwang tinatawag na variable. Binibigyang-diin nito na kapag binago namin ang halagang inilalaan sa isang ibinigay na lokasyon ng memorya, binabago namin ang halagang nauugnay sa identifier na itinalaga sa lokasyong iyon sa panahon ng pagpapatupad ng programa.

Kapag ang isang variable ay idineklara sa isang programa, ang uri nito ay karaniwang tinutukoy sa parehong oras. Tinutukoy ng uri ng data ang parehong interpretasyon ng partikular na data at ang mga operasyong maaaring gawin dito. Kasama sa mga uri ng data ang Integer, Real, Character, at Boolean.

Ang uri ng Integer ay ginagamit upang kumatawan sa numeric na data na isang integer. Sa memorya ang mga ito ay madalas na kinakatawan sa binary's complement code. Maaari kang magsagawa ng mga normal na aritmetika at pagpapatakbo ng paghahambing sa data ng Integer.

Ang totoong uri ay nilayon na kumatawan sa numeric na data na maaaring maglaman ng mga hindi integer na halaga. Karaniwang nakaimbak ang mga ito sa memorya bilang mga binary floating point na numero. Ang mga pagpapatakbo na maaaring isagawa sa Real data ay kapareho ng mga maaaring isagawa sa Integer data. Gayunpaman, ang mga pagmamanipula na kinakailangan upang magdagdag ng dalawang elemento ng Real data ay iba sa mga manipulasyon na kinakailangan upang maisagawa ang mga operasyon sa mga variable na Integer.

Ang uri ng Character ay ginagamit para sa data na binubuo ng mga character na naka-imbak sa memorya bilang ASCII o UNICODE code. Ang data ng ganitong uri ay maihahambing sa isa't isa [matukoy kung alin sa dalawang character ang mauuna sa isa pa sa alpabetikong pagkakasunud-sunod]; suriin kung ang isang string ng mga character ay isa pa, at pagsamahin din ang dalawang mga string sa isa, mas mahabang string, pagdaragdag ng isa sa mga ito pagkatapos ng isa pa [concatenation operation].

Ang Boolean ay tumutukoy sa data na maaari lamang kumuha ng dalawang value: True at False. Ang isang halimbawa ng naturang data ay ang resulta ng isang paghahambing na operasyon sa pagitan ng dalawang numero. Kasama sa mga operasyon sa Boolean data ang pagsuri kung True o False ang kasalukuyang value ng variable.

Ang pangunahing memorya ng makina ay nakaayos sa anyo ng magkahiwalay na mga cell na may sunud-sunod na pagtaas ng mga address. Gayunpaman, ang mga cell na ito ay kadalasang ginagamit bilang batayan para sa pagpapatupad ng iba pang mga paraan ng pag-iimbak ng data. Halimbawa, ang teksto ay karaniwang tinitingnan bilang isang mahabang string ng mga character, habang ang impormasyon sa pagbebenta ay maaaring tingnan bilang isang parihabang talahanayan na may mga numerong halaga, bawat isa ay kumakatawan sa bilang ng mga transaksyon na nakumpleto ng isang partikular na empleyado sa isang partikular na araw. Ang layunin ay upang bigyan ang gumagamit ng isang paraan upang manipulahin ang mga abstract na istruktura, sa halip na suriin ang mga detalye ng aktwal na organisasyon ng data sa pangunahing memorya ng makina. Upang magamit nang tama ang isang computer, dapat kang magkaroon ng isang mahusay na kaalaman sa mga istrukturang relasyon sa pagitan ng data, ang mga pangunahing pamamaraan ng kumakatawan sa mga istruktura sa loob ng computer, pati na rin ang mga paraan ng pagtatrabaho sa kanila. Ang mga sumusunod na istruktura ng impormasyon ay ginagamit para sa mga koneksyon sa pagitan ng data sa isang computer: array, record, list, tree, stack, queue.

Mga array

Ang array ay isang istraktura na naglalaman ng ilang elemento ng parehong uri. Ginagamit ang mga index upang mag-order ng mga elemento ng array. Ang mga index ay isinusulat sa panaklong pagkatapos ng pangalan ng array. Ang isang array na may isang index ay tinatawag na one-dimensional, na may dalawang - two-dimensional, atbp.

Itala

Ang talaan ay isang istraktura na binubuo ng mga elemento na hindi kinakailangang magkapareho ang uri. Ang mga indibidwal na elemento ng isang talaan ay tinatawag na mga patlang. Ang patlang, sa turn, ay maaari ding maging isang talaan.

itala ang Mag-aaral (
Pangalan,
Apelyido,
Grupo
)

Mga listahan

Ang isang listahan ay isang hanay ng mga talaan, ang bawat isa ay naglalaman ng isang espesyal na field - isang index. Ang isang pointer ay nagli-link ng isang tala sa ilang iba pang tala o naglalaman ng isang Null na halaga, na nagpapahiwatig na ang halaga ng pointer ay hindi natukoy.

Ang mga entry sa isang solong naka-link na listahan ay may isang pointer, at sila ay konektado sa isang chain:

Ang arrow sa figure ay nagpapahiwatig ng mga nilalaman ng pointer, at ang salitang Data ay tumutukoy sa koleksyon ng mga field kung saan naka-imbak ang data. Ang isang listahan ay maaaring ayusin gamit ang isang two-dimensional array, ang lahat ng mga elemento kung saan ang unang index ay katumbas ng 0 ay inilaan upang mag-imbak ng data, at lahat ng mga elemento na may unang index na katumbas ng 1 ay mga pointer.

Sa listahang ito, ang mga entry na naglalaman ng mga titik ng alpabetong Ingles ay nakaayos sa pagkakasunud-sunod ng alpabeto. Ang unang entry sa listahan ay naglalaman ng character na "A", ang pangalawa - "B", atbp.

Upang gumana sa isang listahan kailangan mong magawa ang tatlong pangunahing operasyon:

Pass() - pagtawid o paglipat kasama ang listahan;
Add() - pagdaragdag ng bagong entry sa listahan;
Delete() - nag-aalis ng entry mula sa listahan.

Bilang karagdagan sa mga pagpapatakbo, ang pagtatrabaho sa isang listahan ay nangangailangan ng dalawa pang variable:

Head variable, na nag-iimbak ng impormasyon tungkol sa unang entry sa listahan
Kasalukuyang variable, na tumuturo sa kasalukuyang entry sa listahan

Ang talahanayan ay nagbubuod ng mga paglalarawan ng ilang mga operasyon sa isang listahan, isang halimbawa ng pagpapatupad na ibinigay sa itaas.

Pangalan ng operasyon	Pseudocode
Ibaba ang listahan ng isang hakbang	function Pass(Kasalukuyan) ( kung (M Null) pagkatapos ay Kasalukuyan:=M; return(Kasalukuyan); }
	function Add(Kasalukuyan, Bago) ( M:= M; M:=Bago; bumalik; }
Idagdag sa listahan ang entry na itinuro ng Bagong variable	function na Tanggalin(Kasalukuyan) ( kung (M Null) kung gayon M:=M]; bumalik; }

Ang mga entry sa isang dobleng naka-link na listahan ay pinagsama-sama, ngunit may dalawang pointer na field. Ang isa sa kanila ay tumuturo sa nakaraang elemento sa listahan, ang isa sa susunod na elemento. Ang istrukturang ito ay nagpapahintulot sa iyo na lumipat sa listahan sa dalawang direksyon: pasulong at paatras.

Ang isang listahan na ang huling entry ay tumuturo sa una ay tinatawag na isang circular list. Walang entry na may null pointer sa mga listahang ito.

Ang puno ay isang branched na listahan, ang bawat entry ay maaaring maglaman ng ilang pointer. Ang mga entry na kasama sa puno ay tinatawag na mga node. Ang mga node na ang mga pointer ay walang laman ay tinatawag na dahon. Ang tuktok na panimulang node ng puno ay tinatawag na root node. Sa maraming problema, sapat na ang paggamit ng mga binary tree, na ang mga node ay hindi hihigit sa dalawang pointer.

Halimbawa. Kailangan mong kalkulahin ang mathematical expression (3+7)*(2/(3-1)). Isipin natin ang expression na ito bilang isang puno:

Ang bawat node ng punong ito ay isang talaan ng sumusunod na anyo:

record Node (
Operasyon
Numero
LeftPointer
RightPointer
)

Ang mga dahon ng puno ay naglalaman ng mga numero, ang natitirang mga node ay naglalaman ng mga simbolo ng mga operasyon.

Ang pagkakaroon ng pagpapatupad ng inilarawan na puno sa isang dalawang-dimensional na hanay, nakuha namin ang sumusunod na larawan:

Upang kalkulahin ang halaga ng isang puno, kailangan mong kalkulahin ang mga halaga ng kanan at kaliwang subtree, at pagkatapos ay isagawa ang resultang operasyon sa kanila. Ang pseudocode ng algorithm na lumulutas sa problema ay magiging ganito:

function na Kalkulahin (Kasalukuyan) (
kung (M=Null) kung gayon
Resulta:= M;
iba pa(
R1:=Kalkulahin(M);
R2:=Kalkulahin(M);
Resulta:=R1(M)R2;
}
bumalik (Resulta);
}

Ang stack ay isang istraktura ng data na nakaayos sa isang last-in, first-out na batayan. Ang data na nakaimbak sa stack ay ina-access sa itaas. Ang data ay itinutulak sa stack nang sunud-sunod.

Kapag nagtatrabaho sa isang stack, dalawang sitwasyong pang-emergency ang posible: isang pagtatangka na basahin ang data mula sa isang walang laman na stack; isang pagtatangkang itulak ang isang elemento sa stack kapag ang bilang ng mga elemento sa stack ay umabot sa maximum na pinapayagang numero.

Ang queue ay isang istraktura ng data na nakaayos sa isang first-in, first-out na batayan. Mayroong variable na dami ng data sa queue. Kapag pumila, ang data ay idinagdag sa buntot kapag nakuha, ito ay kinuha mula sa ulo.

Hash table

Ang pag-hash ay isang pamamaraan na nagbibigay-daan sa direktang pag-access sa mga talaan nang hindi gumagamit ng anumang karagdagang mga istruktura. Ang proseso ay maaaring madaling ilarawan bilang mga sumusunod. Ang espasyo kung saan iniimbak ang data ay nahahati sa ilang mga segment. Ang mga rekord ay ipinamamahagi sa mga bucket na ito ayon sa ilang algorithm na tinatawag na hashing algorithm, na nagko-convert ng halaga ng key field sa isang bucket number. Ang bawat tala ay naka-imbak sa isang segment na tinukoy ng prosesong ito. Samakatuwid, ang isang record ay maaaring makuha sa pamamagitan ng paglalapat ng hashing algorithm sa halaga ng key field nito at pagbabasa ng mga talaan ng kaukulang segment. Ang istraktura ng data na binuo sa ganitong paraan ay tinatawag na hash table.

Halimbawa, kung kailangan mong mag-ayos ng hash table para mag-imbak ng malalaking titik ng English alphabet, maaari mong piliin ang ASCII character code bilang mga key, at ang hashing algorithm ay puputulin ang low-order na limang bit at gagamitin ang mga ito para bumuo ng index ng array element para sa pag-iimbak ng character:

Sa pangkalahatan, ang isang hashing algorithm ay dapat, batay sa key value, na gumawa ng index value sa loob ng mga hangganan ng array at pantay-pantay na ipamahagi ang mga key sa mga elemento ng array. Ang kabiguang sumunod sa huling kinakailangan ay nagreresulta sa mga sitwasyon kung saan ang maraming tala ay nahulog sa parehong segment. Ang mga sitwasyong ito ay tinatawag na banggaan.