Динамикалық айнымалылар құрылымы

Жоспар

КІРІСПЕ 3
НЕГІЗГІ БӨЛІМ
1 ДИНАМИКАЛЫҚ ҚҰРЫЛЫМДЫ МӘЛІМЕТТЕР 5
1.1 Динамикалық жады ұғымы. Көрсеткіштер 5
1.2 Динамикалық жадыны басқару 7
1.3 Динамикалық жадымен жұмыс жасау үшін қолданылатын 11
процедуралар мен функциялар
1.4 Динамикалық массивтер 12

2 ДИНАМИКАЛЫҚ АЙНЫМАЛЫЛАР ҚҰРЫЛЫМЫ. ТІЗІМДЕР 15
2.1 Тізім. Бір бағытталған тізімдер 15
ПРАКТИКАЛЫҚ БӨЛІМ 19
ҚОРЫТЫНДЫ 23
ПАЙДАЛАНЫЛҒАН ДЕРЕК КӨЗДЕР ТІЗІМІ 25

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Курстық жұмыс
Тегін: Антиплагиат
Көлемі: 24 бет
Таңдаулыға:

ҚАЗАҚСТАН РЕСПУБЛИКАСЫНЫҢ БІЛІМ ЖӘНЕ ҒЫЛЫМ МИНИСТРЛІГІ

Тізімдер
(Алгоритмдеу және бағдарламалау негіздері пәні бойынша )

1304000 Электрондық есептеу техникасы және бағдарламалық
қамтамасыздандыру мамандығы

Орындаған: топ білім алушысы
Ғылыми жетекшісі: ., информатика пәні

оқытушысы

Қорғауға жіберілді (жіберілмеді).
Информатика және ақпараттық
жүйелер пәндер бірлестік жетекшісі
______________ .
(қолы)
______________________ 2010 ж.

Ақтөбе ж
МАЗМҰНЫ

КІРІСПЕ
3
НЕГІЗГІ БӨЛІМ
1 ДИНАМИКАЛЫҚ ҚҰРЫЛЫМДЫ МӘЛІМЕТТЕР 5
1.1 Динамикалық жады ұғымы. Көрсеткіштер
5
1.2 Динамикалық жадыны басқару
7
1.3 Динамикалық жадымен жұмыс жасау үшін қолданылатын
11
процедуралар мен функциялар
1.4 Динамикалық массивтер
12
2 ДИНАМИКАЛЫҚ АЙНЫМАЛЫЛАР ҚҰРЫЛЫМЫ. ТІЗІМДЕР 15
2.1 Тізім. Бір бағытталған тізімдер
15
ПРАКТИКАЛЫҚ БӨЛІМ
19
ҚОРЫТЫНДЫ
23
ПАЙДАЛАНЫЛҒАН ДЕРЕК КӨЗДЕР ТІЗІМІ
25

КІРІСПЕ

