DYNAMIC DATA STRUCTURE(Динамические структуры данных)

Dynamic data structure(Динамические структуры данных)

ပရိုဂမ္မ်ားအား execution ၿပဳလုပ္ခ်ိန္တြင္ dynamic data မ်ားအား create ၿပဳလုပ္နိဳင္ၿပီး ထို႕အတူ resize လည္းၿပဳလုပ္နိဳင္သည္။
dynamic structure မ်ားတြင္ ေအာက္ေဖာ္ၿပပါမ်ားသည္ အသံုးၿပဳမွဳ႕အမ်ားဆံုးၿဖစ္သည္။
queue(очередь)
stacks(стеки)
double-linked lists(двунаправленный список)
binary tree(бинарное дерево)

သာမန္ structure မ်ားကဲ့သို႕ပင္ dynamic structure မ်ားသည္လည္း fields မ်ား member of structure မ်ားျဖင့္ဖြဲ႕စည္းထားၿခင္းၿဖစ္သည္။သို႕ေသာ္ ထို႕ထက္ပို၍ ၎ fields ၏ information မ်ားတြင္ ကိုယ္ပိုင္ structure type ရွိေသာ pointer-fields မ်ားပါ၀င္ရန္လိုအပ္ေပသည္။

Dynamic structure အားေအာက္ပါအတိုင္း ေၾကၿငာနိဳင္သည္။

struct node {  int info;     / / This can be any information field, and their

                                    / / can be more than one

struct node * next;    / / pointer to a structure of type node

}

Declare ၿပဳလုပ္လိုက္ေသာ structure type တြင္ integer type အသံုးၿပဳထားေသာ information field နွင့္ ထုိ structure type ၏ pointer ပါ၀င္ရန္လိုအပ္ေပသည္။ ၎တို႕၏ အကူအညီၿဖင့္ structure သည္ list မ်ားအား ေပါင္းစပ္လိမ့္မည္ၿဖစ္သည္။list မ်ားသည္ အမ်ိဳးမ်ိဳးေသာ data မ်ား stroe ၿပဳလုပ္ရာတြင္ အလြန္အဆင္ေၿပလြယ္ကူေစသည္ၿဖစ္သည္။

Structure ေပၚတြင္ point ၿပဳလုပ္ေသာ pointer အား node(узел) ဟုေခၚဆိုေလ့ရွိၾကသည္။

Formation of the queue(Формирование очереди)

List(список) တစ္ခုအား ဖန္တီးရန္အတြက္ node structure ကဲ့သို႕ေသာ structure တစ္ခု declare ၿပဳလုပ္ရန္ လိုအပ္ေပသည္။

struct node { int info;

                   struct node * next;

                   };

Declare ၿပဳလုပ္ထားေသာ structure ဆီသို႕ pointer အသံုးၿပဳရမည္ၿဖစ္သည္။

typedef node *NodePtr;      //pointer to node

ထိုကဲ့သို႕ ၿပဳလုပ္ၿပီးလွ်င္ list ၏ ပထမဆံုး ဆီသို႕ pointer တစ္ခု declare ၿပဳလုပ္ရမည္ၿဖစ္သည္။ ထိုကဲ့သို႕ေသာ အရာအား list တြင္ list ၏ heading(заголовок) ဟုရည္ညြန္းေလ့ရွိသည္။ကၽြန္ေတာ္တို႕သည္ ၎အား head ဟုေခၚဆိုေလ့ရွိၿပီး ေအာက္ပါအတိုင္း declare ၿပဳလုပ္ရမည္ၿဖစ္သည္။

NodePtr head =NULL;

