4

Дараалал, түүнийг массив ашиглан зохион байгуулах

Лекц № 4            Дараалал, түүнийг массивашиглан зохион байгуулах

 

—   Дараалал нь стекийн адил хязгаарлагдмал үйлдэлтэй өгөгдлийн бүтэц юм. Элемэнт оруулах буюу шинээр элемэнт нэмэх үйлдэл нь төгсгөлдөө хийгддэг, элемэнт гаргах буюу устгах үйлдэл нь эхэндээ хийгддэг өгөгдлийн бүтэцийг дараалал гэнэ.

—   Дараалалыг FIFO /First-In-First-Out/ төрлийн жагсаалт ч гэж нэрлэлдэг. Өөрөөр хэлбэл эхэлж орсон нь эхэлж гарна гэсэн үг.

—  Дарааллын компьютер дэхь жишээнээс дурьдвал  Үйлдлийн систем процессууд буюу санах ойд ачаалагдсан програмуудыг хугацааны хуваарилалтаар зохиоцуулан ажиллуулах

—   Принтерт хэвлэх файлуудын цуваа

Дарааллыг нэвтрүүлэх

—  Дарааллын үндсэн үйлдлүүд болох

—  Элемэнт нэмэх буюу оруулах үйлдэл нь дарааллын төгсгөлд хийгдэх тул төгсгөлийг тодорхойлох rear гэсэн хувьсагч.

—  Элемэнт устгах буюу гаргах үйлдэл нь дарааллын эхэнд хийгдэх тул эхлэлийг тодорхойлох front гэсэн хувьсагчийг ашиглана.

Дарааллын амьдрал дээр тохиолдох олон жишээ байдаг.

Жишээлбэл, банкны кассан дах хүмүүсийн дараалал, замын уулзвар дахь машинны дараалал гэх мэтчилэн эхэлж ирсэн эхэлж үйлчлүүлэх олон жишээ дурьдаж болно. Аливаа бодит амьдарлын асуудлыг шийдсэн шийдлээс компьтерийн программчлалын олон асуудлуудад санаа авч нэвтрүүлдэг.

—  Дараалал нь компьютерийн программчлалд маш чухал үүрэг гүйцэтгэнэ. Жишээлбэл,үйлдлийн систем процессуудыг(санах ойд ачаалагдсан программуудыг) хугацааны хуваарилалтаар зохицуулан ажиллуулах,мөн принтерт хэвлэгдэх ажлуудын цуваа зэрэгт дараалал зүй ёсоор ашиглагдана.

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

Дарааллын ажиллах зарчим

—  Дарааллыг массив ашиглан нэвтрүүлэх үед дараалал дүүрэн эсвэл хоосон эсэхийг шалгахдаа бүрт back ба front хувьсагчуудын ашиглана. Нөгөө талаас, дарааллаас элемент гаргах бүрт front заагч нэг байрлалаар мөн цагийн зүүний дагуу шилжин, back заагчтай ижил элементэд заах үед дараалал ганц элемент байх болно.Сүүлчийн элементийг дарааллаас гаргаснаар front заагч нэг шилжин дараалал хоосон болно. Сүүлчийн элементийг дарааллаас гаргаснаар front заагч нэг шилжин дараалал хоосон болно.

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

Дарааллын өгөгдөл

Дарааллын өгөгдөл / *items /

Дарааллын хэмжээ

/ MaxQue /

Дарааллын эхлэл

 / front /

Дарааллын төгсгөл

/ rear /

Дарааллын үйлдэл

Дараалалд элемэнт нэмэх /Enqueue/ үйлдэл

Дарааллаас элемэнт устгах /Dequeue/

Дарааллын элемэнтүүдийг харах /Viewqueue/

Дараалал дүүрсэн эсэхийг шалгах /Fullqueue/

Дараалал хоосон эсэхийг шалгах /Emptyqueue/

Дарааллыг массив ашиглан нэвтрүүлэх

—  Дарааллыг массив ашиглан нэвтрүүлэх үед массивын хэмжээгээр дараалалд хадгалагдах элемэнтийн тоо хязгаарлагдана. Тиймээс  Дараалалд элемэнт нэмэх бүртээ дараалал дүүрсэн эсэхийг шалгах хэрэгтэй болно.  Дарааллаас элемэнт устгах бүртээ дараалал элемэнттэй эсэхийг шалгана. Дараалалд элемэнт нэмэх болон устгахад rear болон front хувьсагчдийн утга харгалзан нэг нэгээр нэмэгдэнэ

Дарааллыг массив ашиглан нэвтрүүлэх

Дарааллыг массив ашиглан нэвтрүүлэх

Дарааллыг массив ашиглан нэвтрүүлэх

—  Энэ байдлыг шийдэхийн тулд дарааллын эхний элемэнтийг хоосоноор тодорхойлно. Ингэснээр §front==rear үед дараалал хоосон байх нөхцөл биелэнэ.  (rear + 1) % maxQue == front үед дараалал дүүрэн байх нөхцөл биелэнэ.

Дарааллыг классаар тодорхойлох

—  class Queue{ int maxQue, front, rear;

—  ItemType* queItems;

—  public:

—  Queue(int max);

—  ~Queue();

—  void MakeEmpty();

—  bool Emptyqueue();

—  bool Fullqueue() ;

—  void Enqueue(ItemType newItem);

—  void Dequeue(ItemType& item);

—   void Viewqueue();};

Дарааллыг үүсгэх байгуулагч функц:

—  Queue::Queue(int max)

