На сортировку / 2 / 1 курс / 5.Алгоритм и языки программ / С ДӘРІСТЕР ЖИНАҒЫ / 12-дәріс. Мәліметтер және динамикалық құрылымдар

12-дәріс. Тақырыбы: Мәліметтер және динамикалық құрылымдар.

Жоспар:

1. Мәліметтердің динамикалық құрлымы.

Мәліметтердің динамикалық структурасы-өлшемдері программаның

орындалу барысында өзгеретін (өсетін немесе кемитін) мәліметтер

структурасы. Байланысқан тізім- кез келген орнында қоюды және жоюды

іске асыруға болатын мәліметтер элементтерінің «тізілген қатар»

жиынтығы. Стектер қою және жоюдың орындалуына тек қана стектің бір

ұшынан -үстінен рұқсат береді. Кезектер деп күту сызығын айтуға болады.

қою кезектің соңында, ал жою-кезектің басында іске асады. Екілік бұтағы

тез іздеуді және мәліметтерді сұрыптауды жеңілдетеді, мәліметтер

элементтерінің қайталануын тиімді жояды, каталогтардың файлдық

структурасын және өрнектерді машиналық тілге компиляциялауды ұсынады.

Өздеріне сілтемелейтін структуралар. Өздеріне сілтемелейтін

структуралар элемент ретінде сол типке сілтемелейтін көрсеткішті алады.

Мысалы,

struct node {

int data;

struct node *nextptr;

};

struct node типін баяндайды. Struct node типті структура екі элементтен

тұрады: бүтін data және nextPtr көрсеткіш. NextPtr элементі struct node типті

структураға сілтемелейді. NextPtr элементін кейде байланыстырушы деп

атайды, яғни nextPtr элементін struct node типті структураны осы типтес

басқа структурамен байланыстыру үшін қолданады.

Жадыны динамикалық үлестіру. Мәліметтердің динамикалық

структурасын құру және қолдану жадыны динамикалық үлестіруді талап

49

етеді-жаңа түйіндерді сақтау және керексіз болып қалған жадылар блоктарын

босату үшін орындалу процесінде қосымша жадыны алу мүмкіндіктері.

Динамикалық жадымен бөлінетін максималды өлшем компьютердің

мүмкіндікті физикалық жадысымен немесе виртуальді жадысы бар жүйедегі

мүмкіндікті виртуальді адрестік кеңістіктікпен анықталады. Жадыны

динамикалық үлестіру үшін malloc және free функцияларын, сондай-ақ sizeof

операциясын қолдану қажетті. Malloc функциясын void* типті жадысына

бөлінетін көосеткішті қайтару және бөлу қажетті байт санының аргументі

ретінде қолданады. void* көрсеткішін кез келген айнымалы-көрсеткішке

меншіктеуге болады. Malloc функциясы әдетте sizeof операциясымен бірге

қолданылады. Егер жадының қажетті саны болмаса, онда malloc NULL

көрсеткішін қайтарады. Free функциясы жадыны босатады, яғни жады

жүйеге қайтарылады және келешекте оны қайтадан ерекшелейді(бөледі).

Байланысқан тізімдер. Байланысқан тізімдер-бұл түйін деп аталатын

өзіне сілтенетін структуралардың және көрсеткіш-байланыстармен біріккен

сызықты жинағы. Байланысқан тізімге қатынас тізімнің бірінші түйінінде

көрсеткішпен қамтамасыз етіледі. Келесі түйіндерге қатынас әрбір түйінде

сақталатын байланысқан көрсеткішпен орындалады. Байланысқан көрсеткіш

жалпы келісіммен тізімнің соңғы түйінінде тізімнің соңын білдіріп, NULL-

мен орнатылады. Мәліметтер байланысқан тізімде сақталады, динамикалық-

әрбір түйін қажеттілігіне қарай құрылады. Түйін басқа структуралармен қоса

кез келген типті мәліметтерден тұра алады. Байланысқан тізім структура

қанша мәліметтер элементтерінен тұратыны алдын-ала белгісіз болғанда

ыңғайлы. Егер әрбір жаңа элементті сәйкес тізімнің позициясына

орналастырса, онда байланысқан тізімдер сұрыпталған түрде болуы мүмкін.

Стектер. Стек-бұл байланысқан тізімнің қысқартылған түрі. Жаңа

түйіндер тек жоғарыдан стекке қосыла алады және стектен жойылы алады.

Осы себепті стекті соңғы келді-бірінші шықты (LIFO) түрдегі структура деп

атайды. Стекке көрсеткіш арқылы стектің жоғарғы элементіне сілтенеді.

Байланысқан элемент стектің соңғы түйінінде стектің шекарасын көрсету

үшін NULL-мен орнатылады.

Кезектер. Кезекте түйіндер басынан жойылады, ал кезектің соңынан

(хвост) қосылады. Осы себепті жиі кезектерді соңғы келді-бірінші шықты

(LIFO) типіндегі мәліметтер структурасы деп атайды.

Бұтақтар. Бұтақ ерекше қасиеттері бар бейсызықты структура, екі

өлшемді мәліметтер структурасы болып табылады. Бұтақ түйіні екі не оданда

көп байланыстардан құралады. Екілік бұтақтар дегеніміз тек екі байланыстан

тұратын бұтақты айтады. Бұтақтың бірінші түйіні түпкі деп аталады. Түпкі

түйіннің әрбір байланысы мұрагерге сілтенеді. Сол мұрагер- солдағы бұтақ

ішіндегі бұтақтың бірінші түйіні, ал оң мұрагер- оңдағы бұтақ ішіндегі

бұтақтың бірінші түйіні. Іздеудің екілік ағашы (түйінде қайталанбайтын

мәндермен) былай құрылған: кез келген сол ағаштың ішіндегі ағаштың

мәндері жоғарыда орналасқан түйіннің мәнінен кіші, ал кезкелген оң

ағаштың ішіндегі ағаштың мәні жоғарыда орналасқан түйіннің мәнінен

50

артық.

56