Algoritmalar · Ünite 2
Veri Yapıları: Dizi, Bağlı Liste, Yığın, Kuyruk, Ağaç, Çizge
10 soruluk deneme testine geç ↓1. Veri yapısı nedir?
Veri, bir olgunun, kavramın ya da komutun iletilmeye, yorumlanmaya ve işlenmeye uygun biçimdeki gösterimi. Veri yapısı ise bu veriyi bellekte saklamak, geri çağırmak ve işlemek için kurulan düzen. Kısacası programcının kafasındaki bilgiyle bilgisayarın belleği arasındaki köprü.
Neden gerekli? Not defteri örneği
Bir sınıfın adlarını, matematik ve Türkçe notlarını tutmak istiyorsun. Her öğrenci için ayrı değişken açarsan (isim, mat, tur, isim2, mat2, tur2…) öğrenci sayısı arttıkça işin içinden çıkılmaz; bir öğrencinin adının yanına başkasının notu yazılabilir.
Daha iyisi: üç dizi açmak. Her dizi bir tablonun sütunu, indis de satır numarası gibi düşünülür. İlk öğrencinin bilgileri hep aynı indiste durur: ogrenciler[0], mat[0], tur[0].
| İndis | Öğrenciler | Matematik | Türkçe |
|---|---|---|---|
| 0 | Öğrenci 1 | 76 | 90 |
| 1 | Öğrenci 2 | 20 | 45 |
| 2 | Öğrenci 3 | 80 | 67 |
Gerçek hayatta nerede?
- →Kuyruk (queue): işletim sistemi ve diskler gelen istekleri sırayla tutar (aygıt kuyruğu); medya oynatıcının çalma listesi.
- →Yığın (stack): kelime işlemcide Geri al / Yinele, tarayıcıda ziyaret edilen adres geçmişi.
- →Ağaç (tree): NTFS gibi dosya sistemleri klasör–dosya hiyerarşisini ağaçla tutar.
Veri yapıları üzerindeki altı temel işlem
| İşlem | Ne yapar? |
|---|---|
| Gezinme (traversing) | Yapıdaki elemanları tek tek dolaşıp çıktı olarak verir. |
| Arama (searching) | Bir değerin yapıda olup olmadığını bulur. |
| Ekleme (insertion) | İstenen noktaya eleman ekler. |
| Silme (deletion) | İstenen elemanı çıkarır. |
| Sıralama (sorting) | Elemanları bir ölçüte göre dizer. |
| Birleştirme (merging) | Elemanları (ya da iki yapıyı) birleştirir. |
Hangi yapıyı seçeceğin, bu işlemlerden hangisini ne sıklıkla yapacağına bağlı. Doğru seçim hem kod yazmayı kolaylaştırır hem de zaman ve alan karmaşıklığını düşürür.
2. Sınıflandırma: basit ve karmaşık
- →Basit (ilkel) veri türleri: dilde hazır gelir, işlemci doğrudan işler, tek bir değer tutar. Boolean, integer, float, char, pointer. Kapladıkları bellek sabittir; bu yüzden «en büyük / en küçük değer» sınırları vardır.
- →Karmaşık (türetilmiş) veri yapıları: basit türlerden kurulur, birden fazla değer tutar, boyutu büyüyebilir. Elemanlar arasındaki ilişkiye göre ikiye ayrılır:
- →Doğrusal: elemanlar sıra hâlinde, her biri bir öncekine ve bir sonrakine bağlı → dizi, yığın, kuyruk, bağlı liste.
- →Doğrusal olmayan: bağlantı sayısı birden fazla ve asimetrik → ağaç, çizge (graf).
3. Basit veri türleri
| Tür | Ne tutar? | Örnek | Tutamaz |
|---|---|---|---|
| Boolean | Mantıksal doğru / yanlış | true, false | — |
| Integer | Pozitif ya da negatif tam sayı | 0, 10, -33000 | 0,2 |
| Float | Ondalıklı (kayar noktalı) sayı | 3.14, -2, 9 | — |
| Char | Tek bir karakter (harf, rakam, işaret) | a, A, 9 | 12 (iki karakter) |
| Pointer (gösterge) | Başka bir değişkenin bellek adresi | 0x1F4 | — |
- →Boolean: «A, B'ye eşit mi?» gibi karşılaştırmaların sonucu boolean'dır. Örnek: mezunMu değişkeni false ise öğrenciyi ders seçme ekranına yönlendir.
- →Sayılar: diller belleği verimli kullanmak için farklı boyutlarda tür sunar. C#'ta tam sayı için Byte (8 bit) ve Integer, ondalıklı için Float (32 bit) ve Double (64 bit). C#'ta Float toplamda yaklaşık 7 anlamlı basamak tutar (Double yaklaşık 15–16).
- →Char: eski ASCII 7 bit kullanır → 128 karakter, Türkçe ş, ç, ö yok. Unicode neredeyse tüm dillerin karakterlerini kapsar. Yaygın kodlaması UTF-8'de İngilizce harfler yine 1 bayt, ş, ç, ö gibi harfler 2 bayt, bazı karakterler 4 bayta kadar yer kaplar.
- →Pointer: bir adresi saklar. O adresteki değere ulaşmaya göstergeyi çözümleme (dereferencing) denir. Metin gezinme, başvuru çizelgeleri ve ağaç üzerindeki döngüleri hızlandırır.
Başvuru çizelgesi (lookup table): ağır hesapların (ör. trigonometrik değerler) girdilerini ve sonuçlarını önceden tutan dizi. Hesaplamak yerine tablodan okunur.
4. Doğrusal karmaşık yapılar
Dizi (array)
Aynı türdeki verileri bitişik bellek hücrelerinde tutar; her elemana eşit yer ayrılır (int için 4 bayt). Bu sayede herhangi bir elemanın adresi doğrudan hesaplanır, diğerlerine bakmaya gerek kalmaz. Buna rastgele erişim denir.
adres(i) = ilk elemanın adresi + eleman boyutu × (i − ilk indis) matNot[2] → 100 + 4 × (2 − 0) = 108
- →Artıları: indisle anında erişim; arama ve sıralama kolay.
- →Eksileri: yalnızca tek tür veri; boyutu sabit. Fazlası gerekirse sorun, azı kullanılırsa bellek israfı. Araya ekleme ya da silmede sonraki bütün elemanlar kaydırılır.
Bağlı liste (linked list)
Birbirine bağlı düğümlerden oluşur. Düğümler bellekte dağınık durur; her düğümde iki parça var: veri ve bir sonraki düğümün adresini tutan gösterge. Son düğümün göstergesi NULL'dır; listenin bittiği böyle anlaşılır.
| Dizi | Bağlı liste | |
|---|---|---|
| Bellek | Bitişik | Dağınık, her yer kullanılabilir |
| Boyut | Sabit, baştan belirlenir | Çalışırken büyüyüp küçülür |
| Erişim | İndisle doğrudan (rastgele) | Baştan sırayla: 4. eleman için önce ilk 3'ü |
| Araya ekleme / silme | Zor: elemanlar kaydırılır | Kolay: yalnızca adresler değişir |
| Ek yük | Sadece veri | Veri + gösterge, daha fazla yer |
Yığın (stack) ve kuyruk (queue)
- →Yığın, LIFO (Son Giren İlk Çıkar): kitap yığını gibi; ekleme de çıkarma da tepeden. Tepedeki elemanı gösteren tek bir gösterge tutulur. 90, 60, 76, 82 sırasıyla girdiyse önce 82 çıkar, en son 90.
- →Kuyruk, FIFO (İlk Giren İlk Çıkar): bilet kuyruğu gibi; ekleme arka uçtan, silme ön uçtan.
| Yığın kullanılan yerler | Kuyruk kullanılan yerler |
|---|---|
| Geri al / Yinele | Disk ve yazıcı işlerinin sırası |
| Tarayıcı adres geçmişi | İşletim sisteminde kesmeler |
| Metni tersine çevirme | Sistemler arası veri aktarımı takibi |
| Özyinelemeli fonksiyonlar, labirentte gerileme (backtracking) | Medya oynatıcı çalma listesi |
5. Doğrusal olmayan yapılar
Burada bir elemanın ikiden fazla bağlantısı olabilir; hiyerarşi, çoklu bağlantı ve ağırlıklı bağlantı kurulabilir. Doğrusal yapı tek bir döngüyle gezilirken, burada alt dalları gezmek için yeni döngüler gerekebilir.
Ağaç (tree)
Hiyerarşik veriyi tutar: düğümler sıralı değil katman katman dizilir. Her düğüm, verisinin yanında çocuklarına giden bağlantıları da taşır. Her düğümün en fazla iki çocuğu olan ağaca ikili ağaç (binary tree) denir.
| Terim | Anlamı | Şekilde |
|---|---|---|
| Kök (root) | En üstteki tek düğüm | A |
| Kenar (edge) | İki düğümü bağlayan çizgi | A–B |
| Yol (path) | Kenarlarla bağlı düğüm serisi; kökten her düğüme tek bir yol var | A, B, E, J |
| Ebeveyn / çocuk | Aşağı doğru kenarı olan düğüm / o kenarın ucundaki düğüm | B, E'nin ebeveyni |
| Kardeş (sibling) | Aynı ebeveynin çocukları | H ve I |
| Yaprak (leaf) | Hiç çocuğu olmayan uç düğüm | H, I, F, G, J |
| Alt ağaç (subtree) | Bir düğüm ve altındakiler | D, H, I |
| Katman (level) | Kök 0. katman, çocukları 1. katman… | B, C → 1 |
| Derinlik (depth) | Kökten o düğüme kadar kenar sayısı | J → 3 |
| Yükseklik (height) | Düğümden yaprağa kadar kenar sayısı | B → J: 2 |
Kullanım: dosya sistemleri, sözlükler, yönlendirme tabloları. Kelime işlemcilerin yazım denetimi de Trie adlı bir ağaç kullanır.
Çizge (graph)
Düğümler (vertex) ve onları bağlayan kenarlardan (edge) oluşur; G(V, E) diye yazılır, V düğüm kümesi, E kenar kümesi. Ağaçtan farkı: ebeveyn–çocuk ilişkisi ve katman yok, iki düğüm arasında birden fazla yol olabilir, döngü kurulabilir. Bir kenarla bağlı iki düğüme bitişik denir.
- →Yönsüz çizge: (A, B) kenarı iki yönde de gezilebilir.
- →Yönlü çizge: kenarın yönü belli; yalnızca giriş düğümünden (initial) uç düğüme (terminal) gidilir.
- →Ağırlıklı çizge: kenarlara değer verilir. Şehirler düğüm, yollar kenar, uzunluklar ağırlık → A'dan B'ye en kısa yol aranır.
- →Temel işlemler: düğüm ekleme, kenar ekleme, düğümleri gezme.
Hepsi bir arada
| Yapı | Tür | Tek cümlede |
|---|---|---|
| Dizi | Doğrusal, statik | Bitişik, aynı tür, indisle anında erişim. |
| Bağlı liste | Doğrusal, dinamik | Dağınık düğümler, her biri sonrakini gösterir. |
| Yığın | Doğrusal, dinamik | LIFO: son giren ilk çıkar. |
| Kuyruk | Doğrusal, dinamik | FIFO: ilk giren ilk çıkar. |
| Ağaç | Doğrusal olmayan | Tek kök, katmanlar, her düğüme tek yol. |
| Çizge | Doğrusal olmayan | Hiyerarşi yok, çok yol, yönlü / ağırlıklı olabilir. |
Kendini test et!
Cevabı görmek için soruya dokun.
1.Başlangıç adresi 200 olan ve her elemanı 4 bayt olan bir dizide dizi[5] hangi adrestedir? (İlk indis 0)
✓ 200 + 4 × 5 = 220.
2.16 bitlik bir değişken kaç farklı değer tutabilir?
✓ 2^16 = 65.536.
3.Yığına sırayla 3, 8, 5 eklendi, sonra iki kez çıkarma yapıldı. Yığında ne kaldı?
✓ Önce 5, sonra 8 çıkar; yığında yalnızca 3 kalır.
4.Aynı sayılar bir kuyruğa eklenip iki kez çıkarma yapılsaydı ne kalırdı?
✓ Önce 3, sonra 8 çıkar; kuyrukta 5 kalır.
5.Bağlı listede 4. elemana neden doğrudan ulaşılamaz?
✓ Düğümler bellekte dağınık; adresi ancak bir önceki düğümün göstergesinden öğrenilir. Bu yüzden baştan sırayla gidilir.
6.Ağaç ile çizge arasındaki temel fark nedir?
✓ Ağaçta tek kök, ebeveyn–çocuk hiyerarşisi ve her düğüme tek yol var. Çizgede hiyerarşi yok; iki düğüm arasında birden fazla yol olabilir.
Deneme testi
Sınavda çıkabilecek türden 10 soru. Bir şık seç; doğru cevap ve açıklaması hemen çıkar.
1.Aşağıdakilerden hangisi basit (ilkel) veri türü değildir?
2.Eleman eklemenin ve çıkarmanın aynı uçtan yapıldığı, «Son Giren İlk Çıkar» ilkesiyle çalışan yapı hangisidir?
3.Bir yazıcıya gönderilen belgelerin geliş sırasına göre basılması için en uygun veri yapısı hangisidir?
4.7 bitlik ASCII standardında kaç farklı karakter tanımlanabilir?
5.Başlangıç adresi 100 olan, her elemanı 4 bayt olan bir dizide (ilk indis 0) matNot[3] elemanının adresi kaçtır?
6.Bağlı listelerin dizilere göre avantajı aşağıdakilerden hangisidir?
7.Ağaç veri yapısında hiç çocuğu olmayan uç düğümlere ne ad verilir?
8.Bir ağaçta kök düğümden bir düğüme giden yol üzerindeki kenar sayısına ne denir?
9.Şehirler arasındaki en kısa yolu bulmak için yolların uzunluklarının kenarlara değer olarak verildiği yapı hangisidir?
10.Bellekteki başka bir değişkenin adresini saklayan veri türü ve o adresteki değere ulaşma işlemi hangi seçenekte doğru eşleştirilmiştir?
Bu not ders kitabının yerine geçmez; konu kendi cümlelerimizle, yapay zekâ desteğiyle özetlendi.