|
|
|
Bağlı Listeler ve Uygulamaları - 1 |
|
| Gönderiliyor lütfen bekleyin... |
|
|
Birçok
uygulamada problemleri çözebilemek için veri kümeleri üzerinde işlem
yapmak gerekir. Veri sadece bir değerden oluşabildiği gibi birden çok
değerlerden de oluşabilir. Örneğin, çalıştığımız şirketimiz için bir
personel takibi uygulaması geliştirdiğimizi düşünelim. Bu
uygulamamızda şirkette çalışan personllerin tümü veri kümesini oluşturacaktır.
Personel verisini tanımlayabilmemiz içinde birden çok bilgiye ihtiyacımız
olacaktır. Personelin adı, soyadı, çalıştığı bölüm, maaşı gibi bilgiler
verimizi oluşturan alanları temsil eder. Uygulamamızda çalışanların listesini
alacak bir raporlama geliştirirken veri kümemizdeki bütün verilere (personel
bilgileri) erişebilmeli ya da belirli bir personel ait maaşı hesaplarken o
personele ait bilgilere veri kümemiz üzerinde arama yaparak erişebilmeliyiz.
Burda önemli olan nokta bu veri kümesini oluşturmaktır. Bu gibi uygulamalarda
çözüm yolu olarak bağlı listeleri kullanabiliriz. Peki nedir bu bağlı liste
?(linked list). Aynı kümeye ait verilerin bellek üzerinde bir gösterici
(pointer) yardımı ile birbirine bağlanması sonucu oluşturulan veri yapısıdır.
Bu veri yapısındaki bütün elemanların ortak noktası kendi içlerinde bağlantı
bilgisi içeren kendi türünden bir ya da daha fazla göstericiye sahip
olmasıdır. Veri yapısı, kümedeki herhangi bir elemanın, kendisinden
önce ve kendisinden sonra hangi elemanın bulunduğu bilgisi bu göstericilere
değer vererek kurulur. Bağlı listelerdeki elemanlar genellikle yapılardan
(struct) oluşur. Şimdi personel bilgisi tutacak bir yapı tanımlayalım;
typedef struct _PERSONEL {
char personel_adi_soyadi[60];
char personel_bolum[20];
int personel_maas_katsayi;
/* Bu gösterci yardımı ile bir sonraki elmanın
bilgilerine erişiriz */
struct _PERSONEL* pNextPersonel;
}PERSONEL;
|
Şekil -1 |
Yapımız, personel bilgilerini tutacak bölümler ile
listedeki bir sonraki elemanın adresini gösteren pNextPersonel isimli
göstericiden oluşmaktadır. Listedeki elemanlar dizilerdeki gibi hafızada
ardışıl olmayacağından, bir sonraki elemana ulaşabilmek için bu göstericiyi
kullanarak listedeki tüm elemanlara erişebiliriz. Nerdeyse bütün bağlı
listelerdeki elemanların yapısı, şekildeki gibi biri elemanlar
arasındaki bağlantı bilgisini (p) diğeri ise elemana ait bilgileri içeren
(data) iki bölümden oluşur.
Aslında bağlı listeler programlamada ve algoritmaların
geliştirilmesinde çok önemli bir yere sahiptir. Bir çok problemin çözümü ancak
bağlı listeler kullanılarak çözülebilir, bazı uygulamalarda da problemlerin
çözülmesinde büyük kolaylıklar sağlayabilemektedir. Birçok bağlı liste veri
modeli geliştirilmiştir. Bunlara kısaca değinelim :
Tek Yönlü Bağlı Listeler : Listedeki
elemanlar arasında sadece tek bir bağ vardır. Bu tür bağlı listelerde hareket
yönü sadece listenin başından sonuna doğrudur. (Şekil - 1)
Çift Yönlü Bağlı Listeler : Listedeki
elemanlar arasında iki yönlü bağ vardır. Elemanın bağlantı bilgisi bölümünde
iki gösterici bulunur. Bu göstericinin biri kendisinden sonra gelen
elemanı diğeri ise kendisinden önce gelen elamanın adres bilgisini tutar. Bu
sayede listenin hem başından sonuna hem de listenin sonundan başına doğru
hareket edilebilir. Bu yöntem daha esnek bir yapıya sahip olduğundan bazı
problemlerin çözümünde daha işlevsel olabilmektedir. (Şekil - 2)
Dairesel Bağlı Listeler : Listedeki
elemanlar arasında tek yönlü bağ vardır. Tek yönlü bağlı listelerden tek farkı
ise son elemanın göstericisi ilk listenin ilk elamanının adresini
göstermesidir. Bu sayade eğer listedeki elemanlardan birinin adresini
biliyorsak listedeki bütün elemanlara erişebiliriz.(Şekil - 3)
Şekil - 2 |
Şekil - 3 |
Şimdi buraya kadar inceledeğimiz konuları
somutlaştırmak için örnek bir uygulama yapalım. Örneğimiz
tanıdıklarımızın mail bilgileri tutacak bir bağlı liste oluşturarak
bu liste üzerinde ekle, silme, bulma ve listeleme işlemlerini yapacak
fonksiyonları yazacağız.Bu uygulamamızda tek yönlü bağlı liste modelini
kullanacağız. Daha sonraki makalede ise çift yönlü bağlı listeleri inceleyecek
ve örnek uygulama geliştireceğiz.
Uygulamamız için ilk önce mail bilgilerini tutacak veri elemanın yapısını
hazırlayalım. Veri yapımızın data bölümü, mail sahibinin id’si,
adı, mail adresi alanlarından oluşsun. Tek yönlü bağlı
liste modelini kullanacağımız için bağlantı bölümü sadece bir göstericiye sahip
olacak. Buna göre yapımızın:
#define NAME_LEN 30
#define ADDR_LEN 256
typedef struct _MAILNODE {
char person_name[NAME_LEN];
char person_mail_addr[ADDR_LEN];
int person_id;
struct _MAILNODE *pNextMailNode;
}MAILNODE;
|
şeklinde bildirimini yaptık. Yapımızın ismi MAILNODE, mail adresinin sahibinin
ismini person_name ve mail adresini person_mail_addr dizileri ile veri
elemanında saklayacak ve mail sahibine bir ID vermek için de person_id
değişkenini kullanacağız. Şimdi de liste üzerinde yapacağımız işlemler için
fonksiyonlarımızın prototip bildirimlerini yapalım :
int get_option(void);
void set_MailNode(MAILNODE *pNode);
void display_MailNode(const MAILNODE *pNode);
void add_MailNode(void);
void list_MailNodes(void);
void delete_MailNode(void);
void find_MailNode(void);
|
get_options fonksiyonunu kullanıcıdan hangi işlemi seçtiğini belirlemek
için, set_MailNode fonksiyonunu belirlenen herhangi bir liste elemanının
bilgilerini düzenlemek için,display_MailNode fonksiyonunu yine belirlenen bir
liste elemanın bilgilerini görüntülemek için, add_MailNode fonksiyonun bir mail
veri yapısını listeye eklemek için, list_MailNodes fonksiyonunu listedeki tüm
elemanların görüntülenmesi için, delete_MailNode fonksiyonunu kullanıcının
belirttiği herhangi bir elamanın silinmesi için ve find_MailNode ise mail
adresini bildiğimiz bir elamanın bulunmasını ve bu elamanın bilgilerini
görüntülemek için kullanacağız. Bu fonksiyonları tanımlarken liste üzerinde
hareket edeceğimiz için listenin başını tutan bir değişkene ihtiyacımız olacak.
Bu değişken yine MAILNODE yapısı türünden bir gösterici olmalı ve
göstericimizin adını da g_head olarak tanımlayalım. Program
ilk defa çalıştığında listede hiçbir elaman olmadığı için g_head göstericisinin
değeri NULL yapalım.
MAILNODE* g_head = NULL;
Şimdi bildirimini yapmış olduğumuz fonksiyonların tanımlamalarını
yapalım:
#define LIST_NODES 1
#define ADD_NODE 2
#define DELETE_NODE 3
#define FIND_NODE 4
#define EXIT_PROG 5
int get_option(void)
{
char input[15];
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] CIK\n");
printf("Secenek : ");
fflush(stdin);
gets(input);
option = atoi(input);
return option;
}
|
Bu fonksiyonda , input dizisi ile kullanıcıdan alınan
menü seçeneğini tutacak ve atoi(...) fonksiyonu ile girilen değeri int
türüne çevirerek fonksiyonun geri dönüş değeri olarak belirleyeceğiz. Ayrıca
kullanıcıya şeçenekleri göstren bir menü hazırladık. Şimdi display_MailNode ve
set_MailNode fonksiyonlarının tanımlanmasına geçelim :
void display_MailNode(const MAILNODE
*pNode)
{
printf("Kisi ID = %d\n", pNode->person_id);
printf("Kisi Adi = %s\n", pNode->person_name);
printf("Mail Adresi = %s\n",
pNode->person_mail_addr);
printf("\n-------------------------\n");
} |
void set_MailNode(MAILNODE *pNode)
{
printf("Kisi ID : ");
scanf("%d", &pNode->person_id);
fflush(stdin);
printf("Kisi Adi : "); gets(pNode->person_name);
printf("Mail Adresi : ");
gets(pNode->person_mail_addr);
} |
set_MailNode fonksiyonu MAILNODE türünden bir
gösterici alarak ilgili ilgili yapının elemanlarını düzenlememizi sağlar.
display_MailNode fonksiyonu da benzer şekilde bilgisinin görüntülenmesini
istediğimiz liste elemanının adresini alarak bilgilerini ekrana yazdırır.
Şimdi ise listeye eleman ekleyen add_MailNode fonksiyonunu tanımlayalım :
void add_MailNode(void)
{
/* aslında malloc
fonksiyonun geri dönüş değerini cast etmemize gerek yok. Ama bazı
derleyiciler bu konuda problem çıkardığı için
biz yine de cast edelim */
MAILNODE *new_node = (MAILNODE
*)malloc(sizeof(MAILNODE));
if (new_node == NULL)
{
printf("Yeterli memory
yok!\n");
exit(EXIT_FAILURE);
}
set_MailNode(new_node);
new_node->pNextMailNode = g_head;
g_head = new_node;
}
|
Daha önce de belirttiğimiz gibi program ilk
çalıştığında g_head NULL değerdedir yani herhangi bir elemanı göstermez.
Listeye bir eleman eklemek istediğimizde bunu hafızada (memory) dinamik olarak
oluştururuz. Bunu malloc ile gerçekleştirdikten sonra her ihtimale karşı
işlemin başarılı olup olmadığını kotrol etmeliyiz. Daha sonra dinamik
olarak oluşturduğumuz elemanın bilgilerini set_MailNode ile
düzenledik ve böylece eleman listeye eklenmek için hazır hale geldi. Eğer
eklediğimiz eleman ilk elemansa yani daha öncesinde liste boş ise eklediğimiz
elemanın bağlantı bilgisinde NULL değer olmalı çünkü kendisinden sonra hiç bir
elaman yok. Eğer daha önce listede herhangi bir eleman varsa iki şekilde
listeye eleman ekleyebiliriz. Birinci seçeneğimiz listenin başına ikinci
seçenek ise listenin sonuna eklemektir. Bu örnekte listenin başına ekleyeceğiz.
Eğer listenin başına ilk defa eleman ekleniyor ise new_node->pNextMailNode =
g_head; ile elemanın gösterdiği sonraki eleman NULL değer olacaktir
ki (g_head’in NULL değere sahip olduğunu hatırlayalım.) bu da listenin ilk
elemanı olduğunu gösterir. g_head listenin başını yani ilk elemanını gösteren
gösterici olduğuna göre g_head = new_node; ile listenin başını belirlemiş
oluyoruz. Bir sonraki eleman eklenme işleminde (biz elemanı listenin başına
ekliyoruz!) bu eleman listenin başında olmasını istediğimizden kendisinden
sonra gelecek olan elman listenin başındaki eleman olmalıdır. Peki listenin
başını tutan elamanımız hangisi? g_head! o zaman new_node->pNextMailNode =
g_head; dersek son oluşturduğumuz eleman listenin başına geçecek ve g_head
= new_node; ile de bir sonraki eleman ekleme işlemi için listenin başı belli
olacaktır. Peki biz elemanları listenin sonuna eklemek isteseydik nasıl bir yol
izleyecektik? Öncelilkle yeni oluşturduğumuz elemanın son eleman oldugunu
belirlemek için listeye eklemeden önce pNextMailNode =NULL; olması gerekir.
Daha sonra bütün listeyi dolaşarak (bir for döngüsü ile listedeki elemanların
pNextMailNode bilgisinin NULL olup olmadığını kontrol ederek) en son elemanı
belirleyip, bu elemanın pNextMailNode değerini yeni oluşturduğumuz
elemanın adresi ile değiştirmeliyiz. Böylece listenin başına hiç dokunmadan
sadece son eleman üzerinde değişiklikler yaparak yeni elemanı (new_node)
listenin sonuna ekleyebiliriz. Bu özelliğin uygulamamıza eklenmesini alıştırma
olması bakımından size bırakıyorum.
Şimdi de listemizdeki tüm elemanların dökümünü verecek list_MailNodes
fonsiyonunun bildirimini yapalım :
void list_MailNodes(void)
{
MAILNODE *pNode;
if (g_head == NULL) {
printf("Listelenecek kayit
bulunamadi!!!\n");
return;
}
printf("\n*******LISTE*******\n");
for(pNode = g_head; pNode ! = NULL; pNode =
pNode->pNextMailNode)
display_MailNode(pNode);
} |
Liste alırken dikkat etmemiz gereken konu listede
eleman olup olmadığını anlamamızdır. Bunu ise sadece g_head in NULL olup
olmadığına bakarak anlayabiliriz. Ekleme işlemlerinde dikkat edersek g_head in
değeri değişerek NULL olmayan bir değere sahip oluyordu. Son adımda ise eğer
listede eleman veya elemanlar mevcut ise MAILNODE türünden bir gösterici
yardımı ile listemizi dolaşıyoruz (listenin sonuna geldiğimizi ise pNode nin
NULL olup olmadığına bakarak anlarız) ve her eleman için display_MailNode
fonksiyonunu kullanarak bilgileri ekrana yazdırıyoruz.Şimdi ise yine önemli
fonksiyonlardan biri olan delete_MailNode fonksiyonunun tanımlamasını yapalım :
void delete_MailNode(void)
{
int person_id;
MAILNODE *pCurNode, *pPrevNode;
printf("Silinecek Kisi ID : ");
scanf("%d", &person_id);
for (pPrevNode = NULL, pCurNode = g_head; pCurNode ! = NULL
&& pCurNode->person_id ! = person_id;pPrevNode = pCurNode, pCurNode
= pCurNode->pNextMailNode)
;
if (pCurNode == NULL)
{
printf("%d nolu kayit listede
bulunamadi!!!\n", person_id);
return;
}
if (pPrevNode == NULL)
g_head = g_head->pNextMailNode;
else
pPrevNode->pNextMailNode =
pCurNode->pNextMailNode;
printf("%d nolu kayit silindi.\n", person_id);
free(pCurNode);
} |
Şekil - 4
|
Silme işlemini id değerine göre yapacağımızdan
kullanıcıdan elemanın id değerini person_id ile alıyoruz. Silme işleminin
mantığı ise, önce silinecek elemanı listenin başından başlayarak ararız.
Bulduğumuz zaman bu elemandan önceki ve sonraki değerleri bilememiz
gerekecektir. Örneğin listemizde elemanlar X->Y->Z şekinde yer aldığını
düşünelim. Bu durumda biz Y elemanını silmek isteğimizde X in sonraki elemanını
gösteren pNextMailNode Z nin adresini göstermelidir. Eğer bu ayarlamayı
yapmazsak Z elemanına erişimi kaybetmiş oluruz. Eğer X’i yani ilk elemanı
silmek istediğimizde ise g_head yani listenin başını gösteren gösterici bu defa
da Y elemanını gösterecek biçinde ayarlanmalıdır. Eğer bunu yapmazsak
listeyi tamami ile kaybetmiş oluruz. Bu tasarımı gerçekleştirmek için
birbirini peşisıra takip eden iki tane MAILNODE türünden göstericiye
ihtiyacımız var. Örneğimizde pCurNode bulmak istediğimiz elemanı, pPrevNode ise
ondan önceki elemanı göstren göstericilerdir. İlkbaşta pPrevNode NULL değeri,
pCurNode ise listenin başındaki elemanı gösterir. Eğer döngü bittiğinde
(pCurNode, NULL değere sahipse listenin son elemanına geldiğimizi,
pCurNode->person_id person_id değerine eşitse istediğimizi bulduğumuzu
anlarız ve for döngüsünden çıkarız)pCurNode NULL değere sahip ise
istediğimiz id’ye göre bir eleman bulunamamış demektir ve kullanıcıyı
bilgilendirerek fonksiyonu sonlandırırız. Eğer döngü bittiğinde pPrevNode NULL
değere sahip ise bu durum bize ilk elemanı silmek istediğimizi söyler. Bu
durumda yapılacak iş, g_head in listenin ikinci elemanını göstermesini
sağlamaktır. g_head->pNextMailNode listenin ikinci elemanını gösterdiğinden
g_head = g_head->pNextMailNode; ile listenin ilk elemanını değiştirmiş
oluruz. Bunlar dışında silmek için aradığımız özelliğe sahip bir eleman
bulunduğunda, kendisinden önceki elemanın pNextMailNode göstericisine,
kendisinden sonra gelen elemanın adresini vermeliyiz.(Aklınıza son elemanı
silmek istediğimizde (Z) ne olacak gibi bir soru geliyorsa son elemanın
pNextMailNode değer NULL değer olduğunda ve kendisinden önce gelen elemanın
(Y) pNextMailNode değerine NULL atanacağından listemizin son elemanını (Y)
yine belirlemiş oluruz ). Son adımda ise artık bu eleman için
ayırdığımız bölge işimize yaramadığından free(...) fonksiyonunu bu
bölgeyi sisteme iade etmeliyiz.
Son olarak listemizde belirli özelliklere göre arama
yapmak için find_MailNode fonksiyonumuzu tanımlayalım.
void find_MailNode(void) {
char person_mail_addr[ADDR_LEN];
MAILNODE *pCurNode;
printf("Bulunacak Kisinin Mail Adresi : ");
gets(person_mail_addr);
for (pCurNode = g_head; pCurNode ! = NULL &&
strcmp(pCurNode->person_mail_addr, person_mail_addr) ; pCurNode =
pCurNode->pNextMailNode)
;
if (pCurNode == NULL) {
printf("%s mail adresine iliskin
kayit listede bulunamadi!!!\n", person_mail_addr);
return;
}
display_MailNode(pCurNode);
} |
Arama fonksiyonumuzda, kullanıcıdan bulunduğunda o
eleman ile ilgili bilgilerinin görüntülenmesini istediğimiz mail adresi
bilgisinin girilmesini istiyoruz. for döngümüzde yine listeyi başatan sona
kadar dolanıyoruz. strcmp fonksiyonu ile girilen mail adresi ile o an listedeki
elemana ait mail adresi birbirine eşit ise döngüye son veriyoruz. Döngü
bittiğinde eğer pCurNode, NULL ise ya listede hiç eleman yoktur veya
listenin sonuna kadar gelinmiştir ve hiçbir eşleşen kayıt bulunamamıştır. Eğer
bulundu ise display_MailNode(...) ile bulunan elemanın bilgileri ekrana
yazılır. Bu yazdığımız fonksiyonlarımızı test etmek için main fonksiyonunu
yazalım :
int main(int argc,char *argv[])
{
int option;
while(1) {
option = get_option();
switch(option) {
case
LIST_NODES : list_MailNodes();break;
case
ADD_NODE : add_MailNode();break;
case
DELETE_NODE : delete_MailNode();break;
case
FIND_NODE : find_MailNode();break;
case
EXIT_PROG : goto EXIT_POINT;
default
: printf("Secmis oldugunuz secenek gecersiz\n");
}
}
EXIT_POINT:
printf("\nProgram sonlandirildi\n");
return 0;
}
|
Kullanıcıya get_option ile hazırladığımız menüyü
gösterip seçeneği aldıkdan sonra switch bloğuna sokarak gerekli fonksiyonu
çağırıyoruz. Sonsuz döngünün sebebi ise işlem bittikten sonra menüyü tekrar
ekrana getirmektir. Eğer kullanıcı programdan çıkmak isterse goto ile
EXIT_POINT ile belirttiğimiz noktaya programı yönlendirerek programı
sonladırmış oluyoruz.
Bir sonraki makalemizde Çift Yönlü Bağlı listeleri inceleyecek ve örnek bir
uygulama geliştirmeye çalışacağız.
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ı - 1 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
|
|
|