Algoritmalar Ve Programlama Dersi 2. Ünite Sorularla Öğrenelim

C Dili ile programlamada bir dizi ile işlem yapabilmek için, diğer veri tiplerindeki değişkenlerde olduğu gibi, öncelikle dizinin tanımlanması gerekmektedir.

Dizilerin tanımlanmasındaki genel ifade şu bileşenlerden oluşur:

1.  dizi-tipi: Dizinin hangi tipteki verilerden oluşacağını gösterir (int, char, double,float vb. veri tipleri olabilir)
2. dizi-adı: Tanımlanan dizinin adını ifade eder.
3. dizi-uzunluğu: Köşeli parantez içerisinde belirtilen bu değer, dizinin uzunluğunu belirtir.

Satır ve sütunlardan oluşan tablolar şeklinde tanımlanabilen iki boyutlu diziler, çok boyutlu dizilerin en yalın halidir. M adet satır, N adet sütundan oluşan iki boyutlu bir dizi, toplam (m x n) elemana sahip olabilir. Örneğin 4 satır ve 3 sütundan oluşan iki boyutlu bir dizinin eleman sayısı (4*3)=12 olacaktır.

Bağlı liste (linked list), aynı türden nesnelerin doğrusal bir sırada ve birbirlerine bağlı şekilde saklandığı veri yapısıdır. Bağlı listedeki nesnelere düğüm (node) adı verilir ve düğümler birbirlerine bir sonraki düğümü işaret eden göstericiler (next pointer) aracılığıyla bağlanmışlardır. Ayrıca, bağlı listelerde listenin başlangıcını işaret eden bir baş gösterici (head pointer) de bulunur.

Bağlı listeleri oluşturan düğümler genellikle iki kısımdan meydana gelir. Düğümün ilk kısmında veri saklanırken, ikinci kısmında ise bir sonraki düğümün bilgisayar hafızasın- daki yeri saklanır

Veri yapısı olarak benzerlik gösteren dizilerin ve bağlı listelerin, birbirleriyle kıyaslandığında, çeşitli açılardan avantajları ve dezavantajları bulunmaktadır. Bağlı listelerin ve dizilerin çeşitli ölçütlere göre karşılaştırması aşağıda verilmiştir:

• Veri yapısı uzunluğu: Dizilerde veri yapısının uzunluğu sabittir, gerekli durumlarda dizi uzunluğu arttırılamaz veya azaltılamaz. Bağlı listelerde uzunluk dinamiktir, yeni nesneler eklenebilir, var olan nesneler silinebilir.

• Hafıza kullanımı: Bağlı listelerdeki her bir nesnenin göstericisi için, bilgisayar ha- fızasında yer ayrılması gerekir. Dizilerde böyle bir durum söz konusu değildir.

• Veri ekleme/silme maliyeti: Dizilerde ekleme ve çıkarma işlemleri, programlama açısından oldukça yüksek maliyetlidir. Bağlı listelerde ekleme veya çıkarma yapmak, dizilerdekine göre daha az maliyetli ve kolaydır.

• Verilere doğrudan erişim: Dizi elemanlarına indisler aracılığıyla doğrudan erişilebilir. Bağlı listelerde ise böyle bir durum söz konusu değildir. Bağlı listenin bir elemanına erişmek için o elemanın listede aranması ve bulunması gerekir.

Bağlı listelerin elemanları dolaşılırken ileriye doğru gitmek, geriye doğru hareket etmek ve listenin sonundan listenin başına erişmek mümkün olabilir. Belirtilen bu hareket kabiliyetleri, çeşitli türlerde bağlı listelerin ortaya çıkmasına neden olur. Bağlı listelerdeki üç tür aşağıda listelenmiştir:

1. Tek yönlü bağlı liste (Singly linked list)
2. Çift yönlü bağlı liste (Doubly linked list) 
3. Dairesel bağlı liste (Circular linked list)

Tek yönlü bağlı listelerde, liste düğümleri arasındaki gezinme hangi yönlere doğru gerçekleşir?

Tek yönlü bağlı listelerde, liste düğümleri arasındaki gezinme yalnızca ileriye doğru gerçekleşir. 

Çift yönlü bağlı listelerde, liste düğümleri arasında hem ileriye hem de geriye doğru gidilebilir. Çift yönlü bağlı listenin bir düğümü, bir sonraki düğümü işaret eden göstericinin (next pointer) yanı sıra, bir önceki düğümü işaret eden göstericiyi (previous pointer) de içerir.

Bir bağlı listenin son düğümünün bir sonraki düğümü işaret eden göstericisi (next poin- ter) listenin ilk düğümünü işaret ettiğinde liste dairesel hale gelmiş olur. Bağlı listelerin bu çeşidine dairesel bağlı liste denilmektedir.

Programlamada kuyruk (queue), verilerin doğrusal sırada tutulmasını sağlayan bir veri yapısıdır. Bir kuyruğun başı (front) ve sonu (rear) bulunur. Kuyruk yapısındaki temel işlemler olan ekleme (enqueue) son taraftan, çıkarma (dequeue) ise baş taraftan gerçekleştirilir. Dolayısıyla kuyruğa ilk giren eleman, kuyruktan ilk çıkan eleman olur. 

Yaşantımızdaki çeşitli aktivitelerde nesnelerin üst üste dizilmesi gerekir. Üniversite ye- mekhanesindeki tepsiler, restoran mutfağındaki tabaklar, elbise dolabı rafındaki kıyafetler, nesnelerin günlük yaşamda üst üste dizilmesi için gösterilebilecek basit örneklerdir. Bir üniversite yemekhanesindeki tepsilerden almak istediğimizde, temiz tepsilerin içerisinden en üstte olanı alırız. Temiz tepsiler biriktirilirken, yeni gelen tepsiler var olanların üstüne eklenir. Nesnelerin üst üste dizilimi, günlük hayatta olduğu gibi programlamada da var olan bir gereksinimdir. Bu ihtiyaç, yığın (stack) adı verilen veri yapıları ile karşılanır.

Yığın, verilerin doğrusal bir şekilde tutulduğu, ekleme ve çıkarma işlemlerinin en üst noktadan yapıldığı bir veri yapısıdır. Eklenen veri, yığının en üst noktasında saklanırken; çıkarılan veri de yığının en üst noktasından alınır. Yığının en üst noktasının takibi, yığının tepe noktası (top) aracılığıyla sağlanır

Programlamada, yığınlar üzerinde yapılan temel işlemler eleman ekleme (push), ele- man çıkarma (pop) ve en üstteki elemanı elde etmedir (peek). Pop işleminde en üstteki eleman yığından çıkarılırken, peek işleminde yalnızca bu elemanın değeri elde edilir, eleman yığından çıkarılmaz. Bu işlemlerin yanı sıra yığının doluluk kontrolü (isFull) ve yığının boşluk kontrolü (isEmpty) gibi yardımcı fonksiyonlar da kullanılabilir.

LIFO (Last-In First-Out): Programlamada yığınlar LIFO kuralı ile anılır. Bu ifade, “Son Giren İlk Çıkar” şeklinde tercüme edilebilir.