Algoritmalar Ve Programlama Dersi 2. Ünite Özet

Diziler

Dizi (array), aynı tipteki verilerin tek bir değişken altında tutulmasını sağlayan veri yapısıdır. Sabit bir değere sahip olan dizinin uzunluğu, dizi oluşturulurken belirlenir. Bir dizide bulunan verilerin her biri, o dizinin bir elemanı olarak adlandırılır. Dizinin elemanlarına erişim indis (index) adı verilen sayısal değerler aracılığıyla sağlanır. İndislerin numaralandırılması 0 ile başlar, dizinin uzunluğunun 1 eksiğine kadar ardışık olarak artarak devam eder.

Dizilerin Tanımlanması: 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

[dizi-uzunluğu] şeklindedir.

dizi-tipi: Dizinin hangi tipteki verilerden oluşacağını gösterir (int, char, double, float vb. veri tipleri olabilir).

dizi-adı: Tanımlanan dizinin adını ifade eder.

dizi-uzunluğu: Köşeli parantez içerisinde belirtilen bu değer, dizinin uzunluğunu belirtir.

Dizilere Değer Atama: Bir diziyi veri tipi, isim ve kapasite belirterek tanımladığımızda, bilgisayar hafızasında dizi için bir yer ayrılır; fakat dizi elemanlarına bir değer ataması yapılmaz.

Dizilere değer atamak için dizi tanımlaması ile birlikte veya tanımlamadan sonra kodlanan çeşitli komutlar vardır. Dizinin elemanları üzerinde gezinecek döngüler aracılığıyla dizi elemanları sıfırlanabilir, bir veri kaynağından (kullanıcı, metin dosyası, veri tabanı vb.) alınan değerler dizinin elemanlarına atanabilir, dizi elemanlarının değerleri programcı tarafından kod içerisinde belirtilebilir. Bu noktada önemli olan husus, programcının ihtiyacı doğrultusunda en doğru yöntemin uygulanmasıdır.

Bir dizinin elemanlarına değer atama işlemi, dizinin tanımlanmasıyla birlikte yapılırken dizinin boyutu belirtilmeyebilir.

Çok Boyutlu Diziler: Programlamada tek boyutlu dizilerin yanı sıra çok boyutlu diziler de oluşturulabilmektedir. Çok boyutlu dizilerin en yaygın olanları iki boyutlu ve üç boyutlu dizilerdir

İki Boyutlu Diziler: 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 (mxn) elemana sahip olabilir.(S:20, Şekil 2.3)

İki boyutlu dizilerin elemanlarına değer atarken, her iki boyuttaki indisler üzerinde dolaşılmalıdır. Bu gereksinim için iç içe geçmiş iki adet for dögüsü kuruabilir.

Üç Boyutlu Diziler: Üç boyutlu diziler, iki boyutlu dizilerin katmanlar halinde bir araya gelmesiyle oluşur. Üç boyutlu bir diziyi "iki boyutlu dizilerin dizisi" olarak tanımlamak mümkündür. Boyut uzunlukları sırasıyla a, b, c olan üç boyutlu bir dizinin sahip olacağı toplam eleman sayısı a *b *c kadar olur.

Üç boyutlu dizilerde dizi tanımlama ve elemanlara değer atama işlemleri, iki boyutlu dizilerdeki işlemlere benzerlik gösterir. Üç boyutlu dizilerin elemanları gezilirken, iç içe geçmiş üç adet for döngüsü kurulabilir.

Bağlı Listeler

Bağlı liste (linkedlist), 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ındaki yeri saklanır.

Bağlı Listeler ile Dizilerin Karşılaştırması: 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 hafı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ı Liste Türleri: 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) Tek yönlü bağlı listelerde, liste düğümleri arasındaki gezinme yalnızca ileriye doğru gerçekleşir. (S:22, Şekil 2.4)
2.  Çiftyönlü bağlı liste (Doubly linked list) Ç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. (S:23, Tablo 2.5)
3. Dairesel bağlı liste (Circular linked list) Bir bağlı listenin son düğümünün bir sonraki düğümü işaret eden göstericisi (nextpointer) 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 (S:23, Tablo 2.6). Gerek tek yönlü gerek çift yönlü bağlı listelerin dairesel hale getirilmesi mümkündür. Bazı kaynaklarda, dairesel bağlı listeler, kendi içlerinde tek yönlü veya çift yönlü olarak ikiye ayrılmaktadır.

Bağlı Listelerde Temel İşlemler Bağlı listelerde listeye yeni eleman ekleme, listeden eleman çıkarma, listedeki toplam eleman sayısını bulma, listenin elemanlarını dolaşma, listede eleman arama, listenin ilk veya son elemanını bulma gibi çeşitli işlemler yapılabilir.

Düğüm Yapısını Oluşturma: Bağlı listenin elemanlarını temsil etmek için bir düğüm yapısı oluşturulmalıdır. Bu yapıda düğümde saklanacak veri (data) ve bir sonraki düğümün göstericisi (next pointer) yer alır

