Бір өлшемді массивтерді сұрыптау алгоритмдері

Жоспар
Кіріспе

МАЗМҰНЫ

КІРІСПЕ
3
БІР ӨЛШЕМДІ МАССИВТЕР 4
1.1. Бір өлшемді массивтердің Turbo Pascal тіліндегі сипаттамасы 4
1.2. Массивтермен амалдар орындау 7
1.3. Массив элементтерімен амалдар орындау 8
БІР ӨЛШЕМДІ МАССИВТЕРДІ СҰРЫПТАУ АЛГОРИТМДЕРІ 11

2.1. Ауыстырмалы сұрыптау («көпіршік» тәсілі) 11
2.2. Қойылымды сұрыптау 12
2.3.Таңдап алу арқылы сұрыптау 12
ЕКІ ӨЛШЕМДІ МАССИВТЕР (МАТРИЦА) 13

3.1. Матрицаның Turbo Pascal тіліндегі сипаттамасы 13
3.2. Квадрат матрицада индекстердің ара қатынасы 15
3.3. Массивтерді қолдану ережелері 15

ҚОРЫТЫНДЫ 17

ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР 18

ҚОСЫМША 19

КІРІСПЕ

Қарапайым типтер қатарына жататын стандартты (integer, real) және қолданушылар (тізбектелген тип) типтерінде бір айнымалыны сақтау үшін, негізінен компьютер жадысының бір ғана ұяшығы қолданылады. Бірақ көптеген программалау есептерінің шешімін табу барысында әрбір элементтің деректерін жеке айнымалыға сақтау орнына, оларды тізбектеп бір жерде сақтау анағұрлым тиімді болып табылады.
«Массив» деген ұғыммен ғылыми-техникалық және экономикалық мәселелерді шешу барысында кездесеміз. Себебі біз мұндай жағдайда көп көлемді есептеулер мен цифрлармен жұмыс істеуге мәжбүр боламыз.
Массив – бұл жалпы атпен біріккен және компьютердің жадында белгілі бір орынды алатын бір типті элементтердің жиынтығы болып келеді. Массивтегі элементтер саны әрдайым шектеулі болады.
Жалпы алғанда массив бұл – мәліметтердің құрылымдық жиыны, ол шектелген сан элементтерден тұрады және олардың бәрі бір типті элементтер болады.
Массивтерді біз жүйелі тип атауымыздың себебі массивтер өзіне біртиптік (логикалық) элементтерді жиғаны, олар индекстері бойынша сұрыпталған, индекс - әр элементтің массивтің ішіндегі өз орнын белгілейтін айнымалы.

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

МАЗМҰНЫ

КІРІСПЕ 3
БІР ӨЛШЕМДІ МАССИВТЕР 4
1.1. Бір өлшемді массивтердің Turbo Pascal тіліндегі 4
сипаттамасы
1.2. Массивтермен амалдар орындау 7
1.3. Массив элементтерімен амалдар орындау 8
БІР ӨЛШЕМДІ МАССИВТЕРДІ СҰРЫПТАУ АЛГОРИТМДЕРІ 11
2.1. Ауыстырмалы сұрыптау (көпіршік тәсілі) 11
2.2. Қойылымды сұрыптау 12
2.3.Таңдап алу арқылы сұрыптау 12
ЕКІ ӨЛШЕМДІ МАССИВТЕР (МАТРИЦА) 13
3.1. Матрицаның Turbo Pascal тіліндегі сипаттамасы 13
3.2. Квадрат матрицада индекстердің ара қатынасы 15
3.3. Массивтерді қолдану ережелері 15
ҚОРЫТЫНДЫ 17
ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР 18
ҚОСЫМША 19

КІРІСПЕ

