C ile Veri Yapıları İçin Ön Bilgiler

C'de her değişkenin bir tipi ve bellekte kapladığı belirli bir bayt sayısı vardır; sizeof bu sayıyı derleme sırasında verir. İki tamsayı arasındaki bölme tamsayı bölmesidir: kesirli kısım atılır. Dizi indisleri, heap'te ebeveyn indisi (i / 2) ve ikili aramadaki orta nokta hep bu kurala dayanır.

int a = 7, b = 2;
printf("%d\n", a / b);           /* 3   */
printf("%d\n", a % b);           /* 1   */
printf("%.1f\n", (double)a / b); /* 3.5 */
printf("%zu\n", sizeof(int));    /* çoğu sistemde 4 */

C'de bütün argümanlar değerle geçirilir (call by value): fonksiyon, çağıranın değişkeninin bir kopyasını alır. Bu yüzden iki değişkeni takas etmek isteyen bir fonksiyon, değişkenlerin kendilerini değil adreslerini almalıdır. Derste swap, yığının top sayacı ve arama ağacına ekleme hep bu nedenle adres alır.

void takas_yanlis(int x, int y) { int t = x; x = y; y = t; }
void takas(int *x, int *y)      { int t = *x; *x = *y; *y = t; }

int a = 1, b = 2;
takas_yanlis(a, b);   /* a == 1, b == 2: kopyalar değişti */
takas(&a, &b);        /* a == 2, b == 1 */

Dizi, aynı tipte öğelerin bellekte art arda durduğu bir bloktur; a[i] erişimi O(1) sürer ve C sınır denetimi yapmaz. Bir diziyi fonksiyona geçirmek, ilk öğesinin adresini geçirmektir; boyut ayrıca verilmelidir. Dizge (string) ise sonunda '\0' bulunan bir char dizisidir: "dog" dört bayt kaplar.

int topla(const int a[], int n) {
    int s = 0;
    for (int i = 0; i < n; i++) s += a[i];
    return s;
}

int uzunluk(const char *s) {
    int n = 0;
    while (s[n] != '\0') n++;
    return n;
}
/* topla((int[]){4, 5, 6}, 3) == 15, uzunluk("dog") == 3 */

struct, farklı tipteki alanları tek bir kayıtta toplar; typedef bu tipe kısa bir ad verir. Alana değişken üzerinden ., işaretçi üzerinden -> ile erişilir; p->deger yazımı (*p).deger ile aynıdır. Bağlı listenin düğümü, kendi tipinden bir işaretçi taşıyan kendine başvuran yapıdır (self-referential struct).

typedef struct dugum *dugum_gost;
typedef struct dugum {
    int deger;
    dugum_gost bag;      /* sonraki düğüm ya da NULL */
} dugum;

dugum d = { 3, NULL };
dugum_gost p = &d;
p->deger = 8;            /* d.deger artık 8 */

Önişlemci, #define ile tanımlanan makroları derlemeden önce metin olarak yerine koyar; bu yüzden makro parametreleri parantez içinde yazılır. Başlık dosyası (.h) bir modülün arayüzünü, .c dosyası ise gerçeklemesini taşır. Başlıkta yalnız typedef struct kesir Kesir; bildirilirse yapının içi kullanıcıdan gizlenir: bu bir opak tiptir ve C'de soyut veri tipinin karşılığıdır.

/* kesir.h */
#ifndef KESIR_H
#define KESIR_H
typedef struct kesir Kesir;     /* opak: alanlar görünmez */
Kesir *kesir_olustur(int pay, int payda);
void   kesir_sil(Kesir *k);
#endif

#define KARE(x) ((x) * (x))     /* KARE(1 + 2) == 9 */

Kendini çağıran bir fonksiyon, her çağrıda problemi küçültmeli ve bir taban duruma ulaşmalıdır. Her çağrı için çağrı yığınına yerel değişkenleri ve dönüş adresini tutan bir çerçeve eklenir; derinlik n ise ek bellek O(n) olur. Ağaç gezinmeleri, ikili arama, Hanoi kuleleri ve hızlı sıralama bu düzenle yazılır.

