Yazan : Şadi Evren ŞEKER

Siteye gelen bir soru üzerine bu yazıyı ekliyorum. Öncelik sırası (priority queue), kullanarak gelen hastaları verilen önceliğe göre dairesel bir bağlı listeye (linked list) yerleştiren ve ardından sırayla gelen hastaları listeden alan bir kodu C++ dilinde yazalım.

İlk olarak bir hastanın tanımını yapan sınıfı aşağıdaki şekilde kodluyoruz:

Bu tanıma göre bir hasta, ad, soyad ve sıradaki önceliğini bilmektedir. Bu sınıftan üretilen her hasta için bu bilgilerin girilebileceğini kabul ediyoruz.

Ayrıca yukarıdaki hasta sınıfında, yine sınıf ile aynı isme sahip bir inşa fonksiyonu (constructor) bulunmaktadır. Buradaki amaç, nesne (object) oluşturulurken bu aşamada ilk değerlerini atamaktır.

Hasta sınıfını tanımladıktan sonra, bağlı listenin her bir düğümünü (node) tutacak olan sınıfa geçebiliriz. Yukarıdaki sınıf tanımında siraEleman ismi verilen bu yapıda, bir veri bir de sonraki üyeleri bulunmaktadır. Basitçe, veri göstericisi her düğümde duran anlık veriyi ve sonraki göstericisi ise bağlı listemizin sıradaki elemanını gösterecektir.

Sonuçta üretmeyi planladığımız bağlı listeyi aşağıdaki şekilde çizebiliriz:

Yukarıdaki temsili resimde olduğu gibi, her düğüm (yuvarlak olarak tasvir edilmiştir), bir adet veriyi (kutu olarak tasvir edilmiştir) ve yine kendi cinsinden başka bir düğümü göstermektedir.

Sonuçta bağlı liste yapısı dairesel olmaktadır.

Yukarıda kodu verilen, siraEleman sınıfı işte bu resimdeki yuvarlak olarak tasvir edilen düğümleri tutmakta, hasta sınıfı ise kutularla gösterilen değerleri tutmaktadır.

Yukarıdaki temel sınıfları tanımladıktan sonra, ana sınıfımız olan ve bağlı listenin kodlandığı sira sınıfını kodlamaya geçebiliriz.

Sınıfımızda 3 adet temel fonksiyon bulunacaktır. Bunlar ekleme işlemi yapan ekle fonksiyonu, sıradaki hastayı alan siradaki fonksiyonu ve bağlı listenin durumunu bastıran bastir fonksiyonudur.

Sırasıyla bu fonksiyonların kodlamasını inceleyelim:

Yukarıdaki kodda, sıra bilgisini tutarken, sıranın ilk elemanını gösteren bir gösterici tanımlanmıştır. Bu gösterici “ilk” ismiyle isimlendirilmiş olup 27. satırda tanımlandıktan sonra, 28. satırda bulunan inşa fonksiyonu (constructor) içerisinde ilk değeri atanmıştır. Buna göre ilk göstericisi, ilk başta NULL değer taşımaktadır. Bunu elle özel olarak yazıyor olmamız, kodun geliştirildiği Dev-CPP ortamından kaynaklanmaktadır. Normalde bazı derleyiciler, bir göstericinin içerisine değer konulmadığı zaman NULL değerini atar, ancak Dev-CPP ortamında bu işlemi elle yapmak gerekmektedir.

Sonuçta inşa fonksiyonumuz çalıştıktan sonra elimizde bir ilk isimli gösterici (pointer) ve bu göstericinin gösterdiği bir NULL değeri olacaktır. Bu durum, bizim listemizin boş olduğu durumdur.

Gelelim en kritik fonksiyonumuz olan ve 31. Satırdan itibaren başlayan ekle fonksiyonuna. Bu fonksiyon öncelikle eklenecek olan hastayı gösteren bir gösterici almaktadır. Ardından bu hastayı önceliğine göre, dairesel listemize eklemektedir.

Fonksiyonda görüldüğü üzere 3 ihtimal değerlendirilmiştir. İlk if satırımızda (32. satır) listenin boş olup olmadığı kontrol edilmiştir.

Şayet liste henüz boşken ekleme işlemi yapılmak isteniyorsa, bu durumda tek bir düğüm oluşturup bu düğümün sonraki elemanı olarak gene kendisini işaretliyoruz. (listenin dairesel liste olması gerektiğini hatırlayınız).

