Реттеу, сұрыптау алгоритмі

Деректерге көп қолданылатын амалдардың бірі – сұрыптау.

Сұрыптау дегеніміз – массив элементтерін белгілі бір ережені сақтайтындай етіп, реттеп орналастыру.

Сұрыптау ішкі және сыртқы деп бөлінеді. Сыртқы сұрыптауға сыртқы жадыдағы деректерді сұрыптау жатады. Ал ішкі сұрыптауға ішкі жадыға деректерді реттеп орналастыру жатады.

Ішкі сұрыптау бірнеше әдіспен орындалады:

1. Көпіршіту әдісі

Әдістің бұлай аталуы массивтің 1-ші және 2-ші элементтері салыстырылып, егер 1-ші элемент үлкен болса, олар орындарын ауыстырады, ал үлкен болмаса орнында қалады, сонда ауыр элемент астына түсіп жеңілі бетіне шығатын болғандықтан көпіршу сияқты көрінеді.

a₁, a₂, a₃, … , a_n тізбегі берілген. Элементтерін өсу реті бойынша реттеу керек.

aрг n, a

нәт a

басы бүт i, нақ Б

әзір i≤n-1

Б:=a[i];

a[i+1]:=Б

i:=1;

бітті

а – ны шығару.

Соңы.

Дәл осылай кемуі бойынша да реттеуге болады.

Массивтің ішінен ең үлкен элемент табылады. Ол элемент р-шы орында тұрсын. Сол элементті n-ші орындағы элементпен салыстырады. Егер n<>p болса, онда n-ші орында орналасқан элементпен орындарын ауыстырады. Әрі қарай қалған реттелмеген элементтердің ішінен тағы ең үлкен элемент табылады да, ол (n-1)-ші элементпен салыстырылады, егер ең үлкен элемент (n-1)-ші элементтен үлкен болса, орнында қалады да, болмаса орындарын ауыстырады. Осы процесс барлық элементтерге қолданылып шығады.

Алгоритмі келесідей болады:

Белгілеулер: a[1..n] –берілген массив болсын, r – массивтің реттелмеген элементтерінің саны.

1. R=n болсын.

2. Max=max{a[1..r]} табамыз.

3. Max<>r және a[max]<>a[r] болса, онда a{max] элементі мен a[r] элементі орындарын ауыстырады

4. әйтпесе R=r-1 деп реттелмеген келесі элементтерге көшеміз. Алғашқы r элементтер – реттелмеген элементтерді құрайды, ал соңғы n-r элементтер өсуі бойынша реттеледі.

5. Егер r=1 болса, онда реттеу аяқталады, әйтпесе 2-ші пунктке көшеді.
3. Кірістіру арқылы сұрыптау.

Алдында қарастырылған көпіршіту және сызықты сұрыптау әдістері кемімелі қадаммен сұрыптауға жатады. Шынында да, әрбір сұрыптау итерациясын орындаған сайын реттелмеген элементтер саны 1-ге кеміп отырады.

Ал кірістіру арқылы сұрыптау өзгеше принциппен орындалады:

Массивтің алғашқы 2 элементі реттеледі де реттелген s жиынын құрайды. Сосын келесі екі элемент реттеледі де сол жағынан үлкен элемент, оң жағынан кіші элемент орналаспайтындай етіп s –реттелген жиынға кірістіріліп отырады. S жиынға кірістірілетін элементтің орны дихотомия әдісімен анықталады.

Кірістіру әдісінде келесі бағалаулар дұрыс:

Салыстыру саны=1+2+[log₂3]+1+[log₂4]+1+…+[log₂(n-1)]+1=(n-1)+log₂(n-1)!=nlog₂n;

Меншіктеу саны: min=0; max=3+4+5+…+n+1=(n+4)(n-1)/2

Күрделілігі: O(n²)-меншіктеу саны бойынша, O(nlog₂n)-салыстыру саны бойынша.

1. 
   Реттелмеген массивте біртіндеп іздеу алгоритмі қалай жүреді?
   
2. 
   Реттелген массивте бинарлы іздеу алгоритмі қалай жүреді?
   
3. 
   Сұрыптаудың қандай әдістері бар?
   

Ұсынылатын әдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

• 
  негізгі түсініктер
  
• 
  ақпаратты сақтау
  
• 
  деректер структурасының классификациясы
  
• 
  деректер структурасына қолданылатын амалдар
  
• 
  программалау технологиясы
  

