Veri Yapıları - Doubly Linked List

By Burak TUNGUT - 26.11.2012 - 1 Yorum - Kategori C / C++

Bir veri yapıları konusunda daha tekrar beraberiz :) Dün yazdığım Singly Linked List konusunda bir hayli olumlu e-mailler aldığımı söylemeden geçmeyeceğim. Bugün ise dünkü yapımızla neredeyse aynı olan fakat iki yönde de hareket etme kabiliyetine sahip olan Doubly Linked List yapısını göreceğiz.

Küçük farklılıklar, büyük kolaylıklar

Keşke yukarıda yazdığım başlık her konuda geçerli olsa. Ne yazık ki her konuda küçük farklılıklar ile büyük kolaylıklar, kazançlar sağlamak söz konusu olmuyor. Fakat dün derinlemesine bir inceleme yaptığımız singly yapıda hatırlatsanız tek yönde hareket edebiliyorduk çünkü struct içeriğimizde yönümüzü belirleyen tek bir özelliğimiz mevcuttu.
Doubly yapıda ise ismindende anlaşılacağı üzere iki yöndede hareket edebilmek için struct içeriğimizde bir önceki vagonumuzu gösterecek bir özellik daha olacak. Bir önceki makalemizi okumayanlar için hatırlatalım ; biz bir tren yolculuğundayız ve kayıtlarımızda bizler için birer vagon :)

Yapacağımız farklılıklar

Dünki özellikle uzun ekle methodundan sonra size sevindirici birkaç şey söyleyebilirim. Bu yapıda dünki methodları neredeyse aynen kullanacağız. Sadece yeni yapımızda bir önceki kaydıda gösterecek bir özelliğimiz olduğu için sizde takdir edersiniz ki ekleme işleminde sadece bir kaç satır fazla kod yazacağız. Gel gelelim buna rağmen silme işleminde yaptığımız bir önceki kaydı bulma işlemini bu sefer yapmayarak bir hayli işimizi kolaylaştıracağız :)

Yeni Struct'ımız

struct Yapi{
	int Data;
	Yapi* Next;
	Yapi* Back;
};

Dünki yapıdan tek farkı Next de olduğu gibi bir de bir önceki vagonu gösterecek olan Back pointerımızı ekleyip işlemlerimize devam edelim.

Devamı

Veri Yapıları - Singly Linked List

By Burak TUNGUT - 25.11.2012 - 3 Yorum - Kategori C / C++

Dün yazdığım makale ile Veri Yapılarına ve Struct tanımlanmasına ilişkin güzel bir örnek incelemiştik. Bugün ise sizlerle yeni bir yapıyı yanı Linked List yapısını inceliyor olacağız. Makaleye başlamadan önce şunu söylemeleyim ki ilk defa bu konuya başlayacak olanlar ve pointerlar ile arası iyi olmayanlar hatta olaya biraz eğlenceli bakmak isteyenler kesinlikle yapacağımız bu yapıda tren vagonlarını düşünsünler :) Umarım tren yolculuğundan hoşlanıyorsunuzdur çünkü yolculuğumuz başlamak üzere :)

Yazdığımız Struct İçin Bir Array Düşünelim

Yukarıda linkini verdiğim makaleyi şöyle bir göz önüne alalım. Hatırlarsanız Ogrenci adında bir struct tanımlayıp üzerinde çok küçük bir kaç işlem yapmıştık. Birde Ogrenci yapısından bir array tanımladığımızı. Bunu düşünmek hiçte zor değil nasıl int için bir array tanımlıyabiliyorsak, kendi yaptığımız bir yapı içinde tanımlayabiliriz.
Fakat ne yaparsak yapalım bu arrayin bir sınırı olmak zorunda. Hatta C# ve Java da olduğu gibi C++ da runtime anında belirleme şansımız olmayan bir sınır :)

Son cümlemi biraz açacak olursam ; C# ve Java da bir array tanımlarken, kodlama esnasında sınır bildirmek zorunda değilsiniz. Bu işi runtime yani uygulamanın çalışma esnasında da yapabilirsiniz. Fakat C++ da böyle bir imkanımız yok. Bu da demektirki öyle bir yapı tercih etseydik çalışma anında bile belirleyemediğimiz bir sınır dahilinde olacaktık.

Neden Linked List ?

