Veri yapısı - Data structure

Karma tablo olarak bilinen bir veri yapısı .

Gelen bilgisayar bilimleri , bir veri yapısı verimli erişim ve modifikasyon sağlayan bir veri organizasyonu, yönetim ve depolama biçimidir. Daha doğrusu bir veri yapısı, veri değerleri, bunlar arasındaki ilişkiler ve verilere uygulanabilecek işlevler veya işlemler topluluğudur, yani verilerle ilgili cebirsel bir yapıdır .

kullanım

Veri yapıları, soyut veri türleri (ADT) için temel oluşturur . ADT, veri türünün mantıksal biçimini tanımlar. Veri yapısı, veri türünün fiziksel biçimini uygular.

Farklı türdeki veri yapıları, farklı türdeki uygulamalara uygundur ve bazıları belirli görevler için oldukça uzmanlaşmıştır. Örneğin, ilişkisel veritabanları veri alımı için yaygın olarak B-ağacı dizinlerini kullanırken, derleyici uygulamaları genellikle tanımlayıcıları aramak için karma tabloları kullanır.

Veri yapıları, büyük veritabanları ve internet indeksleme hizmetleri gibi kullanımlar için büyük miktarda veriyi verimli bir şekilde yönetmek için bir araç sağlar . Genellikle verimli veri yapıları, verimli algoritmalar tasarlamanın anahtarıdır . Bazı biçimsel tasarım yöntemleri ve programlama dilleri , yazılım tasarımında anahtar düzenleyici faktör olarak algoritmalardan ziyade veri yapılarını vurgular. Veri yapıları, hem ana bellekte hem de ikincil bellekte depolanan bilgilerin depolanmasını ve alınmasını düzenlemek için kullanılabilir .

uygulama

Veri yapıları genellikle bir bilgisayarın , bir işaretçi tarafından belirtilen, belleğindeki herhangi bir yerden veri alma ve saklama yeteneğine dayanır - bir bellek adresini temsil eden , kendisi bellekte saklanabilen ve program tarafından manipüle edilebilen bir bit dizisi . Bu nedenle, dizi ve kayıt veri yapıları, aritmetik işlemlerle veri öğelerinin adreslerinin hesaplanmasına dayanırken, bağlantılı veri yapıları , veri öğelerinin adreslerinin yapının kendisinde saklanmasına dayanır.

Bir veri yapısının uygulanması genellikle bu yapının örneklerini yaratan ve işleyen bir dizi prosedür yazmayı gerektirir . Bir veri yapısının verimliliği, bu işlemlerden ayrı olarak analiz edilemez. Bu gözlem, soyut bir veri tipinin teorik kavramını, üzerinde gerçekleştirilebilecek işlemlerle dolaylı olarak tanımlanan bir veri yapısını ve bu işlemlerin matematiksel özelliklerini (uzay ve zaman maliyetleri dahil) motive eder .

Örnekler

Python 3. Standart tür hiyerarşi.png

