Veri yapısı programlama. Veri yapıları. resmi olmayan rehber

19.05.2019

Tercüme

Elbette, veri yapılarının kutsal bilgisine sahip olmadan başarılı bir programcı olabilirsiniz, ancak bazı uygulamalarda kesinlikle yeri doldurulamazlar. Örneğin, bir haritadaki iki nokta arasındaki en kısa yolu hesaplamanız veya örneğin bir milyon giriş içeren bir telefon defterinde bir isim bulmanız gerektiğinde. Bahsetmemek gerekirse, veri yapıları spor programlamasında sürekli olarak kullanılmaktadır. Bazılarını daha ayrıntılı olarak ele alalım.

Sıra

Öyleyse Loopy'ye merhaba deyin!

Loopy ailesiyle hokey oynamayı sever. "Oynat" derken şunu kastediyorum:

Kaplumbağalar kapıya uçtuğunda yığının tepesine atılırlar. Yığına eklenen ilk kaplumbağanın ilk ayrılan olduğuna dikkat edin. denir Sıra... Tıpkı günlük hayatta gördüğümüz sıralarda olduğu gibi listeye ilk eklenen madde, listeden ilk çıkan oluyor. Bu yapıya da denir FIFO(İlk giren ilk çıkar).

Ekleme ve silme işlemlerine ne dersiniz?

Q = def ekleme (elem): q.append (elem) # kuyruğun sonuna bir öğe ekle yazdır q def sil (): q.pop (0) # kuyruktan sıfır öğesini kaldır yazdır q

Yığın

Böyle eğlenceli bir hokey oyunundan sonra Loopy herkes için krep yapar. Onları bir yığına koyar.

Tüm krepler hazır olduğunda Loopy onları tek tek tüm aileye servis eder.

Yaptığı ilk krepin en son servis edileceğini unutmayın. denir Yığın... Listeye eklenen son öğe ilk ayrılan olacaktır. Ayrıca bu veri yapısı denir LIFO(Son Giren İlk Çıkar).

Öğe ekleme ve kaldırma?

S = def push (elem): # Yığına bir öğe ekleyin - Push s.append (elem) print s def customPop (): # yığından bir öğeyi kaldırın - Pop s.pop (len (s) -1) baskı s

Yığın

Yoğunluk Kulesi'ni hiç gördünüz mü?

Yukarıdan aşağıya tüm elemanlar yoğunluklarına göre yerlerine yerleştirilmiştir. İçine yeni bir nesne düşürürseniz ne olur?

Yoğunluğuna göre gerçekleşecektir.

Bu nasıl çalışır Yığın.

Yığın ikili bir ağaçtır. Bu, her ebeveynin iki çocuğu olduğu anlamına gelir. Ve bu veri yapısına yığın desek de, düzenli bir dizi aracılığıyla ifade edilir.
Ayrıca yığın her zaman logn yüksektir, burada n eleman sayısıdır

Şekil, aşağıdaki kurala dayalı bir maksimum yığını göstermektedir: çocuklar daha küçük ebeveyn. Çocukların her zaman olduğu küçük yığınlar da vardır. daha fazla ebeveyn.

Yığınlarla çalışmak için birkaç basit işlev:

Global heap global currSize def parent (i): # i-th öğesinin üst dizinini alın return i / 2 def left (i): # i-th öğesinin sol çocuğunu alın return 2 * i def right (i ): # i-inci dönüşün sağ çocuğunu alın (2 * i + 1)

Mevcut bir yığına öğe ekleme
İlk olarak, öğeyi yığının en altına ekliyoruz, yani. dizinin sonuna. Ardından, yerine oturana kadar ebeveynle değiştiririz.

algoritma:

Öğeyi yığının en altına ekleyin.
Eklenen öğeyi üst öğeyle karşılaştırın; sipariş doğruysa, dururuz.
Değilse, öğeleri değiştiririz ve önceki noktaya döneriz.

Kod:

Def takas (a, b): # a indeksli elemanı b indeksli elemanla değiştir temp = yığın [a] yığın [a] = yığın [b] yığın [b] = temp def ekleme (elem): global currSize index = len (yığın) heap.append (elem) currSize + = 1 par = parent (index) flag = 0 while flag! = 1: if index == 1: # Kök elemana ulaşıldı flag = 1 elif yığın> elem: # Kök elemanın indeksi elemanımızın indeksinden büyükse - elemanımız yerindedir flag = 1 else: # Ana elemanı takas (par, indeks) ile değiştirin indeks = par par = ebeveyn (index) print yığın
while döngüsünün maksimum geçiş sayısı ağacın yüksekliğine veya logn'a eşittir, bu nedenle algoritmanın karmaşıklığı O'dur (logn).

Maksimum Yığın Öğesini Alma
Yığındaki ilk öğe her zaman maksimumdur, bu yüzden onu sileriz (önceden hatırlayın) ve en düşük olanla değiştiririz. Ardından, işlevi kullanarak yığını doğru sıraya koyacağız:

MaxHeapify ().

algoritma:

Kök elemanı en düşük olanla değiştirin.
Yeni kök öğeyi çocuklarla karşılaştırın. Doğru sıradaysa, durun.
Değilse, kök öğeyi alt öğelerden biriyle değiştirin (min-yığın için daha küçük, max-yığın için daha büyük) ve 2. adımı tekrarlayın.

