Dinamikalıq maǵlıwmatlar strukturası. Sızıqlı dizimler

Dinamikalıq maǵlıwmatlar strukturası.Sızıqlı dizimler.

REJE:
1. Dinamikalıq maǵlıwmatlar dúzilisi.

2. Sızıqlı bir ólshemli dizimler hám olar ústinde ámel orınlaw
algotirmleri.

Gilit sózler: list, linked list, sızıqlı dizimler, bir hám eki ólshemli dizimler.
1. Dinamikalıq maǵlıwmatlar strukturası
Bizge belgili, massivler (statikalıq strukturalar) programmalastırıw tillerinde júdá paydalı hám zárúr strukturalar. Biraq, onıń eki kemshiligi bar:
- Onıń ólshemin programma orınlanıwı dawamında ózgertip bolmaydı;
- Struktura arasına element kiritiw ushın qalǵanların jılıstırıw kerek.
Bul kemshilik baylanısqan strukturalar menen islewge alıp keledi. Baylanısqan strukturalar birdey tiptegi elementler (túyinler) izbe-izligi bolıp,olar yadta túrli orınlarǵa jaylastırıladı hám oz-ara bir-biri menen kórsetkishli maydanlar arqalı baylanısadı.Baylanısqan strukturalardı programmada túrlishe ámelge asırıw múmkin.
Baylanısqan strukturalarda elementlerdi tómendegishe payda etip alamız:

Informatiyalıq maydanda paydalanıwshınıń paydalı maǵlıwmatı jazıladı. Kórsetkishli maydanǵa keyingi elementtiń yadındaǵı adresi jazıladı. Sonday elementlerden quram tapqan strukturaǵa sızıqlı bir ólshemli dizim delinedi.
Baylanısqan dizimlerde massivtiń kemshilikleri joq qılınǵanlıǵı sebepli struktura uzunlıǵı hám elementler arasındaǵı qatnaslar programma orınlanıwı dawamında ózgerip turadı. Bul dinamikalıq struktura qásiyeti esaplanadı. Dinamikalıq struktura dep:
- elementleri arasındaǵı qatnaslar
- struktura uzunlıǵı (elementler sanı)
programma orınlanıwı dawamında ózgerıp turatuǵın dúziliske aytıladı. Dinamikalıq strukturalarda elementler yadta qálegen jerde jaylasıwı múmkin. Usı sebepli olar arasındaǵı qatnaslar kórsetkishler arqalı belgilenedi. Elementler strukturaǵa kelip qosılǵan waqıtta yadtan bos orın qıdırıp tabıladı hám elementler jaylastırıladı.Sol sebepli elementler yadında izbe-iz yacheykalarda jaylaspaǵan bolıwı múmkin. Eger fizikalıq yad jetispewshiligi sezilmese, struktura uzınlıǵı arttırılıwı múmkin.
Bunday strukturalar menen islewdiń ózine jarasa abzallıqları hám kemshilikleri bar. Abzallıǵı sonda, struktura uzınlıǵına aldınan shegara qoyılmaydı.Oǵan element kiritiw hám óshiriw ámelleri massivke qaraǵanda ańsat keshedi. Sebebi elementler yadqa qálegen jerge jaylastırıp atırǵan waqıtta aldın kelıp túsken elementler ornınan qozǵatılmaydı.Tek olardıń kórsetkishleri durıslap qoyıladı.
Kemshiligi sonnan ibarat, aldınan bar bolǵan strukturanı massivlerde bar bolǵan tártiplestiriw algoritmleri menen tártiplestirip bolmaydı, sebebi olar elementlerdiń indeksleri menen baylanıslı túsinik bolıp esaplanadı. Elementlerdiń indeksi degen túsinik joqlıǵı sebepli elementlerge tuwrıdan tuwrı múrájattıń ilaji joq, eń awır jaǵdayda aqırǵı elementke N múrájat arqalı jetip barıladı.
Izlew ámeli de tap sonday. Yaǵnıy eń awır jaǵdayda aqırǵı elementti N salıstırıwda tabıw múmkin.
Baylanısqan dizimler eń kóp tarqalǵan dinamikalıq strukturalardan esaplanadı. Maǵlıwmatlardı logikalıq sáwlelendiriw kóz- qarasınan dizimler ekige bólinedi: sızıqlı hám sızıqlı emes.
Sızıqlı dizimlerde elementler arasındaǵı baylanıs qatań tártiplengen boladı, yaǵnıy element kórsetkishi ózinen aldınǵı yáki keyingi element mánzilin saqlaydı. Sızıqlı dizimlerge bir yáki eki ólshemli dizimler kiredi. Ulıwma alǵanda, dizim elementleri bir yáki bir neshe kórsetkishli maydanlarǵa iye bolıwı múmkin hám hár bir kórsetkishi arqalı qálegen elementke múrájat qılsa, bunday dizimler sızıqlı emes dizimler delinedi.