Қарапайым типтер қатарына жататын стандартты (integer, real) және
қолданушылар (тізбектелген тип) типтерінде бір айнымалыны сақтау үшін,
негізінен компьютер жадысының бір ғана ұяшығы қолданылады. Бірақ көптеген
программалау есептерінің шешімін табу барысында әрбір элементтің деректерін
жеке айнымалыға сақтау орнына, оларды тізбектеп бір жерде сақтау анағұрлым
тиімді болып табылады.
Массив деген ұғыммен ғылыми-техникалық және экономикалық мәселелерді
шешу барысында кездесеміз. Себебі біз мұндай жағдайда көп көлемді
есептеулер мен цифрлармен жұмыс істеуге мәжбүр боламыз.
Массив – бұл жалпы атпен біріккен және компьютердің жадында белгілі
бір орынды алатын бір типті элементтердің жиынтығы болып келеді. Массивтегі
элементтер саны әрдайым шектеулі болады.
Жалпы алғанда массив бұл – мәліметтердің құрылымдық жиыны, ол
шектелген сан элементтерден тұрады және олардың бәрі бір типті элементтер
болады.
Массивтерді біз жүйелі тип атауымыздың себебі массивтер өзіне
біртиптік (логикалық) элементтерді жиғаны, олар индекстері бойынша
сұрыпталған, индекс - әр элементтің массивтің ішіндегі өз орнын белгілейтін
айнымалы.
I. БІР ӨЛШЕМДІ МАССИВТЕР
. 1.1. Бір өлшемді массивтердің Turbo Pascal тіліндегі сипаттамасы

Массивтің элементі ретінде программалау тіліне сәйкес анықталған типті
бола алады. Мысалы, Turbo Pascal тілінде массивтің элементі ретінде кез
келген типті қолдануға болады, сондықтан да массивтер өз жазылымдар түрінде
(record), белгілер ретінде (labels), өзі массивтері (arrays) ретінде де
қолданыла алады.
Массивтер элементтерінің типі – базалық деп аталады. Turbo Pascal
тілінің басқа программалау тілдерінен айырмашылығы болып массивтер
жарияланған кезде элементтерінің саны шектеулі болуы, және программаның
орындалуы барысында өзгермеуі саналады.
Массив элементтері нөмірленеді. Осыдан массивті құрайтын элементтер
өзіне тән белгілі бір орын тәртібімен (индексі) орналасады. Массивтің әрбір
элементіне индексін көрсету арқылы жұмыс істеуге болады. Массивке мысал
ретінде векторларды қарастыруға болады.
Әр элементтің мәнін жадыдан алу үшін массивті алдын ала индекстеу
керек. Массивтер элементтерімен жұмыс жасау барысында, массив атауынан
кейін міндетті түрде тік жақшаға алынған индекс көрсетіледі. Индекс тек
скалярлы тип (көбінесе бүтін - integer) бола алатын аралықтан алына алады,
оны, мысалы, нақты типке (real) меншіктеуге болмайды. Индекстің типі
индекстің мәндерінің өзгеру шекарасын анықтайды.
Массив сипаттамалары:
• Типі – массив элементтерінің жалпы типі;
• Көлемі – массив индекстерінің саны;
• Шектелімі – әрбір индекстерінің шектеу бойынша сәйкестілігі;
• Пішімі – көлем және шектеулер жиындары.
Массивті келесі жағдайларда қолданамыз:
• Бүкіл мәлімет жадыда өңделу үшін берілген жағдайда;
Оған мысал – санды мәліметтерді сұрыптау, яғни оларды өсуі немесе кемуі
бойынша орналастыру.
• Есептеулердің нәтижелері немесе жадының бірнеше ұяшығындағы уақытша
айнымалылар мәндерінің бәрі бірдей логикалық мәнге ие болатын болса,
оларды жадыға сақтап қою керек. Бұл ұяшықтар бір атпен белгіленіп,
массивті құрайды.
Мысалы, берілген мәтінде алфавиттің 42 әріптің әрбіреуі неше рет
кездесетінін есептеуге керек делік. Бұл мәтінді оқып, есте сақтауға қиын
мәселе және ол керек те емес. Оларды есептейтін бізге айнымалы қажет, яғни
А әрпінің неше рет енуін СА, ал Ә әрпін СӘ айнымалысы, т.с.с. 42 айнымалы
керек еді.
Осы айнымалылардың бәрі де бірдей логикалық мәнге ие, яғни бәрі де
белгілі бір әріптің ену санын өзіне сақтайды. Біз оны Санағыш деген атпен
бір жиынға келтіреміз де, көлемін 42 деп белгілейміз. Массивтің индексі 1
мен 42 мән аралығында өзгеріп отырады. Яғни Санағыш(1) А әрпінің ену санын,
Санағыш(2) Ә әрпінің, т.с.с.
Егер массивтің әр элементіне бір реттік (өлшемді) нөмер тіркелген
болса, онда мұндай массив – бір өлшемді массив деп аталады.
Turbo Pascal программалау тілінде массив былай жарияланады:
массивтің аты:array [элемент саны] of айнымалы типі
Массивтің әр элементі A[I] болып белгіленеді, А – массивтің аты, I –
индексі (0=I= N болып тұрады, бірақ көбінесе 1=I=N қолданылады).
A(I) – массив элементінің мәні.
Массивтерді қолдану үшін оларды типтер (type) немесе айнымалыларды
сипаттау (var) бөлімінде хабарлану қажет.
Жалпы жазылу түрі:
type
Массив типінің атауы = array [индекс типі ] of элемент типі;
var
массив атауы: массив типінің атауы;

