KampüsCepteBir programın hızı ve bellek kullanımı, verinin nasıl düzenlendiğine ve üzerinde hangi adımların izlendiğine bağlıdır. Bu ünite temel veri yapılarını ve algoritma kavramını anlatır.
Veri yapısı nedir?
Veri yapısı, verilerin bellekte nasıl düzenleneceğini, saklanacağını ve onlara nasıl erişileceğini belirleyen yapıdır. Kütüphanedeki kitapların konu ve yazar sırasıyla dizilmesi gibi, veriyi belirli bir düzende tutarak eklemeyi, aramayı ve sıralamayı kolaylaştırır. Elemanları sıra hâlinde dizilen yapılara doğrusal (dizi, yığın, kuyruk, bağlı liste), dallanarak bağlanan yapılara doğrusal olmayan (ağaç, graf) denir.
Doğrusal veri yapıları
- Dizi (array): Aynı türden verilerin bellekte yan yana tutulduğu ve her elemana bir indis ile erişilen yapıdır. İndis genellikle 0'dan başlar; n elemanlı dizinin son indisi n − 1'dir. Elemana doğrudan erişim çok hızlıdır, ama araya ekleme ve silme için elemanlar kaydırılır.
- Yığın (stack): Elemanlar yalnızca tepeden eklenip çıkarılır; son giren ilk çıkar (LIFO). Üst üste konmuş tabaklar gibidir. İşlemleri push (ekle), pop (çıkar) ve top'tur (tepeyi göster). Geri al (Ctrl+Z), tarayıcıdaki geri düğmesi ve parantez denetimi yığınla yapılır.
- Kuyruk (queue): Elemanlar arkadan eklenir, önden çıkar; ilk giren ilk çıkar (FIFO). Banka sırası gibidir. Yazıcıya gönderilen belgeler ve çağrı merkezindeki aramalar kuyrukla yönetilir.
- Bağlı liste: Her düğüm hem veriyi hem de bir sonraki düğümün adresini tutar; son düğüm NULL gösterir. Tren vagonları gibidir; araya eleman eklemek için yalnızca bağlantılar değişir.
A, B, C sırasıyla eklenen elemanlar yığından C, B, A sırasıyla; kuyruktan ise A, B, C sırasıyla çıkar.
Doğrusal olmayan veri yapıları
- Ağaç: Elemanların üst–alt ilişkiyle bağlandığı hiyerarşik yapıdır. En üstteki düğüme kök, alt düğümü olmayanlara yaprak denir. Bilgisayardaki klasör yapısı ve soy ağacı birer ağaçtır.
- Graf: Düğümlerin kenarlarla serbestçe bağlandığı yapıdır; bir düğüme birden çok yoldan ulaşılabilir. Şehirler ve aralarındaki yollar, sosyal ağlar birer graftır.
Algoritma
Algoritma, bir problemi çözmek için izlenen, sırası belli ve sonlu sayıdaki adımlar dizisidir. Bir yemek tarifi ya da çay demleme talimatı da birer algoritmadır. İyi bir algoritma sıfır ya da daha fazla giriş alır, en az bir çıkış üretir, her adımı açık ve tek anlamlıdır, mutlaka sona erer ve gereksiz adım içermez. Algoritma bir programlama diline bağlı değildir; sözel olarak, sözde kodla (pseudo code) ya da akış şemasıyla gösterilebilir.
Akış şeması
- Oval: Başla / Bitir.
- Paralelkenar: Giriş / çıkış (veri okuma, sonuç yazdırma).
- Dikdörtgen: İşlem (hesaplama, atama).
- Eşkenar dörtgen (baklava): Karar; koşul sınanır, evet ve hayır yollarına ayrılır.
- Ok: Akış yönü.
Akış şemalarında üç temel yapı vardır: adımların sırayla yapıldığı sıralı yapı, koşula göre yol seçilen karar yapısı ve adımların koşul sağlandıkça tekrarlandığı döngü yapısı. Toplam bulunurken başlangıç değeri 0, faktöriyel gibi çarpım bulunurken 1 olmalıdır; aksi hâlde çarpım hep 0 çıkar.
Arama ve sıralama
- Doğrusal arama: Aranan değer dizinin başından itibaren tek tek karşılaştırılır. Dizinin sıralı olması gerekmez.
- İkili arama: Yalnızca sıralı dizilerde çalışır. Ortadaki elemanla karşılaştırılır; aranan küçükse sol, büyükse sağ yarıda devam edilir. Her adımda alan yarıya indiği için 1000 elemanlı bir dizide en fazla 10 adımda sonuca ulaşır.
- Kabarcık sıralama: Yan yana iki eleman karşılaştırılır, sıraları yanlışsa yer değiştirilir. Her geçişin sonunda en büyük eleman dizinin sonuna yerleşir. Örnek: [5, 3, 8, 1] üç geçişte [1, 3, 5, 8] olur.
Veri yapıları ve algoritmalar birlikte kullanılır: harfleri yığına ekleyip geri çıkarmak bir kelimeyi tersine çevirir (KİTAP → PATİK), yazıcıda ise ilk gönderilen belgenin ilk basılması için kuyruk kullanılır.