Bağlı Yapılar

Önceki ders bir belleği kimin bırakacağını ölçtü. Bu kurs farklı bir eksenle başlıyor: bir düğümü değiştirdiğinde bu değişikliği kimin göreceği. Aynı bellek bloğuna iki farklı işaretçi tutulduğunda, birinden yapılan bir değişiklik ötekinden de görünür — kaynak bunu söylemez, çünkü iki değişkenin bildirimi de aynıdır (struct Dugum *). Bağlı liste bu paylaşımın en açık örneğidir: bir sonraki düğüme giden alan bir işaretçi taşır ve o işaretçiyi kim tutuyorsa aynı düğümü görür.

Bu ders bağlı listeyi ve ikili arama ağacını sıfırdan kurup dört sınıftan ortak’ı ve kopya‘yı aynı yapı üzerinde karşılaştırıyor: bir düğüme takma adla erişip değiştirmek paylaşılan bir görünürlük üretir (ortak); listenin tamamını yeni düğümlerle çoğaltmak bu paylaşımı keser (kopya). Önceki kursun (**C’de Bellek ve İşaretçiler**) sorduğu “bu düğümü kim bırakacak” sorusu burada da geçerli — ağacı bıraktığımızda hâlâ o sözleşmeye uyuyoruz — ama bu dersin ölçtüğü eksen ayrı: sahiplik değil, görünürlük.

Bağlı Liste: Ekleme, Dolaşma, Bırakma

Liste tek yönlü ve her ekleme başa yapılıyor. liste_toplam bütün düğümleri dolaşıp değerlerini topluyor, liste_serbest her düğümü bırakmadan önce bir sonrakini saklıyor. liste_sig_kopyala yeni bir düğüm ayırmıyor, gelen başı olduğu gibi döndürüyor; bu yüzden döndürdüğü liste orijinaliyle aynı düğümleri paylaşıyor. liste_derin_kopyala ise her düğüm için yeni bir ayırma yapıp değeri kopyalıyor; döndürdüğü liste bağımsız bir bellek bloğu zincirine sahip.

// dugum.h — tek yonlu bagli liste ve temel islemler
#ifndef DUGUM_H
#define DUGUM_H

struct Dugum {
    int deger;
    struct Dugum *sonraki;
};

struct Dugum *liste_ekle(struct Dugum *bas, int deger);
int liste_toplam(const struct Dugum *bas);
void liste_serbest(struct Dugum *bas);
struct Dugum *liste_sig_kopyala(struct Dugum *bas);
struct Dugum *liste_derin_kopyala(const struct Dugum *bas);

#endif

// dugum.c — liste islemlerinin gerceklemesi
#include <stdlib.h>
#include "dugum.h"

struct Dugum *liste_ekle(struct Dugum *bas, int deger) {
    struct Dugum *yeni = malloc(sizeof *yeni);
    if (yeni == NULL) {
        return bas;
    }
    yeni->deger = deger;
    yeni->sonraki = bas;
    return yeni;
}

int liste_toplam(const struct Dugum *bas) {
    int toplam = 0;
    for (const struct Dugum *d = bas; d != NULL; d = d->sonraki) {
        toplam += d->deger;
    }
    return toplam;
}

void liste_serbest(struct Dugum *bas) {
    while (bas != NULL) {
        struct Dugum *sonraki = bas->sonraki;
        free(bas);
        bas = sonraki;
    }
}

struct Dugum *liste_sig_kopyala(struct Dugum *bas) {
    return bas;
}

struct Dugum *liste_derin_kopyala(const struct Dugum *bas) {
    struct Dugum *yeni_bas = NULL;
    struct Dugum *son = NULL;
    for (const struct Dugum *d = bas; d != NULL; d = d->sonraki) {
        struct Dugum *yeni = malloc(sizeof *yeni);
        if (yeni == NULL) {
            liste_serbest(yeni_bas);
            return NULL;
        }
        yeni->deger = d->deger;
        yeni->sonraki = NULL;
        if (son == NULL) {
            yeni_bas = yeni;
        } else {
            son->sonraki = yeni;
        }
        son = yeni;
    }
    return yeni_bas;
}

Takma Ad ile Değişen Düğüm

Liste 1, 2, 3 değerleriyle kuruluyor. ikinci işaretçisi ikinci düğümü işaret ediyor — yeni bir düğüm değil, listenin kendi düğümlerinden biri. ikinci üzerinden yapılan değişiklik listenin toplamına yansıyor, çünkü ikisi de aynı bellek bloğuna bakıyor.

// takma_ad.c — listenin kendi dugumune ikinci bir gostergeyle erisim
#include <stdio.h>
#include "dugum.h"

