Veri Yapıları

Dersin Haritası

Bu sayfa dersin bütün bölümlerini tek bir haritada birleştirir. Her bölüm bir düğümdür; bir ok, sonraki konunun önceki konunun hangi fikrine dayandığını gösterir. Derse başlamadan önce okunursa konuların nereye gittiğini, ders sırasında okunursa bulunulan yeri gösterir.

Şekil 1: Dersin haritası. Oklar, bir konunun hangi konunun üzerine kurulduğunu gösterir. Diziden başlayan yol bağlı yapılara, ağaçlara ve çizgelere ayrılır.

Şekil 1 konular arasındaki bağları gösterir. Her düğüm bir bölümdür; bir ok, sonraki konunun öncekinin hangi fikrine dayandığını belirtir. Haritada yalnızca en yakın bağlar çizilmiştir; bir bölümün dayandığı bütün bölümler Tablo 1'dedir.

Tablo 1: Haritadaki bağlar.
Konu (bölüm)	Dayandığı konu	Bağ
Giriş (1)	—	Verinin bellekte temsili, ilkel ve referans tipler, soyut veri tipi; bütün yapılar bu dille anlatılır.
Algoritma Analizi (2)	Giriş	Bir yapıyı seçmek için işlemlerin maliyetini ölçmek gerekir: Büyük O, Omega ve Teta.
Diziler (3)	Algoritma Analizi	İlk yapı: bitişik bellek ve indisle O(1) erişim; ekleme ve silmenin bedeli analizle görülür.
Özyineleme (4)	Algoritma Analizi, Diziler	Problemi daha küçük örneklerine indirmek; çağrı yığını ve yineleme bağıntısıyla analiz.
Bağlı Listeler (5)	Diziler	Dizinin sabit boyu ve kaydırma maliyeti düğümlerle aşılır: başa ekleme O(1), rastgele erişim yok.
Liste ADT ve Java Koleksiyonları (6)	Diziler, Bağlı Listeler	Dizi ve bağlı liste aynı Liste ADT'sinin iki gerçeklemesidir; Java koleksiyonları ve Iterator.
Yığınlar (7)	Diziler, Bağlı Listeler	Yalnızca üstten erişilen liste: push ve pop dizi ya da bağlı listeyle O(1).
Kuyruklar ve Deque (8)	Diziler, Bağlı Listeler, Yığınlar	İki uçlu erişim: dairesel dizi ya da bağlı liste; iki yığınla kuyruk.
Ağaçlar (9)	Özyineleme, Bağlı Listeler	Düğümler artık birden çok çocuğa bağlanır; gezinmeler özyinelemeyle yazılır.
Arama Ağaçları (10)	Ağaçlar	Ağaca sıralama koşulu eklenir: arama, ekleme ve silme O(h); denge yüksekliği O(log n) tutar.
Öncelikli Kuyruklar ve Heap (11)	Kuyruklar ve Deque, Ağaçlar	Kuyruk ADT'sinin öncelikli biçimi; tam ikili ağacın dizide saklanmasıyla heap.
Eşlemeler ve Hash Tabloları (12)	Diziler, Liste ADT ve Java Koleksiyonları	Eşleme ADT'si; hash tablosu dizi kovaları ve zincirleme listeleriyle ortalama O(1).
Kümeler ve Ayrık Kümeler (13)	Arama Ağaçları, Eşlemeler ve Hash Tabloları	Küme, değeri olmayan eşlemedir: hash ve ağaç tabanlı gerçeklemeler; ayrık kümeler ağaçla.
Çizgeler (14)	Kuyruklar ve Deque, Ağaçlar, Öncelikli Kuyruklar ve Heap, Kümeler ve Ayrık Kümeler	Ağacın genellemesi: BFS kuyruk, Dijkstra ve Prim öncelikli kuyruk, Kruskal ayrık küme kullanır.

Haritanın ana omurgası şöyle okunabilir: analiz → dizi → bağlı yapı → ağaç → çizge. İlk dört bölüm bütün dersin aracıdır: her yapı bir soyut veri tipi olarak tanımlanır ve işlemleri Büyük O ile ölçülür. Dizi ile bağlı liste, sonraki bütün yapıların iki temel gerçekleme biçimidir; yığın, kuyruk ve liste ADT'si bu ikisinin üzerine kurulur. Özyineleme ağaçlara götürür; arama ağaçları ile hash tabloları eşleme ve kümelerin iki gerçeklemesidir. Çizgeler son bölümde öncekilerin hepsini kullanır: gezinme kuyruğu ve yığını, öncelikli kuyruk ve ayrık kümeler.