Деректер структурасы мен алгоритмдер программаның негізгі құраушысы болып табылады. Компьютердің өзі сол деректердің структурасы мен алгоритмдерден тұрады. Орнатылған деректердің структурасы екілік шамалар сақталған жады сөзі және регистрлер түрінде көрінеді. Аппаратураның конструкциясына бекітілген алгоритмдер – орандауға жататын, жадыға енгізілген деректерден команда – бұйрық түрінде ойластырылған электронды логикалық тізбекке айналдырылған қатаң ережелер. Сондықтан кез келген компьютердің жұмыс негізінде тек қана деректердің бір түрімен белгілі бір биттермен немесе екілік цифрлармен операцияларды орындауды білу жатады. Осы деректермен компьютер тек орталық процессордың бұйрықтар жүйесімен анықталатын, сәйкес өзгермейтін алгоритмдердің жиынымен жұмыс істейді.

Программалау тілдерінде қабылданған деректердің типтері натуралды, бүтін, нақты сандардан, литерлерден, жолдардан, т.б. тұрады.

Кейбір программалау тілдерінде деректердің типтері компиляторда анықталса, кейбіреуінде типті анықтап көрсету керек болады. Программада деректердің мәндері қанша қажет болса, сонша өзгеріп, ал типі өзгеріссіз қалуы керек.

Деректердің структурасы жалпы жағдайда деректер элементтерінің жиыны және олардың арасындағы байланыс жиыны деп қарастырылады.

Деректер структурасының классификациясы бірнеше белгілеріне қарай анықталады:

1. Деректердің физикалық структурасы

2. Деректердің логикалық структурасы

Деректердің машина жадысында қалай орналасатыны, физикалық көрінісі физикалық структурасы деп аталады.

Ал машина жадысында орналастырылуын есепке алмаған жағдайда деректердің қарастырылуы логикалық структурасы деп аталады.

Жалпы деректер структурасының типтері екіге бөлінеді:

1. Қарапайым немесе жай типтер

2. интегралданған- ауқымды типтер

Жай типтерге базалық, примитивті типтер жатады. Оларды биттен үлкен құрмалас бөліктерге бөлуге болмайды.

Ауқымды типтерге композитті, күрделі құрылымды типтер жатады. Олардың құрамдас бөлігі басқа бір структуралар болуы мүмкін.

Деректер элементтерінің арасында айқын берілген байланыстың бар болу, болмауына қарай деректердің структурасы тағы 2-ге бөлінеді:

1. байланысты

2. байланыссыз

Деректер структурасының маңызды белгілерінің бірі - өзгермелілігі- элементтердің саны және олардың арасындағы байланыс өзгеріп отырады.

Структуралардың өзгеруі элементтердің мәнінің өзгеруіне соқтырмайды. Сондықтан структуралардың өзгермелілігіне қарай үшке бөлінеді:

1. статикалық

2. жартылай статикалық

3. динамикалық

Деректердің тағы бір маңызды белгісі – реттелгендік. Бұл белгісіне қарай:

1. сызықты

2. сызықты емес структуралар болып бөлінеді.

Программалау тілдерінде «Деректер структурасы» мен «Деректер типі» ұғымдары тығыз байланысты. Кез келген деректер (тұрақты шама, айнымалы, функция мәні, өрнек т.б.) өздерінің типімен мінезделеді.

Әр тип бойынша ақпарат мына ұғымдарды бірмәнді анықтайды:

• 
  көрсетілген типтің деректерді сақтау структурасын, яғни дерекке ұяшық бөліп, онда қалай жазылатыны, екілік түрін ойластыруды;
  
• 
  сипатталған типті объектінің қабылдайтын мәндер жиынын;
  
• 
  сипатталған типті объектіге қолданылатын амалдар жиынын;
  

1. Құру

3. Таңдау

4. Жаңарту

Құру операциясы деректер структурасына жадыдан ұяшықтар бөлу болып табылады.

Жою операциясы құруға қарама қарсы, жадыдан деректерді өшіру болып табылады.

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

Жаңарту операциясы деректер структурасында деректер мәндерін өзгертуге көмектеседі.

Бұл операциялар барлық деректер структурасына жалпы қолданылатын операцияларға жатады, ал кейбір деректер структурасына қолданылатын арнаулы операциялар бар.

1. 
   Деректер структурасы деген не?
   
2. 
   Деректер структурасына қолданылатын амалдар
   
