Massivlər, əlaqəli siyahılar, stek və növbə

Massivin yaddaşda necə yerləşdiyini, dinamik massivin amortizasiyalı O(1) əlavə etməsini, əlaqəli siyahıları, stek və növbəni və onların tətbiqlərini öyrən.

  • Universitet
  • 25 dəq
  • 10 sual
  • 59 dərsdən 47-cisi

Bu dərsdə öyrənəcəksən

  • Massiv elementinin ünvanını hesablamaq və O(1) müraciəti izah etmək
  • Dinamik massivdə əlavə etmənin amortizasiyalı dəyərini sübut etmək
  • Massiv ilə əlaqəli siyahını əməliyyatların mürəkkəbliyinə görə müqayisə etmək
  • Məsələ üçün stek və ya növbə seçmək və onları tətbiq etmək

Brauzerdə «Geri» düyməsini basanda ən son açdığın səhifəyə qayıdırsan, xidmət mərkəzindəki elektron növbədə isə birinci bilet alan birinci qəbul olunur. Bu iki gündəlik qayda informatikanın iki əsas verilənlər strukturunun — stekin və növbənin mahiyyətidir. Onların altında isə daha sadə «kərpiclər» dayanır: massiv və əlaqəli siyahı. Hər strukturun güclü və zəif tərəfini bilmək proqramın sürətini çox vaxt alqoritmdən də çox müəyyən edir.

Massiv və dinamik massiv

MassivTərif

Eyni ölçülü elementlərin yaddaşda ardıcıl, boşluqsuz yerləşdirildiyi struktur. Elementin ünvanı onun indeksindən sadə düsturla hesablanır, ona görə istənilən elementə müraciət O(1) vaxt aparır.

addr(A[i]) = base + i · s

Burada

base
massivin başlanğıc ünvanı (A[0]-ın ünvanı)
i
elementin indeksi (0-dan başlayır)
s
bir elementin ölçüsü, bayt

İndeksin 0-dan başlamasının səbəbi də budur: i elementin başlanğıcdan neçə addım uzaqda olduğunu göstərir.

Nümunə 1: ünvanın hesablanması

Məsələ

4 baytlıq tam ədədlər massivi 1000 ünvanından başlayır. A[25] elementi hansı ünvandadır? Bəs A[5]-dən A[6]-ya keçəndə ünvan nə qədər dəyişir?

Həllini göstərHəllini gizlət

Həll

addr(A[25]) = 1000 + 25 · 4 = 1000 + 100 = 1100.
Qonşu elementlər arasında fərq s = 4 bayt.
Hesab i-nin qiymətindən asılı olmayaraq bir vurma və bir toplamadır — bu, O(1) müraciətin səbəbidir.

Bunun da bədəli var: massivin ortasına element əlavə etmək üçün sağdakı bütün elementləri bir yer sürüşdürmək lazımdır — O(n). Həm də ölçü əvvəlcədən sabitdir. Dinamik massiv (Python list, Java ArrayList, C++ vector) bu problemi belə həll edir: yer bitəndə iki dəfə böyük yeni massiv ayırır və köhnə elementləri ora köçürür.

