Veri Yapıları Ders Notları

Dizi kullanımı etkin programlamanın ayrılmaz bir parçasıdır.Belleğin muhtelif lokasyonlarında bulunan çok miktardaki bilgi üzerinde ayrı ayrı işlme yapmak yerine, belleğin ardışıl pozisyonlarına yerleştirilen bilgiler üzerinde işlem yapmak çok daha pratiktir. Ardışıl bellek lokasyonlarında yer alan ve tek bir isimle temsil edilebilen bilgi topluluğuna "dizi" adı verilir. Bir bilgi topluluğunun dizi olabilmesi için topluluktaki tüm elemanların aynı ortak özelliğe sahip olması gerekir. Programlamada kullanılacak bütün dizilere bir isim vermek gerekir. Örneğin haftanın günleri dizisine gunler simini verebiliriz. Dizi isimleri kavram olarak diziyi oluşturan elemanların tamamını temsil eder. Diziyi oluşturan elemanlardan herhangi bir tanesini ifade edebilmek için elemanın dizi içindeki yerleşimini gösteren bir sayının dizi ismi ile kullanılması gerekir. Dizi elemanlarının dizi içindeki yerleşimlerini belirten sayılara "indis" adı verilir. Indis değerleri belirli bir sayıdan itibaren birer birer artan tamsayılardır.

Örnek

var

gunler:array[1..7]of string[9]

Pascal diliyle yazılan bir programda değişken tanımlandığında bilgisayar belleğinde adı geçen değişkene o isimde bir yer ayrılır. Eğer programda dizinli bir değişken tanımlandıysa yukardaki örnekte olduğu gibi. Tanaımlanan bun dizinli değişkenin herbir elemanı için bellekte 10 Byte yer ayrılır.

İçerik

Tek Boyutlu Diziler (String Katar)

var

ad:String[5];

Begin

Ad:='Hasan';

Writeln(Ad[1]);

End.

Tek boyutlu bir dizi tanımlanırken

Dizi_adi:Array[Başlangıç_no . . Bitiş_no] of veri tipi

Örnek : Klavyeden girilen bir cümledeki a harflerinin yerine * karakteri atayan pascal programı.

uses crt;

var

ad=string[30];

i = integer;

begin

clrscr

writeln('Cümleyi Gir:');Readln(ad);

for i=1 to 30 do

if ad[1]='A' then ad[1]='*'

write (ad);

readln;

end.

İçerik

Çok Boyutlu Diziler

Örnek: Bir Öğrenci 4 ayrı dersten 3 er kez sınava girmiş olsun, her dersin sınav notunu gösterebilmek için

1. Matematik: 70,60,80

2. Fizik : 70,55,65

3. Kimya: 100,90,70

4. Biyoloji:100,85,75

Yukarıdaki bilgilerde sayılar öğrencinin derlerden aldığı 1.,2. ve 3. notlarını göstermektedir. buna göre 4 ayrı diziden söz etmek mümkündür. Dizinin isimlerini ders isimleri olarak alabiliriz ve dolayısıyla her bir dizinin elemanlarıda notlar olacaktır. Matematik dizisinin elemanları 70,60 ve 80 dir. Yukarıdaki verilenleri bir tek dizide ifade etmek mümkündür. Fakat bu defada dizi tek boyutlu değil 2 boyutlu olacaktır. Bu şekilde kuracağımız dizinin ismi notlar olsun. Bu dizide birinci boyut derslere, ikinci boyut ise notlara karşılık gelir. Birinci boyuttaki eleman sayısı 4, ikinci boyuttaki eleman sayısı ise 3 tür. Dizinin eleman sayısı her boyuttaki eleman sayılarının çarpımına eşittir. Buna göre notlar dizisinin elaman sayısı 4X3=12 dir. Bir dizi isminin sahip olduğu boyut sayısı dizi için kullanılacak indis sayısına eşittir. Yan, notlar için 2 tane indis kullanılacaktır. Birinci indis dersi,ikinci indisde notu gösterir.