Def ExtractMax (): global currSize eğer currSize! = 0: maxElem = yığın yığın = yığın # Kök öğeyi en sonuncusu ile değiştirin heap.pop (currSize) # Son öğeyi kaldırın currSize - = 1 # Yığın boyutunu azalt maxHeapify ( 1) return maxElem def maxHeapify (indeks): global currSize lar = indeks l = sol (indeks) r = sağ (indeks) # Hangi çocuğun daha büyük olduğunu hesaplayın; ebeveynden daha büyükse, l ise değiştirin<= currSize and heap[l] >yığın: lar = l ise r<= currSize and heap[r] >yığın: lar = r ise lar! = dizin: takas (indeks, lar) maxHeapify (lar)
Ve yine, maxHeapify işlevine yapılan maksimum çağrı sayısı ağaç yüksekliğine veya logn'a eşittir; bu, algoritmanın karmaşıklığının O (logn) olduğu anlamına gelir.

Herhangi bir rastgele diziden bir demet yapmak
Tamam, bunu yapmanın iki yolu var. Birincisi, her bir elemanı yığına birer birer yerleştirmektir. Bu basit, ama tamamen etkisiz. Bu durumda algoritmanın karmaşıklığı O (nlogn) olacaktır, çünkü O (logn) işlevi n kez çalışacaktır.

Daha verimli bir yol, maxHeapify işlevini ' alt yığınlar', From (currSize / 2) ilk öğeye.

Karmaşıklık O(n) olacaktır ve bu ifadenin ispatı ne yazık ki bu makalenin kapsamı dışındadır. Yığının currSize / 2 to currSize kısmındaki öğelerin hiçbir çocuğu olmadığını ve bu şekilde oluşturulan 'alt yığınların' çoğunun oturum yüksekliğinden daha az olacağını anlayın.

Def buildHeap(): aralıktaki i için global currSize (currSize / 2, 0, -1): # range () içindeki üçüncü argüman yineleme adımıdır, bu durumda yönü belirler. yığın yazdır maxHeapify (i) currSize = len (yığın) -1

Gerçekten, tüm bunlar neden?

Garip bir şekilde, " olarak adlandırılan özel bir sıralama türünü uygulamak için yığınlara ihtiyaç vardır. yığın sıralama”. Daha az verimli olan "insert sort" ve "balon sort" un korkunç O (n 2) karmaşıklığından farklı olarak, "yığın sıralama" O (nlogn) karmaşıklığına sahiptir.

Uygulama son derece basittir. Yığından sırayla maksimum (kök) öğeyi almaya devam edin ve yığın boşalana kadar diziye yazın.

Def heapSort (): aralıktaki i için (1, len (yığın)): yığın yazdır heap.insert (len (yığın) -i, extractMax ()) # maksimum öğeyi dizinin sonuna ekle currSize = len ( yığın) -1
Yukarıdakilerin tümünü özetlemek için, yığınla çalışmak için işlevleri içeren birkaç satır kod yazdım ve OOP hayranları için her şeyi bir sınıf biçiminde tasarladım.

Kolay, değil mi? Ve işte kutlayan Lupi!

Doğramak

Loopy, çocuklarına şekilleri ve renkleri ayırt etmeyi öğretmek istiyor. Bunu yapmak için eve çok sayıda çok renkli figür getirdi.

Bir süre sonra, kaplumbağaların kafası nihayet karıştı.

Bu yüzden işleri biraz kolaylaştırmak için başka bir oyuncak çıkardı.

Çok daha kolay oldu çünkü kaplumbağalar şekillerin şekle göre sıralandığını zaten biliyorlardı. Her gönderiyi işaretlersek ne olur?

Kaplumbağaların artık belirli bir sayıya sahip bir sütunu kontrol etmeleri ve ihtiyaç duydukları çok daha az sayıda figür arasından seçim yapmaları gerekiyor. Ve her şekil ve renk kombinasyonu için ayrı bir sütunumuz varsa?

Diyelim ki posta numarası aşağıdaki gibi hesaplanıyor:

Ad Soyad yaz mevsimi tre Meydan
ph + u + o + t + p + e = 22 + 10 + 16 + 20 + 18 + 6 = Sütun 92

Kra uykulu Düz dağ
k + p + a + n + p + i = 12 + 18 + 1 + 17 + 18 + 33 = Sütun 99

6 * 33 = 198 olası kombinasyon olduğunu biliyoruz, bu da 198 sütuna ihtiyacımız olduğu anlamına geliyor.

Sütun sayısını hesaplamak için bu formülü arayalım - Özet fonksiyonu.

Kod:
def hashFunc (parça): sözcükler = parça.split ("") # dizeyi sözcüklere böl color = sözcükler şekil = sözcükler poleNum = 0 aralıktaki i için (0, 3): poleNum + = ord (renk [i]) - 96 poleNum + = ord (şekil [i]) - 96 dönüş poleNum
(Kiril biraz daha karmaşık, ama basit olması için bu şekilde bıraktım. - yaklaşık)

Şimdi, pembe karenin nerede saklandığını bulmamız gerekirse, şunu hesaplayabiliriz:
hashFunc ("pembe kare")

Bu, öğelerin konumunun bir özet işlevi tarafından belirlendiği bir özet tablosu örneğidir.
Bu yaklaşımla, herhangi bir elemanı aramak için harcanan zaman, eleman sayısına bağlı değildir, yani. O (1). Yani hash tablosundaki arama süresi sabit bir değerdir.

Tamam ama diyelim ki arıyoruz” araba güzel Düz mugon "(tabii ki, renk" karamel "varsa).