Ayrıca listemizin ilk elemanını gösteren ilk göstericisi de bu yeni oluşturulan düğümü göstermektedir.

İkinci kontrolümüz (kodun 36. Satırında) bağlı listeye eklenen ilk elemandan daha önde olması gereken bir eleman olması durumunu incelemektedir.

Bu kontrol oldukça önemlidir ve dikkatsiz bir kodlamada gözden kaçabilir.

Listenin ilk elemanını gösteren ilk isimli gösterici sabit düşünülürse, bu durumda bu göstericinin gösterdiği düğümün değerine göre daha öncelikli birisi gelmesi durumunda hata oluşur. Çözüm olarak kodun 36. Satırında bulunan if kontrolü eklenmiştir.

Kontrolden geçilmesi durumunda yapmamız gereken en önemli eylem, ilk elemanımızı gösteren elemanı bulmaktır. Bunun sebebi dairesel bir listeye ekleme yapılırken, listenin ilk elemanını, listenin son elemanını göstermesi özelliğini bozmamaktır.

Örneğin aşağıdaki şekilde bir bağlı listemiz bulunsun:

Yeni gelen (ve resimde yeşil renkle gösterilen) elemanı, listeye ekleyeceğimizi düşünelim. Ayrıca listenin başına eklemek istediğimizi de düşünelim.

Bu durumda ilk elemanı gösteren ve listenin sonunda olan elemanın sonrasına bu yeni gelen yeşil eleman eklenecektir.

Sonuç olarak ilave bir gösterici ile listede hareket edip ilk göstericisini kaybetmeden listenin sonuna gitmemiz gerekiyor. Kodda bu göstericiye iter adı verilmiştir (iter kelimesi iterator kelimesinin kısaltması olarak liste içerisinde dolaşan bir göstericiye atfen verilmiştir).

Yukarıdaki şekilde, iter göstericisi son elemanı gösterdikten sonra ekleme işlemi yapılabilir. İter göstericisinin sona gitmesini sağlayan, kodun 38. satırındaki while döngüsüdür. Ardından iter->sonraki = yeni denilerek önce son elemandan yeni elemana bir gösterici atanmaktadır:

Ardından yeni->sonraki = ilk denilerek bu yeni eklenen elemanın sonrasına ilk eleman konulmaktadır.

Son olarak yeni eklenen bu elemanı listenin başı yapmak için ilk= yeni denilmektedir:

Artık listemiz, yukarıdaki şekilde de görüldüğü üzere, yeşil elemandan başlayıp, dairesel bir şekilde hafızada tutulmaktadır.

Gelelim ekleme işleminin son koşulu olan ve 45. Satırdan başlayan else bloğuna.

Bu durum, listenin boş olması ve listenin en başına eklenmesi durumları dışında kalan durumları tutmaktadır.

Listenin sonuna veya aradaki herhangi iki düğüm arasına eklemek için bu blok çalışır.

İşlem oldukça basit bir şekilde, eklenecek olan düğüme kadar önceliklere dikkat ederek ilerleme esasına dayanır. Kodun 48. satırındaki while döngüsü, liste sonu veya öncelik sırasında bizden sonrakileri atlayarak ilerler. Bizden önceliksiz birisi gelince bizi eklemek için durur. Bu kontrol sırasında, tek eleman bulunması ihtimali veya listenin sonuna eklenmesi ihtimaline karşı ilave bir if satırı daha eklenmiştir.

İşlem basitçe yeni bir düğüm oluşturup, ekleme işlemi yapacağımız düğümden sonrasının sonrasını, geçici bir göstericide (pointer) tutmaktadır.

Ekleme işlemi yapılıp eklenecek düğümden sonrasına, yeni düğüm bağlandıktan sonra, işte bu geçici düğüm, yeni düğümümüzün sonrasına bağlanmaktadır.

Sıradaki hastanın alınması işlemi için olan kodlamamız aşağıdaki şekildedir:

Yukarıdaki kodda, ekleme koduna benzer şekilde 3 ihtimal değerlendirilmiştir. İlk ihtimalde, liste boşken, sıradaki hasta istendiğinde, NULL değer döndürülmektedir.

İkinci ihtimalde, şayet listedeki son hasta da alınırsa, bu durumda liste boş hale getirilmektedir. Koddaki 63. Satırda bulunan free komutu gerekmemekle birlikte, kullanılmaması durumunda hafızada (RAM) tutulmakta olan hasta bilgileri silinmez. Uzun süreli kullanımlarda hafızada bu tip veri kırıntılarının kalması performans kaybına ve nihayetinde programın bozulmasına sebep olur. Bu yüzden hafızada bulunan bütün nesneleri, işimiz bittikten sonra free komutu ile kaldırmamız gerekir.

