Bağlı Liste(Linked List) Yapısı

Programlama dillerinde birden çok veriyi tutmak için genellikle dizileri kullanırız. Ancak dizileri kullanmak için verimizin boyutunu bilmemiz gerekir. Eğer bilmiyorsak ya da belirlediğimiz değerin üzerine çıkmak istiyorsak sıkıntı yaşarız. Yaşayacağımız bir diğer sıkıntı ise elimizdeki veri setinin arasına bir değer girmek istersek ortaya çıkar. Örneğin 500 elemanlı bir dizinin 300. elemanına dışarıdan başka bir değer girersek 300. elemandan sonraki değerleri birer kaydırmamız gerekir. İşte tüm bunları aşmak için bağlı liste(linked list) kullanabiliriz.

Bağlantılı liste kullanmanın avantaj ve dezavantajları;

  • Dinamik boyuta sahip oluruz
  • Araya eleman eklerken fazla maliyet oluşturmaz

 

  • Rastgele erişim yoktur
  • Pointer için fazladan alan kullanırız.

 

Linked list temel işlemlerimiz

  • Ekle
  • Sil
  • Ara
  • Bul
  • Yok et

  • Her bir elemanımıza düğüm(node) denir.
  • Bağlanmış düğümler serisine bağlantılı liste denir.
  • Her düğümde veri ve işaretçi bulunur.
  • Baş; ilk düğüme olan işaretçidir.
  • Son düğüm NULL işaret eder.

Şimdi implemente edelim

Öncelikle 2 ana sınıfımız olacak. Bunlar Node ve List

Şimdi de InsertNode fonksiyonumuzu yazalım. Kabaca algoritması;

  • index’inci elemanı bul
  • Yeni düğüm için hafızada yer ayır
  • Yeni düğüm kendisinden sonrasını gösterecek
  • Yeni düğümden önceki düğüm yeni düğümü gösterecek

Yukarıdaki işlemleri yaparken 2 farklı durumla karşılaşırız.

  • İlk düğüm olarak ekleme
  • Ortaya ve sona ekleme
FindNode fonskiyonumuz

  • Listede x verisini ara
  • Böyle bir düğüm varsa pozisyonunu dön yoksa 0 dön
DeleteNode fonksiyonu

  • Silinecek düğümü bul
  • Bulunan düğümü hafızadan sil
  • Düğümden önceki pointer düğümden sonraki pointeri göstersin.

Ekleme işleminde olduğu gibi 2 özel durumumuz var.

  • İlk düğümü silme
  • Ortadaki veya sonraki düğümü silme
Listedeki elemanları ve eleman sayısını yazdırma
Listeyi silme
 

Örnek işlemler

Projeyi buradan indirebilirsiniz

İkili Ağaçlar(Binary Tree)

Öncelikle bazı terimlerden bahsetmek istiyorum.

bmn9m

Kök- Yukarıdaki resimde görüldüğü gibi ağaç yapımızda tüm elemanlar aslında tek bir yere bağlı. Buna kök diyoruz.

Çocuk ve ebeveyn- Kök hariç her düğümün bir ebeveyni vardır.

Yaprak-Çocuğu olmaya düğümlere denir. 3-7-10 gibi

Kardeş-Ebeveyni aynı olan düğümlerdir.

İkili Ağaçların özellikleri

  • Hiçbir düğümün ikiden fazla çocuğu olamaz.
  • Ortalama bir ağacın derinliği(kökten düğüme olan yolun uzunluğu) N’den küçüktür. En kötü durumda N-1 olur.

 

Ağaç Gezme

Önce kök gezme(pre-order traversar)

  • Kökteki veriyi yaz
  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz

preorder

 Çıktı: ++a*bc*+*defg

Sonra kök gezme(post-order traversar)

  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz
  • Kökteki veriyi yaz

Çıktı: abc*+de*f+g*+

İç kök gezme(in-order traversar)

  • Sol altağaçtaki veriyi iteratif olarak yaz
  • Kökteki veriyi yaz
  • Sağ altağaçtaki veriyi iteratif olarak yaz

Çıktı: a+b*c+d*e+f*g

Ayrıca iç kök gezme işlemi ile sayıları da sıralamış oluruz.

 

 

Çıktı:

screenshot

Radix Sort Algoritması


Radiks sort algoritması, 1887 yılında Herman Hollerith’in geliştirdiği “tabulating machine” için kullandığı yönteme dayanır.

  • Yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir.
  • Algoritma O(n) zaman karmaşıklığına sahiptir.
  • Alan maliyeti yüksektir.
  • Çok fazla miktarda sayı sıralanacaksa yönetimi zordur.
  • İki farklı şekilde kullanılabilir. En anlamlı basamağa göre(most significant digit) sıralama ve en anlamsız basamağa göre(least significant digit) sıralama.

Örnek vermek gerekirse;

156,38,147,159,254,300,29,79 sayılarını hep birlikte sıralayalım

1. adımda tüm sayılarımızın aynı sayıda haneden oluşması gerekir. Bunun için iki basamaklı sayılarımızın başına 0 yazıyoruz.

156,038,147,159,254,300,029,079

2. adımda sıralamamıza başlıyoruz .(ben en değersiz basamağa göre sıralama yapacağım) birler basamağındaki sayıların değerlerine göre sıralamaya başlıyorum.

300,254,156,147,38,159,029,079

3. adımda onlar basamağına göre sıralamamızı yapıyoruz.

300,029,038,147,245,156,159,079

4.adımda yüzler basamağına göre sıralamamızı yapıyoruz.

029,038,079,147,156,159,254,300

 

radix_sort

Çıktı:

radix_sort2

 

Yararlandığım kaynaklar:

http://www.geeksforgeeks.org/radix-sort/

https://en.wikipedia.org/wiki/Radix_sort