Bağlantılı Listeler (Linked Lists)

Veri yapıları için temel niteliğinde olan bir başka konuysa bağlantılı listeler. Aslında veri yapılarının temeli desem daha doğru olacak. Çünkü diğer veri yapılarını elde ederken kullanılan en temel yapılardan birisi. Oldukça güçlü bir yönetim sağlıyor bize. Öğeleri bellek adreslerini kullanarak birbirine bağlıyoruz ve işlemlerimizi gerçekleştiriyoruz. Dinamik bellek yönetimi, işaretçiler (pointer) gibi konuların önemi de burda boy göstermeye başlıyor. Kod üzerinde çalışırken slaytlardan yeterli açıklamayı yazdığıma inanıyorum. main() fonksiyonu altındaki açıklama satırları sanırım doğru yer olacak.

Bu kodta sınıftaki öğrencilerin bilgilerini tutan bir linked list hazırlayacağız. Her öğrenci, listenin başka bir elemanı olacak. Bu sayede, bir sınıfa gelen giden öğrencileri de rahatlıkla tutmuş olacağız. Şimdi kodu

görelim.

#include <iostream>
#include <string.h>
#define ISIM_UZUNLUGU 20

using namespace std;

struct ogrenci
{
    int okulNum;
    char isim[ISIM_UZUNLUGU];
    float ortalama;
    struct ogrenci *next; // Sonrakini bu tutacak.
};

typedef ogrenci kayit; // Öğrenci düğümleri kayit değişken türü olarak belirlendi.

struct sinif
{
    kayit *baslangic; // Sınıfın ilk öğrencisinin kaydı bu olacak.
    unsigned char ogrenciSayisi; // Kaç öğrenci var?
    void olustur();
    void ekle(kayit *); // Sınıfa öğrenci ekler.
    void sil(int); // Sınıftan öğrenci siler.
    void ara(kayit *); // Sınıfta öğrenci arar. İsme ya da numaraya Göre.
    void listele();
};

void sinif::olustur(){
    baslangic = NULL; // Hiç öğrenci yok.
    ogrenciSayisi = 0; // Öğrenci sayısı da 0 olarak tutulsun.
}

void sinif::ekle(kayit *eklenecek){
    kayit *dolas = baslangic;
    kayit *ekle = new kayit; // Yeni bir bellek alanı oluşturuldu.
    *ekle = *eklenecek; // Tüm içeriğin yeni ayrılan yere kopyası oluşturuldu.
    ekle->next = NULL; // Son eleman yapıldı.
    if (baslangic == NULL){ // Boşsa, yani sınıfın ilk öğrencisi ekleniyorsa
        baslangic = ekle; // Kopyalanan struct ile listeyi başlat.
        ogrenciSayisi = 1; // Öğrenci sayısını 1 yaparak başla.
        return;
    }

    for(int i = 0; i < ogrenciSayisi - 1 ; i++){
        cout << dolas << endl;
        dolas = dolas->next; // Son elemana kadar git.
    }

    dolas->next = ekle; // Yeni oluşturulan bellek alanına son eleman yollandı.
    ogrenciSayisi++; // 1 öğrenci arttı.
}

void sinif::ara(kayit *aranan){
    kayit *dolas; // Aramayı yaparken kullanacağımız geçici değişken.
    dolas = baslangic; // Başlangıç değerinden başlayalım.

    while( dolas ){
        // İsimler YA DA okul numaraları tutarsa:
        if ( ( strcmp(aranan->isim, dolas->isim) == 0 ) || ( aranan->okulNum == dolas->okulNum ) ){
            // Bilgileri yazdır.
            cout << "Bulunan öğrenci: " << dolas->okulNum << " - ";
            cout << dolas->isim << endl << "Ortalama: " << dolas->ortalama << endl;
            return; // Fonksiyondan çık.
        }

        dolas = dolas->next; // Sonraki elemana geç.
    }
    // Bulunamazsa:
    cout << "Hata: Kayıt Bulunamadı.";
}