Курстық жұмыстың өзектілігі: Паскаль программалау ортасында
Динамикалық жадының құрылымы соның ішіндегі тізімдерді қолдануды,
компьютердің оперативтік жадысын көрсеткіштер мен динамикалық жадыны
қолдану арқылы тиімді пайдалану мен ақпаратты өңдеу бойынша программалаудың
тиімді әдістемелері қарастыру.
Жалпы алғанда компьютер жадысының тұрақты жады және уақытша жады деп
екіге бөлінетіні белгілі. Турбо Паскальда жазылған программаны орындау
уақытша жадыда жүргізіледі де, программада анықталған, сипатталған
айнымалылардын барлығы уақытша жадының тұтас, белгілі бір аймағында
орналасады. Осы тұтас аймақты мәліметтер сегменті деп атайды. Мәліметтер
сегментінің ұзындығы 65536 байт немесе 64 кбайт болады. Бұл көлемдегі жады
қарапайым есептерді шешуге ғана мүмкіндік бере алады, ал үлкен көлемдегі
мәліметтерді өңдейтін қолданбалы программалар үшін қажет жады көлемі де
үлкен болуы керек екені түсінікті. Қазіргі компьютерлердің жалпы жадысының
көлемі 640 кбайттан кем болмайды, сондықтан компьютер жадысына қатысты осы
мүмкіндіктерді толық пайдалану үщін динамикалық жады пайдаланылады.
Динамикалық жады - бұл дербес компьютердің, мәліметтердің сегментін, стекті
және программаньң өзінің денесі алатын орынды қоспағандағы немесе
есептемегендегі жұмыс істеп түрған программаға бере алатын уақытша жадысы.
Сонда ол уақытша берілетін жады программа жұмыс істеп түрған кезде
программа үшін пайдаланылады да, ал оның жұмысы тоқтаған соң бұрынғы
қызметін атқара береді, яғни динамикалык жады "өзгермелі жады" деген
мағынаны білдіреді.
Компьютердің жадысы байттар деп аталатын ұяшықтардан құралады. Бұл
байттардың барлығы номерленген. Осы номерлерді байттардың адресі деп
атайды. Программада компьютер жадысын пайдалану үшін осы байттардың
адрестері қолданылады. Бүл адрестерді программада қалай береді.
Байттың адресі екі сөзден құралады. Ол екі сөзді сегмент және ығысу деп
атайды. Жадының сегмент сақталатын бөлігі, адресі 16- ға еселі болатын
байттан басталады, ал ығысу- қажет адреске бару үшін сегменттің басынан
бастап неше байтты өткізіп жіберу керек екенін көреетеді. Осы адрестерді
программада көрсету үшін динамикалық айнымалылар қолданылады. Бұл
динамикалық айнымалыларды көрсеткіштер ( немесе сілтемелер, нұсқағыш)
деп атайды.
Динамикалық мәліметтер көмегімен өлшемі анықталмаған массивтерді
өңдеуді қарастырайық. Бір элементтен тұратын массив үшін massiv типін
сипаттайық. massiv типті айнымалыны сипаттамаймыз да, ал мәліметтерінің
базалық типі massiv болатын типтелген көрсеткішті сипаттайық. Программаның
орындалу кезінде массивтегі элементтер санын анықтап, массив үшін жадыдан
қажет өлшемді бөле аламыз. Массивпен жұмыс жасалып болған соң, алдыңғы
бөлінген жадыны босатуға болады. Жадыны осылайша бөлу арқылы анықталатын
массивтер динамикалық деп аталады. х динамикалық массивінің і-ші элементі
х^[і] деп жазылады.
Динамикалық массивтерде объект программа орындалу кезінде өзінің
өлшемін өзгертпейді. Ал кейде жеке компоненттерді алу немесе қосу арқылы
біртипті эдементтер құрылымын өзгертетін жағдайлар да кездеседі. Осы кезде
біз тізімдерді қолданамыз. Өзара көрсеткіштер мен байланысатын біртиптік
элементтер қатарын тізім деп атаймыз. Айталық, өзара көрсеткіштер
тізбегімен байланысқан бірипті элементтер қатары берілсін. Әрбір элемент,
соңғысынан басқа, мәліметтерімен қоса келесі элементке көрсеткіштен
құралған болсын. Мұндай құрылым сызықтық бірбағытталған тізім деп аталады.
Курстық жұмыстың мақсаты: Динамикалық құрылымды мәліметтер соның ішіндегі
динамикалық жады ұғымы, көрсеткіштер, динамикалық жадыны басқару,
динамикалық жадымен жұмыс жасау үшін қолданылатын процедуралар мен
функциялар, динамикалық массивтер, тізім, бір бағытталған тізім,
байланысқан тізімдерді қолдануды қарастыру.
Курстық жұмыстың міндеттері:
- Динамикалық айнымалылар құрылымы;
- Тізімдер;
- Бірбағытталған тізім;
- Байланысқан тізімдер;
Зерттеу обьектісі:TURBO PASKAL программалау ортасы.
Зерттеудің ғылыми болжамы:Паскаль оқып үйренуге жеңіл, түрлі салалық
информациямен жұмыс істеуге нәтижелі болғандықтан дүние жүзінде көп тараған
тілдердің бірі.Паскаль тілінде тізімнің ерекшеліктері, тізім арқылы
берілген әрбір бағанның ұяшықтарындағы ақпараттарды өзгертуге немесе
ақпарат еңгізуге болады.
Зерттеу әдістері:Ұяшықтағы ақпаратты өңдеуге және ұяшыққа ақпарат енгізуін
әдістерін зерттедім.