int main(void) {
    struct Dugum *bas = NULL;
    bas = liste_ekle(bas, 3);
    bas = liste_ekle(bas, 2);
    bas = liste_ekle(bas, 1);

    printf("%s %d\n", "takma adla degismeden once toplam", liste_toplam(bas));

    struct Dugum *ikinci = bas->sonraki;
    ikinci->deger = 20;

    printf("%s %d\n", "takma adla degistikten sonra toplam", liste_toplam(bas));
    printf("%s %d\n", "ikinci ile bas->sonraki ayni dugum mu", (int)(ikinci == bas->sonraki));

    liste_serbest(bas);
    return 0;
}

takma adla degismeden once toplam 6
takma adla degistikten sonra toplam 24
ikinci ile bas->sonraki ayni dugum mu 1

VY1. ikinci değişkeni struct Dugum * tipinde ve bas da öyle — kaynağın hiçbir yerinde ikinci‘nin listenin kendi bir düğümünü mü gösterdiği yoksa bağımsız bir kopya mı olduğu yazmıyor. Bunu belirleyen, bildirim değil atamanın kendisi: ikinci = bas->sonraki bir kopyalama değil bir işaretçi kopyalama, yani ikinci ve bas->sonraki aynı adresi taşıyor. ikinci->deger = 20 satırı bu yüzden bas üzerinden okunan toplamı da değiştiriyor: 6’dan 24’e. Son satır bunu adres basmadan doğruluyor — ikinci == bas->sonraki karşılaştırması, iki işaretçinin aynı düğümü gösterdiğini 1 olarak veriyor. Sınıf ortak: değişikliği ikinci bir okuyucu (burada bas üzerinden yapılan liste_toplam çağrısı) görüyor, çünkü ikisi arasında paylaşılan tek bir nesne var, kopyalanmış iki nesne değil.

Sığ Kopya, Derin Kopya

liste_sig_kopyala bir düğüm bile ayırmıyor; aldığı başı olduğu gibi döndürüyor. Bu yüzden döndürdüğü işaretçiyle orijinal liste aynı düğümlere bakıyor ve biri üzerinden yapılan değişiklik ötekinden görünüyor. liste_derin_kopyala her düğüm için yeni bir ayırma yapıyor; döndürdüğü liste kopyalama anındaki değerleri taşıyor ama sonrasında orijinalle hiçbir düğümü paylaşmıyor.

// kopya_karsilastirma.c — sig kopya paylasiyor, derin kopya kesiyor
#include <stdio.h>
#include "dugum.h"

int main(void) {
    struct Dugum *bas = NULL;
    bas = liste_ekle(bas, 3);
    bas = liste_ekle(bas, 2);
    bas = liste_ekle(bas, 1);

    struct Dugum *sig = liste_sig_kopyala(bas);
    bas->sonraki->deger = 200;
    printf("%s %d\n", "sig kopyanin gordugu ikinci deger", sig->sonraki->deger);

    struct Dugum *derin = liste_derin_kopyala(bas);
    bas->sonraki->deger = 2000;
    printf("%s %d\n", "derin kopyanin gordugu ikinci deger", derin->sonraki->deger);

    liste_serbest(derin);
    liste_serbest(bas);
    return 0;
}

sig kopyanin gordugu ikinci deger 200
derin kopyanin gordugu ikinci deger 200

VY2. İki satır da aynı sayıyı (200) basıyor ama farklı nedenlerle ve bu fark dersin ölçtüğü şey. İlk satırda sig, bas ile aynı düğümleri gösteriyor; bas->sonraki->deger = 200 ataması sig->sonraki->deger’i de değiştiriyor, çünkü ikisi tek bir nesneye bakıyor — sınıf ortak. İkinci satırda derin, kopyalama anında (ikinci düğüm henüz 200 değerini taşırken) yeni düğümler ayırarak kuruldu; kopyalamadan sonra yapılan bas->sonraki->deger = 2000 ataması derin’i etkilemiyor, çünkü derin‘in düğümleri bas‘ınkilerden bağımsız bellek blokları. derin->sonraki->deger hâlâ kopyalama anındaki 200’ü taşıyor, 2000’i değil — sınıf kopya: değişiklik ikinci bir okuyucuya hiç ulaşmıyor, çünkü aralarında paylaşılan bir nesne yok. liste_sig_kopyala’nın döndürdüğü işaretçi bas ile tıpatıp aynı olduğu için bu derste yalnız derin ve bas ayrı ayrı bırakılıyor; sig’i ayrıca bırakmak aynı bloğu iki kez bırakmak olurdu.

İkili Arama Ağacı: Ekleme, Dolaşma, Bırakma