HashFunc ("karamel dikdörtgen")
bize kırmızı dikdörtgenin sayısıyla aynı olan 99'u döndürür. " denir. Çarpışma”. Çarpışmaları çözmek için “ Zincirleme yöntemi”, Her sütunun ihtiyacımız olan kaydı aradığımız bir liste içerdiğini ima etmek.

Bu yüzden karamel dikdörtgeni kırmızı olanın üzerine koyuyoruz ve hash fonksiyonu o sütunu gösterdiğinde bunlardan birini seçiyoruz.

İyi bir hash tablosunun anahtarı, doğru hash fonksiyonunu seçmektir. Bu, bir hash tablosu oluşturmada yadsınamaz bir şekilde en önemli şeydir ve insanlar kaliteli hash fonksiyonlarını geliştirmek için muazzam miktarda zaman harcarlar.
İyi tablolarda hiçbir pozisyon 2-3'ten fazla eleman içermez; aksi halde hashleme kötü çalışır ve hash fonksiyonunu değiştirmeniz gerekir.

Bir kez daha, öğeden bağımsız bir arama! Devasa olan her şey için karma tabloları kullanabiliriz.

Hash tabloları, algoritmayı kullanarak büyük metin parçalarındaki dizeleri ve alt dizeleri bulmak için de kullanılır. Rabin-Karp veya algoritma Knut-Morris-Pratt, örneğin bilimsel makalelerdeki intihalleri tespit etmek için yararlıdır.

Bu konuda, bence, bitirebiliriz. Gelecekte, örneğin daha karmaşık veri yapılarına bakmayı planlıyorum. Fibonacci yığını ve Segment ağacı... Umarım bu resmi olmayan rehber ilginç ve faydalı olmuştur.

Kilitli Habr için çevrildi

Veri yapısı kavramı o kadar temeldir ki, bunun için basit bir tanım bulmak zordur. Bu kavramı veri türleri ve değişkenlerle ilgili olarak formüle etmeye çalışırsanız görev basitleşir. Bildiğiniz gibi, bir program bir algoritma (prosedürler, işlevler) ve bunlar tarafından işlenen verilerin birliğidir. Veri, sırayla, temel ve türetilmiş veri türleri tarafından tanımlanır - sabit boyutlu değişkenlerin, üzerlerinde ve bileşenleri üzerinde bilinen işlem kümeleriyle "ideal" temsilleri. Değişkenler, oluşturulmuş veri türlerinin "eşlendiği" bellek alanları olarak adlandırılır.
Bir programda, dolaylı olarak ilişkili (aynı prosedürler ve işlevlerdeki verileri kullanarak) ve doğrudan ilişkili (işaretçiler aracılığıyla ilişkilerin varlığıyla) değişken gruplarını her zaman ayırt edebilirsiniz. İlk yaklaşım olarak, veri yapıları olarak kabul edilebilirler.

BASİT (temel, ilkel) veri yapıları (türleri) ve ENTEGRE (yapılandırılmış, bileşik, karmaşık) arasında ayrım yapın. Basit veri yapıları, bitlerden daha büyük bileşenlere ayrıştırılamayanlardır. Fiziksel yapı açısından, belirli bir makine mimarisinde, belirli bir programlama sisteminde, belirli bir basit türün boyutunun ne olacağını ve yerleşim yapısının ne olduğunu her zaman önceden söyleyebilmemiz önemlidir. hafıza. Mantıksal bir bakış açısından, basit veriler bölünemez birimlerdir. Entegre veri yapıları, bileşenleri diğer veri yapıları olan basit veya sırayla entegre olanlardır. Entegre veri yapıları, programlama dilleri tarafından sağlanan veri entegrasyon araçları kullanılarak programcı tarafından tasarlanır.

Veri öğeleri arasında açıkça belirtilen ilişkilerin yokluğuna veya varlığına bağlı olarak, BAĞLANMAMIŞ yapılar (vektörler, diziler, diziler, yığınlar, kuyruklar) ve BAĞLANTILI yapılar (bağlı listeler) arasında ayrım yapılmalıdır.

Bir veri yapısının çok önemli bir özelliği değişkenliğidir - yapının elemanları arasındaki eleman sayısı ve (veya) bağlantılardaki bir değişiklik. Yapı oynaklığının tanımı, veri öğelerinin değerlerinin değiştiği gerçeğini yansıtmaz, çünkü bu durumda tüm veri yapıları oynaklık özelliğine sahip olacaktır. Değişkenlik temelinde yapılar ayırt edilir: STATİK, YARI STATİK, DİNAMİK. Değişkenliğe dayalı veri yapılarının sınıflandırılması Şekil 2'de gösterilmektedir. 1.1. Statik, yarı statik ve dinamik olan temel veri yapıları RAM'e özgüdür ve genellikle çevrimiçi yapılar olarak adlandırılır. Dosya yapıları, harici bellek için veri yapılarına karşılık gelir.

Pirinç. 1.1. Veri yapılarının sınıflandırılması

Bir veri yapısının önemli bir özelliği, elemanlarının sıralanmasının doğasıdır. Bu temelde, yapılar DOĞRUSAL ve DOĞRUSAL OLMAYAN yapılara ayrılabilir.