3. 
   Программалау технологиясы деген не?
   

Ұсынылатын әдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   сандық типтер
   

• 
  бүтін
  
• 
  нақты
  
• 
  ондық
  
• 
  сандық типтерге қолданылатын операциялар
  

2. 
   Биттік типтер
   
3. 
   Логикалық типтер
   
4. 
   Терілімді типтер
   
5. 
   Шектелген типтер
   
6. 
   Көрсеткіштер
   

Деректер структурасы қабылдайтын мәндерінің түрлеріне қарай келесі типтерге бөлінеді:

1. 
   Сандық типтер
   
2. 
   Биттік типтер
   
3. 
   Логикалық типтер
   
4. 
   Символдық типтер
   
5. 
   Терілімді типтер
   
6. 
   Шектелген типтер
   
7. 
   Көрсеткіштер
   
8. 
   Тізімдер
   
9. 
   Жазулар
   
10. 
    Файлдар
    
11. 
    Массивтер
    
12. 
    Жиындар
    
13. 
    Таблицалар
    
14. 
    Стектер
    
15. 
    Кезектер
    
16. 
    Дектер
    
17. 
    Жолдар
    
18. 
    Динамикалық типтер
    
19. 
    Графтар
    
20. 
    Ағаштар (бұтақтар)
    

1. 
   Сандық
   
2. 
   Биттік
   
3. 
   Логикалық
   
4. 
   Символдық
   
5. 
   Терілімді
   
6. 
   Шектелген
   
7. 
   Көрсеткіштер
   

Нақты типті деректердің өзі тұрақты нүктелі, айнымалы нүктелі болып бөлінеді, олардың да жадыдағы байттары әртүрлі. Бүтін сандардың мәні жадыда дәл анықталса, нақты сандардың мәні белгілі бір дәлдікпен анықталады.

Биттік типтер деректердің екілік разрядтарымен жұмыс жасауға көмектееді. Биттік типтер бір бірімен байланысы жоқ байттардың жиыны.

Логикалық типтер логикалық ақиқат, жалған, иә, жоқ сияқты мәндерді қабылдайтын, 1 байт орын алатын деректер.

Символдық типтер алдын ала анықталған символдар жиыныннан қабылданатын мәндер. Дербес ЭЕМ-дерде көбіне стандартты ASCII –символдар коды таблицасы орнатылған, одан басқа EBCDIC-кодтар таблицасы да бар. Символдық типті деректерге салыстыру, жалғастыру операциясы қолданылады.

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

Шектелген типтерге терілімді типтердің ішінен белгілі бір аралықты қамтитын деректерден құралатын, кей жағдайда қолданушы өзі анықтайтын деректер типтері жатады. Мысалы: жаз айлары, қыс айлары, демалыс күндері, т.б.

Көрсеткіштер деректер орналасқан ұяшықтың адресін анықтайтын типтер. Олар типтендірілген көрсеткіштер және типтендірілмеген көрсеткіштер деп бөлінеді. Егер типтендірілген көрсеткіш деп жарияланса, онда олар бүтінге көрсеткіш, символға көрсеткіш т.б. деп аталуы мүмкін. Ал типтендірілмеген көрсеткіштер кез келген ұяшықтың адресін анықтайды, ол деректердің мәніне көңіл аудармайды. Көрсеткіштер деректерді алмастыру уақытында жадыны реттеуге тиімді.

Өзін тексеру сұрақтары

1. Деректердің қандай типтері бар?

2. Сандық типтер қалайша бқлінеді?

3. Күрделі типтер қалайша бөлінеді?

Ұсынылатын әдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

7. 
   векторлар
   
8. 
   массивтер
   
9. 
   жиындар
   
10. 
    жазулар
    
11. 
    таблицалар
    

Деректердің статикалық структурасы базалық, примитивті структуралардың құрылымды жиынынан тұрады. Оларға жады тұрақты-автоматты түрде бөлінеді, себебі олардың мәндері өзгермейді.

Векторлар – бір өлшемді массивтер- бір типті саны санаулы элементтер жиынынан тұратын деректер. Вектордың әр элементінің нөмірі оның тұрған орнын анықтайды. Элементтері тізбектелген ұяшықтар жиынын құрайды. Элементтің типіне қарай жадыдан байттар бөлінеді. Жады көлемі элементтер санын элементтер ұзындығына көбейту арқылы анықталады.

Массивтер – екі өлшемді, көп өлшемді болады.