long fakt(int n) {
    if (n <= 1) return 1;        /* taban durum */
    return n * fakt(n - 1);      /* küçülen problem */
}
/* fakt(4) -> 4 * fakt(3) -> 4 * 3 * fakt(2)
           -> 4 * 3 * 2 * fakt(1) = 24 */

İşaretçi (pointer), bir nesnenin adresini tutan değişkendir. &x x'in adresini verir, *p p'nin gösterdiği nesneye ulaşır. NULL hiçbir yeri göstermeyen işaretçidir ve derste boş listenin, boş alt ağacın gösterimidir. İki işaretçi aynı nesneyi gösterebilir; biri üzerinden yapılan değişiklik ötekinden de görülür.

int x = 5;
int *p = &x;     /* p, x'in adresini tutar */
int *q = p;      /* q de x'i gösterir      */
*q = 7;          /* x == 7, *p == 7        */
p = NULL;        /* p artık hiçbir yeri göstermez; x hâlâ 7 */

Bir ifade içinde dizinin adı ilk öğesinin adresine dönüşür. İşaretçiye 1 eklemek onu bir bayt değil, bir sonraki öğeye ilerletir: int 4 bayt ise adres 4 artar. a[i] yazımı tanım gereği *(a + i) demektir. Çok boyutlu dizilerin satır öncelikli adres hesabı da bu kurala dayanır.

int a[] = {10, 20, 30, 40};
int *p = a;               /* p == &a[0] */
printf("%d\n", *(p + 2)); /* 30 */
p++;                      /* p == &a[1] */
printf("%d\n", p[1]);     /* 30: p[1] == a[2] */
printf("%td\n", &a[3] - p);  /* 2 öğe */

Yerel değişkenler fonksiyon bitince yok olur; malloc ile ayrılan blok ise free çağrılana kadar heap bellekte yaşar. malloc bellek kalmazsa NULL döndürür, bu yüzden dönüş değeri her seferinde denetlenir. Geri verilmeyen blok bellek sızıntısına (memory leak), geri verildikten sonra kullanılan işaretçi ise sarkan işaretçiye (dangling pointer) yol açar.

int n = 5;
int *a = malloc(n * sizeof *a);
if (a == NULL) return 1;          /* bellek yok */
for (int i = 0; i < n; i++) a[i] = i * i;
int *b = realloc(a, 2 * n * sizeof *a);  /* büyüt */
if (b == NULL) { free(a); return 1; }
a = b;
free(a);
a = NULL;                         /* sarkan işaretçi kalmasın */

Bir fonksiyon, çağıranın işaretçisini (örneğin listenin başını ya da ağacın kökünü) değiştirecekse o işaretçinin adresini almalıdır. Tip bu durumda dugum ** olur. Değerle çağrı kuralının işaretçilere uygulanmasıdır: işaretçi de bir değişkendir ve kopyalanarak geçirilir.

void basa_ekle(dugum_gost *bas, dugum_gost yeni) {
    yeni->bag = *bas;   /* yeni düğüm eski başı gösterir */
    *bas = yeni;        /* çağıranın baş işaretçisi değişir */
}

dugum_gost liste = NULL;
basa_ekle(&liste, p);   /* liste artık p'nin düğümünü gösterir */

Fonksiyonun adı da bir adrestir ve başka bir fonksiyona argüman olarak geçirilebilir. Standart kitaplıktaki qsort, öğe tipini bilmeden çalışır: diziyi void * olarak alır ve iki öğenin sırasını, kullanıcının verdiği karşılaştırma fonksiyonuna sorar. Fonksiyon negatif, sıfır ya da pozitif döndürür.

int artan(const void *x, const void *y) {
    int a = *(const int *)x, b = *(const int *)y;
    return (a > b) - (a < b);   /* -1, 0 ya da 1 */
}

