Sakarya University Data Structure Homework 1
Veri Yapıları 1. Ödev Raporu
Ödevi geliştirmeye derste işlenilen circular doubly linked list ve array listi baz alarak başladım. İstenilen formatta random veri oluşturup yazma ve okuma kısımlarını çabuk hallettim. Bu kısımlarda zorunlu olarak kütüphanesini kullandım. Bundan sonraki kısımda ilk defa bir veri yapısı yazdığım için oldukça zorlandım. Veri yapısı içine veri yapısı koyma ve aradaki bağlantıyı yapmak için uzun süre uğraştım. Bu tarz problemlerde genelde anlamlı bir hata mesajı vermiyordu. Bu yüzden debug için birçok yere cout yazarak problemin kaynağına inmeye çalıştım. Edindiğim bilgilere göre deneysel yaklaşıp farklı yöntemlerle problemleri çözmeyi denedim. Sonuçta en performanslı ve pratik gelen ve dökümanla uyuşan yolu uyguladım. Bazı problemleri çözmem baya vakit aldı. Bir hafta boyunca günün büyük bir kısmında bu ödevle uğraştım. Bu süreçte konuyu daha iyi anladım. Program şu şekilde. MainList diye bir veri yapısı var. Aslında bu veri yapısı CircularDoublyLinkedList’in pointerlarını tutan bir ArrayList. CircularDoublyLinkedList de Node’lardan oluşuyor. Nodeların prev ve next adında, başka bir Node a işaret eden pointerları var. Aynı zamanda girilen veriyi tutmayı sağlayacak int türünde data değişkeni var. Bir de nodelar arası gezinmemize yarayan Iterator’muz var.
CircularDoublyLinkedList çoklu ekleme yada silme esnasında performans kaybı yaşamamak için bu fonksiyonlara parametre olarak iterator alıyor. Iterator ekleme yada silme fonksiyonlarının çağıran fonksiyonda kademeli olarak arttırılarak, eklenecek her eleman için ListeOrta nın gösterdiği Node a dönmek yerine, sadece next yada preve ötelenmiş oluyor. Ayrıca bu sayede her liste üzerinde gezinme için sadece bir iterator oluşturulması yeterli oluyor. Bu fonksiyonların standart fonksiyonlarından tek farkı iteratoru dışarıdan almaları. preve doğru ötelenmesi ise nexte ötelenen fonkisyonda prev ve next pointerlarının yer değiştirmesi ile oluyor. Dizi olarak alınan verilerin veri yapısına eklenmesi AddMultiple fonksiyonuyla gerçekleşiyor. Bu fonksiyonda dizinin yanında dizi boyutunun ayrıca gönderilmesinin sebebi program.cpp içinde her satırın eleman sayısına göre dinamik dizi oluşturulması. Bu yüzden dizi boyutunu söyleyen standart yöntemler işe yaramıyor. Bu sebeple çözümü döngü içinde satır eleman sayısını tutan int i fonksiyona parametre olarak göndermekte buldum. Add multiple fonksiyonun diziyi nasıl istenilen şekilde nodelara atadığına gelirsek, öncelikte ortadaki elemanı atıyor. Sonra okumaya devam (boyut-1)/2 edip sola doğru dolduruyor. Ama ilk elemanı atadığı ve 1 den başlaması gerektiği için (boyut+1)/2 defa sola ekliyor. Sonra kaldığı yerden devam edip sola attığıadet kadar kalan elemanları sağa atıyor. Orta atama işlemi iteratorun başta bulunduğu node’a (yani ListeOrta’nın gösterdiği node) değerleri atarken, prev ve next e yapılan eklemeler node’un atanacağı yöne göre bir gerisinden yapılıyor. CircularDoublyLinkedList ilk oluşturulduğu zaman için boş bir ListeOrta node u oluşturuluyor.Bundan dolayı ilk atama yapılırken yeni node oluşturulup bir ileri eklenmek yerine, veriler bu node’a atanıyor.
CircularDoublyLinkedList’in içinde static Capraz() fonksiyonu var. Bu fonkisyon prametre olarak çaprazlanmak istenen iki CircularDoublyLinkedList’in pointerini alıyor. Bu listelerin boyut bilgileri değişkenlere kaydediliyor. İki yazım için 2 farklı for döngüsü bulunuyor. Ayrıca bu döngülerin içinde 2 ayrı senaryo var. Küçük sayıda olan dizinin boyutuna ulaşana kadar yapılacaklar ve büyük sayıda olan dizi ile küçük sayıda olan dizi arasında olan değerler için yapılacak olan. Küçük dizinin kapsadığı elemanlar için sadece data değerleri yer değiştiriyor. Ama küçük eleman sayılı listenin boyutundan büyük değerlerde küçük boyutlu listeye ekleme, büyük boyutlu listeye kaldırma yapmak gerektiği için farklı işlemler uygulanıyor. Bu işlemler de 2 senaryoya ayrılıyor. Birisi büyük liste orta değeri içeren listenin eleman sayısının küçük liste orta değeri içeren listenin eleman sayısından küçük olması. 2.si ise tam tersi. Bu hangi yöne ekleme yapılacağını belirliyor. İşlem yön bağımsız şekilde şöyle gerçekleşiyor. Kaldırılacak değeri kaydet. Kaldırılacak değeri kaldır. Kaydedilen değeri diğer listeye ekle. Bu işlem sırasında büyük sayılı dizide remove yapılacak konumu gösteren iterator ötelenmemeli. Çünkü kendisinden sonraki elemanı kaldırıyor. Insert de ise ekledikten sonra öteleme işlemi yapılmalı. Tüm bu işlemler bitince en son ödevde istenilen formatta ekrana yazdırılır.
MainList genel olarak klasik bir ArrayList. Ama findMax(),findMin() ve Caprazla() fonksiyonları ile standart arraylistlerden ayrılıyor. findMin() ve findMax() fonkların çalışma mantığı şöyle. Tüm dizilerin orta elemanlarını sırayla birbiriyle karşılaştır. Büyük yada küçük olan değerin bulunduğu diziyi gösteren pointeri kaydet. Daha büyük bir değer bulursa aynısını yap. Tüm elemanlar içinde gezinince de dizinin pointerini dön.
Caprazla() methodu içinde ise bu fonklar çağırlıp CircularDoublyLinkedList lere atanır. Bu listler de CircularDoublyLinkedList classı içinde static olarak bulunan capraz fonkuna parametre olarak gönderillir.
Progarm.cs içinde yorum satırında Sayilar.txt generator bulunmakta. İsteğe bağlı olarak, istenilen parametrelerle aktive edilebilir. Sayilar.txt okuma işlemi işe su şekilde gerçekleşir.
getline() ile satırlar arası gezilir. Önce her satın eleman sayısı tespit edilir, sonra bu sayıyla la dinamik dizi oluşturulup satırdaki tüm elemanlar diziye ayrılak ve stirng int dönüşümü yapılarak atanır. Sonra bu dizi, her döngüde oluşturulan ve satırdaki tüm elemanları tutacak olan CircularDoublyLinkedList in AddMultiple methoduna, elaman sayısı bilgisi ile gönderilir. Sonra da ArrayList formunda olan MainList’in add methoduna CircularDoublyLinkedList gönderilerek Mainliste eklenmiş olur.