1 ДИНАМИКАЛЫҚ ҚҰРЫЛЫМДЫ МӘЛІМЕТТЕР

1.1 Динамикалық жады ұғымы. Көрсеткіштер

Жалпы алғанда компьютер жадысының тұрақты жады және уақытша жады деп
екіге бөлінетіні белгілі. Паскальда жазылған программаны орындау уақытша
жадыда жүргізіледі де, программада анықталған, сипатталған айнымалылардың
барлығы уақытша жадының тұтас, белгілі бір аймағында орналасады. Осы тұтас
аймақты мәліметтер сигменті деп атайды. Мәліметтер сигментінің ұзындығы
65536 байт немесе 64 кбайт болады. Бұл көлемдегі жады қарапайым есептерді
шешуге ғана мүмкіндік бере алады, ал үлкен көлемдегі мәліметтерді өңдейтін
қолданбалы программалар үшін қажет жады көлемі де үлкен болуы керек екені
түсінікті. Қазіргі компьютерлердің жалпы жадысының көлемі 640 кбайттан кем
болмайды, сондықтан компьютер жадысына қатысты осы мүмкіндіктерді толық
пайдалану үшін динамикалық жады пайдаланылады.
Динамикалық жады – бұл дербес компьютерлердің, мәліметтердің
сигментін, стекті және программаның өзінің денесі алатын орынды
қоспағандағы немесе есептемегендегі жұмыс істеп тұрған программаға бере
алатын уақытша жадысы. Сонда ол уақытша берілетін жады программа жұмыс
істеп тұрған кезде программа үшін пайдаланылады да, ол оның жұмысы тоқтаған
соң бұрыңғы қызметін атқара береді, яғни динамикалық жады өзгермелі жады
деген мағынаны білдіреді.
Компьютердің жадысы байттар деп аталатын ұяшықтардан құралады. Бұл
байттардың барлығы нөмірленген. Осы нөмірлерді байттардың адресі деп
атайды. Программада компьютер жадысын пайдалану үшін осы байттардың
адрестері қолданылады. Бұл адрестерді программада қалай береді?
Байттың адресі екі сөзден құралады. Ол екі сөзді сигмент және ығысу
деп атайды. Жадының сигмент сақталатын бөлігі, адресі 16 – ға еселі болатын
байттан басталады. Ол ығысу – қажет адреске бару үшін сигменттің басынан
бастап неше байтты өткізіп жіберу керек екенін көрсетеді. Осы адрестерді
программада көрсету үшін динамикалық айнымалылар қолданылады. Бұл
динамикалық айнымалыларды көрсеткіштер (немесе сілтемелер нұсқағыш) деп
атайды.
Көрсеткіш – бұл динамикалық жадымен жұмыс істеу үшін енгізілген ұғым,
шама, айнымалы. Көрсеткіштің немесе динамикалық айнымалының қабылдайтын
мәндері бұл жадының байттарының адресі болып табылады.
Көрсеткіштер арқылы динамикалық жадыға Паскальдағы кез – келген типке
жататын мәліметті апарып қоюға және жіберуге болады. Айталық, бұл
мәліметтер динамикалық жадыда 1 байтқа орналасуы мүмкін немесе қатар тұрған
2 байтқа, 4 байтқа, 16 байтқа да орналасуы мүмкін, бірақ бұл көрсеткіштер
үшін бәрі бір болып есептеледі. Себебі, ол мәлімет орналасқан алғашқы
байттың ғана адресін көрсетіп тұрады.
Көрсеткіштердің екі түрі болады:
Типтелген көрсеткіштер, яғни мұнда көрсеткіш Паскальдағы белгілі бір
типпен байланыстырылады. Оны программада сипаттау үшін ″ ^ ″ (қалпақша)
белгісі қолданылады және төмендегідей түрде жазылады:

