Veri Yapıları: Dairesel Bağlı Listeler

(Son Güncelleme: )
veri yapıları › c++
, , ,

Dairesel Bağlı Listeler

Dairesel bağlı listelerin tek yönlü listelerden tek farkı son elemanın sonraki işaretçisinin ilk elemanı işaret etmesidir. Böylece dairesel bir zincir yapısı oluşturulmuş olur. Basitçe yapı şekildeki gibidir;

Bağlı Liste Yapısı

Yani kabaca, değişecek olan tek şey kontrol şeklimiz. Sayacımızın sonraki işaretçisi NULL gösterene kadar değil ilk işaretçisinin gösterdiği yeri gösterene kadar devam edeceğiz.

Yapıda temel aynı olduğu için sadece fonksiyonların işleme mantığını aşağıdaki şekilde paylaşacağım.

Listeleme:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Listele(oge* ilkEleman)
{
    int i = 1;
    oge* s = ilkEleman;

    do
    {
        cout << i << ". eleman: " << s -> sayi << endl;
        i++;
        s = s -> sonraki;
    } while(s != ilkEleman);

    cout << endl;
}

Ekleme:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
oge* Ekle(oge* ilkEleman, int eklenecekDeger)
{
    // liste boş ise
    if(ilkEleman == NULL)
    {
        ilkEleman = (oge*) malloc(sizeof(oge));
        ilkEleman -> sonraki = ilkEleman;
        ilkEleman -> sayi = eklenecekDeger;
        
        return ilkEleman;
    }

    // liste bir veya daha fazla elemana sahip ise
    oge* s = ilkEleman;
    oge* gecici = (oge*) malloc(sizeof(oge));

    // eklenecek değer ilk elemandan küçükse
    if(ilkEleman -> sayi > eklenecekDeger)
    {
        gecici -> sayi = eklenecekDeger;
        gecici -> sonraki = ilkEleman;
        
        while (s -> sonraki != ilkEleman)
        {
            s = s -> sonraki;
        }
        
        s -> sonraki = gecici;
        return gecici;
    }

    // son eleman değilse ve
    // sonraki eleman eklenecek sayidan küçükse
    // eklenecek eleman için doğru aralığı bulmaya çalışıyoruz.
    while(s -> sonraki != ilkEleman &&
            s -> sonraki -> sayi < eklenecekDeger)
    {
        s = s -> sonraki;
    }

    // aralığı bulduktan sonra
    // büyük elemanı geçicinin sonraki işaretine atıyoruz.
    gecici -> sonraki = s -> sonraki;

    // sayimizi ekliyoruz.
    gecici -> sayi = eklenecekDeger;
    
    // sonraki işaretine elemanı atıyoruz.
    s -> sonraki = gecici;

    return ilkEleman;
}

Silme:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
oge* Sil(oge* ilkEleman, int silinecekDeger)
{
    oge* s = ilkEleman;
    oge* gecici;

    if(s -> sayi == silinecekDeger) // silinecek olan eleman ilk elemansa
    {
        // son elemana kadar geliyoruz.
        while (s -> sonraki != ilkEleman)
        {
            s = s -> sonraki;
        }
        
        // ilkEleman'ı yani ilk'i zincirden çıkarıyoruz.
        s -> sonraki = ilkEleman -> sonraki;
        
        // ilkEleman'ı siliyoruz.
        free(ilkEleman);
        
        // yeni ilk eleman olacak olan ikinci elemanı döndürüyoruz.
        return s -> sonraki;
    }

    // silinecek olan eleman ilk eleman değilse
    // listede aramaya başlıyoruz.
    do
    {
        // silinecek eleman bulunduysa
        if(s -> sonraki -> sayi == silinecekDeger &&
            s -> sonraki != ilkEleman)
        {
            gecici = s -> sonraki;
            s -> sonraki = s -> sonraki -> sonraki;
            free(gecici);
            
            return ilkEleman;
        }
        
        // bulunamadıysa sonraki elemana geçiyoruz.
        s = s -> sonraki;
    } while(s -> sonraki != ilkEleman);
    
    // silinecek eleman bulunamadıysa
    cout << "Silinecek eleman bulunamadi." << endl;
    return ilkEleman;
}