Bellekteki öğelerin karşılıklı düzenlenmesinin doğasına bağlı olarak, doğrusal yapılar, bellekteki öğelerin SONUÇ dağılımına (vektörler, diziler, diziler, yığınlar, kuyruklar) ve ARBITRARY CONNECTED öğelerin bellekte dağılımına sahip yapılara ayrılabilir. (tek bağlantılı, çift bağlantılı listeler). Doğrusal olmayan yapılara bir örnek, çok bağlantılı listeler, ağaçlar, grafiklerdir.

Programlama dillerinde "veri yapıları" kavramı, "veri türleri" kavramıyla yakından ilişkilidir. Herhangi bir veri, yani sabitler, değişkenler, fonksiyon değerleri veya ifadeler türlerine göre karakterize edilir.

Her tür için bilgiler benzersiz bir şekilde şunları tanımlar:

1) belirtilen türde bir veri depolama yapısı, yani. bir yandan bellek tahsis etmek ve içindeki verileri temsil etmek ve diğer yandan ikili gösterimi yorumlamak;

· 2) açıklanan türden bir veya başka bir nesnenin sahip olabileceği bir dizi kabul edilebilir değer;

· 3) açıklanan türdeki bir nesneye uygulanabilen bir dizi izin verilebilir işlem.

VERİ YAPISI - fiziksel (veri türleri) ve mantıksal (algoritma, işlevler) birbiriyle ilişkili değişkenler ve değerleri kümesi.

Bir veri yapısı kavramının yalnızca onu oluşturan değişkenleri değil, aynı zamanda değişkenleri mantıksal olarak birbirine bağlayan algoritmaları (fonksiyonları) değil, aynı zamanda buna içkin olması gereken dahili değerleri de tanımladığını unutmayın. veri yapısı. Örneğin, bir dizide yer alan ve değişken bir boyuta (veri yapısı) sahip olan bir pozitif değerler dizisi boş bir sonlandırıcıya sahip olabilir. Bu sınırlayıcının oluşturulması ve doğrulanması için tüm işlemler, işlevler tarafından gerçekleştirilir. Bu nedenle, veri yapısının önemli bir bölümünün işlenmesi için algoritmalarda "sabit kodlanmış" olduğunu söyleyebiliriz.
Değişkenleri veri türleri aracılığıyla tanımlamanın bilinen yolu, ilk olarak programdaki değişkenlerin sayısının sabit olması ve ikinci olarak program çalışırken boyutlarının değiştirilememesi ile karakterize edilir. Bu değişkenler arasındaki ilişkiler az çok kalıcıysa, bu tür veri yapılarına statik denilebilir.

STATİK VERİ YAPISI - aralarındaki ilişkilerin değişmeyen doğası ile sabit boyutta sabit sayıda değişken kümesi
Ve bunun tersi, bir veri yapısının parametrelerinden biri değişkenlerin sayısıysa, programın yürütülmesi sırasında boyutları veya aralarındaki ilişki değişirse, bu tür veri yapılarına dinamik denir.

DİNAMİK VERİ YAPISI - bir dizi değişken, programların yürütülmesi sırasında aralarındaki ilişkinin sayısı, boyutu veya doğası.

Dinamik veri yapıları, programlama dilinin iki unsuruna dayanır:

· Sayısı değişebilen ve nihai olarak programın kendisi tarafından belirlenen dinamik değişkenler. Ek olarak, dinamik diziler oluşturma yeteneği, değişken boyutlardaki veriler hakkında konuşmanıza olanak tanır;

· Veriler ve bu ilişkileri değiştirme yeteneği arasında doğrudan bir ilişki sağlayan işaretçiler.

Bu nedenle, bu tanım gerçeğe yakındır: dinamik veri yapıları, dinamik değişkenler ve işaretçiler tarafından bağlanan dizilerdir.
Veri yapılarından bahsetmişken, sıradan değişkenlerin RAM'de (dahili bilgisayar belleği) bulunduğunu unutmamalıyız. Bu nedenle, veri yapıları genellikle bellekle ilgilidir. Ancak, dilde, dosyalarla çalışan operatörler (Pascal) veya işlevler (C) aracılığıyla dolaylı olarak kullanılabilen harici bellek de vardır. İkili rastgele erişimli dosya modunda, herhangi bir dosya sınırsız doğrudan adreslenebilir bellek alanının bir analogudur, yani programın bakış açısından sıradan bellek gibi görünür. Doğal olarak, program değişkenleri bellekten dosyadaki rastgele bir konuma kopyalayabilir ve bunun tersi de olabilir ve bu nedenle dosyadaki herhangi bir (dinamik dahil) veri yapısını düzenleyebilir.
Veri yapısı, depolama, ekleme ve silme, değiştirme, arama vb. dahil olmak üzere verilerle çalışmayı organize eden bir yürütücüdür. Veri yapısı, bunlara belirli bir erişim sırasını korur. Bir veri yapısı, bir tür depo veya kütüphane olarak düşünülebilir. Bir veri yapısını tanımlarken, onun için mümkün olan bir dizi eylemi listelemeniz ve her bir eylemin sonucunu açıkça tanımlamanız gerekir. Bu tür eylemlere reçete diyeceğiz. Programatik bir bakış açısından, bir veri yapısı reçete sistemi, paylaşılan değişkenler üzerinde çalışan bir dizi fonksiyona karşılık gelir.
Veri yapıları en uygun şekilde nesne yönelimli dillerde uygulanır. Onlarda sınıf, veri yapısına karşılık gelir, verilerin kendisi sınıfın üye değişkenlerinde saklanır (veya verilere üye değişkenler aracılığıyla erişilir), sınıf yöntemleri kümesi reçete sistemine karşılık gelir. Kural olarak, nesne yönelimli dillerde, veri yapıları standart sınıfların bir kitaplığı olarak uygulanır: bunlar, standart sınıf kitaplığı STL'nin parçası olan C++ dilinin kapsayıcı sınıfları veya çeşitli uygulayan sınıflardır. Java dilinin Java Developer Kit kitaplığından veri yapıları.
Bununla birlikte, veri yapıları Fortran veya C gibi geleneksel programlama dillerinde de başarılı bir şekilde uygulanabilir. Bu durumda, nesne yönelimli programlama stiline bağlı kalınmalıdır: veri yapısıyla çalışan işlevler kümesini açıkça tanımlayın ve yalnızca bu işlev kümesiyle verilere erişimi kısıtlayın. Verinin kendisi statik (genel değil) değişkenler olarak uygulanır. C dilinde programlama yaparken, veri yapısı iki kaynak dosyaya karşılık gelir:
1.başlık veya veri yapısının arayüzünü açıklayan h-dosyası, yani. veri yapısı reçete sistemine karşılık gelen bir dizi fonksiyon prototipi;
2. Uygulama dosyası veya verileri depolayan ve bunlara erişen statik değişkenleri tanımlayan ve ayrıca veri yapısının reçete sistemine karşılık gelen işlevleri uygulayan C dosyası
Veri yapısı genellikle daha önce uygulanmış daha basit bir temel yapıya dayalı olarak veya bir diziye ve bir dizi basit değişkene dayalı olarak uygulanır. Mantıksal bir bakış açısıyla bir veri yapısını tanımlama ile onun uygulamasını tanımlama arasında net bir ayrım yapılmalıdır. Pek çok farklı uygulama olabilir, ancak mantıksal bir bakış açısından (yani, harici bir kullanıcının bakış açısından) bunların hepsi eşdeğerdir ve belki de yalnızca reçetelerin uygulanma hızında farklılık gösterir.