Var
Көрсеткіштің аты: ^ типі;
Мысалы,
Var
p1: ^ real;
p2: ^ integer;
немесе
type
Person Pointer = ^ Person Record;
Person Record = record;
Name: string;
Job: string;
Next: Person Pointer;
End;

Мұндағы Person Pointer деген типті анықтау үшін әлі анықталмаған
Person Record деген тип қолданылады, ал бұл Паскальдағы осыған дейінгі
қарастырылған типтер үшін мүмкін емес еді. Бұл тек көрсеткіштер үшін,
динамикалық жадыны пайдалануға берілген мүмкіндік. Мұның мағынасы мынада:
динамикалық жадыда мәліметтерді тізім түрінде орналастыру қарастырылған.
Тізімнің әрбір элементі екі бөліктен тұрады:
Бірінші бөлікте тізімнің элементі (немесе мәліметтің өзі, яғни тізім
элементінің информациялық бөлігі) орналасады;
Екінші бөлікте тізімнің келесі элементі орналасатын байттың адресіне
көрсететін, сілтейтін көрсеткіш (немесе тізім элементінің адрестік бөлігі)
орналасады, тізімнің аяқталғанын көрсеткіштің nil деген мәнін білдіреді (1
сурет).

Тізімнің 1 – ші
элементі
Көрсеткіш
Тізімнің n – ші

элементі
Nil

Тізімнің 2 – ші
элементі
Көрсеткіш

1 сурет. Мәліметтердің тізім түрінде берілуі.

Бұл тізім бір бағытта болуы мүмкін немесе соңғы элементтегі көрсеткіш
қайтадан бастапқы 1 – ші элементке сілтейтін болса, онда тұйықталған тізім
пайда болады. Тұйықталған тізімді басқаша сақина деп те атайды.

1.2 Динамикалық жадыны басқару

Турбо Паскальда динамикалық жадыны байттардан құрылған массив түрінде
қарастырады да оны куча деп атайды. Нақты тұрғыдан алып қарағанда, куча
жадының, программаның денесі орналасқаннан кейінгі келесі үлкен адресті
байтынан басталады. Кучаның басы HeapOrg, соңы HeapEnd стандарт
айнымалыларында сақталады. ( 2 сурет )

Жоғарғы адрестер
Жүйелік
облыс

Куча

Программа
Жүйелік
облыс

Heap End →

Heap Ptr →

Heap Org →

Төменгі адрестер

2 сурет. Кучаның ДК жадысында орналасуы.

Бос динамикалық жадының ағымдағы шекарасын HeapPtr көрсеткіші бере
алады. Айталық, динамикалық жадыға немесе кучаға і = 2 бүтін сан мен
r=2*3,14=6,28=2*pi нақты санды орналастыратын және жадны қайтадан босататын
программа фрагментіндегі динамикалық жадының өзгерісін қарастырайық. Мұнда
new және dispose динамикалық жадымен жұмыс істеуге арналған процедуралар
қолданылады.
New – динамикалық жадыға жіберілетін айнымалы үшін кучадан орын
тағайындауды қамтамасыз ететін процедура, ал Dispose – керісінше кучадағы
айнымалыға берілген орынды босататын процедура.
Берілген і және r айнымалыларындағы мәліметтерді кучаға орналастыратын
программа фрагменті келесі түрде болады:
Var
I: ^ integer; { i – бүтін типті көрсеткіш }
R: “ real; { r – нақты типті көрсеткіш }
Begin
New ( i ); { i – көрсеткіш немесе динамикалық айнымалы үшін кучадан
орын босатылады, яғни і – ге адрес беріледі }
I ^:= 2; { берілген адрес бойынша 2 саны динамикалық жадыға орналасады}
New ( r ); { r – ге орын босатылады}
R ^:= 2*pi; { r – дің адресі бойынша 2 саны динамикалық жадыға
орналасады}
Writeln ( i ^ * 5 ); { i – адрестегі мәліметті немесе 2 – ні 3 – ке
көбейтіп
баспаға шығару}
End.
Бұл мысалдан шығатын қорытынды мынау: i мен i ^ немесе r мен r ^
шатастырмау керек, мұндағы i мен r көрсеткіштердің өздері болып табылады
және олардың мәндері – байттардың адрестері, ал i ^ мен r ^ бұл адрестерді
көрсетеді, мәліметтер осы адрестердегі жадыда орналасады, сондықтан
мәліметтермен жұмыс істеген кезде i ^, r ^ адрестер пайдаланылады.
Әрі қарай кучадан алынған орынды босатып, қайтып беретін программа
фрагменті қарастырылсын.

