24 Ağustos 2011 Çarşamba

AVL Ağacı (AVL Tree)

AVL Ağaçları sürekli olarak dengeli olan ikili arama ağaçlarındandır. G.M. Adelson-Velsky ve E.M. Landis tarafından geliştirilmiş olan bu ağaç algoritmasının ismi de bu kişilerin isimlerinin baş harflerinden oluşmaktadır.
Algoritma basitçe, bir düğümün kolları arasındaki derinlik farkı 2 ise bu durumda dengeleme işlemi yapılır. Şayet fark 2′den az ise (yani 1 veya 0) ise bu durumda bir dengeleme işlemine gerek yoktur.
Algoritmanın ağacı dolaşma (traverse) algoritması ikili arama ağaçları ile aynıdır. Ancak ağaca ekleme ve silme işlemleri sırasında ağacın dengesinin bozulması söz konusu olduğu için bu fonksiyonlara ilave olarak derinlik kontrolü eklenmiştir.
Ekleme ve silme işlemlerinde ikili arama ağacının ekleme ve silme işleminin aynısını yaptıktan sonra aşağıdaki dengeleme işlemi yapılır.
Ağaçta ekleme veya silme yapılan her düğüm için:
sol <- Düğümün sol kolunun derinliğini ölç
sağ <- Düğümün sağ kolunun derinliğini ölç
şayet sol - sağ >1
sola dengele
şayet sağ - sol < -1
sağa dengele

8 Ağustos 2011 Pazartesi

