GLib Çift Bağlı Liste Nasıl Belgesi

Açık Kaynak, Programlama, tutorial, ytulinux

Merhabalar, uzun bir süre sonra kaldığım yerden yazmaya devam etmenin kıvancını duymaktayım :)

Bundan bir kaç saat önce, hash tablosu kullanmak için bir kütüphane aramaya başladım ve glib-2.0 kütüphanesinin, standartlaşmış ve c programlama dili ile veri yapılarına takla atlatmak üzere donatılmış olduğunu farkettim. Kısa bir flashback yaşayıp, boşa geçen yıllarımı yadettikten sonra, bu konuda bir nasıl belgesi aramaya başladım.

http://www.scribd.com/doc/3499572/Manage-C-Data-Using-the-GLib-Collections

adresindeki kitabı buldum ki henüz bir kaç sayfasına bakmış olmama rağmen oldukça beğendim.

http://www.gtk.org/api/2.6/glib/

adresinde de bu kütüphaneye ait atıf kütüphanesini (Reference Library) buldum. Ancak demin linkini vermiş olduğum kitap eğer sayılmazsa, bir çok alanda yazılmış tonlarca dökümantasyona kıyasla bu konuda pek anlatım bulamadım.

Bu kütüphanedeki yapıları kullanabilir hale gelmek istiyorum, tabi bunu yaparken belgelendirmesini de yapıp topluma faydalı sayacan sevecen bir genç olmamak için herhangi bir nedenim yok.

Hedefim olabildiğince her veri yapısını kullanmayı gösteren ayrı ayrı nasıl belgesi yazmak, umarım sıkılıp bu belgelendirmeyi yarıda bırakmam.

Evet bu kadar edebiyat parçaladıktan sonra sanırım esas işimize dönebiliriz. Bu belgenin hedefi, Glib-2.0 kütüphanesindeki çift bağlı listelerin (double linked list) nasıl kullanıldığını gözler önüne sermek.

Öncelikle çift bağlı liste nedir, yenir mi bu konuda bir kaç şey yazmak sanırım oldukça faydalı olacaktır.

Hmm şimdi bağlı liste nedir oradan başlamak daha mantıklı geldi. İşi gaz ve toz bulutuna kadar götürmeden başlasam sanırım iyi olacak :) Bilenler direk olarak konuları atlayıp kendilerini ilgilendiren kısma gelebilirler.

Bağlı Liste
Dİyelim ki N tane verimiz var. Bu verilerin tipi tamsayı olsun. Bu sayıları genellikle dizide tutar, işlemlerimizi dizi üzerinde yaparız. Ancak işlemlerimiz her zaman basit olmayabilir. Örneğin, elimizde bir dizi var ve her seferinde dizinin ilk elemanını silip, diziyi sıkıştıran ve ilk elemanı geriye döndüren bir fonksiyon yazmak istiyoruz. (Evet farkındayım pek de gerekli görünen bir örnek olmadı ama anlamaya yardımcı olacağını düşünüyorum)

Eğer bu olayı dizi mantığıyla yaparsak, her seferinde diziyi sıkıştırmamız, dolayısıyla N kere dönecek bir döngüye ihtiyacımız olacaktır. Karmaşıklığımız N kadar artıyor. Bir sonraki sayıyı çektiğimizde de N-1 kere daha dönmesi gerekecek. Dizinin tüm elemanlarının bu fonksiyon ile geri döndürülmesi ise bu durumda (N*(N-1))/2 karmaşıklığına sahip olacaktır ki (N + N-1 + N-2 + N-3…..1) bu pek de isteyeceğimiz bir durum olmayacaktır. Bu şekilde siz sevgili okurlarıma ölümü gösterip sıtmaya razı ettikten sonra bağlı listeyi anlatayım.