Біртипті саны санаулы элементтердің жиынтығынан тұратын, әрбір элементі индекспен номерленген, индекстерінің саны массив өлшемін білдіретін атаулы деректерді массив дейді.

Массивті қолдану үшін оның атауы және индексі анықталуы керек. Екі индексті массив екі өлшемді, үш индексті массив үш өлшемді деп аталады.

Жазулар (структуралар).

Әртүрлі типті деректерді анықтайтын өрістердің ақырлы реттелген жиыны жазулар деп аталады.

Жазуларды белгілі бір заттық облыстан алынған объектіні толық анықтап, программалау үшін қолданған тиімді. Жазу өрістермен құралады. Өрістерді компоненттер деп те атайды. Жазу деректер таблицасын еске түсіреді. Таблицаның бағандарының атаулары өрістер, таблицаның әр жолы жазу немесе жазба деп аталады Программада жазулар өздерінің атауымен және өріс атауымен біріктіріліп қолданылады.

Жиындар - біртипті, мәндері қайталанбайтын деректердің жиынтығы.

Жиын базалық типке жататын деректердің бәрін қабылдайды. Базалық тип 256 мүмкін мәндерден аспауы керек, жадыда 32 байтқа дейін орын алады және массивтер сияқты орналасады, элементтері индекстеледі.

Таблицалар - элементтері жазу болатын векторды айтуға болады. Вектор сияқты әр элементі индекстелмейді. Әр өрісті толық анықтайтын кілттік өріс тағайындалып, сол кілт бойынша деректер қолданылады. Кілт - біртипті көп жазулардың жиынынан таңдалынатын мәндері қайталанбайтын белгілі бір өріс. Бір таблицада бір немесе бірнеше кілт болуы мүмкін. Таблицаға логикалық деңгейдегі операциялар қолданылады: іздеу, сұрыптау.

Іздеу операциясы екі әдіспен орындалады:

1. Біртіндеп іздеу немесе сызықты іздеу

Деректер реттелмеген болса, элементтің кілті анықталып, кілттің мәнімен жазулар салыстырылады, сәйкестік болса жазудың табылғаны туралы ақпарат шығады, әйтпесе іздеу сәтсіз аяқталады.

2. Бинарлы іздеу.

Жазулар таблицаға алфавит бойынша немесе өсу реті бойынша енгізіледі. Белгілі бір жазуды іздеу таблицаның ортасындағы сол жазуға сәйкес кілттік өрістің мәнін зерттеуден басталады. Егер кілттің мәні үлкен болса, онда таблицаның үстіңгі жартысының ортасындағы жазуға сәйкес кілттің мәні тексеріледі, осы процедура таблицаның үстіңгі жартысында сәйкес жазу табылғанша жалғасады да, егер іздеу сәтті аяқталса іздеу тоқтатылады. Егер кілттің мәні кішкентай болса, онда таблицаның төменгі жартысының ортаңғы жазуына сәйкес кілт мәні тексеріледі,

Таблицаны сұрыптау белгілі бір ереже талабын қанағаттандыратындай етіп жазуларды реттеуге жатады. Сұрыптау алгоритмдері көп, оны таңдауға әсер ететін факторлар:

- Қол астында бар жады ресурсы: енгізілетін және шығарылатын жиындар жадының әртүрлі облысында орналасуы керек пе, әлде шығарылатын жиындар енгізілетін жиындардың орнына жазылуы керек пе - сол зерттеледі.

- Енгізілетін жиындар бастапқы кезден бастапреттелген болуы.

- Операцияның уақытша мінездемесі: алгоритмнің жылдам орындалуы үшін кілттік өрістің мәндері сандық тип немесе символдық тип болуы ескеріледі.

- Алгоритмнің күрделілігі: алгоритм неғұрлым қарапайым болса, орындалуы соғұрлым жеңіл болады.

Сұрыптау стратегиялары:

1. Таңдау стратегиясы. - енгізілетін жиыннан реттелу шартын қанағаттандыратын элемент таңдалынып алынады да номеріне байланысты орны анықталып, шығарылатын жиынға енгізіледі.

2. Енгізу стратегиясы - енгізілетін жиыннан номерлі элемент таңдалынып, реттелу шартына сәйкес орнын анықтап шығарылатын жиынға енгізіледі.

3. Тарату, орналастыру стратегиясы - енгізілетін жиын бірнеше ішкі жиынға бөлінеді де, сұрыптау әр ішкі жиында жүргізіледі.

