Algoritma ve Veri Yapıları 3 List-Stack-Queue

1. Giriş

Merhabalar, Bu başlık altında 3tane önemli ve en temel veri yapılarını tartışacağız. Kullandığımız bir çok önemli yazılımlar bu yapıları kullanmaktadır. Ama daha öncesinde Soyut Veri Türleri değinmek istiyorum. Stack,List,Queue birer Soyut veri türüdür.

2. Soyut Veri Yapıları (Abstract Data Type)

Bir soyut veri yapısı, obje kümelerinden oluşmaktadır. Aslında tüm soyut veri yapıları matematiksel soyutlamalardan oluşur ama, Biz daha çok kullanılmalarından ve programlaması üzerinde duracağımız için. Matematiksel yönünü, bizim şimdilik düşünmemiz önemli değildir. Liste gibi objeler , kümeler, graphlar ve onların operatörlerini, soyut veri yapıları kullanarak tanımlayabiliriz. Veri yapıları tanımlarken kesin bir kuralımız yoktur. SVY tanımlarken bizim kullandığımız tasarıma göre kuralları ortaya çıkartırız.

3. LİST

Listelerin genel formu A0,A1,A2,........,An-1 şeklindedir. Bu durumda list'mizde genişliği ise N olmaktadır. Eğer ki bir list genişliği, 0 ise bizim için list boştur. Yani boş list (empty list) olarak adlandırırız. Eğer Ai, Ai-1 (i<N) takip ediyorsa (sonra geliyorsa) veya Ai-1 önce geliyorsa Ai(i>0). Bu durumda An sonrası yada A0 öncesi tanımlı değildir. İlk elamanı A0 ve son elamanı An-1 olan bir listede, Ai elemanın pozisyonunu i belirtmektedir. Bu tanımlarla ilgi bazı önemli operasyonlardan bahsedecek olursak; Listeyi yazıdır, ListeyiBosalt, Bul(kaçıncı sırada olduğu), KthEkle(belli bir pozisyona ekleme). Örnek: 35 42 11 55 88 66 124 gibi 7 elamanlı bir listemiz olsun ve 3 pozisyona bir ekleme yapalım KthEkle(x,3) bu durumda 35 42 11 x 55 88 66 124 şeklinde eklenmelidir.

3.1. Listenin Basit Dizi Uygulamaları

Bilindiği üzere bir dizi yaratır iken sabit bir alan ayırmak zorundayız. int X [5] örnek vermek gerekirse. Dizin tüm elemanlarını yazdırmak istediğimizde ise O zamanda; Hangi Indekste hangi elamanın olduğu öğrenmek içinde O(1) sabit bir zamana ihtiyacımız vardır. Ekleme, Silme işlemleri de bir o kadar yorucudur. İlk posizyona yani, Sıfırıncı indis'e ekleme yaptığımızda, dizinin boyutunu artırıp, bütün elamanlarını birer pozisyon kaydırıp ilk sıraya ekleme yapmalıyız. bu durumda O(N) zamana ihtiyaç doğacaktır.

3.2. LİNKED LİST

Linked listler, ekleme ve silme işlemlerinden lineer (dogrusal) yani O kaçınmak için tasarlanmıştır. Linked Listler aslında Düğüm (Node) serilerinden oluşmaktadır ve her düğüm bir element (int x) ve kendinden sonra gelen düğümün linkini tutmaktadır. Bir linked listin tüm elemanlarını yazdırmayı istediğimizde, İlk düğümden başlayarak, bir sonraki düğüme geçiş yapar, yine dizilerde O lineer zamana ihtiyacımız olacaktır. Ancak, bir i'ninci sıradaki bir elemanı bulmak isteydik bu zaman O(i) olacaktı.

yukarıda alıntı yapılarak gösterilen resimde Linked List yapısı gösterilmektedir.


Eğer ki bir biz 2. düğümü silmek isteseydik, 1. nodun linkini 3 node bağlayacaktık. Ekleme işleminde ise malloc ile yer ayırarak yeni bir node oluşturup. Önceki düğümün linkini oluşturduğumuz düğüme, Yeni düğümün linki de önceki düğümden sonra gelen düğüme bağlanacaktır. Böylecelikle dizide O lineer zamanı ihtiyacımız var iken, Linked listte bu durum O(1) sabit zamanda yapılacaktır.

1.3. Vektör Dizi uygulaması

1. Vektör Uygulaması : indexlenmesi sabit zamanda yapılır. veri eklemesi veya silmesi zordur.
   
2. List Uygulaması: Veri eklenmesi veya silinmesi basittir. Ama indexlenemez.

Örnek pseudo Kod:
#define FatalError(str) fprintf(stderr,"%s\n",str) exit(1)
#include <stdlib.h>
#include "fatal.h"
#define SPARE_Capacity 16
typedef int ElementType;

Struct listHeader
{
int size;
int capacity;
ElelentType* elements;
}

typedeff struct listHeader * list;

List InitializeList (List L )
{
if (L !=Null ) DeleteList(L);
L = Malloc(sizeof( Struct Listheader);
if (L == NULL ) FattalError("Out Of memory");
L->size = 0;

Yazı Devam Edecektir

Video hazırlayamazmısınız?

Planlıyorum ama, khan academy deki gibi bir program arıyorum. Öteki türlü hem tahta hem kamera zor oluyor.

Anladım ancak video daha iyi olacaktır. Yapmaya çalışın.