Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Mühazirə 6

Xətti dinamik strukturlar. Siyahı strukturları

Dinamik strukturlarda elementlərin sayı dəyişkən olur. Elementlər arasındakı əlaqə xətti ardıcıl, xətti əlaqələndirilmiş və qeyri-xətti əlaqələndirilmiş olur.

Xətti əlaqələndirilmiş dinamik strukturlara aşağıdakılar aiddir:

1. 
   birəlaqəli siyahı strukturları;
   
2. 
   ikiəlaqəli siyahı strukturları;
   
3. 
   Sətr, mətn əlaqəli siyahı strukturları .
   

Üzərilərində daxil etmə və xaric etmə əməliyyatının aparılması mümkün olan, dəyişən rəqəmli elementdən təşkil olunan nizamlanmış çoxluq siyahı adlanır. Elementləri arasında qonşuluq munasibəti təsvir olunan siyahı xətti adlanır. Məntiqi siyahıya əvvəl ki, bölmədə nəzər saldıq. Ancaq orada söhbət verilənlərin yarımstatik strukturundan gedirdi və siyahının ölçüsünə məhdudiyyətlər qoyulurdu. Əgər siyahının uzunluğuna məhdudiyyət qoyulmursa onda o, yaddaşda əlaqəli struktur şəklində təsvir ediləcəkdir. Əlaqəli xətti siyahılar verilənlərin dinamik strukturunun ən sadə təsvir formasıdır.

Siyahılarda qrafiki əlaqələri oxların köməyi ilə təsvir etmək daha asandır. Əgər element heç bir başqa elementlə əlaqəli deyilsə, onda göstəricinin sahəsində heç bir elementi göstərməyən qiymət yazılır. Belə istinad xüsusi adla - nil adlanır.

Şəkil 5.1 – də birəlaqəli siyahının strukturu verilmişdir. INF hissəsi verilənlərin informasiya sahəsinin, NEXT növbəti elementin göstəricisidir. Hər bir siyahının xüsusi elementi olmalıdır hansı ki, siyahının başlanğıcının göstəricisi və ya digər elementlərdən adətən formatına görə fərqlənən siyahının başlanğıcı olur.Sonuncu elementinin göstərici sahəsində xüsusi nil göstəricisi var, hansı ki, siyahının sonunu bildirir.

Şəkil 3.1. Birəlaqəli siyahı strukturu

Ancaq birəlaqəli siyahının emalı heç də rahat deyil. Buna səbəb əks istiqamətdə hərəkətin mümkün olmamasıdır. Bu hal iki əlaqəli siyahıda mümkündür, burada hər bir elementin iki göstəricisi: siyahının öncəki və sonrakı elementini göstərir.İki əlaqəli siyahı struktur şəkil 5.2 – də verilib, harada ki, NEXT – göstəricisi növbəti elementi, PREV – göstəricisi öncəki elementi göstərir. Kənar elementlərdə uyğun göstəricilərdə NİL hissəsi olmalıdır, şəkildə göstərilən kimi.

Şəkil 3.2. İkiəlaqəli siyahının struktur

Siyahının emalını asanlaşdırmaq üçün siyahının sonuna sonu göstərən göstərici əlavə edilməlidir. Hər bir elementdə iki göstəricinin olması siyahının emalını çətinləşdirir və bununla yanaşı yaddaşın hərcmərcliyinə səbəb olur. Bununla yanaşı siyahı üzərində aparılan bəzi əməliyyatları daha effektiv edir. Baxılan xətti siyahıların daha çox istifadə edilən forması halqavari formadır hansı ki, həm bir əlaqəli, həm də iki əlaqəli siyahı formasında verilə bilər.Bu halda bir əlaqəli siyahıda sonuncu elementin göstəricisi birinci elementi göstərməlidir. İki əlaqəli siyahı formasında isə birinci və sonuncu elementin göstəricisi ünvanlanmanı şəkil 5.3 – də verilən kimi dəyişir.

Şəkil 3.3. Halqavari ikiəlaqəli siyahının strukturu.

Bu cür siyahılarla iş siyahılar üzərində bəzi əməliyyatları asanlaşdırır. Siyahının emalı zamanı bəzi təhlükəsizlik əməllərinə nəzarət etmək lazımdır ki, dövrənin uyğunluğu pozulmasın.

Yaddaşda siyahı özlüyündə deskriptorla birliyə, formata və ölçüyə görə eyni yazıları hansılar ki, yaddaşın bir hissəsində bir – biri ilə göstəricinin sayəsində xətti ardıcıllıq şəklində əlaqələnmişdir. Yazı informasiya sahəsi və siyahının qonşu elementinin göstəricisinin sahəsini özündə cəmləyir. İnformasiya bölməsinin bir çox sahələri yaddaş blokunda bu elementə aid əlavə informasiya ilə verilir. Siyahı deskriptoru xüsusi yazı formasında reallaşdırılır və özündə siyahının başlanğıc ünvanını, struktur kodunu, siyahının adını, siyahıdakı axıcı elementin rəqəmini və s. özündə cəmləyir. Deskriptor yaddaşın siyahısının elementləri təyin edilən bölməsində yerləşə bilər.