4 Біріктіру, жымдастыру стратегиясы - Сұрыпталған әрбір ішкі жиынды жымдастыру арқылы шығарылатын жиын құрастырылады.
Көпмүшелікті Горнер схемасымен есептеу алгоритмі
y= a₀xⁿ₊a₁ x^n-1+…+a_n-1 x + a_n теңдеуімен берілген көрсеткіші n-ге тең көпмүшеліктің мәнін есептеү керек.

Горнер схемасы бұл көпмүшеліктегі көбейту және қосу амалдарының санын максималды азайтады.

n=2 болсын, сонда көпмүшелік былай жазылады:

y= a₀x²₊a₁x¹+a₂ -> 3көбейту, 2 қосу амалдары бар бұл өрнекті былай жазуға болады:

y= (a₀x²₊a₁)x+a₂ -> 2 көбейту, 2 қосу амалы болды.

n=3 болсын:

y= a₀x³₊a₁x²+a₂x+a₃ – 9 амал бар

y= ((a₀x₊a₁)x+a₂)x+a₃ – 6 амал бар. Сонда бұл әдіс алгоритмі 2 операциядан тұрады:

1. 
   x-ке көбейту
   
2. 
   келесі коэффициентті қосу
   

арг n, x, a

нет y

басы бүт i

i:=0

әзір i

қ. б.

i:=i+1

қ. с.

бітті

соңы
Өзін тексеру сұрақтары

1. 
   векторлар деп нені ұғасыз?
   
2. 
   массивтердің неше түрі бар?
   
3. 
   жиындар қалайша жазылады?
   
4. 
   жазулар қалайша қолданылады?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

1. 
   жартылай статикалық деректер структурасының жалпы мазмұндамасы.
   
2. 
   Стектер (LIFO кезегі)
   
3. 
   FIFO кезегі
   
4. 
   Дектер
   
5. 
   Жолдар
   

Жартылай статикалық деректер структурасының белгілері:

- ұзындығы өзгермелі және оны өзгерту процедурасы қарапайым

- структураның ұзындығын өзгерту белгілі бір шектік мәннен асып кетпеуі керек.

Жартылай статикалық деректер структурасының логикалық деңгейі сызықты тізім қатынасымен байланысқан деректер структурасы. Элементтері реттік номермен қолданылады. Физикалық деңгейі - бір бағытты байланысқан тізім, әрбір келесі элемент ағымдағы элементті көрсетіп тұрған көрсеткіш адресімен анықталады.

Стектер (LIFO кезегі).

Стек - өзгермелі ұзындықты, енгізу, шығару тек бір жақтан ғана жүргізілетін тізбектелген тізім.

Стек төбесі тізімнің қай жақ шетінен элемент енгізілетін, шығарылатын болса, сол жақта болады. "Соңғы келіп, бірінші кету" принципіне негізделген кезекті LIFO кезегі дейді. Стекке қолданылатын операциялар:

- кезекке жаңа элемент енгізу

- элементті шығарып тастау

- стектегі элемент санын анықтау

- стекті тазалау

- стек төбесінен бұзбау арқылы элементті оқу.

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

"Бірінші келіп, бірінші кету" принципіне негізделген кезекті FIFO кезегі дейді. Мұнда элементтерді кезекке енгізу тек бір жақтан ғана орындалады, оны кезек соңы дейді. Ал элементтерді шығару екінші жағынан орындалады, оны кезектің басы дейді. Бұл кезектерде екі көрсеткіш болады: біреуі кезек басын, біреуі кезек соңын көрсетіп тұрады. Элементті кезекке енгізгенде көрсеткіш соңының адресіне жазылады да, көрсеткіш бірге өседі, ал элементті кезектен шығарғанда көрсеткіш басының адресіне жазылады да, көрсеткіш бірге кемиді.

Дектер - екі соңы бар кезектер. Элементті енгізу, шығару кезектің екі жағынан бірдей орындалады. Дектердің логикалық, физикалық структурасы сақиналы FIFO кезегімен бірдей. Дектердің басы және соңы болмайды, сол жақ шеті, оң жақ шеті болады. Оларға қолданылатын операциялар:

- оң жақтан элементті енгізу

- сол жақтан элементті енгізу

- оң жақтан элементті шығару

- сол жақтан элементті шығару

- өлшемін анықтау

- тазалау