Konu başlığımız linked list idi ama halen bu konuda fazla söz etmedik :) Aslında yukarıdaki senaryoya devam edelim. Bizim şu anda tek ihtiyacımız Mr.Muscle'ın reklamlarında olduğu gibi eski yapıyı silip, bizi kurtaracak yapıyı getirecek bir süper kahraman. İşte bu süper kahraman sizsiniz ve yeni yapımız ise Linked List.
Yukarıda dediğimiz gibi array bizim için bir yere kadar çözüm sonuçta sınırı var fakat linked listin böyle bir engeli yok. Tabiri caizse "Ekle Ekleyebildiğin Kadar". Tek bir engelimiz var o da bilgisayarımızın RAM'i. Sonuçta 8byte'lık bir yapı ile memory de sızma yapacak kadar da ekleme yapmayız herhalde :) . Sınırları zorlarım diyenleri duyar gibiyim :)

Linked List = Sonsuz Kayıt

Linked List'i anladık, peki Singly'de ne ?

Aslında şimdi söyleceklerim tamamiyle teoride ve haliyle aklımızda da bir bulut gibi havada kalacak. Hiç uzatmadan tıpkı ders kitaplarının bizlere herşeyi harika öğretiyormuş gibi (Umarım mesaj gitmiştir :) ) bende şunu söyleyebilirim ki, tek yönde hareket etme kabiliyetine sahip linked list'e, Singly Linked List denir.

Trenimizi dizayn edelim

Artık işimize geri dönelim ve senaryomuzdan bahsedelim. Bugün ki amacımız içersine int bir değer verebileceğimiz bir linked list yapısı tasarlamak. Kısacası ucu bucağı olmayan bir sayı listesi tasarlayıp, ekleme, silme, bulma gibi fonksiyonlar yazacağız.
Şimdi ise bir vagon düşünelim. Bu vagon sadece iki bölmeden oluşsun, bir bölmede sayımız (Data), diğer bölmede ise ondan sonra gelen vagonu gösterecek bir pointer (Next) olsun. Aslında burda yapacağımız struct içeriğinide belirlemiş olduk. Demek ki struct içeriğimizde bir adet int ve bir adet söz konusu struct yapısını gösteren bir pointer olacak.

Lokomotif nerede ?

Hemen şunu söylemeleyim ki artık lokomotif demiyor, ona Head diyoruz. Sonuçta yukarıdaki gibi biz her bir sayı eklediğimizde bizim bir vagonumuz olacak e haliyle bunlarıda çekecek en başta bir lokomotif, pardon Head olmalı. Çünkü biz eklediğimiz bu sayıları bir array içersinde tutmayacağız haliyle bize tüm işlemlerde hangi vagondan başlayacağımızı gösterecek bir yapıya ihtiyacımız var ki bu da bizim Head değişkenimiz olacak.

Teorik bilgimizi simülize edelim

Aşağıda gördüğünüz resimde içinde A,B,C,D yazan vagonlarımız iki bölmeden oluşup, sağ taraftaki bölmeden diğer vagona bağlanmışlar. First Node dediğimiz vagon ise bizim ilk vagonumuz yani Head burayı gösterecek, Last Node ise son vagonumuz ki bunu ayrıca tutmaya hiç gerek yok çünkü bir düşünelim tüm vagonlar bir sonrakini gösterecek fakat Last Node son vagon olduğu için sonraki vagonu gösteren pointerımız NULL olacak.

Singly Linked List

Linked List yapısında mutlaka ilk vagonu elimizde tutmalı, son vagonun ise Next kısmının NULL olduğunu unutmamalıyız!

Devamı

Veri Yapıları - Struct Tanımlama ve Kullanımı

By Burak TUNGUT - 24.11.2012 - Kategori C / C++

2. Sınıf derslerimden olan Data Structures & Algorithm (Veri Yapıları ve Algoritmalar) dersinde öğrendiğim herşeyi bir yazı dizisi halinde getirmeye an itibari ile karar verdim. Tabi ki her ders için birer yazı yazmaktansa, öğrendiğim her bir kavramı kullanabileceğimiz diğer kavramlar ile birleştirerek sizlere sunacağım.