void sinif::sil(int silinecek){
    kayit *dolas, *onceki = NULL;
    dolas = baslangic;
    while (dolas){
        if ( dolas->okulNum == silinecek ){ // bulunursa
            cout << dolas->okulNum << " numaralı öğrenci " << dolas->isim << " siliniyor..." << endl;
            if (onceki == NULL){ // Önceki henüz oluşturulamadıysa ilk öğrencidir diyoruz.
                cout << "Sınıf listesindeki ilk öğrenci silindi.";
                onceki = dolas;
                dolas = dolas->next; // İlk eleman yerine ikinciyi koy.
                delete onceki; // Hafızadan temizlemeyi de yaptık.
                ogrenciSayisi--; // Öğrenci sayısını 1 azalt.
                return;
            }
            onceki->next = dolas->next;
            delete dolas;
            cout << "Kayıt başarıyla silindi." << endl;
            ogrenciSayisi--;
            return;
        }
        onceki = dolas; // Önceki elemanın next değerini değiştirmemiz gerekecek.
        dolas = dolas->next; // Bir sonraki elemana geçelim.
    }
    // Bulunamazsa:
    cout << "Hata: Kayıt bulunamadı. Silinme işlemi iptal edildi." << endl;
}

void sinif::listele(){
    kayit *dolas = baslangic;
    while ( dolas ){
        // Kaydı yazdır.
        cout << dolas->okulNum << " - " << dolas->isim << " - " << dolas->ortalama << endl;
        dolas = dolas->next; // İlerle
    }

}

int main(int argc, char const *argv[])
{
    /* Linked list için temel fonksiyonlar: print,makeEmpty,find,insert,remove */

    // C'deki gibi tanımlamada dizi boyutu bilinmek zorunda. new ile yapsak da
    // boyutu bir şekilde belirmemiz gerekiyor. Aşırı fazla ya da dar alanlar kullanılır.

    // Lineer fonksiyonlarda baştan sona gidilerek işlem yapılır.
    // Normal dizilerde silme ve belirli konuma ekleme çok fazla işlem gerektirir.
    // Bu da yavaş çalışmaya neden olur. (Hepsi kaydırılmak zorundadır.)
    // Resimlerde detay var.

    // Linked list bağlantılı birimlerle oluşturulur. Bu birimlere düğüm(node) denir.
    // Tüm alanlar seçime bağlıdır ancak "next" pointerı sonraki elemanı göstermelidir.
    // Son elemanın next işaretçisine NULL değeri verilir.
    // Dolayısıyla elemanlar hafızada ard arda tutulmaz, kafaya göre tutulur.

    // Linked list'e ulaşabilmek için head pointerını bilmemiz gerekiyor. Çünkü bu
    // listenin başını belirtiyor.

    // Linked list, en temel ama en çok kullanılan veri yapısı türüdür.

    kayit *head; // Kaydın başlangıcını burda tutalım. Normal başlangıç böyle.
    head = new kayit; // BUNU YAPMAYI UNUTMA NULL POINTER E ATAMA DENER HATA ALIRSIN!!!!
    head->next = NULL;
    // Sınıftaki öğrencileri tutan bir sistem denersek...

    struct sinif A;
    A.olustur(); // Başlatma fonksiyonu çağırılarak head'e NULL atanmış oldu.

    int islem;
    while(1){
        cout << "Yapmak istediğiniz işlem\n1. Ekle\n2. Ara\n3. Listele\n4. Sil: ";
        cin >> islem;
        switch (islem){
            case 1:
                cout << "Öğrenci adı:";
                cin >> head->isim;
                cout << "Öğrenci numarası: ";
                cin >> head->okulNum;
                cout << "Ortalama: ";
                cin >> head->ortalama;
                A.ekle(head);
                break;
            case 2:
                cout << "Aranacak öğrenci adı: ";
                cin >> head->isim;
                cout << "ya da numarası: ";
                cin >> head->okulNum;
                A.ara(head);
                break;
            case 3:
                A.listele();
                break;
            case 4:
                cout << "Kaydı silinecek öğrencinin okul numarası: ";
                cin >> head->okulNum;
                A.sil(head->okulNum);
                break;
        }
    }

    return 0;
}

Sorularınız olursa her daim burdan sorabilirsiniz.

 
comments powered by Disqus