int d[] = {37, 15, 24};
qsort(d, 3, sizeof d[0], artan);   /* d: 15 24 37 */

Derste lg n, 2 tabanında logaritmadır: n'yi 1'e indirmek için kaç kez ikiye bölmek gerektiğini söyler. 2¹⁰ = 1024 ≈ 10³ olduğundan bir milyon öğede lg n ≈ 20'dir. İkili arama, dengeli ağacın yüksekliği ve heap işlemleri bu yüzden O(lg n) sürer. Logaritmanın tabanı yalnız sabit bir çarpanı değiştirir; büyük O içinde taban yazılmaz.

int ikiye_bolme_sayisi(int n) {
    int k = 0;
    while (n > 1) { n /= 2; k++; }
    return k;                     /* ⌊lg n⌋ */
}
/* 1 → 0, 8 → 3, 1000 → 9, 1024 → 10 */

İç içe döngülerin maliyeti çoğu zaman bir toplamdır. İki formül derste sürekli kullanılır: 1 + 2 + … + n = n(n + 1)/2 ve 1 + 2 + 4 + … + 2ᵏ = 2ᵏ⁺¹ − 1. İlki seçimli ve eklemeli sıralamanın O(n²) olduğunu, ikincisi k derinlikli ikili ağacın en çok 2ᵏ − 1 düğüm taşıdığını ve kapasitesi ikiye katlanan dizide toplam kopya sayısının O(n) kaldığını gösterir.

int sayac = 0;
for (int i = 0; i < n - 1; i++)       /* seçimli sıralama */
    for (int j = i + 1; j < n; j++)
        sayac++;                      /* bir karşılaştırma */
/* sayac == (n-1) + (n-2) + ... + 1 == n(n-1)/2
   n = 5 için 10 */

Bir önerme n = 1 için doğruysa (taban adım) ve n − 1 için doğruluğu n için doğruluğunu gerektiriyorsa (tümevarım adımı), bütün n ≥ 1 için doğrudur. Özyinelemeli bir fonksiyonun doğruluğu da aynı biçimde kanıtlanır: taban durum doğru sonuç verir, küçük çağrılar doğruysa büyük çağrı da doğrudur. Ağaçlardaki düğüm sayısı lemmaları bu yöntemle kanıtlanır.

/* Önerme: toplam(n) == n * (n + 1) / 2 */
int toplam(int n) {
    if (n == 0) return 0;            /* taban: 0 == 0·1/2 */
    return toplam(n - 1) + n;        /* (n-1)n/2 + n == n(n+1)/2 */
}

x % m, x'in m'ye bölümünden kalandır ve negatif olmayan x için 0 ile m − 1 arasında kalır. Dairesel kuyrukta dizinin sonuna gelen indis (arka + 1) % MAX ile başa döner; hash tablosunda k % m anahtarı bir kovaya eşler. C'de negatif bir sayının kalanı negatif çıkabilir; hash hesaplarında bu yüzden unsigned tipler kullanılır.

#define MAX 5
int arka = 4;
arka = (arka + 1) % MAX;     /* 0: başa dönüldü */

unsigned h(unsigned k, unsigned m) { return k % m; }
/* m = 13: h(27, 13) == 1, h(40, 13) == 1 → çakışma */

n öğenin n! farklı dizilişi ve 2ⁿ farklı alt kümesi vardır. Kaba kuvvet algoritmaları bu sayıların tümünü dener; permütasyon üretimi O(n · n!), alt küme üretimi ve SAT denemesi O(2ⁿ) sürer. 2ⁿ ve n! o kadar hızlı büyür ki n = 25 civarında bile en hızlı makine yetmez; geri izleme ve iyi bir algoritma bu yüzden önemlidir.

/* n öğenin bütün alt kümeleri: her bit bir öğe */
for (unsigned m = 0; m < (1u << n); m++) {
    for (int i = 0; i < n; i++)
        if (m & (1u << i)) printf("%d ", a[i]);
    printf("\n");
}   /* n = 3 için 8 satır, ilki boş küme */