Жолдар - алфавит деп аталатын ақырлы символдық жиындарға жататын сызықты, реттелген символдар тізбегі.

Жиынның қасиеттері:

- алфавит тұрақты болса да жолдардың ұзындығы өзгермелі болады

- жолдың символдарын қолдану оның бір шетінен басталады, сондықтан жолдың тізбегі реттелген болуы керек.

- жолдың әрбір элементі қолдануға жатады

Жиынға қолданылатын операциялапр:

- жол ұзындығын анықтау

- жолдарды меншіктеу

- жолдарды тіркеу - конкатенация

- ішкі жолды анықтау

- жолдан ішкі жолды іздеу
Өзін тексеру сұрақтары

1. 
   жартылай статикалық деректер структурасы?
   
2. 
   Стектер (LIFO кезегі) деген не?
   
3. 
   FIFO кезегін қалай түсінесіз?
   
4. 
   Дектер деген не?
   
5. 
   Жолдар деген не?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

• 
  Жадыда деректердің байланысының берілуі
  
• 
  Сызықты байланысты тізімдер
  
• 
  Сызықты емес тармақталған тізімдер
  

Деректердің динамикалық структурасы өлшемі айнымалы, жадыдан алдын ала орын босатылмайтын, программаны орындаған сайын мәндері, мәндерінің саны өзгеріп отыратын деректер.

Динамикалық деректердің элементтерінің арасында байланыс орнату үшін көрсеткіштер қолданылады. Олар әр динамикалық элементтің жадыдағы адресін көрсетіп тұрады. Динамикалық деректер структурасының элементтері екі өрістен тұрады:

1. деректер өрісі - ақпараттық өріс, ол массив, жазу, вектор т.б. бола алады.

2. байланыс өрісі - белгілі бір элементті басқа структураның элементімен байланыстыратын бір немесе бірнеше көрсеткіштер бола алады.

Деректердің байланыстырылып көрінуінің жетістігі – структураларды барынша өзгерту мүмкіндігінде:

1. 
   структуралардың мөлшері машиналық жадының қолдануға болатын көлемімен шектеледі;
   
2. 
   структура элементтері логикалық тізбегін өзгерткенде жадыдағы деректерді ауыстырудың қажеті жоқ, оның орнына көрсеткіштер жылжиды, түзетіледі.
   

3. 
   көрсеткіштермен жұмыс жасау үшін программисттің квалификациясы жоғары болуы керек;
   
4. 
   байланыс қрістеріне қосымша жады бөлінеді;
   
5. 
   уақытты үнемдемейді;
   

Тізім дегеніміз элементтерінің саны өзгермелі, енгізу, шығару операцияларын қолдануға болатын реттелген жиын.

Элементтерінің арасында көршілік қатынасты бейнелейтін тізімді сызықты тізім дейді.

Бірбайланысты тізімді өңдеу тиімді емес, себебі қарама қарсы бағытта қозғалу мүмкіндігі жоқ. Ондай мүмкіндіктер екі байланысты тізімдерде бар, оларда екі көрсеткіш болады, біреуі алдыңғы біреуі келесі элементті көрсетіп тұрады. Сызықты байланысты тізімде NEXT өрісі бар – ол тізімдегі келесі элементті көрсеткіш деп аталады. PREV өрісі бар – ол тізімдегі алдыңғы элементті көрсеткіш деп аталады. Тізімдегі соңғы элементті көрсеткіш те қолданылады, ол NIL болады. Екі көрсеткішті анықтау, оларды жылжыту арқылы элементтерді өңдеу көп уақытты алады, бірақ тізімге қолданылатын кейбір операцияларға оларды қолдану тиімді.

Сызықты емес тармақталған тізімдер деп элементтері тізім болатын тізімдерді айтады. Егер екі байланысты тізімде көрсеткіштердің біреуі басқа көрсеткіш ретіне кері ретпен берілсе, ондай тізім сызықты тізім болады, егер көрсеткіштің біреуі кез келген ретпен берілсе, онда тізім сызықты емес тізім деп аталады.

Тармақталған тізім үш ұғыммен сипатталады: реті, тереңдігі, ұзындығы.

Реті. Тізім ішінде элементтер пайда болатын тізбекпен анықталатын тізім элементіне транзитивті қатынас берілген. (x,y,z) тізімінде х атомы у-тің алдыңғысы, ал у атомы z-тің алдыңғысы, сонда х атомы z-тің алдыңғысы болатыны білінеді. Берілген тізім (y,z,x) тізіміне эквивалентті болмайды.