VERİ TÜRLERİ VE YAPILARI

"Algoritmalar ve veri yapıları" disiplini için metodik talimatlar

O.L tarafından derlenmiştir. Çağaeva

"Yazılım ve Sistemler" Bölümü tarafından hazırlanmıştır FUO UrFU

Tanıtım

V çevremizdeki dünya, bilgi yoluyla görüntülenen çok çeşitli nesneler, nesneler, fenomenler, süreçlerdir.

Bilgi ile temsil edilen her varlık (nesne, fenomen) bir dizi karakteristik özelliğe (özellikler, nitelikler, parametreler, özellikler, anlar) sahiptir. Örneğin, bir malzemenin özellikleri ağırlığı, boyutları, kalitesi, fiyatı, stok numarası vb.'dir. Bu tür bir varlığı satın alma organizasyonu olarak nitelendiren özellik işaretleri, Devletteki ad, departman bağlantısı, adres, hesap numarasıdır. Banka vb.

Fiziksel bir varlığın özellikleri, temel bilgi birimleri olan ve nitelikler olarak adlandırılan değişken değerler kullanılarak görüntülenir.

Nitelik, herhangi bir karmaşık bilgi kümesinin mantıksal olarak bölünemez bir öğesidir ve bilgi tarafından görüntülenen bir nesnenin veya işlemin belirli bir özelliği ile ilişkilendirilir.

V işlenen bilgilerden, gereklilikler, bilgi oluşumu yapısında daha karmaşık olan geri kalan her şeyin bir araya getirildiği "atomlar" ile temsil edilir. Ve tam tersi, herhangi bir karmaşıklıktaki bilgi birimleri sırayla bileşenlerine ayrılabilir ve nihayetinde bu tür bileşenlere bölünebilir - mantıksal olarak daha fazla ayrıştırılamayan değişken miktarlar. Bu tür temel bileşenler sahne olacaktır.

Literatürde sahne malzemelerinin diğer yaygın eşanlamlıları şunlardır: eleman, alan, terim, nitelik ve nitelik.

Her sahnenin bir adı vardır. Sıkıştırılmış yazma amacıyla algoritmalaştırma ve programlamada kısaltmalar en sık kullanılır. tanımlayıcı adları, dahası, belirli uygulamalar genellikle uzunluklarını, alfabelerini ve kapsamlarını sınırlar. Bazı durumlarda, yalnızca harici belgelerde kullanılan tam adlar da dahil olmak üzere, örneğin rapor sütunlarının başlıkları olarak, gereksinimlerin adları için eşanlamlıların kullanılmasına da izin verilir.

Her öznitelik, bu özniteliği bilgisel olarak görüntüleyen nesnenin (olgu) özelliğinin özelliklerine bağlı olarak belirli bir sonlu değer kümesine sahiptir. Değer sınıfı olarak adlandırılan bu küme, örneğin "hastanın sıcaklığı" parametresi için ve "hastanın cinsiyeti" özelliği için bir başka kümedir.

Bu nedenle, değişkenin değeri, belirli bir zamanda, verilen değişkenin değer sınıfının konumlarından biridir ve bu, özelliğin karşılık gelen durumunu (durumlar kümesinden) yansıtması beklenir. değişkeni karakterize eden nesne (fenomen). Bu nedenle, "hastanın sıcaklığı" değişkeninin mevcut değeri 37.4 ° ve "hastanın cinsiyeti" - "erkek" değişkeni olabilir. Başka bir deyişle, props değeri, karşılık gelen varlık özelliğinin değerini temsil etmek için kullanılır.