(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n(n + 1 + 2 + 4 + … + 2ᵏ) / n < (n + 2n) / n = 32ᵏ < n

Burada

n
əlavə edilən elementlərin sayı
1 + 2 + … + 2ᵏ
bütün genişlənmələrdə köçürülən elementlərin cəmi (< 2n)

Amortizasiyalı dəyər: n əlavə etmənin ümumi işi 3n-dən azdır, deməli, bir əlavə etmə orta hesabla O(1)-dir — ayrı-ayrı «bahalı» genişlənmələrə baxmayaraq.

Python
class DynamicArray:
    def __init__(self):
        self.cap, self.n, self.copies = 1, 0, 0
        self.data = [None]

    def append(self, x):
        if self.n == self.cap:
            self.cap *= 2
            new = [None] * self.cap
            for i in range(self.n):
                new[i] = self.data[i]
                self.copies += 1
            self.data = new
        self.data[self.n] = x
        self.n += 1

arr = DynamicArray()
for k in range(1, 1025):
    arr.append(k)
    if k in (1, 2, 3, 5, 9, 17, 1024):
        print(k, arr.cap, arr.copies)
print('copies per append:', arr.copies / arr.n)
Gözlənilən nəticə
1 1 0
2 2 1
3 4 3
5 8 7
9 16 15
17 32 31
1024 1024 1023
copies per append: 0.9990234375
Sütunlar: element sayı, tutum, ümumi köçürmə sayı. Genişlənmə yalnız 2-ci, 3-cü, 5-ci, 9-cu, 17-ci… əlavədə baş verir; 1024 əlavədən sonra cəmi 1023 köçürmə olub — hər əlavəyə 1-dən az.

Davamını oxumaq üçün pulsuz qeydiyyatdan keç

Dərsin qalan bölmələri, test və qeydlər Educora hesabı ilə açılır. Qeydiyyat bir dəqiqə çəkir; irəliləyişin bütün cihazlarında saxlanılır.

Əlaqəli siyahılar

Əlaqəli siyahıTərif

Hər düyünün qiyməti və növbəti düyünə göstəricisi olan zəncir. Düyünlər yaddaşın istənilən yerində ola bilər; birinci düyünə baş (head) deyilir. İkitərəfli siyahıda hər düyün əvvəlkinə də göstərici saxlayır.

ƏməliyyatDinamik massivBirtərəfli əlaqəli siyahı
i-ci elementə müraciətO(1)O(n)
əvvələ əlavə / əvvəldən silməO(n)O(1)
sona əlavəamortizasiyalı O(1)O(1) (tail göstəricisi ilə)
məlum düyündən sonra əlavəO(n) (sürüşdürmə)O(1)
qiymətə görə axtarışO(n)O(n)
yaddaşyığcam, keşə uyğunhər düyünə əlavə göstərici, səpələnmiş
Seçim sualı: tez-tez indeksə görə oxuyursansa — massiv; əvvəldə və ortada çox əlavə/silmə edirsənsə — siyahı.
Python
class Node:
    def __init__(self, value, next=None):
        self.value, self.next = value, next
class LinkedList:
    def __init__(self):
        self.head = None
    def push_front(self, value):
        self.head = Node(value, self.head)
    def reverse(self):
        prev, cur = None, self.head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev, cur = cur, nxt
        self.head = prev
    def items(self):
        cur = self.head
        while cur:
            yield cur.value
            cur = cur.next
lst = LinkedList()
for city in ['Shaki', 'Ganja', 'Baku']: lst.push_front(city)
print(list(lst.items()))
lst.reverse()
print(list(lst.items()))
Gözlənilən nəticə
['Baku', 'Ganja', 'Shaki']
['Shaki', 'Ganja', 'Baku']
push_front yeni düyünü başa O(1)-də qoşur. reverse siyahını bir keçiddə — O(n) vaxt və O(1) əlavə yaddaşla çevirir: hər düyünün göstəricisini geriyə yönəldir. Bu, müsahibələrin klassik tapşırığıdır.

Stek (LIFO) və növbə (FIFO)

StrukturPrinsipƏməliyyatlar (hamısı O(1))Tətbiqlər
StekLIFO — sonuncu gələn birinci çıxırpush, pop, peekfunksiya çağırışları steki, «Geri al» (undo), mötərizələrin yoxlanması, DFS
NövbəFIFO — birinci gələn birinci çıxırenqueue, dequeue, frontçap növbəsi, şəbəkə buferləri, tapşırıq planlayıcısı, BFS

Nümunə 2: postfiks ifadənin stek ilə hesablanması

Məsələ

Postfiks (tərs Polşa) yazılışında operator operandlardan sonra gəlir. 5 1 2 + 4 * + 3 - ifadəsini stek ilə hesabla.

Həllini göstərHəllini gizlət

Həll

Qayda: ədəd → push; operator → iki ədəd pop et, nəticəni push et.
5 → [5]
1 → [5, 1]
2 → [5, 1, 2]
+ → 1 + 2 = 3 → [5, 3]
4 → [5, 3, 4]
* → 3 · 4 = 12 → [5, 12]
+ → 5 + 12 = 17 → [17]
3 → [17, 3]
- → 17 − 3 = 14 → [14]
Cavab: 14 (adi yazılışda 5 + (1 + 2) · 4 − 3). Hər simvol bir dəfə emal olunur → O(n).
Python
from collections import deque

def balanced(text):
    pairs = {')': '(', ']': '[', '}': '{'}
    stack = []
    for ch in text:
        if ch in '([{':
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

for s in ['(a[i] + b) * {c}', '(]', '((x)']:
    print(s, balanced(s))

queue = deque(['Aysel', 'Murad', 'Leyla'])
queue.append('Elvin')
print(queue.popleft(), 'is served;', list(queue), 'wait')
Gözlənilən nəticə
(a[i] + b) * {c} True
(] False
((x) False
Aysel is served; ['Murad', 'Leyla', 'Elvin'] wait
Stek açılan mötərizələri saxlayır: bağlanan mötərizə stekin başındakı ilə cüt olmalıdır, sonda stek boş qalmalıdır. deque hər iki ucdan O(1)-də əlavə və silmə verir — ideal növbə.

Növbəni sabit ölçülü massivdə də qurmaq olar: dairəvi bufer baş (head) və quyruq (tail) indekslərini saxlayır və massivin sonuna çatanda qalıqla bölmə vasitəsilə yenidən əvvələ «dolanır». Belə növbə yaddaş ayırmır və şəbəkə kartlarında, səs kartlarında, klaviatura buferində işlədilir.

tail = (head + size) mod mnext(i) = (i + 1) mod m

Burada

head
növbənin ilk elementinin indeksi
size
növbədəki elementlərin sayı
m
massivin tutumu
tail
növbəti elementin yazılacağı indeks

Nümunə 3: dairəvi bufer

Məsələ

Tutumu m = 6 olan dairəvi buferdə head = 4, size = 3. Yeni element hansı indeksə yazılacaq? Sonra iki element çıxarılır. head nə olar?

Həllini göstərHəllini gizlət

Həll

Elementlər 4, 5, 0 indekslərindədir.
tail = (4 + 3) mod 6 = 7 mod 6 = 1 → yeni element A[1]-ə yazılır, size = 4.
İki çıxarma: head = (4 + 1) mod 6 = 5, sonra (5 + 1) mod 6 = 0; size = 2.

Klassik müsahibə sualı: iki stekdən növbə qurmaq. Yeni elementlər in stekinə push olunur. Çıxarmaq lazım olanda out steki boşdursa, in-dəki bütün elementlər bir-bir out-a köçürülür — bu zaman sıra tərsinə çevrilir və ən köhnə element yuxarıya çıxır. Tək bir çıxarma O(n) ola bilər, amma hər element ən çoxu bir dəfə köçürülür, ona görə n əməliyyatın cəmi O(n), yəni hər əməliyyat amortizasiyalı O(1)-dir.

Yadda saxla

  • Massivdə element ünvanı base + i · s ilə hesablanır — müraciət O(1), ortaya əlavə O(n).
  • Dinamik massiv tutumu həndəsi artırır, ona görə sona əlavə amortizasiyalı O(1)-dir.
  • Əlaqəli siyahıda əvvələ və məlum düyündən sonra əlavə O(1), indeksə görə müraciət isə O(n)-dir.
  • Stek — LIFO (çağırışlar, undo, mötərizələr), növbə — FIFO (buferlər, BFS); hər ikisinin əməliyyatları O(1)-dir.
  • Dairəvi bufer indeksləri mod m ilə dolandırır və sabit yaddaşda növbə yaradır.
Dərsdə səhv və ya qeyri-dəqiqlik gördün?

Özünü yoxla

10 sual. Hər düzgün cavab XP qazandırır.

Sual 1 / 10

Sual 1 / 10. Tutumu 1-dən başlayan və hər dəfə iki dəfə artan dinamik massivə 64 element əlavə edilir. Cəmi neçə element köçürülür?