Strtok ile Okunan Satırı parçalama

  Kullanıcı dosyasında okunan  veriyi bazen parçalamak durumunda kalırsınız.Mesela dosyada öğrencilere ait yazılı notlarını okumanız isteniyorr.
  
   Mehmet Sağlam 80 70  54
   Nergis Şekerci   65  80 44
   Aydın Bulut Kahraman  26 68 71
   Can Sağlam    56 58 74
   Damla Ezgi Demir 89 96 100

      Şeklindeki ogrenci yapısı içindeki isim soyisim ve not dizilerina atamanız isteniyor.Bunun için normalde fscanf gibi fonksiyonları kullanabilirsiniz.Fakat yukarıdaki veriyi bu şekilde okumaya kalktığınızda Aydın Bulut Kahraman adlı öğrencinde Aydın-isim, Bulut-soyisim değişkenine atanır.Dolayısıyla Kahraman kelimesinin not değişkenine atanması gerekir.(not değişkeni char not[] şeklinde bir karakter dizisi olsun.)

  Bu durumda yapıyı kelime kelime, yerine satır satır okuma işlemini kullanabiliriz.
 
   char veri[100];  şeklinde bir char dizisi tanımlayalım.

   getline(veri, 100)  ile bu veriyi okuyalım.

    Şimdi elimizdeki verinin 3 ya da iki isimli oluşuna göre atama yapmamız gerekiyor.Bunun için önce strtok dizgi parçalama fonksiyonu ile  okuduğumuz satırı parçalayalım.

             char *pch;
             pch=strtok(veri," .,-\t\n");
    Şimdi  parça sayısına göre isim, soyisim  dizilerine okuduğmuz verileri kopyalayalım.


   int  i=0;    
    while(pch!=NULL){
        if(i==0)
          strcpy(isim,pch);               /*   İlk okunan değer isim değişkenine atanır.
      if(i==1){
          strcpy(soyisim,pch);          /*İkinci okunan değer soyisim değişkenine atanır.
          strcpy(yedek, pch);          /*İkinci okunan değer 3 isimli olma ihtimaline karşın yedek bir
.                   }                           /*değişkene  atanır
      if(i==2){
        strcat(isim, " ");
        strcat(isim, yedek);              /* i değişkeni 2 olursa 3. isim var demektir.Bu durumda isim
        strcpy(soyisim,  pch);           /*değişkenine ilk okunan ismin yerine boşluk karakteri ve
          }                                      /* ikinci isim atanır. 3. okunan değer ise soyisim değişkenine
         pch=strtok(NULL," .,- \t\n"); /* atanır.
         i++;
      }







    Yukarıdaki yapı dosyadan okuma sırasında oluşabilecek bu tür durumlarda kullanılabilir.

C ile Dosya İşlemleri

Bu yazının amacı C dilinde dosya işlemlerinin nasıl yapıldığını anlatmaktır. C dilindeki dosya işlemlerinden önce bu dilde yazılan programın çalışacağı işletim sisteminin dosya yapısının iyi bilinmesi gerekmektedir. Bu yazının konusu dışında olan işletim sistemlerinin kullandığı dosya sistemlerini lütfen okuyunuz.
C dilinde dosya işlemleri için file.h dosyasının içerilmesi (include) gerekir.
#include <file.h>
Yukarıda gösterildiği şekilde içerilir.
Dosya Açma
Dosya açmak için fopen fonksiyonu kullanılır. Basitçe dosyanın adını ve açma şeklini alan bu fonksiyon geri değer olarak integer döndürür ve açmanın başarılı olup olmadığı anlaşılabilir.
if(fopen(“deneme.txt”,”r”)){
printf(“dosya açıldı”);
}else{
printf(“dosya açılamadı”);
}
yukarıdaki örnek kodda fopen fonksiyonuna parametre olarak “deneme.txt” dosyası verilmiştir. Bunun anlamı programımız ile aynı dizinde bulunan deneme.txt dosyasının açılmasıdır. Şayet farklı bir dizinden okunması isteniyorsa tam yol verilebilir. Örneğin:
c:\deneme\deneme.txt –> C sürücüsundeki deneme dizinin altındaki deneme.txt (WINDOWS)
/usr/bin/deneme.txt –> root dizin / altındaki usr altındaki bin altındaki deneme.txt dosyası (LINUX)
..\dosyalar\deneme.txt –> programımızın bulunduğu dizinin bir altında bulunan dosyalar dizinin altındaki deneme.txt dosyası (WINDOWS)
şeklinde kullanılabilir. Hemen ardından fopen fonksiyonuna verilen ikinci parametre ise dosyanın açılma şeklini belirtir. Bu şekiller:
r or rb
Dosyayı okuma (read) için açar.
w or wb
Dosyayı yazma(write) için açar ve şayet dosya zaten varsa içindekileri temizleyerek yoksa yeni bir dosya oluşturur.
a or ab
Dosyaya ilave (Append) için açar. Bunun anlamaı dosya yoksa oluşturulacak varsa mevcut bilgilerin sonuna yazılacak demektir.
r+ or rb+ or r+b
Mevcut Dosyayı hem okumak hemde yazmak için açar.
w+ or wb+ or w+b
Dosyayı bir önceki şekilde olduğu gibi hem okumak hem de yazmak için açar. Ancak dosya yoksa oluşturur, dosya varsa içindekileri siler.
a+ or ab+ or a+b
Dosyayı ilave şeklinde açar ve şayet dosya yoksa oluşturur, varsa içindekilerin sonuna ilave eder. Bu şekilde açılan dosyalardan hem okuma hemde yazma işlemi yapılabilir.
Yukarıdaki şekillerin “b” sembolü alanları binary mod anlamındadır.
Yukarıdaki bu şekillerden birisi tercih edilerek ilgili sembol fopen’a ikinci parametre olarak verilir. Yukarıdaki örnek kodda da görüldüğü üzere fopen fonksiyonu bir if içerisindedir. Bunun anlamı fopen fonksiyonundan başarılı sonuç dönerse dosyanın açıldığı anlaşılacaktır. Aksi halde dosyanın açılması başarısızlıkla sonuçlanmıştır ve programımızda bu durum için basit bir hata mesajı ekrana basılır.
Dosyadan okuma ve yazma
Dosya açıldıktan sonra dosyaya okuma ve yazma işlemleri yapılabilir. Okuma ve yazma işlemlerinin yapılabilmesi için yukarıda anlatılan dosya açma işlemine ilave olarakaçılan dosyayı gösteren bir göstericiye (pointer) ihtiyaç duyulmaktadır. Bu gösterici fopen fonksiyonu tarafından döndürülmektedir. Kod örneği aşağıdadır:
FILE *fp;
fp = fopen(“dosya.txt”,”r”);
yukarıdaki örnek kodun ilk satırında fp isminde bir dosya göstericisi tanımlanmıştır. İkinci satırında ise bu göstericinin içerisine fopen fonksiyonundan dönen değer atanmıştır. Buna göre dosyaya erişilmesi istendiğinde fp göstericisi üzerinden işlem yapılması yeterlidir.
Dosyalardan okuma ve yazma yapan çok sayıda fonksiyon olmasına karşılık anlaşılması en kolay fonksiyonlar C dili ilk öğrenilirken öğrenilen scanf ve printf fonksiyonlarının birer türevi olan fscanf ve fprintf fonksiyonlarıdır. Birer örnek aşağıda verilmiştir:
int i;
fscanf(fp,”%d”,&i);
fprintf(fp,”%d”,i);
yukarıdaki örneklerde bir i değişkeni integer tipinde tanımlanmıştır. Bu değişkene ikinci satırda fscanf fonksiyonu ile bir değer dosyadan okunmuştur. Bu fonksiyon ilk bakışta da anlaşılacağı üzere scanf fonksiyonundan farklı olarak ilave bir dosya göstericisi parametresi kullanmaktadır. Bu parametre fonksiyonun ilk parametresidir. Yukarıdaki örnekte bulunan “fp” dosya göstericisi de böyle bir dosya gösterici örneğidir.
fprintf fonksiyonu da ilave bir dosya göstericisi almak dışında standart printf fonksiyonundan farklı değildir.
Hatırlanması gereken önemli bir nokta, fscanf fonksiyonunun kullanılması için dosyanın okuma, fprintf fonksiyonunun kullanılabilmesi için ise dosyanın yazma şeklinde açılması gerekmektedir.
Örnek
Örnek olarak basit bir öğrenci kayıt sistemini C dilinde kodlamaya çalışalım. Amacımız “kayit.txt” isimli bir dosyaya, kullanıcıdan öğrenci bilgisi okuyup kaydetmek ve daha sonra kullanıcının istediği bir anda bu dosyayı aratarak kayıtlara ulaşmasını sağlamak olsun.
Öncelikle kullanıcı ile iletişimi sağlayan ufak bir menü tasarımı yapalım:

Yukarıdaki kodda, sonsuz bir döngü (14. satır) içerisinde dönen printf satırları ile yazılmış olan bir menü görülmektedir. Kullanıcının menüden yaptığı seçim bir değişkene okunmakta ve değerine göre if koşulları ile kontrol edilerek ilgili işlem icra edilmektedir. Örneğin yukarıdaki kodda, 20. satırda bulunan if koşuluna girilmesi için kullanıcının menüden 1′i seçmiş olması, diğer bir deyişle, klavyeden 1 yazarak enter’a basması gerekmektedir.
Kodumuzda öğrenci kayıtlarını tutacağımız için bir oluşum (composition) kullanmamız ve bu oluşumu C dilinde yapılar (structs) kullanarak tanımlamamız mümkündür:

Yukarıda, örnek bir öğrenci yapısı (struct) gösterilmektedir. Kodun 5-9.  satırları arasında bu yapıyı oluşturan değişken tipleri tanımlanmıştır. Ayrıca yapının ismi “ogrenci” olarak tanımlanmıştır.
Kodumuzdaki main fonksiyonu içerisinde, 12. satırda, ogrenci yapısından bir tip oluşturulmakta ve bu yeni tipe xyz ismi verilmektedir. Bu tip, C dilinde tanımlı olan diğer tipler gibi (örneğin int, char, float) bir tip olmakta ve bu tipten yeni değişkenler tanımlamamıza imkan tanımaktadır.
Kodumuzdaki seçimlere göre çalışacak olan kayıt ekleme ve silme işlemlerini aşağıdaki şekilde kodlayabiliriz. Öncelikle kayıt ekleyen kısma bakalım:

Yukarıdaki kodda, 21. satırda xyz tipinde bir değişken tanımlanıp, ardından 22-29. satırlar arasında bu değişkenin içerisine klavyeden değer okunmuştur. Okunan değerler yapı (struct) içerisinde ilgili değişkenlere yerleştirilmiş ve hafızada tutulmaktadır.
Kodun 30. satırında bir dosya göstericisi tanımlanıp, göstericinin “kayit.txt” dosyasını göstermesi sağlanmıştır. Buradaki dosyanın açılış şekli, “a” parametresinden de anlaşılacağı üzere ekleme (append) halindedir.
Kodun 31. satırında fprintf fonksiyonu marifetiyle fp göstericisinin gösterdiği yani “kayit.txt” dosyasına okunan yapısındaki isim, soyisim ve no değişkenlerinin değeri bastırılmakta ve nihayetinde 32. satırda dosya kapatılarak kayıt işlemi tamamlanmaktadır.
Kayıtlar arasında arama işlemi yapan kod kısmı ise aşağıda verilmiştir:

Yukarıdaki kodun, 36. satırında, aranan ismi tutmak amacıyla bir dizgi (string) tanımlanmış ve bu değişkenin içerisine kullanıcıdan aranması istenen değer 37. satırda scanf ile okunmuştur.
38. satırda, dosya okuma şeklinde (read) açılmış ve fp isimli dosya göstericisine atanmıştır.
42. satırda feof fonksiyonu ile dosyanın sonuna kadar dönen bir döngü tanımlanmıştır. Buradaki döngü fp göstericisinin dosya sonunu göstermesi durumunda 1 döndürmektedir. Dolayısıyla dosya sonuna kadar 1 dönmesini ve dosya sonuna ulaşılınca 0 dönmesini sağlamak maksadıyla ! işaretiyle dönen değerin tersi alınmaktadır. While döngüsü kısaca dosya sonuna kadar dönen bir döngü halini almıştır.
Döngünün içindeki 43. satırda, dosyadan fscanf fonksiyonu ile okunan isimli yapının içerisine değerler okunmaktadır.
44. satırda okunan değerlerden isim bilgisi, aranan dizgi (string) ile karşılaştırılmakta ve eşitlerse 45. satırdaki printf fonksiyonu çalışmakta ve ekrana aranan öğrenci bilgisini yazmaktadır. Eşit olmaması durumunda bir sonraki öğrenciye devam edilmektedir.
Kodun tamamı aşağıdaki şekildedir: