C’de Öncelik Kuyruğu

Bu yazıdaki kod örneği C’de bağlı liste (bağlaçlı liste, linked list) kullanarak öncelik kuyruğu (küçükten büyüğe sıralı bağlı liste) kullanıma ufak bir örnek oluşturuyor.

Bağlaçlı liste yapısının işleyişini Wikipedia’dan aldığım aşağıdaki çizim oldukça iyi açıklıyor:

Görebileceğiniz gibi her bir kutucuk bir bilgi ve bir sonraki bilginin referans/bellek adresini içeriyor.

Öncelik kuyruğu, küçük olanın hep ilk çıkması demektir. Kuyruğa giriş sırası fark etmeksizin ufak olan sayılar daha önce çıkar. Bunu bağlaçlı liste ile bellekte tutmak istersek aklımıza iki yöntem gelebilir:

Bunlardan birincisi, geleni standart bir kuyruktaki gibi sona eklemek, kuyruktan eleman çıkarılacağında ise tüm kuyruğu gezerek en küçük elemanı aramak olabilir. Bağlı liste yapısında arama doğrusal yapılacağı için en kötü ihtimalle n tane (n eleman sayıdır) karşılaştırma gerekecektir.

İkinci yöntem ise gelen yeni veriyi sıralayarak bağlı listedeki uygun yere eklemektir. Böylece liste hep sıralı kalacaktır. Bağlı listenin ilk elemanı (kuyruğun başındaki eleman) hep en küçük eleman olacaktır. Liste gezildiğinde (ki bağlı bir listeyi sadece doğrusal gezebilirsiniz) elemanlar küçükten büyüğe sıralı çıkacaktır.

Benim kod örneğim ikinci yöntemi içeriyor. Örneğimde bağlı listeye sıralı eleman ekleme ve elemanları listeme (bağlı listeyi bir defa sıralı gezme) yer alıyor.

C dilinde daha kapsamlı bir bağlı liste örneği Wikipedia’da mevcut.

Not: Benim örneğimde harflerin karşılaştırılması ASCII koduna göre yapılmıştır.

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

/* Bagli Liste Yapisi */
struct list_el {
   char karakter;
   struct list_el *sonraki;
};

typedef struct list_el bliste;

/* Fonksiyon Prototipleri */
void beklet();
void bliste_m();
void bliste_ekle(char, bliste**);
int main();

void beklet() {
    /* Bu fonksiyonun tek amaci kullaniciyi bir tusa basana kadar
       bekletmek, ve sonra ekrani silmektir. */
    printf("\nDevam etmek icin bir tusa basin.");
    getche();
    system ("cls");
}

void bliste_m() {
    /* Bagli liste icin gerekli ilk tanimlamalar */
    bliste *simdiki, *bas;
    bas = NULL;

    /* Eklenecek veriyi ekrandan alma. */
    char eklenecek='a';
    printf("Sirali bagli listeye harf ekleyeceksiniz. Ekleme islemini 'x' yazarak birebilirsiniz.\n");
    while(eklenecek !='x') {
        eklenecek = getche();
        bliste_ekle(eklenecek,&bas);
        printf(" ");
    }
    printf("Bagli listenin icindekiler sirasiyle yazdiriliyor:\n");

    /* Bagli listeyi gezip, listeleme. */
    simdiki = bas;

    while(simdiki) {
        printf("%c\n", simdiki->karakter);
        simdiki = simdiki->sonraki ;
   }
}

void bliste_ekle(char c, bliste **bas) {
    /* Bagli listeye sirali eleman ekler. */
    bliste *onceki = NULL, *eklenecek, *etkin ;

    /* Bagli liste ile oncelik kuyrugu uygulamasi */
    eklenecek = (bliste*)malloc(sizeof(bliste));
    eklenecek->karakter = c;
    eklenecek->sonraki = NULL;

	etkin = *bas;

    /* Bu kisim bagli listeye sirali sekilde eleman ekler */
    while (etkin != NULL && eklenecek->karakter > etkin->karakter) {
        onceki = etkin;
        etkin = etkin->sonraki;
    }

    if (onceki == NULL) {
        *bas = eklenecek;
    } else {
        onceki->sonraki = eklenecek;
    }
	eklenecek->sonraki = etkin;

}

int main() {
    bliste_m();
    beklet();
    return 0;
}