Bu açmazdan çıkmak istiyorsunuz. Ne yaparsınız? Her tamsayı değişkenimize ait bir de işaretçi koyarsınız. (birazdan herşey yerine oturacak) Her işaretçi, bağlı olduğu tamsayı değişkenden sonra hangi tamsayı değişkenin geldiğini gösterir.

typedef struct {
int sayi;
tamsayi * sonraki;
}  tamsayi;

diyelim ki bu şekilde 5 tane sayımız var.
sayi  sonraki
1          2
2          4
5          -1
3          5
4          3
Bir an için adresleme ile ilgili bildiklerinizi bir yana bırakın ve hafızada bu sayıların 1. adresten 5. adrese doğru dizildiklerini düşünün. Görüleceği gibi ilk sayımız 1, 2. adresi işaretlemiş. 2 de 2 var, o da 4. adresi işaretlemiş. 4 te 3 var, 5. adresi işaretlemiş. Bu şekilde küçükten büyüğe sayılarımızı işaretlemiş bulunuyoruz.
Ne demiştik, her seferinde ilk sayıyı sileceğiz. Peki ilk sayıyı silersek ilk sayının hangisi olduğunu nereden bileceğiz? Bağlı listelerin başında, ilk düğümün ne olduğunu gösteren bir işaretçi bulunur.
Yani düşünün ki elimizde

tamsayi * ilk,elde;
// ilk düğümü gösteren işaretçimiz “ilk”, onun gösterdiği düğümü yaratıyoruz
ilk = (tamsayi * ) malloc (sizeof(tamsayi));
// ilk düğümümüzün değerini atıyoruz
ilk->sayi = 1;
// en son yarattığımız düğümü elde değişkeninde tutuyoruz ki eklemeleri yapabilelim
elde=ilk;

for (i=0;i<4;i++){
//sonraki düğümü ekliyoruz, elde düğümünün içindeki sonraki işaretçisine bu düğümün adresini atıyoruz
elde->sonraki = (tamsayi * ) malloc (sizeof(tamsayi));
//elde değişkenine son yarattığımız düğümü atıyoruz
elde=elde->sonraki;
elde->sayi=1; // tüm sayılar 1 olsun uğraşmayalım şimdi 😀
}
//bundan sonra başka düğüm yok anlamında, işaretçiye -1 atıyoruz.
elde->sonraki = -1;
/* Malloc başarısız olursa falan fıstık gibi şeyleri kodun daha kısa olması ve beni daha az yorması açısından koymuyorum, zaten konumuz aslında bağlı listenin nasıl yazıldığı değil. Bu konuları üstünkörü geçseniz de olur, zaten yazılmışını kullanmayı öğreneceksiniz :)*/
şeklinde bir yapı olsun.
Eğer ilk elemanı silmek istersek, “ilk” işaretçimize ilk değil de ikinci düğümün adresini vermemiz yeterli (tabi bu arada ilk düğümü free() etmeyi unutmuyoruz yoksa bellek devamlı şişer)
Neyse bağlı liste böyle birşey, gelelim çift bağlı listeye.
Çift Bağlı Liste
Bağlı listede sadece sonraki elemanı gösteren işaretçimiz vardı. Çift bağlı listede ise önceki elemanı gösteren işaretçi de var. Peki bu ne işe yarar? Diyelim ki 5 değerini alan düğümden önceki düğümü bulmak istiyoruz. Bağlı listede bunu yapamayız. (evet olabildiğince basit örnekler :) umarım basit anlatmaya çalışırken açıklayıcılıktan uzaklaşmıyorumdur.)
Gelelim kuru fasülyenin faydalarına…
GLib Çift Bağlı Liste

http://library.gnome.org/devel/glib/unstable/glib-Doubly-Linked-Lists.html
adresinde atıf listesi bulunan veriyapımızın, tanım şekli şu şekildedir:

typedef struct {
gpointer data;
GList *next;
GList *prev;
} GList;

