Bu Blogda Ara

15 Mayıs 2010 Cumartesi

Bağlı Listeler

Merhabalar,
Bu yazımda sizlere bağlı liste veri yapısından bahsedeceğim. Veri yapısı deyince kulağa egzotik gelebilir. Ama inanın bildiğiniz şeylerden farklı bir şey anlatmayacağım. "Bildiklerimizi bir araya getirerek bilmediğimiz bir yapıyı tanımlama" şeklinde anlıyorum veri yapılarını...

Nedir? Neden gerek duyulmuştur?
Bağlı liste veri yapısı hafızanın farklı bölgelerinde bulunan verileri birbirine katar şeklinde bağlayan yapıdır.Dizi vb. yapılar zaten bu işi sağlamıyor mu? şeklinde bir soru aklınıza tam bu satırda gelmiş olmalı. Evet sağlıyor ama bir yere kadar. Diziler hafızanın belirli bir noktasında ardışıl olarak gelir. Yani dizinin ilk elemanı hafızanın 100 nolu adresinde bulunuyorsa dizinin ikinci elemanı 101 nolu gözde bulunacaktır. Ayrıca diziler ilk oluşturulduğunda uzunluğu belli olmak zorundadır. Daha sonra genişleme imkanı yoktur. Ancak tekrar boyutlandırma yapılabilir ki bu iş oldukça maliyetlidir. İşte böyle dinamik genişleyen ucuz maliyetli bir yapıya ihtiyaç duyulduğu sırada keşfedilmiş olmalı bağlı listeler.

Bağlı derken?
Bağlı listenin her bir elemanı hafızada birbirine bir sonraki elemanın aderesini gösterecek bilgiye sahiptir. Biz yalnızca ilk elemanın adresini biliriz. İkinci elemana ulaşmak için önce birinci elemana gideriz, ondan bir sonraki yani ikinici elemanın adresini alırız daha sonra ikinci elemana ulaşabiliriz. Üç, dört, beş ... hafıza dolana kadar üretilebilir, ulaşım mekanizması hep aynı. Bağlı derken bu mekanizma kastediliyor.

İhtiyaca göre...
Sorunlar farklı olunca çözümler, dolayısıyla gereksinimler de farklı oluyor. Bağlı liste veri yapısı iki çeşittir. Tek yönlü ve çift yönlü. İlkinde sadece ileri yönlü haraket yapmak mümkünken ikinci tipde geri gelme de mümkündür. Siz kendi probleminize en uygun tipi seçmelisiniz.

Bırak gevezeliği de biraz kod yaz!

Tek yönlü bağlı liste, C örneği

#include <stdio.h>
#include <stdlib.h>

typedef struct _eleman
{
struct _eleman *sornakiEleman; // bir sonraki elemanı işaret eder.
int veri; // yapının sakladığı veri. istenilen tipte istenildiği kadar veri eklenebilir.
} eleman;

typedef struct
{
eleman *ilkEleman; // bağlı listeyi temsil eden yapı. Yalnızca ilk elemanı işaret ediyor.
} bagliListe;

bagliListe *bagliListeUret();
void elemanEkle(bagliListe*,int);
void elemanCikart(bagliListe*,int);
void listele(bagliListe*);

int main()
{
bagliListe * bl = bagliListeUret(); // yeni bir bağlı liste ürettik.
elemanEkle(bl,6); // eleman ekleyelim.
elemanEkle(bl,34);
elemanEkle(bl,987);
elemanEkle(bl,5);
elemanEkle(bl,2);
listele(bl); // listele.
system("pause");
elemanCikart(bl,3); // 3. elemanı çıkart. ( ilk eleman 0'dan başlar)
listele(bl); // tekrar listele, farkı gör.
system("pause");
}

bagliListe *bagliListeUret()
{
bagliListe* bl = (bagliListe*)malloc(sizeof(bagliListe)); // yeni bir bağlı listeyi hafızada oluşturup ilgili adresi alıyoruz.
bl->ilkEleman = NULL;
return bl;
}