Diziler için kullanılabilecek boyut sayısı artırılabilir ancak pratikte 3 veya daha fazla boyuta sahip verileri bir tablo içinde göstermek mümkün değildir.

Yukarıdaki örneği biraz daha genişleterek 3 boyutlu dizi örneği verebiliriz. notlar dizisi bir tek öğrencinin 4 ayrı dersten aldığı notları temsil etmekteydi. Şimdi tek bir öğrenci yerine bir sınıfın bütün öğrencilerinin notlarını bir dizi ile göstermeye çalışalım ve sınıftaki öğrenci sayısını 20 kabul edelim. Burada kullanacağımız dizi ismi sinif olsun.

sinif[1,2,3]-->1 nolu öğrencinin 2. dersten aldığı 3. notu temsil eder.

sinif[5,3,1]-->5 nolu öğrencinin 3.dersten aldığı 1. notu temsil eder.

İçerik

Pointerlar ve Dinamik Veri Yapıları

Dinamik veri yapılarında hafızanın boş alanlarından yararlanmak en büyük amaçtır.

İçerik

POINTERLAR

Veri olarak iki ayrı tam sayıdan meydana gelen ve belli bir bellek lokasyonunun adresini gösteren değerlerden oluşur. Pointer tipi verilerde ilk değer gösterilen lokasyonun segment adresini, ikinci değer ise offset adresini gösterir. Bu tür verilerle kullanılan bilgisayarın bütün belleğine erişmek mümkündür. Pointerlar özellikle dinamik değişkenlerin oluşturulması ve kullanılmasında kullanılır. Pointer kullanımının asıl amacı kullanılan bilgisayarın boş bellek alanlarını belirlemektir. Pointer tipi veriler bilgisayar belleğindeki çeşitli lokasyonları gösteren adreslerdir. Bu nedenle adresleme tekniğinin öğrenilmesi gerekir. Belleği adreslemek için kullanılan sayılar 2 Byte uzunluğundadır. 65535 sayısı 2 byte ile ifade edilebilecek en büyük tam sayıdır. 64 K büyüklüğündeki bir bellek 65535 byte'dan oluşur ve son byte'ın adresi 65535 dir. Bellek 64 KB lik bölümlere ayrılır. 64 KB lik her bölüme "segment" adı verilir. Her bölümün adreslemesinde kullanılan değerler ise "offset" olarak adlandırılır. Yani 2 byte'lık tam sayılar ile segment içerisindeki hücreleri göstermek için kullanılan sayılara offset denilebilir. Ancak offset ile gösterilen adres gerçek adres değeri olamaz çünkü bu adres sıfırıncı byte'ı değil segmentin sıfırıncı byte'ını başlangıç pozisyonu olarak almaktadır. Gerçek adresi bulabilmek için bu offset adresinin değerinin segmentin başlangıç pozisyonuna eklenmesi gerekir.

Gerçek adres=segment_adresi*16+offset_adresi

İçerik

Segment Kullanımı

Veri bildirim deyimleri bellek alanını program değişkenleri ve veri için ayırır ve optimal olarak kullanılır. Programdaki bütün veri ve komutlar bellekte saklanır. İşletim durumundaki program komutlarının bellek yerleşiminin yazmaç çiftinin birleşimi ile belirlenecek şekilde tasarlanmışlardır. Bunlar ikinci bir yazmaç çiftiyle tanımlanacak bir program verisinin bellek yerleşimi ve üçüncü bir yazmaç çiftiyle tanımlanan ve yığın olarak kullanılan alanlardır. Bu alanlar sırasıyla belleğin kod segmentleri, veri segmentleri ve yığın segmentleridir.

CS-Kod Segment(Code Segment)

Kod segment yazmacı program komutlarının başlangıcını tanıtır. Sonraki byte'ını işletilecek asıl bellek adresi belirlenen paragrafın kod segment yazmacına yerleştirilmesiyle ve bu değerin komut pointerina(IP) eklenmesiyle bulunur. Programın çalışması işletilebilir kod bloğunun ilk byte'ında başlanması ve orada bulduğu komutların işletiminden oluşur.

