C’de Pointer Aritmetiği – Linear Search Algoritması

Pointer aritmetiği ile yapılacak  işlemlere geçmeden önce, arama algoritmaları nasıl işler ne işe yarar ondan bahsedelim.. Dizi, yığıt, kuyruk gibi veri yapılarıyla işlem yapmaya başladığınızda veri yapısına ekleme-silme işlemleri dışında en çok kafa yorulacak konu arama ve sıralama algoritmalarıdır. Arama algoritmalarıyla başlıyoruz..

Bir veri yapısında (örneğimiz için kullanacağımız dizi gibi..) arama yapabilmek için öncelikle veri yapısı içerisinde elemandan elemana istediğimiz gibi dolaşabilmemiz gerekir. Zaten diziyi dolaştıktan sonra geriye yalnızca bir karşılaştırma işlemi eklemek kalıyor ki bu da oldukça basit bir işlem..

Özetle, bir arama algoritmasının yapması gereken işlemi, “gez – karşılaştır(kontrol et) – sonuç döndür” şeklinde özetleyebiliriz. Hangi arama algoritması olursa olsun bu üç işlemi yerine getirmek zorundadır.

Şimdi bu arama algoritmaları içinden, en kolay anlaşılanı “Linear Search” ile başlayalım..

Öncelikle etkinliği hakkında birkaç şey söyleyeyim. Bir algoritmanın etkinliği pek çok duruma göre değişkenlik gösterebilir. Örneğin çok fazla kayıt içeren bir veri yapısı üzerinde arama işlemi yapıyorsak bu algoritma oldukça masraflı olacaktır. Ancak sıralı olmayan ve makul sayıda kayıt içeren bir veri yapısı için, kullanılabilecek en etkin yöntemlerden biridir.

Peki ne yapıyor bu algoritma ?

Oldukça basit.. Aradığımız elemanı, veri yapısının ilk elemanından itibaren tüm elemanlarla karşılaştırmak üzere bir döngü başlatıyor. Eğer eleman bulunursa bulunduğuna dair bir sinyal yaratıp (örneğin “bulundu” isimli değişkenin değerini 1 yapmak gibi) döngüden çıkıyor. Şayet bulunamazsa (dolayısıyla sinyal yaratılmamışsa) ve döngü bitmiş ise, elemanın dizide bulunmadığını belirtecek başka bir sinyal yaratıyor. (“Sinyal = return değerindeki değişiklik” veya “Sinyal = değişken değerindeki değişiklik” olarak düşünülebilir. Ben sinyal demeyi tercih ettim. )

C ile yazılmış algoritmayı görelim..

#include <stdio.h>
#include <stdlib.h>

//@author yigitcansener

int linear_search_ile_arama_yap(int [],int); //pointer kullanmadan doğrudan diziyi alarak arama yapacak linear search fonksiyonu..
int main()
{
 int dizi[] = {1,4,3,6,5,8,2,9,11,0}; //10 elemanli bir dizi tanimladik..
 int aranacak_sayi;
 int bulundu=0;
 printf("Aranacak sayiyi giriniz: "); //Kullanıinidan aranacak sayi istendi..
 scanf("%d",&aranacak_sayi); //Sayi alindi..

if((bulundu = linear_search_ile_arama_yap(dizi,aranacak_sayi)) == -1) //Eger arama sonucu olarak -1 donerse, listede aranan eleman olmadigi anlasiliyor...
 printf("Aradiginiz sayi listede yok!\n");
 else
 printf("Aradiginiz sayi listede %d. elemanda bulundu.\n",bulundu); // Eger donen eleman -1 den farkli ise, elemanin listede bulundugu anlasiliyor ve elemanin listedeki konumu donduruluyor..

return 0;
}

int linear_search_ile_arama_yap(int dizi[],int aranan)
{
 int i;

for(i=0;i<10;i++) // Dizi geziliyor..
 if(dizi[i] == aranan) // Karsilastirma islemi yapiliyor..
 return i; // Eger esitlik var ise esitligin bulundugu indeks return ediliyor.. (Sinyal)

return -1; // Eger dongu sonunda hic esitlik bulunmazsa, yani icteki return hic isletilmemisse, fonksiyondan -1 dondurulerek bir ust fonksiyona dizide elemanin bulunmadigi bildiriliyor..(Sinyal)
}

Kaynak koddan da anlaşılacağı gibi işlemler oldukça basit. Şimdi işin içine pointerları karıştırıp bir arama fonksiyonu daha oluşturalım. Büyük ölçüde bu koda bağlı kalarak, hatta bu kodu düzenleyerek elde etmeye çalışalım..

#include <stdio.h>
#include <stdlib.h>

//@author yigitcansener

int linear_search_ile_arama_yap(int *,int); //Diziye ait pointer ile arama yapacak linear search fonksiyonu..
int main()
{
 int dizi[] = {1,4,3,6,5,8,2,9,11,0}; //10 elemanli bir dizi tanimladik..
 int aranacak_sayi;
 int *ptr_dizi; // Dizinin ilk elemanini gosterecek olan pointeri tanimladik..
 int bulundu=0;
 printf("Aranacak sayiyi giriniz: "); //Kullanıinidan aranacak sayi istendi..
 scanf("%d",&aranacak_sayi); //Sayi alindi..

ptr_dizi = dizi; //Dizinin yalnizca adini kullanarak, baslangic adresini ptr_dizi pointerine aktardik.

if((bulundu = linear_search_ile_arama_yap(ptr_dizi,aranacak_sayi)) == -1) //Eger arama sonucu olarak -1 donerse, listede aranan eleman olmadigi anlasiliyor...
 printf("Aradiginiz sayi listede yok!\n");
 else
 printf("Aradiginiz sayi listede %d. elemanda bulundu.\n",bulundu); // Eger donen eleman -1 den farkli ise, elemanin listede bulundugu anlasiliyor ve elemanin listedeki konumu donduruluyor..

return 0;
}

int linear_search_ile_arama_yap(int *ptr,int aranan) //Pointer aritmetigi kullanarak arama yapan fonksiyon..
{
 int i;

for(i=0;i<10;i++) // Dizi geziliyor..
 {
 if(*ptr == aranan) // Karsilastirma islemi yapiliyor..
 return i; // Eger esitlik var ise esitligin bulundugu indeks return ediliyor.. (Sinyal)

ptr++;//Dizinin bir sonraki elemanina gecilmesi icin pointer degiskeninin degeri arttiriliyor..
 }
 return -1; // Eger dongu sonunda hic esitlik bulunmazsa, yani icteki return hic isletilmemisse, fonksiyondan -1 dondurulerek bir ust fonksiyona dizide elemanin bulunmadigi bildiriliyor..(Sinyal)
}

Görüldüğü gibi birkaç küçük değişiklik ile fonksiyonu pointerlar üzerinden işler hale getirdik..

Bir sonraki yazıda, sıralama algoritmaları ve pointer aritmetiği kullanarak sıralama algoritması tasarlama üzerinde duracağız..

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Log Out / Değiştir )

Connecting to %s

%d blogcu bunu beğendi: