C++’da Bağlantılı Listelerin Türleri (Types of Linked Lists)

Veri yapıları kategorisine yazdığım önceki yazılardan birinde, bağlantılı listeleri (linked lists) anlatmıştık. Bu yazıda, bu listelerin farklı türlerini ele alacağız. Halkalı listeler, çift bağlantılı listeler (doubly linked lists) ve çok boyutlu bağlantılı listeler (multilists) türlerinin ne oldukları ve tanımları alttaki kodta main() fonksiyonunda yorum satırlarında açıklanmıştır. Ayrıca kod üzerinde doubly linked list (çift bağlantılı liste) örneği yapılmıştır. Kodu anasayfada çok yer kaplamaması için yazının devamına koydum, sorularınızı

sormaktan çekinmeyin.

#include <iostream>

using namespace std;

struct esya
{
    char isim[30];
    int sayi;
    struct esya *next;
    struct esya *previous;
};

struct ev
{
    esya *head;
    esya *tail;
    int elemanSayisi;
    void olustur();
    void ekle(esya *, int);
    void sirala();
};

void ev::olustur(){
    head = NULL; tail = NULL; // Başını ve sonunu NULL olarak atayalım.
    elemanSayisi = 0;
}

void ev::ekle(esya *oge,int sira){
    // Sıra eleman sayısını aşıyorsa hata bastır:
    if (elemanSayisi < sira){
        cout << "Hata: Listede bu sıra kadar eleman yok!" << endl;
        return;
    }

    if (sira == -1){ // Sona ekleme yapılacaksa direk atama şansı da olsun.
        sira = elemanSayisi+1;
    }

    esya *eklenecek = new esya; // Yeni hafıza ayrıldı.
    *eklenecek = *oge; // İçerik yeni ayrılan hafızaya kopyalandı.
    esya *dolas = head; // Gezinirken kullanacağımız değişken

    if ( head == NULL ){ // Eğer liste boşsa ilk öğe oluşturulsun.
        head = eklenecek; // Tek eleman olduğu için başı da
        tail = eklenecek; // sonu da aynı elemanda olacak.
        elemanSayisi++;
        return;
    }

    // İstenen konum en baş ya da en sonsa özel muamele uygulanacak:
    if ( sira == (elemanSayisi+1) ){ // Sona ekleme yapılacak demek ki.
        eklenecek->next = NULL; // Son eleman olduğunu belirledik.
        eklenecek->previous = tail;
        tail->next = eklenecek;
        tail = eklenecek;
        elemanSayisi++;
        return;
    }

    if ( sira == 1 ){ // En başa ekleyeceksek
        eklenecek->next = head; // İlk eleman olduğunu belirledik.
        head->previous = eklenecek;
        eklenecek->previous = NULL;
        head = eklenecek;
        elemanSayisi++;
    }

    for( int i = 1; i < sira; i++ ){
        dolas = dolas->next; // İstenen konuma kadar gel.
    }

    // Bağlara bakılırsa 4 aşama yapılması gerekiyor.
    (dolas->previous)->next = eklenecek;
    eklenecek->next = dolas->previous;
    eklenecek->next = dolas;
    dolas->previous = eklenecek;
    elemanSayisi++;
}

void ev::sirala(){
    esya *dolas = head;
    int sira = 0;
    while(dolas){
        sira++;
        cout << sira << ". " << dolas->isim << " - " << dolas->sayi << endl;
        dolas = dolas->next;
    }

}

int main(int argc, char const *argv[])
{
    /* İlk seçenek listeyi içi boş, fasulye bir düğümle başlatmak. */
    // Boş düğüm sayesinde head hiçbir zaman NULL olmaz ve özel birçok durumdan kurtulmuş oluruz.
    // Ayrıca ilk elemanı silmek için de özel bir kod gerekmemeye başlar.

    /* Halkalı Listeler */
    // En sondaki elemanın next işaretçisi NULL yerine ilk elemanı tutar.
    // Tanımlamalar değişmez ancak başı ve sonu neye göre belirlenir o sıkıntı olur.
    // Belirli bir konuma ekleme yapmak veya bir konumdan silmek de değişen işlemler arasına girer.
    // Head işaretçisi listenin sonunu göstermek zorundadır. head->next listenin ilk elemanını gösterir.
    // Bu sayede en başa ve en sona ekleme-çıkarma işlemleri basitleşir.

    /* Çift Bağlantılı Listeler (Doubly Linked Lists) */
    // Düğümler hem sonrakinin hem öncekinin (next ve previous) adresini tutarlar.
    // İşaretçiler sayesinde listede iki yönde de ilerlemek mümkün hale gelir.
    // Daha önceden yazılan tüm fonksiyonlarda değişiklik gerektirir.
    // Ortaya direnç gibi bir şekil çıkar.

    /* Çok Boyutlu Bağlantılı Listeler (Multilists) */
    // Çok boyutlu diziler gibi, bağlantılı listelerde de benzer bir uygulama yapılabilir.
    // Mesela masanın türlerine göre, çalışma masası, yemek masası, bilgisayar masası gibi
    // ayrımlar yapılacaksa, ana listede masa, sandalye gibi öğeler varken, bu türler her birinin
    // alt listeleri haline gelir. Bunu en basit anlamdaki linked list kullanarak yapabiliriz.

    ev Home; // Bir ev cinsinden yapı oluşturalım.
    Home.olustur(); // Yapıyı başlatacak fonksiyonu çağırdık.

    esya *refEsya = new esya; // Referans olması için bir tane oluşturuldu.

    int secim, knm;
    while (1){
        cout << "========\n1. Ekle\n2. Görüntüle\nYapmak istediğiniz işlem: ";
        cin >> secim;
        switch (secim){
            case 1:
                cout << "Eşyanın adı: ";
                cin >> refEsya->isim;
                cout << "Eşyanın miktarı: ";
                cin >> refEsya->sayi;
                cout << "Kaçıncı sıra? (Sona eklemek için -1): ";
                cin >> knm;
                Home.ekle(refEsya, knm);
                break;
            case 2:
                Home.sirala();
        }
    }

    return 0;
}

İyi çalışmalar.

 
comments powered by Disqus