İlk derslerde öğrendiğim kavramları günümüz yüksek seviyeli dilleri (Java ve C#) ile karşılaştırınca aslında amaçsız bir iş içinde olduğumuzu düşünmüştüm. Çünkü bu dillerde rahat bir şekilde istediğimiz classları, içlerinde propertyler ve methodlar olacak şekilde rahatça yazabiliyor ve hata alsak bile kolayca düzeltebiliyoruz. Gel gelelim benzer yapıyı C++ da struct'lar ile yapmaya çalışıyor ve ne kadarda ilkel olduğunu görüyoruz. Aslında bu noktada düşündüğüm tek şey şöyle oldu ;

 

Yüksek seviyeli dillerde kolayca yazmamızı sağlayan mimarinin altında yatan gerçekler ve zoru gördükten sonra kolay herşeyin daha anlamlı gelmesi

Belki olaya olması gerektiğinden fazlaca iyi yönden baktık, ama en azından artık yapacağımız işi biraz tanıdık.

Lafı fazla uzattık gibi, artık konumuza ve hazırladığım ufak senaryoya başlayabiliriz.

C++ sonrasını tamamiyle unutalım

Evet tıpkı yukarıda dediğim gibi artık C# ve Java elimizde yok ve C++ da kullandığımız temel veri tipleri yani int, float, string vs.'den başka elimizde bir tip yok ancak bizim yazacağımız öğrenci programı içinse öğrenciler için kullanabileceğimiz bir veri tipine ihtiyacımız var bu arada farkındamısınız senaryomuzunda öğrenci programı olduğunu söylemiş bulundum :)

Temel olarakda bir öğrencinin numarasını ve aldığı puanı içinde tutacak bir yapıya ihtiyacımız var. Tıpkı yüksek seviye dillerde bir class yazarmış gibi aşağıdaki kodu aynen C++ da yazıyor ve uygulama içersinde kullanacağımız structımızı tanımlamış oluyoruz.

struct Ogrenci{
	int No;
	int Puan;
};

Burda dikkat etmemiz gereken en önemli şey ise structın tanımlanmasında bizden istenen syntax kuralına dikkat etmemiz olacaktır.

Devamı

Veri Yapıları - Pointerlara Giriş

By Burak TUNGUT - 21.11.2012 - Kategori C / C++

Veri yapıları konusunda ki ilk makalemde sizlerle daha önce değindiğimiz Pointerlara devam edeceğiz.
Pointer konusundan bir kez daha bahsederek bizler için önem ve kullanım yerlerine değiniyor olacağız.

Aslında yazılım literatüründe her ne kadar Türkçe kelimeler ile anlaşmak güç ve anlamsız olsa da işaretçi olarak adlandırdığımız Pointerları bir kez daha tanıyalım ve C# için daha önceki makalelerimde yer verdiğim bir kaç konu ile bağdaştıralım.

Pointer Kavramı

Pointer kavramının ne olduğuna gelirsek, aslında uygulama içersinde her ne kadar farketmesek de RAM ile ilgili bütün işlerimizde yer alan bu kavram en kısa şekilde değer olarak başka bir değişkenin adresini tutan değişkenler diyebiliriz.
Zaten pointerları diğer değişkenlerden ayırt eden en büyük özellik de budur. Yani değişkenler bir değer taşırken, pointerlar değere sahip olan herhangi bir değişkenin adresini değer olarak taşılar.

Daha iyi bir şekilde kavramak için küçük bir örnek yapalım,
{
       int burak = 50;
}
Yukarıdaki gibi bir kod bloğu ile burak adına sahip bir integer değişken tanımladık. Ram'da ki adresini tamamiyle atıyor ve aşağıdaki gibi bir görünüm çiziyorum,
 

Değer adı burak  
Adresi 253670  
İçeriği 50 ...

Yani stack memory üzerinde 253670 adresli bölgede 50 değeri tutuluyor.

Şimdi ise aynı değişkene pointer üzerinden nasıl ulaşabileceğimizi inceleyelim. Bunun için öncelikle bir pointer tanımlayalım ve içeriğine tanımladığımız değişkenin adresini atayalım.
{
       int burak = 50;
       int *ptr = &burak;
}
Hemen bir hatırlatma yapalım. Bir pointer tanımlamanın, değişken tanımlamadan tek farkı; atayacağımız ismin önünde * (Indirection) ekinin gelmesi. Dikkat etmemiz gereken en önemli nokta ise pointerın içine adresini atacağımız veri tipinin, pointer veri tipiyle aynı olması. Açıklayacak olursak, yukarıda burak değişkeni bir integer ve hiç şüphesiz bunu adresleyecek olan ptr adlı pointerda integer olmak zorundadır!
 

Peki Neden & (Ampersand) eki kullanıyoruz ?

C ve C++ da ve unsafe kod kullanımında herhangi bir değişkenin bellek üzerindeki adrese erişimimizi & (Ampersand) eki ile gerçekleştiririz. Yukarıdaki kod bloğunun devamında printf fonksiyonu ile burak ve &burak değerlerini yazdıracak olursanız, 50 ve bu değerin bellekteki adresinin ekrana yazıldığını görebilirsiniz.

Konumuz daha fazla dağılmadan devam edelim ve son kod bloğu ile Ram üzerinde ki görünümü simüle edelim,

 

Değer adı burak ptr  
Adresi 253670 253696  
İçeriği 50 253670 ...


Gördüğünüz üzere ptr adlı pointer değişkeninin içeriği yani aldığı değer, içeriği 50 olan burak adlı değişken ile aynı.
Yani artık adresini aldığımız bu değişkene direkt olmadan ulaşabiliriz.

Devamı
1
Facebook
Son Yorumlar