Sahip olabilecekleri değer türlerine bağlı olarak bir takım nitelik türleri vardır. Bununla birlikte, en yaygın sahne türleri şunlardır: sayısal ve metin.

Sayısal nitelikler, doğal birimlerin sayılması, ölçülmesi, tartılması, diğer nicel toplam verilere dayalı hesaplamalar vb. sonucunda elde edilen varlıkların nicel özelliklerini karakterize eder. Bu nedenle, bu tür niteliklerin değerleri, tüm karakteristik özellikleri ve nitelikleri ile sayılardır. .

Somut temsillerde, sayı sınıfına, sayı sistemine, ondalık noktanın sabitlenmesine, paketlemeye ve diğerlerine bağlı olarak çeşitli sayısal değerler görünür; aynı uygulama içinde bile, sayıların aralığına, giriş / çıkış ve farklı ortamlarda temsil edilme biçimlerine kısıtlamalar getirilir. Sayısal bir türün tüm gereksinimleri çeşitli aritmetik işlemlerde aktif olarak kullanıldığından ve çoğu genellikle bu tür işlemlerin bir sonucu olarak oluşturulduğundan, bu farklılıklar ve sınırlamalar ve uygun bir dönüştürme ihtiyacı sürekli olarak akılda tutulmalıdır. aparat.

Metin türünün gereklilikleri, kural olarak, varlıkların niteliksel özelliklerini ifade eder ve incelenen sürecin gerçekleştiği koşulları ve belirli veya belirli veya

diğer sayısal değerler. Bu nedenle, bu tür ayrıntılara nitelikler denir.

Özellik değerleri, dize veya metin adı verilen karakter dizileridir (harfler, sayılar, çeşitli karakterler ve özel gösterimler).

Belirli bir bilgi sisteminin tüm olası ikili ayırt edilebilir sembollerinin eksiksiz seti, görevlerin doğasına, kullanılan teknik veri işleme araçlarına ve diğer faktörlere bağlı olarak alfabesini oluşturur. Ayrıca, farklı işleme aşamalarında ve hatta tek bir hesaplama sistemi çerçevesinde farklı alfabeler kullanmak mümkündür.

Alfabenin boyutu (bir değerin bir basamağında olabilen çeşitli karakterlerin sayısı) ve bileşimi (kümesi) aşağıdaki problemlerin çözümüyle doğrudan ilişkilidir:

kodlama ve şifre çözme,

bilgi birimlerinin değerlerinin kompakt kaydı,

verilerin etkin depolanması, aramalarının hızlandırılması, iletilmesi, bilgisayarlara girişi,

makinelerden tüketime en uygun biçimde bilgi alınması,

her türlü yeniden yazma maliyetini azaltmak.

Bu nedenle alfabe seçimi büyük önem taşımaktadır.

Bilginin kullanımı için, algoritmikleştirme ve programlamada, verilen bir şeyin türü ve yapısı gibi kavramlara çok büyük önem verilir.

1. VERİ TÜRLERİ

Bilgisayardaki hesaplama işlemi bilindiği gibi programlar ve veriler yardımıyla gerçekleştirilir. Programın kendisi de verilere atıfta bulunur. Bu nedenle, verilerin bir bilgisayarın çalışabileceği herhangi bir bilgiyi tanımladığını söyleyebiliriz. Bu durumda bilgi, gerçek dünyadaki nesneler, süreçler ve ilişkiler ve bunlar arasındaki bağlantılar hakkında herhangi bir gerçek ve bilgi olarak anlaşılır. Tüm veriler, değer de dahil olmak üzere bir dizi nitelik (işaretler, ayrıntılar) ile karakterize edilir.

Bu özellikler anlamın yanı sıra "veri tipi" kavramını da içermektedir. Bir verilenin türü, verilen değerler kümesi ve bu değerler üzerinde bilinen özelliklerine uygun olarak yapılabilecek işlemler kümesi ile belirlenir. Bu nedenle, veri türü, karşılık gelen değer üzerinde izin verilen işlemleri belirler.

Programlama dilleri genellikle tamsayı, gerçek, karakter, bit, işaretçiler vb. gibi yaygın veri türlerini kullanır.

2. VERİ YAPILARI

Bu özel türün bir özelliği, organizasyonun basitliğidir (yapılandırılmamışlık).

Bir veri yapısı, aralarında bazı ilişkiler bulunan bir veri öğeleri topluluğudur ve veri öğeleri hem basit veri (skaler) hem de veri yapıları olabilir.

Böylece yapı şu şekilde tanımlanabilir: S = (D, R), burada D bir veri öğeleri kümesidir, R, veri öğeleri arasındaki bir ilişkiler kümesidir.

Bir veri öğesinin diğerlerine olan tüm bağlantıları, karşılık gelen veri öğesiyle ilişkili bir ilişki öğesi oluşturur.

Bir yapının grafiksel temsili, veri öğelerini ve ilişkilerini (bunlar arasındaki ilişkileri) yansıtmalıdır, bu nedenle yapıyı bir grafik biçiminde tasvir etmek uygundur. Bu durumda, grafiğin köşeleri veri öğeleri olarak yorumlanabilir ve veri öğeleri arasındaki ilişkiler, yönlendirilmiş yaylara veya yönsüz kenarlara karşılık gelir (Şekil 1).

