Aralık 2010 | Sayı : 21
      Veri Yapılarında Yığın ve Kuyruk Yapıları Aralık 2010 | Sayı : 21

Herkese merhabalar. Programcıların olmazsa olmazlarından biri de veri yapılarıdır. Bu ayki yazımda sizlere veri yapılarının en anlaşılmaz noktalarını, örnek kodları biraz görselleştirerek anlatmaya çalıştım. Ödevlerinizde sizlere yardımcı olacağını ümit ederek yazıma başlıyorum.

Yığın ve Kuyruk Modelleri

Verileri geçici olarak saklayan, pointerlar aracılığıyla verileri birbirine bağlayan mekanizmalar yığın ve kuyruk modelleridir.

C dilinde “int sayilar[20] “ tanımlaması; 4, 12, 33 gibi tamsayılardan maksimum 20 tane alabilen “sayilar” adında bir tamsayi dizisini ifade eder. Bu diziye 20’den daha fazla sayı ekleyemezsiniz. Ayrıca sadece int tipinde veri içerebilir. Bu dizi yapısı statik (sabit) bir modeldir. Farz edin ki, büyük bir dizimiz var ve bu dizi int, char, string, float gibi çeşitli tipler barındırıyor. Üstelik sabit boyutlu da değil. İşte bu imkanı bize veri yapıları sağlıyor. Yığın ve kuyruk modellerinin en önemli özelliği de dinamik yapıda olmalarıdır. Bu sayede, istediğiniz boyutta, çeşitli tipler içeren diziler yaratabilirsiniz.

Yığın yapısı

Bir mikroişlemcinin içinde stack pointer (yığın işaretçisi) bulunur. Bu pointer, işlemciye kesme (interrupt) geldiğinde saklayıcılarında tutulan verileri geçici olarak saklayacağı yığındaki boş göze işaret eder.

 Yığın yapısında LIFO (last in-first out) kuralı vardır. Yığına son giren ilk çıkar.

Yığın yapısı ile ilgili ekleme ve çıkarma örneğini inceleyelim. Bu örnekte yığın yapısı sadece bir integer değerini ve adresi tutmaktadır.

struct yigin_yapisi{

            int veri;

            struct yigin_yapisi *sonrakiPtr;

};

typedef struct yigin_yapisi yigin; //Burada "yigin" tipini yaratıyoruz.

typedef yigin *yiginPtr; // Pointerların tipini yaratıyoruz.

void ekle(yiginPtr * sPtr,int deger){

   yiginPtr yeniPtr;

   yeniPtr =(yiginPtr)(malloc(sizeof(yigin)));

   yeniPtr->veri = deger;

   yeniPtr->sonrakiPtr=*sPtr;

   *sPtr=yeniPtr;  

}

void cikar(yiginPtr *sPtr){

  yiginPtr geciciPtr;

  int cikdeger;

  geciciPtr=*sPtr;

  cikdeger=geciciPtr->veri;

  *sPtr=(*sPtr)->sonrakiPtr;

  free(geciciPtr);

  printf("%d yigittan cikarildi\n",cikdeger);

}

void yazdir(yiginPtr xPtr){

            while(xPtr!=NULL){

      printf("%d\n",xPtr->veri);

      xPtr=xPtr->sonrakiPtr;}}

void secme(){

            printf("1.yigina sayi gir\n");

            printf("2.yigindan sayi cikar\n");

            printf("3.yigini goster\n");

            printf("0.cikis\n");

}

int main()

{

            int sayi,secim,kontrol=1;

            yiginPtr aPtr=NULL;

            while(kontrol != 0)

            {

              secme();

              scanf("%d",&secim);

              switch(secim){

case 1:

              printf("Yigina bir sayi giriniz\n");

              scanf("%d",&sayi);

              ekle(&aPtr,sayi);

              break;

case 2:

              cikar(&aPtr);

              break;

case 3:

            printf("suan yigindaki sayilar sirasiyla:\n");

                        yazdir(aPtr);//Pointerda değişiklik yapmayacağız, sadece yazacağımız için adresini almadık.

                           break;    //aPtr listenin baş pointerının adresini gönderir çünkü biz ekle fonksiyonunda sürekli baş pointerın

                                     //adresini değiştirdik ama hep o başı gösterdi.

case 0:

            kontrol=0;

            break;

              }

            }

            system("pause");

            return 0;

}

   Yığına ekleme yapma mantığını daha ayrıntılı inceleyelim ve ekle() fonksiyonuna ilk çağrıyı yapalım.