Bağlı listenin tek-sonraki-işaretçili paylaşımı ikili ağaçta iki işaretçiye (sol, sag) çıkıyor ama ilke aynı: bir düğüme birden fazla yoldan erişildiğinde, hangi yoldan erişildiği kaynakta görünmüyor. agac_ekle özyinelemeli, agac_toplam sıralı (inorder) dolaşıp değerleri topluyor, agac_serbest önce alt ağaçları sonra kökü bırakıyor — listedeki “kim bırakacak” sözleşmesi burada da geçerli, bu ders yalnız o sözleşmenin üzerine değil, ağacın görünürlüğüne odaklanıyor.

// agac.h — ikili arama agaci temel islemleri
#ifndef AGAC_H
#define AGAC_H

struct AgacDugumu {
    int deger;
    struct AgacDugumu *sol;
    struct AgacDugumu *sag;
};

struct AgacDugumu *agac_ekle(struct AgacDugumu *kok, int deger);
int agac_toplam(const struct AgacDugumu *kok);
void agac_serbest(struct AgacDugumu *kok);

#endif

// agac.c — ekleme, siralanmis dolasma ve birakma
#include <stdlib.h>
#include "agac.h"

struct AgacDugumu *agac_ekle(struct AgacDugumu *kok, int deger) {
    if (kok == NULL) {
        struct AgacDugumu *yeni = malloc(sizeof *yeni);
        if (yeni == NULL) {
            return NULL;
        }
        yeni->deger = deger;
        yeni->sol = NULL;
        yeni->sag = NULL;
        return yeni;
    }
    if (deger < kok->deger) {
        kok->sol = agac_ekle(kok->sol, deger);
    } else {
        kok->sag = agac_ekle(kok->sag, deger);
    }
    return kok;
}

int agac_toplam(const struct AgacDugumu *kok) {
    if (kok == NULL) {
        return 0;
    }
    return agac_toplam(kok->sol) + kok->deger + agac_toplam(kok->sag);
}

void agac_serbest(struct AgacDugumu *kok) {
    if (kok == NULL) {
        return;
    }
    agac_serbest(kok->sol);
    agac_serbest(kok->sag);
    free(kok);
}

// agac_takma_ad.c — agacin kendi dugumune ikinci bir gostergeyle erisim
#include <stdio.h>
#include "agac.h"

int main(void) {
    struct AgacDugumu *kok = NULL;
    int degerler[] = {5, 3, 8, 1, 4};
    for (size_t i = 0; i < sizeof degerler / sizeof degerler[0]; i++) {
        kok = agac_ekle(kok, degerler[i]);
    }
    printf("%s %d\n", "agactaki degerlerin toplami once", agac_toplam(kok));

    struct AgacDugumu *sol_alt = kok->sol;
    sol_alt->deger = 30;
    printf("%s %d\n", "sol_alt uzerinden degisince toplam", agac_toplam(kok));

    agac_serbest(kok);
    return 0;
}

agactaki degerlerin toplami once 21
sol_alt uzerinden degisince toplam 48

VY3. sol_alt, kok->sol ile aynı düğümü gösteriyor — ağaca yeni bir dal eklemedi, var olan bir düğüme ikinci bir yoldan (kökün sol alanı yerine kendi değişkeni üzerinden) eriştik. sol_alt->deger = 30 ataması bu düğümün değerini 3’ten 30’a çıkarıyor ve agac_toplam(kok) bunu görüyor: 21’den 48’e. Bağlı listedeki ikinci örneğiyle aynı ilke — sınıf yine ortak. Ağacı bırakırken (agac_serbest) uyduğumuz sözleşme ayrı bir soru: her düğümü kim bırakacak, önceki kursun (C’de Bellek ve İşaretçiler) ekseni. Bu ders o soruyu yeniden açmıyor; yalnız bir değişikliğin ikinci bir işaretçiden görünüp görünmediğini ölçüyor.

Struct Atamasıyla Kısmi Sığ Kopya

liste_sig_kopyala ile liste_derin_kopyala iki uç örnekti: biri hiçbir şeyi kopyalamıyordu, öteki her düğümü kopyalıyordu. Ama C’de bir yapıyı kopyalamanın üçüncü, daha sinsi bir yolu var: struct atamasi (=). struct Dugum kopya = *bas; yazıldığında derleyici bas’ın gösterdiği yapının her alanını yeni bir değişkene kopyalıyor — ama “her alan”ın içinde bir işaretçi de varsa, o işaretçi de bir değer olarak kopyalanıyor, gösterdiği yer değil.

// struct_atama.c — degisken tipi atamayla kismi sig kopya
#include <stdio.h>
#include "dugum.h"

