1-3

Лекц -1  Өгөгдлийн бүтэц 

   Өгөгдлийн бүтэц гэдэг нь өгөгдлийг үр ашигтай ашиглах боломжтой байдлаар хадгалах буюу зохион байгуулахыг хэлнэ. Өөр өөр төрлийн өгөгдлийн бүтцүүд нь өөр өөрийн гэсэн тусгай үүрэгтэй болон давуу талтай байдаг.  Жишээ нь tree нь өгөгдлийн сан зохион байгуулахад илүү тохиромжтой байдаг бол хэш хүснэгт нь хөрвүүлэгчдэд тодорхойлогч хайх зорилгоор ашиглагддаг.  Өгөгдлийн бүтцүүд нь их хэмжээний өгөгдлүүдийг үр ашигтайгаар зохион байгуулах зорилготой жишээ нь: томоохон хэмжээний өгөгдлийн сан болон интернэт хаяглалтын үйлчилгээнд ашигладаг. Аливаа нэгэн үр ашигтай алгоритмийг зохион байгуулахад зөв өгөглийн санг ашиглах нь чухал. Зарим нэгэн программчиллийг загварчилахдаа алгоритм гэхээсээ илүүтэйгээр өгөгдлийн санг түлхүү ашигладаг. Хадгалах болон дуудаж ашиглах үйлдлүүд нь Үндсэн болон хоёрдогч санах ойн аль алинд нь ашиглагдаж болно.

Энгийн өгөгдлийн бүтцүүд

Өгөгдлийн бүтцийн жагсаалт

Массив буюу Хүснэгт (Array)

Стек, Stack

Дараалал, Queue

Граф, Graph

Мод, Tree

Овоолго, Heap

Хэш хүснэгт, Hash Table

Үндсэн зарчим

Өгөгдлийн бүтэц нь ерөнхийдөө өөрөө санах ойд хадгалагдсан , хөтөлбөрийн удирдагдаж болох юм гэсэн хаягийн нь битийн мөр заасан нь санах ойд ямар нэг газарт нь нөхөж суулгах нь компьютерийн чадвар, нөөц мэдээлэл дээр суурилсан байдаг. Тиймээс бүртгэлийн болон массив өгөгдлийн бүтэц арифметик үйл ажиллагаанд мэдээллийн зүйлсийн хаягуудыг тооцоолох үндэслэсэн байх; холбоотой өгөгдлийн бүтцүүдийн бүтэц нь өөрөө хүрээнд өгөгдөл зүйлсийн хаягуудыг хадгалах суурилсан байдаг байна. Олон өгөгдлийн бүтцүүд нь заримдаа

 ( XOR холбосон шиг), төрийн бус ердийн байдлаар нэгтгэн аль аль нь зарчмуудыг ашиглаж байна.  Өгөгдлийн бүтцийн шийдэл нь ихэвчлэн байгаа бүтэц, жишээ бий болгох, удирдахыг журмын багцыг бичих шаардлагатай. Өгөгдлийн бүтцийн үр ашигтай эдгээр үйл ажиллагаа нь тус тусад нь дүн шинжилгээ хийж болохгүй. Энэ ажиглалт нь хийсвэр өгөгдлийн төрөл Хэрэв энэ гүйцэтгэж болох үйл ажиллагаанд шууд бус байдлаар тодорхойлж байдаг бөгөөд энэ нь өгөгдлийн бүтэц, (тэдний орон зай , цаг хугацааны зардал гэх мэт) эдгээр үйл ажиллагааны шинж чанарын математик онолын үзэл баримтлалыг урам дэм өгдөг.

Дэмждэг хэл