Мысалы:
type
GRUP = array [1..8] of integer;

var
A: GRUP; {A – массивіне жады бөлу}

Мұндағы:
Массив типінің атауы – массив элементтерінің жиынын сипаттайды;
Индекс типі – тізбектелген немесе шектелген типтерді көрсету; (Массив
индексі тік жақшаға алынып жазылады)
Элемент типі – массив элементтерінің типін көрсету.

1.2. Массивтермен амалдар орындау

Біркелкі жүйе етіп массивпен жұмыс істеу үшін массивтің
идентификаторы қолданылады. Оның индексі көрсетілмей, тек квадрат жақшада
жазылады. Массив тек тең, тең емес және меншіктеу амаладары қолданыла
алады. Мұндай амалдарда қолданылатын массивтер құрылымы бірдей болуы қажет,
яғни индекстердің бірдей типтері болуы және компоненттердің бірдей болуы
қажет етіледі.
Мысалы, егер А және В массивтері былай жарияланатын болса: var A,B:
array[1..20] of real; онда осы амалдарды оларға қолдану мынадай қорытындыны
береді:

Амал Қорытынды
A=B True, шын болады егер А массивінің элементтері В массивінің сәйкес
элементтеріне тең болса.
AB True, шын болады егер А массивінің элементтерінің ішінде кем дегенде
бір элементі В массивінің сәйкес нөмерлі элементке тең болмауы жеткілікті.
A:=B, В массивінің барлық элементтері А массивінің сәйкес элементтеріне
меншіктеледі. В массивінің элементтері өзгеріссіз қалады.
1.3. Массив элементтерімен амалдар орындау

