Soyut veri türü - Abstract data type

İle karıştırılmaması gereken cebirsel veri türü.

İçinde bilgisayar Bilimi, bir soyut veri türü (ADT) bir matematiksel model için veri tipleri. Soyut bir veri türü, davranışıyla tanımlanır (anlambilim ) bakış açısından kullanıcıveriler, özellikle olası değerler, bu tür veriler üzerindeki olası işlemler ve bu işlemlerin davranışı açısından. Bu matematiksel model, veri yapıları, verilerin somut temsilleri olan ve bir kullanıcının değil, uygulayıcının bakış açısıdır.

Resmi olarak, bir ADT, "mantıksal davranışı bir dizi değer ve bir dizi işlemle tanımlanan bir nesne sınıfı" olarak tanımlanabilir;[1] bu bir cebirsel yapı Matematikte. "Davranış" ile kastedilen, yazara göre değişir, davranış için iki ana biçimsel belirtim türü aksiyomatik (cebirsel) şartname ve bir soyut model;[2] bunlar karşılık gelir aksiyomatik anlambilim ve operasyonel anlambilim bir soyut makine, sırasıyla. Bazı yazarlar ayrıca hesaplama karmaşıklığı ("maliyet"), hem zaman (hesaplama işlemleri için) hem de alan (değerleri temsil etmek için) açısından. Pratikte, birçok yaygın veri türü ADT değildir, çünkü soyutlama mükemmel değildir ve kullanıcılar aşağıdaki gibi sorunların farkında olmalıdır. aritmetik taşma bu temsilden kaynaklanmaktadır. Örneğin, tamsayılar genellikle sabit genişlikli değerler (32 bit veya 64 bit ikili sayılar) olarak depolanır ve bu nedenle tamsayı taşması maksimum değer aşılırsa.

ADT'ler, bilgisayar bilimlerinde teorik bir kavramdır, tasarım ve analizinde kullanılır. algoritmalar, veri yapıları ve yazılım sistemleri ve bunların belirli özelliklerine karşılık gelmez bilgisayar dilleri —Mainstream bilgisayar dilleri, resmi olarak belirtilen ADT'leri doğrudan desteklemez. Bununla birlikte, çeşitli dil özellikleri ADT'lerin belirli yönlerine karşılık gelir ve ADT'lerle kolayca karıştırılabilir; bunlar şunları içerir soyut tipler, opak veri türleri, protokoller, ve sözleşme ile tasarım. ADT'ler ilk olarak Barbara Liskov ve 1974'te Stephen N. Zilles, CLU dil.[3]

Örnekler

Örneğin, tamsayılar ..., −2, −1, 0, 1, 2, ... değerleri olarak ve toplama, çıkarma, çarpma ve bölme işlemleriyle birlikte büyüktür, küçüktür, bilindik matematiğe göre davranan (dikkatle tamsayı bölümü ), bilgisayar tarafından tam sayıların nasıl temsil edildiğinden bağımsız olarak.[a] Açıkça, "davranış", çeşitli aksiyomlara (eklemenin birleşebilirliği ve değişebilirliği, vb.) Ve işlemler üzerindeki ön koşullara (sıfıra bölünemez) uymayı içerir. Tipik olarak tamsayılar bir veri yapısında şu şekilde temsil edilir: ikili sayılar, çoğu zaman Ikisinin tamamlayıcısı ama olabilir ikili kodlu ondalık veya içinde birinin tamamlayıcısı, ancak kullanıcı somut temsil seçiminden soyutlanmıştır ve verileri veri türleri olarak basitçe kullanabilir.

Bir ADT yalnızca işlemlerden değil, aynı zamanda temeldeki verilerin değerlerinden ve işlemler üzerindeki kısıtlamalardan da oluşur. Bir "arayüz" tipik olarak sadece operasyonlara ve belki de operasyonlar üzerindeki bazı kısıtlamalara, özellikle ön koşullar ve son koşullar, ancak operasyonlar arasındaki ilişkiler gibi diğer kısıtlamalara atıfta bulunur.

