Mustafa Kemal Üniversitesi

Transkript

Algoritma Geliştirme ve Veri Yapıları – 3
Veri Yapıları
Veri Yapıları
• Veri yapısı, bilginin anlamlı sırada bellekte veya
disk, çubuk bellek gibi saklama birimlerinde
tutulması veya saklanması şeklini gösterir.
• Bilgisayar sistemleri ikili taban üzerine kurulmuş
olup hemen her şey 1 ve 0’ların anlamlı sırada
dizilerek birbirinden farklı kodlar oluşturulmasına
dayanır.
• Veri yapısı verilerin saklanış biçimiyle ilgilenirken,
veri modeli ise veriler arasındaki ilişki ve
bağlantılar konusu ile ilgilenir.
Veri Yapıları
1) Veri Yapısı
•
•
Ham haliyle 01000001 şeklinde bit dizisinde oluşan
verilerin anlamlı hale gelmesi veya bilgi olması için onun
formatının da bilinmesi gerekir. Örneğin verilen
01000001 bit dizisi ASCII kümeye göre A harfine, ikili
sayı sistemine göre 65 sayısına karşılık düşer.
Veri yapıları, sayısal sistemlerin iç yapısında bit dizisi
şeklinde bulunan verilerin anlamlı hale getirilmesi için
kullanılan bir biçimleme-kalıplama yöntemdir, yani
verinin tutulacağı yerin şeklidir. Örneğin 16-bit biraraya
getirilip tamsayı, 8-bit bir araya getirilip karakter veri
türü oluşturulur.
Veri Yapıları
1) Veri Yapısı
•
Her programlama dili tarafından desteklenen temel veri
türleri;
o
o
o
o
•
•
Tamsayı (21, 5678, vs.)
Karakter (A, B, ~, @, vs.)
Gerçel Sayı (3.5, 2.68, 3.6*103 vs.)
Sözce/Sözcük (ali, elma vs.)
Veri yapıları; temel veri yapıları ve tanımlamalı veri yapıları
olmak üzere ikiye ayrılabilir.
Temel veri yapıları, daha çok programlama dilleri tarafından
doğrudan değişken veya sabit bildirimi yapılarak
kullanılırken, tanımlamalı veri yapıları kendisinden önceki
tanımlamalı veya temel veri yapıları üzerine kurulurlar.
Veri Yapıları
2) Temel Veri Yapıları
•
•
Tüm programlama dilleri genel olarak karakter, tamsayı,
gerçel sayı, sözce/sözcük ve dizi için temel veri yapılarını
destekler, bazıları da karmaşık sayı, mantıksal değer
tutulması gibi veri yapılarını da desteklemektedir.
6210 sayısı bilgisayar belleğinde;
o
o
o
Sayının ikili tabandaki karşılığına göre 0011 1110
ASCII karakter kümesine göre 0011 0110 0011 0010
BCD kodlamaya göre 0110 0010
Veri Yapıları
2-1. Karakter
•
•
•
Karakter, en temel veri yapılarından birisi olup tek tek
karakterlerin veya art arda gelerek sözcüklerin,
cümlelerin tutulduğu bir yapıdır.
Kodlama işlemi bir karakter tablosuna göre yapılır, tablo
değiştirildiğinde karakterlere karşı düşen kodlar
değişeceğinden ham verinin içerdiği bilgi farklı görülür.
Bilgisayar uygulamasında en yaygın kullanılan karakter
tabloları ASCII’dir; Unikod kodlama standardı da
yaygınlaşmaktadır.
Veri Yapıları
ASCII
•
•
•
•
ASCII tabloda her bir karakter 7 bit olup 128 farklı
karakterden oluşmaktadır. Genişletilmiş ASCII tabloda ise her
bir karakter 8 bit olup tabloda 256 karakter bulunmaktadır.
Bilgisayar uygulamalarında daha çok genişletilmiş ASCII kod
tablosu kullanılmaktadır.
Bu kod tablosu kullanan her yapı karakter başına 1 byte (8
bit) yer işgal eder. Örneğin yalın metin dosyalarının(*.txt)
boyutu yaklaşık olarak içerdiği karakter sayısı kadardır.
Tablodaki ilk 32 karakter (yazdırılamayan) kontrol amaçlı
olarak kullanılır ve kontrol karakteri olarak adlandırılır.
Dosyalama işlemleri, veri aktarımı vs gibi uygulamalarda
belirli anlamlara sahiptirler.
Veri Yapıları
Unikod (Unicode)
•
•
•
Unikod, metin tabanlı verilerin sayısal ortamda
gösterilmesi ve bellekte tutulması için evrensel bir
kodlama şeklidir. Ortaya çıkışının ana temeli Dünya
üzerinde konuşulan/yazılan ulusal dillerden bağımsız
ortak bir kodlama sisteminin gereksinimidir.
Unikod kodlama sisteminde herbir karakter bellekte 16
bit yer işgal eder(216=65536 farklı karakter).
Unikod kodlama sistemi kod blokları şeklinde
düzenlenmiştir.
Örneğin;
Genişletilmiş
Latin-A,
“Mathematical Alphanumeric Symbols”, vb.
Veri Yapıları
2-2. Tamsayılar
•
•
Bir tamsayı, bellekte en yalın haliyle ikili tabandaki doğal
karşılığı ile saklanır.
Tamsayı formatları;
o
o
o
o
Doğal ikili kod
1’e Tümleyen
2’ye Tümleyen
BCD Kodlamalı
Veri Yapıları
Doğal İkili Kod
•
•
Sayı doğrudan ikili tabandaki karşılığı ile saklanır.
Sayının mutlak değeri “S”
S=bn-12n-1+bn-22n-2+bn-32n-3+…..+b222+b121+b020
S10=(bn-1bn-2bn-3…b2b1b0)2
•
Bit dizisinin en solundaki bit en anlamlı, en sağındaki bit
en anlamsız olarak adlandırılır.
10’luk tabandaki sayı 2 ye bölünerek ikili taban karşılığı
elde edilir.
•
Veri Yapıları
1’e Tümleyen
•
Bu yöntemde sayının doğal ikili tabandaki karşılığının 1’e
tümlenmişi kullanılır. 1’e tümleme bit dizisi içerisindeki
1’lerin 0, 0’ların 1 yapılması ile elde edilir.
2’ye Tümleyen
•
•
Bu yöntemde sayının doğal ikili tabandaki karşılığının
2’ye tümlenmişi kullanılır. 2’e tümleme bit dizisi
içerisindeki 1’lerin 0, 0’ların 1 yapılıp sonuca 1
eklenmesi ile elde edilir.
Aynı zamanda 1’e tümlenmiş olan ikili diziye 1 eklenmiş
halidir.
Veri Yapıları
BCD Kodlama
•
•
BCD kodlama, [0,9] arasındaki rakamların 4 bitlik
kodlaması kullanılarak gerçekleştirilir.
Rakam
BCD Kodu
Rakam
BCD Kodu
0
0000
5
0101
1
0001
6
0110
2
0010
7
0111
3
0011
8
1000
4
0100
9
1001
123 sayısı 1=0001; 2=0010; 3=0011  0001 0010 0011
Veri Yapıları
İşaretsiz Tamsayı (Unsigned Integer)
•
•
İşaretsiz tam sayılar, pozitif tamsayılar anlamına gelir.
Hiçbir zaman eksi olamayacağı için sayının işaret
bilgisinin tutulmasına gerek yoktur.
n bitlik işaretsiz bir tamsayı 0 ile 2n-1 arasında bir değere
sahiptir.
Veri Yapıları
İşaretli Tamsayı (Signed Integer)
•
•
•
•
İşaretli tamsayı hem artı hem de eksi sayıların olabileceği
anlamına gelir. Bu nedenle sayı içerisinde işaret bilgisi de
tutulmalıdır.
Genel olarak, 1 tane bit işaret biti olarak değerlendirilir. Bu
bit 1 iken sayı eksi bölgede, 0 iken sayı artı bölgede
anlamındadır.
10 bitlik bir işaretli tamsayıda, 9 bit sayının mutlak değerini,
1 bit ise sayının işaretini temsil eder.
Tamsayıları işaretli göstermek için
o
o
Doğal ikili kodun en soluna işaret biti eklenmesi
2’ye tümleyen şekliyle gösterilmesi
Veri Yapıları
İşaretli Tamsayı - Örnek
•
8 bitlik -1 ve +1 sayısının hem doğal hem de 2’ye
tümleme yöntemi ile gösterilmesi
1 sayısı => 0000 0001
Doğal ikili kod ile -1 için; 1000 0001
2’ye tümleme ile -1 için; 1111 1111
Veri Yapıları
Tamsayının bit Uzunluğu ve Bölgesi
•
Uzunluklar konusunda belirli standartlar vardır. Sayının
bit uzunluğu 1 bit olsa dahi çalışılan tamsayı türü 32
bitlik ise sayı bu alanda tutulmak zorundadır.
Tamsayı Türü
İşaretsiz
8 bitlik
[0, 255]
[-128, +127]
16 bitlik
[0, 65 535]
[-32 768, +32 767]
32 bitlik
[0, 4 294 967 295]
[-2 147 483 648, +2 147 483 647]
64 bitlik
[0, 264-1]
[-263, +263-1]
128 bitlik
[0, 2128-1]
[-2127, +2127-1]
İşaretli
Veri Yapıları
İşaretli Tamsayı - Örnek
•
-3910 sayısının 16 bitlik olarak doğal ve 2’ye tümleme
yöntemiyle gösterimi
39=> 10 0111 ==(16bit)=>0000 0000 0010 0111
Doğal => 1000 0000 0010 0111
2’ye tümleme ile;
0000 0000 0010 0111 =(tümleme ile)=>1111 1111 1101 1001
Doğal ikili kod ile => 1000 0000 0010 0111
2’ye tümleme ile => 1111 1111 1101 1001
Veri Yapıları
2-3. Gerçel Sayı
•
•
Tam kısma ek olarak kesri olan sayılardır, gerçel sayı
yapısı hem kesri olan gerçel sayıların gösterilmesinde
hem de tamsayı veri yapısıyla gösterilemeyecek kadar
çok büyük veya çok küçük sayıların gösterilmesinde
kullanılır.
Sayısal ortamlarda kesirli sayıların gösterilmesinde
bilgisayar uygulamalarında en fazla kayan noktalı
gösterim kullanılır.
o
o
Kayan Noktalı (Kesrin yeri değişken)
Sabit Noktalı (Kesrin yeri sabit)
Veri Yapıları
Kayan Noktalı Sayı Formatı & IEEE 754
•
•
Kayan noktalı sayıların bit düzeyindeki veri yapısında, bit
dizisindeki bitlerin bir kısmı üs, bir kısmı çarpan ve bir tane
de işaret biti kullanılır.
IEEE 754 standardına göre 32 bitlik bir kayan noktalı sayının
bit haritası şöyledir; 23’ü çarpan, 8’i üs ve 1 bit de işaret.
Veri Yapıları
•
Sayı genel olarak şu şekilde gösterilir (Ç:Çarpan,
T:Taban, Ü:Üs)
Sayı = ± Ç x T ±Ü
•
T, taban bilgisi olup tüm sayılar için aynı olacağından
saklanmasına gerek yoktur. Bu nedenle Ç,Ü ve işaret
bitinin saklanması yeterlidir.
Veri Yapıları
Veri Yapıları
*Örnek
•
•
•
•
•
•
3,14 şeklinde verilen pi sayısının 32-bitlik IEEE 754 formatına
göre bit haritasını çıkartınız.
3,14=(-1)i*(1+k)*2üs-bias
i: sayının işareti
(1+k): Çarpan (1 ≤ Çarpan≤2 aralığında olmalıdır. K=0,…
şeklinde bir ondalık sayı)
Bias: bit haritasında verilen üs sayısından çıkarılan bir sabit
olup 32 bitlik kayan noktalı sayı için değeri 127 (tablodan)
Sayı “+” olduğu için i=0;
Veri Yapıları
*Örnek
•
(-1)0*(1+k)*2n=3,14 => n=1 için k=0,57’dir.
•
üs-bias=n=1  bias=127(tablodan), üs=1+127=128 olur.
i
üs
k
0
128
0,57
•
Veri Yapıları
*Örnek
•
•
•
•
•
•
•
•
i=(0)10=(0)2
üs=(128)10=(1000 0000)2
k=(0,57)10=(???)2
0.57*2=1,14  1’den büyük q-1=1
0.14*2=0,28  1’den küçük q-2=0
…
0.32*2=0,64  1’den küçük q-22=0
0.64*2=1,28  1’den büyük q-23=1
0.28*2=0,56  1’den büyük q-24=0
Veri Yapıları
*Örnek
•
•
•
k=(0,57)10≈(0,10010001111010111000010)2
i
üs
k
0
1000 0000
100 1000 1111 0101 1100 0010
Tam karşılığı bulunamadığı için 24. bitte kesilmiştir.
Sonuç gerçel sayı IEEE 754’e formatında tutulduğunda bir
miktar hata payı olur.
Veri Yapıları
2-4. Sözce ve Sözcükler
•
•
•
Bir yazının/metnin tamamını, herhangi bir cümlesini,
sözcüğünü veya hecesini bellek üzerinde tutmak için
sözce(string) veri yapısı kullanılır.
Sözce, aslında karakterlerin art arda geldiği bir karakter
dizisidir. Sıradan bir karakter dizisinden farkı, sözcenin
kaç elemanlı olduğunun bilinmesi veya sözce sonu
karakteri kullanılmasıdır.
C dilinde sonlandırma karakteri ‘\0’ verisidir(NULL).
Veri Yapıları
2-4. Sözce ve Sözcükler
•
•
•
•
Bu yapıda iki tip yaklaşım mevcuttur. Birisi oluşturulacak olan dizi
yapısının karakter sayısını tutması, diğeri ise sonlandırma karakteri
kullanılması.
Karakter sayısını kullanan yaklaşımda eleman sayısı dizinin en
başında verilmiştir. Ve diziye girilecek karakter sayısı bu rakam ile
sınırlıdır.
Sonlandırma karakteri yaklaşımında ise, oluşturulacak olan
karakter dizisinin boyutu sonlandırma karakterinin bulunduğu yer
ile sınırlıdır. Bu da tüm belleğin kullanılmasına izin verir niteliktedir.
Sonlandırma karakteri yaklaşımının dezavantajı elemanların sayımı
gibi işlemlerde ortaya çıkar. Sonlandırma elemanına kadar olan
karakterlerin sayılması gereklidir. Karakter sayısının tutulması
yönteminde ise dizinin ilk elemanına bakmak yeterlidir.
Veri Yapıları
Veri Yapıları
2-5. Dizi/Matris
•
•
•
Dizi veri yapısında, kümeye ait olan veriler bellekte art arda
tutulur. Dolayısıyla dizinin başlangıç adresi veya adı
bilindiğinde herhangi bir elemana kolayca erişilebilir.
Dizi veri yapısı, doğrudan programlama dilinin imkanı
dahilinde dizi bildirimleri yapılarak sağlanır.
Temel veri yapısına dayanan birkaç dizi bildirimi;
Veri Yapıları
2-5. Dizi/Matris
struct tarih{
struct kayit{
char ad[10];
char soyad[15];
char adres[50];
char sehir[10];
char bolum[8];
int boy;
float kilo;
short int gun;
short int ay;
int yil;
}
}
Veri Yapıları
2-5. Dizi/Matris
struct tarih dogumgunleri[2000];
struct kayit ogrenciler[10];
• Bu dizi bildirimlerinin geçerli olabilmesi için daha önce
struct tarih ve struct kayit adlı toplulukların tanımlı
olması gerekir.
• Bu durumda her bir tarih veri yapısı 6; kayıt veri yapısı
da 99 sekizli(byte) boyutundadır. Buna göre dogumgunu
dizisi bellekte 2000*6, ogrenciler dizisi de 10*99 bytelık
yer işgal eder(Veri türü tablosundan).
Veri Yapıları
3) Tanımlamalı Veri Yapıları
•
•
Tanımlamalı veri yapısı, temel ya da daha önceden
tanımlanmış veri yapılarının kullanılıp yeni veri yapıları
oluşturulmasıdır.
Yeni veri yapısı tanımlamak gereksinime göre iki şekilde
yapılabilir;
o
o
•
Topluluk Oluşturma
Ortaklık Oluşturma
Her birinin kullanım amacı farklı olup uygulamaya göre
bir tanesi veya hepsi bir arada kullanılabilir.(En çok
kullanılanı topluluk oluşturmadır)
Veri Yapıları
3-1. Topluluk Oluşturma
•
•
•
Topluluk birden çok veri yapısının bir araya getirilip
yeni bir veri yapısı, bir aile ortaya çıkarmaktır.
Bağlantılı liste, ağaç ve özel amaçlı veri modelleri
böylesi yeni veri yapılarına gereksinim duyar, zaman,
tarih gibi birden çok değişkenin olduğu veri yapıları
da topluluk bildirimiyle yapılabilir.
Topluluk tanımlanması C dilinde struct deyimiyle
yapılır.
Veri Yapıları
Veri Yapıları
3-1. Topluluk Oluşturma
struct kimlik{
char ad[15];
char soyad[20];
int yas;
char adres[50];
}
Veri Yapıları
3-2. Ortaklık Oluşturma
•
•
•
•
Ortaklık, birden çok değişkenin aynı bellek alanını
kullanmasını sağlayan bir veri yapısı tanımlamasıdır.
Böylece, bellek alanı kısıtlı uygulamalarda bazı
değişkenlerin ortaklaşa yer kullanması sağlanmış olur.
Ancak, birine atama yapıldığında diğerinin değişeceği
unutulmamalıdır.
Ortaklık tanımlanması C dilinde union deyimiyle yapılır.
Ortaklıkta en fazla yeri işgal eden veri yapısı hangisi ise,
ortaklık içerisindeki tüm değişkenler orayı paylaşır.
Veri Yapıları
3-2. Ortaklık Oluşturma
union paylas{
int i;
float f;
char kr;
}

Mustafa Kemal Üniversitesi

Transkript

Benzer belgeler

Mustafa Kemal Paşa`nın Chicago Tribune Muhabirine Verdiği Mülakat

üniversite öğrencileri - Adana Ressamlar Derneği

İnkılap Tarihi ve Atatürkçülük A

Issue Content - Türkiye Klinikleri

Bu PDF dosyasını indir - Mustafa Kemal Üniversitesi Tıp Dergisi

Etrafında gördüğün veya hissettiğin olağandışı bir