—  {

—   maxQue = max + 1; front = maxQue – 1;

—  rear = maxQue – 1; queItems = new ItemType[maxQue];

—   }

—  Тайлбар: Queue Q(10); 10 хэмжээтэй Q гэсэн нэртэй дарааллыг үүсгэж байна

Дараах queue классын зарлалтаар массив ашиглан дарааллыг хэрхэн үүсгэхийг харцгаая.

—  template <class Type>

—  class Queue  (

—      Type * queue ;

—      Int front , back , MaxSize ;

—  Public:

—      Quenue (int MSize) : MaxSize (MSize) (

—              queue  = new Type  (MaxSize) ;

—              front = back = 0

—  )

—  ~Queue ( ) (

—     delete [ ] queue ;

—  )

—  bool insert (Type item) ;

—  bool remove (Type item) ;

—  bool empty ( ) ;

—  bool full ( ) ;

—  ) ;

—  Queue байгуулагч функцээр Maxsize бүхий массив үүсгэж байна.Дараалал дүүрэх үед нөхцөл ёсоор массив нэг хоосон элемент агуулах ба дараалал нь хамгийн ихдээ Maxsize-1 элемент агуулж чадна.

—  Дээрх queue классыг программд дараах байдлаар ашиглаж болно.

—  Void main () {

—  Queue<char> q(6) ;

—  Char s [ ] = “Queues ; “ , ch ;

—  int i=0 ;

—  while ( * ( s+i ) && q. insert (*(s+i) ) )

—  cout << “queue <- “ << * (s+i++) << endI ;

—  }

—  / *

—  while (* (s+i) && !q. full ( ) )  {

—  q. insert ( * (s+i ) ) ;

—  cout << “queue <- “ << * (s+i++) << endI ;

—  }

—  Дээрх программын кодод 6 тэмдэгт агуулах дарааллыг үүсгэсэн байна.Гэвч дарааллыг массиваар илэрхийлэх үед дүүрэн дараалал нь нэг хоосон элемент ашуулах учир энэ программын дараалал хаигийн ихдээ 5 элемент агуулах болно.Дээрх программыг ажилуулахдаа ‘Q’, ‘u’, ‘e’, ‘u’, ‘e’, ‘s’ гэсэн тэмдэгтүүдыг эхний 5 тэмдэгт оруулсны дараа дараалал дүүрэн гэсэн мэдээллийг авах болно. Дараалалд элемент оруулах хэсгийн кодыг программ дахь / * */ хаалтад байгаа хэсгээр солисноор дараалал дүүрэн гэсэн мэдээлэл гарахаас зайлсхийж болно.Өөрөөр хэлбэл дараалал дүүрэн үед insert ( ) функцээр элемент оруулахыг оролдохын өмнө full ( ) функцээр дарааллын төлөвийг урьдчилан шалгах юм.

Дарааллын нэг холбоост жагсаалтаар илэрхийлэх

—  Нэг холбоост жагсаалт нь дарааллыг нэвтрүүлэх хамгийн зохимжтой арга юм.Нэг холбоост жагсаалтын эхний болон төгсгөлийн элементийн заах хоёр заагчийн тусламжтайгаар дараалалд хийх бүх үйлдлүүдийг гүйцэтгэж болно.Дарааллын ажиллах зарчим ёсоор жагсаалтын төгсгөлийн хоёр элементээс бусад элемэнтэд хандах шаардлагагүй байдаг.

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

—  Нэг холбоост жагсаалтын онцлогоос хамаарч элементийг жагсаалтын төгсгөлд оруулж, жагсаалтын эхлэлээс элемент гаргах хэрэгтэй байдгийг анхаарах нь зүйтэй.

Дарааллын нэг холбоост жагсаалтаар илэрхийлэх

—  Дараах queue классын зарлалтаар дарааллыг тодорхойлъё.

—  template <class Type>

—  class Queue (

—  struct Node  (

—  Type data ; Node *link ;

—  Node  (Type d)  : data (d) , link (NULL)  { }

—  ) ;

—  Node *front , *back ;

—  Public :

—  Queue ( )  {

—  Front = back = NULL ;

—  )

—  ~Queue ( )  ;

—  bool insert (Type item) ;

—  bool remove (Type item) ;

—  bool empty ( ) ;

—  ) ;

—  front  болон back заагчууд NULL утгатай байхад дараалал хоосон байна.

Дарааллын онцгой тохиолдлууд

—  Дараалалд хийх үйлдлүүд болон зохион байгуулалтын хэлбэрээс хамааран дарааллын үндэс шинж чанараас гажих тохиолдлууд байдаг. Энд бид дарааллын онцгой хэлбэрүүд болон давхар төгсгөлт дараалал ба эрэмбэт (зэрэглэлт) дарааллыг авч үзэх болно. Давхар төгсгөлт дараалал Элементийг оруулах ба гаргах үйлдлийг аль ч төгсгөлд нь гүйцэт гэж болох дарааллыг давхар төгсгөлт дараалал (deque – double ended queue ) гэнэ. Давхар төгсгөлт дараалалд нь эсрэг чиглэлтэй хоёр дарааллын, нөгөө талаас хоёр стекийн нэгдэл мэт юм. Өөрөөр хэлбэл давхар төгсгөлт дарааллын тухайн нэг төгсгөлд орсон элемент тэр төгсгөлөөр гарвал энэ нь стекийн зарчмаар, хэрэв нөгөө төгсгөлөөр гарвал дарааллын зарчмаар ажиллах болно.

Дарааллын онцгой тохиолдлууд

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