Genellikle daha basit ilkel veri türleri üzerine inşa edilmiş çok sayıda veri yapısı türü vardır :

  • Bir dizi , belirli bir sırada, tipik olarak hepsi aynı türden bir dizi öğedir (dile bağlı olarak, tek tek öğelerin tümü ya aynı türde olmaya zorlanabilir ya da hemen hemen her türden olabilir). Hangi öğenin gerekli olduğunu belirtmek için öğelere bir tamsayı dizini kullanılarak erişilir. Tipik uygulamalar, dizilerin öğeleri için bitişik bellek sözcükleri tahsis eder (ancak bu her zaman bir gereklilik değildir). Diziler sabit uzunlukta veya yeniden boyutlandırılabilir olabilir.
  • Bir bağlanmış liste (aynı zamanda, sadece adı verilen listesi ) bağlantılı hale getirilmiş liste içinde bir sonraki düğüme veri her bir düğümün kendisi bir değere sahip herhangi bir tür elemanlar olarak adlandırılan düğümler, ve puanlık bir doğrusal koleksiyonudur. Bir bağlantılı listenin bir diziye göre başlıca avantajı, değerlerin listenin geri kalanının yerini değiştirmeden her zaman verimli bir şekilde eklenip kaldırılabilmesidir. Belirli bir öğeye rastgele erişim gibi belirli diğer işlemler, listelerde dizilere göre daha yavaştır.
  • Bir kayıt ( tuple veya struct olarak da adlandırılır ) bir toplu veri yapısıdır. Kayıt, tipik olarak sabit sayı ve sırayla ve tipik olarak adlara göre dizine eklenmiş diğer değerleri içeren bir değerdir. Kayıtların öğelerine genellikle alanlar veya üyeler denir .
  • Bir birlik bir veri yapısıdır olduğu izin temel tür bir dizi örneklerinin, örneğin depolanabilir belirtir şamandıra veya uzun bir tamsayı . Bir kayan nokta ve bir tamsayı içerecek şekilde tanımlanabilecek bir kayıtla kontrast ; oysa bir birlik içinde bir seferde yalnızca bir değer vardır. En geniş üye veri tipini içerecek kadar yeterli alan ayrılmıştır.
  • Bir isim levhası birlik (ayrıca varyant , varyant kayıt , ayrımcılık birlik veya ayrık birleşimi ) artmış tür güvenliği için akım türü belirten ek bir alan ihtiva eder.
  • Bir nesne , bir kaydın yaptığı gibi veri alanlarını ve ayrıca veri içerikleri üzerinde çalışan çeşitli yöntemleri içeren bir veri yapısıdır . Bir nesne, bir sınıflandırmadan bir sınıfın bellek içi örneğidir . Nesne yönelimli programlama bağlamında , kayıtlar, onları nesnelerden ayırt etmek için düz eski veri yapıları olarak bilinir .

Ek olarak, grafikler ve ikili ağaçlar , yaygın olarak kullanılan diğer veri yapılarıdır.

Dil desteği

Çoğu montaj dili ve BCPL (Temel Birleştirilmiş Programlama Dili) gibi bazı düşük seviyeli diller , veri yapıları için yerleşik destekten yoksundur. Öte yandan, birçok üst düzey programlama dili ve MASM gibi bazı üst düzey derleme dilleri, kayıtlar ve diziler gibi belirli veri yapıları için özel sözdizimine veya diğer yerleşik desteğe sahiptir. Örneğin, C (BCPL'nin doğrudan soyundan gelen) ve Pascal dilleri , vektörlere (tek boyutlu diziler ) ve çok boyutlu dizilere ek olarak sırasıyla yapıları ve kayıtları destekler .

Çoğu programlama dili , veri yapısı uygulamalarının farklı programlar tarafından yeniden kullanılmasına izin veren bir tür kitaplık mekanizmasına sahiptir. Modern diller genellikle en yaygın veri yapılarını uygulayan standart kitaplıklarla birlikte gelir. Örnekler, C++ Standart Şablon Kitaplığı , Java Koleksiyonları Çerçevesi ve Microsoft .NET Çerçevesidir .

Modern diller ayrıca genellikle modüler programlamayı , bir kütüphane modülünün arayüzü ile onun uygulanması arasındaki ayrımı destekler . Bazıları, istemcilerin uygulama ayrıntılarını gizlemesine olanak tanıyan opak veri türleri sağlar. C++ , Java ve Smalltalk gibi nesne yönelimli programlama dilleri genellikle bu amaç için sınıfları kullanır .

Bilinen birçok veri yapısı, birden fazla bilgi işlem iş parçacığının bir veri yapısının tek bir somut örneğine aynı anda erişmesine izin veren eşzamanlı sürümlere sahiptir.

Ayrıca bakınız

Referanslar

bibliyografya

daha fazla okuma

Dış bağlantılar