List ၏ အစအား Null-pointer ဟုအသံုးၿပဳရၿခင္းသည္ list ၏အစသည္ empty ၿဖစ္ေနသည္ဟုသိသာေစရန္ၿဖစ္သည္။list အား formation စတင္ၿပဳလုပ္ရန္အတြက္ list တြင္ ပထမဆံုး element အားစတင္ထည့္သြင္းရမည္ၿဖစ္ၿပီး ထိုထည့္သြင္းရမည့္ element အတြက္ memory ေနရာသည္ empty  ၿဖစ္ရမည္ၿဖစ္သည္။ထုိသို႕ စစ္ေဆးအသံုးၿပဳရန္အတြက္ ေအာက္ေဖာ္ၿပပါအတိုင္း operator ၿဖင့္အသံုးၿပဳနိဳင္သည္။

if( head == NULL )

{        head = new node;

          head->          info = 1;

          head->next = NULL;

}

Operator p->info = 1 ; သည္ operator (*p).info=1; နွင့္အတူတူပင္ၿဖစ္သည္။အထက္ေဖာ္ၿပပါ ပရိုဂမ္အတြင္းမွ ပထမအေၾကာင္း head = new node သည္ head မွာ node တစ္ခုထပ္မံတည္ေဆာက္လိုက္ၿပီး ထို node ၏ structure အတိုင္း combine ၿပဳလုပ္သြားမည္ၿဖစ္သည္။ ဒုတိယ statement သည္ head ထဲမွ info အား 1 နွင့္တိုက္ရိုက္တူညီေပးၿခင္းၿဖစ္သည္။

ထိုကဲ့သို႕ေသာ element တစ္ခုတည္းပါ၀င္ေသာ list အား ေအာက္ပါအတိုင္း သရုပ္ၿပေဖာ္ၿပနိဳင္သည္။

list of one element 

သို႕ေသာ္ list မ်ားအား element တစ္ခုတည္းၿဖင့္တည္ေဆာက္ၿခင္းသည္ တစ္ခါတစ္ရံမွသာအသံုးၿပဳေလ့ရွိသည္။ ထို႕ေၾကာင့္ ေနာက္ထပ္ ထပ္မံ၍ list အတြင္းသို႕ element မ်ား ထပ္မံေပါင္းစပ္ရန္လိုအပ္ေပသည္။ထိုသို႕ ၿပဳလုပ္ရန္အတြက္ လက္ရွိ p element အား pointer ထပ္မံေၾကၿငာရန္ မၿဖစ္မေနလိုအပ္ၿပီး ေနာက္ထပ္ လုပ္ေဆာင္ခ်က္မ်ားအား ထပ္မံေပါင္းထည့္ရမည္ၿဖစ္သည္။

NodePtr p;     //pointer to current element

NodePtr tail;   //pointer to the “tail” of the queue

if(head == NULL )

{ head=new node;

head->info =1;        //or some value

head->next =NULL;

}

p=new node;

p->info =2;

p->next = head->next;       //In this case NULL

head->next=p;

tail = p;

ထိုကဲ့သို႕ element အား insert ၿပဳလုပ္ၿပီးလွ်င္ list အား ေအာက္ေဖာ္ၿပပါအတိုင္းေဖာ္ၿပနိဳင္သည္။

list of two element 

 ထိုနည္းအတိုင္းပင္ element မ်ားထပ္မံၿဖည့္စြပ္ၿပီးလွ်င္ List သည္ ေအာက္ေဖာ္ၿပပါ အတိုင္း ၿဖစ္လိမ့္မည္ၿဖစ္သည္။ အကယ္၍ queue(list) အတြင္းရွိ element အေရအတြက္ကို သိရွိပါက ၎အား for loop ၏ parameter အၿဖစ္အသံုးၿပဳနိဳင္သည္။

NodePtr p;     //pointer to current element

NodePtr tail;   //pointer to the “tail” of the queue

int N=10;       //number of element in queue

int cnt=1;      //count of item in the queue

head=NULL;

…………

if(head ==NULL)

{head = new node;

head->info = cnt++; //or some value

head->next = NULL;

tail = head;

}

for(int i=2;i<=N; i++)

