Soyut veri türü "liste". soyut veri türü veri genellikleri soyut

C++ dili, temel C dili türlerine benzer şekilde davranan veri türleri oluşturmanıza olanak tanır. Bu türler genellikle denir soyut veri türleri(ATD).
ADT'yi C dilinde uygulamak için yapılar kullanılır. Ama veri kullanımı yapısal tip kullanımına kıyasla önemli ölçüde sınırlı baz türleri veri. Örneğin, yapısal veriler çeşitli işlemlerde (toplama, çıkarma) işlenen olarak kullanılamaz. Bu tür verileri işlemek için, çeşitli eylemleri gerçekleştiren bir dizi işlev yazmanız ve işlemler yerine bu işlevleri çağırmanız gerekir.

Ek olarak, yapının elemanları hiçbir şekilde kazara değiştirilmeye karşı korunmaz. Yani, herhangi bir işlev (yapısal verileri işlemek için kullanılan araçlar kümesinden olmasa bile) bir yapı öğesine atıfta bulunabilir. Bu, nesne yönelimli programlamanın ana ilkelerinden birine aykırıdır - veri kapsülleme: dışında başka işlev yoktur. özel fonksiyonlar bu veri türündeki manipülasyonların veri üyelerine erişimi olmamalıdır.

Tarih kavramının bir gösterimini tanımlamak için bir yapı ve bu tür değişkenlerle çalışmak için bir dizi işlev kullanarak tarih kavramının uygulanmasını düşünün:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#katmak
yapı tarihi
{
int ay; // ay
gün; // gün
yıl; // yıl
};
geçersiz set_date(tarih* f, int d, int m, int y)
{
f->gün = gün;
f->ay = m;
f->yıl = y;
}
geçersiz print_date(tarih*f)
{
printf("%d.%d.%d" , f->gün, f->ay, f->yıl);
}
int ana()
{
bugün tarih;
set_date(&bugün, 2, 4, 2014);
print_date(&bugün);
getchar();
0 dönüşü;
}

Bu örnekte işlevler ve veri türü arasında açık bir ilişki yoktur. Açıklanan işlevlerden herhangi birini çağırmak için, yapının bir örneğine argüman olarak bir işaretçi iletmeniz gerekir.

Böyle bir ilişki, işlevleri bir yapının üyeleri olarak tanımlayarak kurulabilir. Bu işlevler, yapının kendisinde bulunan veriler üzerinde hareket edebilir.
Varsayılan olarak, bir yapı bildirildiğinde, verileri ve işlevleri paylaşılır, yani yapı türündeki nesnelerin ne kapsülleme ne de veri koruması vardır:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#katmak
yapı tarihi
{
int ay; // ay
gün; // gün
yıl; // yıl
geçersiz set_date(int d, int m, int y)
{
gün=d; ay=ay; yıl=y;
}
geçersiz baskı_tarihi(geçersiz);
};
geçersiz tarih::print_date(void )
{
printf("%d.%d.%d" , gün, ay, yil);
}
int ana()
{
bugün tarih;
bugün.set_date(2, 4, 2014);
bugün.print_date();
getchar();
0 dönüşü;
}

Üye işlevler ve veri üyeleri

Vücutta açıklanan işlevler soyut tip veriler, üye işlevler veya yöntemlerdir ve üye verilere veya yapı alanlarına erişim için standart sözdizimi kullanılarak yalnızca uygun türdeki özel bir değişkende çağrılabilir.

Üye işlevler iki şekilde tanımlanabilir:

• doğrudan yapının açıklamasında işlevin açıklaması;
• yapının dışındaki işlevin açıklaması.

Bir yapı içinde tanımlanan üye işlevler dolaylı olarak satır içidir ( ). Genel bir kural olarak, bir yapı içinde yalnızca kısa, sık kullanılan üye işlevler tanımlanmalıdır:

geçersiz küme(int m, int d, int y) (ay = m; gün = d; yıl = y;);

• tipüye işlevinin dönüş türüdür
• ATD— soyut veri türünün adı (yapı veya sınıf adı)
• İsim- üye işlev adı

geçersiz tarih::print_date(void )
( printf("%d.%d.%d" ,gün, ay, yil);)

Bir üye işlevinde, üye adları açık bir nesne başvurusu olmadan kullanılabilir. Bu durumda ad, işlevin çağrıldığı nesnenin üyesini ifade eder.

Aynı yapının üye fonksiyonları polimorfik, yani aşırı yüklenmiş olabilir.

Erişim hakları

C++'daki bir yapı kavramı (C'den farklı olarak), bir yapının üyelerinin genel, özel veya korumalı olmasına izin verir:

• genel - genel;
• özel - özel;
• korumalı - korumalı.

Kullanım anahtar kelime Korumalı, miras kavramıyla ilgilidir.

private anahtar sözcüğünü kullanmak, bu yapıyı izleyen üyelere erişimi kısıtlar. Özel üyeler, yalnızca bu üyelere erişim ayrıcalıklarına sahip birkaç işlev kategorisi tarafından kullanılabilir. Temelde aynı yapının üye fonksiyonlarıdır.
public anahtar sözcüğü, bir yapı nesnesine bir arabirim oluşturur.

