 SİTE
İÇİ ARAMA |
|
|
 Blogroll |
|
|
|
|
|
|
Bağlı Listeler ve Uygulamaları - 2 |
|
| Gönderiliyor lütfen bekleyin... |
|
|
Daha önceki makalede bağlı listeler konusuna giriş yapıp, bağlı liste türlerini incelemiş ve tek yönlü bağlı listeler ile ilgili bir örnek uygulama geliştirmiştik
(İlgili makaleyi buraya tıklayarak okuyabilirsiniz). Bu makalemizde
çift yönlü bağlı listeler (doubled linked list) konusunu inceleyip bir
örnek uygulama geliştireceğiz.
Çift yönlü bağlı liste, tek yönlü bağlı listelere ek
olarak, elemana kendisinden önceki elamanı da gösteren bir
göstericinin dahil edilmesi ile hazırlanan elemanlar kümesinden oluşturulur.
Yani listedeki bir eleman kendisinden önceki ve sonraki elemanlara
ilişkin bağlantı bilgisi içerir. Çift yönlü bağlı listenin, tek yönlü
bağlı listeye göre en önemli avantajı listede ileriye ve geriye doğru hareket
ederek, ekleme ve silme işlemlerini basitleştirip listemizin yönetimini daha da
kolaylaştırmaktır. Bu uygulamamızda dosya sistemi oluşturacağız. Yapımız
dosyanın ismini, dosyanın büyüklüğünü ve dosyanın özellik bilgilerini tutacak.
Ayrıca bu örneğimizde bilgileri bir dosyaya yazacak ve dosyadan okuyacak
fonksiyonları da yazacağız. Şimdi bu yapının bildirimini yapalım.
/*sembolik sabitler */
#define NAME_LEN 128
#define LIST_NODES 1
#define ADD_NODE 2
#define DELETE_NODE 3
#define FIND_NODE 4
#define SAVE 5
#define LOAD 6
/* yapı bildirimi */
typedef struct _FILENODE {
char file_name[NAME_LEN];
int file_size, file_attr;
struct _FILENODE *pNextFileNode, *pPrevFileNode;
}FILENODE;
|
Yapı, dosyanın ismini tutacak char türünden bir dizi,
dosyanın büyüklük ve özellik bilgisini tutacak int türünden iki değişken ve
struct _FILENODE türünden iki göstericiden oluşmaktadir. pNextFileNode
göstericisi, elamanın, kendisinden sonra gelen elemanın, pPrevFileNode
göstericisi ise kendisinden önce gelen elemanın bellekdeki adres bilgisini
tutar.Böylece tek yönlü bağlı listelere ek olarak listemizde geriye doğru
da hareket edebiliriz. Şimdi listemiz üzerinde işlem yapacak
fonksiyonlarımızın bildirimini ve tanımlamalarını yapalım.
/* fonksiyon prototip bildirimi */
int get_option(void);
void set_FileNode(FILENODE *pNode);
void display_FileNode(const FILENODE *pNode);
void add_FileNode(void);
void add_FileNodeFromDB(FILENODE *pNode);
void list_FileNodes(void);
void find_FileNode(void);
void delete_FileNode(void);
int save(void);
int load(void);
/* global değişkenler */
FILENODE *g_pHead = NULL, *g_pTail = NULL; |
Tek yönlü bağlı liste örneğindeki birçok fonksiyon bu
örneğimizde de var. Ek olarak add_FileNodeFromDB örneği ile database
dosyasından yükleme yapacağımızda listemize elemanları bu fonksiyon ile
ekleyeceğiz. Yine save fonksiyonu ile listemizi bir dosyaya kaydedecek, load
fonksiyonu ile dosyadaki kayıtlı elemanları listemize yükleyeceğiz. Global
değişkenlerden g_pHead listedeki ilk elemana ve g_pTail ise listedeki son
elemana erişmek için kullanacağız. Listede hiçbir eleman olmadığından bu
göstericilere NULL değerler atadık.
int get_option(void) {
char input[20];
int option;
printf("\n*******MENU*******\n");
printf("[1] LISTELE\n");
printf("[2] KAYIT EKLE\n");
printf("[3] KAYIT SIL\n");
printf("[4] KAYIT BUL\n");
printf("[5] KAYDET\n");
printf("[6] YUKLE\n");
printf("[7] CIK\n");
printf("Secenek : ");
fflush(stdin);
gets(input);
option = atoi(input);
return option;
}
|
get_option fonksiyonu ile bir menü gösterip
kullanıcıdan yapacağı işlemi belirlemesini sağlıyoruz.
void set_FileNode(FILENODE *pNode) {
printf("Dosyanin ismi : ");
gets(pNode->file_name);
printf("Dosyanin buyuklugu : ");
scanf("%d", &pNode->file_size);
printf("Dosyanin ozelligi : ");
scanf("%d", &pNode->file_attr);
} |
set_FileNode fonksiyonu ile adresi verilen yapının
elemanlarının düzenlenmesini sağlıyoruz.
void display_FileNode(const FILENODE *pNode) {
printf("Dosyanin ismi : %s\n", pNode->file_name);
printf("Dosyanin buyuklugu : %d\n",
pNode->file_size);
printf("Dosyanin ozelligi : %d\n", pNode->file_attr);
printf("------------------------------\n");
} |
display_FileNode fonksiyonu adresi verilen yapının
bilgilerini ekrana yazar.
void add_FileNode(void) {
FILENODE *pNode = (FILENODE *) malloc(sizeof(FILENODE));
if (pNode == NULL) {
printf("Yeterli bellek
ayrilamadi!");
exit(EXIT_FAILURE);
}
set_FileNode(pNode);
if (g_pHead == NULL) {
g_pHead = pNode;
pNode->pPrevFileNode = NULL;
}
else {
g_pTail->pNextFileNode = pNode;
pNode->pPrevFileNode = g_pTail;
}
g_pTail = pNode;
pNode->pNextFileNode = NULL;
} |
add_FileNode fonksiyonu ile listeye eleman eklemek için kullanıyoruz. Eleman
eklerken dikkat etmemiz gereken şey listenin boş ya da dolu olup olmadığı.
Şimdi fonksiyonu incelemeye başlıyalım. İlk adımda eklenecek eleman için
bellekte yer tahsis ediyoruz. Eğer tahsisat işlemi başarısız ise programı
sonlandırıyoruz. Sonraki adımda set_FileNode fonksiyonu ile elemanın
bilgilerini düzenliyoruz. Sonrasında g_pHead ’in NULL olup olmadığına
bakıyoruz. Eğer NULL ise liste boş demektir. Bu durumda g_pHead ’a pNode yi
atayarak, g_pHead ’in listenin ilk elemanını göstermesini sağlıyoruz. İlk
eleman pNode olduğundan bundan öncesinde de eleman olmadığından pNode nin
kendisinden önceki elemanı gösteren göstericiye NULL değerini atıyoruz. Listede
tek eleman olduğunda bu eleman aynı zamanda listenin son elemanı olduğundan
listenin son elemanını gösteren g_pTail ’e pNode yi atayarak aynı
zamanda listenin son elemanınıda belirlemiş oluyoruz.Listede başka eleman
olmadığına göre bu elemanın kendisinden sonraki elemanı gösteren göstericiye de
NULL değerini atıyoruz. Eğer listede eleman var ise listenin sonuna yeni
elemanımızı ekleyeceğiz. O anda listedeki son elemanın kendisinden
sonraki elemanı gösteren göstericisine ekleyeceğimiz elemanın adresini
atıyoruz. Eklediğimiz elemandan (pNode) önceki eleman hala g_pTail
olduğuna göre bu elemanın kendisinden önceki elemanı gösteren göstericisine
g_pTail göstericisini atıyoruz. Eklediğimiz elemanın listedeki son eleman
olmasını istediğimiz için g_pTail e elemanımızın adresini (pNode) atıyoruz.
Artık eklemek istediğimiz eleman, son eleman olduğuna göre kendisinden sonra
eleman bulunmadığını belirtmek için kendisinden sonraki elemanı gösteren
göstericisine NULL değerini atıyoruz.
void add_FileNodeFromDB(FILENODE *pNode) {
if (g_pHead == NULL) {
g_pHead = pNode;
pNode->pPrevFileNode =
NULL;
}
else {
g_pTail->pNextFileNode = pNode;
pNode->pPrevFileNode =
g_pTail;
}
g_pTail = pNode;
pNode->pNextFileNode = NULL;
} |
add_FileNodeFromDB fonksiyonu, listemizin diskteki dosyadan kayıtlar
okunarak oluşturulması sırasında kullanacağız. add_FileNode fonksiyonundan
farklı olarak FILENODE türünden bir gösterici alması ve bu gösterici yardımı
ile elemanın listeye eklenmesini sağlamaktadır. Dosyada halihazırda daha
önceden oluşturduğumuz kayıtlar vardır. Bu kayıt belleğe yüklenecek ve kaydın
adresi add_FileNodeFromDB ye argüman olarak verilerek listeye ekleme
işlemini gerçekleştireceğiz.
void list_FileNodes(void) {
FILENODE *pNode;
int record_count = 0;
pNode = g_pHead;
if (g_pHead == NULL){
printf("Listelenecek eleman yok!");
return;
}
while (pNode) {
display_FileNode(pNode);
++record_count;
pNode = pNode->pNextFileNode;
}
printf("\nToplam %d kayit listelendi\n", record_count);
}
|
list_FileNode fonksiyonu ile listedeki bütün elemanların ekrana yazdırılmasını
sağlıyoruz. Listenin başını bir gösterici ile alıyoruz.
Eğer bu göstericinin değer NULL ise listede eleman yok demektir. Uyarımızı
verip fonksiyonu return; ile sonlandırıyoruz. Eğer eleman var ise
display_FileNode ile elemanın bilgilerini ekrana yazdırıp,
göstericiye kendisinden sonra gelen elemanın adresini atıyoruz. Son
elemana gelindiğinde gösterici (pNode) NULL değere sahip olacak ve while
döngüsünden çıkılacaktır. record_count değişkeni ile kaç elemanın listelendiği
bilgisini tutuyoruz. Son adımda kaç eleman listelendiğini ekrana yazdırıyoruz.
void find_FileNode(void) {
FILENODE *pNode;
char file_name[NAME_LEN];
pNode = g_pHead;
printf("Bulunacak dosyanin ismi : ");
gets(file_name);
while(pNode) {
if (!strcmp(pNode->file_name,
file_name)) {
printf("\n*****Bulunan Dosyanin bilgileri*****\n");
display_FileNode(pNode);
return;
}
pNode = pNode->pNextFileNode;
}
printf("%s dosya ismi ile eslesen kayit bulunamadi!!!\n",
file_name);
} |
find_FileNode fonksiyonu ile listede dosya işlemine göre arama yapıyoruz.
Öncelikle kullanıcıdan bulunmasını istediğimiz elemanın dosya ismi bilgisini
alıyoruz. Yine bir gösterici yardımı ile listenin ilk elemanını alıp listede
yürümeye başlıyoruz. strcmp fonksiyonu ile kullanıcıdan alınan dosya ismi ile
elemanın dosya ismi bilgisi karşılaştırılıyor. Eğer eşleşme sağlandı ise
display_FileNode fonksiyonu ile elemanın bilgileri ekrana yazdırıp fonksiyonu
sonlandırıyoruz. Eğer eşleşme yok ise bunu kullanıcıya bildiriyoruz.
void delete_FileNode(void) {
FILENODE *pNode;
char file_name[NAME_LEN];
pNode = g_pHead;
printf("Silinecek dosyanin ismi : ");
gets(file_name);
while(pNode) {
if (!strcmp(pNode->file_name,
file_name)) {
if
(pNode->pPrevFileNode == NULL) /* ilk
eleman ise - p1 */
g_pHead = pNode->pNextFileNode;
else
pNode->pPrevFileNode->pNextFileNode = pNode->pNextFileNode;
if
(pNode->pNextFileNode == NULL) /* son
eleman ise - p2 */
g_pTail = pNode->pPrevFileNode;
else
pNode->pNextFileNode->pPrevFileNode = pNode->pPrevFileNode;
printf("%s
dosyasi listeden silindi!\n", pNode->file_name);
free(pNode);
return;
}
pNode = pNode->pNextFileNode;
}
printf("%s dosya ismi ile eslesen kayit bulunamadi!!!\n",
file_name);
} |
delete_FileNode ile kullanıcıdan aldığımız dosya ismine göre listede eşleşen
bir kayıt bulduğumuzda ilgili kaydın silinmesi işlemini gerçekleştiriyoruz.
Eşleşen kayıt bulunduğunda silme işlemi gerçekleşirken dikkat etmemiz gereken
durumlar var. Listede sadece bir eleman mı var, ilk elemanı mı siliyoruz, son
elemanı mı siliyoruz yoksa aradan bir eleman mı siliyoruz. Eğer ilk
elemanı siliyorsak , listenin başındaki ilk elemanı gösteren (g_pHead)
göstericiyi düzenlememiz gerekir. Böylece listenin ilk elemanı
değiştirmiş oluruz. (Tabiri caizse "ipin ucunu" kaçırmamak için). Eğer ilk
eleman silinecek ise; listenin başını gösteren göstericiye silinecek elemandan
(pNode) sonraki elemanı gösteren gösterici atanır. Eleman silinmeden önce
silinecek elemandan sonraki ve önceki elemanlar arasında bağlantı kurmamız
gerekir. O zaman silinecek elemandan (pNode) sonra gelen elemanın
(pNode->pNextFileNode) kendisinden önce gelen elemanı gösteren
göstericisine (pNode->pNextFileNode->pPrevFileNode), silinecek olan
elemandan önceki elemanın (pNode->pPrevFileNode) adresi atanır. Artık
silinecek elemandan önceki ve sonraki elemanlar arasında bağlantı olduğuna göre
elemanı rahatlıkla silebiliriz. free(pNode); ile pNode için bellekde tahsis
edilen alan sisteme iade edilirek listeden eleman silinmiş olur. Eğer son
eleman silinecek ise ; Kendisinden önceki elemanın kendisinden sonra gelen
elemanı gösteren göstericisine
(pNode->pPrevFileNode->pNextFileNode), silinecek olan elemandan sonraki
elemanın (pNode->pNextFileNode) adresi atanmalıdır(NULL değer atandığına
dikkat ediniz.).Daha sonra listenin son elemanını belirlemek için g_pTail
göstericisine silinecek olan elemandan önceki elemanın
(pNode->pPrevFileNode) adresi atanmalıdır.Artık listenin sonunu da
belirlemiş olduk ve free(pNode); ile son elemanıda silebiliriz. Peki aradan bir
eleman silinir ise; o zaman silinecek elemandan (pNode) önce gelen
elemanın (pNode->pPrevFileNode) kendisinden sonra gelecek elemanı gösteren
göstericiye (pNode->pPrevFileNode->pNextFileNode), silinecek olan
elemandan sonra gelen (pNode->pNextFileNode) elemanı gösteren gösterici
atanmalıdır. Aynı şekilde, silinecek olan elemandan sonra gelen elemanın
(pNode->pNextFileNode) kendisinden önce gelen elemanı gösteren göstericisine
(pNode->pNextFileNode->pPrevFileNode), silinecek olan elemanın
kendisinden önce gelen elemanı gösteren (pNode->pPrevNode) göstericisi
atanır.Artık silinecek elemandan bir önceki ve bir sonraki elemanlar arasında
bağlantı kurulduğuna göre free(pNode); ile tahsis edilmiş alan tekrar sisteme
iade edilerek silme işlemi gerçekleştirilir. Peki listede sadece tek eleman
varsa ve silemek istersek ;Bu durumda silinecek olan elemanın
kendisinden sonra ve önceki elemanları gösteren göstericilerin NULL değerde
olması gerekir. O zaman yapmamız gereken şey listenin başını ve sonunu
gösteren göstericilere NULL değeri atayarak listeyi boşaltmak ve
listedeki tek elemanın bellekteki alanını free fonksiyonu ile
sisteme iade etmektir. Bu durumda yazmış olduğumuz fonksiyonun p1 ve p2
ile işaretlenmiş kısımları çalışacaktır.
int save(void) {
FILE *pDB;
FILENODE *pNode;
int record_count = 0;
if ((pDB = fopen("database.cso","wb")) == NULL) {
printf("database.cso dosyasi
olusturulamadi\n");
return -1;
}
pNode = g_pHead;
printf("\nKayit islemi basladi\n");
while(pNode) {
fwrite(pNode, sizeof(FILENODE), 1,
pDB);
++record_count;
pNode =
pNode->pNextFileNode;
}
printf("\nKayit Islemi Tamamlandi. Toplam %d kayit
eklendi\n", record_count);
fclose(pDB);
return 1;
} |
save fonksiyonu ile listemizdeki tüm elemanları diskte database.cso adlı bir
dosya oluşturarak dosyaya kaydedilmesini sağlar.
Bu sayede verilerimiz kalıcı olarak saklanmış olur. Öncelikle fopen ile
dosyamızı oluşturuyoruz.Yine bir gösterici ile listenin ilk elemanına
gidiliyor ve eğer kayıt var sie fwrite ile bu elemanan dosyaya yazılıyor. Daha
sonra gösterici bir sonraki elemana gidiyor ve kaydediliyor. Eğer dosyanın
sonuna gelindiğinde gösterici (pNode) NULL değere sahip olacak ve döngüden
cıkılacaktır.Son adımda fclose ile dosya kapatılır. Fonksiyonun geri dönüş
değeri fonksiyonun başarılı olup olmadığını belirlemek için kullanılabilir.
Eğer geri dönüş değeri -1 ise fonksiyonumuz başarısız, 1 ise başarılı olarak
işlemini tamamlamıştır.
int load(void) {
FILE *pDB;
FILENODE *pTemp;
int record_count = 0;
if ((pDB = fopen("database.cso","rb")) == NULL) {
printf("database.cso dosyasi
acilamadi\n");
return -1;
}
while (g_pHead) { /* liste boşaltılıyor */
pTemp = g_pHead->pNextFileNode;
free(g_pHead);
g_pHead = pTemp;
}
g_pHead = g_pTail = NULL;
printf("\nYukleme Islemi Basladi\n");
while(!feof(pDB)) {
pTemp = (FILENODE
*)malloc(sizeof(FILENODE));
if (pTemp == NULL) {
printf("Bellek yetersiz!");
exit(EXIT_FAILURE);
}
if (fread(pTemp, sizeof(FILENODE),
1, pDB) != 1)
break;
add_FileNodeFromDB(pTemp);
++record_count;
}
printf("\nYukleme Islemi Tamamlandi. Toplam %d kayit
yuklendi\n", record_count);
fclose(pDB);
return 1;
}
|
load fonksiyonu ile daha önce save fonksiyonu ile listeyi kaydettiğimiz dosyadan
okuma yaparak bellekte dinamik olarak listeyi oluşturma işlemini
gerçekleştirir. Yalnız dikkat etmemiz gereken nokta dosyadan yükeleme yaparken
listeyi boşaltmamız gerekir .Aksi durumda listeye sürekli aynı elemanlar
eklenecektir. İlk adımda daha önceden oluşturduğumuz database.cso dosyası
açılır. Sonraki adımda o anda bellekte olan liste boşaltılır. Tabi bu durumda
listenin başını ve sonunu gösteren göstericilerin de NULL değere sahip olması
gerekir. Dosyanın sonu gelene kadar dosyadan okuma yapılır. Önce dosyadan
okunacak her bir eleman için bellekte yer tahsis edilir. fread ile dosyadan bir
eleman okunur ve daha önceden ayrılmış belleğe bu bilgi yazılır. Son adımda ise
add_FileNodeFromDB fonksiyonu ile bu eleman listeye eklenir. İşlemler bittikten
sonra fclose ile dosya kaptılır. Yine bu fonksiyonun işlemini başarılı bir
şekilde yapıp yapmadığını kontrol etmek için geri dönüş değerinden
yararlanılabilir. Şimdi bu fonksiyonlar için test bölümünü yazalım.
int main(int argc,char *argv[]) {
int option;
while(1) {
option = get_option();
switch(option) {
case
LIST_NODES : list_FileNodes();break;
case
ADD_NODE : add_FileNode();break;
case
DELETE_NODE : delete_FileNode();break;
case
FIND_NODE : find_FileNode();break;
case SAVE :
save();break;
case LOAD :
load();break;
case
EXIT_PROG : goto EXIT_POINT;
default :
printf("Secmis oldugunuz secenek gecersiz\n");
}
}
EXIT_POINT:
printf("\nProgram sonlandirildi\n");
return 0;
} |
Birçok algoritmanın geliştirilmesinde, birçok problemlerin çözülmesinde, sistem
proglamlamada ve bir çok programdaki kuyruk yapılarının tasarlanmasında
sıklıkla kullanılan bağlı listeler konusuna ve veri kümleri üzerinde işlemlerin
nasil geliştirildiğine değinmiş olduk.
Mutlu ve sağlıklı günler...
Programın kaynak kodunu ve çalıştırılabilir
halini burdan indirebilirsiniz.
Makale:
Bağlı Listeler ve Uygulamaları - 2 C ve Sistem Programlama Oğuz Yağmur
|
|
|
|
|
-
-
Eklenen Son 10
-
Bu Konuda Geçmiş 10
Bu Konuda Yazılmış Yazılmış 10 Makale Yükleniyor
Son Eklenen 10 Makale Yükleniyor
Bu Konuda Yazılmış Geçmiş Makaleler Yükleniyor
|
|
|
|