Örneğin, bir özet yığın Son giren ilk çıkar yapısı olan, üç işlemle tanımlanabilir: it, yığına bir veri öğesi ekleyen; pop, ondan bir veri öğesini kaldıran; ve dikizlemek veya üst, kaldırmadan yığının üstündeki bir veri öğesine erişen. Bir soyut kuyruk İlk giren ilk çıkar yapısı olan, aynı zamanda üç operasyona sahip olacaktır: sıraya almakkuyruğa bir veri öğesi ekleyen; kuyruktan çıkarmak, ilk veri öğesini ondan kaldıran; ve ön, kuyruktaki ilk veri öğesine erişen ve hizmet veren. Bir yığın için her bir pop'un her zaman en son gönderilen ve henüz atılmamış öğeyi döndürdüğünü belirten matematiksel bir kısıtlama getirilmedikçe, bu iki veri türünü ayırt etmenin bir yolu yoktur. Ne zaman verimliliği analiz etmek Yığınları kullanan algoritmalardan biri, yığına kaç tane veri öğesi itilmiş olursa olsun tüm işlemlerin aynı zamanı alacağını ve yığının her öğe için sabit bir depolama miktarı kullandığını da belirtebilir.

Giriş

Soyut veri türleri, soyut algoritmaların açıklamasını basitleştirmek, veri yapılarını sınıflandırmak ve değerlendirmek ve resmi olarak tanımlamak için kullanılan (diğer şeylerin yanı sıra) tamamen teorik varlıklardır. tip sistemler programlama dilleri. Bununla birlikte, bir ADT olabilir uygulandı spesifik olarak veri tipleri veya veri yapıları, birçok yönden ve birçok programlama dilinde; veya bir resmi belirtim dili. ADT'ler genellikle şu şekilde uygulanır: modüller: modülün arayüz ADT işlemlerine karşılık gelen prosedürleri beyan eder, bazen yorumlar kısıtlamaları tanımlayan. Bu Bilgi gizleme strateji, modülün uygulanmasının bozulmadan değiştirilmesine izin verir. müşteri programları.

Soyut veri türü terimi, aynı zamanda bir dizi genelleştirilmiş bir yaklaşım olarak da kabul edilebilir. cebirsel yapılar kafesler, gruplar ve halkalar gibi.[4] Soyut veri türleri kavramı, veri soyutlama, önemli nesne yönelimli programlama ve sözleşme ile tasarım metodolojileri yazılım geliştirme.[5]

Soyut bir veri türü tanımlama

Soyut bir veri türü, bir veri türünü oluşturan veri nesnelerinin ve bu nesneler üzerinde çalışan işlevlerin matematiksel bir modeli olarak tanımlanır. Bunları tanımlamak için standart kurallar yoktur. "Zorunlu" ve "işlevsel" tanım stilleri arasında geniş bir ayrım yapılabilir.

Zorunlu stil tanımı

Felsefesinde zorunlu programlama soyut bir veri yapısı, bir varlık olarak düşünülür. değişebilir- farklı olabileceği anlamına gelir eyaletler farklı zamanlarda. Bazı işlemler ADT'nin durumunu değiştirebilir; bu nedenle, işlemlerin değerlendirilme sırası önemlidir ve aynı varlıklar üzerindeki aynı işlem, farklı zamanlarda çalıştırılırsa farklı etkilere sahip olabilir - tıpkı bir bilgisayarın talimatları veya emir dilinin komutları ve prosedürleri gibi. Bu görüşün altını çizmek için, işlemlerin idam veya uygulamalı, ziyade değerlendirildi. Zorunlu stil genellikle soyut algoritmaları açıklarken kullanılır. (Görmek Bilgisayar Programlama Sanatı tarafından Donald Knuth daha fazla ayrıntı için)

Soyut değişken

ADT'nin emir kipi tarzı tanımları genellikle bir soyut değişken, en basit, önemsiz olmayan ADT olarak kabul edilebilir. Soyut bir değişken V iki işlemi kabul eden değiştirilebilir bir varlıktır:

  • mağaza(V, x) nerede x bir değer belirtilmemiş nitelikte;
  • getirmek(V), bir değer verir,