Soyut bir veri türünün üye verilerini özel bir alana ( private ) ve üye işlevlerin bazılarını - public bölümüne ( public ) yerleştirmek standarttır. Bu durumda, özel (özel) kısım, nesnenin veri ve yardımcı fonksiyonlarını tanımlar ve genel kısmın üye fonksiyonları, nesne ile çalışmak için yöntemler uygular.

Veri gösterimini (veri kapsülleme) gizlemek için tarih yapısını değiştirelim:

1
2
3
4
5
6
7
8

yapı tarihi
{
özel :
int ay, gün, yıl;
halk :
geçersiz küme(int, int, int);
geçersiz baskı();
};

Veriler için soyut modellerin geliştirilmesi ve bu verilerin işlenme yolları temel bileşen bilgisayar kullanarak problem çözme sürecinde. Bunun örneklerini hem günlük programlamada düşük düzeyde (örneğin, içinde tartışılan dizileri ve bağlantılı listeleri kullanırken) hem de çözerken yüksek düzeyde görüyoruz. uygulamalı görevler("Giriş" bölümündeki birleştirme arama ormanını kullanarak bağlantı sorununu çözerken olduğu gibi). Bu ders, üst düzey soyutlamalar kullanarak programlar oluşturmanıza izin veren soyut veri türlerini (bundan böyle ADT olarak anılacaktır) tartışır. Soyut veri türleri, programların veriler üzerinde gerçekleştirdiği soyut (kavramsal) dönüşümleri, bir veri yapısının herhangi bir özel temsilinden ve bir algoritmanın herhangi bir özel uygulamasından ayırmanıza olanak tanır.

Tüm bilgi işlem sistemleri soyutlama seviyelerine dayalı olarak: silikonun ve diğer malzemelerin belirli fiziksel özellikleri, 0-1 ikili değerlerini alabilen soyut bir bit modelinin benimsenmesine izin verir; daha sonra, belirli bir bit kümesinin değerlerinin dinamik özellikleri üzerine makinenin soyut bir modeli oluşturulur; ayrıca, makinenin makine dilinde bir programın kontrolü altında çalışması ilkesine dayanarak, programlama dilinin soyut bir modeli oluşturulur; ve son olarak, bir C++ programı olarak uygulanan soyut bir algoritma kavramı oluşturulur. Soyut veri türleri, bu süreci daha da ileriye götürmeyi ve belirli hesaplama görevleri için C ++ sisteminin sağladığından daha yüksek düzeyde soyut mekanizmalar geliştirmeyi mümkün kılar. özel uygulamalar ve çok sayıda uygulama alanındaki sorunları çözmek için uygun olduğu kadar, daha fazlası için soyut mekanizmalar oluşturmak için uygundur. yüksek seviye bu temel yapıları kullananlar. Soyut veri türleri, bize giderek daha fazla yeni sorunu çözmek için sonsuz genişletilebilir bir araç seti sağlar.

Bir yandan, soyut yapıların kullanılması, kişiyi ayrıntılı uygulamalarıyla ilgili endişelerden kurtarır; Öte yandan, ne zaman verim program önemlidir, temel işlemleri gerçekleştirmenin maliyetlerini bilmeniz gerekir. Yerleşik birçok temel soyutlama kullanıyoruz. donanım bilgisayar ve makine talimatları için temel olarak hizmet eden; yazılımda diğer soyutlamaları uygulamak; ve önceden yazılmış sistem yazılımı tarafından sağlanan ek soyutlamaları kullanın. Üst düzey soyut yapılar genellikle daha basit yapılara dayanır. Tüm seviyelerde aynı temel ilke geçerlidir: programlardaki en önemli işlemleri ve en önemli işlemleri bulmanız gerekir. önemli özellikler verileri ve ardından hem soyut düzeyde kesin olarak tanımlamak hem de bunların uygulanması için etkili somut mekanizmalar geliştirmek. Bu derste, bu prensibin uygulanmasına ilişkin birçok örneğe bakacağız.

Yeni bir soyutlama düzeyi geliştirmek, (1) manipüle edilecek soyut nesnelerin ve bunlar üzerinde gerçekleştirilecek işlemlerin tanımlanmasını; (2) verileri bazı veri yapılarında temsil eder ve işlemleri uygular; (3) ve (en önemlisi) bu nesnelerin uygulamalı problemleri çözmek için kullanıma uygun olmasını sağlamak. Bu noktalar basit veri türleri için de geçerlidir, bu nedenle "Temel Veri Yapıları" kapsamında ele alınan veri türlerini desteklemek için temel mekanizmalar amaçlarımız için uyarlanabilir. Bununla birlikte, C++ dili, sınıf adı verilen yapı mekanizmasının önemli bir uzantısını sunar. Sınıflar, soyutlama katmanları oluşturmada son derece faydalıdır ve bu nedenle kitabın geri kalanında bu amaç için kullanılan ana araç olarak ele alınır.

