Standart C Programlama Dili

5.9. Bir Örnek—Dosya Sıralama

Bu kısımda, malloc ve free kütüphane fonksiyonlarını kullanan ve bu bölümde öğrenilmiş bazı kavramları gösteren bir örneğe bakacağız. Problem bir metin dosyasındaki satırları sıraya sokmaktır. Sıraya sokma düzeni, sistem tarafından sağlanan sıraya göre olacaktır. Bu, bizim sistem için, artan ASCII karakterleri sırasıdır. (Ek A’ya bakınız.) Bu program MS-DOS, Windows veya unix’teki sort komutuna benzemektedir.

Yöntemimiz ikili bir ağaç kullanmak olacaktır. Ağacın her düğümünde bir bilgi alanı ve iki gösterge vardır: biri sola, biri sağa. Algoritma şöyledir:

• Boş bir ağaçla başla.
• Bir satır oku; bir düğüm oluştur; bilgi bölümünü satırla doldurup iki göstergeye BOŞ (NULL) koy. Bu, kök düğümü olacaktır.
• Bir sonraki satırı oku; bu satır için yukarıdaki gibi bir düğüm oluştur. Şimdi bu düğümün ağaç içine konulacak yeri araştır. Kök düğümüne olan göstergeden başlayarak ve BOŞ bir gösterge elde edilmediği sürece göstergeleri şu şekilde izle: Eğer yeni satır, eldeki gösterge tarafından işaret edilen düğümdeki satırdan sözlük sırası açısından küçükse, göstergeye o düğümün sol göstergesini aktar; aksi takdirde sağ göstergeyi aktar; bu işlemi tekrarla. Sonunda BOŞ bir göstergeye ulaşılacaktır; bu göstergeyi yeni düğümü gösterecek şekilde değiştir.
• Girilen bütün satırlar için önceki adımı tekrarla. Sonunda—ille de dengeli olmasına gerek olmayan—bir ikili ağaç elde edilecektir.

Sayısal değerler kullanılarak elde edilen örnek bir ikili ağaç Şekil 5.1’de gösterilmiştir.

Ağacı bastırmak için aşağıdaki özçağrılı algoritmayı kullanacağız: Kök düğüme olan göstergeden başla. Eğer gösterge BOŞ değilse, soldaki altağacı bastır; eldeki düğümün bilgisini bastır; sağdaki altağacı bastır. Altağaçların basım işi aynı tümcede anlatılan algoritma kullanılarak yapılacaktır. Bu algoritma önünde sonunda bitecektir; çünkü tümce başında eğer koşulu vardır. Dikkat ederseniz, bir ağaçtaki göstergelerin yarısından fazlası BOŞtur. Neden?

Bu algoritmayı bir program şeklinde uygulamaya sokmak için düğüm için ne tür bir veri yapısı kullanacağımıza karar vermemiz gerekir. Doğal olarak, bu, üç üyeden oluşan bir yapı (struct) olacaktır: satir, sol ve sag; bu son ikisi de aynı yapıya olan gösterge tipinden olacaktır. Yani, bir öz-referanslı yapımız olacaktır. İlk üye (satir), belirli bir üst limite (örneğin 80 karaktere) kadar olabilecek bir satırı saklayabilecek büyüklükte bir karakter dizisi şeklinde tanımlanabilir. Fakat bütün satırlar bu kadar uzun olamayacaklarına göre, dizi içindeki alanın büyük bir bölümü kullanılmayabilecektir, yani bellek israfı olacaktır. Bundan dolayı satir bir karakter göstergesi şeklinde tanımlanmıştır ve satırın boyu kadar, yürütme esnasında istenen, bellek bölgesinin başına işaret edecektir.

Şimdi de program:

#include <stddef.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAKSSU 80         /* en büyük satır uzunluğu */

typedef struct dugum {    /* struct dugumun tanımı  */
  char  *satir;           /* bilgi */
  struct dugum  *sol, *sag;
} *dugumg;                /* dugumg tipinin tanımı */

void *yeni (size_t d)     /* bellek ayırma */
{
  void *g;

  if ((g=malloc(d))!=NULL)
    return g;             /* tamam */
  fprintf(stderr, "SIRALA: Yetersiz bellek");
  exit(1);                /* programı kes */
} /* yeni */

size_t satiroku           /* satır uzunluğu döndür; 0 dosya sonu */
  (char *d, int u)
{
  register char  *g = d;
  register int  c;

  while ((c=getchar())!='\n' && c!=EOF)
    if (u-->1)
      *g++ = (char)c;     /* daha uzun satırları kes */
  if (c==EOF && g==d)
    return 0;             /* bir şey okunamadı */
  *g++ = '\0';
  return g-d;             /* asıl uzunluk artı bir ('\0' için) */
} /* satiroku */

void satirlaribas         /* ağacın özçağrılı taranması */
  (dugumg g)
{
  if (g!=NULL) {
    satirlaribas(g->sol);
    printf("%s\n", g->satir);
    satirlaribas(g->sag);
    free((void *)g->satir);
    free((void *)g);
  }
} /* satirlaribas */

