Masīvi un saistītie saraksti
Masīvi ir visbiežāk izmantotā datu struktūra elementu kolekcijas glabāšanai. Lielākā daļa programmēšanas valodu nodrošina metodes, kā viegli deklarēt masīvus un piekļūt masīvu elementiem. Saistītais saraksts, precīzāk, atsevišķi saistītais saraksts, ir arī datu struktūra, ko var izmantot elementu kolekcijas glabāšanai. To veido mezglu secība, un katram mezglam ir atsauce uz nākamo secības mezglu.
Parādīts 1. attēlā, ir koda daļa, ko parasti izmanto, lai deklarētu un piešķirtu vērtības masīvam. 2. attēlā parādīts, kā masīvs izskatītos atmiņā.
Virsējais kods definē masīvu, kurā var saglabāt 5 veselus skaitļus, un tiem var piekļūt, izmantojot indeksus no 0 līdz 4. Viena svarīga masīva īpašība ir tāda, ka viss masīvs tiek piešķirts kā viens atmiņas bloks un katrs elements iegūst savu vietu. masīvā. Kad masīvs ir definēts, tā lielums tiek fiksēts. Tātad, ja neesat pārliecināts par masīva lielumu kompilēšanas laikā, jums ir jādefinē pietiekami liels masīvs, lai tas būtu drošā pusē. Taču lielāko daļu laika mēs faktiski izmantosim mazāk elementu, nekā esam atvēlējuši. Tātad ievērojams atmiņas apjoms faktiski tiek iztērēts. No otras puses, ja “pietiekami liels masīvs” patiesībā nav pietiekami liels, programma avarēs.
Saistīts saraksts piešķir atmiņu saviem elementiem atsevišķi savā atmiņas blokā, un kopējo struktūru iegūst, savienojot šos elementus kā saites ķēdē. Katram elementam saistītajā sarakstā ir divi lauki, kā parādīts 3. attēlā. Datu laukā ir faktiski saglabātie dati, un nākamajā laukā ir atsauce uz nākamo ķēdes elementu. Pirmais saistītā saraksta elements tiek saglabāts kā saistītā saraksta galvenais elements.
| dati | nākamais |
3. attēls. Saistītā saraksta elements
4. attēlā ir attēlots saistīts saraksts ar trim elementiem. Katrs elements saglabā savus datus, un visi elementi, izņemot pēdējo, saglabā atsauci uz nākamo elementu. Pēdējam elementam nākamajā laukā ir nulles vērtība. Jebkuram saraksta elementam var piekļūt, sākot no sākuma un sekojot nākamajam rādītājam, līdz atbilstat vajadzīgajam elementam.
Lai gan masīvi un saistītie saraksti ir līdzīgi tādā nozīmē, ka tos abus izmanto elementu kolekcijas glabāšanai, tie atšķiras, jo tiek izmantotas stratēģijas, lai piešķirtu atmiņu elementiem. Masīvi piešķir atmiņu visiem tā elementiem kā vienu bloku, un masīva lielums ir jānosaka izpildes laikā. Tas padarītu masīvus neefektīvus situācijās, kad jūs nezināt masīva lielumu kompilēšanas laikā. Tā kā saistītais saraksts piešķir atmiņu saviem elementiem atsevišķi, tas būtu ļoti efektīvs situācijās, kad jūs nezināt saraksta lielumu kompilēšanas laikā. Deklarēšana un piekļuve elementiem saistītajā sarakstā nebūtu vienkārša salīdzinājumā ar to, kā jūs tieši piekļūstat elementiem masīvā, izmantojot tā indeksus.
