Data Structures and Algorithms with C

Undergraduate, Giresun University, Computer Engineering, 2025

data structures and algorithms with c This course studies data structures and algorithms through their memory representation and their implementation in C. Each topic is developed from the abstract data type to a working C99/C11 implementation with pointers, dynamic memory, and structures, together with its complexity analysis. The course covers arrays and structures, linked lists, stacks, queues, lists, trees, priority queues and heaps, hash tables, search trees, graphs, sets and union-find, as well as recursion, backtracking, spanning trees, shortest paths, and sorting algorithms.

Ders Kitabı

📕 C ile Veri Yapıları ve Algoritmalar (PDF, 21 MB)

Başlangıç Kaynakları

Kısım I: Temeller

Bölüm 1: Giriş ve Algoritma Analizi

Bir yazılımın gereksinimlerden doğrulamaya uzanan yaşam döngüsü, algoritma kavramı ve soyut veri tiplerinin C’de başlık dosyalarıyla nasıl ifade edildiği ele alınır. Seçimli sıralama, C kodu ve SWAP makrosuyla birlikte ilk örnek olarak işlenir. Programların başarımı alan ve zaman karmaşıklığı üzerinden incelenir; adım sayma, en iyi, ortalama ve en kötü durum ile O, Ω ve Θ gösterimleri örneklerle açıklanır. Sihirli kare problemi ve sıralama ile doğrusal aramanın çalışma süresinin ölçülmesi, kuramsal analizi uygulamayla buluşturur.

Bölüm 2: Diziler ve Yapılar

Dizi soyut veri tipi ve C’de dizilerle işaretçiler arasındaki yakın ilişki konunun başlangıç noktasıdır. malloc ile dinamik diziler ve büyüyen dizilerin amortize maliyeti, iki ve daha çok boyutlu dizilerde satır ve sütun öncelikli adres hesabı işlenir. Alt üçgen ve kuşak matrislerin tek boyutlu dizilerde yer kazandıran biçimde saklanması gösterilir. Konu struct, union ve hizalama, karakter dizisi olarak dizgiler ve matris çarpımıyla tamamlanır.

Bölüm 3: Özyineleme, İkili Arama ve Geri İzleme

Özyinelemeli algoritmalar yığın çerçeveleri üzerinden izlenir; özyineleme ile döngü arasındaki ilişki ve kuyruk özyinelemesi açıklanır. İkili aramanın yinelemeli ve özyinelemeli sürümleri ile logaritmik karmaşıklığı adım adım gösterilir. Hanoi kuleleri ve permütasyon üretimi özyinelemeli düşünmenin klasik örnekleri olarak çözümlenir. Geri izleme ise satisfiability, n-vezir, alt küme üretimi ve Warnsdorff kuralıyla at gezisi problemleri üzerinde işlenir.

Kısım II: Doğrusal Yapılar

Bölüm 4: Bağlı Listeler

Dizinin yetersiz kaldığı durumlardan yola çıkılarak düğümlerden oluşan bağlı liste malloc ve free ile kurulur. Tek yönlü bağlı listede gezinme, başa, sona, araya ve sıralı ekleme, silme ve arama yordamları adım adım izlenir. Listeyi ters çevirme, iki listeyi birleştirme, orta düğümü bulma ve Floyd’un döngü tespiti algoritması klasik yordamlar arasında yer alır. Dairesel ve çift yönlü bağlı listeler, başlık düğümü ve serbest düğümleri yeniden kullanan kullanılabilir düğüm listesi de incelenir.

Bölüm 5: Polinomlar ve Seyrek Matrisler

Polinom soyut veri tipi, katsayı dizisi ve terim dizisi gösterimleriyle tanıtılır; padd yordamıyla polinom toplama ve analizi yapılır. Polinomların bağlı listeyle gösterimi ve bu gösterimle polinom çarpımı ele alınır. Seyrek matrisler üçlü tablo biçiminde saklanır; transpose ve hızlı fast_transpose yordamları ile seyrek matris çarpımı maliyetleriyle birlikte işlenir. CSR gösterimi ve bağlı seyrek matris de seçenek olarak tanıtılır.

Bölüm 6: Yığınlar

Son giren ilk çıkar (LIFO) ilkesiyle çalışan yığın, soyut veri tipi ve kullanım alanlarıyla tanıtılır. Dizi üzerinde push ve pop işlemleri, taşma ve alt taşma durumları ile küresel dizi yerine struct kullanan daha düzenli bir gerçekleme C koduyla gösterilir. Bağlı liste ile yığın gerçeklemesi dizi tabanlı sürümle karşılaştırılır. Fonksiyon çağrılarının çağrı yığınındaki karşılığı, tek dizide birden çok yığın tutma yöntemi ve hangi çıkış sıralarının mümkün olduğu da incelenir.