kısıtlama ile

  • getirmek(V) her zaman değeri döndürür x en son kullanılan mağaza(V, x) aynı değişken üzerinde işlem V.

Pek çok programlama dilinde olduğu gibi, işlem mağaza(V, x) sıklıkla yazılır V ← x (veya benzer bir gösterim) ve getirmek(V) bir değişken olduğunda ima edilir V bir değerin gerekli olduğu bir bağlamda kullanılır. Örneğin, V ← V + 1, genel olarak şunun kısaltması olarak anlaşılır: mağaza(V,getirmek(V) + 1).

Bu tanımda, bir değeri bir değişkene depolamanın örtük olarak varsayılmıştır. U farklı bir değişkenin durumu üzerinde hiçbir etkisi yoktur V. Bu varsayımı açık hale getirmek için, şu kısıtlama eklenebilir:

  • Eğer U ve V farklı değişkenlerdir, dizi { mağaza(U, x); mağaza(V, y)}, { mağaza(V, y); mağaza(U, x) }.

Daha genel olarak, ADT tanımları genellikle bir ADT örneğinin durumunu değiştiren herhangi bir işlemin başka bir örneğin (aynı ADT'nin diğer örnekleri dahil) durumu üzerinde hiçbir etkisinin olmadığını varsayar - ADT aksiyomları iki örneğin birbirine bağlı olduğunu belirtmedikçe (takma ad ) Bu anlamda. Örneğin, soyut değişkenin tanımını soyut içerecek şekilde genişletirken kayıtları, bir kayıt değişkeninden bir alan seçen işlem R bir değişken vermeli V bu kısmının diğer adı R.

Soyut bir değişkenin tanımı V saklanan değerleri de kısıtlayabilir x belirli bir setin üyelerine X, aradı Aralık veya tip nın-nin V. Programlama dillerinde olduğu gibi, bu tür kısıtlamalar açıklamayı basitleştirebilir ve algoritmaların analizi ve okunabilirliklerini artırın.

Bu tanımın değerlendirmenin sonucu hakkında hiçbir şey ifade etmediğini unutmayın. getirmek(V) ne zaman V dır-dir başlatılmamışyani herhangi bir mağaza operasyon V. Bunu yapan bir algoritma, etkisi tanımlanmadığı için genellikle geçersiz kabul edilir. (Bununla birlikte, verimliliği büyük ölçüde böyle bir varsayıma bağlı olan bazı önemli algoritmalar vardır. getirmek yasaldır ve değişkenin aralığında keyfi bir değer döndürür.[kaynak belirtilmeli ])

Örnek oluşturma

Bazı algoritmaların, bazı ADT'lerin (yeni değişkenler veya yeni yığınlar gibi) yeni örneklerini oluşturması gerekir. Bu tür algoritmaları açıklamak için genellikle ADT tanımına a oluşturmak() genellikle aksiyomlar ile ADT'nin bir örneğini veren işlem

  • sonucu oluşturmak(), algoritma tarafından kullanılan herhangi bir örnekten farklıdır.

Bu aksiyom, diğer örneklerle kısmi örtüşmeyi de dışlayacak şekilde güçlendirilebilir. Öte yandan, bu aksiyom hala oluşturmak() programa erişilemez hale gelen önceden oluşturulmuş bir örnek vermek için.

Örnek: soyut yığın (zorunlu)

Başka bir örnek olarak, soyut bir yığının emir kipi tarzı bir tanımı, bir yığının durumunun S sadece işlemler tarafından değiştirilebilir

  • it(S, x), nerede x biraz değer belirtilmemiş nitelikte;
  • pop(S), sonuç olarak bir değer veren,

kısıtlama ile

  • Herhangi bir değer için x ve herhangi bir soyut değişken V, işlem dizisi { it(S, x); V ← pop(S)} eşdeğerdir V ← x.

Görevden beri V ← x, tanımı gereği, durumunu değiştiremez S, bu durum şunu ima eder: V ← pop(S) geri yükler S daha önce sahip olduğu duruma it(S, x). Bu koşuldan ve soyut değişkenlerin özelliklerinden, örneğin, dizinin

{ it(S, x); it(S, y); U ← pop(S); it(S, z); V ← pop(S); W ← pop(S) }

nerede x, y, ve z herhangi bir değerdir ve U, V, W çift ​​olarak farklı değişkenlerdir, eşdeğerdir

{ U ← y; V ← z; W ← x }

Burada, bir yığın örneğindeki işlemlerin, diğer yığınlar da dahil olmak üzere diğer herhangi bir ADT örneğinin durumunu değiştirmediği varsayılır; yani,

  • Herhangi bir değer için x, yve farklı yığınlar S ve T, sekans { it(S, x); it(T, y)}, { it(T, y); it(S, x) }.

Soyut bir yığın tanımı genellikle ayrıca bir Boole değerli işlev boş(S) ve a oluşturmak() aksiyomlara eşdeğer bir yığın örneği döndüren işlem

  • oluşturmak() ≠ S önceki herhangi bir yığın için S (yeni oluşturulan bir yığın, önceki tüm yığınlardan farklıdır);
  • boş(oluşturmak()) (yeni oluşturulan yığın boştur);
  • değil boş(it(S, x)) (bir şeyi bir yığına itmek, boş kalmamasını sağlar).

Tek örnekli stil

Bazen bir ADT, algoritmanın yürütülmesi sırasında yalnızca bir örneği varmış gibi tanımlanır ve tüm işlemler, açıkça belirtilmeyen bu örneğe uygulanır. Örneğin, yukarıdaki soyut yığın işlemlerle tanımlanmış olabilir it(x) ve pop(), üzerinde çalışan sadece mevcut yığın. Bu stildeki ADT tanımları, açık bir örnek parametresi (gibi) eklenerek ADT'nin birden fazla birlikte var olan örneğini kabul etmek için kolayca yeniden yazılabilir. S önceki örnekte) örtük örneği kullanan veya değiştiren her işleme.

Öte yandan, bazı ADT'ler birden fazla örnek varsayılmadan anlamlı bir şekilde tanımlanamaz. Bu, tek bir işlemin ADT'nin iki farklı örneğini parametre olarak aldığı durumdur. Bir örnek için, soyut yığının tanımını bir işlemle artırmayı düşünün karşılaştırmak(S, T) bu, yığınların S ve T aynı öğeleri aynı sırada içerir.

İşlevsel stil tanımı

Bir ADT'yi tanımlamanın başka bir yolu, ruhuna daha yakın fonksiyonel programlama, yapının her durumunu ayrı bir varlık olarak ele almaktır. Bu görünümde, ADT'yi değiştiren herhangi bir işlem, bir matematiksel fonksiyon bu, eski durumu bir argüman olarak alır ve sonucun bir parçası olarak yeni durumu döndürür. Zorunlu işlemlerin aksine, bu işlevlerin hiçbir yan etkiler. Bu nedenle, değerlendirildikleri sıra önemsizdir ve aynı argümanlara uygulanan aynı işlem (aynı giriş durumları dahil) her zaman aynı sonuçları (ve çıktı durumlarını) döndürür.

İşlevsel görünümde, özellikle, zorunlu değişkenlerin anlambilimine sahip bir "soyut değişken" tanımlamanın yolu (veya gerekliliği) yoktur (yani, getirmek ve mağaza operasyonlar). Değerleri değişkenlere depolamak yerine, bunları bağımsız değişkenler olarak işlevlere aktarırsınız.

Örnek: soyut yığın (işlevsel)

Örneğin, soyut bir yığının eksiksiz bir işlevsel stil tanımı şu üç işlemi kullanabilir:

  • it: bir yığın durumunu ve keyfi bir değeri alır, bir yığın durumu döndürür;
  • üst: yığın durumunu alır, bir değer döndürür;
  • pop: bir yığın durumunu alır, bir yığın durumu döndürür.

İşlevsel tarz tanımında, bir oluşturmak operasyon. Gerçekte, "yığın örneği" kavramı yoktur. Yığın durumları, tek bir yığın yapısının potansiyel durumları olarak düşünülebilir ve aynı sırayla aynı değerleri içeren iki yığın durumu özdeş durumlar olarak kabul edilir. Bu görüş aslında bazı somut uygulamaların davranışını yansıtır. bağlantılı listeler ile karma eksileri.

Onun yerine oluşturmak(), soyut bir yığının işlevsel stil tanımı, özel bir yığın durumunun varlığını varsayabilir, boş yığın, Λ veya "()" gibi özel bir sembolle gösterilir; veya tanımlayın alt() argüman almayan ve bu özel yığın durumunu döndüren işlem. Aksiyomların şu anlama geldiğine dikkat edin:

  • it(Λ, x) ≠ Λ.

Bir yığının işlevsel stil tanımında, birinin bir boş yüklem: bunun yerine, bir yığının boş olup olmadığını, Λ'ye eşit olup olmadığını test ederek test edebilir.

Bu aksiyomların şu etkiyi tanımlamadığına dikkat edin: üst(s) veya pop(s), sürece s tarafından döndürülen bir yığın durumudur it. Dan beri it yığını boş bırakmazsa, bu iki işlem tanımsızdır (dolayısıyla geçersizdir) s = Λ. Öte yandan, aksiyomlar (ve yan etkilerin olmaması) şu anlama gelir: it(s, x) = it(t, y) ancak ve ancak x = y ve s = t.

Matematiğin diğer bazı dallarında olduğu gibi, yığın durumlarının yalnızca varlıkları aksiyomlardan sınırlı sayıda adımda kanıtlanabilenler olduğunu varsaymak gelenekseldir. Yukarıdaki soyut yığın örneğinde, bu kural her yığının bir sonlu sonlu bir sayıdan sonra boş yığın (Λ) haline gelen değerler dizisi pops. Yukarıdaki aksiyomlar, kendi başlarına sonsuz yığınların varlığını dışlamaz ( popsonsuza kadar, her seferinde farklı bir durum ortaya çıkarır) veya dairesel yığınlar (sonlu bir sayıdan sonra aynı duruma geri döner) pops). Özellikle, devletleri dışlamazlar s öyle ki pop(s) = s veya it(s, x) = s bazı x. Bununla birlikte, verilen işlemlerle bu tür yığın durumları elde edilemeyeceğinden, bunların "olmadığı" varsayılır.