IP yazmacı : İşletilecek sonraki komutların adresini içerir. Bunun nedinide yazmaçın değişmesinin programı olumsuz yönde etkileyecek olmasıdır. Komut işaretleyicisine doğrudan erişilemez yada değiştirilemez.

İçerik

DS-Veri Segment(Data Segment)

Veri segmenti yazmacı, programın veri bölümünün başlangıcını tanıtır. Derleyici bir veri bildirimini karşılarken veri segmenti içerisinde o verinin boyutuna bağlı bir alan ayırır. Verinin belirli bir tipi varsa başlangıç değeri belleğe yerleştirilir. Aksi durumda değeri programın başlangıcından önceki içeriğinden oluşur. Kaynak dizini yazmaçı veri segmenti içerisindeki veri elemanını işaret etmek için kullanılır. Eğer bir komut veri aktarımına ihtiyaç duyuyorsa başka bir yazmaç hedef veriyi işaret ederken SI yazmacı kaynak veriyi işaret eder. Pascal da DSEG, DS yazmacının kullanımındaki değerle geri döner.

var

ad:string[15];

I:word;

Begin

ad:='KAYSERI'

for I:=1 to 1000 do

write (chr(mem[dseg:I]));

end.

İçerik

SS-Yığın Segment(Stack Segment)

Yığın segmenti yazmacı programın başlangıcını gösterir. Yığın işaretleyici yazmacı(SP) üzerinde bulunan offseti gösterir. Yığın, belleğin program tarafından silme, doldurma olarak kullanılılan bölümüdür. Geçici saklanan herhangi bir veri, kendisine ihtiyaç duyulana kadar yığında saklanır. Birçok program yığını LIFO olarak tanımlanır. Yığın alanı 64 K sınırını aşamaz ve SS yazmacı program işletimi süresince değiştirilemez.

İçerik

HEAP

Pascal bir programı icra etmeden ; belleğe yüklemeden önce veya bellekte bulduğu ilk boş alandan itibaren program için gerekli olan DATA, CODE, STACK segmentleri için yer ayırır. Belleğin geriye kanal kısmı boştur ve programcının değişik amaçları için kullanılabilir durumdadır. Bu boş alana "HEAP" adı verilir. Heap üzerindeki işlemler stack'e benzer yapılır. Heap'in başlangıç noktası "heap.ptr" adı verilen özel bir lokasyonda tutulur. Programcı tarafından heap üzerinde yapılan her işlem heap.ptr nin değişmesine sebep olur. Dinamik değişkenler tarafından temsil edilecek değerler heap üzerinde ayrılan yerlerde tututlurlar.

İçerik

Segment ve Offset Adreslerinin Okunması

Değerlerin okunmasında 2 fonksyon kullanılır.

1-)Seg(değişken): Belirtilen değişkenin segment adresini bulur.

2-)Ofs(değişken): Belirtilen değişkenin offset adresini bulur.

3-)Mem[seg:ofs]: Bellekte belirtilen segment ve offset bulunan değere erişme amacıyla veya belleğin belirtilen segment ve offsetine bir değer yazdırmak için kullanılır.

Uses crt;

var

ad:string[7];

begin

clrscr;

Ad:='HASAN'

writeln('Ad degişkeninin segment adresi..:',seg(ad));

writeln('Ad değişkeninin offset adresi..:',ofs(ad));

