Деректер структурасыныЈ классификациясы

ДеректердіЈ структурасы жалпы жа“дайда деректер элементтерініЈ жиыны жЩне олардыЈ арасында“ы байланыс жиыны деп ›арастырылады.

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

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

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

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

Ал машина жадысында орналастырылуын есепке алма“ан жа“дайда деректердіЈ ›арастырылуы логикалы› структурасы деп аталады.

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

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

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

Жай типтерге базалы›, примитивті типтер жатады. Оларды биттен Їлкен ›±рмалас бйліктерге бйлуге болмайды.

Ау›ымды типтерге композитті, кЇрделі ›±рылымды типтер жатады. ОлардыЈ ›±рамдас бйлігі бас›а бір структуралар болуы мЇмкін.

Деректер элементтерініЈ арасында ай›ын берілген байланыстыЈ бар болу, болмауына ›арай деректердіЈ структурасы та“ы 2-ге бйлінеді:

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

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

Деректер структурасыныЈ маЈызды белгілерініЈ бірі - йзгермелілігі- элементтердіЈ саны жЩне олардыЈ арасында“ы байланыс йзгеріп отырады.

СтруктуралардыЈ йзгеруі элементтердіЈ мЩнініЈ йзгеруіне со›тырмайды. Сонды›тан структуралардыЈ йзгермелілігіне ›арай Їшке бйлінеді:

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

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

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

ДеректердіЈ та“ы бір маЈызды белгісі – реттелгендік. Б±л белгісіне ›арай:

1. сызы›ты

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

Программалау тілдерінде «Деректер структурасы» мен «Деректер типі» ±“ымдары ты“ыз байланысты. Кез келген деректер (т±ра›ты шама, айнымалы, функция мЩні, йрнек т.б.) йздерініЈ типімен мінезделеді.

Шр тип бойынша а›парат мына ±“ымдарды бірмЩнді аны›тайды:

1. 
   кйрсетілген типтіЈ деректерді са›тау структурасын, я“ни дерекке ±яшы› бйліп, онда ›алай жазылатыны, екілік тЇрін ойластыруды;
   
2. 
   сипаттал“ан типті объектініЈ ›абылдайтын мЩндер жиынын;
   
3. 
   сипаттал“ан типті объектіге ›олданылатын амалдар жиынын;
   

1. љ±ру

3. ТаЈдау

4. ЖаЈарту

љ±ру операциясы деректер структурасына жадыдан ±яшы›тар бйлу болып табылады.

Жою операциясы ›±ру“а ›арама ›арсы, жадыдан деректерді йшіру болып табылады.

ТаЈдау операциясын структуралардыЈ йз ішінде деректерге р±›сат алу Їшін программист ›олданады. Р±›сат алу операциясыныЈ тЇрі ›ажетті деректер структурасыныЈ типінен тЩуелді.

ЖаЈарту операциясы деректер структурасында деректер мЩндерін йзгертуге кймектеседі.

Б±л операциялар барлы› деректер структурасына жалпы ›олданылатын операциялар“а жатады, ал кейбір деректер структурасына ›олданылатын арнаулы операциялар бар.

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

°сынылатын Щдебиеттер

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

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

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

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

Деректер структурасы ›абылдайтын мЩндерініЈ тЇрлеріне ›арай келесі типтерге бйлінеді:

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.
   

1. 
   векторлар
   
2. 
   массивтер
   
3. 
   жиындар
   
4. 
   жазулар
   
5. 
   таблицалар
   

ДеректердіЈ статикалы› структурасы базалы›, примитивті структуралардыЈ ›±рылымды жиынынан т±рады. Олар“а жады т±ра›ты-автоматты тЇрде бйлінеді, себебі олардыЈ мЩндері йзгермейді.

Векторлар – бір йлшемді массивтер- бір типті саны санаулы элементтер жиынынан т±ратын деректер. ВектордыЈ Щр элементініЈ нймірі оныЈ т±р“ан орнын аны›тайды. Элементтері тізбектелген ±яшы›тар жиынын ›±райды. ЭлементтіЈ типіне ›арай жадыдан байттар бйлінеді. Жады кйлемі элементтер санын элементтер ±зынды“ына кйбейту ар›ылы аны›талады.

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

Біртипті саны санаулы элементтердіЈ жиынты“ынан т±ратын, Щрбір элементі индекспен номерленген, индекстерініЈ саны массив йлшемін білдіретін атаулы деректерді массив дейді.

Массивті ›олдану Їшін оныЈ атауы жЩне индексі аны›талуы керек. Екі индексті массив екі йлшемді, Їш индексті массив Їш йлшемді деп аталады.

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

ШртЇрлі типті деректерді аны›тайтын йрістердіЈ а›ырлы реттелген жиыны жазулар деп аталады.

Жазуларды белгілі бір затты› облыстан алын“ан объектіні толы› аны›тап, программалау Їшін ›олдан“ан тиімді. Жазу йрістермен ›±ралады. ирістерді компоненттер деп те атайды. Жазу деректер таблицасын еске тЇсіреді. ТаблицаныЈ ба“андарыныЈ атаулары йрістер, таблицаныЈ Щр жолы жазу немесе жазба деп аталады Программада жазулар йздерініЈ атауымен жЩне йріс атауымен біріктіріліп ›олданылады.

Жиындар - біртипті, мЩндері ›айталанбайтын деректердіЈ жиынты“ы.

Жиын базалы› типке жататын деректердіЈ бЩрін ›абылдайды. Базалы› тип 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. 
   структура элементтері логикалы› тізбегін йзгерткенде жадыда“ы деректерді ауыстырудыЈ ›ажеті жо›, оныЈ орнына кйрсеткіштер жылжиды, тЇзетіледі.
   