Массивті жариялағаннан кейін оның әр элементінің идентификаторын
(атын) қойып және квадрат жақшада индексін көрсетіп, өңдеуге болады.
Мысалы, Mas[2], Vector[10] жазылымдары Mas массивінің 2-ші элементіне,
Vector массивінің 10-шы элементіне жүгінуге мүмкіндік береді.
Екі өлшемді массивтермен жұмыс істегенде екі индекс көрсетіледі, ал n
өлшемді массивте n индекс саны көрсетіледі. Мысалы, Matr[4,4] массивінде
төртінші жолдың төртінші бағанында орналасқан элементті өңдеуге мүмкіндік
береді.
Массивтің индекстелген элементтері – индекстелген айнымалылар деп
аталады, олар жай айнымалылар ретінде де пайдалана береді. Мысалға олар
амалдарда операнд ретінде, for, while, repeat операторларында, Readm
Readln, Write, Writeln операторларында параметр ретінде де қолданыла алады.
Оларға өз типіне сай келетін кез келген мәнді меншіктеуге болады.
Массивтің кез-келген элементтеріне арифметикалық операцияларды,
салыстыру және меншіктеу операторларын қолдануға болады. Сонымен қатар,
массивтерге Turbo Pascal программалау тіліндегі айнымалы типіне сәйкес
келетін барлық стандартты процедуралар және функциялар қолданылады.
Массивтің кез-келген элементіне нәтиже беру үшін, меншіктеу операторы
қолданылады:
Массив атауы[индексі] := нәтиже
Массивтің кез-келген элементтерімен жұмыс істегенде программалау
барысында олардың индексінің мәне типтер немесе айнымалылар бөлімінде
сипатталған шектеуден аспауы тиіс. Егер массив индексінің мәні сипатталған
шектеуден асып кетсе онда, синтаксистік қате тіркеліп, экранда Index type
is not compatible with declarationo деген сөз тіркестері шығаралады.
Массивтер қолданылатын программаларда {R+} директивасын жазу арқылы
массивтің шектеулерін тексеруге болады. Егер программада {R+}директивасы
беріліп, массив индексі шектеуден асып кетсе, онда экранға Range check
error сөз тіркесі шығарылады.
Массивтерді программада қолдану үшін Turbo Pascal программалау
тілінде оларды бірден var бөлімінде сипаттау жолы қарастырылған.
Жалпы жазылу түрі:
var
Массив атауы: array [индекс типі] of элемент типі;
Мысалы, бөлшек сандарға арналған он сегіз элементтен тұратын GR
массивін сипаттау:
var
GR: array [1..18] of real;
Мысал. Берілген тоғыз элементтен тұратын А массивіне бөлшек сандар
еншізіп, оларды дисплей бетіне ретімен шығару программасын қарастырайық:
{$R}
PROGRAM MASSIV; {Программа атауы}
Type {Типтерді сипаттау бөлімі}
Max = array [1..9] of real; {Шарт бойынша массив типі}
Var {айнымалыларды сипаттау бөлімі}
A: Mas; {Mas типті А - массиві}
I: integer; {циклды басқару айнымалысы}
BEGIN {негізгі программа басы}
WRITELN(‘A – массивінің 9 элементін енгізіңіз:’);
FOR I := 1 TO 9 DO {I – бойынша циклі}
READ(A[I]); {А[I] массивіне нақты сандарды
енгізу операторы}
FOR I := 1 TO 9 DO {I – бойынша циклі}
WRITE(‘ A[‘, I, ’] = ’, A[I]); {А[I] массивінің элементін
дисплейге шығару операторы}
END. {негізгі программа соңы}

II. БІР ӨЛШЕМДІ МАССИВТЕРДІ СҰРЫПТАУ АЛГОРИТМДЕРІ

Сұрыптау – қазіргі заманда мәліметерді өңдеу процессінің кең тараған
түрлерінің бірі. Сұрыптау деп – массив элементтерін белгіленген ережелер
бойынша орналастыру болып табылады. Мысалы, массивті өсуі не кемуі бойынша
сұрыптау.

2.1. Ауыстырмалы сұрыптау (көпіршік тәсілі)

Алгоритм 1-ші мен 2-ші элементтерді салыстырудан басталады. Егер 2-ші
элемент 1-шіден кіші болса, онда оларды орындарымен алмастырылады. Бұл
процесс қатар тұрған әр жұп элементтері үшін қайталанады, процесс бүкіл N
элементтері өңделмейінше қайталанады. Массивтің бір өтімінен кейін ең
үлкен элемент ең артқы (N-ші) орынға тұрғызылады. Алгоритм жалғаса береді,
сонда p-ші өтім кезінде алғаш (N-p) элементтері оң жақтағы көрші
элементтерімен салыстырылады. Егер келесі бір өтімде алмастырулар болмаса,
алгоритм өз жұмысын тоқтатады. Соңында ең жеңіл элементтер алгоритм
орындалуы барысында біртіндеп қалқып шығады.
for i := 1 to n-1 do
for j := n-1 downto i do
if a[j] a[j+1] then begin
x := a[j];
a[j] := a[j+1];
a[j+1] := x;
end;

2.2. Қойылымды сұрыптау
Басында алғаш тұрған екі элемент сұрыпталады. Олар сұрыпталған S
жиынын құрайды. Келесі элемент алынып, сұрыпталған S жиынына сол жағындағы
элементтері одан кіші етіліп, ал оң жағынан артық болып қойылады. Берілген
элементті жиынға тұрғызу орны – аралықты жартыға бөлу арқылы табылады.
Алгоритм өз жұмысын аяқтайды сол жағдайда, қашан N-ші орында тұрған элемент
өңделіп болады.

