3. Ders Veri Yapıları - Dr. Sadi Evren SEKER
Transkript
3. Ders Veri Yapıları - Dr. Sadi Evren SEKER
Veri Yapıları Yrd. Doç. Dr. Şadi Evren ŞEKER Not: Bu sunumun amacı, İstanbul Üniversitesi Bilgisayar Mühendisliği Bölümü, Bilgisayar Mühendisliğine Giriş Dersi için genel amaçlı veri yapıları hakkında bilgi vermektir. Bilmenin Seviyeleri Veri (Data) ●Bilgi (Information) ●Malumat(Knowledge) ●Bilgelik (Wisdom) ● Veri Yapılarına Neden İhtiyaç duyulur ● Hafıza ve Zaman ikilemi ● Probleme özel çözümler ● Verinin kolay erişilebilirliği Veri Yapılarına Erişim Şekilleri ● ● Ardışık Erişim Şekilleri (Sequential Access) ● FIFO (First In First Out) , İlk Giren İlk Çıkar ● LIFO (Last In First Out) , Son Giren İlk Çıkar Doğrudan Erişim Şekilleri (Rast Gele Erişim, Random Access) Klasik Veri Yapıları ● Yığın (Stack) ● Sıra (Queue) ● Öncelik Sırası (Priority Queue) ● Dairesel Sıra (Circular Queue) ● Diziler (Array) ● Ağaçlar (Tree) Diziler ● ● ● Rastgele erişim mümkündür Gösterici Aritmetiği Kullanılabilir (pointer artihmetic) Hafızada Sabit yer ayırılması gerekir(Static memory allocation) Diziler Kullanılarak Veri Sıralama ● Seçerek Sıralama (Selection Sort) ● Rastgele Sıralama (Bogo Sort) ● Kabarcık Sıralaması (Baloncuk Sıralaması, Bubble Sort) ● Öne Ekleme Sıralaması (Insert Front Sort) ● Kabuk Sıralaması (Shell Sort) ● Sallama Sıralaması (Shaker's Sort) Verinin Aranması ● Doğrusal Arama (Linear Search) ● İkili Arama Algoritması (Binary Search) Gösterici Kullanımı ● ● Bağlı Listeler (Linked List) ● Çift Bağlı Listeler (Doubly Linked List) ● Çift Uçlu Listeler (Double Ended Lists) ● Dairesel Bağlı Listeler (Circular Lists) Ağaçlar (Tree) ● İkili Ağaçlar (Binary Tree) ● N-li Ağaçlar (N-ary Tree) ● Yığıt (Heap) Bağlı Liste Görselleştirmesi Tekli Bağlı Liste (Singular Linked List) ●Çift Uçlu Bağlı Liste (Double Ended Linked List) ●Çift Yönlü Bağlı Liste (Doubly Linked List) ●Dairesel Bağlı Liste (Circular Linked List) ● Dolaşma Algoritmaları ● Dolaşıcı (Iterator) Kullanılması ● Listeye Ekleme ● Listeden Silme ● Listeden Okuma / Arama Dolaşıcı (Iterator) Bağlı Listeye Ekleme İşlemi ● Eklenecek Yerden bir önceye Gidilir ● Yeni Düğüm (node) oluşturulur ● ● Yeni düğümün sonrasına, eklemeden sonraki düğümün sonrası atanır Dolaşıcının (Iterator) sonrasına yeni düğüm atanır Bağlı Listeye Yeni Eleman Eklenmesinin Görsel hali Dolaşıcı (Iterator) Dolaşıcı (Iterator) Dolaşıcı (Iterator) Çift Bağlı Listeye Eleman Eklenmesi Dolaşıcı (Iterator) Dolaşıcı (Iterator) Dolaşıcı (Iterator) Dolaşıcı (Iterator) Bağlı Listeden Eleman Silinmesi ● ● ● Silinecek Düğümden öncesine kadar gidilir Dolaşıcının sonrası, sonrasının sonrasına atanır. Eski düğüm hafızadan kaldırılır Listeden Düğüm Silinmesi Dolaşıcı (Iterator) Dolaşıcı (Iterator) Dolaşıcı (Iterator) Bağlı Listelerde Veri Organizasyonu ● Sıralı Bağlı Listeler ● Bağlı Listede Arama ● ● Doğrusal Arama İkili Arama (Binary Search): Ağacın bağlı liste üzerinde kodlanması Ağaçlar ● ● Çizge Kuramı Dersinin Notlarını Hatırlayınız (Graph Theory) Klasik bir ağaç aşağıdaki yapıdadır ● Veri ● Çocuklarını gösteren işaretçiler (pointers) ● Bir ağaçtaki her düğümün tek çocuğu varsa bağlı listedir. Ağaçlarda Dolaşma ● ● Derin Öncelikli Dolaşma (Depth First Search) ● LRN ● RLN ● RNL ● LNR Sığ Öncelikli Dolaşma (Breadth First Search) ● NLR ● NRL Bir Ağacın Dizide Kodlanması Kök 0'ın Solu 0'ın Sağı 1'in Solu 1'in Sağı 2'nin Solu 2'nin Sağı 3'ün Solu 0 1 2 3 4 5 6 7 0 1 3 7 Sol Düğüm : 2i +1 Sağ Düğüm: 2i +2 2 4 5 6 Yığıtlar ● Azami Yığıt (Max-Heap) ● Asgari Yığıt (Min-Heap) ● Yığıtlama (Heapify) Yığıtlama (Heapify) Eleman Eklenmesi ● 7 25 32 25 43 35 89 45 32 46 43 89 45 46 35 7 Kök 0'ın Solu 0'ın Sağı 1'in Solu 1'in Sağı 2'nin Solu 2'nin Sağı 3'ün Solu 0 1 2 3 4 5 6 7 25 32 43 35 89 45 46 7 7 25 43 32 89 45 46 35 Yığıtlarda Silme 25 43 32 35 43 89 45 32 46 35 46 89 45 Kök 0'ın Solu 0'ın Sağı 1'in Solu 1'in Sağı 2'nin Solu 2'nin Sağı 0 1 2 3 4 5 6 25 32 43 35 89 45 46 43 32 35 89 46 45 Yığıtlama ● Karışık bir dizinin yığıtlanması 15 3 35 11 8 2 15 Yığıtlama 15 35 35 3 11 8 2 15 15 15 35 3 15 8 2 11 3 15 8 2 11 Yığıt Sıralaması (Heap Sort) 25 32 35 43 89 45 46 B-Ağaçları (B-Tree) ● B-Ağaçlarının Düğüm Boyu (Node Size) ● B-Ağacında Arama ● B-Ağacına Ekleme ● B-Ağacından Silme Özetleme (Hashing) ● Özetleme Fonksiyonları ● Özetleme Tabloları ● Çakışma (Collusion)