Bölüm 2: Diziler ve Yapılar

2.1Dizi soyut veri tipi

Bir veri yapısını iki düzeyde düşünmek mümkündür. Soyut düzeyde yalnız yapının ne iş gördüğü, yani hangi değerleri tuttuğu ve hangi işlemleri sunduğu konuşulur. Somut düzeyde ise bu işlemlerin bellekte hangi düzenle ve hangi kodla yapıldığı ele alınır. Birinci düzeye soyut veri tipi (abstract data type, ADT), ikinci düzeye gerçekleme (implementation) denir. Dizi, bu iki düzeyin çoğu zaman birbirine karıştırıldığı bir yapıdır: “dizi” denince akla hemen bellekte yan yana duran hücreler gelir. Oysa yan yana durmak dizinin tanımı değil, en yaygın gerçeklemesidir.

2.1.1Dizi bir eşlemedir

Soyut bakışta dizi, indislerle değerler arasında kurulmuş bir ilişkidir. Her geçerli indise tek bir değer karşılık gelir. Bir sınıftaki öğrencilerin sıra numarasına göre notları, bir yılın günlerine göre sıcaklıklar ya da bir satranç tahtasının karelerine göre taşlar bu türden ilişkilerdir. İndis kümesi bir sayı aralığı olabileceği gibi, satranç tahtasındaki gibi sayı çiftlerinden de oluşabilir.

Bir ADT yalnız değerleriyle değil, işlemleriyle de tanımlanır. Horowitz, Sahni ve Anderson-Freed'in ders kitabı dizi ADT'si için üç işlem verir. Create boş bir dizi kurar, Retrieve bir indisteki değeri okur, Store ise bir indise değer yazar. Tablo 2.1'de bu işlemlerin anlamı görülür.

Tanımda iki ayrıntı önemlidir. Birincisi, Retrieve ve Store geçersiz bir indiste hata verir. ADT düzeyinde indis denetimi işlemin bir parçasıdır. İkincisi, Store “yeni diziyi” döndürür. Soyut düzeyde bir yazma işlemi eski diziyi bozmaz, yeni bir eşleme üretir. C gibi bir dilde ise yazma, var olan hücrenin içeriğini değiştirir. Bu iki fark, gerçeklemenin ADT'den neden ayrı düşünülmesi gerektiğini gösterir. C dizisi indisi hiç denetlemez ve yazdığı yeri yerinde değiştirir. Bu iki özellik hız kazandırır, karşılığında güvenlikten verir.

2.1.2Hızın kaynağı ve bedeli

Dizinin en yaygın gerçeklemesi, öğeleri bellekte ardışık hücrelere yerleştirmektir. Her öğe aynı tipte olduğundan aynı sayıda bayt kaplar. Bu sayıya s, ilk öğenin adresine α denirse i indisli öğenin adresi doğrudan hesaplanır:

Bu hesap bir çarpma ve bir toplamadan ibarettir. Dizinin uzunluğu ne olursa olsun işlem sayısı değişmez. Bu yüzden indisle erişim O(1) sürer. Bin öğeli bir dizinin 999. öğesine erişmek, ilk öğesine erişmek kadar kısa sürer. Bağlı liste gibi yapılarda aynı öğeye ulaşmak için baştan başlayıp öğe öğe ilerlemek gerekir. Dizinin ayırt edici gücü budur.

Ardışık yerleşimin iki bedeli vardır. Birincisi, dizinin boyutu baştan bellidir. Bellekte ayrılan blok sonradan kendiliğinden uzamaz; daha büyük bir dizi gerekirse yeni bir blok ayrılıp eski öğeler oraya taşınır. İkincisi, araya ekleme ve silme pahalıdır. n öğeli bir dizinin başına yeni bir öğe eklemek için bütün öğelerin birer hücre sağa kaydırılması gerekir. Silmede de boşalan yeri kapatmak için sonraki öğeler sola kaydırılır. Kaydırılan öğe sayısı en kötü durumda n olduğundan araya ekleme ve silme O(n) sürer. Dizinin sonuna ekleme ise kaydırma gerektirmez; bu işlemin maliyeti dinamik dizilerde ayrıca incelenir.

2.2C'de tek boyutlu dizi

C, dizi ADT'sini doğrudan dilin içinde gerçekler. Bir dizi bildirildiğinde derleyici ardışık bir bellek bloğu ayırır ve ilk öğenin adresini akılda tutar. Bu kesim bildirimi, adres hesabını, sizeof işlecini ve dizi adının işaretçiyle olan yakın ilişkisini ele alır. Konuyu izlemek için işaretçiyle ilgili iki işleci bilmek yeter: &x, x nesnesinin adresini verir; *p ise p işaretçisinin gösterdiği nesneye ulaşır.

2.2.1Bildirim, adres ve sizeof

Aşağıdaki bildirim iki dizi tanımlar. list beş tamsayı, plist ise beş tamsayı işaretçisi tutar.

int list[5], *plist[5];
/* list : 5 tamsayı       */
/* plist: 5 tamsayı işaretçisi */

list[i]  /* adresi: α + i * sizeof(int) */
sizeof list   /* 5 * sizeof(int) bayt */

Derleyici list için beş int'lik ardışık bir blok ayırır ve list[0]'ın adresini, yani α'yı tutar. Program list[i] yazdığında öğenin adresi çalışma anında α + i · sizeof(int) olarak hesaplanır. sizeof, bir tipin ya da nesnenin bayt cinsinden boyunu veren bir işleçtir. Değeri derleme sırasında bilinir. Yerel bir dizide sizeof list bütün dizinin boyunu verir: int 4 bayt ise 5 · 4 = 20 bayt. plist ise beş işaretçi tutar ve 64 bitlik bir sistemde her işaretçi 8 bayt olduğu için sizeof plist 40'tır. Bu değerler not için yazılan sürücü programda ölçülmüştür; int ve işaretçi boyları derleyiciye ve sisteme göre değişebilir.

Şekil 2.1 bu yerleşimi gösterir. Her kutu bir öğedir; kutunun üstünde indisi, altında adresi yazar. Adresler dörder bayt artar, çünkü her int dört bayt kaplar. İndisler 0'dan başlar: n öğeli bir dizinin geçerli indisleri 0, 1, …, n − 1'dir. Sıfırdan başlamanın nedeni adres formülüdür. İlk öğenin adresi α + 0 · s = α olur ve formülde ayrıca bir düzeltme terimi gerekmez.

C, indisin geçerli olup olmadığını denetlemez. ADT'deki Retrieve ve Store geçersiz indiste hata verirken C, list[5] ifadesinde de α + 5 · 4 adresini hesaplar ve oraya erişir. Bu adreste dizinin bir parçası bulunmaz; başka bir değişken, dönüş adresi ya da hiç ayrılmamış bir bölge olabilir. C standardı bu durumu tanımsız davranış (undefined behavior) sayar. Program çökebilir, yanlış sonuç üretebilir ya da görünüşte doğru çalışabilir. En tehlikelisi sonuncusudur, çünkü hata ancak başka bir makinede ya da başka bir girdide ortaya çıkar.

2.2.2Dizi adı ve işaretçi

İşaretçi (pointer), bir nesnenin bellek adresini tutan değişkendir. C'de dizi adı çoğu ifadede ilk öğenin adresine dönüşür. Örneğin list yazıldığında derleyici bunu &list[0] olarak, yani int * tipinde bir adres olarak işler. Bu kural dizi ile işaretçiyi birbirine çok yaklaştırır. Tablo 2.2 birbirine eşdeğer ifadeleri listeler.

Tablonun ikinci satırı işaretçi aritmetiğinin (pointer arithmetic) temel kuralını içerir. Bir işaretçiye tamsayı eklendiğinde birim bayt değil, gösterilen tipin bir öğesidir. p bir int * ise p + 1 bir sonraki int'i gösterir; adres 1 değil, 4 bayt artar. double * için artış 8 bayt, char * için 1 bayttır. Derleyici çarpmayı kendisi yapar. Bu sayede *(list + i) yazımı, adres formülü α + i · s'nin C'deki doğrudan karşılığı olur. Gerçekte list[i] yazımı da standartta *(list + i) olarak tanımlanır; köşeli parantez bu toplama ve içerik alma işleminin kısa yazılışıdır.

Dizi adı ile işaretçi değişkeni yine de aynı şey değildir. İki fark önemlidir:

• Dizi adına atama yapılamaz. list = p; derlenmez. Dizi adı bir değişken değil, derleyicinin bildiği sabit bir adrestir. p = list; ise geçerlidir, çünkü p bir değişkendir ve başka bir adres tutabilir.
• sizeof farklı sonuç verir. Yerel bir dizide sizeof list bütün dizinin boyunu (20 bayt) verir. Bir işaretçide ise sizeof p yalnız işaretçinin kendi boyudur (64 bitlik sistemde 8 bayt).

İkinci fark fonksiyon parametrelerinde sık hataya yol açar. C'de bir fonksiyona dizi geçirildiğinde dizi kopyalanmaz; yalnız ilk öğesinin adresi geçer. Bu yüzden void f(int a[]) ile void f(int *a) bildirimleri tamamen aynıdır. Parametre int a[10] diye yazılsa bile a fonksiyonun içinde bir işaretçidir ve sizeof a 8 verir. Not için yazılan sürücüde derleyici bu kullanımda -Wsizeof-array-argument uyarısını vermiştir. Dizinin uzunluğu fonksiyona ayrı bir parametreyle gönderilir. Standart kütüphanedeki qsort, memcpy ve fwrite gibi fonksiyonların hepsinin bir uzunluk parametresi almasının nedeni budur.

2.2.3Kod izleme: yazdir()

Aşağıdaki program dört öğeli bir diziyi yazdir fonksiyonuna geçirir. Fonksiyon her öğenin adresini ve değerini işaretçi aritmetiğiyle yazdırır.

void yazdir(int *p, int n) {
  int i;
  for (i = 0; i < n; i++)
    printf("%p %d\n", (void *)(p + i), *(p + i));
}

int main(void) {
  int dizi[] = {10, 20, 30, 40};
  yazdir(dizi, 4);
  return 0;
}

Program satır satır şöyle çalışır:

• main, dizi'yi yığında (stack) dört ardışık int olarak ayırır. Boyut başlangıç değerlerinin sayısından çıkarılır. İlk öğenin adresine α diyelim.
• yazdir(dizi, 4) çağrısında dizi kopyalanmaz. dizi adı &dizi[0]'a dönüşür ve bu adres, yani α, p parametresine kopyalanır. Uzunluk ayrı parametreyle (n = 4) gelir.
• Döngünün her turunda p + i, α + i · 4 adresini hesaplar. *(p + i) bu adresteki değeri okur; p[i] yazmakla aynıdır.
• %p biçimi bir void * bekler. Bu yüzden adres (void *) ile dönüştürülür. Dönüşüm yazılmazsa davranış standarda göre tanımsızdır.

Gerçek çıktıda α yerine onaltılık bir adres görünür. Not için yapılan bir çalıştırmada adresler …F910, …F914, …F918 ve …F91C çıkmıştır. Son iki onaltılık basamak 10, 14, 18, 1C biçiminde dörder artar. Adresin kendisi her çalıştırmada değişebilir; değişmeyen, ardışık iki öğe arasındaki 4 baytlık farktır. Fonksiyon dizinin her öğesine bir kez uğrar ve her turda sabit iş yapar. Süresi Θ(n), ek belleği O(1)'dir.

2.3Dinamik diziler