{ p=new node;

p->info = cnt++;

tail->next = p;         //in this case – NULL

p->next = NULL;

tail = p;

}

list of several element(item) 

ကၽြန္ေတာ္တို႕သည္ queue(list) အား ဖန္တီးတည္ေဆာက္ခဲ့ၿခင္းၿဖစ္သည္။ (queue ,FIFO , First Input First Output).။ ထို႕ေၾကာင့္ ့header element(head) သည္ အၿမဲတမ္း list ၏ ပထမ element ဆီကိုသာ point ၿဖစ္ရမည္ၿဖစ္သည္။

Example . Program forming a queue of 10 items and display it on screen.

#include "stdafx.h"

#include <iostream>

#include <conio.h>

using namespace std;

struct node {

              int info;

              struct node *next;

                     };

int _tmain(int argc, _TCHAR* argv[])

{   typedef node *nodeptr;

       nodeptr head=NULL;

       nodeptr p,tail;

       int N=10;

       int count=1;

       if (head == NULL){

       head = new node;

    head-> info = count++;           // Or some other value

    head-> next = NULL;

    tail = head;

       }

       for (int i = 2; i <= N; i++){

              p = new node;

              p-> info = count++;

        tail-> next = p;      // in this case - NULL

        p-> next = NULL;

        tail = p;

       }

       p = head;

       for (int i = 1; i <= N; i++){

              cout << p->info <<" ";

              p = p->next;

       }

       cout << endl;

       _getch();

       return 0;

}

The formatting of the stack (Форматирование стека)

Stack ဆုိသည္မွာ “last-in first-out” (LIFO ,List Input – First Output) နည္းၿဖင့္ ဖြဲ႕စည္းထားေသာ data structure ၿဖစ္သည္။stack ၏ပံုစံသည္ အပ္ခ်ည္ၿဖင့္သီထားေသာ ပုတီးပံုစံနွင့္တူညီသည္။ပုတီးသီးမ်ား အားလံုးအား ယူရန္အတြက္ ေနာက္ဆံုးမွေန၍ အလံုးမွေန၍ အလြယ္အကူ တစ္ခုခ်င္းဆီၿဖဳတ္ယူနိဳင္သည္။ queue ကဲ့သို႕ပင္ stack သည္လည္း reference(link) structure ကိုအေၿခခံ၍ organize ၿပဳလုပ္ထားၿခင္းၿဖစ္သည္။ ထို႕ေၾကာင့္ stack အား formation ၿပဳလုပ္ရန္အတြက္ queue အား formation ၿပဳလုပ္သကဲ့သို႔ ပင္ declare ၿပဳလုပ္ရမည္ၿဖစ္သည္။

struct node{ int info;

                 struct node *next;

               };

typedef node *NodePtr;      //pointer to Node type

stack ၏ ပထမအား ပံုတြင္ၿပထားသည့္အတိုင္းၿဖစ္ၿပီး ၎၏ information field အား 1 နွင့္တူညီထားသည္ကို ေတြ႕ၿမင္နိဳင္သည္။ပံုတြင္ၿပထားသည့္အတိုင္းပင္ ေနာက္ထပ္ head element ၏ next pointer မ်ားသည္ အစဥ္အလိုက္တည္ရွိမည္ၿဖစ္သည္။သို႕ၿဖင့္ ေနာက္ဆံုးအလွည့္ၿဖစ္သြားေသာ 1 element ဆီသို႕ ေရာက္ေအာင္ တစ္ဆင့္ၿခင္းသြားမည္ၿဖစ္သည္။

stack

Stack အား formation ၿပဳလုပ္ရန္ ေအာက္ေဖာ္ၿပပါ operation အားၿဖင့္ မွန္ကန္စြာၿပဳလုပ္နိဳင္သည္။

NodePtr head = NULL;

if (head == NULL)

   { head = new node;

      head->info = random(100) - 50;

      head->next = NULL;

    }