Bu nedenle, açıklanan ve sunulan veri yapısı, makine belleğindeki temsili dikkate alınmadan düşünüldüğünden, soyut veya mantıksal olarak adlandırılır. Ancak herhangi bir veri yapısı makine belleğinde temsil edilmelidir. Böyle bir veri yapısına fiziksel yapı, depolama yapısı, iç yapı veya bellek yapısı denir.

Şekil 1. Yönsüz (a) ve yönlendirilmiş (b) grafiği

Bu nedenle, verilerin fiziksel yapısı, verilerin makine belleğinde temsil edilme şeklini yansıtır.

Genel durumda, derecesi yapının kendisine ve yansıtılması gereken fiziksel ortamın özelliklerine bağlı olan mantıksal ve karşılık gelen fiziksel yapı arasında bir fark vardır.

Örneğin, programlama dilleri açısından, iki boyutlu bir dizi dikdörtgen bir tablodur ve bellekte her biri dizi öğelerinden birinin değerini ve dizi öğelerini depolayan doğrusal bir hücre dizisidir. satırlara (veya sütunlara) göre sıralanır.

Elbette, mantıksal yapıyı fiziksel yapıyla eşleştirmek için mantıksal yapı ile fiziksel yapı arasında bir mekanizma olmalıdır.

Böylece, her veri yapısı, mantıksal (soyut) ve fiziksel (somut) temsili ile ve ayrıca yapı temsilinin bu iki seviyesindeki bir dizi işlemle karakterize edilebilir (Şekil 2).

Mantıksal bir yapı üzerinde işlemler

Mantıksal veri yapısı

Fiziksel bir yapı üzerindeki işlemler

Fiziksel veri yapısı

Pirinç. 2. Veri yapısının mantıksal ve fiziksel temsili arasında eşleme

2.1. Veri yapılarının sınıflandırılması

V Veri öğeleri arasında açıkça belirtilen ilişkilerin yokluğuna veya varlığına bağlı olarak, ilişkisiz yapılar (vektörler, diziler, diziler, yığınlar, sıralar) ve bağlantılı yapılar (bağlı listeler) arasında ayrım yapılmalıdır.

Bir yapının önemli bir işareti, değişkenliğidir - yapı elemanları arasındaki eleman sayısı ve / veya bağlantılardaki bir değişiklik. Veri öğesinin anlamı kastedilmemektedir, çünkü bu durumda bu özellik, belki de sabitler ve ROM'da depolanan veriler dışında tüm veri yapıları için tipik olacaktır. Değişkenlik temelinde statik, yarı statik ve dinamik yapılar ayırt edilir.

Bir veri yapısının önemli bir özelliği, elemanlarının sıralanmasının doğasıdır. Bu temelde, yapılar doğrusal olarak sıralı veya doğrusal ve doğrusal olmayan olarak ayrılabilir.

Bellekteki öğelerin karşılıklı düzenlenmesinin doğasına bağlı olarak, doğrusal yapılar, öğelerinin bellekte sıralı dağılımına sahip yapılara (vektörler, diziler, diziler, yığınlar, kuyruklar) ve öğelerin rastgele bağlı dağılımına sahip yapılara ayrılabilir. bellek (basit bağlı, çift bağlı, döngüsel olarak bağlı, ilişkisel listeler). Doğrusal olmayan yapıların örnekleri, çoklu bağlantılı listeler, ağaç yapıları ve genel grafik yapılarıdır.

2.2. En basit statik yapılar

İLE En basit veri yapıları genellikle vektörler, diziler, kayıtlar, tablolardır. Aşağıdaki özelliklerle karakterize edilirler:

varlığının tüm dönemi boyunca yapının sabitliği;

elemanların bitişikliği ve yapının tüm elemanları için aynı anda tahsis edilen hafıza alanının sürekliliği; elemanlar arasındaki ilişkilerin basitliği ve sabitliği

Bu ilişkiler hakkındaki bilgileri yapı elemanları için ayrılan bellek alanından hariç tutmayı ve örneğin tanımlayıcılarda kompakt bir biçimde saklamayı sağlayan yapılar.

Bu özelliklerden dolayı vektörler, diziler, kayıtlar ve tablolar statik yapılar olarak kabul edilir.

2.2.1. Vektör

Bir vektör, aynı türden sonlu sıralı basit veri veya skaler kümesidir. Geometrik bir bakış açısından, bir vektör, koordinatları vektör elemanlarının değerleri olan çok boyutlu uzayda bir noktayı tanımlar.

Vektörün öğeleri birbirleriyle tek olası ilişki içindedir - doğrudan ardışıklık ilişkisi. Vektör öğelerinin katı dizisi,

bunları ardışık tamsayılarla - indekslerle numaralandırın. Bir vektörün mantıksal yapısı, elemanlarının sayısı ve türü ile tam olarak tanımlanır. Örneğin, int dizisi, 10 elemanlı bir tamsayı dizisidir.

Bir vektör üzerindeki en önemli işlem, elemanlarına erişimdir. Bir öğeye erişildiğinde, seçilen veri türü için anlamlı olan herhangi bir işlem bu öğe üzerinde gerçekleştirilebilir.

Mantıksal düzeyde, bir vektörün bir elemanına erişmek için, vektörün adını ve karşılık gelen elemanın indeksinin değerini belirtmek yeterlidir. Örneğin: dizi + dizi.

Bir vektörün fiziksel yapısı, her biri vektörün bir öğesini depolamak için tasarlanmış alanlar veya yuvalar olarak adlandırılan eşit uzunluktaki bir bellek dizisidir. Alan, adreslenebilir minimum bellek hücresinin boyutuna sahip olabilir veya bir dizi ardışık bellek hücresi grubuna karşılık gelebilir.