int list[5]; gibi bir bildirimde boyut derleme sırasında bellidir. Pek çok programda ise boyut ancak çalışma anında öğrenilir: kullanıcının girdiği öğrenci sayısı, bir dosyadaki satır sayısı ya da bir ağ bağlantısından gelen paket sayısı. Bu durumda bellek çalışma anında istenir. Buna dinamik bellek ayırma (dynamic memory allocation) denir. C'de bu iş <stdlib.h> başlığındaki malloc, calloc, realloc ve free fonksiyonlarıyla yapılır.

2.3.1malloc ile dizi

Aşağıdaki parça önce dizinin boyutunu okur, sonra o kadar int'lik bir blok ayırır, bloğu dizi gibi kullanır ve en sonunda geri verir.

int n, i, *a;
scanf("%d", &n);
a = malloc(n * sizeof *a);   /* n int */
if (a == NULL) {
  fprintf(stderr, "Yetersiz bellek\n");
  exit(EXIT_FAILURE);
}
for (i = 0; i < n; i++)
  a[i] = i * i;              /* dizi gibi */
free(a);                     /* geri ver */
a = NULL;          /* sarkan işaretçi olmasın */

Kod satır satır şöyle çalışır:

• malloc(n * sizeof *a), n tamsayıya yetecek bayt sayısını ister ve bloğun başlangıç adresini döndürür. Dönüş tipi void *'dır; C bu adresi int * tipindeki a'ya dönüşüm yazmadan atar.
• Bellek yetmezse malloc NULL döndürür. Boş işaretçi (null pointer) hiçbir nesneyi göstermez. Bu durum denetlenmeden a[i]'ye yazılırsa program çöker. Denetim başarısız olursa bir ileti yazılır ve program exit(EXIT_FAILURE) ile sonlanır.
• Döngü a[i] = i * i ile bloğu doldurur. a bir işaretçi olsa da a[i] yazımı dizideki gibi çalışır, çünkü a[i] zaten *(a + i) demektir.
• free(a) bloğu sisteme geri verir. Ardından a = NULL yazılır. free'den sonra a hâlâ eski adresi tutar, ama o adresteki bellek artık programa ait değildir. Böyle bir işaretçiye sarkan işaretçi (dangling pointer) denir. NULL atamak, olası bir yanlış kullanımı belirsiz bir bozulma yerine hemen fark edilen bir hataya çevirir.

Yerel bir dizi ile malloc bloğunun ömrü farklıdır. Fonksiyon içinde bildirilen dizi, çağrının yığın çerçevesinde durur ve fonksiyon dönünce yok olur. malloc ile alınan blok ise heap bellekte (heap memory) durur ve free edilene kadar yaşar. Bu yüzden bir fonksiyon, içinde ayırdığı bir bloğun adresini güvenle döndürebilir, ama yerel bir dizinin adresini döndüremez. Yerel dizinin adresi fonksiyon döndüğü anda sarkan işaretçi olur.

Boyut ifadesindeki sizeof *a kalıbı bilinçli bir seçimdir. sizeof *a, a'nın gösterdiği tipin boyunu verir. a'nın tipi sonradan double * yapılsa bile ifade kendiliğinden doğru boyu hesaplar. sizeof(int) yazmak da doğrudur, ama tip değişince güncellenmesi unutulabilir. Daha tehlikeli hata, sizeof(int *) ile sizeof(int)'i karıştırmaktır: 64 bitlik bir sistemde ilki 8, ikincisi 4 bayttır. Yanlış olan küçük kalırsa bloğun sonundan taşılır, büyük kalırsa bellek boşa gider.

Kütüphanenin iki fonksiyonu daha vardır. calloc(n, s), n tane s baytlık öğe için yer ayırır ve bloğun bütün baytlarını sıfırlar. malloc ise bloğu sıfırlamaz; ilk içerik belirsizdir. realloc(p, yeni), daha önce ayrılmış bir bloğu büyütür ya da küçültür. Blok yerinde büyüyemezse realloc yeni bir blok ayırır, eski içeriği oraya kopyalar ve eski bloğu serbest bırakır. p NULL ise realloc tam olarak malloc gibi davranır. Bu son özellik, boş başlayan büyüyen dizilerde işe yarar.

2.3.2Büyüyen dizi: ekle()

Kaç öğe geleceği hiç bilinmiyorsa dizi büyüyebilmelidir. Dinamik dizi (dynamic array), dolduğunda realloc ile büyütülen dizidir. Bir dinamik diziyi tanımlamak için üç bilgi gerekir: öğelerin durduğu bloğun adresi, dizide şu anda kaç öğe bulunduğu ve bloğun en çok kaç öğe alabildiği. Son değere kapasite (capacity) denir. Aşağıdaki kodda bu üç bilgi DinDizi yapısının veri, boyut ve kap alanlarında durur.

typedef struct { int *veri; int boyut, kap; } DinDizi;

int ekle(DinDizi *d, int x) {
  if (d->boyut == d->kap) {              /* dolu */
    int yeni = d->kap ? 2 * d->kap : 1;
    int *t = realloc(d->veri, yeni * sizeof *t);
    if (t == NULL) return 0;    /* eski blok sağlam */
    d->veri = t;
    d->kap = yeni;
  }
  d->veri[d->boyut++] = x;
  return 1;
}

Kod satır satır şöyle çalışır:

• d bir DinDizi *'dır. Yapının kendisi kopyalanmasın ve fonksiyon boyut ile kap'ı kalıcı olarak değiştirebilsin diye işaretçi alınır. d->boyut yazımı (*d).boyut'un kısaltmasıdır.
• d->boyut == d->kap ise dizi doludur ve önce büyütülmelidir. Yeni kapasite eskisinin iki katıdır. Kapasite 0 ise iki katı da 0 olacağından yeni 1 alınır. ?: koşul işleci bu iki durumu tek satırda ayırır.
• realloc'un sonucu önce geçici t değişkenine alınır. Başarısızlıkta realloc NULL döndürür ama eski bloğa dokunmaz. Sonuç doğrudan d->veri'ye yazılsaydı eski bloğun adresi kaybolurdu: öğeler hem erişilemez hem geri verilemez olurdu. Bu, bir bellek sızıntısıdır (memory leak). Kodda başarısızlık durumunda 0 döndürülür ve dizi eski hâliyle sağlam kalır.
• Büyütme başarılıysa d->veri ve d->kap güncellenir.
• d->veri[d->boyut++] = x; satırı öğeyi ilk boş hücreye yazar. boyut++ son ek biçimidir: ifadede önce eski değer kullanılır, sonra değer bir artırılır. Bu yüzden x, veri[boyut]'a yazılır ve ardından boyut bir artar.

İlk eklemede veri NULL'dır ve realloc(NULL, …) bir malloc gibi davranır; kopyalanacak öğe yoktur. Sonraki büyütmelerde sırayla 1, 2 ve 4 öğe kopyalanır. Beş ekleme için toplam yalnız 7 kopya yapılmıştır. Dördüncü eklemede (4) dizide yer vardır ve öğe doğrudan yazılır. Not için yazılan sürücü programda realloc çağrılarının sayısı ve kopya toplamı bu tabloyla birebir aynı çıkmıştır. Burada “kopya”, realloc'un en kötü durumda taşıdığı öğe sayısıdır. Blok yerinde büyüyebilirse realloc hiç kopyalamaz; analiz bu yüzden bir üst sınır verir.

2.3.3Amortize maliyet

Tek bir ekle çağrısının maliyeti büyük ölçüde değişir. Dizide yer varsa çağrı bir yazmadan ibarettir ve O(1) sürer. Dizi doluysa realloc bütün öğeleri kopyalayabilir; bu çağrı O(n) sürer. Yalnız en kötü duruma bakılırsa n ekleme için O(n²) gibi karamsar bir sonuç çıkar. Oysa pahalı çağrılar seyrektir: kapasite her seferinde ikiye katlandığı için büyütme yalnız 1, 2, 4, 8, … öğeden sonra gerekir. Uzun bir işlem dizisinin toplam maliyetini işlem sayısına bölerek işlem başına maliyeti bulmaya amortize analiz (amortized analysis) denir.

Kapasiteyi ikiye katlamak yerine her seferinde bir hücre artırmak ilk bakışta daha tutumlu görünür. Ama bu durumda her eklemede büyütme gerekir. i. eklemede i − 1 öğe kopyalanır ve toplam kopya 0 + 1 + … + (n − 1) = n(n − 1)/2 olur. Bu O(n²)'dir. Sabit bir c kadar artırmak da durumu düzeltmez: büyütme sayısı n/c olur ve toplam kopya yine n² ile orantılı kalır. Önemli olan artışın sabit değil, mevcut kapasiteyle orantılı olmasıdır. Tablo 2.5 iki stratejiyi birkaç n için karşılaştırır.

Katlamada ekleme başına kopya sayısı 1'in altında kalır; n ikinin kuvveti olduğunda kopya tam n − 1'dir. Bir artırmada ise ekleme başına kopya (n − 1)/2'dir ve n ile birlikte büyür. Bin öğede fark beş yüz kattan fazladır.

Amortize sonuç, her tek eklemenin hızlı olduğu anlamına gelmez. Büyütme anına denk gelen ekleme yine O(n) sürer. Amortize analiz uzun bir işlem dizisinin ortalamasını garanti eder; olasılığa dayanmaz, en kötü işlem dizisi için de geçerlidir. Gerçek zamanlı bir sistemde tek bir işlemin süresi önemliyse bu ayrım dikkate alınmalıdır.

Katlamanın bir de bellek bedeli vardır. Büyütmeden hemen sonra kapasitenin yaklaşık yarısı boştur. Kapasite hiçbir zaman boyutun iki katını aşmaz; yani en kötü durumda hücrelerin yarısı kullanılmaz. Bazı kütüphaneler bu payı azaltmak için 1,5 gibi daha küçük bir çarpan kullanır. Çarpan 1'den büyük kaldığı sürece toplam kopya yine O(n)'dir; yalnız sabit değişir.

Not için yazılan bir denemede malloc ve realloc sayaçlı bir sarmalayıcıyla değiştirildi ve üçüncü realloc bilerek başarısız yapıldı. ekle 0 döndürdü, dizi iki öğesiyle (0, 1) sağlam kaldı ve free'den sonra hiç ayrılmış blok kalmadı.

2.3.4İki boyutlu dinamik dizi: dizi2b()

Satır ve sütun sayısı çalışma anında belli olan bir matris için en yaygın yöntem, bir işaretçi dizisi kurmaktır. Önce her satır için bir işaretçi tutan bir dizi ayrılır, sonra her satır ayrı bir blok olarak ayrılır ve adresi bu diziye yazılır. Matrisin adresi, işaretçi dizisinin adresidir. Bu adresin tipi int **, yani işaretçiye işaretçidir (pointer to pointer).

int **dizi2b(int satir, int sutun) {
  int i, **x = malloc(satir * sizeof *x);
  if (x == NULL) return NULL;
  for (i = 0; i < satir; i++) {
    x[i] = malloc(sutun * sizeof **x);
    if (x[i] == NULL) {                /* geri al */
      while (--i >= 0) free(x[i]);
      free(x); return NULL;
    }
  }
  return x;
}

Kod satır satır şöyle çalışır:

• malloc(satir * sizeof *x), satir tane işaretçilik bir blok ayırır. x bir int ** olduğu için *x bir int *'dır ve sizeof *x işaretçi boyunu verir. Bu blok ayrılamazsa fonksiyon hemen NULL döndürür.
• Döngü her satır için sutun tane int ayırır. **x bir int olduğundan sizeof **x tamsayı boyudur. İki sizeof ifadesi birbirinden farklıdır ve karıştırılmaması gerekir.
• Bir satır ayrılamazsa o ana kadar ayrılanlar geri verilir. while (--i >= 0) önce i'yi azaltır, sonra denetler; böylece başarısız olan i. satır atlanır ve i − 1, …, 0 satırları serbest bırakılır. En son işaretçi dizisi geri verilir ve NULL döner. Bu adım yazılmazsa başarısızlıkta ayrılmış satırlar sızar.
• Bütün satırlar ayrıldıysa x döner. Çağıran taraf x[i][j] yazımını sıradan bir iki boyutlu dizideki gibi kullanabilir.