1-)  aPtr yigin yapısında tanımlı ve yapıyı gösteren bir pointer. Main() fonksiyonunun içinde ilk değerine NULL atanmıştır. ekle(&aPtr, sayi) fonksiyonu ile aPtr’nin adresi gönderilmiştir çünkü bu adres sürekli değişecektir. O yüzden adresin adresini gönderiyoruz. ekle(yiginPtr * sPtr, int deger) ile aPtr’yi sPtr temsil etmektedir.

            İlk şekilde bellekten yer ayrılıyor. YeniPtr bir adres tutuyor.

2-)  İkincisinde ise ayrılan yere 6 değeri atanıyor.

3-)  Üçüncü şekilde sonraki ptr NULL yapılıyor. Hatırlarsanız *sPtr ilk çağrı olduğu için NULL geldi.

4-)  Son adımda ise eklenen yeniptr *sptr ye atanarak bir elemanlı yığını oluşturmuş oluyoruz. Artık *sPtr NULL tutmuyor. Liste başını tutuyor.

İlk çağrı konuyu anlamakta yeterli değildir. İkinci çağrıyı da yapmadan yığına ekleme mantığını geçmeyelim.

1) Birinci şekilde bir elemanlı yığınımızdan bağımsız bir yeniPtr oluşturulur.

2) İkinci şekilde bu pointera değer girilir. yeniPtr adında 7 sayısını gösteren yeni bir pointer oluşturulur.

3) Fonksiyon içindeki  *sPtr adresin adresini tuttuğu için her çağrıda liste başını bize getirir. Sonra bu 7‘nin sonrakiPtr’sine listenin başı atanır.

4) *sPtr= yeniPtr diyerek 7’yi liste başı yapmış oluruz.

Yığına ekle() fonksiyonunu çağırarak değerler ekledik ve her seferinde yeni eklediğimiz sayı liste başını tuttu. Şimdi yığından eleman çıkaralım. Yığında LIFO mantığı olduğu için cikar() fonksiyonuna yapacağımız her çağrıda, liste başında hangi eleman varsa o elemanı yığından çıkaracağız. sPtr’nin adresini tutmak o yüzden önemlidir.

1) *sPtr’nin içeriği geciciPtr’de saklanır.

2) Liste başındaki sayı cikdeger’de tutulur.

3) *sPtr=*sPtr->sonrakiPtr ile artık sonraki değer liste başını gösterir ve geciciPtr’de tutulan değer hafızadan silinir.

Kuyruk Yapısı

Kuyruk modelinde FIFO (first in - first out) kuralı geçerlidir. Bir banka kuyruğunu düşünün. Sırada bekleyen insanlardan ilk gelen işini bitirir ve sıradan ayrılır.

Kuyruk modeli örneğinde yığında yaptığımız gibi sadece integer değeri tutmayacağız. Hem bir integer hem de char dizisi tutacağız. Böylece dinamik veri yapılarının çeşitli türleri de içinde nasıl barındırdığına tanık olacağız.

struct kuyruk{

            int sayi;

            char ad[10];

            struct kuyruk *sonrakiPtr;

};

typedef struct kuyruk Kuyruk;

typedef struct kuyruk *kuyrukPtr;

kuyrukPtr yer_ayir(){

            kuyrukPtr p;

            p=(kuyrukPtr)malloc(sizeof(struct kuyruk));

            return (p);

 

}

int bosmu2( kuyrukPtr basPtr){

            return basPtr==NULL;

}

void ekle(kuyrukPtr *kPtr,kuyrukPtr *sPtr,int veri,char *isim){

 

 kuyrukPtr temp;

            temp=yer_ayir();         

            temp->sayi=veri;

            strcpy(temp->ad,isim);

            temp->sonrakiPtr=NULL;

            if(bosmu2(*sPtr)){

                        *sPtr=temp;

            }

            else

            (*kPtr)->sonrakiPtr=temp;

            *kPtr=temp;

}

void sil(kuyrukPtr *sPtr,int *px,char *isim){

 

            kuyrukPtr gecici;

            gecici = (*sPtr);

 

            (*sPtr) =gecici->sonrakiPtr;

            *px = gecici->sayi;

            strcpy(isim,gecici->ad);

            free(gecici);

            printf("%d.%s silindi\n",*px,isim);

}

void yazdir(kuyrukPtr kPtr){

            printf("kuyruktaki veriler\n");

            while(kPtr != NULL )

            {

                        printf("%d.%s\n",kPtr->sayi,kPtr->ad);

                        kPtr= kPtr->sonrakiPtr;

            }

}

void sec()