Bölüm 7: Kuyruklar

İlk giren ilk çıkar (FIFO) ilkesiyle çalışan kuyruk, soyut veri tipi ve kullanım alanlarıyla ele alınır. Dizi ile doğrusal kuyruğun kayma sorunu, modüler aritmetiğe dayanan dairesel kuyrukla çözülür; kuyruğun dolu ya da boş olduğunu ayırt etmenin yolları karşılaştırılır. Bağlı kuyruk gerçeklemesi ve dizi tabanlı sürümle farkları işlenir. Deque, çoklu kuyruk, iş zamanlama benzetimi ve iki yığınla kuyruk kurma konuyu tamamlar.

Bölüm 8: Yığın ve Kuyruk Uygulamaları

Yığın ve kuyruğun gerçek problemlerdeki kullanımı iki büyük uygulama üzerinden incelenir. Labirent problemi hareket tablosu ve yığın yardımıyla geri izlenerek çözülür ve karmaşıklığı değerlendirilir. İşleç önceliği ve birleşme kuralları ışığında infix, postfix ve prefix gösterimler tanıtılır; postfix ifadelerin hesaplanması ve isp ile icp öncelikleri kullanılarak infix ifadelerin postfix biçime çevrilmesi adım adım gösterilir. Prefix hesaplama, parantez denetimi ve diğer uygulamalar da ele alınır.

Bölüm 9: Liste ADT ve Genelleştirilmiş Listeler

Liste soyut veri tipinin sözleşmesi ile dizi ve bağlı liste gerçeklemeleri karşılaştırılır. Öğeleri hem atom hem de alt liste olabilen genelleştirilmiş listeler, çok değişkenli polinom örneği ve bellek görünümüyle tanıtılır. Kopyalama, eşitlik, gezinme, derinlik ve ters çevirme yordamları özyinelemeli olarak yazılır ve adım adım izlenir. Ağacın listeyle kurulması, paylaşılan listeler, referans sayma ve çöp toplama fikri de incelenir.

Kısım III: Ağaçlar

Bölüm 10: Ağaçlar

Ağaç terminolojisi ve derinlik tanımlarından sonra ikili ağaç, tam ve mükemmel ağaç kavramları ile düğüm sayısı ilişkileri ele alınır. İkili ağacın dizi ve bağlı gösterimleri karşılaştırılır; genel ağacın ikili ağaca dönüştürülmesi gösterilir. Kök önde, kök ortada ve kök sonda gezinmeler özyinelemeli yordamlarla ve ifade ağacı örneğiyle işlenir, ardından yığın kullanan yinelemeli sürümlere geçilir. Kuyrukla düzey düzey gezinme, ağaç kopyalama, eşitlik denetimi ve çocukların yer değiştirmesi de incelenir.

Bölüm 11: Arama Ağaçları

İkili arama ağacının tanımı ve ekleme sırasının ağacın biçimine etkisi örneklerle gösterilir. Ekleme, yinelemeli ve özyinelemeli arama ile derinlik hesaplama yordamları C koduyla yazılır; özyinelemeli aramadaki tuzaklar ve ek parametre kullanımı tartışılır. Silme işleminin durumları ve farklı silme yöntemleri adım adım işlenir. Dengesizliğin maliyeti AVL ağaçları, tek ve çift döndürmelerle giderilir; kırmızı-siyah ağaçlar ve B-ağaçları da kısaca tanıtılır.

Bölüm 12: Kılavuzlu İkili Ağaçlar

n düğümlü bir ikili ağaçta boş kalan n+1 NULL işaretçinin kılavuz olarak değerlendirilmesi fikri Perlis ve Thornton’a dayanır. Kılavuzların kurma kuralları, kılavuz bayrakları ve başlık düğümü örneklerle açıklanır. Kök ortada ardılın bulunması ve yığın kullanmadan gezinme adım adım izlenir; Morris gezinmesi de tanıtılır. Kılavuzlu ağaca sağa ve sola düğüm ekleme durumları ayrıntılı olarak işlenir.

Bölüm 13: Öncelikli Kuyruk ve Heap

Öncelikli kuyruk kavramı, gereksinimi ve soyut veri tipi tanıtılır. Tam ikili ağacın dizide saklanmasına dayanan maksimum ve minimum heap yapısı, ikili arama ağacından farklarıyla birlikte açıklanır. Yukarı kaydırmayla ekleme ve aşağı kaydırmayla silme yordamları C koduyla yazılır ve adım adım izlenir; heap diğer yapılarla sayısal örnekler üzerinden karşılaştırılır. Aşağıdan yukarı heap kurmanın neden O(n) sürdüğü, d-ary heap ve uygulamalar da ele alınır.

Kısım IV: Hash, Çizgeler ve Kümeler

