Veri Yapıları #04 | Dairesel Liste ve Josephus: Sıcak Patateyi Kim Kazanır?

Eğitmen: Dr. Süleyman Burak ÇELİK

Veri Yapıları dersinin dördüncü videosu. Yedi kişi bir daire olmuş, elden ele sıcak bir patates dolaşıyor; iki kez el değiştirince elinde patates kalan oyundan çıkıyor. Son kalan kim? Bu oyunu tek bağlı dairesel listeyle birkaç satırda çözüyoruz. Dairesel listede son düğüm NULL yerine ilk düğümü gösterir. Listeyi tutmak için yalnızca son düğümün adresi yeter: ilk düğüm sonun sonrakidir, böylece iki uca da tek adımda ulaşılır. Tek düğümlü dairesel listede düğüm kendini gösterir; geçen derste hata olan durum burada tam istenen şey. Doğrusal listenin durma koşulu (p NULL olana kadar) burada hiç gerçekleşmez; bunu gerçekten çalıştırıp görüyoruz, sonra do-while ile tam bir tur dönüyoruz. Sona eklemenin üç, başa eklemenin iki atama olduğunu, silmek için bir önceki düğümde durulduğunu adım adım izliyoruz. Josephus programı 7 kişi ve 2 pasla 3, 6, 2, 7, 5 ve 1'i eliyor, 4 kazanıyor; kitaptaki örnek (5 kişi, 1 pas: 2, 4, 1, 5; kazanan 3) da aynı çıkıyor. Çözümün adım sayısı (N − 1)·(M + 1): bin kişide 2997, bir milyon kişide yaklaşık 3 milyon. Son olarak dairesel listenin işletim sistemlerindeki round robin zamanlamasıyla ilişkisini görüyoruz. Ekrandaki her çıktı, kodun gerçekten derlenip çalıştırılmasından geliyor. Bu derste: 1. Dairesel liste: son düğüm ilk düğümü gösterir; neden sonu tutarız 2. Tek düğümün kendini göstermesi ve do-while ile tam bir tur 3. Sona ve başa ekleme, bir önceki düğümde durarak silme 4. Josephus (sıcak patates) problemi: program ve kitabın örneği 5. Adım sayısı (N − 1)·(M + 1) ve round robin zamanlama Bölümler: 0:00 Sonu olmayan liste 0:15 Sıcak patates: kim kazanır? 0:44 Son düğüm ilk düğümü gösterir 1:15 Nerede dururuz? do-while 1:48 Sona ve başa eklemek 2:20 Bir önceki düğümde durarak silmek 2:46 Josephus programı 3:30 Bu çözüm ne kadar iş yapar? 4:01 Round robin: sırayla dönen işler 4:28 Bugünün dört kuralı 4:51 Sonraki ders: çift bağlı liste Kaynak kitap: Mark Allen Weiss — Data Structures and Algorithm Analysis in C++, 4. baskı (2014), §3.2.2 ve Alıştırma 3.6 (Josephus), 3.35 (dairesel bağlı liste). Konu sırası ve kavramlar kaynak kitaptan izlenir; programlar C ile özgün yazıldı, anlatım ve ekranlar özgündür. Hedef kitle: veri yapılarına başlayan mühendislik ve bilgisayar/yazılım öğrencileri. Ön koşul: temel C (struct, işaretçiler, malloc) ve bu serinin 3. dersi (bağlı liste).