{

            printf("\n1 ekleme\n");

            printf("2 silme\n");

            printf("3 yazdirma\n");

            printf("4  cikis\n");

}

 

int main(){

            kuyrukPtr sPtr=NULL;

            kuyrukPtr kPtr=NULL;

            int sayi,i,x;

            int secim;

            char isim[10];

            char ad[10];

            printf("bir secim yapiniz\n");

            sec();

            scanf("%d",&secim);

            while(secim !=4){

                        switch(secim){

                        case 1:

                        printf("isim giriniz:\n");

                        scanf("%s",isim);

                        printf("numara giriniz:\n");

                        scanf("%d",&sayi);

                        ekle(&kPtr,&sPtr,sayi,isim);

                        break;

                        case 2:

                        sil(&sPtr,&x,ad);

                        break;

 

                        case 3:

                yazdir(sPtr);

                        break;

                        default :

                                   printf("yanlis secim\n");

                                   break;

                        }

                        sec();

                        scanf("%d",&secim);

            }

            system("pause");

            return 0;

}

Bu kuyruk örneğinde kuyruk yapısı isim, sıra numarası ve pointer tutan bir yapıdan oluşmaktadır. Kodun tamamında yine en önemli iki fonksiyon olan ekle() ve sil() fonksiyonlarını daha yakından inceleyeceğiz.

Burada yığından farklı olarak sona ekleme olur. *kPtr ve *sPtr adında iki farklı pointer kullanmamızın sebebi,  *sPtr’nin liste başını, *kPtr’nin ise liste sonunu tutmasıdır. Yığında sadece liste başını tutmak yeterliydi çünkü sürekli baştan ekleme, çıkarma yapıyorduk. Burada liste sonuna ekleme yaptığımız için liste sonunu da tutuyoruz. Başını tutmamızın sebebi ise, bu listedeki verileri yazdırırken ve silerken bize lazım olmasıdır. Ayrıca bazı özel algoritmalarda while döngüsüyle tekrar tekrar başa dönme ihtiyacı hissedebiliriz. O yüzden başı da tutmak gerekir.

ekle() fonksiyonuna ilk çağrıyı yapalım. Yığından tek farkı, son adımda ilk eklenen veriye *sPtr ve *kPtr değerinin atanmasıdır çünkü ilk eklenen hem liste başıdır, hem de son elemandır.

İlk çağrının yetersiz olacağını düşünerek ekle()’yi tekrar çağıralım. Burada ise artık yeni eklenenin bilgisini *kPtr tutar. Artık*sPtr’de herhangi bir değişiklik yapılmaz.


ekle()  fonksiyonunu birkaç kez çağırdıktan sonra kuyruktan eleman çıkaralım. Kuyruk yapısının mantığına bakılırsa ilk çıkış hakkı 28 numaralı giriş yapan Adnan Bey’indir.

 *kPtr’yi ekle() yaparken değiştiririz. *sPtr’yi de sil() yaparken değiştiririz.

Gördüğünüz gibi listeden çıkarma işlemi yığın gibi liste başından yapılır ama kuyrukta ekleme sondan yapıldığı için kuyruk başından çıkanlar, ilk girenlerdir.

 
      Özge ATASEVEN
İ.Ü. Bilgisayar Mühendisliği 3. Sınıf
- Aralık 2010 -
Editörden... | Ercan ZENGİN PHP CodeIgniter Çatısı | Muhammet ARSLAN Facebook Oyun Dünyası | Erman TEPE Biyometrik Güvenlik Sistemleri | Rüya ŞAMLI YÖK'ten Haberler ve Projeler | Muhammed CÜCE Veri Yapılarında Yığın ve Kuyruk Yapıları | Özge ATASEVEN Pro Evolution Soccer 2011 | Mustafa ÇUHA WMI | Rukiye Şerife BAŞTUĞ Evrenin Çöplüğü | Bihter HEPVİDİNLİ Bilgisayarın Temel Yapısı ve İnsanoğlu | Bülent ÇOBANOĞLU Windows 8 Hakkında Dedikodular | Serkan AKDEMİR Nöral Kriptografi | Gülay GENÇ
« önceki sayfa - 5 - sonraki sayfa »

Ana Sayfa | Künye | Dergimiz | | İletişim
© 2009-2010 Bilisimdergi.Com Tasarım - Kodlama : İU BİLGİSAYAR

Creative Commons License
Bilişim Dergi içeriği  Creative Commons  lisansı ile korunmaktadır.
Kaynak göstermek ve link vermek şartıyla yazılarımızı kullanabilirsiniz.