Ийм BCPL ( үндсэн Combined Programming Language) , өгөгдлийн бүтцүүдийн хувьд дутмаг дэмжлэг үзүүлэх ихэнх угсралт хэл , зарим нь доод түвшний хэл . Олон өндөр түвшний програмчлалын хэл, гэх мэт зарим MASM дээд шатны угсралт хэл, , нөгөө талаас , тусгай байдгийг мэдэх , эсвэл , бусад барьсан ийм С хэлээр векторууд (нэг хэмжээст массивт ) зэрэг зарим өгөгдлийн бүтэц, дэмжлэг Pascal болон олон- хэмжээст массивт .  Ихэнх програмчлалын хэл өгөгдлийн бүтцийн шийдлүүд янз бүрийн хөтөлбөрт дахин ашиглах боломжийг олгодог номын сангийн механизмыг зарим төрлийн онцлог. Орчин үеийн хэл нь ихэвчлэн хамгийн түгээмэл өгөгдлийн бүтцийг хэрэгжүүлэх нь стандарт сангуудын хамт ирдэг. Жишээ нь C + + Стандарт Загвар Номын сан, Java цуглуулгууд хүрээ , болон Microsoft-ийн . NET Framework- байна.  Орчин үеийн хэлнүүд бас ерөнхийдөө модульчлагдсан нэвтрүүлэг нь номын сангийн модулийн интерфэйс , түүний хэрэгжилтийн хооронд ялгадаг дэмждэг. Зарим үйлчлүүлэгч хэрэгжүүлэх нарийвчилсан дарж нуу олгодог ил тод бус мэдээлэл төрлийг өгнө. Ийм C + + , Java болон Smalltalk зэрэг объект хандалтат програмчлалын хэл, энэ зорилгоор хичээлд ашиглаж болох юм. Олон гэгддэг өгөгдлийн бүтэц олон тооцоолох утас зэрэг мэдээлэл бүтэцрүү хандах боломж олгож байгаа юм.

Лекц-2  Стек

         Стек буюу Stack нь онцгой үүрэгтэй өгөгдлийн бүтцийн төрөл буюу цуглуулга юм. Стекийн үндсэн үйлдлүүд нь pop буюу элемент гаргах болон push буюу элемент нэмэх бөгөөд эдгээр үйлдлүүдийг стекийн орой гэх нэг төгсгөлд гүйцэтгэдэг. Стект хамгийн сүүлд орсон элемент хамгийн эхэнд гардаг учраас компьютерийн ухаанд стекийг LIFO (Last In First Out) бүтэц гэж бас нэрлэдэг. Push болон Pop аргын үндсэн шинж нь стекийн элемэнтүүдийн зүй тогтолтой байдгийг илэрхийлдэг. Стекээс элемент устгах нь нөгөө талаараа шинэ элемэнтэд орон зай бий болгож байгаа хэрэг юм. Ингэснээр хамгийн доор байгаа элемент нь хамгийн удаан оршин байх юм. Үндсэн үйлдлүүдээс гадна Peek буюу шагайх аргыг хэрэгжүүлсэн байдаг. Энэхүү арга нь хамгийн дээд талын элементийг устгалгүйгээр утгыг нь буцаадаг арга юм.

Стек нь багтаамж хязгаартай байх үед ашиглагддаг. Хэрэв стек нь дүүрэн ба дахиж элемент нэмэх зай байхгүй бол тухай стек нь overflow хэлбэрт шилжинэ. Pop арга нь стекийн хамгийн дээд талаас эхлэн элементүүдийг устгадаг ба устгасаар стекийн хамгийн доод талд ирэхэд өөр ямар нэгэн устгах элемэнтгүй болж стек нь underflow хэлбэрт шилжинэ.

Стек нь цөөхөн тооны арга ашигладаг хязгаарлагдмал өгөгдлийн бүтэц юм. Push болон Pop аргын үндсэн шинж нь стекийн элемэнтүүдийн зүй тогтолтой байдгийг илэрхийлдэг. Стекээс элемент устгах нь нөгөө талаараа шинэ элемэнтэд орон зай бий болгож байгаа хэрэг юм. Ингэснээр хамгийн доор байгаа элемент нь хамгийн удаан оршин байх юм.

Стек гэхийг бухал, овоолох, юмыг давхарлаж тавих гэж орчуулж болно. Стек гэдэг ойлголтыг анх 1946 онд Алан Тюринг нээжээ. Үүнээс 10 орчим жилийн дараа буюу 1955 онд Германы Клаус Самелсон болон Фридрих Бауэр нар стекийн тухай ойлголтыг мөн тусдаа нээж 1957 онд патент авчээ. Мөн л үүнтэй зэрэгцэн стекийг Австралийн Чарльз Леонард Хамблин 1957 оны эхний хагасд нээж байв.  Стек гэдэг нь компьютерийн шинжлэх ухааны нэгэн энгийн өгөгдлийн бүтэц бөгөөд үүнийг хийсвэр байдлаар илэрхийлэх боломжтой, эсвэл эсвэл шугаман жигсаалтын хэлбэрээр орой хэсгээсээ нэмж хасдаг байдалтайгаар тодорхойлж болно.

Стекийн шаардлага