Şekil 2.3 yapının bellekteki görünümünü verir. x[i][j] ifadesi iki adımda çözülür: x[i], yani *(x + i), i. satırın adresini getirir; [j] bu adresten j öğe ilerler. Tam açık yazılışı *(*(x + i) + j)'dir. Sürücü programda x[2][3] = 23 ve *(*(x + 1) + 2) = 12 değerleri, satırlara 10i + j yazıldıktan sonra beklendiği gibi okunmuştur.

Bu yapı ile int a[3][4]; gibi gerçek bir iki boyutlu dizi arasında önemli bir fark vardır. Gerçek dizide on iki öğenin hepsi tek bir ardışık blokta durur. İşaretçi dizisinde ise her satır ayrı bir malloc çağrısıyla ayrıldığından satırlar bellekte ardışık olmak zorunda değildir. Bu iki sonuç doğurur. Birincisi, satırlar farklı uzunlukta olabilir; alt üçgen bir matrisin i. satırı için yalnız i + 1 hücre ayırmak mümkündür. İkincisi, yapı bir adım daha fazla dolaylı erişim içerir ve bütün matrisi tek bir memcpy ile kopyalamak mümkün değildir.

Böyle bir matris geri verilirken sıra önemlidir. Önce her x[i] satırı, sonra x işaretçi dizisi free edilir. Sıra tersine çevrilirse x serbest bırakıldıktan sonra x[i] okunmuş olur; bu, geri verilmiş belleğe erişimdir. Yalnız free(x) yazılırsa satırların adresleri kaybolur ve hepsi sızar.

Maliyet açısından dizi2b satir + 1 tane malloc çağrısı yapar. Her çağrının süresi sabit kabul edilirse fonksiyon O(satir) sürer. Ayrılan bellek satir · sutun tamsayı ile satir işaretçinin toplamıdır. Öğelere erişim, iki dolaylı adım içerse de O(1)'dir.

2.4Çok boyutlu diziler ve adres hesabı

Bir tablo, bir resim ya da bir oyun tahtası iki indisle; bir hacim ya da bir video üç indisle doğal biçimde ifade edilir. Öğelerine birden çok indisle erişilen diziye çok boyutlu dizi (multidimensional array) denir. Bellek ise tek boyutludur: her baytın tek bir adresi vardır. Bu kesim, çok boyutlu bir dizinin tek boyutlu belleğe nasıl dizildiğini ve bir öğenin adresinin nasıl hesaplandığını inceler.

2.4.1Bellek tek boyutludur

A[u₀][u₁]…[u_n−1] olarak bildirilen n boyutlu bir dizide u₀ · u₁ · … · u_n−1 öğe vardır. Örneğin A[10][10][10] bin öğe tutar. Derleyici bu öğeleri belleğe bir sıraya koymak zorundadır. İki temel sıra vardır.

C, C++ ve Python'daki NumPy kütüphanesi varsayılan olarak satır öncelikli düzeni kullanır. Fortran, MATLAB ve R sütun önceliklidir. İki dil arasında matris aktaran bir programda bu farkın gözden kaçması, matrisin farkında olmadan transpozunun alınmasıyla sonuçlanır.

Hangi düzen seçilirse seçilsin adres hesabı aynı soruya dayanır: A[i][j] öğesinden önce bellekte kaç öğe vardır? Bu sayıya k denirse öğenin adresi α + k · s olur. Burada α dizinin başlangıç adresi, s bir öğenin bayt cinsinden boyudur. Tek boyutlu dizide k = i'dir; çok boyutlu dizide k birkaç terimin toplamıdır.

C'de int x[3][4]; bildirimi aslında dizilerden oluşan bir dizidir: her biri dört int'lik üç öğe. x[1] ifadesi 1. satırın, yani dört öğelik bir dizinin başını gösterir. Sürücü programda x[1] - x[0] farkı 4 öğe çıkmıştır: iki satır başı arasında tam bir satır vardır. Bu yapı, satır öncelikli düzenin dilin tip sisteminde doğrudan görünmesidir.

2.4.2Satır ve sütun öncelikli formüller

int x[3][4] dizisini ele alalım; satır sayısı u₀ = 3, satır uzunluğu u₁ = 4'tür. Satır öncelikli düzende x[i][j]'den önce i tam satır bulunur. Her satırda u₁ öğe olduğundan bu satırlar i · u₁ öğe eder. Öğenin kendi satırında ise solunda j öğe vardır. Toplam:

Sütun öncelikli düzende ise önce j tam sütun gelir. Her sütunda u₀ öğe vardır; bunlar j · u₀ öğe eder. Öğenin sütunu içinde üstünde i öğe bulunur:

Şekil 2.4 aynı öğenin iki düzende farklı konuma düştüğünü gösterir. x₁₂ satır öncelikli düzende 1 · 4 + 2 = 6. konumda, sütun öncelikli düzende 2 · 3 + 1 = 7. konumdadır. İki formül aynı mantığı izler; yalnız hangi indisin “dış”, hangisinin “iç” olduğu değişir.

Formüldeki parantez içindeki ifade öğe birimindedir. Bayt adresine geçmek için öğe boyu s ile çarpılır. C'de işaretçi aritmetiği bu çarpmayı kendisi yaptığından &x[0][0] + 6 zaten 6 · s bayt ileridedir. Elle bayt adresi hesaplanırken ise s unutulmamalıdır.

2.4.3Kod izleme: adres()

Satır öncelikli formül küçük bir fonksiyonla yazılabilir. Fonksiyon başlangıç adresini, iki indisi, satır uzunluğunu ve öğe boyunu alır, bayt adresini döndürür.

/* int x[3][4]: satır öncelikli bayt adresi */
long adres(long alfa, int i, int j,
           int ust1, int s) {
  long k = (long)i * ust1 + j;   /* öncekiler */
  return alfa + k * s;
}

int main(void) {
  printf("%ld\n", adres(100, 1, 2, 4, 4));
  printf("%ld\n", adres(100, 2, 3, 4, 4));
  return 0;
}

k, öğeden önceki öğelerin sayısıdır. (long)i dönüşümü çarpmanın long türünde yapılmasını sağlar; çok büyük dizilerde int çarpımı taşabilir. Fonksiyon alfa + k * s'yi döndürür. main iki öğenin adresini sorar: x[1][2] ve x[2][3]; dizi 100 adresinden başlar, u₁ = 4 ve s = 4'tür.

İkinci çağrıdaki x[2][3] dizinin son öğesidir. k = 11, yani on iki öğeli dizide son konum çıkar. Program derlenip çalıştırıldığında 124 ve 144 yazdırır. Sütun öncelikli düzen kullanılsaydı x[1][2] için k = 2 · 3 + 1 = 7 ve adres 128 olurdu. Sürücü programda gerçek bir int x[3][4] dizisinde &x[1][2] - &x[0][0] farkı da 6 öğe çıkmıştır; C'nin satır öncelikli olduğu böylece doğrudan görülür. Fonksiyon girdiye bağlı hiçbir döngü içermez; süresi O(1)'dir.

2.4.4Üç boyutlu dizi

Üç boyutlu bir dizi, iki boyutlu dizilerden oluşan bir dizidir. G[2][2][3] dizisinde iki dilim vardır; her dilim 2 satır ve 3 sütunluk bir matristir. Satır öncelikli düzende önce 0. dilimin altı öğesi, sonra 1. dilimin altı öğesi gelir. Bir dilimin içi de satır satır dizilir.

G[i][j][k]'dan önceki öğeler yine katman katman sayılır. Önce i tam dilim vardır; her dilim u₁ · u₂ öğe eder. Sonra kendi diliminde j tam satır, her biri u₂ öğe. En sonda kendi satırında k öğe. Tablo 2.8 bu terimlerin adım adım nasıl eklendiğini gösterir; adresler öğe birimindedir.

Son satırdaki ifadede üç çarpma ve üç toplama vardır. Çarpma toplamadan daha pahalı bir işlem olduğundan derleyici ifadeyi ortak çarpanı paranteze alarak yeniden yazar:

Bu biçimde iki çarpma ve üç toplama kalır. G[1][0][2] için hesap (1 · 2 + 0) · 3 + 2 = 8 verir. Şekil 2.6 ile karşılaştırınca [1][0][2] hücresinin altında gerçekten +8 yazdığı görülür. Sürücü programda gerçek bir int G[2][2][3] dizisinde &G[1][0][2] - &G[0][0][0] farkı da 8 çıkmıştır.

2.4.5n boyutlu genelleme

Aynı düşünce her boyut sayısına genişler. A[u₀][u₁]…[u_n−1] dizisinde A[i₀][i₁]…[i_n−1]'den önce, en dıştaki indis için i₀ tam “dilim” vardır ve her biri u₁ u₂ … u_n−1 öğe eder. Bir içteki indis için i₁ tane u₂ … u_n−1 öğelik blok vardır. En içteki indis yalnız i_n−1 öğe ekler.

Terimler bir toplam olarak yazılabilir. j. indisin katsayısı, ondan sonra gelen bütün boyutların çarpımıdır:

a_j katsayıları yalnız boyutlara bağlıdır, indislere bağlı değildir. Derleyici onları bir kez, derleme sırasında hesaplar. Formülün dikkat çekici bir sonucu, u₀'ın hiçbir katsayıda geçmemesidir. En dıştaki boyutun uzunluğu adres hesabına girmez. C'de bir fonksiyon parametresi int a[][4] diye yazılabilir ama int a[3][] diye yazılamaz; nedeni budur. İlk boyut adres için gereksizdir, sonrakiler ise zorunludur.