Bölüm 14: Hash Tabloları

Doğrudan adreslemeden yola çıkılarak hash fikri ve sözlük soyut veri tipi tanıtılır. Bölme, çarpma, katlama ve orta-kare yöntemleri ile dizgiler için hash fonksiyonları incelenir. Çakışmaların çözümü için doğrusal ve karesel yoklama ile çift hash kullanan açık adresleme ve zincirleme C koduyla işlenir. Açık adreslemede silindi işaretiyle silme, yük faktörü ve yeniden boyutlandırma da ele alınır; iki yaklaşım karşılaştırılır.

Bölüm 15: Çizgeler

Königsberg köprüleri probleminden başlanarak çizge tanımı, komşuluk, yol, bağlantılılık ve derece kavramları açıklanır. Komşuluk matrisi, komşuluk listesi, sıralı dizi, ortogonal gösterim ve çok bağlı liste olmak üzere beş gerçekleme karşılaştırılır; ağırlıklı çizgelerin gösterimine de değinilir. Derinlik öncelikli (DFS) ve genişlik öncelikli (BFS) gezinme C koduyla yazılır ve adım adım izlenir. Bağlantılı bileşenlerin bulunması, döngü tespiti ve iki parçalı çizgeler de incelenir.

Bölüm 16: Kümeler ve Union-Find

Ayrık kümeler ile birleşim ve küme bulma işlemleri, ata dizisine dayanan gerçeklemeyle tanıtılır. Basit yordamların kötü bir işlem dizisinde O(n²) maliyete ulaştığı gösterilir. Ağırlıklı kural ağacın derinliğini sınırlar, azaltma kuralı ise bulma sırasında yolu kısaltır; her iki iyileştirme de adım adım izlenir. Tarjan–van Leeuwen analizi, Ackermann fonksiyonu ve tersi ile bileşen sayma ve Kruskal algoritması gibi uygulamalar da ele alınır.

Bölüm 17: Minimum Kapsayan Ağaçlar

Kapsayan ağaç kavramı, ağaç ve ağaç dışı kenarlar ile kapsayan ağaçların özellikleri üzerinden tanıtılır; eşbiçimlilik ve düzlemsellik konusuna da değinilir. Minimum maliyetli kapsayan ağaç problemi açgözlü yaklaşımla ele alınır. Kruskal algoritması kenarların sıralanması ve union-find ile, Prim algoritması ise ağacı tek düğümden büyüterek kodlanır ve adım adım izlenir; Prim’in heap ile gerçeklemesi de gösterilir. Sollin (Borůvka) algoritması, minimum kapsayan ağaç ile en kısa yol ağacı arasındaki fark ve Kruskal ile Prim’in karşılaştırılması konuyu tamamlar.

Bölüm 18: En Kısa Yol ve Aktivite Ağları

Tek kaynaklı en kısa yol problemi kaba kuvvet analiziyle başlar ve açgözlü fikre dayanan Dijkstra algoritmasıyla çözülür; önceller dizisiyle yolun kendisi de bulunur. Negatif kenarlar için Bellman-Ford, tüm düğüm çiftleri için Floyd-Warshall algoritması adım adım işlenir. AoV ağlarında topolojik sıra, sayaçlı başlıklar kullanan bir yordamla bulunur. AoE ağlarında en erken ve en geç zamanlar, bolluklar ve kritik yol hesaplanır.

Kısım V: Sıralama

Bölüm 19: Temel Sıralama Algoritmaları

Sıralama problemi, kararlılık ve yerinde sıralama kavramlarıyla birlikte ortak C makroları üzerinden tanıtılır. Seçimli, eklemeli ve kabarcık sıralaması adım adım izlenir ve analiz edilir; eklemeli sıralamanın ortalama durumu ters çift sayısıyla hesaplanır. Doğrusal zamanlı saymalı sıralama, Shell sıralaması ve kova sıralaması da işlenir. Karar ağacı yardımıyla karşılaştırmaya dayalı sıralamanın alt sınırı kanıtlanır ve algoritmaların hangi durumda uygun olduğu tartışılır.

Bölüm 20: İleri Sıralama Algoritmaları

Hızlı sıralama bölümleme değişmezi üzerinden anlatılır; en kötü, en iyi ve ortalama durum analizleri yapılır. Özyinelemesiz sürüm, medyan-3 ve küçük alt diziler için eşik kullanan iyileştirilmiş hızlı sıralama ile C kitaplığındaki qsort ve hibrit sıralamalar ele alınır. Birleştirme sıralamasının dizi ve bağlı liste sürümleri, heap sıralaması ve çok anahtarlı verilerde basamağa göre sıralama adım adım izlenir ve analiz edilir. Algoritmaların hangi durumda tercih edileceği karşılaştırmalı olarak tartışılır.