Çoğu zaman, fiziksel bir yapı, verilen fiziksel yapı hakkında bilgi içeren bir tanımlayıcı veya başlık ile ilişkilendirilir. Tanımlayıcı, örneğin vektörün sınır boyutlarının yalnızca program yürütme aşamasında bilinmesi durumunda gereklidir.

Bir tanımlayıcı da makine belleğinde saklanır ve kayıt adı verilen bir yapıdır. Bir vektör için, tanımlayıcı genellikle adını, boyutunu, sınır indeks değerlerini, eleman tipini, alanı veya yuva boyutunu, vektörün ilk elemanının adresini (bu elemanı saklayan alan) saklar.

2.2.2. Dizi

Dizi, her elemanı bir vektör olan bir vektördür. Sırayla, bir dizinin elemanı olan bir vektörün elemanları da vektör olabilir. Bu elemanın elemanından elemanına geçiş süreci vb., er ya da geç bazı veri tiplerinin bir skaleri ile bitmelidir ve dizinin bütün skaler elemanları bu tipe karşılık gelmelidir (Şekil 3).

Pirinç. 3. Çok boyutlu bir dizinin görünümü

Şekil 3, çok boyutlu bir dizinin görünümünü göstermektedir: her kafes düğümünde bir dizi öğesi vardır. Böylece boyutu (3,3,2)'ye eşittir.

Bir vektörde olduğu gibi, bir dizi için en önemli temel işlem, elemanına erişimdir. Mantıksal yapı düzeyinde, dizi adı ve dizi öğesini benzersiz olarak tanımlayan sıralı bir dizi dizin kullanılarak gerçekleştirilir. Örneğin: dizi [i] [j].

Bir vektörden farklı olarak, genel bir dizi için, mantıksal bir yapının fiziksel bir yapıya dönüştürülmesi daha karmaşık bir forma sahiptir. Bu dönüşüm, dizinin çok boyutlu mantıksal yapısını tek boyutlu bir fiziksel yapıya eşleyen bir doğrusallaştırma işlemiyle gerçekleştirilir. Bu fiziksel yapı, dizi öğelerinin doğrusal olarak sıralanmış bir dizisidir. Bu nedenle, çok boyutlu bir dizinin fiziksel yapısı, bir vektörün fiziksel yapısına benzer.

Ne olursa olsun, çok boyutlu bir dizi tanımlayıcısı bir vektör tanımlayıcısından farklıdır. Örneğin, dizinin boyutu, öğelerin nasıl sıralandığı (satırlar veya sütunlar) hakkında bilgi depolamalıdır.

2.2.3. Kayıt

Bir kayıt, genellikle çeşitli türlerdeki verileri içeren, sonlu sıralı bir öğeler kümesidir.

Kayıt öğelerine genellikle alanlar denir. Kayıt, tekdüzelik veya tekdüzelik gerektirmeyen genelleştirilmiş bir vektör kavramıdır.

Tercüme

Sıra

Öyleyse Loopy'ye merhaba deyin!

Loopy ailesiyle hokey oynamayı sever. "Oynat" derken şunu kastediyorum:

Ekleme ve silme işlemlerine ne dersiniz?

Q = def ekleme (elem): q.append (elem) # kuyruğun sonuna bir öğe ekle yazdır q def sil (): q.pop (0) # kuyruktan sıfır öğesini kaldır yazdır q

Yığın

Böyle eğlenceli bir hokey oyunundan sonra Loopy herkes için krep yapar. Onları bir yığına koyar.

Tüm krepler hazır olduğunda Loopy onları tek tek tüm aileye servis eder.

Yaptığı ilk krepin en son servis edileceğini unutmayın. denir Yığın... Listeye eklenen son öğe ilk ayrılan olacaktır. Ayrıca bu veri yapısı denir LIFO(Son Giren İlk Çıkar).

Öğe ekleme ve kaldırma?

S = def push (elem): # Yığına bir öğe ekleyin - Push s.append (elem) print s def customPop (): # yığından bir öğeyi kaldırın - Pop s.pop (len (s) -1) baskı s

Yığın

Yoğunluk Kulesi'ni hiç gördünüz mü?

Yukarıdan aşağıya tüm elemanlar yoğunluklarına göre yerlerine yerleştirilmiştir. İçine yeni bir nesne düşürürseniz ne olur?

Yoğunluğuna göre gerçekleşecektir.

Bu nasıl çalışır Yığın.

Yığınlarla çalışmak için birkaç basit işlev:

Mevcut bir yığına öğe ekleme
İlk olarak, öğeyi yığının en altına ekliyoruz, yani. dizinin sonuna. Ardından, yerine oturana kadar ebeveynle değiştiririz.

algoritma:

Öğeyi yığının en altına ekleyin.
Eklenen öğeyi üst öğeyle karşılaştırın; sipariş doğruysa, dururuz.
Değilse, öğeleri değiştiririz ve önceki noktaya döneriz.

Kod:

MaxHeapify ().

algoritma:

Kök elemanı en düşük olanla değiştirin.
Yeni kök öğeyi çocuklarla karşılaştırın. Doğru sıradaysa, durun.
Değilse, kök öğeyi alt öğelerden biriyle değiştirin (min-yığın için daha küçük, max-yığın için daha büyük) ve 2. adımı tekrarlayın.