Her terimi ayrı hesaplamak çok sayıda çarpma gerektirir. Horner yöntemi (Horner's method), bir polinomu iç içe çarpımlarla hesaplayan yöntemdir ve burada da işe yarar. Adres terimi şöyle yeniden yazılabilir:

Hesap t = i₀ ile başlar ve her boyut için t = t · u_j + i_j yapılır. Döngü n − 1 kez döner, her turda bir çarpma ve bir toplama yapılır. Toplam n − 1 çarpma yeter. Üç boyutlu dizideki “paranteze alma” bu yöntemin n = 3 için özel hâlidir.

2.4.6Kod izleme: ofset()

Horner yöntemi, indis dizisini ve boyut dizisini alan genel bir fonksiyonla yazılır. Fonksiyon öğe biriminde konumu (ofseti) döndürür; bayt adresi alfa + t * s ile bulunur.

/* ind: indisler, ust: boyutlar, n: boyut sayısı */
int ofset(const int ind[], const int ust[], int n) {
  int j, t = ind[0];
  for (j = 1; j < n; j++)
    t = t * ust[j] + ind[j];            /* Horner */
  return t;               /* adres = alfa + t*s */
}

Parametrelerdeki const, fonksiyonun dizileri değiştirmeyeceğini belgeler. t en dıştaki indisle başlar. Döngü j = 1'den başladığı için ust[0] hiç okunmaz. En dıştaki boyutun adres hesabına girmediği kodda da böylece görülür.

Ara değer t = 2'nin anlamı ilginçtir. İki dilimin satırları art arda sayılırsa (dilim 0'ın satırları 0 ve 1, dilim 1'in satırları 2 ve 3) aranan öğe 2 numaralı satırdadır. Son adımda bu satır numarası satır uzunluğuyla (3) çarpılıp sütun indisi eklenince öğenin konumu çıkar. Hesap toplam iki çarpma kullanır, yani n − 1. Doğrudan formül de aynı sonucu verir: 1 · 2 · 3 + 0 · 3 + 2 = 8. Sürücü programda A[4][5][6] dizisi için [2][3][4]'ün ofseti de denenmiş ve fonksiyonun sonucu (82) gerçek dizideki farkla aynı çıkmıştır. ofset'in süresi boyut sayısıyla doğrusaldır, Θ(n). Boyut sayısı bir dizi için sabit olduğundan erişim, öğe sayısına göre O(1)'dir.

2.5Üçgen matrisler

Adres formülü yalnız derleyicinin işine yaramaz. Programcı da belleği kendi düzenleyip öğelerin yerini bir formülle bulabilir. Bu fikrin en sade uygulaması, yarısı boş olan matrisleri yalnız dolu yarılarıyla saklamaktır.

2.5.1Alt üçgen matris

Kare bir matris ana köşegeniyle ikiye bölünür. Bazı uygulamalarda yarılardan biri yeter. Şehirler arası uzaklık tablosunda i'den j'ye uzaklık j'den i'ye uzaklıkla aynıdır; tablonun yarısı öbür yarısının tekrarıdır. Doğrusal denklem sistemlerinin çözümünde de köşegenin üstü sıfır olan matrisler sık çıkar.

Sıfırları saklamaya gerek yoktur. Matrisin geri kalanı tek boyutlu bir ALT dizisinde satır satır tutulur. Kullanıcıya ise iki boyutlu bir matrisle çalışıyormuş gibi bir arayüz sunulur: a_ij istendiğinde fonksiyon onun ALT'taki konumunu hesaplar.

Formülü bulmak için yine aynı soru sorulur: a_ij'den önce ALT'ta kaç öğe vardır? i. satırda i + 1 öğe saklanır (sütun 0'dan i'ye kadar). Önceki satırlar 1 + 2 + … + i = i(i + 1)/2 öğe eder. Öğenin kendi satırında solunda j öğe vardır:

n × n bir alt üçgen matriste toplam 1 + 2 + … + n = n(n + 1)/2 öğe saklanır. Tam matris n² hücre ister. Kazanç n(n − 1)/2 hücredir ve büyük n'de belleğin yaklaşık yarısı demektir. Şekil 2.8 üzerinde formül denenebilir: a₂₁ için k = 2 · 3/2 + 1 = 4 bulunur ve ALT[4] gerçekten a₂₁'dir.

2.5.2Kod izleme: AltUcgenOku()

Aşağıdaki fonksiyon n × n bir alt üçgen matrisin saklanan öğelerini standart girdiden satır satır okur ve alt dizisine yerleştirir.

#define MAX_SIZE 100
void AltUcgenOku(int alt[], int n) {
  int i, j, k;
  if (n * (n + 1) / 2 > MAX_SIZE) {
    printf("Alt dizi boyutu yetersiz!\n"); exit(1);
  }
  for (i = 0; i < n; i++) {
    k = (i + 1) * i / 2;      /* öncekiler */
    for (j = 0; j <= i; j++)  /* j <= i */
      scanf("%d", &alt[k + j]);
  }
}

Kod satır satır şöyle çalışır:

• Önce saklanacak öğe sayısı n(n + 1)/2, dizinin kapasitesi MAX_SIZE ile karşılaştırılır. Sığmazsa ileti yazılır ve program sonlanır. Bu denetim olmasaydı büyük bir n dizinin sonundan taşmaya yol açardı.
• Dış döngü satırları gezer. k = (i + 1) * i / 2, i. satırdan önce yerleşmiş öğe sayısıdır; yani satırın alt'taki başlangıcıdır. Bölme çarpımdan sonra yapılır; i(i + 1) her zaman çift olduğundan bölme tamdır.
• İç döngü yalnız j <= i için döner; köşegenin üstündeki sıfırlar okunmaz. Her değer alt[k + j]'ye yazılır.

Fonksiyonun gövdesi her saklanan öğe için bir scanf yapar. İç döngünün toplam tur sayısı 1 + 2 + … + n = n(n + 1)/2'dir. Süre saklanan öğe sayısıyla orantılıdır, Θ(n²). Tam matrisi okumak n² tur sürerdi; üçgen gösterim sabit çarpanı yarıya indirir ama büyüme hızını değiştirmez. Sürücü programda alt dizisi okumadan sonra 3 1 4 1 5 9 2 6 5 3 olarak yazdırılmış ve tablo doğrulanmıştır.

2.5.3Erişim ve hata kodları: AltUcgenEris()

Okumadan sonra matrise erişmek için (i, j) çiftini ALT içindeki konuma çeviren bir fonksiyon gerekir. Fonksiyon iki istisnayı da ayırt etmelidir: indisler matrisin dışında olabilir ya da istenen öğe üst üçgende, yani saklanmayan sıfırlı bölgede olabilir.

int AltUcgenEris(int i, int j, int n) {
  if (i < 0 || i >= n || j < 0 || j >= n) {
    printf("Gecersiz indis\n");
    return -2;
  } else if (i < j) return -1;    /* üst üçgen: 0 */
  else return (i + 1) * i / 2 + j;   /* geçerli */
}
/* main: */
printf("%d\n", AltUcgenEris(2, 1, 4));
printf("%d\n", AltUcgenEris(1, 3, 4));
printf("%d\n", AltUcgenEris(4, 0, 4));

Fonksiyon önce sınırları denetler. İndislerden biri [0, n − 1] aralığının dışındaysa ileti yazar ve −2 döndürür. Sonra i < j olup olmadığına bakar. Öyleyse öğe üst üçgendedir; değeri sıfırdır ama ALT'ta yeri yoktur ve fonksiyon −1 döndürür. Geriye kalan durumda öğe alt üçgendedir ve konum formülle hesaplanır.

Sürücü programın çıktısı 4, -1, Gecersiz indis ve -2 satırlarından oluşur. Dönüş değerlerinin seçimi bilinçlidir. Geçerli konumlar 0, 1, 2, … gibi negatif olmayan sayılardır. Hata kodları {−1, −2} bu kümeyle kesişmez. Bu yüzden çağıran taraf dönüş değerine bakarak durumu her zaman ayırt edebilir: negatif değer bir istisna, sıfır ya da pozitif değer gerçek bir konumdur. Hata kodu olarak örneğin 0 seçilseydi, a₀₀'ın konumuyla karışırdı.

Fonksiyon girdiye bağlı döngü içermez: birkaç karşılaştırma ve bir formül hesabı yapar. Süresi O(1)'dir. Tam matristeki a[i][j] erişimi kadar hızlıdır, ama yarı bellekle çalışır.

2.5.4Öteki üçgenler ve simetrik matris

Saklanan yarı, köşegenin hangi yanında olduğuna göre dört biçimde olabilir. Her birinde konum formülü aynı yöntemle çıkarılır: önceki satırlardaki öğeler toplanır, sonra satır içindeki sıra eklenir. Tablo 2.13 dört durumun sonucunu verir.

Üst sağ üçgende r. satırda n − r öğe vardır. i. satırdan önceki toplam n + (n − 1) + … + (n − i + 1) = i · n − i(i − 1)/2'dir. Satırın ilk saklanan öğesi köşegendedir (j = i), bu yüzden satır içindeki sıra j − i'dir. Sol üst üçgende satır uzunlukları aynıdır ama satır 0. sütundan başlar; sıra doğrudan j olur. Sağ alt üçgende i. satır i + 1 öğe tutar ve j = n − 1 − i sütunundan başlar; sıra j − (n − 1 − i)'dir. Not için yazılan bir döngü, n = 1'den 8'e kadar her matriste dört formülü denemiştir. Formüllerin verdiği konumlar, satır satır sayılan konumlarla hep aynı çıkmıştır.

Gerçek bir simetrik matriste (a_ij = a_ji) üst üçgen sıfır değil, alt üçgenin aynasıdır. Bu durumda AltUcgenEris üst üçgen için −1 döndürmek yerine indisleri yer değiştirir: i < j ise k = j(j + 1)/2 + i. Uzaklık tablosu ya da bir çizgenin yönsüz komşuluk matrisi böyle saklanabilir. Bellek yine yarıya iner ve hiçbir bilgi kaybolmaz.

2.6Kuşak matrisler

Üçgen matriste saklanan bölge köşegenin bir yanıydı. Pek çok sayısal problemde ise sıfırdan farklı öğeler köşegenin iki yanında, dar bir şeritte toplanır. Isı iletimi ya da titreşim gibi fizik problemlerinin sayısal çözümünde her bilinmeyen yalnız komşularıyla ilişkilidir; ortaya çıkan matrisin köşegenden uzak öğeleri sıfırdır. Böyle bir matrisi tam saklamak belleğin büyük kısmını sıfırlara harcamak demektir.

2.6.1Tanım ve öğe sayısı

Şekil 2.10'daki matriste köşegen ve altındaki iki kuşak (a = 3) ile köşegenin üstündeki bir kuşak (b = 2, köşegen dâhil) saklanır. d₀₂, d₀₃, d₁₃ ve d₃₀ kuşak dışında kalır.

Saklanan öğe sayısını bulmak için kuşaklar tek tek sayılır. Ana köşegende n öğe vardır. Köşegenden bir uzak kuşakta (altta ya da üstte) n − 1, iki uzak kuşakta n − 2 öğe bulunur. Genel olarak köşegene uzaklığı t olan bir kuşakta n − |t| öğe vardır. Toplam a + b − 1 kuşak saklanır, çünkü köşegen hem a'da hem b'de sayılmıştır. Her kuşak n öğeli olsaydı toplam n(a + b − 1) olurdu. Alt kuşaklardaki eksikler 1 + 2 + … + (a − 1) = a(a − 1)/2, üst kuşaklardaki eksikler b(b − 1)/2'dir:

Örnekte 4 · 4 − 3 − 1 = 12 öğe saklanır; tam matris 16 hücre isterdi. Kazanç küçük görünür, çünkü matris küçüktür. n = 1000, a = b = 3 olan bir matriste ise tam matris bir milyon hücre isterken kuşak gösterimi 1000 · 5 − 3 − 3 = 4994 hücreyle yetinir.

Saklama sorunu böylece çözülür. Asıl soru, saklanan öğelere hızlı erişilip erişilemeyeceğidir. Öğeler sıkıştırıldığında konum hesabı da karmaşıklaşır. Kuşak matris gösteriminin değeri, erişimin hâlâ sabit sürede yapılabilmesine bağlıdır.

2.6.2Kuşak numarası ve ARA dizisi

Erişimin anahtarı, bir öğenin hangi kuşakta olduğunu indislerinden hemen anlamaktır. Aynı kuşaktaki öğelerde j − i farkı sabittir. Örneğin d₂₀ ve d₃₁ aynı kuşaktadır: 0 − 2 = 1 − 3 = −2. Bu farka kuşak numarası denir. Ana köşegenin numarası 0'dır; negatif numaralar alt kuşakları, pozitif numaralar üst kuşakları gösterir.

Geçerli kuşak numaraları [1 − a, b − 1] kapalı aralığındadır. Örnekte bu aralık [−2, 1]'dir. Numarası bu aralığın dışında kalan öğeler sabit bölgededir ve saklanmaz. Böylece bir öğenin kuşak içinde mi dışında mı olduğu tek bir çıkarma ve iki karşılaştırmayla anlaşılır.

Öğeler kusak dizisinde kuşak kuşak, en alttaki kuşaktan başlayarak saklanır. Bir öğenin konumu iki parçadan oluşur: kuşağının kusak içindeki başlangıcı ve öğenin kuşak içindeki sırası.

• Kuşak başlangıcı. Her kuşağın başlangıcı ara (ARA) dizisinde tutulur. Dizide a + b − 1 öğe vardır, yani kuşak başına bir öğe. C'de dizi indisi negatif olamayacağı için kuşak numarası a − 1 kaydırılarak kullanılır: t numaralı kuşağın başlangıcı ara[t + a - 1]'dedir. Örnekte ara = {0, 2, 5, 9} olur; −2 numaralı kuşak 0'dan, −1 numaralı kuşak 2'den, köşegen 5'ten, +1 numaralı kuşak 9'dan başlar.
• Kuşak içindeki sıra. Bir alt kuşağın ilk öğesi 0. sütundadır; kuşak boyunca her adımda sütun bir artar. Bu yüzden alt kuşakta sıra j'dir. Bir üst kuşağın ilk öğesi 0. satırdadır; sıra i'dir. Köşegende i = j olduğundan ikisi de aynı sonucu verir.

Tasarımın arkasındaki düşünce şudur: her şeyi kısıtlıymış gibi inceleyip erişim mekanizmasını bu kısıtlardan çıkarmak. Kuşak numarasının sabit olması, kuşak uzunluklarının n − |t| olması ve ilk öğenin yerinin bilinmesi birer kısıttır. Üçü birlikte, karmaşık görünen bir sıkıştırmayı birkaç aritmetik işleme indirger.

2.6.3Kod izleme: KusakMatrisKur()

Aşağıdaki fonksiyon kuşak matrisin öğelerini standart girdiden okur. Girdi kuşak kuşak, en alttaki kuşaktan başlayarak gelir. Fonksiyon her kuşağın başlangıcını ara'ya yazar ve öğeleri kusak'a yerleştirir. abs fonksiyonu <stdlib.h> başlığındadır.

void KusakMatrisKur(int kusak[], int ara[],
                    int n, int a, int b) {
  int i, k, toplamoge = 0;   /* önceki kuşaklar */
  if (n*(a+b-1) - a*(a-1)/2 - b*(b-1)/2 > MAX_SIZE) {
    printf("Bellek yetersiz!\n"); exit(-1);
  }
  for (i = 1 - a; i <= b - 1; i++) {  /* kuşak kuşak */
    ara[i + a - 1] = toplamoge;     /* kuşak başı */
    for (k = 0; k <= n - abs(i) - 1; k++)
      scanf("%d", &kusak[ara[i + a - 1] + k]);
    toplamoge += n - abs(i);
  }
}

Kod satır satır şöyle çalışır:

• toplamoge, o ana kadar yerleşmiş öğe sayısıdır; yani sıradaki kuşağın başlangıcıdır.
• Önce saklanacak öğe sayısı MAX_SIZE ile karşılaştırılır. Formül, kuşak uzunluklarının toplamından çıkan öğe sayısıdır.
• Dış döngü kuşak numarası i'yi 1 − a'dan b − 1'e kadar gezer. Burada i bir satır indisi değil, kuşak numarasıdır.
• ara[i + a - 1] = toplamoge kuşağın başlangıcını kaydeder.
• İç döngü kuşağın n − |i| öğesini okur: k, 0'dan n − |i| − 1'e kadar gider. Her değer kusak[ara[i + a - 1] + k]'ye yazılır.
• Kuşak bitince toplamoge, kuşağın uzunluğu kadar artar.

Sonuçta toplamoge 12'ye ulaşır; bu, öğe sayısı formülünün verdiği değerdir. Sürücü programın yazdırdığı ara ve kusak dizileri tabloyla aynıdır. Fonksiyon her saklanan öğe için bir scanf yapar ve dış döngü a + b − 1 kez döner. Süre O(a + b + saklanan öğe sayısı)'dır; kuşak sayısı öğe sayısını aşamayacağından bu O(saklanan öğe sayısı)'dır. Ek bellek ara dizisinin a + b − 1 hücresidir.

2.6.4Kod izleme: KusakMatrisEris()

Erişim fonksiyonu (i, j) çiftini kusak içindeki konuma çevirir. Kuşak dışındaki öğeler için iki ayrı hata kodu döndürür; böylece üst ve alt sabit bölge birbirinden ayrılabilir.

int KusakMatrisEris(int i, int j, int n, int a,
                    int b, int ara[]) {
  if (i < 0 || j < 0 || i >= n || j >= n) {
    printf("Indis tasmasi\n"); return -3;
  } else if (j - i >= 1) {         /* üst üçgen */
    if (j - i < b)               /* geçerli kuşak */
      return ara[j - i + a - 1] + i;
    else return -1;              /* üst sabit bölge */
  } else if (i - j < a)          /* köşegen / alt */
    return ara[j - i + a - 1] + j;
  else
    return -2;                   /* alt sabit bölge */
}

Fonksiyonun mantığı dört duruma ayrılır:

• İndislerden biri matrisin dışındaysa ileti yazılır ve −3 döner.
• j − i ≥ 1 ise öğe köşegenin üstündedir. Kuşak numarası b'den küçükse öğe geçerli bir üst kuşaktadır ve konum ara[j - i + a - 1] + i'dir. Değilse öğe üst sabit bölgededir; −1 döner.
• Aksi hâlde öğe köşegende ya da altındadır. i − j < a ise geçerli bir alt kuşaktadır (köşegen dâhil) ve konum ara[j - i + a - 1] + j'dir.
• Hiçbiri değilse öğe alt sabit bölgededir; −2 döner.

Sürücü programda dört sorgu aynı sonuçları vermiştir. Ayrıca bütün (i, j) çiftleri için erişim fonksiyonu çağrılıp matris yeniden kurulmuş, kuşak dışı öğelere 0 yazılmıştır. Ortaya çıkan matris örnekteki değerlerle aynıdır. Fonksiyon her durumda sabit sayıda karşılaştırma ve aritmetik işlem yapar; girdiye bağlı bir döngüsü yoktur. Süresi O(1)'dir.

2.6.5ARA dizisi mi, formül mü?

KusakMatrisEris sabit sürede çalışır, çünkü kuşak başlangıçları önceden ara dizisine yazılmıştır. Bu dizi olmasaydı her erişimde önceki kuşakların uzunluklarını bir döngüyle toplamak gerekirdi ve erişim O(a + b)'ye çıkardı. ara bunu önler ama bedeli vardır: fazladan bellek harcar ve matrisin parametreleri değişirse yeniden kurulmalıdır. Bu da programı dinamik olmaktan uzaklaştırır.

Burada genel bir tasarım ilkesi görülür. Performansı gerçekten artırıyorsa, makul ölçüde fazladan bellek kullanmakta sakınca yoktur. ara yalnız a + b − 1 hücredir; saklanan öğelerin yanında çok küçüktür. Yine de aynı sonucu hiç ek bellek kullanmadan almak mümkündür: kuşak başlangıcı da kapalı bir formülle hesaplanabilir.

/* t: kuşak no (1-a..b-1); ara[t+a-1] ile aynı */
int kusak_basi(int t, int n, int a) {
  if (t <= 0)                     /* alt kuşaklar */
    return (t + a - 1) * n
           - (a * (a - 1) + t * (1 - t)) / 2;
  return (a - 1) * n - a * (a - 1) / 2  /* t=0 başı */
         + t * n - t * (t - 1) / 2;
}

Formül iki durumda çıkarılır.

• Alt kuşaklar ve köşegen (t ≤ 0). t'den önce 1 − a, …, t − 1 numaralı t + a − 1 kuşak vardır. Hepsi n öğeli olsaydı toplam (t + a − 1) · n olurdu. Eksikler, bu kuşakların numaralarının mutlak değerleridir: (−t + 1) + … + (a − 1) = a(a − 1)/2 − t(t − 1)/2. Kodda bu ifade (a * (a - 1) + t * (1 - t)) / 2 olarak yazılmıştır; iki biçim aynıdır.
• Üst kuşaklar (t > 0). Köşegenin başlangıcı, yukarıdaki formülde t = 0 konarak bulunur: (a − 1) · n − a(a − 1)/2. Ona köşegen ve 1, …, t − 1 numaralı kuşakların uzunlukları eklenir: n + (n − 1) + … + (n − t + 1) = t · n − t(t − 1)/2.

n = 4, a = 3 için t = −2, −1, 0, 1 değerleri sırayla 0, 2, 5 ve 9 verir; ara ile aynıdır. Not için yazılan bir döngü n ≤ 11 ve bütün a, b ≤ n değerleri için 4 356 kuşak başlangıcını tek tek saymıştır. Formülle hiç fark çıkmamıştır. Formülle erişim kusak_basi(j - i, n, a) + (j > i ? i : j) olur. Bu da O(1)'dir; birkaç çarpma fazladan yapılır ama dizi gerekmez. Hangisinin seçileceği, belleğin mi işlem süresinin mi daha değerli olduğuna bağlıdır.

2.6.6&& işlecinin değerlendirme sırası

Erişim fonksiyonlarındaki koşullar i < 0 || i >= n || … gibi birleşik ifadelerdir. Bu tür ifadeler için sık duyulan bir kanı vardır. Buna göre derleyicinin ifadeyi soldan sağa mı sağdan sola mı taradığı bilinemez. Bu yüzden aşağıdaki iki biçimden ikincisi daha güvenlidir.

/* 1 */ if (i < n && a[i] != 0) ...

/* 2 */ if (i < n)
          if (a[i] != 0) ...

Bu kanı yanlıştır. C standardı && ve || işleçleri için soldan sağa değerlendirmeyi ve kısa devre değerlendirmeyi (short-circuit evaluation) garanti eder (C99 §6.5.13–14). &&'nin sol tarafı yanlışsa sonuç zaten yanlıştır ve sağ taraf hiç hesaplanmaz. ||'de sol taraf doğruysa sağ taraf hesaplanmaz. Birinci biçimde i < n yanlışsa a[i] hiç okunmaz. İki biçim aynı derecede güvenlidir; birincisi C'de yaygın ve doğru bir kalıptır. Sürücü programda üç öğeli bir dizide i = n = 3 iken birinci biçim denenmiş; koşul a[3] okunmadan yanlış çıkmıştır.

Asıl tuzaklar başka yerdedir. & (bit düzeyi VE) ve | kısa devre yapmaz; i < n & a[i] != 0 yazılırsa iki taraf da hesaplanır ve a[n] okunur. Ayrıca f(x) + g(x) gibi sıradan bir ifadede işlenenlerin hangi sırayla hesaplanacağı standartta belirtilmemiştir. f ve g aynı küresel değişkeni değiştiriyorsa sonuç derleyiciye göre farklı çıkabilir. Değerlendirme sırası yalnız &&, ||, ?: ve virgül işlecinde garanti altındadır.

2.7Yapılar ve birlikler

Dizinin bütün öğeleri aynı tiptedir. Gerçek dünyadaki kayıtlar ise farklı tipte parçalardan oluşur: bir öğrencinin numarası tamsayı, adı karakter dizisi, not ortalaması ondalıklı sayıdır. C bu tür kayıtları struct ile tanımlar. union ise birkaç alanın aynı belleği paylaştığı özel bir kayıt türüdür. Bu kesim iki yapıyı, bellekteki görünümlerini ve hizalamanın boyut üzerindeki etkisini ele alır.

2.7.1struct

typedef struct {
  char ad[10];
  int yas;
  float maas;
} insan;

insan k1, k2;
strcpy(k1.ad, "Ali");
k1.yas = 21;
k1.maas = 3500.0f;
k2 = k1;          /* alan alan kopyalanır */
/* if (k1 == k2) -> DERLENMEZ */

Kod satır satır şöyle çalışır:

• typedef struct { … } insan; adsız bir yapı tanımlar ve ona insan adını verir. typedef, var olan bir tipe yeni bir ad veren bildirimdir. Bu sayede değişken bildirirken her seferinde struct yazmak gerekmez: insan k1, k2; yeterlidir.
• k1.ad bir char dizisidir. Dizilere atama yapılamadığı için ad strcpy ile kopyalanır. k1.yas ve k1.maas sıradan değişkenler gibi atanır. 3500.0f sonundaki f, sabitin float olduğunu belirtir.
• k2 = k1; bütün yapıyı alan alan kopyalar. İlginç olan şudur: yapının içindeki ad dizisi de kopyalanır. Tek başına bir diziye atama yapılamaz, ama dizi bir yapının alanıysa yapı ataması onu da taşır.
• k1 == k2 derlenmez. C yapılar için eşitlik işleci tanımlamaz. Nedeni hizalamadır: alanlar arasında anlamsız dolgu baytları (padding) bulunabilir ve bayt bayt karşılaştırma yanlış sonuç verebilir. İki yapıyı karşılaştırmak için alan alan karşılaştıran bir fonksiyon yazılır; char dizisi alanları strcmp ile karşılaştırılır.

Yapılar fonksiyonlara çoğu zaman işaretçiyle geçirilir. Yapı değerle geçirilirse bütün alanları kopyalanır; büyük yapılarda bu pahalıdır. İşaretçiyle geçirmek yalnız bir adres kopyalar. insan *p = &k2; tanımından sonra p->yas ile (*p).yas aynı alanı verir. Parantez gereklidir, çünkü . işlecinin önceliği *'dan yüksektir: *p.yas, “p.yas'ın gösterdiği yer” anlamına gelir ve derlenmez. Ok işleci (arrow operator) bu yazımı kısaltmak için vardır.

Sürücü programda sizeof(insan) 20 çıkmıştır. Alanların toplamı 10 + 4 + 4 = 18 bayttır. Aradaki 2 bayt hizalamadan gelir: yas alanı 4'ün katı olan bir adreste başlamalıdır ve ad 10. baytta bittiği için iki dolgu baytı eklenir.

2.7.2İç içe ve kendine başvuran yapılar

Bir yapının alanı başka bir yapı olabilir. Ayrıca bir yapı, kendi türünden bir nesneyi gösteren bir işaretçi alanı taşıyabilir.

typedef struct {
  int gun, ay, yil;
} tarih;

typedef struct {
  char ad[10];
  tarih dogum;          /* iç içe yapı */
} kisi;
/* k.dogum.yil = 2004; */

typedef struct liste {
  char veri;
  struct liste *bag;    /* kendine başvuru */
} liste;

kisi yapısının dogum alanı bir tarih yapısıdır. İç içe alanlara nokta işleci art arda uygulanarak erişilir: k.dogum.yil = 2004;. Sürücü programda sizeof(kisi) 24 çıkmıştır: 10 baytlık ad, 2 dolgu baytı ve 12 baytlık tarih.

liste yapısı farklıdır. bag alanının tipi struct liste *, yani yapının kendi türüne işaretçidir. Bu tür yapılara kendine başvuran yapı (self-referential struct) denir. Tanımda yapıya bir etiket adı (struct liste) verilmesi zorunludur. typedef ile verilen liste adı bildirim bitene kadar henüz tanımlı değildir; alanın tipi ancak etiketle yazılabilir.

Şekil 2.13 böyle üç yapının birbirine bağlanmasını gösterir. Her düğüm sonrakinin adresini tutar; zincirin sonu NULL ile belirtilir. Sürücü programda üç düğüm a, b, c değerleriyle kurulmuş ve for (q = &a1; q != NULL; q = q->bag) döngüsüyle sırayla yazdırılmıştır. Bu yapı, bağlı listelerin, ağaçların ve çizgelerin temelidir. Dizinin aksine düğümler bellekte ardışık olmak zorunda değildir; araya ekleme yalnız birkaç bağın değiştirilmesiyle yapılır.

Bir yapı kendi türünden bir alan içeremez. struct liste { char veri; struct liste sonraki; }; gibi bir tanımda yapının boyu kendi boyunu içermek zorunda kalırdı; bu sonsuz bir boyut demektir ve derlenmez. Kendi türüne işaretçi ise sorun yaratmaz, çünkü işaretçinin boyu gösterdiği tipin boyundan bağımsızdır (64 bitlik sistemde 8 bayt). Sürücüde sizeof(liste) 16 çıkmıştır: 1 baytlık karakter, 7 dolgu baytı ve 8 baytlık işaretçi.

2.7.3union ve hizalama

Birlik, bir kaydın türüne göre farklı bilgiler taşıması gerektiğinde bellek kazandırır. Ders kitabındaki örnekte bir kişinin cinsiyetine göre iki farklı bilgi tutulur. İki alan hiçbir zaman aynı anda gerekmediği için aynı belleği paylaşabilir.

typedef struct {
  enum { KADIN, ERKEK } tur;   /* etiket */
  union {
    int cocuk_sayisi;          /* KADIN ise */
    int sakal;                 /* ERKEK ise */
  } u;
} cinsiyet;

cinsiyet c;
c.tur = ERKEK;
c.u.sakal = 0;   /* yalnız etiketle uyumlu alanı oku */

tur alanı bir sayım tipidir (enumeration, enum): KADIN 0, ERKEK 1 değerini alan adlandırılmış sabitlerdir. Bu alan, birliğin hangi alanının geçerli olduğunu gösteren bir etikettir. Böyle bir yapıya etiketli union (tagged union) denir. Kod, etiketi ERKEK yapıp ardından yalnız onunla uyumlu sakal alanını kullanır.

Etiketin doğru tutulması tamamen programcının işidir. C, birliğin hangi alanına en son yazıldığını izlemez. c.u.sakal = 0; yazıldıktan sonra c.u.cocuk_sayisi okunursa aynı dört bayt bu kez başka bir anlamla yorumlanır. Burada iki alan da int olduğu için sonuç 0 çıkar, ama alanlar farklı tipte olsaydı anlamsız bir değer okunurdu. Doğru kalıp, birliğe her erişimden önce etikete bakmaktır: if (c.tur == ERKEK) … c.u.sakal …. Sürücü programda sizeof c.u 4, sizeof c ise 8 bayt çıkmıştır: 4 baytlık etiket ve 4 baytlık birlik. Ayrı iki alan kullanılsaydı yapı 12 bayt olurdu.

Yapı boyunu belirleyen asıl etken hizalamadır (alignment). İşlemciler çoğu tipi kendi boyunun katı olan adreslerden en hızlı biçimde okur; bazı işlemciler hizasız okumaya hiç izin vermez. Bu yüzden derleyici her alanı uygun bir adres katına yerleştirir ve gerekirse araya dolgu baytları ekler. Yapının toplam boyu da en büyük hizalama gereğinin katına yuvarlanır; böylece yapı dizilerinde her öğe doğru hizada başlar.

Şekil 2.14 aynı üç alanın iki farklı sırasını karşılaştırır. Birinci sırada c 0. bayta yerleşir; x 4'ün katında başlamak zorunda olduğu için 1, 2, 3. baytlar dolgu olur ve x 4–7. baytları kaplar. d 8. baytta durur. Yapının boyu 4'ün katı olmalıdır, bu yüzden sona üç dolgu baytı eklenir: toplam 12. İkinci sırada x 0–3, c 4, d 5. baytları kaplar; sona iki dolgu baytı eklenir ve toplam 8 olur. Aynı veri üçte bir daha az bellekle tutulur. Sürücü programda bu iki yapının boyları 12 ve 8, offsetof ile ölçülen x konumu ise birincisinde 4 çıkmıştır.

Pratik kural, alanları büyükten küçüğe doğru sıralamaktır. Hizalama kuralları derleyiciye ve işlemciye bağlıdır; burada verilen değerler yaygın 32 ve 64 bitlik sistemler için tipiktir. Dosyaya ya da ağa ham bayt olarak yazılan yapılarda dolgu baytları taşınabilirlik sorunu çıkarır. Bu yüzden böyle durumlarda alanlar tek tek yazılır.

2.7.4Kod izleme: sinif_ort()

Yapılar dizilerde toplanabilir. Aşağıdaki fonksiyon bir sınıfın öğrenci kayıtlarını içeren diziyi alır ve not ortalamalarının ortalamasını döndürür. Bir yapının bütün öğelerine belirli bir sırayla birer kez uğramaya gezinme (traversal) denir.

typedef struct {
  int no;
  char ad[16];
  double ort;
} Ogrenci;

double sinif_ort(const Ogrenci s[], int n) {
  double top = 0.0;
  int i;
  for (i = 0; i < n; i++)
    top += s[i].ort;               /* . ile alan */
  return n > 0 ? top / n : 0.0;    /* boş sınıf */
}

Kod satır satır şöyle çalışır:

• const Ogrenci s[] parametresi bir işaretçidir; dizi kopyalanmaz. const, fonksiyonun kayıtları değiştirmeyeceğini belgeler ve yanlışlıkla bir alana yazılırsa derleyicinin hata vermesini sağlar.
• s[i].ort önce i. kaydı bulur (α + i · sizeof(Ogrenci) adresi), sonra onun ort alanını okur. Yapı dizisinde de adres formülü aynen geçerlidir; yalnız öğe boyu yapının boyudur.
• n > 0 ? top / n : 0.0, boş sınıfta sıfıra bölmeyi önler. Kayan noktalı sayılarda sıfıra bölme programı durdurmaz ama sonsuz ya da NaN üretir; bu değer sessizce sonraki hesaplara yayılır.

Fonksiyon her kayda bir kez uğrar; süresi Θ(n), ek belleği O(1)'dir. Sürücü programda sonuç %.2f biçimiyle 3.10 olarak yazdırılmıştır. Ara toplamların tam değerleri ise 3.2000000000000002, 5.8000000000000007 ve 9.3000000000000007'dir. 3,2 gibi ondalık sayılar ikili tabanda tam gösterilemez ve küçük yuvarlama hataları birikir. Bu yüzden kayan noktalı sonuçlar == ile karşılaştırılmaz; ya belirli bir basamakla yazdırılır ya da küçük bir tolerans içinde karşılaştırılır.

Ogrenci yapısı da hizalamanın etkisini gösterir. 4 baytlık no ve 16 baytlık ad 20 bayt eder. double 8'in katında başlamalıdır; bu yüzden 4 dolgu baytı eklenir ve ort 24. baytta başlar. Toplam boy 32 bayttır. Sürücü programda offsetof(Ogrenci, ort) 24, sizeof(Ogrenci) 32 çıkmıştır.

2.8Dizgeler

Metin, programların en çok işlediği veri türlerinden biridir. Pek çok dil metin için ayrı bir tip sunar. C'de ise metin, özel bir kurala uyan sıradan bir char dizisidir. Bu sadelik hız kazandırır ama dikkatsiz kullanıldığında en yaygın güvenlik açıklarının da kaynağı olur.

2.8.1'\0' ile biten char dizisi

char s[] = "dog";      /* 4 bayt: d o g \0 */
char t[10];
char *p = "dog";       /* salt okunur sabit */

strlen(s)   /* 3 : \0'a kadar */
sizeof s    /* 4 : dizinin boyutu */

strcpy(t, s);                 /* t yeterince büyük mü? */
snprintf(t, sizeof t, "%s!", s);   /* güvenli */
if (strcmp(s, "dog") == 0) ...     /* == değil! */

Kod satır satır şöyle çalışır:

• char s[] = "dog"; dört baytlık bir dizi ayırır. Derleyici dizgeyi kopyalar ve sona '\0' ekler; boyutu bu yüzden 3 değil 4'tür (Şekil 2.16).
• char t[10]; on karakterlik boş bir alandır; içeriği henüz belirsizdir.
• char *p = "dog"; bir dizi ayırmaz. p, programın salt okunur bölgesindeki bir dizge sabitini gösterir. p[0] = 'D'; yazmak tanımsız davranıştır ve çoğu sistemde programı çökertir. Bu yüzden böyle işaretçiler const char *p olarak bildirilmelidir; o zaman derleyici yazma girişimini yakalar.
• strlen(s) 3, sizeof s 4 verir. strlen karakterleri '\0''a kadar sayar; sizeof ise dizinin kapladığı bellektir.
• strcpy(t, s), s'yi sonlandırıcısıyla birlikte t'ye kopyalar. strcpy hedefin boyunu bilmez; t yeterince büyük değilse sonundan taşar. Burada 10 bayt 4 baytlık dizge için yeterlidir.
• snprintf(t, sizeof t, "%s!", s) hedefin boyunu ikinci parametre olarak alır ve en çok sizeof t - 1 karakter yazıp sonuna her zaman '\0' koyar. Taşma imkânsızdır. Sürücüde t'nin yeni değeri dog! olmuştur.
• strcmp(s, "dog") == 0 iki dizgenin içeriğini karakter karakter karşılaştırır. s == "dog" yazılsaydı içerikler değil adresler karşılaştırılırdı ve sonuç büyük olasılıkla yanlış çıkardı.

<string.h> başlığı dizgeler için bir dizi fonksiyon sunar. Tablo 2.17 en çok kullanılanları özetler. Bu fonksiyonların hepsi dizgenin sonunu '\0''dan anlar. Sonlandırıcısı olmayan bir dizi bu fonksiyonlara verilirse, belleğin ilerisinde rastlantısal bir sıfır bulunana kadar okumaya devam ederler.

strncpy'nin bir tuzağı vardır. Kaynak, verilen sınırdan uzunsa strncpy hedefe '\0' koymaz; sonuç dizge değildir. Bu yüzden güvenli kopya için snprintf ya da sınır bir eksik tutularak sonradan elle '\0' yazılan strncpy tercih edilir.

2.8.2Kod izleme: uzunluk()

Aşağıdaki fonksiyon strlen'in yaptığı işi açıkça yazar. Bir işaretçiyi '\0''a gelene kadar ilerletir ve başlangıçtan ne kadar uzaklaştığını döndürür.

size_t uzunluk(const char *s) {
  const char *p = s;
  while (*p != '\0')     /* sonlandırıcıya dek */
    p++;
  return (size_t)(p - s);  /* işaretçi farkı */
}

/* uzunluk("veri") */

p başlangıçta s ile aynı yeri gösterir. Döngü her turda *p'yi sonlandırıcıyla karşılaştırır; farklıysa p'yi bir karakter (1 bayt) ilerletir. Döngü bittiğinde p sonlandırıcıyı gösterir. İki işaretçinin farkı p - s, aralarındaki öğe sayısıdır; bu da dizgenin uzunluğudur. Fark ptrdiff_t tipindedir ve size_t'ye dönüştürülerek döndürülür.

Uzunluğu bulmak için dizge baştan sona taranır: süre Θ(n)'dir. Dizi gibi uzunluğu ayrıca tutulan yapılardan farklı olarak C dizgesinin uzunluğu her seferinde yeniden hesaplanır. Bu, sık rastlanan bir verimsizliğe yol açar:

for (i = 0; i < strlen(s); i++)   /* her turda strlen! */
    ...

Döngü koşulu her turda yeniden hesaplanır ve her hesap n karakteri tarar. n tur için toplam n · n karakter okunur; döngü O(n²) olur. Bir milyon karakterlik bir metinde bu, bir milyon yerine bir trilyon okuma demektir. Doğrusu uzunluğu döngüden önce bir kez hesaplamaktır: size_t len = strlen(s); for (i = 0; i < len; i++). Döngü gövdesi dizgeyi değiştirmiyorsa iyi derleyiciler bu dönüşümü kendileri yapabilir, ama buna güvenmemek gerekir.

2.9Matris işlemleri

İki boyutlu diziler en çok matris hesaplarında kullanılır. Bu kesim matris toplamayı ve çarpmayı inceler; özellikle çarpmanın adım sayısını tam olarak çıkarır. Örneklerde N derleme sırasında tanımlı bir sabittir ve matrisler int a[][N] biçiminde geçirilir. İkinci boyutun yazılması zorunludur, çünkü adres hesabı satır uzunluğuna ihtiyaç duyar.

2.9.1Matris toplama

Aynı boyutlu iki matrisin toplamında her hücre, iki matrisin aynı konumdaki hücrelerinin toplamıdır. m × N matrisler için kod iki iç içe döngüden oluşur.

void topla(int a[][N], int b[][N], int c[][N], int m) {
    int i, j;
    for (i = 0; i < m; i++)
        for (j = 0; j < N; j++)
            c[i][j] = a[i][j] + b[i][j];
}

İç döngü gövdesi her hücre için bir kez, toplam m · N kez çalışır. Döngü denetimleri de bu sayıyla orantılıdır. Süre Θ(mN)'dir; n × n kare matrislerde Θ(n²). Sonuç matrisi dışında ek bellek gerekmez. Her hücre bir kez okunup bir kez yazıldığı için bundan daha hızlı bir toplama algoritması yoktur: girdinin her hücresine en az bir kez bakmak gerekir. Sürücüde 2 × 3 iki matrisin toplamı denenmiş ve beklenen sonuç alınmıştır.

2.9.2Kod izleme: mult()

A ve B iki n × n matris olsun. Çarpım C = AB'nin her hücresi, A'nın bir satırı ile B'nin bir sütununun iç çarpımıdır:

#define N 2
void mult(int a[][N], int b[][N], int c[][N]) {
  int i, j, k;
  for (i = 0; i < N; i++)
    for (j = 0; j < N; j++) {
      c[i][j] = 0;
      for (k = 0; k < N; k++)
        c[i][j] += a[i][k] * b[k][j];
    }
}

Dış iki döngü sonuç matrisinin hücrelerini gezer. Her hücre önce sıfırlanır, sonra en içteki döngü n çarpımı toplar. A = [[1, 2], [3, 4]] ve B = [[5, 6], [7, 8]] için izleme Tablo 2.19'da verilmiştir.

Sürücü program sonucu [[19, 22], [43, 50]] olarak yazdırmıştır. En içteki atama sekiz kez, yani N³ kez çalışmıştır. n büyüdükçe bu sayı küp olarak büyür; matris boyu iki katına çıkınca iş sekiz katına çıkar.

2.9.3Adım sayısı, dikdörtgen matrisler ve transpoz

Çarpmanın tam adım sayısı her satırın kaç kez çalıştığı sayılarak bulunur. Bir for döngüsünün koşulu, gövdenin çalışma sayısından bir fazla denetlenir: son denetim yanlış çıkar ve döngü biter. Tablo 2.20 satır satır sayımı verir.

Toplam (n + 1) + (n² + n) + n² + (n³ + n²) + n³ terimlerinin toplanmasıyla bulunur. Baskın terim 2n³'tür; süre Θ(n³)'tür. Yapılan çarpma sayısı tam n³'tür. Not için yazılan sayaçlı bir sürümde adımlar n = 1'den 9'a kadar sayılmış ve formülle aynı çıkmıştır (örneğin n = 2'de 33, n = 3'te 88).

Matrisler kare olmak zorunda değildir. m × n bir matris ile n × p bir matrisin çarpımı m × p boyutludur; yani m · p hücresi vardır. Her hücre n çarpımın toplamıdır. Toplam çarpma sayısı ve süre Θ(m · n · p)'dir. Bu sonuç, art arda çarpılan matrislerde çarpma sırasının neden önemli olduğunu da açıklar. (AB)C ile A(BC) aynı sonucu verir ama çok farklı sayıda çarpma gerektirebilir.

Bir matrisin transpozu (transpose), satırlarıyla sütunlarının yer değiştirmiş hâlidir: a_ij ile a_ji takas edilir. Kare bir matriste bu iş ek dizi kullanmadan, yerinde (in place) yapılabilir.

void transpoz(int a[][N], int n) {
    int i, j, t;
    for (i = 0; i < n; i++)
        for (j = i + 1; j < n; j++) { /* yalnız üst üçgen */
            t = a[i][j];
            a[i][j] = a[j][i];
            a[j][i] = t;
        }
}

İç döngü j = i + 1'den başlar; yalnız köşegenin üstündeki hücreler gezilir. Her takas, bir üst üçgen hücresini karşılığındaki alt üçgen hücresiyle değiştirir. Döngü j = 0'dan başlasaydı her çift iki kez takas edilirdi: ilk takas transpozu alır, ikincisi geri çevirir ve matris hiç değişmemiş olurdu. Köşegen hücreleri kendi yerlerinde kalır. Takas sayısı (n − 1) + (n − 2) + … + 0 = n(n − 1)/2'dir; süre Θ(n²), ek bellek tek bir geçici değişkendir. Sürücüde 3 × 3 bir matris üç takasla transpoz edilmiştir. Kare olmayan bir matrisin yerinde transpozu çok daha zordur, çünkü satır uzunluğu değişir ve öğeler dizide çevrimler hâlinde yer değiştirir.

2.10Karmaşıklık özeti

Tablo 2.21 bölümdeki işlemlerin süre ve ek bellek maliyetlerini bir arada verir. Süreler en kötü durum içindir; amortize olanlar ayrıca belirtilmiştir.

Tablonun ortak bir dersi vardır: bellekteki yerleşim bilindiğinde erişim bir formüle iner ve sabit sürede yapılır. Tek boyutlu dizi, çok boyutlu dizi, üçgen ve kuşak matrislerin hepsinde aynı soru sorulmuştur: “aranan öğeden önce kaç öğe var?” Maliyeti artıran işlemler ise öğelerin yerini değiştirenlerdir: araya ekleme, büyütme ve tarama.

2.11Sık yapılan hatalar

Bölümdeki hataların çoğu C'nin bilinçli bir tercihinden doğar: dil indisleri, bellek ayırmanın sonucunu ve dizge sonunu denetlemez. Aşağıdaki listede her hata, doğru kalıbıyla birlikte verilmiştir.

1. Dizi sınırı dışına yazmak. a[n]'ye erişmek tanımsız davranıştır ve C bunu denetlemez. n öğeli bir dizinin son indisi n − 1'dir; döngü koşulu i < n yazılır.
2. a = realloc(a, …) yazmak. Başarısızlıkta eski bloğun adresi kaybolur ve blok sızar. Sonuç önce geçici bir değişkene alınır, NULL değilse asıl işaretçiye atanır.
3. sizeof(int *) ile sizeof(int)'i karıştırmak; parametrede sizeof a kullanmak. İlki yanlış boyda bellek ayırır. İkincisinde parametre bir işaretçi olduğundan dizinin değil işaretçinin boyu çıkar. malloc(n * sizeof *a) kalıbı ve uzunluğun ayrı parametreyle geçirilmesi bu iki hatayı önler.
4. İki boyutlu dinamik dizide satırları free etmeden yalnız işaretçi dizisini bırakmak. Bütün satırlar sızar. Önce her x[i], sonra x serbest bırakılır.
5. Satır ve sütun öncelikli formülleri karıştırmak; öğe boyunu (s) unutmak. Satır öncelikli formülde satır uzunluğu (u₁) kullanılır; bayt adresi için öğe sayısı s ile çarpılır.
6. Dizgeler için == kullanmak ya da '\0' için yer ayırmamak. == adresleri karşılaştırır; içerik için strcmp kullanılır. n karakterlik bir dizge n + 1 bayt ister.
7. Hizalamayı hesaba katmamak. Bir yapının boyu alanlarının toplamından büyük olabilir. Boy her zaman sizeof ile alınır; elle toplanmaz.

2.12Özet

• Dizi soyut düzeyde ⟨indis, değer⟩ çiftlerinden oluşan bir eşlemedir; işlemleri Create, Retrieve ve Store'dur. C gerçeklemesinde öğeler ardışık durur ve A[i]'nin adresi α + i · s ile O(1)'de hesaplanır. Araya ekleme ve silme kaydırma gerektirdiği için O(n)'dir.
• C indisleri denetlemez; a[n]'ye erişim tanımsız davranıştır. Dizi adı çoğu ifadede ilk öğenin adresine dönüşür: list[i] ≡ *(list + i). İşaretçi aritmetiği öğe sayar, bayt değil. Dizi adına atama yapılamaz; fonksiyona geçirilen dizi işaretçiye dönüşür ve uzunluğu ayrıca gönderilir.
• malloc heap bellekten blok ayırır; dönüşü NULL için denetlenir, iş bitince free edilir ve işaretçiye NULL atanır. sizeof *a kalıbı tip değişse de doğru boyu verir.
• Dinamik dizi dolunca kapasitesini ikiye katlar. n eklemede toplam kopya 2n'den azdır; ekleme başına amortize maliyet O(1)'dir. Sabit artışla büyütmek O(n²) kopya demektir. realloc'un sonucu önce geçici bir değişkene alınır.
• İki boyutlu dinamik dizi bir işaretçi dizisi ve ayrı satır bloklarından oluşur (int **). Satırlar ardışık olmak zorunda değildir; bırakırken önce satırlar, sonra işaretçi dizisi free edilir.
• C satır öncelikli düzeni kullanır: &x[i][j] = α + (i · u₁ + j) · s. Sütun öncelikli düzende α + (j · u₀ + i) · s'dir. n boyutlu dizide adres α + Σ i_j a_j'dir; Horner yöntemi bunu n − 1 çarpmayla hesaplar. En dıştaki boyut adres hesabına girmez.
• Alt üçgen matris n(n + 1)/2 öğeyle saklanır; a_ij'nin konumu i(i + 1)/2 + j'dir. Erişim fonksiyonu geçerli konumlarla kesişmeyen hata kodları (−1, −2) döndürür.
• Kuşak matriste aynı kuşaktaki öğelerin j − i farkı sabittir. Öğe sayısı n(a + b − 1) − a(a − 1)/2 − b(b − 1)/2'dir. Kuşak başlangıçları ARA dizisinde tutulur ya da kapalı bir formülle hesaplanır; her iki yolla erişim O(1)'dir.
• && ve || soldan sağa ve kısa devreyle değerlendirilir; i < n && a[i] != 0 güvenlidir. & ve | kısa devre yapmaz.
• struct farklı tipteki alanları toplar; atanabilir ama == ile karşılaştırılamaz. Kendine başvuran yapı bağlı yapıların temelidir. union'ın alanları aynı belleği paylaşır; geçerli alan bir etiketle izlenir. Hizalama dolgu baytları ekler; alanlar büyükten küçüğe dizilerek yapı küçültülebilir.
• C dizgesi '\0' ile biten bir char dizisidir; n karakter n + 1 bayt ister. strlen O(n)'dir; döngü koşulunda çağrılırsa döngü O(n²) olur. İçerik strcmp ile karşılaştırılır; taşmaya karşı snprintf kullanılır.
• Matris toplama Θ(mn), kare matris çarpımı 2n³ + 3n² + 2n + 1 adımla Θ(n³), dikdörtgen matris çarpımı Θ(mnp)'dir. Kare matrisin yerinde transpozu n(n − 1)/2 takasla yapılır.

2.13Kavram listesi

Terimlerin İngilizce karşılıkları ve öteki bölümlerdeki kullanımları terim sözlüğünde bulunur.

• soyut veri tipi abstract data type (ADT)
• gerçekleme implementation
• dizi array
• eşleme mapping
• indis index
• işaretçi pointer
• işaretçi aritmetiği pointer arithmetic
• işaretçiye işaretçi pointer to pointer
• boş işaretçi null pointer (NULL)
• sarkan işaretçi dangling pointer
• sizeof işleci sizeof
• dinamik bellek ayırma dynamic memory allocation
• heap bellek heap memory
• malloc / calloc / realloc / free
• bellek sızıntısı memory leak
• dinamik dizi dynamic array
• kapasite capacity
• ikiye katlama doubling
• amortize analiz amortized analysis
• çok boyutlu dizi multidimensional array
• satır öncelikli düzen row-major order
• sütun öncelikli düzen column-major order
• Horner yöntemi Horner's method
• alt üçgen matris lower triangular matrix
• kuşak matris band matrix
• kısa devre değerlendirme short-circuit evaluation
• struct (yapı) struct
• typedef (tip adı) typedef
• ok işleci arrow operator (->)
• kendine başvuran yapı self-referential struct
• union (birlik) union (C)
• etiketli union tagged union
• sayım tipi enumeration (enum)
• hizalama alignment
• gezinme traversal
• dizge string
• dizge sonu karakteri null character ('\0')
• transpoz transpose
• yerinde in place

2.14Kendini Dene

1. int a[6]; dizisi 1000 adresinden başlıyor ve sizeof(int) = 4. &a[4] ve a + 4 hangi adresi verir? *(a + 4) hangi öğedir?

   Cevap

   İkisi de 1000 + 4 · 4 = 1016 adresini verir. İşaretçi aritmetiği öğe saydığı için a + 4, 4 bayt değil 4 öğe, yani 16 bayt ileridedir. *(a + 4), a[4]'ün kendisidir.

2. short s[4][7]; dizisi 500 adresinden başlıyor ve sizeof(short) = 2. Satır öncelikli düzende &s[2][5] kaçtır? Dizi sütun öncelikli saklansaydı ne olurdu?

   Cevap

   Satır öncelikli: öğeden önce 2 tam satır (2 · 7 = 14 öğe) ve satırında 5 öğe vardır; 500 + 19 · 2 = 538. Sütun öncelikli: önce 5 tam sütun (5 · 4 = 20 öğe) ve sütununda 2 öğe; 500 + 22 · 2 = 544. Satır öncelikli formülde satır uzunluğu (7), sütun öncelikli formülde sütun uzunluğu (4) kullanılır.

3. int A[3][4][5]; dizisinde A[2][1][3]'ün Horner yöntemiyle bulunan ofseti nedir? Hesapta kaç çarpma yapılır?

   Cevap

   t = 2; t = 2 · 4 + 1 = 9; t = 9 · 5 + 3 = 48. İki çarpma yapılır (n − 1, n = 3). İlk boyut olan 3 hesaba hiç girmez. Gerçek bir C dizisinde &A[2][1][3] - &A[0][0][0] da 48'dir.

4. 6 × 6 bir alt üçgen matris ALT dizisinde saklanıyor. Dizide kaç öğe vardır? a₅₂ hangi konumdadır? AltUcgenEris(2, 5, 6) ne döndürür?

   Cevap

   6 · 7/2 = 21 öğe. a₅₂: 5 · 6/2 + 2 = 17. AltUcgenEris(2, 5, 6) üst üçgendeki a₂₅'i sorar; 2 < 5 olduğu için −1 döner (değer 0, saklanmıyor).

5. n = 5, a = 2, b = 2 olan bir kuşak matris (üç köşegenli matris) kaç öğe tutar? ARA dizisi nedir? d₃₄ ve d₄₃ kusak dizisinin hangi konumlarındadır?

   Cevap

   5 · 3 − 1 − 1 = 13 öğe. Kuşaklar −1, 0, 1 ve uzunlukları 4, 5, 4'tür; ARA = [0, 4, 9]. d₃₄: kuşak 4 − 3 = 1, üst kuşak; konum ara[1 + 1] + i = 9 + 3 = 12. d₄₃: kuşak −1, alt kuşak; konum ara[0] + j = 0 + 3 = 3.

6. Boş başlayıp kapasitesini ikiye katlayan bir dinamik diziye 20 öğe eklenirse toplam kaç kopya yapılır ve son kapasite kaç olur? Kapasite her seferinde 1 artırılsaydı kopya sayısı ne olurdu?

   Cevap

   Büyütmeler 1, 2, 4, 8 ve 16 öğe dolduğunda olur: 1 + 2 + 4 + 8 + 16 = 31 kopya, son kapasite 32. Bu, 2 · 20 = 40'tan azdır. 1 artırmada 0 + 1 + … + 19 = 190 kopya yapılır.

7. struct { char a; int b; char c; double d; } tipik bir 64 bitlik sistemde kaç bayt tutar? Alanlar yeniden sıralanarak boy kaça indirilebilir?

   Cevap

   a 0. bayt, 3 dolgu, b 4–7, c 8. bayt, 7 dolgu, d 16–23: toplam 24 bayt. { double d; int b; char a, c; } sırasında 8 + 4 + 1 + 1 = 14 bayta 2 dolgu eklenir ve boy 16 olur. Sürücü programda iki değer de ölçülmüştür.

8. for (i = 0; i < strlen(s); i++) if (s[i] == ' ') say++; döngüsü 10 000 karakterlik bir dizgede yaklaşık kaç karakter okur? Döngü nasıl düzeltilir?

   Cevap

   Koşul her turda yeniden hesaplanır ve her strlen 10 000 karakter tarar. 10 001 denetimde yaklaşık 10⁸ karakter okunur; döngü O(n²)'dir. Uzunluk döngüden önce bir kez hesaplanır (size_t len = strlen(s);) ya da döngü s[i] != '\0' koşuluyla yazılır; ikisi de O(n)'dir.

9. 2 × 3 bir matris ile 3 × 4 bir matris çarpılıyor. Sonuç kaç hücrelidir ve kaç çarpma yapılır?

   Cevap

   Sonuç 2 × 4, yani 8 hücrelidir. Her hücre 3 çarpımın toplamıdır: 2 · 3 · 4 = 24 çarpma.

10. size_t f(int a[10]) { return sizeof a; } fonksiyonu 64 bitlik bir sistemde ne döndürür? Neden?

    Cevap

    8 döndürür. Parametre int a[10] diye yazılsa da derleyici onu int *a olarak işler; sizeof a işaretçinin boyudur, 40 değildir. Dizinin uzunluğu fonksiyona ayrı bir parametreyle gönderilmelidir. Derleyiciler bu kullanım için uyarı verir.

2.15İleri okuma

• E. Horowitz, S. Sahni ve S. Anderson-Freed, Fundamentals of Data Structures in C (2. baskı), Bölüm 2: dizi ADT'si, yapılar, polinom ve seyrek matris gösterimleri, çok boyutlu dizilerin adres hesabı ve dizgeler; bu notun izlediği ders kitabıdır.
• B. W. Kernighan ve D. M. Ritchie, The C Programming Language (2. baskı), Bölüm 5–6: işaretçiler ve diziler arasındaki ilişkiyi, işaretçi dizilerini, çok boyutlu dizileri ve yapıları dilin tasarımcılarının anlatımıyla verir.
• T. H. Cormen, C. E. Leiserson, R. L. Rivest ve C. Stein, Introduction to Algorithms (3. baskı), Kısım 17.4: dinamik tabloların büyütülmesini ve küçültülmesini toplama, muhasebe ve potansiyel yöntemleriyle amortize olarak analiz eder.

2.16Kaynaklar

1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3. baskı, MIT Press, 2009.
2. E. Horowitz, S. Sahni, S. Anderson-Freed, Fundamentals of Data Structures in C, 2. baskı, Silicon Press, 2008.
3. B. W. Kernighan, D. M. Ritchie, The C Programming Language, 2. baskı, Prentice Hall, 1988.

İlgili sayfalar: Bölüm 2 sunumu · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.