int main (void)
{
  char  satir[MAKSSU+1];  /* MAKSSU artı bir ('\0' için) */
  size_t  su;             /* şimdiki satır uzunluğu */
  dugumg  kok = NULL, *g;

  while ((su=satiroku(satir,(int)sizeof satir))  > 0) {
    g = &kok;
    while (*g!=NULL)
      g = (strcmp(satir,(*g)->satir) < 0)
          ? &(*g)->sol : &(*g)->sag;
    *g = (dugumg) yeni(sizeof(struct dugum));
    strcpy((*g)->satir = (char *)yeni(su), satir);
    (*g)->sol = (*g)->sag = NULL;
  }
  satirlaribas(kok);
  return 0;
} /* main */

Programın başında, yapı (struct dugum) ve böyle bir yapıya bir gösterge (dugumg) için tipler tanımlamış bulunuyoruz. main yordamı, her okunan satır için bir defa yürütülen büyük bir while döngüsünden oluşmaktadır.

satiroku fonksiyonu satir karakter dizisinin içine bir satır okur ve okunan karakter sayısı artı bir (en sona konan '\0' için) verir. Dosya sonu (EOF) durumunda ise 0 döndürür.

main içinde iki önemli değişkenimiz vardır: kok, düğüme bir göstergedir ve her zaman kök düğümüne işaret eder, g ise bir düğüme olan göstergeye göstergedir; bir düğümün sol yada sag göstergelerine işaret eder. Bir defa bir satır okundu mu, g kök düğüm göstergesine işaret edecek şekilde getirilir.

Sonra, g tarafından işaret edilen yerde NULL (BOŞ) bir gösterge olmadığı sürece, g’nin işaret ettiği gösterge tarafından işaret edilen düğümde şimdi okunan satırdan sözlük sırasına göre daha büyük bir satırın olup olmadığını kontrol ederiz. Eğer öyle ise g’nin sol, aksi takdirde sag göstergeye işaret etmesini sağlarız. while döngüsü g tarafından işaret edilen (sol ve sag) gösterge bir düğüme işaret ettiği (yani NULL olmadığı) sürece tekrarlanır.

Bir NULL göstergeye ulaştığımızda, g’nin bu göstergeye işaret ettiğini bilerek, döngüden çıkarız. Şimdi yeni bir düğüm oluşturmanın zamanıdır. malloc kütüphane fonksiyonunu kullanan yeni fonksiyonu, bu düğüm için yeterli miktarda bellek bölümü ayırmak için çağrılır. Döndürdüğü gösterge g tarafından işaret edilen göstergeye aktarılır. Daha sonra, okunmuş olan satırı alacak büyüklükte bir bellek bölgesi ayrılır; satır bu bölgeye aktarılır ve bu bölgeye olan gösterge, g’nin işaret ettiği gösterge tarafından gösterilen düğüm, yani yeni düğüm, içindeki satir göstergesine atanır. Ayrıca, bu düğümün sol ve sag göstergelerine de NULL konulur.

Yukarıda anlatılanlar, ilk bakışta, çok karmaşık gelebilir. Eğer açıklamayı tam olarak izleyemediyseniz, tamamen haklısınız. Birkaç tekrar yararlı olacaktır.

Yapılacak son şey ağacı basmaktır. Burada özçağrı bize çok yardımcı olacaktır. Ana program, kok göstergesini vererek satirlaribas adlı özçağrılı fonksiyonu çağırır. Bu fonksiyon, Eğer gösterge NULL değilse, sol altağacı bas; şimdiki düğümün bilgisini bas; sağ altağacı bas cümlesinde denileni yapar ve ayrıca bu düğüm tarafından kullanılan belleği serbest bırak işini de yapar. Bellek serbest bırakıldıktan sonra, tekrar bellek ayırma söz konusu olmadığı için free fonksiyonu çağrılarının bu program için gereksiz olduğuna dikkat edin.

Programımız girdisini standart girdi aygıtından alır ve çıktısını da standart çıktı aygıtına gönderir. Daha sonraki bir bölümde göreceğimiz gibi, programlarımızda girdi ve çıktı için dosyalar da kullanabiliriz, ama daha basit bir yol vardır. Birçok işletim sistemi, girdi ve çıktının yeniden yönlendirilmesi adı verilen ve tekrar derleme yapmadan, standart girdi ve çıktı dosyaları yerine başka dosyaların kullanılmasına izin veren bir yöntem sağlarlar. MS-DOS, Windows veya unix’te bu şu şekilde yapılabilir: Programınızın sirala adlı yürütülebilir dosya içinde derlendiğini varsayın.

>sirala <SIRASIZ >SIRALI

komutunu kullanarak programın girdiyi SIRASIZ adlı disk dosyasından almasını ve çıktıyı SIRALI adlı dosyaya koymasını sağlayabilirsiniz. Bu argümanların bir tanesini belirtmediğinizde ne olduğunu deneyip kendiniz bulmaya çalışın. Program için bu argümanların tamamen görünmez olduğuna dikkat edin; yani (main fonksiyonunun ikinci parametresi olan) argv dizisinde gözükmeyeceklerdir; gerekli işlemleri işletim sistemi yapar.

Başka bir özellik küme komut işlemedir.

>dir | sirala

şeklindeki Microsoft DOS/Windows komutunu veya

$ ls -al | sirala

şeklindeki unix komutunu deneyip çıktıyı açıklayın. Daha fazla bilgi için işletim sisteminizin el kitaplarına danışın.