C ile Veri Yapıları ve Algoritmalar

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. Dizi ve özyinelemeden çıkan yollar doğrusal yapılara, ağaçlara, çizgelere ve sıralamaya 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ş ve Algoritma Analizi (1)	—	Yazılımın yaşam döngüsü, soyut veri tipinin C başlık dosyasıyla ifadesi ve asimptotik analiz.
Diziler ve Yapılar (2)	Giriş ve Algoritma Analizi	Dizi ADT'si ve dizi ile işaretçi ilişkisi; malloc ile dinamik diziler, yapılar.
Özyineleme, İkili Arama ve Geri İzleme (3)	Giriş ve Algoritma Analizi, Diziler ve Yapılar	Özyinelemeyi yığın çerçeveleriyle izlemek; sıralı dizide ikili arama, Hanoi ve permütasyon.
Bağlı Listeler (4)	Diziler ve Yapılar	Dizinin yetersiz kaldığı yerde malloc ve free ile kurulan düğümler.
Polinomlar ve Seyrek Matrisler (5)	Diziler ve Yapılar, Bağlı Listeler	Aynı ADT'nin iki gösterimi: katsayı ve terim dizileri, bağlı liste; seyrek matrisler.
Yığınlar (6)	Diziler ve Yapılar, Özyineleme, İkili Arama ve Geri İzleme, Bağlı Listeler	LIFO yapısı: dizi ve struct ile push ve pop; çağrı yığını özyinelemenin yığınıdır.
Kuyruklar (7)	Yığınlar	FIFO yapısı: doğrusal kuyruğun kayma sorunu dairesel kuyrukla çözülür.
Yığın ve Kuyruk Uygulamaları (8)	Yığınlar, Kuyruklar	Labirentte geri izleme, infix ifadeyi postfix'e çevirme ve değerlendirme.
Liste ADT ve Genelleştirilmiş Listeler (9)	Bağlı Listeler, Polinomlar ve Seyrek Matrisler	Liste ADT'sinin sözleşmesi; çok değişkenli polinomlar genelleştirilmiş listeye götürür.
Ağaçlar (10)	Özyineleme, İkili Arama ve Geri İzleme, Bağlı Listeler	İkili ağaç, dizi ve bağlı gösterim; gezinmeler özyinelemeyle yazılır.
Arama Ağaçları (11)	Özyineleme, İkili Arama ve Geri İzleme, Ağaçlar	Ağaca sıralama koşulu: ekleme ve arama ikili aramanın ağaçtaki karşılığıdır.
Kılavuzlu İkili Ağaçlar (12)	Ağaçlar, Arama Ağaçları	Boş kalan n+1 işaretçi kılavuza dönüşür: yığınsız kök ortada gezinme.
Öncelikli Kuyruk ve Heap (13)	Kuyruklar, Ağaçlar	Kuyruğun öncelikli biçimi; tam ikili ağacın dizide saklanmasıyla heap.
Hash Tabloları (14)	Diziler ve Yapılar, Bağlı Listeler	Doğrudan adreslemeden hash'e; açık adresleme dizi, zincirleme bağlı liste kullanır.
Çizgeler (15)	Bağlı Listeler, Kuyruklar, Öncelikli Kuyruk ve Heap	Komşuluk listesi bağlı listedir; BFS kuyrukla, DFS yığınla gezinir.
Kümeler ve Union-Find (16)	Ağaçlar	Ayrık kümeler ata dizisiyle ağaç olarak saklanır; ağırlıklı birleşim ve yol kısaltma.
Minimum Kapsayan Ağaçlar (17)	Öncelikli Kuyruk ve Heap, Çizgeler, Kümeler ve Union-Find	Açgözlü kapsayan ağaç: Kruskal union-find, Prim heap kullanır.
En Kısa Yol ve Aktivite Ağları (18)	Öncelikli Kuyruk ve Heap, Çizgeler	Dijkstra, Bellman-Ford ve Floyd-Warshall; AoV ve AoE ağlarında topolojik sıra ve kritik yol.
Temel Sıralama Algoritmaları (19)	Giriş ve Algoritma Analizi, Diziler ve Yapılar	İlk örnek olan seçimli sıralama genellenir: eklemeli ve kabarcık sıralaması, kararlılık.
İleri Sıralama Algoritmaları (20)	Özyineleme, İkili Arama ve Geri İzleme, Öncelikli Kuyruk ve Heap, Temel Sıralama Algoritmaları	Böl ve fethet ile hızlı ve birleştirme sıralaması; heap sıralaması ve basamağa göre sıralama.

Haritanın ana omurgası şöyle okunabilir: dizi ve işaretçi → bağlı yapı → ağaç → çizge. Her konu soyut veri tipinden çalışan bir C gerçeklemesine kadar götürülür; bunun iki aracı dizi ile malloc ve free üzerine kurulan bağlı listedir. Yığın ve kuyruk her iki gerçeklemeyle yazılır ve uygulamalarda birleşir. Özyineleme ağaçlara götürür; heap ve ayrık kümeler ağacın dizideki biçimleridir. Çizgeler bu yapıların hepsini birlikte kullanır: kapsayan ağaç için heap ve union-find, en kısa yol için öncelikli kuyruk. Sıralama ise ilk bölümdeki seçimli sıralamadan başlar ve son bölümde böl ve fethet ile heap'e dayanır.