writeln('Ad değişkeninin uzunlugu:!,mem[seg(ad):ofs(ad)];

readkey;

end.

İçerik

Bellek Konum Göstericisi(Pointer)

Herhangi bir tipteki değişkenin (dinamik değişken) bellekte konumlandığı adresi tutar. yani bellek konum göstericisi bir değişken olup içinde bir başka değişken adresini tutar. Değişkenler bellekte kullanımları yönünden ikiye ayrılırlar.

Statik Değişkenler

Çoğunlukla kullanılan türdür. Program geliştirme aşamasında değişken bildirim bloğunda tanımlanan değişkenlerdir. Bu değişkenlerin bellek konumu ve gerekli bellek alanı programın derlenmesi aşamasında belli olur. Tanımlanan statik değişkenler DATA SEGMENT'de oluşturulurlar ve program işleyişi sürdüğü müddetçe bellekte yer işgal etmeye devam ederler. Bu değişkenler için gerekli bellek alanı programın derlenmesi esnasında belli olur. Statik bir değişkenin veri tipi,büyüklüğü değişken bildirim bölümünde tanımlanır ve hafızada büyüklüğü kadar yer kaplar. Statik değişken ile, statik dizi değişkeni hariçtek bir değere işaret edebilir. Statik değişkenlerin ifade etmiş olduğu değerler değşken ismiyle sağlanır. Dizinli değişkenlerde statik değişkenlerdir. Dizinli değişkenler birden çok veriye işaret edebilir. Dizinli değişkenlerin eleman sayıları programın çalışması süresince değiştirilemez ve bir dizinli değişken aynı tipte veriler tutulabilir. Bu özelliklerinden dolayı dizinli değişkenler aynı tipte veriler ve eleman sayısı belli olan dizi işlemlerinde kullanılabilirler. Dizinli değişkenlerin eleman sayısısını azaltmak yani, kullanılmayan elemanların bellekte yeer işgal etmesini engellemek mümkün değildir. Sonuç Olarak tanımlanan her statik değişken program çalıştığı sürece hafızada yer işgal etmeye devam eder. İşi biten statik değişken hafızadan atılmaz.

Dinamik Değişkenler

Programın işletimi sırasında "heap" üzerinde gerekli hacimde yer ayrılmasıyla oluşturulurlar. Ayrılan bu bellek bellek konum göstericisi adı verilen önceden tanımlanmış statik bir değişken aracılığı ile erişilebilir. Diziler, kümeler ve kayıtlar statik veri yapıları olarak adlandırılırlar. Bir statik değişken bir programda veri bildirim bölümünde oluşturulur. Bçimi ve büyüklüğü önceden tanımlanır. Her statik değişken için ana bellekte ayrılan yer değişkenin yaşam süresi boyunca tutulur. Statik değişkenin yapısı programın çalışması süresince hiçbir zaman değişmez. Örneğin bir dizi 10 elemanlı tanımlandıysa 10 elemanlı kalır. Bir kayıtta 3 alan varsa alan sayısı değişmez. Pek çok uygulamada etkin olmalarına karşın statik değişkenlerin bazı sakıncaları vardır. Örneğin bir dizi kullanılacaksa o dizinin uzunluğunun ne olacağına önceden karar vermek gerekir. Dizi uzunluğu gerektiğinden fazla olursa bellek israfına yol açar. Dizi elemanları sıralı biçimde isteniyorsa uygun bir sıralama algoritması uygulanmalıdır. Diziden bir eleman çıkarmak yada diziye bir eleman eklemek için yapılması gereken bir işlem varsa bunu yapmak zor olur. PAscal'da bu sorunların çözümü için biçim ve büyüklükleri değişebilen dinamik veri yapıları kullanılır. Bir dinamik değişken bir programın çalıştırılması sırasında oluşturulur ve yok edilebilir. Dinamik değişkenler, statik değişkenlerden farklı olarak programcı tarafından seçilen isimlerle değişkenin göstericlerle(pointer) dolaylı yoldan gösterilir. Aslında bir gösterici değişken gösterdiği dinamik değişkenin bellekte yerini içerir. Dinamik değişkenlere ve göstericilere, bağlı veri yapıları kurmakta ihtiyaç duyulur. Bir bağlı veri yapısının her elemanı diğer bir elemana bağlanır. Program 64 K dan fazla veri saklama ve işlemeye ihtiyaç duyarsa program derleme aşamasında ne kadar hacimli değişkene