Tanım 4.1. Soyut veri türü (ATD), yalnızca bir arabirim aracılığıyla erişilen bir veri türüdür (bir dizi değer ve bu değerler üzerinde bir dizi işlem). ADT'yi kullanan programa istemci adı verilir ve bu veri türünün özelliklerini içeren programa uygulama adı verilir.

Yalnızca veri türünü soyut yapan kelimedir: ADT söz konusu olduğunda, istemci programların arayüzde açıklanan işlemler dışında hiçbir şekilde veri değerlerine erişimi yoktur. Bu verilerin temsili ve bu işlemleri gerçekleştiren işlevler uygulamadadır ve istemciden bir arabirimle tamamen ayrılmıştır. Arabirimin opak olduğunu söylüyoruz: istemci arabirim aracılığıyla uygulamayı göremez.

C++ programlarında, bu ayrım genellikle biraz daha net yapılır, çünkü en kolay arabirimi dahil ederek oluşturmaktır. veri sunumu, ancak istemci programlarının verilere doğrudan erişimine izin verilmediğini belirtmek. Başka bir deyişle, müşteri geliştiricileri bilebilir veri sunumu, ancak hiçbir şekilde kullanamazsınız.

Örnek olarak, Bölüm 3.1 "Temel Veri Yapıları"ndaki noktalar için veri tipi arayüzünü (Program 3.3) ele alalım. Bu arabirim, noktaların, x ve y ile gösterilen bir çift kayan nokta sayısından oluşan yapılar olarak temsil edildiğini açıkça beyan eder. Veri türlerinin bu şekilde kullanılması büyük sistemlerde yaygındır. yazılım: Bir dizi veri temsil kuralı geliştiriyoruz (aynı zamanda bir dizi ilgili işlem tanımlıyoruz) ve bu kuralları, büyük bir sistemin parçası olan istemci programları tarafından kullanılabilmeleri için bir arabirim aracılığıyla kullanılabilir hale getiriyoruz. Veri türü, sistemin tüm bölümlerinin, temel sistem çapındaki veri yapılarının temsiliyle tutarlı olmasını sağlar. Bu strateji ne kadar iyi olursa olsun, bir dezavantajı var: eğer değiştirmek gerekirse veri sunumu, tüm istemci programlarını değiştirmeniz gerekecektir. Program 3.3 bize yine basit bir örnek veriyor: bu veri türünü geliştirmenin nedenlerinden biri, noktalarla çalışan müşteri programlarının rahatlığıdır ve gerekirse müşterilerin bir noktanın bireysel koordinatlarına erişmesini bekliyoruz. Ancak, tüm istemci programlarını değiştirmeden farklı bir veri temsiline (örneğin, kutupsal koordinatlar veya 3B koordinatlar veya hatta bireysel koordinatlar için diğer veri türleri) geçemeyiz.

Bunun tersine, Program 4.1, Program 3.3'teki veri türüne karşılık gelen, ancak aynı anda hem verileri hem de ilişkili işlemleri tanımlayan bir C++ dil sınıfını kullanan soyut bir veri türünün bir uygulamasını içerir. Program 4.2, bu veri türüyle çalışan bir istemci programıdır. Bu iki program, 3.3 ve 3.8 programları ile aynı hesaplamaları gerçekleştirir. Şimdi ele alacağımız sınıfların bir dizi ana özelliğini gösteriyorlar.

Bir programda int i gibi bir tanım yazdığımızda, sisteme i olarak ifade edilebilecek (yerleşik) int tipindeki veriler için bir bellek alanı ayırmasını söyleriz. C++ dili, bu tür varlıklar için nesne terimine sahiptir. Bir programda POINT p gibi bir tanım yazıldığında, POINT sınıfından p adıyla anılabilecek bir nesne yaratıldığı söylenir. Örneğimizde, her nesne x ve y adlı iki veri öğesi içerir. Yapılarda olduğu gibi, p.y. gibi isimlerle anılabilirler.

X ve y veri üyeleri, sınıfın veri üyeleri olarak adlandırılır. Sınıf ayrıca, bu veri türüyle ilişkili işlemleri uygulayan üye işlevleri de tanımlayabilir. Örneğin, Program 4.1'de tanımlanan sınıfın, NOKTA ve mesafe adlı iki üye işlevi vardır.

Program 4.2 gibi istemci programları, bazı yapı yapılarında bulunan verilerin adlarıyla aynı şekilde adlarını belirterek bir nesneyle ilişkili üye işlevleri çağırabilir. Örneğin, p.distance(q) ifadesi p ve q noktaları arasındaki mesafeyi hesaplar (aynı mesafe q.distance(p) çağrılarak döndürülmelidir). Program 4.1'deki ilk işlev olan POINT() işlevi, yapıcı adı verilen özel bir üye işlevdir: bir sınıfla aynı ada sahiptir ve o sınıftan bir nesnenin yaratılması gerektiğinde çağrılır.