Free komutunu kullanabilmek için, geçici bir pointer (temp) tanımlanmalıdır. Bu tanımlamayı yapmadan free yaparsak, hasta bilgileri silinir. Dolayısıyla önce hasta bilgileri geçici bir göstericiye atanır, sonra free yapılıp bu geçici göstericinin değeri fonksiyon sonucu olarak döndürülür (return).

Son else koşulu ise, diğer bütün durumları (listenin boş olmaması ve listedeki son hastanın alınmaması durumunu) kapsar.

Basitçe sıradaki eleman ilk göstericisinin gösterdiği elemandır. Bu eleman alınıp, free yapıldıktan sonra döndürülür.

Bastır fonksiyonumuz, listenin ilk elemanını gösteren ilk göstericisinden başlayarak listedeki bütün elemanları bir döngüyle dolaşarak bastırır. Burada dolaşma işleminin bitmesinin ardından iter isimli, listeyi dolaşan gösterici, listenin son elemanını bastırmadan çıkar. Çözüm olarak 81. satırdaki gibi ilave bir bastırma işlemine ihtiyaç duyulur.

Kodun testi için, yukarıdaki gibi bir main fonksiyonu hazırladım. Basitçe 5 hastayı, karışık şekillerde ekliyor ve arından 3 kişiyi sıradan istiyor. Ekran çıktısı aşağıdaki şekilde başarılı çalışmaktadır.

Yukarıdaki çıktıda görülen bir takım kontrol satırları (debug) koddaki çalışmayı göstermektedir. Kodun son 3 satırı, istediğimiz sıradaki hastaları vermektdir. En yüksek öneme sahip olan sadi-seker-6 ilk gelmekte sonra 5 ve 4 önemlerine sahip kişiler çıkmaktadır.

Bu son 3 satırdan önceki 5 satır ise, listenin son durumunu göstermektedir. Görüldüğü üzere listedeki 5 kişi önem sırasına göre yerleştirilmiştir.

Kodun tamamına erişmek için tıklayınız.