Önceki örnekte olduğu gibi bu örneği de belirli testlerden geçirdim. Herhangi bir sorunla karşılaşmadım. Kaynak kodun tamamı şu şekilde:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <stdlib.h>

using namespace std;


// liste eleman şablonumuzu oluşturmak için
// struct yapısını kullanıyoruz.
struct v
{
    int sayi;
    v* sonraki;
};
typedef v oge;

void Listele(oge* ilkEleman)
{
    int i = 1;
    oge* s = ilkEleman;

    do
    {
        cout << i << ". eleman: " << s -> sayi << endl;
        i++;
        s = s -> sonraki;
    } while(s != ilkEleman);

    cout << endl;
}

oge* Sil(oge* ilkEleman, int silinecekDeger)
{
    oge* s = ilkEleman;
    oge* gecici;

    // silinecek olan eleman ilk elemansa
    if(s -> sayi == silinecekDeger)
    {
        // son elemana kadar geliyoruz.
        while (s -> sonraki != ilkEleman)
        {
            s = s -> sonraki;
        }
        
        // ilkEleman'ı yani ilk'i zincirden çıkarıyoruz.
        s -> sonraki = ilkEleman -> sonraki;
        
        // ilkEleman'ı siliyoruz.
        free(ilkEleman);

        // yeni ilk eleman olacak olan ikinci elemanı döndürüyoruz.
        return s -> sonraki;
    }
    
    // ilk eleman değilse
    // listede aramaya başlıyoruz.
    do
    {
        // silinecek eleman bulunduysa
        if(s -> sonraki -> sayi == silinecekDeger &&
            s -> sonraki != ilkEleman)
        {
            gecici = s -> sonraki;
            s -> sonraki = s -> sonraki -> sonraki;
            free(gecici);
            return ilkEleman;
        }
        
        // bulunamadıysa sonraki elemana geçiyoruz.
        s = s -> sonraki;
    } while(s -> sonraki != ilkEleman);
    
    // silinecek eleman bulunamadıysa
    cout << "Silinecek eleman bulunamadi." << endl;
    return ilkEleman;
}

oge* Ekle(oge* ilkEleman, int eklenecekDeger)
{
    // liste boş ise
    if(ilkEleman == NULL)
    {
        ilkEleman = (oge*) malloc(sizeof(oge));
        ilkEleman -> sonraki = ilkEleman;
        ilkEleman -> sayi = eklenecekDeger;
        
        return ilkEleman;
    }
    
    // liste bir veya daha fazla elemana sahip ise
    oge* s = ilkEleman;
    oge* gecici = (oge*) malloc(sizeof(oge));

    // eklenecek değer ilk elemandan küçükse
    if(ilkEleman -> sayi > eklenecekDeger)
    {
        gecici -> sayi = eklenecekDeger;
        gecici -> sonraki = ilkEleman;
        
        while (s -> sonraki != ilkEleman)
        {
            s = s -> sonraki;
        }
        
        s -> sonraki = gecici;
        
        return gecici;
    }
    
    // son eleman değilse ve
    // sonraki eleman eklenecek sayidan küçükse
    // eklenecek eleman için doğru aralığı bulmaya çalışıyoruz.
    while(s -> sonraki != ilkEleman &&
            s -> sonraki -> sayi < eklenecekDeger)
    {
        s = s -> sonraki;
    }
    
    // aralığı bulduktan sonra
    // büyük elemanı geçicinin sonraki işaretine atıyoruz.
    gecici -> sonraki = s -> sonraki;
    
    // sayimizi ekliyoruz.
    gecici -> sayi = eklenecekDeger;
    
    // sonraki işaretine elemanı atıyoruz.
    s -> sonraki = gecici;
    
    return ilkEleman;
}

int main(int argc, char *argv[])
{
    // her zaman ilk elemanı gosterecek olan ilk isaretcimiz.
    oge* ilk;
    ilk = Ekle(ilk, 1);
    Listele(ilk);

    return 0;
}