Program 4.1. POINT (nokta) sınıfının uygulanması

Bu sınıf, "kayan noktalı sayı çiftleri" (Kartezyen düzlemdeki noktalar olarak yorumlandıkları varsayılarak) olan bir dizi değerden ve ayrıca POINT'in tüm örnekleri için tanımlanan iki üye fonksiyondan oluşan bir veri tipini tanımlar. class: 0'dan 1'e kadar rasgele değerlerle koordinatları başlatan bir yapıcı olan POINT() işlevi ve başka bir noktaya olan mesafeyi hesaplayan bir mesafe(POINT) işlevi. Temsili veriözeldir ve yalnızca üye işlevler ona erişebilir veya değiştirebilir. Üye işlevlerinin kendileri herkese açıktır (kamuya açık) ve herhangi bir müşteri tarafından kullanılabilir. Kod, örneğin POINT .cxx adlı bir dosyaya kaydedilebilir.

#katmak class POINT ( özel: float x, y; public: POINT() ( x = 1.0*Rand()/RAND_MAX; y = 1.0*Rand()/RAND_MAX; ) float Distance(POINT a) ( float dx = x-a.x dy = y-a.y; dönüş sqrt(dx*dx + dy*dy); ) );

Program 4.2. POINT sınıfı için istemci programı (en yakın noktayı bulma)

3.8 programının bu sürümü, program 4.3'te tanımlanan POINT ADT'yi kullanan bir istemcidir. Yeni işlem, bir POINT nesneleri dizisi oluşturur (her nesneyi rasgele koordinat değerleri ile başlatmak için POINT() yapıcısını çağırarak). a[i].distance(a[j]) ifadesi, a[j] bağımsız değişkeniyle a[i] nesnesindeki üye işlev mesafesini çağırır.

#katmak #katmak #include "POINT.cxx" int main(int argc, char *argv) ( float d = atof(argv); int i, cnt = 0, N = atoi(argv); NOKTA *a = yeni NOKTA[N]); için (i = 0; ben< N; i++) for (int j = i+1; j < N; j++) if (a[i].distance(a[j]) < d) cnt+ + ; cout << cnt << " пар в радиусе " << d << endl; }

İstemci programında POINT p'nin tanımlanması, yeni bir nesne için bir bellek alanı tahsis edilmesi ve ardından (POINT() işlevi kullanılarak) iki veri öğesinin her birine 0 ila 1 aralığında rasgele bir değer atanmasıyla sonuçlanır.

Bazen nesne yönelimli programlama olarak adlandırılan bu programlama tarzı, C++ sınıfı yapısı tarafından tamamen desteklenir. Bir sınıf, yalnızca verilerin birleştirildiği değil, aynı zamanda bu veriler üzerindeki işlemlerin tanımlandığı yapı kavramının bir uzantısı olarak düşünülebilir. Aynı sınıfa ait birçok farklı nesne olabilir, ancak veri üyelerinin aynı değerler kümesini alabilmeleri ve bu veri üyeleri üzerinde aynı işlemler kümesinin gerçekleştirilebilmesi açısından hepsi benzerdir - genel olarak bunlar aynı veri türünün örnekleri. Nesne yönelimli programlamada nesneler, veri üyelerini işlemek için tasarlanır (nesnelerde depolanan verileri işlemek için bağımsız işlevleri kullanmanın aksine).

Sınıfların temel özelliklerine aşina olmak için yukarıda açıklanan küçük bir sınıf örneğine bakıyoruz; bu yüzden tam olmaktan uzaktır. Puan sınıfı için gerçek kodda, daha birçok işlemimiz olacak. Örneğin program 4.1'de x ve y koordinatlarının değerlerini bulmanızı sağlayan işlemler bile yok. Göreceğimiz gibi, bunları ve diğer işlemleri eklemek oldukça basit bir iştir. 5. Bölümde, noktalar için sınıflara ve çizgiler ve çokgenler gibi diğer geometrik soyutlamalara daha yakından bakacağız.

C++'da (ancak C'de değil), yapıların kendileriyle ilişkilendirilmiş işlevleri de olabilir. Sınıflar ve yapılar arasındaki temel fark, anahtar sözcüklerle karakterize edilen bilgiye erişimle ilgilidir.

İyi günler, habravchane!

Aşağıdaki gönderi, sınıfların ve ADT'lerin doğası hakkındaki düşüncelerimin bir özetidir. Bu düşünceler, yazılım geliştirme gurularının kitaplarından ilginç alıntılarla tamamlanmaktadır.

giriiş

Soyutlama, kavramsal sınırlarını tanımlayan ve onları diğer tüm nesne türlerinden ayıran ortak özelliklere sahip bir dizi nesnenin seçilmesi ve verilmesidir.
Başka bir deyişle, soyutlama, ihtiyacımız olan nesne verilerine "ışık tutmamıza" ve aynı zamanda bizim için önemli olmayan verileri "gizlememize" olanak tanır.