Yorumlar

  1. zynp

    hocam tek kelımeyyle: süpersiniz...! ben cok yeniyim ve kendimi programlama konusunda geliştirmek istiyorum su an turbo c++ başlangıç olarak hakkında bilgi topluyorum eğer mümkünse, önerileriniz benim için cok önemli.yayınlarınız için ck teşekkürler.

  2. Kadriye

    kaç gündür uğraşıyorum ama olmadı bir türlü yardımcı olur musunuz? Bağlı listede sıralama yapamıyorum.ilk eklediğim ilk görünüyor ama ben öğrenci numaralarını küçükten büyüğe sıralama yapmak istiyorum.

    Kodum:

    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
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    
     
    #include 
    #include 
    #include 
    #include 
     
     
     
    typedef struct kisi
    {
            char ogr_no[50],isim[50],soyisim[50],sinif[50],donem[50];
            struct kisi *sonra;
     
    };
     
     
     
    struct kisi *yeni , *ilk , *son;
     
    void menu();
    void dugum_ekleme();
    void listele();
    void silme();
     
     
    int main()
    {
        yeni=NULL;
        ilk=NULL;
        son=NULL;
     
     
        menu();
        getch();
        return 0;
    }
    /****************************/
    /*Menu*/
    void menu()
    {
         system("cls");
         int cevap;
         printf("nnnntt1-Kayit eklen");
         printf("tt2-Kayitlari listelen");
         printf("tt3-Kayit siln");
         printf("tt4-Cikisn");
         printf("ttLutfen seciminizi yapiniz :");
         scanf("%d",&cevap);
         switch(cevap)
         {
                      case 1 : dugum_ekleme(); break;
                      case 2 : listele(); break;
                      case 3 : silme(); break;
                      case 4 : exit(1); break;
     
         }
     
    }
     
     
    /************************************************/
    /*Dugum Ekleme Fonksiyonu*/
    void dugum_ekleme()
    {
         if(ilk==NULL)
         {
     
            struct kisi *yeni = ((kisi *) malloc(sizeof(kisi)));
     
            printf("ntLutfen kisinin numarasini giriniz : ");scanf("%s",&yeni->ogr_no);
     
     
     
     
     
     
            yeni->sonra=NULL;
     
            ilk=yeni;
            son=yeni;
     
         }
         else
         {
            struct kisi *yeni = ((kisi *) malloc(sizeof(kisi)));
     
     
     
            printf("ntLutfen kisinin numarasini giriniz : ");scanf("%s",&yeni->ogr_no);
     
     
            yeni->sonra=NULL;      
            son->sonra=yeni;
            son=yeni; 
         }
         printf("ntAna menuye donmek icin bir tusa basiniz...");
         getch();
         menu();
     
    }
     
     
    /***************************************/
    /*Kayit listeleme*/
    void listele()
    {
     
       struct kisi *ara;
       printf("nn");
        if(ilk == NULL) printf("nkayit yokturn");  
      else if(ilk->sonra==NULL)
           {
                               printf ("Tek eleman var:%s",ilk);
           }
         else{ 
               while (ara->sonra->ogr_no>ara->ogr_no){
               printf("ttnOgrenci No->%s ",ara->ogr_no);
                    ara=ara->sonra;
                      }
                    ilk->sonra=ara->sonra;
                    ara->sonra=ilk;
                    ilk=ilk->sonra;
                    ilk->sonra=ilk->sonra->sonra;
                    printf("ttnOgrenci No->%s ",ara->ogr_no);
                    }     
     
       printf("ntAna menuye donmek icin bir tusa basiniz...");
       getch();
       menu();
     
    }
     
     
     
    /*Kayit silme*/
    void silme()
    {
         char ogr_no[50];
         struct kisi *sil , *once;
         printf("ntSilmek istediginiz numarasini giriniz..");
         scanf("%s",&ogr_no);
         once=NULL;
         sil=ilk;
           while(sil)
           {                    
                    if(!strcmp(ogr_no,sil->ogr_no))
                    break;
                    once=sil;
                    sil=sil->sonra;
           }             
         if(sil==NULL)
         printf("tBulunamadi.n");
         else if(sil==ilk)
         {
                     ilk=ilk->sonra;
                     free(sil);
                     printf("tKayit silindi..");
         }
         else if(sil==son)
         {
                     once->sonra=NULL;
                     son=once;
                     free(sil);
                      printf("tKayit silindi..");
     
         }
         else 
         {
                    once->sonra=sil->sonra;
                    free(sil);
     
    printf("tKayit silindi..");
         }
         printf("ntAna menuye donmek icin bir tusa basiniz...");
         getch();
         menu();
    }
  3. Kadriye

    Mantık olarak anladım güya ama koda dökemedim dünden beri uğraşıyorum 🙁

    Hazır kodundan kastınız ne acaba?

  4. Şadi Evren ŞEKER Article Author

    Verdiğim adrese bakarsanız oradaki "Örnek Bağlı Liste kodları" listesinde aşağıdaki başlıkla hazır çalışan kod bulunuyor (rar dosyası olarak indirip çalıştırabilirsiniz):

    Dairesel Tek yönlü bağlı listeye ekleme yapan, sıralı ekleme yapan ve silen kod.

    Başarılar

  5. Kadriye

    Hocam while döngüsünün içindeki hata nerede acaba programı çalıştırdığımda bu döngüye hiç girmiyor.

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    
    for(ara=ilk;ara!=NULL;ara=ara->sonra)
     {
           while (yeni->ogr_no ogr_no )
           {
              yeni->sonra=NULL;
              yeni->sonra=ara;
     
           }
     }
     yeni->sonra=NULL;
     son->sonra=yeni;
     son=yeni;
    }
  6. Kadriye
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    for(ara=ilk;ara!=NULL;ara=ara->sonra)
           {
           while (yeni->ogr_no <= ara->ogr_no )
           {
           yeni->sonra=NULL;
           yeni->sonra=ara;
     
           }
           }
           yeni->sonra=NULL;
           son->sonra=yeni;
           son=yeni;
     
          }
  7. Şadi Evren ŞEKER Article Author

    Bu bahsi geçen değerleri ekrana bastırırsanız probleminizi bulabilirsiniz. Muhtemelen şartları sağlayan bir durumda başlamıyorsunuz.

    1
    2
    3
    4
    5
    6
    7
    8
    
    for(ara=ilk;ara!=NULL;ara=ara->sonra)
       {
           printf("%d %d", yeni->ogr_no,ara->ogr_no);
           while (yeni->ogr_no <= ara->ogr_no )
           {
               printf("%d %d", yeni->ogr_no,ara->ogr_no);
     
           }

    şeklinde printf satırları eklerseniz durumu görebilirsiniz. Ayrıca kodunuzu ne için yazdığınızı anlayamadım ama büyük ihtimal algoritmanızda da hata var. Yaptıklarınız bağlı listelerdeki herhangi bir işlemle karşılanmıyor.

    Başarılar

  8. Kadriye

    Yapmaya çalıştığım şey şu:
    Yeni bir değer ekleneceği zaman öncekileri tarıyo kimden küçükse hemen onun önüne eklio ama tabi olmadı yer değiştirmeyi yapamadım. Araya eleman ekleme gibi

  9. Şadi Evren ŞEKER Article Author

    Bakın size daha önce de adresini verdiğim konumdan kodu alıp aşağıda yayınlıyorum, zaten bu kod sitede yayınlanış durumda ancak bir kere daha buradan anlatıyorum:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    
     
    node *insert2(node* ll,int data){
      if(ll==NULL){
         ll=(node*)malloc(sizeof(node));
         ll->data = data;
         ll->next = ll;
         return ll;
     }
     node *temp =(node*)malloc(sizeof(node));
     temp->data = data;
     node * iter = ll;
     while(iter->next != ll && iter->next->data < temp->data)
                      iter = iter->next;
     temp->next = iter->next;
     iter->next = temp;
     
    }

    Yukarıdaki kod, bahsettiğiniz ve yapmayı istediğiniz iş için yazılmıştır.

    ihtimaller:
    1. bağlı liste tamamen boş olabilir (çözüm en üstteki if koşulu)
    2. Bağlı listede herhangi bir elemandan küçük bir sayı eklemek istiyor olabiliriz ( Çözüm: Durum koddaki while döngüsü içerisindeki küçüklük koşulu ile kontrol ediliyor)
    3. Bağlı listeye, şimdiye kadar eklenen en büyük sayıyı eklemek istiyor olabiliriz. Yani listenin sonuna eklenmesi gerekiyor olabilir (Çözüm, dairesel bağlı liste olduğu için ll eşitliği while döngüsünde kontrol edilmiştir.)

    Ekleme işleminin nasıl yapıldığını görmek istiyorsanız, aynı linki bir kere daha veriyorum burada detaylıca açıklanıyor:

    http://www.bilgisayarkavramlari.com/2007/05/03/linked-list-linkli-liste-veya-bagli-liste/

    Başarılar

  10. Ali

    Hocam yeniyim bu konuda ilginize teşekkür ederim bi kaç sorum olacaktı.

    son msjınızda ki ilk if komutu şunu mu demek istiyor

    ilk eleman yoksa
    ilki ekle
    ilkin değerini değer yap
    ilkin sonrasını ilk yap
    ilke geri dön

    böle anladığım için bana anlamsız geldi :S
    oradaki

    ll->data = data;
    ll->next = ll;
    kodu tam anlayamadım sanırım.

  11. Şadi Evren ŞEKER Article Author

    Evet aynen anladığınız gibi doğru. Yani if kısmında bağlı liste daha hiç yokken oluşturulması aşamasını görüyorsunuz. Bu durum aşağıdaki şekilde, yukarıdaki yazıda da gösterilmiştir.

    Öncelikle bir düğüm (node) oluşturulup kendisini göstermesi sağlanıyor ve bağlı listeyi gösteren ll' de bu düğüme işaret ediyor.

    ll->data = data // eklenecek olan veriyi yeni oluşturduğun düğümün verisi olarak kaydet
    ll->next = ll // bu yeni düğümün next göstericisi kendisini göstersin.

    Yani yukarıdaki şekildekinin aynısı oluşturulmuştur.

  12. aziz

    hocam c# dilinde pek bulamaıyorum ÖNCELİK KUYRUĞU (PRIORITY) hakkında kodlama bu konuda yardım edermisiniz .. tesekkürler

  13. Şadi Evren ŞEKER Article Author

    Yukarıdaki kod zaten öncelik kuyruğu (priority queue) yapmakta, kodun c# diline çevrilmesinde sorun olmamalı C dili ile yazdım ve ufak değişikliklerle çalışır hale getirebilirsiniz. İsterseniz dönüştürmeyi deneyin ve takıldığınız yer olursa veya hata ile karşılaşırsanız yardımcı olmaya çalışayım. Ne yazık ki kullandığım bilgisayarda windows ve visual studio yüklü olmadığı için yazıp yayınlama imkanım bulunmuyor.

    Başarılar

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


− 6 = sıfır