Karmaşıklığın dahil edilip edilmeyeceği

Aksiyomlar açısından davranışın yanı sıra, bir ADT işleminin tanımına bunların dahil edilmesi de mümkündür. algoritmik karmaşıklık. Alexander Stepanov, C ++ tasarımcısı Standart Şablon Kitaplığı, STL şartnamesine karmaşıklık garantilerini dahil ederek şunları tartışmaktadır:

Soyut veri türleri kavramını tanıtmanın nedeni, değiştirilebilir yazılım modüllerine izin vermekti. Bu modüller benzer karmaşıklık davranışını paylaşmadıkça değiştirilebilir modüllere sahip olamazsınız. Bir modülü aynı işlevsel davranışa sahip ancak farklı karmaşıklık ödünleşimlerine sahip başka bir modülle değiştirirsem, bu kodun kullanıcısı tatsız bir şekilde şaşıracaktır. Ona veri soyutlama hakkında sevdiğim her şeyi söyleyebilirim ve o yine de kodu kullanmak istemez. Karmaşıklık iddiaları arayüzün bir parçası olmalıdır.

— Alexander Stepanov[6]

Soyut veri yazmanın avantajları

Kapsülleme

Soyutlama ADT'nin herhangi bir uygulamasının belirli özelliklere ve yeteneklere sahip olduğuna dair bir söz verir; bunların bilinmesi, bir ADT nesnesini kullanmak için gereken her şeydir.