Peki “data type” ve “abstraction” kavramlarını birleştirirsek ne olur? Bize bu veri türündeki nesnelerin davranışını sağlayan bir dizi işlem sağlayan bir veri türü alacağız ve bu veri türü, bu davranışın uygulandığı verileri de gizleyecektir. Buradan ATD kavramına geliyoruz:

ADT, dahili uygulamasını istemcilerden gizleyen bir veri türüdür.
Şaşırtıcı olan şey, ADT'nin soyutlamayı uygulayarak, alt düzey uygulama ayrıntılarını düşünmemize değil, gerçek dünyanın üst düzey bir varlığıyla (Steve McConnell) çalışmamıza izin vermesidir.

Bir ADT tasarlarken, bir arayüzün bir ADT'deki verilerin dahili temsiline bağlı olmaması gerektiğinden, önce bir arayüz tanımlamanız gerektiğine inanıyorum. Arayüzü oluşturan işlemleri tanımladıktan sonra, ADT'nin belirtilen davranışını uygulayacak verilere odaklanmanız gerekir. Sonuç olarak, belirli bir veri yapısı elde ederiz - verileri depolamanıza ve işlemenize izin veren bir mekanizma. Aynı zamanda, ADT'nin güzelliği şu ki, verilerin dahili temsilini değiştirmek istiyorsak, tüm program boyunca dolaşmak ve değiştirmek istediğimiz verilere bağlı olan her kod satırını değiştirmek zorunda değiliz. ADT, tüm program yerine bu türdeki nesnelerin davranışını değiştirmenize izin veren bu verileri kapsar.

ATD'nin Faydaları

Bir ADT kullanmanın birçok avantajı vardır (açıklanan tüm avantajlar Steve McConnell'in Code Perfect'inde bulunabilir):

• Uygulama ayrıntılarının kapsüllenmesi.
  Bu, ADT'nin nasıl çalıştığına ilişkin uygulama ayrıntılarını özetledikten sonra, müşteriye ADT ile etkileşim kurabileceği bir arayüz sağladığımız anlamına gelir. Uygulamanın ayrıntıları değiştirildiğinde, müşterinin ADT'nin işleyişine ilişkin görüşü değişmeyecektir.

• Azaltılmış karmaşıklık
  Uygulama detaylarından soyutlayarak, arayüze, yani bir ADT'nin nasıl yapıldığından çok neler yapabileceğine odaklanıyoruz. Ayrıca ADT, gerçek dünyanın özüyle çalışmamızı sağlar.

• Veri kullanımının kapsamının sınırlandırılması.
  Bir ADT kullanarak, bir ADT'nin iç yapısını temsil eden verilerin kodun diğer bölümlerine bağlı olmayacağından emin olabiliriz. Bu durumda, ADT'nin “bağımsızlığı” gerçekleşir.

• Arayüzün yüksek bilgi içeriği.
  ADT, arayüzün okunabilirliğini ve bilgilendiriciliğini artıran konu alanındaki varlıklar açısından tüm arayüzü temsil etmenize izin verir.

Steve McConnell, yığın veya liste gibi düşük seviyeli veri türlerinin ADT olarak temsil edilmesini önerir. Kendinize bu listenin ne olduğunu sorun. Bir banka çalışanlarının listesini temsil ediyorsa, ADT'yi banka çalışanlarının bir listesi olarak ele alın.

Böylece ATD'nin ne olduğunu anladık ve kullanımının avantajlarını aradık. Şimdi, OOP'de sınıflar geliştirirken, her şeyden önce ADT hakkında düşünmeniz gerektiğini belirtmekte fayda var. Bununla birlikte, Steve McConnell'in dediği gibi, bir dilde programlamazsınız, bir dille programlama yaparsınız. Yani, diziler veya basit veri türleri açısından düşüncelerle sınırlı kalmadan, dilin ötesinde programlama yapacaksınız. Bunun yerine, yüksek düzeyde soyutlama açısından düşüneceksiniz (örneğin, elektronik tablolar veya çalışan listeleri açısından). Bir sınıf, bir eklemeden ve bir ADT kavramını uygulamanın bir yolundan başka bir şey değildir. Sınıfı bir formül olarak bile temsil edebiliriz:
Sınıf = ATD + Kalıtım + Polimorfizm.
Öyleyse sınıfları tasarlarken neden ADT'leri düşünmelisiniz? Çünkü, öncelikle hangi işlemlerin gelecekteki sınıfın arayüzünü oluşturacağına, hangi verileri saklayacağımıza ve hangilerine genel erişim sağlayacağımıza karar vermeliyiz. Arayüzü oldukça bilgilendirici hale getirmeyi, kodu optimize etmeyi ve test etmeyi kolaylaştırmayı ve doğru soyutlamayı nasıl sağlayabileceğimizi düşünmemiz gerekiyor, böylece düşük seviyeli uygulama detayları yerine gerçek dünya varlıkları hakkında düşünebiliriz. Kalıtım ve polimorfizm konularını ADT'nin tanımından sonra düşünmemiz gerektiğine inanıyorum.