int main(void) {
    struct Dugum *bas = NULL;
    bas = liste_ekle(bas, 3);
    bas = liste_ekle(bas, 2);
    bas = liste_ekle(bas, 1);

    struct Dugum kopya = *bas;
    printf("%s %d\n", "atamadan hemen sonra kopyanin deger alani", kopya.deger);

    bas->deger = 100;
    printf("%s %d\n", "bas->deger degisince kopya.deger", kopya.deger);

    bas->sonraki->deger = 200;
    printf("%s %d\n", "ikinci dugum uzerinden degisince kopya.sonraki->deger", kopya.sonraki->deger);

    liste_serbest(bas);
    return 0;
}

atamadan hemen sonra kopyanin deger alani 1
bas->deger degisince kopya.deger 1
ikinci dugum uzerinden degisince kopya.sonraki->deger 200

VY14. struct Dugum kopya = *bas; satırı iki farklı şey yapıyor ve ikisi de aynı atamanın içinde: deger alanı bir int, atama onu değerle kopyalıyor — bu yüzden bas->deger = 100 çalıştığında kopya.deger hâlâ ilk değerinde, 1’de kalıyor. Ama sonraki alanı bir struct Dugum *, atama onu da değerle kopyalıyor — kopyalanan değer bir adres, yani kopya.sonraki ile bas->sonraki atamadan sonra aynı adresi taşıyor. bas->sonraki->deger = 200 çalıştığında bu değişiklik kopya.sonraki->deger üzerinden de görünüyor: 200. Tek bir atama satırı içinde deger alanı için kopya sınıfı, sonraki alanının gösterdiği düğüm için ortak sınıfı aynı anda üretiliyor — “sığ kopya” ile “derin kopya” arasındaki fark bazen bir işlev seçimi değil, bir yapının hangi alanlarının işaretçi taşıdığı meselesi. liste_sig_kopyala’nın döndürdüğü işaretçinin tamamı paylaşılıyordu; burada yalnız sonraki’nin gösterdiği düğüm paylaşılıyor, deger alanının kendisi paylaşılmıyor — aynı struct atamasının içinde iki ayrı sınıf bir arada.

Sınırlayıcı Ölçüm

Bir işaretçinin paylaşımı kaynakta görünmez. İki liste başı ya da iki ağaç dalı aynı düğümü gösterdiğinde bunu yapının tipi söylemez — struct Dugum * bildirimi hem listenin kendi bir düğümünü hem bağımsız bir kopyayı gösterebilir, aralarında kaynak düzeyinde hiçbir ayrım yok. Bu derste her iki durumda da işaretçileri adres basmadan karşılaştırdık: ikinci == bas->sonraki eşitliği, iki değişkenin aynı bellek bloğuna mı baktığını, farklı bloklara mı baktığını söyledi. liste_sig_kopyala ile liste_derin_ kopyala’nın farkı da kaynakta bir imzayla değil, gövdelerinin ne yaptığıyla ortaya çıkıyor: biri hiç ayırma yapmıyor, öteki her düğüm için yeni bir ayırma yapıyor. Bir işlevin dönüş tipine bakarak paylaşıp paylaşmadığını söylemek mümkün değil; bu yalnız gövdeyi okuyarak ya da ölçerek anlaşılıyor.

Özet

• Bağlı liste ve ikili arama ağacı aynı ilkeyle kuruldu: bir düğüme birden fazla işaretçi aynı anda erişebilir ve kaynak bunu söylemez.
• Bir düğüme takma adla erişip değiştirmek listede de ağaçta da ortak sınıfını üretti: ikinci bir okuyucu (liste_toplam, agac_toplam) değişikliği gördü.
• liste_sig_kopyala düğüm ayırmadan başı döndürdüğü için ortak kaldı; liste_derin_kopyala her düğüm için yeni bir ayırma yaptığı için kopya üretti.
• Struct atamasıyla (=) yapılan kısmi kopya, bir yapının skaler alanlarında kopya, işaretçi alanlarının işaret ettiği yerde ortak sınıfını aynı anda üretebiliyor.
• İki işaretçinin aynı düğümü gösterip göstermediği adres basılmadan, yalnız eşitlikle (==) ölçülebiliyor.
• Bir yapının kim tarafından bırakılacağı (K02’nin sorusu) ile bir değişikliğin kim tarafından görüleceği (bu kursun sorusu) ayrı eksenler; bu ders ikincisini ölçüyor.

Sonraki Adım

Bu derste bir düğüme erişmek için hep bir işaretçi tuttuk ve o işaretçi kalıcıydı. Bir sonraki ders, Halka Arabellek ve Kuyruklar, işaretçinin kendisi değil bir konumun (indeksin) paylaşıldığı bir yapıya bakıyor: bir üretici ile bir tüketici aynı diziyi kullanıyor ama biri yazarken diğeri okuyor, ve yazılan değer okunmadan üzerine yazılabiliyor. Sınıf orada ortak değil, aktarım: değer okuyucuya bir kez ulaşıyor, sonra kaybolabiliyor.