else  { p = new node;

                 p->info = random(100) - 50;

                 p->next = head;

                 head = p;

       }

Stack အားတည္ေဆာက္ရန္ loop operator အေရအတြက္ ေရြးခ်ယ္ရာတြင္ stack တြင္ပါ၀င္ေသာ element အေရအတြက္သိရွိၿခင္းအားၿဖင့္ တည္ေဆာက္နိဳင္သကဲ့သို႕ ၎ formation ၿပီးဆံုးၿခင္း အမွတ္အသား ၿဖင့္လည္း အသံုးၿပဳနိဳင္သည္။

Example. Program forming a stack of 10 elements and display it on screen.

# include <iostream>

using namespace std;

void main ()

{struct node {int info;

struct node * next;

};

typedef node * NodePtr;                             / / Pointer on type of node

NodePtr head = NULL;

NodePtr p;                                             / / Pointer to the current item

int N = 10;                                           / / Number of elements in the queue

int cnt = 1;                                           / / Count of items in the queue

if (head == NULL)

{head = new node;

head-> info = cnt + +;                             / / Or random (100) - 50;

head-> next = NULL;

}

for (int i = 2; i <= N; i + +)

{ p = new node;

p-> info = cnt + +;               / / Or random (100) - 50;

p-> next = head;

                 head = p;

}

/ / Print the stack on the screen

  p = head;

for (int i = 1; i <= N; i + +)

{cout << p-> info << '';

p = p-> next;

    }

cout << endl;

}

Adding and deleting items in the linked list(Добавление и удаление элементов в связанном списке)

Queue တြင္ item မ်ားအား list မ်ားအားေပါင္းထည့္ၿခင္းသည္ ၎၏ ေနာက္ဆံုးမွ ေပါင္းထည့္ရၿခင္းၿဖစ္ၿပီး (အထက္တြင္ေဖာ္ၿပၿပီးၿဖစ္ၿပီး) stack တြင္ ေပါင္းထည့္လိုပါက ေရွ႕ဆံုးမွ ေပါင္းထည့္ရၿခင္းၿဖစ္သည္။သို႕ေသာ္ ထိုထက္ပို၍ list ၏ ၾကိဳက္နွစ္သက္ရာေနရာတြင္ လိုအပ္ေသာ element(item) မ်ားအား ထပ္မံေပါင္းထည့္နိဳင္သည္။ ထိုသို႕ၿပဳလုပ္ရာတြင္ list သည္ stack ၿဖစ္ေစ queue ၿဖစ္ေစ အေရးမၾကီးေပ မည္သည့္ list မဆို ၿပဳလုပ္ေဆာင္ရြက္နိဳင္သည္။

Element မ်ားအား ေပါင္းထည့္ၿခင္း(adding) နွင့္ ပယ္ဖ်က္ၿခင္း(deleting) ၿပဳလုပ္ၿခင္း လုပ္ေဆာင္ခ်က္မ်ားသည္ stack နွင့္ queue တို႕တြင္ သေဘာတရားအတူတူပင္ၿဖစ္သည္။

Item တစ္ခုအား list ၏အလယ္သို႕ ေပါင္းထည့္ရန္အတြက္  p element ၏ next အား ထပ္မံေပါင္းထည့္မည့္ v element ၏ ဆီသို႕ pointer အား redirect ၿပဳလုပ္ေပးရမည္ၿဖစ္ၿပီး ထို v element ၏ next ၿပီးသည့္ေနာက္ ေနာက္ထပ္လာမည့္ element ဆီသို႕ point ၿပဳလုပ္ေပးရမည္ ၿဖစ္သည္။

adding an item in the middle of the list

 NodePtr  v,p;

……………

v=new node;

v->info =3;

v->next = p->next;

p->next = v;