ADT konseptinin OOP'de geniş bir uygulama bulduğunu belirtmekte fayda var, çünkü OOP'yi tamamlayan ve hızla değişen yazılım gereksinimleri dünyasında programların karmaşıklığını azaltmanıza izin veren bu kavramdır.

Bu makaleyi geliştiricilerin dikkatini ATD'ye çekmek, iş kalitesini artırmak ve yazılım geliştirmek için yazdım.

Kullanılan kaynaklar:

Steve McConnell - "Mükemmel Kod";
Robert Sedgwick - Java'daki Algoritmalar.

1.2. Soyut veri türleri

Önceki bölümde tanıtılan kavramların çoğu genellikle bir programlamaya giriş kursunda öğretilir ve size aşina olmalıdır. Yalnızca soyut veri türleri yeni olabilir, bu yüzden önce yazılım geliştirme sürecindeki rollerini tartışalım. İlk olarak, soyut bir veri türünü bilinen bir prosedür kavramıyla karşılaştıralım.

Temel bir programlama aracı olan bir prosedür, genelleştirilmiş bir operatör kavramı olarak düşünülebilir. Yetenekleri (toplama, çarpma vb.) sınırlı olan bir programlama dilinin yerleşik işleçlerinden farklı olarak, bir programcı prosedürleri kullanarak kendi işleçlerini oluşturabilir ve bunları yalnızca temel olanlara değil, çeşitli türlerdeki işlenenlere uygulayabilir. Böyle bir prosedür operatörünün bir örneği, matris çarpımının standart alt programıdır.

Yordamların bir başka avantajı da (yeni ifadeler oluşturma yeteneği dışında), kapsülleme programın işleyişinin belirli bir yönünden sorumlu tüm operatörleri programın ayrı bir bölümüne yerleştirerek algoritmanın parçaları. Kapsülleme örneği: Herhangi bir türden girişi okumak ve doğrulamak için tek bir prosedür kullanmak. Kapsüllemenin avantajı, programın işleyişinde sorun olması durumunda hangi kapsüllenmiş ifadelerin değiştirilmesi gerektiğini bilmemizdir. Örneğin, pozitif değerler için giriş verilerinin bir kontrolünü düzenlemek gerekirse, yalnızca birkaç kod satırını değiştirmemiz gerekir ve bu satırların tam olarak nerede olduğunu biliriz.

Soyut bir veri türü tanımlama

biz tanımlarız soyut veri türü(ATD), bu model içinde tanımlanan bir dizi işleç ile matematiksel bir model olarak. Bir ADT'nin basit bir örneği, birleştirme, kesişme ve küme farkı işleçlerine sahip tamsayı kümeleri olabilir. ADT modelinde operatörler, işlenenler olarak yalnızca ADT tarafından tanımlanan verilere değil, aynı zamanda diğer türlerdeki verilere de sahip olabilir: programlama dilinin standart türleri veya diğer ADT'lerde tanımlananlar. Bir operatör eyleminin sonucu, verilen ADT modelinde tanımlananlardan farklı bir türde olabilir. Ancak, herhangi bir operatörün en az bir işleneninin veya sonucunun, söz konusu ADT modelinde tanımlanmış bir veri tipine sahip olduğunu varsayıyoruz.

Yukarıda tartışılan prosedürlerin iki göze çarpan özelliği, genelleştirme ve kapsülleme, soyut veri türlerinin mükemmel tanımlarıdır. Nasıl bir prosedür basit işleçlerin (+, -, vb.) genelleştirilmesiyse, ADT de basit veri türlerinin (tamsayılar, gerçek sayılar, vb.) Bir ADT, veri türlerini, tür tanımının ve o türdeki veriler üzerinde gerçekleştirilebilecek tüm işleçlerin programın bir bölümüne yerleştirilmesi anlamında kapsüller. Bir ADT'nin uygulanmasını değiştirmek gerekirse, programın küçük bir bölümünde nerede bulacağımızı ve neyi değiştireceğimizi biliyoruz ve bunun, bu verilerle çalışırken programın herhangi bir yerinde hatalara yol açmayacağından emin olabiliriz. tip. Ayrıca, ADT işleçlerini tanımlama bölümü dışında, ADT türlerini birincil türler olarak kabul edebiliriz, çünkü tür bildirimleri resmi olarak bunların uygulanmasıyla ilgili değildir. Ancak bu durumda, bazı ifadeler birden fazla ADT için başlatılabileceğinden ve bu ifadelere yapılan atıfların birkaç ADT'nin bölümlerinde olması gerektiğinden, komplikasyonlar ortaya çıkabilir.

Bir ADT'nin yaratılmasına yol açan temel fikirleri göstermek için, soyut LIST (tamsayılar listesi) veri türündeki veriler üzerinde basit işleçler kullanan önceki bölümdeki (liste 1.3) prosedürü açgözlü olarak düşünün. Bu işleçler, LIST türündeki newclr değişkeninde aşağıdaki eylemleri gerçekleştirmelidir.