Var
i : integer;
begin
new ( i );
i ^ := 20;
writeln ( i ^ ); { баспаға 20 саны шығарылады, себебі, ол i ^ адрес
бойынша
орналасқан}
dispose ( i ); { кучаға 2 байттық орынды қайтып береді}
writeln ( i ^ ); { 0 – ді шығарады, себебі, i ^ адрестегі орын босатылды
}
End.

Мұнда i көрсеткіштің мәні, яғни байттың адресі өзгермейді, тек i – ге
бөлінген 2 байт орын қайтадан босайды. Босаған көрсеткішті программада nil
қызметші сөзбен белгілеп кетеді, яғни dispose ( i );
i :=
nil;
Программадағы кучамен жасалатын әрекеттердің барлығын реттеп басқарып
отыратын куча администраторы деп аталатын арнаулы программа болады.
Турбо Паскаль жүйесі статикалық жадыда мәліметтер үшін тек екі
сигмент бөлінеді: біреуі глобальды ( ауқымды ), екіншісі локальды (
жергілікті ) мәліметтер үшін. Бірінші сигментте барлық тұрақтылар мен Const
және Var бөлімдерінде сипатталған базалық емес айнымалылар үшін, негізгі
программаның сипаттамасы үшін және қолданылатын модульдер үшін жадыдан орын
болады.
64 килобайт – глобальдық мәліметтер сигментінің көлемі – көп жағдайда
үлкен көлемді ақпараттары бар есептерді шешу кезінде жеткіліксіз болады.
Мысалы, егер
Var х: array [ 1. . . 100, 1. . . 100 ] of real;
сипаттамасы берілсе, онда 10000 элементі бар осы массив статикалық жадыда
60000байт, яғни барлық сигменттің аумағын алады.
Глобальдық және локальдық мәліметтер үшін сигмент жетіспеген кезде
жүйе келесі хабарламаны шығарады:
Too Many variables ( өте көп айнымалы ).
Сонымен қатар, мәліметтер мен программа үшін статикалық жады
жетіспесе:
Out of memory ( жады шекарасынан шығып кетсін ) деген
хабарлама шығады.
Бұл кезде программа мәліметтері үшін Турбо Паскальдың динамикалық
жадысын қолданған тиімді. Барлық динамикалық жады куча деп аталатын байт –
ұяшықтардың құрылымы ретінде қарастырылады.
Динамикалық жадыны басқару екі операциядан тұрады:
- мәліметтерге, олардың мәндерін жазу үшін жадыдан ұяшықтарды бөлу
( кучадан бөлу );
- жады ұяшықтарын босату ( кучаға қайтып оралу ).
Екі операция да динамикалық жады ұяшықтарының адрестері бойынша,
көрсеткіштер арқылы орындалады.
Турбо Паскальда динамикалық жадыны басқарудың үш әдісі бар. Оларды шартты
түрде басқару процедуралары деп атаймыз:
1. New – Dispose,
2. Mark – Release,
3. Getmem – Freemem.
Бұл әдістерді жеке – жеке қарастырмастан бұрын, куча құрылымымен оны
басқаруда қолданылатын стандартты айнымалылардың сипаттамасына тоқталайық.
Кучаны басқару үшін Pointer типті ( типтелмеген көрсеткіш ) үш стандартты
айнымалы енгізілген:
HeapOrg – кучаның бірінші байтының адресі, куча басы үшін;
HeapPtr – мәліметтер үшін кучадан ұяшықтар бөлінгеннен кейін, кучадағы
алғашқы бос байт адресі үшін;
Freeptr – кучаның соңғы байт – ұяшық адресі, куча соңы үшін.
а) Динамикалық жадыны New – Dispose әдісімен басқару.
Типтелген көрсеткіштер арқылы басқарылатын бұл әдіс негізгі болып
табылады. Осы әдіспен динамикалық айнымалыға жадыдан орын бөлу үшін New
процедурасы қолданылады: New (ААТК);
Мұндағы ААТК – айнымалы аты – типтелген көрсеткіш.
New операторы 2 кезеңде орындалады:
1 – шісі: ААТК : = HeapPtr, көрсеткішке алғашқы бос байттың адресі
меншіктеледі.
2 – шісі: HeapPtr : = HeapPtr + типтің байтпен берілген ұзындығы ,
кучаның бос байт көрсеткішінің мәні,
типтелген
көрсеткішпен анықталған типтің
ұзындығына ығысады.
Динамикалық айнымалы алып тұрған жадыны босату үшін, басқарудың
бірінші әдісіне Dispose процедурасы қолданылады:
Dispose (ААТК);
Dispose процедурасы жұмысының сипаттамасы:
Динамикалық айнымалылар алып тұрған ұяшықтар, әрі қарай ерекшелеу үшін
кучаға қайтарылады. Бұл кезде босаған аумақтың адресі мен ұзындығы
динамикалық жадының босап қалған аумақтардың тізіміне қосылады.
ә) Динамикалық жадыны MARK – RELEASE әдісімен басқару.
Бұл әдіс тек динамикалық жады ұяшықтарының аумағын RELEASE
процедурасымен босату үшін қолданылады:
Процедураны шақыру: RELEASE ( vptr );
Мұндағы vptr – типтелмеген көрсеткіш типті өрнек.
Бұл процедура кучаға адресі параметрмен берілген ұяшықтан бастап, адресі
HeapPtr : = vptr; операторы орындалады.
Әдетте кучаны басқарудың бұл әдісі келесі схема бойынша қолданылады:
1. Динамикалық жадыны әрі қарай RELEASE процедурасымен босату үшін
бастапқы ұяшық MARK процедурасымен белгіленеді. Ұяшықты белгілеу, оның
адресін MARK процедурасы параметрінде, яғни типтелмеген айнымалы
көрсеткіште есте сақталуында негізделеді.
2. Динамикалық айнымалылар қажет болмағаннан кейін, оларға бөлінген
ұяшықтар RELEASE ( nptr ); операторымен босатылады, мұндағы nptr –
типтелмеген айнымалы көрсеткіштің аты, ол MARK процедурасында
қолданылады.
Осы схема бойынша динамикалық жады бөлігінің барлық ұяшығы кучаға қайтып
оралады.
MARK процедурасын шақыру : MARK ( nptr ); мұндағы nptr – Pointer типті
айнымалы аты.
Процедураның орындалуы nptr айнымалысына HeapPtr көрсеткішінің мәнін
меншіктеуге негізделеді.
б) Динамикалық жадыны Getmem – Freemem әдісімен басқару.
Кучаны басқарудың үшінші әдісі динамикалық жадыда ақпараттың қандай да
бір көлемін сақтау үшін қолданылады, және де пайдаланылған ұяшықтарды кейін
босатып отыруы керек.
Динамикалық жады Getmem процедурасы бойынша бөлінеді, шақырылуы:
Getmem (nptr, байт саны );

Мұндағы nptr – типтелмеген айнымалы көрсеткіш.
Бұл процедура кучадан көрсетілген байт санын бөліп, ал ерекшеленген
аумақтың адресін, оның бірінші байтының адресін nptr айнымалысына енгізеді:
Getmem бойынша бөлінген жады, Freemem процедурасы көмегімен
босатылады:
Freemem ( vptr, байт саны );
Мұндағы vptr ... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.