İndi isə C dilindən istifadə edərək yuxarıda verilən məlumatları kodlaşdıraq. C dilində iki ədəd elementi və iteratoru olan bir struktur yaradaraq və listdə saxlanılan verilənləri ekrana çıxaran proqramı tərtib edək. Strukturun təsviri aşağıdaki kimidir:

Burada işlədilən malloc() (Memory Allocation) funksiyası verilmiş struktura uyğun olaraq yaddaşda (RAM-da) düyüm üçün yer ayrılmasını təmin edən C funksiyasıdır. Digər tərəfdən verilənlər ekrana çıxardılarkən root-dan istifadə olunub. İlk anda root və iterator eyni düyümü göstərdiyindən root->x yerinə iterator->x də yaza bilərdik. Bu proqramın yekun nəticəsi aşağıdaki kimidir:

Nəticədən gördüyümüz kimi RAM-da iki düyüm üçün yer ayrılmış və dəyişənlərə müvafiq olaraq 10 və 20 qiymətləri təyin olunmuşdur.

Tapşırığın davamı olaraq yaradılan əlaqəli listin sonuna yeni bir düyüm əlavə edək və listin son halını ekrana çıxaran proqramı tərtib edək;

Bunun üçün yuxarıda yazdığımız kodda dəyişiklik etməliyik. Əlaqəli listin sonuna bir düyüm əlavə edəcəyimizdən ilk olaraq listin sonunu tapmaq lazımdır. Listin sonunu tapmaq üçün bir dövr ifadəsi istifadə edəcəyik. Əvvəlki iki düyümü manual olaraq yaratdığımıza görə listin sonunun NULL olmasını da təmin etməliyik. Bu halda kod aşağıdaki formaya düşür:

Proqramı başlatsaq aşağıdaki nəticəni alarıq.

Nəticədən görüldüyü kimi dövr hər dəfəsində siyahıya yeni bir element əlavə etmişdir.

Növbəti nümunədə əlaqəli listdən element silmə prosesini ələ alırıq.

Silmə əməliyatını yerinə yetirərkən ehtiyatlı davranmaq lazımdır. İlk olaraq silinəcək elementdən əvvəl gələn elementi tapmaq və onu silinəcək elementdən sonra gələn elementlə əlaqələndirmək lazımdır. Əks təqdirdə listin silinən elementdən sonrakı hissəsi ilə əlaqə kəsildiyindən bu hissə fəzada qalır və əlçatmaz hala düşür. Ona görədə əvvəlki və sonraki elementləri əlaqələndirmək, daha sonra isə silinən elementin yaddaşda tutduğu yeri boşaltmaq lazım gəlir. Bu əməliyat C dilində free() funksiyası ilə yerinə yetirilir. Bu nöqtədə free() funksiyası ilə birbaşa element silmək mümkün olmadığından silinəcək elementi saxlamaq üçün bir başqa pointerə ehtyac yaranır. Bu pointeri temp (temporary-müvəqqəti) ilə qeyd ettikdən sonra silmə əməliyatını yerinə yetirə bilərik.

Aşağıda silmə əməliyatını yerinə yetiran funksiya üçün yazılmışdır. Qeyd etmək lazımdırki silinənəcək elementin listin başında, ortasında vəya sonunda gəlməsini kodda nəzərə almaq lazımdır. Aşaıdaki kod bu tələbləri ödəyir.


İndi isə bu funkisyadan istifadə edərək və əvvəlcədən yaratdığımız və elementləri 10 və 20 dəyərlərini saxlayan listdə 20 elementini silməyə çalışaq;


Gözlədiyimiz nəticə:

İlk olaraq EkranaCixart() funksiyasi hər iki elementi ekrana çıxartmalı;

Daha sonra sil() funkisyası ilə 20 dəyərinə malik düyüm listdən silinməli;

Sonda isə Listin son halı yəni geriyə qalan 10 dəyəri ekrana çıxarılmalıdır.

Proqramı başlatsaq aşağıdaki nəticəni alırıq:


Gözlədiyimiz nəticəni aldığımızı görürük.

İndi isə siyahıda olmayan ixtiyari bir dəyəri silməyə çalışaq və kodun düzgün işləyib işləmədiyi test edək;

44 dəyərinə malik düyümü silməyə çalışırıq və listdə belə düyüm olmadığından aşağıdaki nəticəni alırıq.


Bununlada verilənlərin strukturu mövzusunda Əlaqəli Siyahılar mövzusunu əhatə etmiş olduq.