1. Listeyi boşaltın.

2. Listenin ilk öğesini seçin ve liste boşsa değeri döndürün hükümsüz.

3. Listenin bir sonraki öğesini seçin ve değeri döndürün hükümsüz, sonraki öğe yoksa.

4. Listeye bir tam sayı girin.

Açıklanan eylemleri etkili bir şekilde gerçekleştirebileceğiniz çeşitli veri yapılarını kullanmak mümkündür. (Veri yapılarını Konu 2'de ayrıntılı olarak tartışacağız.) Liste 1.3'te karşılık gelen operatörleri ifadelerle değiştirirsek

MAKENULL(newcJr);

w:= İLK(yenicJr);

w:= SONRAKİ(yenicfr);

INSERT(v, yeniclr);

o zaman soyut veri türlerinin ana yönlerinden (ve avantajlarından) biri netleşecektir. Bir veri türünü herhangi bir şekilde uygulayabilirsiniz ve bu türdeki nesneleri kullanan programlar, türün nasıl uygulandığına bağlı değildir - bundan, bu veri türü için işleçleri uygulayan prosedürler sorumludur.

Soyut veri türü olan GRAPH'a (Graph) dönelim. Bu türdeki nesneler, aşağıdaki eylemleri gerçekleştiren işleçler gerektirir.

1. İlk boyanmamış tepe noktasını seçin.

2. İki köşe arasında bir kenar olup olmadığını kontrol edin.

3. Üst kısmı bir renkle işaretleyin.

4. Bir sonraki boyanmamış köşeyi seçin.

Açıkçası, bir grafiğe köşeler ve kenarlar eklemek veya bir grafiğin tüm köşelerini doldurulmamış olarak işaretlemek gibi diğer işleçler açgözlü prosedürün kapsamı dışında kalır. Bu veri türünü destekleyen çeşitli veri yapıları 6. ve 7. konularda ele alınacaktır.

Bu matematiksel modelin nesnelerine uygulanan operatör sayısının sınırlı olmadığı vurgulanmalıdır. Her ifade grubu ayrı bir ADT tanımlar. Soyut veri türü SET (Set) için tanımlanabilecek işleç örnekleri aşağıda verilmiştir.

1. MAKENULL(A), Bu işlem A kümesini boş küme yapar.

2. BİRLEŞTİRME(A, B, C). Bu prosedür iki "giriş" bağımsız değişkeni, A ve B kümeleri alır ve bu kümelerin birleşimini kendi "çıktı" bağımsız değişkeni olan C kümesine atar.

3. BOYUT(A). Bu işlevin bir küme bağımsız değişkeni A vardır ve A kümesinin öğe sayısına eşit bir tamsayı türünden bir nesne döndürür. ADT uygulaması terimi aşağıdakileri ifade eder: bu soyut veri türündeki değişkenleri tanımlayan bildirimlerin programlama diline çevrilmesi, artı ADT nesnelerinde gerçekleştirilen her ifade için prosedürler. Uygulama bağlıdır veri yapıları, ATD'yi temsil ediyor. Her veri yapısı, kullanılan programlama dilinin temel veri türleri temelinde, bu dilde mevcut olan veri yapılandırma araçları kullanılarak oluşturulur. Dizi ve kayıt yapıları, Pascal'da mümkün olan verileri yapılandırmanın iki önemli yoludur. Örneğin, SET tipi bir S değişkeninin olası uygulamalarından biri, setin öğelerini içeren bir dizi olabilir. S.

Aynı model içinde iki farklı ADT tanımlamanın ana nedenlerinden biri, bu ADT'lerin nesneleri üzerinde farklı eylemlerin gerçekleştirilmesi gerektiğidir, yani. farklı tipteki operatörleri tanımlar. Bu özet, küme teorisi ve grafik teorisi gibi yalnızca birkaç temel matematiksel modeli kapsar, ancak farklı uygulamalar, belirli ADT'lerin bu modellerine dayalı olarak farklı operatör kümeleri oluşturur.

İdeal olarak, temel veri türleri ve işleçleri bir ADT uygulamak için yeterli olan bir dilde programlar yazmak arzu edilir. Bu açıdan Pascal dili, çeşitli ADT'leri uygulamak için çok uygun bir dil değildir, ancak öte yandan, bir ADT'yi bu kadar doğrudan bildirmenin mümkün olacağı başka bir programlama dili bulmak zordur. . Bu tür programlama dilleri hakkında daha fazla bilgi için konunun sonundaki bibliyografik notlara bakın.

Soyut veri türü

Soyut veri türü (ATD) bu tür öğelerle çalışmak için belirli bir dizi işlev sağlayan ve ayrıca özel işlevler kullanarak bu tür öğeler oluşturma yeteneği sağlayan bir veri türüdür. Bu türün tüm iç yapısı, yazılım geliştiricisinden gizlenmiştir - bu, soyutlamanın özüdür. Soyut bir veri türü, değerleri üzerinde çalışmak için türün belirli uygulamasından bağımsız olan bir dizi işlevi tanımlar. ADT'lerin belirli uygulamalarına veri yapıları denir.

Programlamada, soyut veri türleri genellikle karşılık gelen tür uygulamalarını gizleyen arayüzler olarak temsil edilir. Uygulama gelecekte değişebileceğinden, programcılar soyut veri türleriyle yalnızca arabirimleri aracılığıyla çalışır. Bu yaklaşım, nesne yönelimli programlamadaki kapsülleme ilkesiyle uyumludur. Bu tekniğin gücü, tam olarak uygulamanın gizlenmesinde yatmaktadır. Dışarıda sadece arayüz yayınlandığı için, veri yapısı bu arayüzü desteklediği sürece soyut bir veri tipi ile verilen yapı ile çalışan tüm programlar çalışmaya devam edecektir. Veri yapılarının geliştiricileri, işlevlerin dış arayüzünü ve anlamını değiştirmeden, uygulamaları kademeli olarak iyileştirmeye, algoritmaları hız, güvenilirlik ve kullanılan bellek açısından iyileştirmeye çalışır.

Soyut veri türleri ile soyut türleri uygulayan veri yapıları arasındaki fark, aşağıdaki örnekle gösterilebilir. Liste soyut veri türü, çeşitli dinamik bellek ayırma yöntemleri kullanılarak bir dizi veya doğrusal liste ile uygulanabilir. Bununla birlikte, her uygulama, tüm uygulamalar için aynı şekilde (hız olarak değil, sonuç olarak) çalışması gereken aynı işlev kümesini tanımlar.

Soyut veri türleri, yazılım ürünlerinin modülerliğini elde etmenize ve tek bir modülün birkaç alternatif değiştirilebilir uygulamasına sahip olmanıza olanak tanır.

ADT örnekleri

Ayrıca bakınız

Bağlantılar

• Lapshin V. A. Programlamada soyut veri türleri

Wikimedia Vakfı. 2010

Diğer sözlüklerde "Soyut veri türü"nün ne olduğunu görün:

soyut veri türü- Yöntemlerini ve özelliklerini somut bir uygulama oluşturmadan numaralandırarak tanımlanan bir veri türü (soyut sınıf). Konular genel olarak bilgi teknolojisi EN Soyut Veri TipiADT ... Teknik Tercümanın El Kitabı

Programlama teorisinde, değerleri cebirsel tür kuruculara sarılmış başka bir türün değerleri olan herhangi bir tür. Başka bir deyişle, bir cebirsel veri türü, her biri ... ... Wikipedia olan bir dizi tür oluşturucuya sahiptir.

Tamsayı, tamsayı veri türü (İngilizce Tamsayı), bilgisayar bilimlerinde, programlama dillerinde en basit ve en yaygın veri türlerinden biridir. Tamsayıları temsil etmek için kullanılır. Bu türdeki sayı kümesi ... ... Wikipedia'dır

Bu terimin başka anlamları vardır, bkz. Set (anlamları). Küme, bilgisayar biliminde bir tür ve veri yapısıdır, matematiksel nesne kümesinin bir uygulamasıdır. Veri türünü ayarla, sınırlı sayıda değer saklamanıza olanak tanır... ... Wikipedia

Bazı programlama dilleri, karmaşık sayılar için özel bir veri türü sağlar. Yerleşik bir türün varlığı, karmaşık değerlerin depolanmasını ve bunlarla ilgili hesaplamaları basitleştirir. İçindekiler 1 Karmaşık yerine aritmetik 2 Dillerde destek ... Wikipedia

Bu terimin başka anlamları da vardır, bkz. İndeks. İşaretçi diyagramı İşaretçi (işaretçi, İngilizce işaretçi), değer aralığı bellek hücrelerinin adreslerinden ve sıfır adresin özel bir değerinden oluşan bir değişkendir. ... ... Wikipedia

Yapıcılarının kendi türlerinde olmayan değerleri döndürebilmeleri ile karakterize edilen cebirsel veri türlerinin türlerinden biri. Bu kavram, çeşitli programlama dillerinde, özellikle ML ve Haskell'de ve ... ... Wikipedia'da uygulanmaktadır.

Özellik, bilgisayar biliminde "nesne yönelimli programları yapılandırmak için basit bir kavramsal model" olarak kullanılan soyut bir türdür. Nitelikler, karışımlar gibidir, ancak sınıf yöntemi tanımlarını içerebilir. ... ... Wikipedia

İkili ağaç, dallanan bağlı veri yapısının basit bir örneğidir. Veri yapısı (İngilizce veri yapısı), depolamaya izin veren bir yazılım birimi ... Wikipedia

- (üst tip) tip teorisinde, genellikle basitçe bir üst veya "sabit" sembol (⊤) olarak belirtilir, evrensel bir tip, yani istenen tip sistemindeki her olası nesneyi içeren bir tip. En yüksek tür bazen şu şekilde anılır ... ... Wikipedia