Bir algoritmanın zamanı, girdi boyutu n'nin fonksiyonu olarak kaç temel adım çalıştığıyla ölçülür. Her atama, karşılaştırma ve dönüş bir adım sayılır; döngünün koşulu gövdeden bir kez fazla denetlenir. Sabitler ayrıntıdır; önemli olan adım sayısının n ile nasıl büyüdüğüdür.

float sum(float list[], int n) {
    float t = 0;                  /* 1 adım      */
    for (int i = 0; i < n; i++)   /* n + 1 adım  */
        t += list[i];             /* n adım      */
    return t;                     /* 1 adım      */
}                                 /* toplam 2n + 3 */

f(n) = O(g(n)), yeterince büyük her n için f(n) ≤ c · g(n) olacak biçimde pozitif bir c sabitinin bulunduğunu söyler: g, f için bir üst sınırdır. Ω alt sınırı, Θ ise ikisinin birlikte geçerli olduğunu gösterir. Alışılmış sıra 1 < lg n < n < n lg n < n² < n³ < 2ⁿ < n! biçimindedir.

/* T(n) = 3n² + 6n + 7 için:
   n ≥ 1 iken 6n ≤ 6n² ve 7 ≤ 7n² olduğundan
   T(n) ≤ 3n² + 6n² + 7n² = 16n²  →  T(n) = O(n²)
   T(n) ≥ 3n²                      →  T(n) = Ω(n²)
   ikisi birlikte                  →  T(n) = Θ(n²) */

Aynı boyuttaki iki girdi farklı sürelerde işlenebilir. Doğrusal aramada aranan ilk öğedeyse tek karşılaştırma yeter (en iyi durum), hiç yoksa n karşılaştırma gerekir (en kötü durum). Ortalama durum, girdilerin dağılımına dair bir varsayım ister. Amortize analiz ise tek tek işlemlere değil bir işlem dizisinin toplam maliyetine bakar.

int dogrusal_ara(const int a[], int n, int x) {
    for (int i = 0; i < n; i++)
        if (a[i] == x) return i;   /* bulundu */
    return -1;                     /* yok: n karşılaştırma */
}

Özyinelemeli bir algoritmanın süresi kendisi cinsinden yazılır ve açılarak çözülür. Her adımda problemi yarıya indirip sabit iş yapan algoritma T(n) = T(n/2) + c ile O(lg n) sürer (ikili arama). İki yarıyı çözüp doğrusal işle birleştiren algoritma T(n) = 2T(n/2) + cn ile O(n lg n) sürer (birleştirme sıralaması). Hanoi kulelerinde h(n) = 2h(n − 1) + 1 bağıntısı 2ⁿ − 1 verir.

int ikili_ara(const int a[], int sol, int sag, int x) {
    if (sol > sag) return -1;
    int orta = sol + (sag - sol) / 2;
    if (a[orta] == x) return orta;
    if (a[orta] < x) return ikili_ara(a, orta + 1, sag, x);
    return ikili_ara(a, sol, orta - 1, x);
}   /* T(n) = T(n/2) + c  →  O(lg n) */

Alan karmaşıklığı, girdinin dışında gereken ek belleği ölçer: döngüyle toplama O(1), aynı işi özyinelemeyle yapmak çağrı yığınında O(n) yer tutar. Kuramsal analiz gerçek ölçümle de sınanır: clock() programın harcadığı işlemci zamanını verir. Kısa işler birçok kez tekrarlanarak ölçülür, printf gibi yavaş giriş çıkış işlemleri ölçülen bölgenin dışında tutulur.

#include <time.h>
clock_t bas = clock();
for (int t = 0; t < 1000; t++)
    dogrusal_ara(a, n, -1);        /* en kötü durum */
double sn = (double)(clock() - bas) / CLOCKS_PER_SEC;
printf("arama başına %g sn\n", sn / 1000);