3. Ders Veri Yapıları - Dr. Sadi Evren SEKER

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)