Değişimin yerelleştirilmesi

ADT'nin uygulaması değiştirilirse, bir ADT nesnesi kullanan kodun düzenlenmesi gerekmez. Uygulamadaki herhangi bir değişiklik yine de arayüzle uyumlu olması gerektiğinden ve bir ADT nesnesi kullanan kod yalnızca arayüzde belirtilen özelliklere ve yeteneklere başvurabileceğinden, ADT'nin kullanıldığı kodda herhangi bir değişiklik gerektirmeden uygulamada değişiklikler yapılabilir. .

Esneklik

Tüm aynı özelliklere ve yeteneklere sahip olan farklı ADT uygulamaları eşdeğerdir ve ADT'yi kullanan kodda bir şekilde birbirinin yerine kullanılabilir. Bu, farklı durumlarda ADT nesnelerini kullanırken büyük bir esneklik sağlar. Örneğin, ADT'nin farklı uygulamaları, farklı durumlarda daha verimli olabilir; her birinin tercih edildiği durumlarda kullanılması mümkündür, böylece genel verimlilik artar.

Tipik işlemler

Genellikle ADT'ler için belirtilen (muhtemelen başka isimler altında) bazı işlemler

  • karşılaştırmak(s, t), iki örneğin durumunun bir anlamda eşdeğer olup olmadığını test eden;
  • karma(s), bazı standartları hesaplayan Özet fonksiyonu örneğin durumundan;
  • Yazdır(s) veya göstermek(s), örneğin durumunun insan tarafından okunabilir bir temsilini üretir.

