Массивтер және байланыстырылған тізімдер
Массивтер элементтер жинағын сақтау үшін ең жиі қолданылатын деректер құрылымы болып табылады. Көптеген бағдарламалау тілдері массивтерді оңай жариялау және массивтердегі элементтерге қол жеткізу әдістерін ұсынады. Байланыстырылған тізім, дәлірек айтқанда, жеке байланыстырылған тізім де элементтер жинағын сақтау үшін пайдаланылуы мүмкін деректер құрылымы болып табылады. Ол түйіндер тізбегінен тұрады және әрбір түйіннің реттегі келесі түйінге сілтемесі бар.
1-суретте көрсетілген, әдетте массивке мәндерді жариялау және тағайындау үшін пайдаланылатын код бөлігі. 2-суретте массив жадта қалай көрінетіні көрсетілген.
Жоғарыдағы код 5 бүтін сандарды сақтай алатын массивді анықтайды және оларға 0-ден 4-ке дейінгі индекстер арқылы қол жеткізіледі. Массивтің маңызды қасиетінің бірі - бүкіл массив жадтың бір блогы ретінде бөлінген және әрбір элемент өз кеңістігін алады. массивте. Массив анықталғаннан кейін оның өлшемі бекітіледі. Сондықтан компиляция уақытында массивтің өлшеміне сенімді болмасаңыз, қауіпсіз жағында болу үшін жеткілікті үлкен массивді анықтауыңыз керек. Бірақ көп жағдайда біз бөлінген элементтерден азырақ элементтерді қолданамыз. Осылайша, жадтың айтарлықтай көлемі іс жүзінде босқа кетеді. Екінші жағынан, «жеткілікті үлкен массив» шын мәнінде жеткілікті үлкен болмаса, бағдарлама бұзылады.
Байланыстырылған тізім жадты өзінің жеке жад блогындағы элементтеріне бөлек бөледі және жалпы құрылым осы элементтерді тізбектегі сілтемелер ретінде байланыстыру арқылы алынады. Байланыстырылған тізімдегі әрбір элементтің 3-суретте көрсетілгендей екі өрісі бар. Деректер өрісі сақталған нақты деректерді және келесі өрісте тізбектегі келесі элементке сілтемені сақтайды. Байланыстырылған тізімнің бірінші элементі байланыстырылған тізімнің басы ретінде сақталады.
| деректер | келесі |
3-сурет: байланыстырылған тізім элементі
4-суретте үш элементі бар байланыстырылған тізім көрсетілген. Әрбір элемент өз деректерін сақтайды және соңғы элементтен басқа барлық элементтер келесі элементке сілтемені сақтайды. Соңғы элемент келесі өрісте нөлдік мәнді сақтайды. Тізімдегі кез келген элементке басынан бастап және қажетті элементке жеткенше келесі көрсеткішті басу арқылы қол жеткізуге болады.
Массивтер мен байланыстырылған тізімдер екеуі де элементтер жинағын сақтау үшін пайдаланылатын мағынада ұқсас болғанымен, олардың элементтеріне жадты бөлу үшін қолданатын стратегияларына байланысты айырмашылықтар бар. Массивтер жадты оның барлық элементтеріне бір блок ретінде бөледі және массив өлшемін орындау уақытында анықтау керек. Бұл компиляция уақытында массив өлшемін білмейтін жағдайларда массивтерді тиімсіз етеді. Байланыстырылған тізім жадты оның элементтеріне бөлек бөлетіндіктен, компиляция уақытында тізім өлшемін білмейтін жағдайларда бұл өте тиімді болады. Мәлімдеме және байланыстырылған тізімдегі элементтерге қол жеткізу, оның индекстерін пайдаланып массивтегі элементтерге тікелей қатынасу жолымен салыстырғанда тікелей болмайды.