Listeye Eleman Ekleme: Bağlı listelerde listenin başına, sonuna veya herhangi bir bölgesine eleman eklemek mümkündür. Ekleme işleminde, eklenecek düğüm için malloc fonksiyonu ile hafızada yer açılır.

Listeden Eleman Çıkarma (Deletion): Bağlı listelerde listenin başından, sonundan veya herhangi bir bölgesinden eleman çıkarılabilir. Çıkarma işleminde çıkarılacak düğüm, free fonksiyonu ile hafızadan silinir. Çıkarma işlemi listenin ara bir bölgesinden yapılacaksa, öncelikle çıkarılacak düğüm liste içerisinde bulunmalı, düğüm bulunduktan sonra çıkarma işlemi gerçekleştirilmelidir.

Listeyi Gezinme (Traversal): Bağlı listenin elemanlarını gezinmek, listenin başından sonuna kadar gitmek demektir. Gezinme işlemi, listenin son elemana ulaşılıncaya kadar, yani bir sonraki düğümü işaret eden göstericisi (next pointer) NULL olan eleman bulunana kadar devam eder. Listenin elemanları gezinilirken, listede eleman arama veya elemanları ekrana yazdırma gibi işlemler de yapılabilir.

Kuyruklar

Günlük hayatta sıraya girerek oluşturduğumuz kuyruk mantığı, programlamada da yer almaktadır. 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. Kuyruk mantığının bir veri yapısı olarak programlanmasında kullanılan iki temel yöntem aşağıda açıklanmıştır.

Dizi ile Kuyruk Uygulaması: Kuyruk veri yapısını programlarken bir diziden faydalanılabilir. Bu yöntemde, verileri tutacak bir diziye, kuyruğun başını takip edecek bir tamsayıya, kuyruğun sonunu takip edecek bir tam sayıya ve kuyruktaki mevcut eleman sayısını gösterecek bir tam sayıya ihtiyaç duyulur. Kuyruk veri yapısının tam sayı tipinde değerleri saklayacağını varsayarsak programda gerekli olan değişkenleri aşağıdaki gibi listeleyebiliriz:

• int queue[N]: Kuyruktaki elemanları tutacak N uzunluğunda tamsayı dizisi
• int front: Kuyruğun başını gösteren indis
• int rear: Kuyruğun sonunu gösteren indis
• int count: Kuyruktaki eleman sayısı

Ekleme ve çıkarma işlemlerinde önemli bir ayrıntı, queue dizisinde dairesel bir yapı kurulmasıdır. Eklemede rear değişkeni, çıkarmada ise front değişkeni dizinin eleman sayısına eşit olursa, ilgili değişken 0 değerine atanır. Böylelikle dizide dairesel bir yapı kurulur ve programın dizi indislerinden bağımsız, kesintisiz olarak çalışması sağlanır.

Bağlı Liste ile Kuyruk Uygulaması: Kuyruk yapısını programlamak için bir bağlı listeden de faydalanılabilir. Bu yöntemde bağlı listenin elemanlarını oluşturacak bir veri yapısına ve kuyruğun başını ve sonunu takip edecek göstericilere ihtiyaç duyulur.

Bağlı liste kullanımı ile kuyruk uygulamasında tam sayı tipinde değerlerin saklanacağını varsayarsak, ihtiyaç duyduğumuz değişkenleri aşağıdaki gibi sıralayabiliriz:

• struct Node: Bağlı listeyi oluşturacak elemanlar için veri yapısı
• struct Node*front: Kuyruğun başını ifade eden Node gösterici
• struct Node*rear: Kuyruğun sonunu ifade eden Node gösterici

Yığınlar

Stack adını verdiğimiz 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 veride yığının en üst noktasından alınır.

Programlamada yığınlar LFO (Last-In First-Out) kuralı ile anılır. Bu ifade, “son giren ilk çıkar” şeklinde tercüme edilebilir.

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), eleman çı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

Yığın mantığının bir veri yapısı olarak programlanmasında kullanılan ili temel yöntem aşağıda açıklanmıştır.

Dizi ile Yığın Uygulaması: Yığın veri yapısını programlamada bir diziden faydalanılabilir. Bu yöntemde verileri tutacak bir diziye ve yığının tepe noktasını takip edecek bir tam sayıya ihtiyaç vardır.

Yığın veri yapısının tam sayı tipinde değerleri saklayacağını varsayarsak, programda gerekli olan değişkenleri aşağıdaki gibi listeleyebiliriz.

• nt stack[N]: Yığındaki elemanları tutacak N uzunluğunda tamsayı dizisi
• nt top: Yığının tepe noktasını gösteren indis

Bağlı Liste ile Yığın Uygulaması: Yığın yapısını programlamak için bir bağlı listeden de faydalanılabilir. Bu yöntemde bağlı listenin elemanlarını oluşturacak bir veri yapısına ve yığının tepe noktasını takip edecek bir göstericiye ihtiyaç duyulur.