BİL204U-ALGORİTMALAR
Ünite 2: Veri Yapıları
Giriş
Veri kavramı olgu, kavram veya komutların, iletişim, yorum ve işlem için elverişli biçimli gösterimi şeklinde tanımlanmıştır. Günlük yaşamda pek çok alandan veriler toplar, çevremizdeki bireyler ve sistemlere veriler göndeririz. Bilgisayar sistemlerinin kalbinde de veriler yer almaktadır. Bilgisayarlar bu verileri yorumlar, birbirleri arasında transfer eder ve istediğimiz çıktıları üretir. Bu çıktı bazı durumlarda bir fotoğrafın gösterimi, bazı durumlarda bir e-Postanın gönderilmesi, bazen de banka hesapları arasında transferi ifade edebilir. Sonuç olarak verilerin bilgisayar sistemleri üzerinde temsili ve işlenmesi oldukça önemli bir iştir. Bu işleri kavramsallaştırmak, kolaylaştırmak ve bu süreçlerin etkisini arttırmak için veri yapıları oluşturulmuştur.
Veri Yapısı
Veri yapıları, programlarda bilgiyi işlemek için oluşturulmuş yapı taşlarıdır. Veri yapıları bellek ortamlarında bilginin saklanması, geri çağrılması ve işlenmesi için bir organizasyon sunar. Farklı amaçlarla tanımlanmış pek çok veri yapısı bulunmaktadır. Örneğin integer gibi veri yapıları tek bir sayısal değerin tutulması için kullanılabilirken ağaç (tree) gibi veri yapıları verilerin hiyerarşik bir biçimde saklanmasını sağlayabilir.
Veri Yapılarının Amaçları
Veri yapılarının amacı bilgisayar sistemi ile programcının zihni arasında bir köprü kurmaktır. Böylece programcı ve bilgisayar sistemi kolayca anlaşabilmektedir. Programcılar amaçlarına ulaştıracak algoritmalarda kullanmak için bir veri yapısını kullanmayı seçebilir ya da amaçlarına özgü bir veri yapısı oluşturabilirler.
İşletim sistemleri ve donanımlar yürüttükleri işlemleri kontrol etmek için kuyruk (queue) veri yapılarını sıklıkla kullanmaktadır. Diskler gibi donanımlar kendilerine gelen istekleri aygıt kuyruğu (device queue) adlı yapılarda tutmaktadır. Kelime işlemciler ya da tasarım yazılımları geri alma ve tekrarlama işlevleri için yığın (stack) veri yapılarını kullanır. Benzer şekilde internet tarayıcılar da ziyaret edilen sitelerin adres geçmişini yığın veri yapılarında saklamaktadır. Diskler üzerindeki dosyaların üst verilerini tutan dosya sistemleri ise (ör.: NTFS) hiyerarşik veri tutma olanağı sunan ağaç veri yapılarını (tree) kullanır.
Her veri yapısının kendine özgü yeterlikleri, avantajları ve sınırlılıkları vardır. Programcılar önlerindeki görevin karakteristikleri ve veri yapılarının özelliklerini dikkate alarak doğru veri yapısını seçmeye çalışır.
Veri yapıları üzerinde sıklıkla gerçekleştirilen işlemler aşağıda listelenmiştir. Programcının veri yapısı tercihi genellikle bu işlemlerin hangilerini ne sıklıkta kullanacağına bağlı olarak değişir:
1. Gezinme (traversing): Veri yapısı üzerindeki nesnelerin çıktı olarak üretilmesidir. 2. Arama (searching): Veri yapısı üzerinde bir değerin aranmasıdır.
3. Ekleme (insertion): Veri yapısında istenilen noktaya element eklenmesidir. 4. Silme (deletion): Veri yapısında istenilen elementin silinmesidir. 5. Sıralama (sorting): Veri yapısı üzerindeki elementlerin belirlenen kritere göre sıralanmasıdır. 6. Birleştirme (merging): Veri yapısı üzerindeki elementlerin birleştirilmesidir.
Veri yapıları özünde soyut kavramlardır. Bilgisayar sistemleri üzerinde veri yapılarının uygulayıcıları programlama dilleridir. Programlama dillerindeki mekanizmalar yoluyla bu soyut yapılar bilgisayar sisteminin belleğinde oluşturulabilir ve düzenlenebilir. Bu nedenle veri yapılarının tanımlanmaları ve düzenlenmeleri için programlama dillerine özgü tekniklerin öğrenilmesi gerekir.
Veri Yapılarının Sınıflandırılması
Veri yapıları pek çok boyutta sınıflanabilir. Bu sınıflamalardan en çok tercih edilenlerden biri basit ve karmaşık (türetilmiş) veri yapılarıdır. Basit veri yapıları bilgisayar işlemcileri tarafından doğrudan manipüle edilebilen, tek bir değer tutabilen ve programlama dillerinde yerleşik olarak sunulan veri yapılarıdır. Bu nedenle bu veri yapılarına veri türleri adı verilmektedir. Bunlar mantıksal (boolean), sayısal (float ve integer), karakter (char) ve adres göstergesi (pointer) veri türleridir. Karmaşık veri yapıları ise basit veri yapılarını kullanarak farklı amaçlarla türetilen ve birden fazla veriyi tutabilen veri yapılarıdır. Karmaşık veri yapıları, veriler arası ilişkilerin kurulma biçimlerine göre doğrusal ve doğrusal olmayan veri yapılarına ayrılır. Doğrusal veri yapılarında veriler arasında bir ardışıklık söz konusudur. Bir element kendinden önceki ve sonraki elementle bağlantılıdır. Diziler (array), yığınlar (stack), kuyruklar (queue) ve bağlı listeler (linked list) doğrusal veri yapılarıdır. Doğrusal olmayan veri yapılarında ise elementler arası bağlantılar asimetriktir. Ayrıca bağlantı sayıları farklılaşabilmektedir. Ağaçlar (tree) ve çizgeler (graph) doğrusal olmayan veri yapılarıdır.
Basit veri türleri yalnızca bir türde ve bir adet veri saklayabilir. Buna karşın karmaşık veri türlerinde birden fazla türde karmaşık ya da basit veri saklanabilir.
Basit Veri Türleri
Basit ya da ilkel veri türleri, tüm veri yapılarının oluşturulduğu temel bir veri türü kümesidir. Basit veri türleri, bilgisayar işlemcileri tarafından yönetilebilen sınırlı bir veri temsili kümesini ifade eder. Bu nedenle işlemciler için derlenmiş tüm programlar bu temel veri türlerini kullanır. Basit veri türleri programlama dilleri tarafından yerleşik olarak sağlanırlar. Bu veri türleri için programcıların herhangi bir özellik tanımlamasına gerek yoktur. integer, float, boolean gibi veri türleri basit veri türleri arasında sayılabilir.
Boolean
Boolean veri türü mantıksal doğru (true) ve yanlış (false) değerlerini tutmak için kullanılır.
Sayılar
Sayısal veriler tam sayılar ve kayar noktalı sayılar (ondalıklı) olmak üzere ele alınabilir. Programlama dillerinde belleğin optimum kullanımı için farklı türde tam sayı (ör.: 5) ve kayar noktalı (ör.: 5,2) değişken türleri tanımlanmış olabilir. C# programlama dilinde tam sayıları tutmak üzere Byte ve Integer türleri tanımlanmıştır. Programlama dilinden bağımsız olarak veri türleri boyutunda tam sayıların tutulması için Integer sınıfı kullanılır. Ondalıklı sayılar içinse Float sınıfı kullanılır. Float veri türünde de pozitif ya da negatif tam sayılar ya da ondalıklı sayılar tutulabilir.
Karakter (Char)
Karakter veri türü tek bir alfanümerik karakterin tutulması için kullanılır. Karakter veri türünde büyük ya da küçük harfler, rakamlar ve özel işaretler tutulabilir. Tutulabilecek değerler arasında a, A ya da 9 sayılabilir. Fakat 12 değeri iki karakter içerdiğinden tutulamaz. Karakter veri türünde saklanabilecek karakter sayısı kullanılan bit sayısı ile orantılıdır.
Gösterge (Pointer)
Gösterge veri türü, bellekte tutulan başka bir değişkenin fiziksel adresini saklamak amacıyla kullanılır. Bu bellek adresinde tutulan değere ulaşma işlemine göstergeyi çözümleme (dereferencing) adı verilir. Kodlarda gösterge kullanımı metinleri gezinme, başvuru çizelgeleri (lookup table), kontrol tabloları ve ağaç yapıları üzerindeki döngüsel işlemlerin performansını arttırır.
Karmaşık Veri Yapıları
Karmaşık veri yapıları programlama dilleri tarafından yerleşik olarak sunulmazlar. Bu veri yapılarının yapı taşları basit veri yapılarıdır. Karmaşık veri yapıları doğrusal (linear) ve doğrusal olmayan (non-linear) veri yapıları altında sınıflandırılır. Doğrusal veri yapılarında elementler ardışık olarak yapılandırılırken, doğrusal olmayan veri yapılarında elementler arasında ardışıklık söz konusu değildir. Doğrusal olmayan veri yapılarında hiyerarşiler, düğümler arası çok sayıda bağlantılar ve ağırlıklandırılmış bağlantılar kurgulanabilir. Doğrusal veri yapılarındaki veriler bir döngü ile gezilebilirken (traverse), doğrusal olmayan veri yapılarında alt açılımları gezinmek için yeni döngülerin tanımlaması gerekebilir.
Doğrusal Karmaşık Veri Yapıları
Doğrusal veri yapılarında elementler sıralı olarak yerleştirilmiştir. Her bir element kendinden önceki ve kendinden sonraki element arasında yer alır. Diziler (array), yığınlar (stack), kuyruklar (queue) ve bağlı listeler (linked list) doğrusal veri yapılarıdır. Diziler bitişik bellek alanlarına yerleştirilmiş aynı tipteki verilerin saklandığı veri yapılarıdır. Dizilerde float, int, boolean gibi basit veri türlerinde değerler saklanabilmektedir. Dizilerde saklanan
değerlere element adı verilir. Çoğu programlama dilinde dizilerin ilk elementinin indisi sıfırdır fakat bu bir zorunluluk değildir. Diziler aynı türdeki birden fazla değerin saklanması için oldukça elverişli veri yapılarıdır. Dizilerde veri arama ve verilerin sıralanması diğer veri yapılarına göre daha kolaydır.
Bağlı listeler, birbirine bağlı düğüm serilerinden oluşan doğrusal veri yapılarıdır. Bu düğümler bilgisayar belleğinde rastgele yerlerde saçılmış durumdadır. Her bir düğüm, veri ve bağlantı adresi (gösterge) bölümlerinden oluşur. Bağlı listelerin dizilere oranla en önemli avantajı element sayılarını dinamik olarak arttırılabilmesidir. Diziler tanımlandıkları boyutun ötesinde element tutamazken dinamik bellek kullanabilme yeteneği sayesinde bağlı listelere kolaylıkla element eklenebilmektedir. Bağlı listelerde bu işlem bellek adreslerinin değiştirilmesi yoluyla kolaylıkla yapılabilmektedir. Çalışma zamanında dizilerin boyutunun artırılması olanaksızken bağlı listelere ekleme yapılabilmektedir. Bu sayede programcının liste boyutu belirlemesine gerek kalmaz.
Bağlı listelerdeki elementlere indis numarası yoluyla rastgele erişim olanağı yoktur. Listedeki dördüncü elemente ulaşabilmek için ilk üç elemente erişilmesi gerekmektedir. Ayrıca bağlı listelerde dizilere oranla daha fazla veri kullanılmaktadır.
Yığınlar Son Giren İlk Çıkar (LIFO-Last In First Out) prensibinde çalışan doğrusal veri yapılarıdır. Bu veri yapılarının en tepesine veri eklenebilir ve en tepedeki veri çıkarılabilir. Bu yapılar bir kitap yığınına benzetilebilir. Yığının üzerine bir kitap eklenebilir ya da en üstteki kitap yığından çıkarılabilir. Bu veri yapılarında en tepedeki elementi işaret den tek bir gösterge tutulur. Ekleme ve çıkarma işlemlerinde bu gösterge güncellenir.
Kuyruklar bir uçlarından ekleme, diğer uçlarından silme işlemleri yapılabilen doğrusal veri yapılarıdır. Ekleme işlemi yapılan sona arka, silme işlemi yapılan sona ise ön adı verilir. Kuyruklar gerçek hayattaki bilet kuyruklarına benzetilebilir. En önden biletini alan elemanlar kuyruktan çıkarken bilet almak isteyenler kuyruğun sonuna eklenirler. Yığınların aksine kuyruklar İlk Giren İlk Çıkar (FIFO – First In First Out) prensibinde çalışır. Kuyruklar da yığınlar gibi pek çok alanda kullanım bulmaktadır.
Doğrusal Olmayan Karmaşık Veri Yapıları
Doğrusal veri yapılarında bir element kendinden önceki ve kendinden sonraki elementler arasındadır. Bu element, yalnızca çevresindeki iki elementle bağlantılıdır. Doğrusal olmayan veri yapılarında ise elementler arası bağlantı sayısı birden fazladır. Doğrusal olmayan veri yapılarında elementler rastgele yerleştirilmiştir.
Ağaç (tree) veri yapısı hiyerarşik verilerin tutulması için kullanılır. Ağaç veri yapıları düğüm adı verilen varlıkların ya da nesnelerin bir koleksiyonudur. Bu düğümler bir hiyerarşi içinde sunulur. Ağaç veri yapılarında düğümler sıralı değil, hiyerarşik bir şekilde sunulur. Bu nedenle
ağaçlarda katmanlardan bahsedilir. Her bir düğüm verinin arasında tanımlı (A, B) kenarı iki yönlü gezilebilir. Yönlü yanında kendisinin çocukları olan düğümlere bağlantılar çizgelerde içerir. yalnızca (terminal node) doğru yapılabilir. Karmaşık bir veri yapısı olan ağaçların anlaşılabilmesi için gerekli bazı terimler; Bilgisayar gösteriminde, veri organizasyonunda ve hesaplamaların • Kök (root): Ağaç yapısının en üstündeki düğüme akışını göstermede ku kök düğüm denir. Her ağaç yapısında tek bir kök internet sitesi üzerindeki gezinimi yönlü çizge kullanılarak düğümü ve kök düğümünden diğer düğümlere tek gösterilebilir/modellenebilir. bir yol bulunur. internet sitesinin sayfaları, kenarlarsa sayfalar arasındaki • Kenar (edge): Ağaç yapılarında düğümler bağlantılardır. Bu modelleme üzerinde ku kenarlar ile birbirine bağlanır. düğümleri sıklıkla ziyaret ettikleri, A sayfasına gelmek için • Yol (path): Birbirine kenarlar ile bağlanmış hangi düğüm serilerine yol adı verilir. Her ağaç bağlantıların gereksiz olduğu gibi incelemeler yapılabilir. yapısında tek bir kök ve ağaç üzerindeki herhangi bir düğüme tek bir yol tanımlıdır. • Ebeveyn (parent): Kök düğümü dışında, kendisinden sonraki düğümlere doğru kenarları olan düğümler ebeveyndir. • Çocuk (child): Bir ebeveyne kenarlarla bağlanan düğümlere çocuk denir. • Kardeş (sibling): Aynı ebeveynden gelen düğümler kardeş düğümlerdir. • Yaprak (leaf): Kendisinden sonra çocuk düğümü gelmeyen uç düğümlere yaprak düğüm adı verilir. Bir ağaç yapısında sayısız yaprak düğüm olabilir. Yaprak düğümler bulundukları ağaç yapısındaki en alt katmandaki düğümlerdir. • Alt ağaç (subtree): Bir düğümün çocuklarına alt ağaç denir. • Katman (level): Kök düğümden başlayarak aşağı doğru açılan düğüm düzeylerine katman denir. • Derinlik (depth): Bir düğüme, kök düğümden gelen yolun uzunluğudur. Bu uzunluğu bulmak için yol üzerindeki kenarlar sayılır. • Yükseklik (height): Bir düğümden, yaprak düğüme giden yolun uzunluğudur. Bu uzunluğu bulmak için yol üzerindeki kenarlar sayılır.
Ağaç veri yapıları öncelikle doğası gereği hiyerarşik verilerin temsili için kullanılır. Örneğin, diskler üzerindeki dosyaların özelliklerini saklayan dosya sistemleri ağaç veri yapıları ile oluşturulur. Ağaç veri yapıları ayrıca sözlükler ve yönlendirme tablolarının oluşturulması için de kullanılabilmektedir.
Çizgeler, düğümler (vertice) ve bu düğümleri birleştiren kenarlardan (edge) oluşan veri yapılarıdır. Çizgeler, düğümler arasında hiyerarşik ilişkilerin bulunmadığı çevrimsel ağaçlar şeklinde düşünülebilir. Bu yapıda ebeveyn/çocuk ilişkisi ve katmanlar bulunmadığından, her bir düğüm diğer düğümlerle karmaşık ilişkiler kurabilmektedir. Bir kenar ile birleştirilmiş iki düğüm bitişiktir. Çizgeler tek boyutlu bir düğümler dizisi ve iki boyutlu kenarlar dizisi ile ifade edilir.
Çizgelerdeki kenarların yönlerinin belirtilmemesi hâlinde yönsüz çizgeler, belirtilmesi hâlindeyse yönlü çizgeler oluşturulur. Yönsüz çizgelerdeki A ve B düğümleri
ise kenarın yönü belli olduğundan gezinme giriş düğümünden (initial node) uç düğüme
bilimlerinde çizgeler, iletişim ağlarının
llanılır. Örneğin, bir kullanıcının bir
Bu gösterimde düğümler
llanıcıların hangi
yolu izledikleri ya da giriş sayfasında hangi