list ၏ အစဆီသို႕ element(item) ထပ္မံေပါင္းထည့္ၿခင္းသည္ လြယ္ကူရိုးရွင္းသည္။ ထိုသို႕ၿပဳလုပ္ရန္ head –pointer အား ထပ္မံေပါင္းထည့္မည့္ v element ဆီသို႔ redirect ၿပဳလုပ္ရမည္ၿဖစ္သည္။ထို႕ေနာက္ v->next သည္ ယခင္က်န္ရွိေနေသာ ပထမဆံုး element(head) ဆီသို႕ point ၿပဳလုပ္ရမည္ၿဖစ္သည္။

NodePtr v,p;

…………..

v=new node;

v->info=0;

v->next= head->next;

head=v;

adding an item to the top of the list

List မ်ားနွင့္ အလုပ္လုပ္ရာတြင္ element မ်ားအား ေပါင္းထည့္ၿခင္းသာမက ၎တို႕အား ပယ္ဖ်က္ရာတြင္လည္း pointer မ်ား redirection ၿပဳလုပ္ၿခင္းသည္ အဓိကက်သည္ၿဖစ္သည္။ထိုသို႕ ပယ္ဖ်က္မွလွ်င္ memory တြင္ free space ပိုမိုရရွိေစမွာၿဖစ္ၿပီး heap ဆီသို႕ ၿပန္လည္ return ၿပန္ေစမွာၿဖစ္သည္။list ၏ အစ element မ်ား အလယ္နွင့္ ေနာက္ဆံုးမွ element မ်ားအား delete ၿပဳလုပ္ၿခင္းတို႕အား ေအာက္ေဖာ္ၿပပါ ပံုမ်ားတြင္ အသီးသီး ေဖာ္ၿပထားပါသည္။

NodePtr d;     //pointer to the item to be removed

…………..

d=head;

head=head->next;

delete d;

Removing an item from the beginning

NodePtr d;     //pointer to the item to be removed

……………

p->next=d->next;

delete d;

Removing an item from the middle of the list

NodePtr d;     //pointer to the item to be removed

…………….

P->next=d->next;     //actually is p->next=NULL

delete d;

Removing an item from the end of the list

List မ်ားတြင္ element မ်ားအား adding ၿပဳလုပ္ၿခင္းနွင့္ removing ၿပဳလုပ္ၿခင္း၏ အဓိကမွာ ထိုသို႕ၿပဳလုပ္ရန္ လိုအပ္ေသာelement မ်ားအား ရွာေဖြၿခင္းပင္ၿဖစ္သည္။

Example. Search for an item in a linked list.

# include <iostream>

using namespace std;

# include <stdlib.h>

void main ()

{int N;                                                         / / Number of items in a list

int target;                                                         / / Search value

int count;                                                         / / Location of the element

struct node {  int dat;                                           / / Information field

struct node * link;               / / Pointer to the field-

};

typedef node * NodePtr;                             / / Pointer to Node

NodePtr head = NULL;

NodePtr here;                                           / / Pointer to the current item

randomize ();

cout << "Enter the number of items in the list";

cin >> N;

for (int i = 0; i <N; i + +)                             / / Form stack

{if (head == NULL)

{head = new node;

              if (head == NULL) {cout << "Not enough memory!" << endl;

                                                                      exit (1);}

              head-> dat = random (100) - 50;

              cout << head-> dat << '';

              head-> link = NULL;

}

              else {here = new node;

                            if (here == NULL)

                                          {Cout << "Not enough memory!" << Endl;

                                          exit (2);

                                          }

                            here-> dat = random (100) - 50;

                            cout << here-> dat << '';

                            here-> link = head;

                            head = here;

                            }

}

cout << endl;

cout << "What is the desired value?";

cin >> target;

here = head; count = 1;                             / / get up beginning List

if (here == NULL) cout << "List is empty! "<< endl;

else {while (here-> dat! = target && here-> link! = NULL)

{here = here-> link;

count + +;

            }

if (here-> dat == target)

     cout << "The item has №" << count << endl;

else cout << "Item not found!" << Endl;

       }

}

translated by zmk@miet51