Тізімді графикалық схема көмегімен бергенде тізім реті горизонтальды стрелкамен анықталады: элементтен стрелка шығып тұрса,онда ол көрсетіп тұрған элементтің алдыңғысы екенін білдіреді.

Тереңдігі. Тізім ішіне сиятын элементтердің максималды деңгейі тереңдігін білдіреді. Тізім ішінде ішкі тізім болса, олар кірістірілген тізімдер болады және дөңгелек жақшаға алынады.

• 
  Жадыда деректердің байланысы қалай беріледі?
  
• 
  Сызықты байланысты тізімдер деген не?
  
• 
  Сызықты емес тармақталған тізімдер деген не?
  

6. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
7. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
8. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
9. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
10. 
    Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
    

• 
  Графтар-логикалық структурасы,анықтамасы,орграф ұғымы
  
• 
  Бұтақтар
  

• 
  Анықтамасы
  
• 
  Екілік бинарлы бұтақтар
  
• 
  ЭЕМ-дегі жазылуы
  
• 
  Балансты бұтақтар
  

Графтар.

Бұл - күрделі объектінің байланысы мен қасиеттерін көрсететін, күрделі, сызықты емес көпбайланысты динамикалық структура.

Көпбайланысты структураның қасиеттері:

1. Әрбір элементке (түйін, төбе) саны еркін алынған сілтемелер болуы мүмкін.

2. Әрбір элемент кез келген басқа элементпен кез келген рет байланысады.

3. Әрбір байланыстырушы жасаушының (қабырға, доға) бағыты және салмағы болады.

Граф түйіндерінде объектінің элементтері туралы ақпарат болады. Түйіндердің арасындағы байланыс граф қабырғаларымен беріледі. Қабырғалардың бағыты көрсетілсе, оны бағдарлы қабырға, егер бағыты көрсетілмесе бағдарсыз қабырға деп аталады.

Барлық қабырғалары бағдарлы болса, ондай графты орграф дейді, егер байланыс қабырғалары бағытталмаған болса - бағдарсыз граф, егер бағытты және бағытсыз қабырғалары бар болса - аралас граф дейді. Қабырғасыз графты нөл граф дейді.

Бағдарлы графтың түйінге енетін қабырғалар саны түйін кірісінің жартыдәрежесі, ал шығатын қабырғалар саны шығыс жарты дәрежесі деп аталады. Графтың кіріс, шығыс қабырғалар саны кез келген болады, болмауы да мүмкін.

Егер графтың қабырғаларына қандай да бір мәндер сәйкес болса, онда графты және қабырғаларды өлшенген дейді. Графтың параллель қабырғалары бар болса, оны мультиграф дейді. Басқа жағдайда жай граф дейді.

Графқа жол - қабырғалармен байланыстырылған түйіндер тізбегі. Жол элементарлы жол деп аталады, егер графтың қабырғалары әр түрлі болса, егер төбелері әр түрлі болса, онда жол жай жол деп аталады. Түйіннің өзіне қайту жолы бар болса, онда циклдық жол деп аталады. Графтың екі түйіні қатарлас деп аталады егер оның бір түйінінен екінші түйініне жол бар болса. Түйін инцидентті деп аталады, егер ол граф төбемі болса, яғни қабырға осы түйінге бағытталса.

Ағаштар.

Келесі қасиеттері бар графтарды ағаштар дейді:

- Басқа ешбір элемент сілтемейтін жалғыз элементі (түйін, төбе) бар болса және ол түбір деп аталады.

- Түбірден бастап элементтерде бар белгілі бір көрсеткіштер тізбегі бойымен структураның басқа кез келген элементіне қатынас жасауға болса.

- Түбірден басқа әрбір элементке тек бір ғана сілтеме жасалса, яғни әрбір элементтің жалғыз адресі болса.

Бағдарлы ағаш деп түбір деп аталатын бір төбесі бар, кіріс жартыдәрежесі нөлге тең, басқа кіріс жартыдәрежелері 1-ге тең болатын циклдік графты айтады. Бұл ағаштардың ең болмағанда бір төбесі бар болады. Аластатылған, дара төбе де бағдарлы ағаш деп аталады.

