Ders Kitapları ve Yardımcı Kaynaklar
-Veri Yapıları ve Algoritmalar
-Dr. Rifat ÇÖLKESEN, Papatya yayıncılık
-Data Structures and Problem Solving Using Java
-Mark Allen Weiss, Pearson International Edition
-Ahmet Yesevi Üniversitesi Ders Notları
-Ayrıca internet üzerinden çok sayıda kaynağa ulaşabilirsiniz
Bu dersteki öğrencilerin Nesne tabanlı programlama dillerinden birisini(Java, C++, C#) veya yordamsal programlama dillerinden birisini(C, Pascal) bildiği varsayılmıştır.
Bilinmesi gereken konular:
Temel veri türleri (int, float)
Kontrol yapısı (if else yapısı)
Döngüler
Fonksiyonlar(Methods)
Giriş çıkış işlemleri
Basit düzeyde diziler ve sınıflar
Veri Yapıları ve Modelleri
Algoritma
Algoritma, bir problemin çözümünde izlenecek yol anlamına gelir. Algoritma, bir programlama dilinde (Java, C++, C# gibi) ifade edildiğinde program adını alır.
Algoritma, belirli bir problemin sonucunu elde etmek için art arda uygulanacak adımları ve koşulları kesin olarak ortaya koyar. Herhangi bir giriş verisine karşılık, çıkış verisi elde edilmesi gereklidir. Bunun dışındaki durumlar algoritma değildir.
Veri
Veri, algoritmalar tarafından işlenen en temel elemanlardır (sayısal bilgiler, metinsel bilgiler, resimler, sesler ve girdi, çıktı olarak veya ara hesaplamalarda kullanılan diğer bilgiler…).
Bir algoritmanın etkin, anlaşılır ve doğru olabilmesi için, algoritmanın işleyeceği verilerin düzenlenmesi gerekir.
Veri Yapısı ve Veri Modeli
Veri yapısı (Data Structure) verinin veya bilginin bellekte tutulma şeklini veya düzenini gösterir.
Tüm programlama dillerinin, genel olarak, tamsayı, kesirli sayı, karakter ve sözcük saklanması için temel veri yapıları vardır. Bir program değişkeni bile basit bir veri yapısı olarak kabul edilebilir.
Veri modeli (Data Model), verilerin birbirleriyle ilişkisel veya sırasal durumunu gösterir; problemin çözümü için kavramsal bir yaklaşım yöntemidir denilebilir.
Bilgisayar ortamında uygulanacak tüm matematik ve mühendislik problemleri bir veri modeline yaklaştırılarak veya yeni veri modelleri tanımlaması yapılarak çözülebilmektedir.
Veri Yapılarına Neden İhtiyaç Vardır?
Bilgisayar yazılımları gün geçtikçe daha karmaşık bir hal almaktadır.
Örneğin 8 milyar sayfanın indekslenmesi (Google)
Yazılımların programlanması ve yönetimi zorlaşmaktadır.
Temiz kavramsal yapılar ve bu yapıları sunan çerçeve programları, daha etkin ve daha doğru program yazmayı sağlar.
Veri Yapılarına Neden İhtiyaç Vardır?
İyi bir yazılım için gereksinimler:
Temiz bir tasarım
Kolay bakım ve yönetim
Güvenilir
Kolay kullanımlı
Hızlı algoritmalar
Verimli Veri Yapıları
Verimli Algoritmalar
Veri Yapılarına Neden İhtiyaç Vardır?
Örnek
Her biri satır başına ortalama 10 kelimeden ve yine ortalama 20 satırdan oluşan 3000 metin koleksiyonu olduğunu düşünelim.
→600,000 kelime
Bu metinler içinde “dünya” kelimesi ile eşleşecek bütün kelimeleri bulmak isteyelim
Doğru eşleştirme için yapılacak karşılaştırmanın 1 sn. sürdüğünü varsayalım.
Ne yapılmalıdır?
Veri Yapılarına Neden İhtiyaç Vardır?
Örnek
Çözüm. 1:
Sıralı eşleştirme: 1 sn. x 600,000 kelime= 166 saat
Çözüm. 2:
İkili Arama (Binary searching):
‐ kelimeler sıralanır
‐ sadece tek yarıda arama yapılır
toplam adım sayısı log 2 N= log 2 600000 yaklaşık 20 adım (çevrim) 20 sn.
20 saniye veya 166 saat!
Veri Yapılarına Neden İhtiyaç Vardır?
Örnek :25 değerini 5 8 12 15 15 17 23 25 27 dizisinde arayalım. Kaç adımda sonuç bulunur?
25 ? 15 15 17 23 25 27
25 ? 23 23 25 27
25 ? 25
14
Veri Yapılarının Sınıflandırılması
Veri yapıları,
Temel Veri Yapıları
Tanımlamalı (Bileşik) Veri Yapıları
Temel veri yapıları, daha çok programlama dilleri tarafından doğrudan değişken veya sabit bildirimi yapılarak kullanılır.
Tanımlamalı veri yapıları, kendisinden önceki tanımlamalı veya temel veri yapıları üzerine kurulurlar; yani, önceden geçerli olan veri yapıları kullanılarak sonradan tanımlanırlar.
Veri Yapılarının Sınıflandırılması
Programlama dilinin elverdiği ölçüde, hemen her tür veri yapısı tanımlanabilir. C Programlama dilinde yeni veri yapısı tanımlamak için struct, union gibi birkaç deyim vardır.
Aşağıdaki bildirime göre tam, kr ve kesirli adlı değişkenler, C programlama dilinde birer temel veri yapısıdır; ancak, toplam adlı değişken ise, tanımlamalı veri yapısı şeklindedir. struct karmasik adlı veri yapısının 2 tane üyesi vardır; biri gerçel, diğeri sanal kısmı tutmak için kullanılır.
Temel Veri Yapıları
Tüm programlama dillerinin, genel olarak, karakter, tamsayı, kesirli sayı ve sözcük (karakter katarı) saklanması için temel veri yapıları vardır. Veri yapısı, aslında, ham olarak 1 ve 0’lardan oluşan verinin yorumlanmasını belirleyen biçimleme (formating) düzenidir. Örneğin, 62 sayısının ikili tabandaki karşılığı, 111110 olarak bellekte saklanır.
Temel veri yapıları aşağıdaki gibi sınıflanabilir:
Tanımlamalı Veri Yapıları
Tanımlamalı veri yapısı, temel veya daha önceden tanımlanmış veri yapılarının kullanılıp yeni veri yapıları oluşturulmasıdır. Üç değişik şekilde yapılabilir:
Topluluk (Struct) Oluşturma: Birden çok veri yapısının bir araya getirilip yeni bir veri yapısı ortaya çıkarmaktır. (Java dilinde sınıflar)
Ortaklık (Union) Oluşturma: Birden çok değişkenin aynı bellek alanını kullanmasını sağlayan veri yapısı tanımlamasıdır. Ortaklıkta en fazla yer işgal eden veri yapısı hangisi ise, ortaklık içerisindeki tüm değişkenler orayı paylaşır.
Bit Düzeyinde Erişim: Verinin her bir bit’i üzerinde diğerlerinden bağımsız olarak işlem yapılması olanağı sunar.
Her birinin kullanım amacı farklı farklı olup uygulamaya göre bir tanesi veya hepsi bir arada kullanılabilir. Genel olarak, en çok kullanılanı topluluk oluşturmadır; böylece birden fazla veri yapısı bir araya getirilip/paketlenip yeni bir veri yapısı/türü ortaya çıkarılır.
Veri Modelleri
Veri modelleri, tasarımı yapılacak programın en uygun ve etkin şekilde olmasını sağlar ve daha baştan programın çalışma hızı ve bellek gereksinimi hakkında bilgi verir. Çoğu zaman, programın çalışma hızıyla bellek gereksinimi miktarı doğru orantılıdır denilebilir.
Veri modeller, genel olarak, aşağıdaki gibi verilebilir:
Bağlantılı Liste (Link List)
Ağaç (Tree)
Graf (Graph)
Durum Makinası (State Machine)
Veritabanı-İlişkisel (Database Relational)
Ağ Bağlantı (Network Connection)
Liste ve Bağlantılı Liste Veri Modeli
Liste veri modeli, aynı kümeye ait olan verilerin bellekte art arda tutulması ilkesine dayanır. Veriler belirli bir düzen içerisinde (sıralı vs.) olabilir veya olmayabilir; önemli olan tüm verilerin art arda gelen sırada tutulmasıdır.
Liste ve Bağlantılı Liste Veri Modeli
Liste veri modeli, aynı kümeye ait olan verilerin bellekte art arda tutulması ilkesine dayanır. Veriler belirli bir düzen içerisinde (sıralı vs.) olabilir veya olmayabilir; önemli olan tüm verilerin art arda gelen sırada tutulmasıdır.
Ağaç Veri Modeli
Ağaç veri modeli, düğümlerden ve dallardan oluşur; düğümlerde verilerin kendileri veya bir kısmı tutulurken, dallar diğer düğümlere olan bağlantı ilişkilerini gösterir. Ağaç veri modeli, özellikle kümenin büyük olduğu ve arama işleminin çok kullanıldığı uygulamalarda etkin bir çözüm sunar.
En üstteki düğüm kök (root), kendisine alttan hiçbir bağlantının olmadığı düğüm yaprak (leaf), diğerleri de ara düğüm (internal node) olarak adlandırılır. Bir düğüme alttan bağlı düğümlere çocuk (child), üsten bağlı düğüme de o düğümün ailesi (parent) denilir.
Graf Veri Modeli
Graf veri modeli, aynı kümeye ait olan verilerin şekilde görüldüğü gibi düğümler, ayrıtlar (kenarlar) ve bunların birleştirilmesinden oluşur. Düğümler birleşme noktasını ayrıtlar da düğümlerin bağlantı ilişkisini gösterir. Verilerin kendileri veya bir kısmı hem düğümlerde hem de ayrıtların bilgi kısmında tutulabilir.
Graflar, yazılım dünyasından önemli bir yere sahiptir. Örneğin, bir şehrin trafik altyapısından en yüksek akışın sağlanması, taşıma şirketinin en verimli taşıma şekli veya network bağlantılarında yüksek başarım elde edilmesi gibi problemler.
Durum Makinası Veri Modeli
Durum makinası veri modeli, bir sistemin davranışını tanımlamak ve ortaya çıkarmak için kullanılan bir yaklaşım şeklidir; işletim sistemlerinde, derleyici ve yorumlayıcılarda, kontrol amaçlı yazılımlarda sistemin davranışını durumlara indirger ve durumlar arası geçiş koşullarıyla sistemi ortaya koyar.
Durum makinası, yazılım uygulamasında birçok alanda kullanılabilir. Örneğin bir robot kolunun hareketi, şifre çözme, gerçek zamanlı işletim sistemlerinde proses kontrolü ve genel olarak kontrol alt sistemlerinin yazılımla uygulamayı başarılı bir şekilde sonuçlandırma durumlarında çözüm olur.
Durum Makinası Veri Modeli
Durum makinası veri modeli şeklen yönlü graflara benzer, ancak, birleşme noktaları graflarda olduğu gibi düğüm olarak değil de durum, ayrıtlar da geçiş eğrileri olarak adlandırılır. Durumlar arasındaki geçişler, sistemin o ana kadar ki durumlarına ve giriş parametrelerine bağlıdır.
Veritabanında İlişkisel Veri Modeli
Veritabanı ilişkisel veri modeli veritabanı uygulamalarında var olan dört beş sınıftan birisidir; veriler şekilde gösterildiği gibi tablolar üzerinden kurulan ilişkilere dayanmaktadır.
Veritabanında İlişkisel Veri Modeli
SQL (Structured Query Language), sorgulama dili kullanılarak veritabanı üzerinde sorgulama yapılabilir. Access, Microsoft SQL, ORACLE, SYBASE, Ingres gibi birçok veritabanı yönetim sistemleri ilişkisel veri modelini desteklemektedir.
Veritabanı yönetim sistemleri, veritabanı oluşturma, tablo yaratma, alanları tanımlama gibi işlerin başarılı bir şekilde sonuçlandırmasını ve genel olarak veritabanı yönetimini sağlarlar.
Ağ Veri Modeli
Ağ veri modeli, katmalı ağ mimarilerinde, bilgisayarlar arasında eş katmanlar (peer layers) düzeyinde veri alış-verişini sağlayan dilim (segment), paket (packet) ve çerçeve yapılarını ortaya koyar ve iletişim için gerekli davranışı tanımlar. Veri haberleşmesinde hemen hemen tüm mimariler katmanlı yapıdadır. Tüm mimariler örnek temsil eden OSI 1, başvuru modeli 7, TCP/IP (Transmission Control Protocol / Internet Protocol) protokol kümesi 4 katmanlıdır.
Veri Modelleri
Bu derste aşağıdaki veri modelleri detaylı ele alınacaktır;
Liste
Sonlu sayıda elemandan oluşan ve elemanları doğrusal sırada yerleştirilmiş veri modeli. Herhangi bir elemanına erişimde sınırlama yoktur.
Yığıt veya Yığın
Elemanlarına erişim sınırlaması olan, liste uyarlı veri modeli (Last In First Out-LIFO listesi).
Kuyruk
Elemanlarına erişim sınırlaması olan, liste uyarlı veri modeli. (First In First Out-FIFO listesi).
Ağaç
Doğrusal olmayan belirli niteliklere sahip veri modeli
Çizge (Graph)
Köşe adı verilen düğümleri ve kenar adı verilen köşeleri birbirine bağlayan bağlantılardan oluşan doğrusal olmayan veri modeli
Veri Yapısı
Artıları
Eksileri
Dizi
Hızlı ekleme ve çok hızlı erişim(indis biliniyorsa).
Yavaş arama, yavaş silme ve sabit boyut.
Sıralı Dizi
Sıralanmamış diziye göre daha hızlı arama.
Yavaş arama, yavaş silme ve sabit boyut.
Yığın
Son giren, ilk çıkar(last-in, first-out) erişimi sağlar.
Diğer öğelere yavaş erişim.
Kuyruk
İlk giren, ilk çıkar(first-in, first-out) erişimi sağlar.
Diğer öğelere yavaş erişim.
Bağlı Liste
Hızlı ekleme ve silme.
Yavaş arama.
Hash Tablosu
Hızlı ekleme ve anahtar bilindiğinde çok hızlı erişim.
Yavaş silme, anahtar bilinmediğinde yavaş erişim ve verimsiz bellek kullanımı.
Küme(Heap)
Hızlı ekleme ve silme.
Diğer öğelere yavaş erişim. Başta en büyük öğeye erişim.
İkili Ağaç
Hızlı arama, ekleme ve silme(ağaç dengeli kalmışsa).
Silme algoritması karmaşık.
Graf
Gerçek-dünya problemlerini modelleyebilmesi.
Bazı algoritmaları yavaş çalışmakta ve karmaşıklığı yüksek.
Veri Yapıları- Bölüm Özeti
Veri modelleri ve onlara ait veri yapıları yazılım geliştirmenin temel noktalarıdır; problemlerin en etkin şekilde çözülebilmesi için ona algoritmik ifadenin doğasına yakın bulunmasıdır. Kısaca, veri yapıları, verinin saklanma kalıbını, veri modelleri de veriler arasındaki ilişkiyi gösterir.
Bilinen ve çözümlerde sıkça başvurulan veri modelleri, genel olarak, bağlantılı liste (link list), ağaç (tree), graf (graph), durum makinası (state machine), ağ (network) ve veritabanı-ilişkisel (database-relation) şeklinde verilebilir.
Her veri modelinin, altında duran veri yapısına bağlı olarak, işlem zaman maliyetleri ve bellek gereksinimleri farklıdır. Program geliştirilirken, zaman ve bellek alanı maliyetlerini dengeleyecek çözüm üretilmeye çalışılır. Genel olarak, RAM türü ardışıl erişimlerin yapılabildiği bellek üzerinde, maliyeti ile bellek gereksinim ters orantılı olduğu söylenebilir.