Zorunlu stil ADT tanımlarında, genellikle

  • oluşturmakADT'nin yeni bir örneğini veren ();
  • başlatmak(s), yeni oluşturulmuş bir örneği hazırlayan s daha ileri işlemler için veya onu bir "başlangıç ​​durumuna" sıfırlar;
  • kopya(s, t), örnek koyar s eşdeğer bir durumda t;
  • klon(t), performans s ← oluşturmak(), kopya(s, t) ve döner s;
  • Bedava(s) veya yok etmek(s) tarafından kullanılan bellek ve diğer kaynakları geri alan s.

Bedava ADT'ler "belleği kullanmayan" teorik varlıklar olduğundan işlem normalde alakalı veya anlamlı değildir. Ancak, ADT'yi kullanan bir algoritma tarafından kullanılan depolamanın analiz edilmesi gerektiğinde gerekli olabilir. Bu durumda, her bir ADT örneğinin durumunun bir işlevi olarak ne kadar bellek kullandığını ve ne kadarının havuza döndürüleceğini belirten ek aksiyomlara ihtiyaç vardır. Bedava.

Örnekler

Çok çeşitli uygulamalarda yararlı olduğu kanıtlanmış bazı yaygın ADT'ler,

Bu ADT'lerin her biri, eşdeğer olması gerekmeyen birçok şekilde ve varyantlarla tanımlanabilir. Örneğin, soyut bir yığın, bir Miktar kaç öğenin itildiğini ve henüz açılmadığını söyleyen işlem. Bu seçim sadece müşterileri için değil, uygulama açısından da fark yaratmaktadır.

Soyut grafik veri türü

1979'da bilgisayar grafikleri için ADT'nin bir uzantısı önerildi:[7] bir soyut grafik veri türü (AGDT). Tarafından tanıtıldı Nadia Magnenat Thalmann, ve Daniel Thalmann. AGDT'ler, yapısal bir şekilde grafiksel nesneler oluşturmak için tesislerle ADT'lerin avantajlarını sağlar.

Uygulama

Daha fazla bilgi: Opak veri türü

Bir ADT uygulamak, bir ADT sağlamak anlamına gelir prosedür veya işlev her soyut işlem için. ADT örnekleri bazı somut örneklerle temsil edilir veri yapısı ADT'nin spesifikasyonlarına göre bu prosedürler tarafından manipüle edilir.

Genellikle aynı ADT'yi birkaç farklı somut veri yapısı kullanarak uygulamanın birçok yolu vardır. Böylece, örneğin, bir soyut yığın, bir bağlantılı liste veya bir dizi.