Шығыс жартыдәрежесі нөлге тең бағдарлы ағаштың төбесі ілінген, соңғы төбе деп аталады. Одан басқа төбелері тармақталу төбелері деп аталады. Түбірден әлдебір төбеге дейінгі жолдың ұзындығы осы төбенің деңгейі - немесе ярус номері деп аталады. Түбір деңгейі нөлге тең болады, ал басқа төбелердің деңгейлері түбір мен төбелердің арасындағы ұзындықпен анықталады, немесе төбелер деңгейлерінің номерлерінің модулі бойынша айырмасына тең.

Бинарлы ағаштар.

m - арлы ағаштар бар, олар әрбір төбелердің шығыс жартыдәрежесі m-нен кіші не тең болатын ағаштар. m=0,1,2,3,... Егер әрбір төбеніңғ шығыс жартыдәрежесі m-ге немесе нөлге тең болса, оны толық ағаш немесе m - арлы ағаш дейді.

m=2 болғанда ағаштарды бинарлы немесе толық бинарлы дейді.

Кез келген ағашты, тоғайларды бинарлы ағашпен көрсету.

1. Әрбір түйінде үлкен ұлға (вертикальды жалғау) тек бір ғана бұтақ қалдыру.

2. Горизонтальды қабырғалармен бір әкелі барлық бауырларды жалғастыру.

3. Сонда мына ережемен ағаш қайта құрылады: сол жақтағы ұл - берілген төбенің астында орналасқан төбе, оң жақ ұл - берілген төбенің оң жағында орналасқан төбе, яғни яруста орналасқан төбе.

4. Ағашты вертикальды бұтақтары сол жақтағы ұлдарды, горизонтальды бұтақтары оң жақтағы ұлдарды көрсететіндей етіп төңкеру.

Нәтижесінде кез келген ағашты бинарлы ағашқа алмастырғанда түбірлі төбеге ілінген сол жақтағы ішкі ағаш түріндегі ағаш алынады.

Балансталған ағаш. Бинарлы ағашта іздеу операциясын жылдамдатуға көмектеседі. Балансты ағаш деп әрбір түйін үшін оның екі ішкі ағашының биіктігінің айырмашылығы біреу болса ғана айтады.

Өзін тексеру сұрақтары

1. 
   Графтар қайда қолданылады?
   
2. 
   Бұтақ деген не?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.
   

Дискілік жадының физикалық структурасы

Тізбекті файлдар

Сыртқы сұрыптау

Бөлімдермен ұйымдастырылған файлдар
Дискілік жадының оперативті жадыға қарағанда құрылысы да, ақпаратты қолдануы да басқаша. Қатты магнитті дискілерде жинақтағыш екі жағынан да ферромагнитті материалмен қапталған, бірнеше ішкі дискілердің жиынтығынан тұрады.Жазу-оқу механизмі дискілер арасынна кірістірілетін тісше, тарақша сияқты.

Тізбектелген файлдар.

Сыртқы жадыдағы файлдық структураның қарапайым түрінің бірі реттелмеген тізбектелген файлдар. Мұнда іздеу операциясы сызықты түрде жүргізіледі.

Сыртқы сұрыптау. Сыртқы жадыда деректерді сұрыптау 2 этаптан тұрады:

1. бөлшектеп сұрыптау

2. жымдастыру

Бірінші этапта сұрыпталатын тізбек бірнеше кішкене бөлшектерге бөлініп барып, әрқайсысы сұрыпталады, ал екінші этапта әрбір сұрыпталған бөлшектер бір бірімен жымдастырылады.

Бөлімдермен ұйымдастырылған файлдар. Кез келген ретпен файлға бөлінген жадыда орналастырылған бірнеше ішкі файлдарға бөлінген тізбекті айтады. Әрбір ішкі файлдың өзінің атауы, әр бөлігінің атауы болады, бәрақ операциялық жүйе бір бөлімге жататын ішкі файлдарды бір файл түрінде қарастырады.

Структуралы-кітапханалық файл 3 бөліктен тұрады: анықтама бөлімі, тақырып, деректер бөлімі. Анықтама бөлігінде файл параметрлері жазылады: тақырыптың өлшемі, деректер бөліміндегі бос кеңістіктің басталу адресі. Тақырып әр жолы бір бөлімнен тұратын таблица іспеттес. Әр бөлім үшін бөлім атауы, деректер облысындағы бөлім адресі, бөлім ұзындығы беріледі.

Өзін тексеру сұрақтары

2. Тізбекті файлдар деген не?

3. Сыртқы сұрыптауды қалай ұғасыз?

Ұсынылатын әдебиеттер

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.