Хэдийгээр стек нь маш хязгаарлагдмал үйлдэлтэй боловч компьютерийн програмчлалд чухал үүрэгтэй өгөгдлийн бүтцүүдийн нэг юм. Тухайлбал ямар нэг ажлын явцад өөр зүйл хийхээр түр хойшлуулах, эсвэл програм бүхэлдээ ийм зарчмаар ажиллах зэрэг олон алгоритмд стек үндсэн үүрэг гүйцэтгэнэ. Жишээ нь CALL, RETURN зэрэг функцэд стекийг ашигладаг байна.

Стекийг массив ашиглан нэвтрүүлэх

  Стекийг олон янзын аргаар нэвтрүүлж болох боловч ихэвчлэн шугаман массив, эсвэл нэг холбоост жагсаалт ашигладаг. Массив ашиглах стекийг ихэвчлэн гараар тодорхойлж өгдөг. Дараах Stack классын зарлалтаар MaxSize хэмжээтэй stack массив, стекийн оройг тодорхойлох top хувьсагч болон стекд элемент хийх push(), стекээс элемэнт авах pop() функц бусад туслах функцүүдийн хамт тодорхойллоо. Stack массивыг заагчаар тодорхойлсноор динамик ойгоос new операторын тусламжтайгаар MaxSize хэмжээтэй зайг Stack классын обьект зарлах үед нөөцлөн авна. Энэ нь хэдийгээр заагч ашиглаж байгаа боловч хувиарлалт хийснээс хойш түүний хэмжээ MaxSize-аас хэтрэхгүй тул статикаар тодорхойлогдож байна.

Стекийн хэрэглээ:

• Хаалтын баланс шалгах алгоритм Стек ашиглан энэ асуудлыг шийдвэрлэх нь хамгийн тохиромжтой. Тэмдэгтүүдийн цувааны эхнээс тэмдэг бүрийг уншин, нээх хаалт тааралдах бүрд түнийг стекд хийх ба хаах хаалт таарвал стекээс нэг элемент авч харгалзах нээх хаалт эсэхийг шалган, зөв тохиолдол цааш үргэлжлүүлэн шалгана. Өөрөөр хэлбэл нээх хаалтнууд стекд орсон дарааллын эсрэг дарааллаар харгалзан хаах хаалтууд байх ёстой.

• Арифметик илэрхийлэл Арифметикийн илэрхийлэл бодоход үйлдлийн тэмдэгүүдийн гүйцэтгэх дараарллыг баримтлах ёстой. Өөрөөр хэлбэл эхлээд хаалтан дахь үйлдлийг, дараа нь зэрэг дэвшүүлэх үйлдлийг, дараа нь үржих ба хуваах, эцэст нь нэмэх ба хасах гэсэн дарааллаар гүйцэтгэдэг. Жишээ нь: 3*(2+1)*2-8/(9-5)=2*9-8/4=16

Лекц № 3 Жагсаалт

Элемэнтүүд нь санах ойд дэс дараалан байрлах

 Жагсаалтын элемэнтүүд нь санах ойд динамикаар үүсдэг шугаман зохион байгуулалттай элемэнтүүдийн олонлогийг  жагсаалт гэнэ. Өөрөөр хэлбэл элемент бүр өгөгдлөөс гадна дараачийн элементийг заах заагчийг цуг агуулж байдаг. Харин массивын элементүүдийн зохион байгуулалт нь санах ойд дэс дарааллан байрлаж, элементүүдийг индексээр байрлалыг тодорхойлдог. Мөн массивын хэмжээг програмд хэрэглэхээс өмнө тодорхойлох ба дунд нь өөрчлөлт оруулж болохгүй. Энэ утгаараа массив статик өгөгдлийн бүтэц юм. Өөрөөр хэлбэл програм ажиллаж байх үед жагсаалтын хэмжээг өөрчлөх боломжтой. Жагсаалт нь ингэж динамикаар зохион байгуулагддаг учир элементүүдэд хийгдэх үйлдлүүд нь маш уян хатан, оновчтой гүйцэтгэгддэг. Динамикаар үүссэн элементүүдийн дарааллыг заагчаар тодорхойлдог. Жагсаалтыг холбоосоор нь дараах байдлаар ангилдаг:

Нэг холбоост жагсаалт /Singly Linked List/

  Цикл жагсаалт /Circular Linked List

 Давхар буюу хоёр холбоост жагсаалт /Doubly Linked List/

  Нэг холбоост жагсаалт зангилаа нь өгөгдөл ба холбоос/заагч/ гэсэн хоёр хэсгээс тогтоно.

 Тухайн элементийн заагч нь дараагийн элементийн хаягийг агуулна. Тэмдэгтүүдийг хадгалах 5 элемент бүхий нэг холбоост жагсаалтыг дүрсэлбэл:

Жагсаалтын элементийн өгөгдөл нь бүхэл тоо, бодит тоо, тэмдэгт мөр гэх мэт үндсэн өгөгдлийн төрлүүдээс гадна хэрэглэгчийн тодорхойлсон өгөгдлийн төрөл ч байж болох юм. Бидний дээрх жишээний хувьд элемент бүр нь нэг тэмдэгт агуулж байна. Харин элементийн холбоос буюу заагч нь дараачийн элементийн хаягийг агуулах ба энэ нь зурагт сумаар дүрслэгдсэн байна. Хамгийн сүүлчийн элементийн заагч нь NULL гэсэн утгыг агуулж байх ёстой. Жагсаалтын элементийн өгөгдөл нь бүхэл тоо, бодит тоо, тэмдэгт мөр гэх мэт үндсэн өгөгдлийн төрлүүдээс гадна хэрэглэгчийн тодорхойлсон өгөгдлийн төрөл ч байж болох юм. Бидний дээрх жишээний хувьд элемент бүр нь нэг тэмдэгт агуулж байна.

Нэг холбоост жагсаалтад хийгдэх үйлдлүүд

Жагсаалтад элемент нэмэх

 Энд жагсаалтын дурын байрлалд шинэ элемент оруулах тухай судлана. Нэг холбоост жагсаалтад шинэ элементийг жагсаалтын ямар нэг элементийн аргаар оруулах нь илүү хялбар юм. Үүнийг жагсаалтын дурын элементэд шууд хэрэглэх боломжгүй, тодруулбал тухайн элементээс түүний өмнөх элементэд шууд хэрэглэх боломжгүйтэй холбоотой.  Хэрэв шинэ элементийг ямагт жагсаалтын төгсгөлд оруулах шаардлагатай бол элемент оруулах бүрт curr заагчийг жагсаалтын төгсгөлд байрлуулах ёстой. Жишээлбэл: A, B, C, D, E, F, H, G, I, J гэсэн тэмдэгтүүдийг жагсаалтын төгсгөлд оруулах кодын хэсгийг дараах байдлаар бичиж болно.

Жагсаалтаас элемент хасах

 Нэг холбоост жагсаалтаас устгах үед түрүүчийн (элемент оруулах) адил асуудал гарах болно. Элементийг жагсаалтаас устгах үед устгах элементийн өмнөх элементийн заагч нь устгах элементийн дараачийн элементийг заах ёстой. Тухайлбал Х элемент бүхий жагсаалтын элементийг устгахын тулд I элементийг заагч S элементийг заах болно. Иймд curr заагч нь устгах элементийг бус түүний өмнөх элементийг зааж байх ёстой. Өөрөөр хэлбэл curr заагчийн заах элементийн дараагийн элементийг устгана

Хоёр холбоост жагсаалт

 Нэг холбоост жагсаалтыг хялбарчлах үүднээс элемэнт бүрд дараагийн элемэнтийг заах заагчаас гадна, өмнөх з элементээ заах заагчийг нэмж өгч болно. Ийм жагсаалтыг хоёр холбоост жагсаалт гэнэ. Хоёр холбоост жагсаалт нь хэдийгээр жагсаалтын дурын элемэнтэд шууд хандах боломжгүй ч хоёр чиглэлд явах боломжтой болсноор элемэнт оруулах . Устгах үед илүү уян хатан юм. Хоёр холбоост жагсаалт дээр хийгдэх үйлдэл нь нэг холбоост жагсаалт дээр хийгдэх үйлдэлтэй төсөөтэй.I зангилааны өмнөх занилааны next  заагч нь I зангилааг алгасаад S зангилааг заана

1.      I зангилааны дараагийн S зангилааны prev заагч нь I зангилааг алгасч L зангилааг заана.

2.      Шинэ элементийг 2 холбоост жагсаалтын тухайн зангилааны өмнө эсвэл хойно оруулах нь зарчмын хувьд адил үйлдэл хийгдэнэ.

Шинэ элеменийг 2 холбоост жагсаалтын тухайн зангилааны өмнө эсвэл хойно оруулах нь нэг холбоост жагсаалттай адилхан. Шинэ элемент оруулахдаа шинэ зангилаа new_node ашиглана

Жагсаалыг массиваар илэрхийлэх

Жагсаалтыг массиваар илэрхийлэх үед холбоосын оронд массивын индексыг ашиглана. Жагсаалтыг илэрхийлэх массив нь өгөгдөл ба холбоос (индекс) талбаруудаас тогтох бичлэгүүдийг агуулж болно.