2.3.Таңдап алу арқылы сұрыптау
N элементтерден құралған массивінің ең үлкен элементі табылады (ол p
нөмерінде тұр делік), ол N-ші орында тұрған элементімен орындарын
ауыстырылады, мұнда бір шарт сақталуы тиіс: N p, яғни олар тең болмауы
керек. Қалған (N-1) элементтерден тағы да ең үлкені таңдап алынады да, N-1
орында тұрған элементпен алмастырылады. Өз жұмысын алгоритм 1-ші және 2-ші
орындарда тұрған элементтер сұрыпталғаннан кейін ғана өз жұмысын тоқтатады.
Ол үшін N-1 өтім керек болады екен. Осылай ең кіші элементтерді сұрыптауға
да қолдануға болады.
for i := 1 to n-1 do begin
k := i; x := a[i];
for j := i+1 to n do
if a[j] x then begin
k := j;
x := a[j];
end;
a[k] := a[i];
a[i] := x;
III. ЕКІ ӨЛШЕМДІ МАССИВТЕР (МАТРИЦА)
Екі өлшемді массив деп – элементі массивтің жол мен бағанында тұрған
орнына тәуелді болатын массив. Жалпы түрде матрицаның элементтері былай
белгіленеді A(I,J), мұндағы A – массивтің аты, I - жолдың индексі (нөмері),
J – бағанның индексі (нөмері).

3.1. Матрицаның Turbo Pascal тіліндегі сипаттамасы

Turbo Pascal тілінде екі өлшемді немесе көпе өлшемді массивтермен
жұмыс істеу үшін, олар сипаттау бөлімінде көрсетілуі тиіс.
Екі өлшемді массивті немесе матрицаны екі түрлі тәсілмен жазуға
болады:
I. матрицаның аты: array[жол саны] of array[баған саны] of
айнымалының типі;
II. матрицаның аты: array[жол саны, баған саны] of айнымалының
типі.

A [n, m] массивін сипаттау жолы:

i
А массиві: 1 2 3 ... n
j 1
2
.
..
m

var
A: array [1..n, 1..m] of integer;

Екі өлшемді массивті енгізу:
FOR I := 1 TO N DO
FOR J := 1 TO M DO
READ(A[I, J]);

Мысал. Берілген жиырма бес элементтен тұратын B[5, 5] екі өлшемді
массивке бөлшек сандар енгізіп, оларды дисплейге кесте түрінде шығару
программасы:
{$R}
PROGRAM MAS; {Программа атауы}
Type {Типтерді сипаттау бөлімі}
Max = array [1..5, 1..5] of real; {Шарт бойынша массив типі}
Var {айнымалыларды сипаттау бөлімі}
В: Mas; {Mas типті В - массиві}
I, J: integer; {циклды басқару айнымалылары}
BEGIN {негізгі программа басы}
WRITELN(‘В – массивінің элементтерін енгізіңіз:’);
FOR I := 1 TO 5 DO {I – бойынша циклі}
FOR I := J TO 5 DO {J – бойынша циклі}
READ(A[I, J]); {B[I, J] массивіне нақты сандарды
енгізу операторы}
FOR I := 1 TO 5 DO {I – бойынша циклі}
BEGIN
FOR I := J TO 5 DO {J – бойынша циклі}
WRITE(B[I, J], ‘ ‘); {B[I, J] массивінің элементін
дисплейге шығару операторы}
WRITELN;
END;
END. {негізгі программа соңы}

3.2. Квадрат матрицада индекстердің ара қатынасы

I=J – матрицаның элементтері бас диагональ бойында орналасқан.
IJ – элементтер бас диагональдың үстінде орналасқан
IJ - элементтер бас диагональдың астында орналасқан
I+J=N+I – элементтер қосалқы диагональ бойында орналасқан.
I+JN+I – элементтер қосалқы диагональдың үстінде орналасқан.
I+JN+I – элементтер қосалқы диагональдың астында орналасқан.

3. 3. Массивтерді қолдану ережелері

Анализ кезінде келесі екі сұраққа жауап беру керек:
1) Берілген есепті шешу үшін массив керек пе?
2) Егер керек болса, онда оның көлемі қандай болуы керек?
Массивті қолдану керек пе?
Бірінші сұрақтың мәні мынада: массивті тек қана ең керекті
жағдайларда ғана қойдалану тиімді. Осыған үш себеп бар:
Программаның үлкею, яғни қиындау барысында, көп массивті қолдана
отырып, индекстері де өсе береді. Сонда қателер саны де көбейе бастайды.
Программаның кодын ... жалғасы

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