İstemcilerin uygulamaya bağlı olmasını önlemek için, bir ADT genellikle bir opak veri türü bir veya daha fazla modüller, arayüzü yalnızca işlemlerin imzasını (parametrelerin ve sonuçların sayısı ve türü) içeren. Modülün uygulanması - yani prosedürlerin gövdeleri ve kullanılan somut veri yapısı - daha sonra modülün çoğu istemcisinden gizlenebilir. Bu, istemcileri etkilemeden uygulamayı değiştirmeyi mümkün kılar. Uygulama açığa çıkarsa, bunun yerine bir şeffaf veri türü.

Bir ADT uygularken, her örnek (zorunlu stil tanımlarında) veya her durum (işlevsel stil tanımlarında) genellikle bir üstesinden gelmek bir çeşit.[8]

Gibi modern nesne yönelimli diller C ++ ve Java, soyut veri türlerini destekler. Bir sınıf bir tür olarak kullanıldığında, gizli bir temsili ifade eden soyut bir türdür. Bu modelde bir ADT tipik olarak bir sınıf ve ADT'nin her bir örneği genellikle bir nesne o sınıfın. Modülün arayüzü tipik olarak oluşturucuları sıradan prosedürler olarak ve diğer ADT işlemlerinin çoğunu yöntemler o sınıfın. Bununla birlikte, böyle bir yaklaşım, bir ADT'de bulunan çoklu temsil varyantlarını kolayca kapsülleyemez. Ayrıca, nesne yönelimli programların genişletilebilirliğini zayıflatabilir. Arabirimleri tür olarak kullanan tamamen nesne yönelimli bir programda, türler temsiller değil davranışlara atıfta bulunur.

Örnek: soyut yığının uygulanması

Örnek olarak, yukarıdaki özet yığınının C programlama dili.

Zorunlu stil arayüz

Zorunlu stilde bir arayüz şöyle olabilir:

typedef yapı stack_Rep stack_Rep;       // tür: yığın örneği gösterimi (opak kayıt)typedef stack_Rep* stack_T;               // tür: bir yığın örneğini işle (opak işaretçi)typedef geçersiz* stack_Item;                 // tür: yığın örneğinde depolanan değer (rastgele adres)stack_T stack_create(geçersiz);               // yeni bir boş yığın örneği oluştururgeçersiz stack_push(stack_T s, stack_Item x); // yığının en üstüne bir öğe eklerstack_Item stack_pop(stack_T s);          // yığından en üstteki öğeyi kaldırır ve onu döndürürbool stack_empty(stack_T s);              // yığının boş olup olmadığını kontrol eder

Bu arayüz aşağıdaki şekilde kullanılabilir:

#Dahil etmek  // yığın arayüzünü içerirstack_T s = stack_create(); // yeni bir boş yığın örneği oluştururint x = 17;stack_push(s, &x);          // yığının en üstüne x'in adresini eklergeçersiz* y = stack_pop(s);     // x'in adresini yığından kaldırır ve onu döndürürEğer (stack_empty(s)) { }     // yığın boşsa bir şeyler yapar

Bu arayüz pek çok şekilde uygulanabilir. Yukarıdaki ADT'nin resmi tanımı yığının ne kadar alan kullanabileceğini veya her bir işlemin ne kadar süreceğini belirtmediğinden, uygulama keyfi olarak verimsiz olabilir. Ayrıca, yığın durumunun s bir aramadan sonra var olmaya devam ediyor x ← pop(s).

Uygulamada resmi tanım, boşluğun itilen ve henüz atılmamış öğelerin sayısıyla orantılı olduğunu belirtmelidir; ve yukarıdaki işlemlerin her biri, bu sayıdan bağımsız olarak sabit bir süre içinde bitmelidir. Bu ek spesifikasyonlara uymak için, uygulama bağlantılı bir liste veya iki tamsayı (bir öğe sayısı ve dizi boyutu) ile birlikte bir dizi (dinamik yeniden boyutlandırma ile) kullanabilir.