Öncelike örnek olarak basit bir program verelim, bunu derledikten sonra (derlerken anlamanıza gerek yok) aşağıdaki açıklamaları okumanızı (okuyunca anlamış olmanız gerekiyor, anlamasanız da hıııı demeniz yeterli) ve programda kullanılmamış fonksiyonları denemenizi tavsiye ediyorum.

#include <glib.h>
#include <stdio.h>
// keyfi olarak oluşturduğum bir fonksiyon, aslında ihtiyaç yok. Olayın printf e özel olmadığını göstermek için yazıldı.
int yaz (char * yazi)
{
printf(“%s\n”,yazi);
return 0;
}
int main ()
{
GList * list = NULL;
list = g_list_append(list, “Slm nbr”);
list = g_list_append(list, “Gule gule”);
g_list_foreach(list,(GFunc)yaz,NULL);
return 0;
}

Derlemek için terminale (başka işletim sistemindeyseniz kendi başınızın çaresine bakmanız gerekecek, linux için glib-2.0 kütüphanesini yüklemeniz yeterli)
gcc program.c -o program.out -I/usr/include/glib-2.0 -I/usr/lib/glib-2.0/include -lglib-2.0
Yazmanız yeterli. Eğer hata verirse whereis glib-2.0 yazarak kütüphanenin yukarıda belirtilen klasörlerden başka klasörde olup olmadığını kontrol edin. (Yüklü olup olmadığı konusuna değinmiyorum bile :=) )

Listemizi oluşturmak için ilk olarak
Glist * liste = NULL;
diyoruz, bu bizim ilk düğümümüzü gösteren işaretçimiz. Düğümümüz henüz yok dolayısıyla NULL.
Yeni bir string eklemek istiyorsak,
liste = g_list_append(liste, “Merhaba dünyalı ben dostum”);
diyerek ilk elemanımızı ekliyoruz.
Eğer araya eleman eklemek istiyorsak,
liste = g_list_insert(liste,”ikinci yazi”,1);
Diyerek, üçüncü parametrede bulunan sıraya verdiğimiz stringi sıkıştırabiliyoruz (0 dan başlıyor)
Eleman silmek için
liste = g_list_remove(liste,”ikinci yazi”);
İki listeyi birleştirmek için
liste = g_list_concat(liste1,liste2);
Listedeki tüm elemanları tek tek bir fonksiyona parametre olarak yollamak için (örneğin printf)
g_list_foreach(liste,(GFunc)printf,NULL); // GFunc, glib kütüphanesinde kullanılan fonksiyon işaretçisi tipi, yani typecast yapıyoruz. Verdiğimiz üçüncü parametre, fonksiyona ek parametre vermek istediğimiz zaman kullanılıyor ki şu an böyle birşeye ihtiyacımız yok
Listeyi ters çevirmek için:
g_list_reverse(liste);
yazmamız yeterli.
İşimiz bitince de g_list_free(liste); diyerek aldığımız bellek alanını rahat bırakıyoruz ki başka programlar soluk alsın.

Çift bağlı liste bu şekilde kullanılıyor. Kolay gelsin :)

Bu yazı toplamda 3946, bugün ise 0 kez görüntülenmiş

4 Comments
  • http://www.ce.yildiz.edu.tr Oğuz YILMAZ

    Sabredip sonuna kadar okumamda başımda duruyor olmanın en ufak bir etkisi olmadı emin ol :p

    O değil de gerçekten iyi olmuş, vatana milete hayırlı bir girdi olmuş. M. Yahya Karslıgil, seni andık bu gece kulakların çınlasın :)

  • http://yildirim.isadamlari.org salih

    iyiymiş hacı

  • Tuba AŞIK

    Bilgilendirici bir makale olmuş.Eline sağlık.
    Şunu da demenden geçemicem:
    //Hele şükür facebook’tan zaman bulup böyle faydalı şeyler yapabildin 😀

  • huseyinalb

    teşekkür ederim :)
    devam etmeye çalışacağım bakalım facebooktan zaman bulabilecek miyim 😛