2.Sızıqlı bir baylanıslı dizimler hám olar ústinde ámel orınlaw algoritmleri

Strukturada elementler ózinen keyingi element penen baylanısqan bolsa, bunday dizimge bir baylanıslı dizim delinedi. Eger hár bir element ózinen aldınǵı hám keyingi element penen baylanısqan bolsa, onda bunday dizimlerge eki baylanıslı dizimler delinedi. Eger aqırǵı element birinshi element kórsetkishi menen baylanısqan bolsa, bunday dizimge saqıyna tárizli dizim delinedi. Dizimniń hár bir elementi sol elementti identifikatsiyalaw ushın giltke iye boladı. Gilt ádette pútin san yáki qatar kórinisinde maǵlıwmatlar maydanınıń bir bólegi sıpatında bar boladı. Dizimler ústinde tómendegi ámeller orınlaw múmkin.
T- dizimdi payda etiw (bireinshi elementti jaratıw);
- dizim aqırına jańa element qosıw;
- berilgen giltke mas elementti oqıw;
- dizimniń kórsetilgen jerine element qosıw(berilgen giltke mas elementten aldın yáki keyin;
-berilgen giltke mas elementti óshiriw;
-gilt boyınsha dizim elementlerin tártiplestiriw.
Dizimler menen islewde programmada baslanǵısh elementti kórsetiwshi
kórsetkish talap etiledi. Sıziqlı bir baylanıslı dizimler ústinde túrli ámeller orınlaw algoritmleri hám programmaların kórip shıǵamız.

Bunday kórinistegi dizim elementi kórsetkishiniń ózine tánligi sonnan ibarat, ol tek ǵana dizimniń keyingi (ózinen keyin keliwshi) elementi adressin kórsetedi. Bir tárepleme baǵıtlanǵan dizimde eń sońǵı element kórsetkishi bos, yaǵnıy NULL boladı.
Lst- dizim bası kórsetkishi. Ol dizimdi jalǵız bir pútin sıpatında ańlatadı. Geyde dizim bos bolıwı da múmkin. Onda Ist=NULL boladı. Házir sızıqlı bir baylanıslı dizim payda etiw programmasın kórip shıǵamız. Bunıń ushın biz paydalanıwshı tárepinen jaratılatuǵın standart emes tip jaratıp alıwımız kerek.
Bunıń bir qansha usılları bar, yaǵnıy klasslar yáki strukturalar menen ámelge asırıw múmkin. Mısalı,
class Node{
public://klass maǵlıwmatlarına sırttan
bolatuǵın múrájátqa ruxsat beriw
int info; // informatsiyalıq maydan
Node* next;// kórsetkishli maydan
};
Bul jerde biz Node atlı tip jarattıq hám dizim pútin sanlardan ibarat.
Endi dizim elementlerin sol tip arqalı daǵazalasaq boladı, yaǵnıy


Node *lst = NULL;// dizim bası kórsetkishi
Node *last = NULL;// dizimge aqırǵı kelip tusken elementtiń kórsetkishi
Endi sol belgilewler arqalı dizim payda etemiz.

Node * p = new Node;

int numb = -1;
cout<<"son kiriting: ";
cin>>numb;
p->info = numb;
p->next = NULL;
if (lst == NULL) {
lst = p;
last = p;
}
else{ last->next = p;
last = p; }
Bul programmada jańa element dizim aqırınan kelip qosıladı.