İşlevsel tarzda arayüz

İşlevsel stil ADT tanımları, işlevsel programlama dilleri için daha uygundur ve bunun tersi de geçerlidir. Bununla birlikte, C gibi zorunlu bir dilde bile işlevsel tarzda bir arayüz sağlanabilir. Örneğin:

typedef yapı stack_Rep stack_Rep;          // tür: yığın durumu gösterimi (opak kayıt)typedef stack_Rep* stack_T;                  // tür: bir yığın durumuna işlemek (opak işaretçi)typedef geçersiz* stack_Item;                    // tür: yığın durumunun değeri (isteğe bağlı adres)stack_T stack_empty(geçersiz);                   // boş yığın durumunu döndürürstack_T stack_push(stack_T s, stack_Item x); // yığın durumunun en üstüne bir öğe ekler ve oluşan yığın durumunu döndürürstack_T stack_pop(stack_T s);                // en üstteki öğeyi yığın durumundan kaldırır ve sonuçta oluşan yığın durumunu döndürürstack_Item stack_top(stack_T s);             // yığın durumunun en üst öğesini döndürür

ADT kitaplıkları

C ++ ve Java gibi birçok modern programlama dili, yukarıda listelenenler gibi birkaç yaygın ADT'yi uygulayan standart kitaplıklarla birlikte gelir.

Yerleşik soyut veri türleri

Bazı programlama dillerinin özellikleri, belirli yerleşik veri türlerinin gösterimi konusunda kasıtlı olarak belirsizdir ve yalnızca bunlar üzerinde yapılabilecek işlemleri tanımlar. Bu nedenle, bu türler "yerleşik ADT'ler" olarak görülebilir. Örnekler, birçok komut dosyası dilindeki dizilerdir, örneğin Awk, Lua, ve Perl Özet listesinin bir uygulaması olarak kabul edilebilir.

Ayrıca bakınız

Notlar

  1. ^ Soyut cebirde tam sayıların karakterizasyonu ile karşılaştırın.

Alıntılar

  1. ^ Dale ve Walker 1996, s. 3.
  2. ^ Dale ve Walker 1996, s. 4.
  3. ^ Liskov ve Zilles 1974.
  4. ^ Rudolf Lidl (2004). Soyut Cebir. Springer. ISBN  978-81-8128-149-4.Bölüm 7, kısım 40.
  5. ^ "Nesne Tabanlı Programlama Nedir?". İşe Alma | Upwork. 2015-05-05. Alındı 2016-10-28.
  6. ^ Stevens, Al (Mart 1995). "Al Stevens, Alex Stepanov ile Röportaj". Dr. Dobb's Journal. Alındı 31 Ocak 2015.
  7. ^ D. Thalmann, N. Magnenat Thalmann (1979). Soyut Grafik Veri Türlerinin Tasarımı ve Uygulanması. IEEE. doi:10.1109 / CMPSAC.1979.762551., Proc. 3. Uluslararası Bilgisayar Yazılımları ve Uygulamaları Konferansı (COMPSAC'79), IEEE, Chicago, ABD, s.519-524
  8. ^ Robert Sedgewick (1998). C Algoritmalar. Addison / Wesley. ISBN  978-0-201-31452-6., tanım 4.4.

Referanslar

  • Liskov, Barbara; Zilles, Stephen (1974). "Soyut veri türleri ile programlama". ACM SIGPLAN Çok Üst Düzey Diller Sempozyumu Bildirileri. SİGPLAN Bildirimleri. 9. sayfa 50–59. CiteSeerX  10.1.1.136.3043. doi:10.1145/800233.807045.CS1 bakimi: ref = harv (bağlantı)
  • Dale, Nell; Walker, Henry M. (1996). Soyut Veri Türleri: Spesifikasyonlar, Uygulamalar ve Uygulamalar. Jones & Bartlett Öğrenimi. ISBN  978-0-66940000-7.CS1 bakimi: ref = harv (bağlantı)

daha fazla okuma

Dış bağlantılar