void elemanEkle(bagliListe* bl,int veri)
{
eleman *e = (eleman*)malloc(sizeof(eleman)); // yeni bir eleman oluşturalım.
e->sornakiEleman = NULL;
e->veri = veri;
eleman *son = NULL; // katarın son elemanı.
son = (eleman *)bl->ilkEleman; // başlangıç elemanını bağlı listeden alalım.
if (son==NULL) // listemiz boş mu?
{
bl->ilkEleman = e;
return;
}
while(son!=NULL) // değilse özyinelemeli olarak son elemana erişmeye çalış.
{
if (son->sornakiEleman==NULL)
break;
son = (eleman*)son->sornakiEleman; // düğümler arası atlama.
}
son->sornakiEleman = e; // nihayet son düğümün işaretçisine kendi adresimizi yazıyoruz.
}

void listele(bagliListe* bl)
{
eleman *e = NULL;
e=(eleman *)bl->ilkEleman;
int i=0;
while(e!=NULL) // özyinelemeli listeleme fonksiyonu.
{
printf("%i. eleman verisi = %i\n",i++,e->veri);
e = (eleman*) e->sornakiEleman;
}
}

void elemanCikart(bagliListe * bl, int sira)
{
eleman *e = NULL;
e=(eleman *)bl->ilkEleman;
eleman *onceki = NULL;
int i=0;
if (e==NULL) // listemiz boş mu?
{
printf("Liste bos oldugu icin cikartma yapilamiyor!\n");
return;
}
while(e!=NULL)
{
if (i==sira)
break;
i++;
onceki = e;
e = (eleman*) e->sornakiEleman;
}
onceki->sornakiEleman = e->sornakiEleman; // silmek istediğimiz elemanın bir önceki düğümü ile bir sonraki düğümü birbirine bağlıyoruz. Böylelikle aradan çekilerek silinmiş izlenimi oluşturuluyor.
free(e); // hafıza sızıntısını önlemek için serbert bıraktığımız elemanı hafızadan silmeyi unutmayalım.

}


Diğer yüksek seviyeli dillerde (Java, C# vb.) bu veri yapısını yapmak çok daha kolay. Mantıktan yola çıkarak o dillerde de sorunsuz bir şekilde bağlı liste veri yapısını oluşturabileceğinize inanıyorum.
Görüşmek üzere...

6 yorum:

Unknown dedi ki...

bu kod cok işime yaradi derslerimde.sizden kucuk bir ricam var.bnmde bir blogum var (blogger).
C kodunu sayfaya atma tarzını nasıl verdiniz?
bu konuda beni bilgilendirirseniz sevinirim.

Ramazan Bellek dedi ki...

İşine yaradığına sevindim. Kod parçalarını sayfa üzerinde renkli olarak göstermek için,
SyntaxHighlighter
version 3.0.83 (July 02 2010)

http://alexgorbatchev.com/SyntaxHighlighter
JavaScript code syntax highlighter.
Copyright 2004-2010 Alex Gorbatchev.

eklentisini kullandım. Kodların sağ üst kısmındaki küçük soru işaretine tıklarsan gerekli sayfa açılır. Gerekli style/javascript adres eklentilerini yapmak için blog yapsını düzenleyip var olan mevcut temanın kodlarına gömmen gerekiyor.

Bu arada blog adresini paylaşırsan sevinirim.

Kolay gelsin.

Unknown dedi ki...

cok tesekkur ederim.yorumu paylaştıktan sonra blogumu yazmadıgımı fakettim.

buda benim ama su anda tam olarak bitmiş degil.size danısacak cok seyim var.

http://clubyazilim.blogspot.com/

bolubeyi dedi ki...

Teşekkürler hocam bir de c sharp ile yapsaydınız güzel olurdu.

Adsız dedi ki...

lan enes naber. burdada çıktın karşıma insafsız :) (bu arada enes bizim sınıfta)

Şeref AKYÜZ dedi ki...

enes sizin sinıfta da sen hangi sinıftasın :) C# ta ben kendi blogumda yaptım bağlı listeler ilgilenen arkadaşlar olursa ziyaret edebilirler...
www.serefakyuz.com