1. 
   кйрсеткіштермен ж±мыс жасау Їшін программисттіЈ квалификациясы жо“ары болуы керек;
   
2. 
   байланыс ›рістеріне ›осымша жады бйлінеді;
   
3. 
   уа›ытты Їнемдемейді;
   

Тізім дегеніміз элементтерініЈ саны йзгермелі, енгізу, шы“ару операцияларын ›олдану“а болатын реттелген жиын.

ЭлементтерініЈ арасында кйршілік ›атынасты бейнелейтін тізімді сызы›ты тізім дейді.

Бірбайланысты тізімді йЈдеу тиімді емес, себебі ›арама ›арсы ба“ытта ›оз“алу мЇмкіндігі жо›. Ондай мЇмкіндіктер екі байланысты тізімдерде бар, оларда екі кйрсеткіш болады, біреуі алдыЈ“ы біреуі келесі элементті кйрсетіп т±рады. Сызы›ты байланысты тізімде NEXT йрісі бар – ол тізімдегі келесі элементті кйрсеткіш деп аталады. PREV йрісі бар – ол тізімдегі алдыЈ“ы элементті кйрсеткіш деп аталады. Тізімдегі соЈ“ы элементті кйрсеткіш те ›олданылады, ол NIL болады. Екі кйрсеткішті аны›тау, оларды жылжыту ар›ылы элементтерді йЈдеу кйп уа›ытты алады, біра› тізімге ›олданылатын кейбір операциялар“а оларды ›олдану тиімді.

Сызы›ты емес тарма›тал“ан тізімдер деп элементтері тізім болатын тізімдерді айтады. Егер екі байланысты тізімде кйрсеткіштердіЈ біреуі бас›а кйрсеткіш ретіне кері ретпен берілсе, ондай тізім сызы›ты тізім болады, егер кйрсеткіштіЈ біреуі кез келген ретпен берілсе, онда тізім сызы›ты емес тізім деп аталады.

Тарма›тал“ан тізім Їш ±“ыммен сипатталады: реті, тереЈдігі, ±зынды“ы.

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

Тізімді графикалы› схема кймегімен бергенде тізім реті горизонтальды стрелкамен аны›талады: элементтен стрелка шы“ып т±рса,онда ол кйрсетіп т±р“ан элементтіЈ алдыЈ“ысы екенін білдіреді.

ТереЈдігі. Тізім ішіне сиятын элементтердіЈ максималды деЈгейі тереЈдігін білдіреді. Тізім ішінде ішкі тізім болса, олар кірістірілген тізімдер болады жЩне дйЈгелек жа›ша“а алынады.

• 
  Жадыда деректердіЈ байланысы ›алай беріледі?
  
• 
  Сызы›ты байланысты тізімдер деген не?
  
• 
  Сызы›ты емес тарма›тал“ан тізімдер деген не?
  

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

• 
  Графтар-логикалы› структурасы,аны›тамасы,орграф ±“ымы
  
• 
  Б±та›тар
  
• 
  Аны›тамасы
  
• 
  Екілік бинарлы б±та›тар
  
• 
  ЭЕМ-дегі жазылуы
  
• 
  Балансты б±та›тар
  

Графтар.

Б±л - кЇрделі объектініЈ байланысы мен ›асиеттерін кйрсететін, кЇрделі, сызы›ты емес кйпбайланысты динамикалы› структура.

Кйпбайланысты структураныЈ ›асиеттері:

1. Шрбір элементке (тЇйін, тйбе) саны еркін алын“ан сілтемелер болуы мЇмкін.

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

3. Шрбір байланыстырушы жасаушыныЈ (›абыр“а, до“а) ба“ыты жЩне салма“ы болады.

Граф тЇйіндерінде объектініЈ элементтері туралы а›парат болады. ТЇйіндердіЈ арасында“ы байланыс граф ›абыр“аларымен беріледі. љабыр“алардыЈ ба“ыты кйрсетілсе, оны ба“дарлы ›абыр“а, егер ба“ыты кйрсетілмесе ба“дарсыз ›абыр“а деп аталады.

Барлы› ›абыр“алары ба“дарлы болса, ондай графты орграф дейді, егер байланыс ›абыр“алары ба“ытталма“ан болса - ба“дарсыз граф, егер ба“ытты жЩне ба“ытсыз ›абыр“алары бар болса - аралас граф дейді. љабыр“асыз графты нйл граф дейді.

Ба“дарлы графтыЈ тЇйінге енетін ›абыр“алар саны тЇйін кірісініЈ жартыдЩрежесі, ал шы“атын ›абыр“алар саны шы“ыс жарты дЩрежесі деп аталады. ГрафтыЈ кіріс, шы“ыс ›абыр“алар саны кез келген болады, болмауы да мЇмкін.

Егер графтыЈ ›абыр“аларына ›андай да бір мЩндер сЩйкес болса, онда графты жЩне ›абыр“аларды йлшенген дейді. ГрафтыЈ параллель ›абыр“алары бар болса, оны мультиграф дейді. Бас›а жа“дайда жай граф дейді.

Граф›а жол - ›абыр“алармен байланыстырыл“ан тЇйіндер тізбегі. Жол элементарлы жол деп аталады, егер графтыЈ ›абыр“алары Щр тЇрлі болса, егер тйбелері Щр тЇрлі болса, онда жол жай жол деп аталады. ТЇйінніЈ йзіне ›айту жолы бар болса, онда циклды› жол деп аталады. ГрафтыЈ екі тЇйіні ›атарлас деп аталады егер оныЈ бір тЇйінінен екінші тЇйініне жол бар болса. ТЇйін инцидентті деп аталады, егер ол граф тйбемі болса, я“ни ›абыр“а осы тЇйінге ба“ытталса.