---
marp: true
theme: kurzus
paginate: true
footer: Adatszerkezetek · 3. hét · Tömbök
---

<!-- _class: cim -->
<!-- _paginate: false -->
<!-- _footer: "" -->

# Adatszerkezetek

## 3. hét – Tömbök: egy- és többdimenziós tömbök, tárolás, dinamikus tömb

Dr. Koczka Ferenc · Eszterházy Károly Egyetem · 2026

---

## Ismétlés

- **O-jelölés:** a lépésszám nagyságrendje – O(1), O(log n), O(n), O(n²)
- **Lineáris keresés:** O(n), bármilyen tömbön
- **Bináris keresés:** O(log n), rendezett tömbön, **közvetlen elérés** kell

### A mai óra kérdései

- Hogyan tárolja a gép a tömböt, és miért O(1) az elérés?
- Mennyibe kerül egy elem beszúrása vagy törlése?
- Hogyan lehet „bővíteni” egy statikus tömböt?

<!--
Időterv: tömb fogalma, tárolás 20' · műveletek 20' · 2D tömbök 20' · dinamikus tömb 25' · összefoglalás 5'
-->

---

## A tömb fogalma

A **tömb** azonos típusú elemek véges sorozata, amelynek elemeit **indexszel** érjük el.

| Tulajdonság | Tömb |
|---|---|
| Elemek típusa | **homogén** |
| Méret | **statikus** – létrehozáskor rögzül |
| Tárolás | **folytonos** – az elemek közvetlenül egymás után |
| Elérés | **közvetlen** – bármelyik elem O(1) idő alatt |
| Kapcsolat | **lineáris** |

Más néven: **vektor** (egydimenziós), **mátrix** (kétdimenziós)

---

<!-- _class: kicsi -->

## Tömbök Java és Go nyelven

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
int[] a = new int[5];        // 0-kkal
int[] p = {2, 3, 5, 7, 11};
p[0] = 1;
int n = p.length;            // 5

for (int x : p)
    System.out.print(x + " ");

int[] b = a;                 // UGYANAZ a tömb
int[] c = Arrays.copyOf(p, p.length);
```

- A tömb **objektum**, a változó referencia
- Alapérték: `0`, `0.0`, `false`, `null`

</div>
<div>

<span class="cimke go">Go</span>

```go
var a [5]int                 // 0-kkal
p := [5]int{2, 3, 5, 7, 11}
p[0] = 1
n := len(p)                  // 5

for _, x := range p {
    fmt.Print(x, " ")
}

b := a                       // MÁSOLAT!
s := []int{2, 3, 5}          // szelet
```

- A méret a **típus része**: `[5]int` ≠ `[6]int`
- A tömb **érték** – a gyakorlatban szeletet (`[]int`) használunk

</div>
</div>

---

## Tárolás a memóriában

![w:1000](kepek/h03_tomb_cim.svg)

Az *i*-edik elem címe **egyetlen számítással** megkapható:

> cím(A[i]) = kezdőcím + i · elemméret &nbsp;&nbsp;&nbsp; (0-tól indexelve)
> cím(A[i]) = kezdőcím + (i − 1) · elemméret &nbsp;&nbsp;&nbsp; (1-től indexelve)

Ezért **O(1)** az elérés – nem kell végigmenni az előző elemeken.

---

## Miért indul 0-tól az index?

- A 0-tól indexelés esetén az index az elem **eltolása** (offset) a tömb elejétől
- `A[0]` a kezdőcímen van, `A[3]` három elemmel arrébb
- C, Java, Go, Python: 0-tól · Pascal, Fortran, Lua, a matematika: 1-től

<div class="doboz figyelem">

A pszeudokódban **1-től** indexelünk, a programokban **0-tól**. Átíráskor:
`Ciklus i ← 1-től n-ig` → `for (int i = 0; i < n; i++)`

</div>

### Indexhatár-ellenőrzés

- Java: `ArrayIndexOutOfBoundsException` · Go: `panic: index out of range`
- C-ben nincs ellenőrzés: a program csendben **felülírja** a szomszédos memóriát – súlyos biztonsági hibák forrása

---

## Műveletek költsége

| Művelet | Lépésszám | Miért? |
|---|---|---|
| *i*-edik elem olvasása / írása | **O(1)** | címszámítás |
| Keresés (rendezetlen) | O(n) | lineáris keresés |
| Keresés (rendezett) | O(log n) | bináris keresés |
| Beszúrás a végére (ha van hely) | O(1) | |
| Beszúrás az elejére / közepére | **O(n)** | az elemeket el kell tolni |
| Törlés az elejéről / közepéről | **O(n)** | az elemeket el kell tolni |

<div class="doboz">

A tömb **gyors olvasásra** és **lassú módosításra** – ha sokat szúrunk be és törlünk a közepén, a **láncolt lista** (9. hét) jobb választás lehet.

</div>

---

## Beszúrás és törlés

![w:1000](kepek/h03_beszuras_torles.svg)

---

<!-- _class: kicsi -->

## Beszúrás és törlés – algoritmus

<div class="ket-hasab">
<div>

<span class="cimke pszeudo">Beszúrás a k-adik helyre</span>

```text
Eljárás Beszúr(A, n, k, x)
  // feltétel: n < kapacitás
  Ciklus i ← n-től k-ig visszafelé
    A[i + 1] ← A[i]
  Ciklus vége
  A[k] ← x
  n ← n + 1
Eljárás vége
```

<span class="cimke pszeudo">Törlés a k-adik helyről</span>

```text
Eljárás Töröl(A, n, k)
  Ciklus i ← k-tól n − 1-ig
    A[i] ← A[i + 1]
  Ciklus vége
  n ← n − 1
Eljárás vége
```

</div>
<div>

<span class="cimke java">Java</span>

```java
static int insert(int[] a, int n,
                  int pos, int x) {
    for (int i = n - 1; i >= pos; i--)
        a[i + 1] = a[i];
    a[pos] = x;
    return n + 1;
}
```

<div class="doboz figyelem">

Beszúráskor **hátulról** kell kezdeni a mozgatást! Elölről haladva minden elemet felülírnánk az első eltolt értékkel.

</div>

</div>
</div>

---

<!-- _class: kicsi -->

## Megfordítás és forgatás helyben

<div class="ket-hasab">
<div>

**Megfordítás** két indexszel – O(n), O(1) tár

```text
Eljárás Megfordít(A, n)
  i ← 1 ; j ← n
  Ciklus amíg i < j
    csere(A[i], A[j])
    i ← i + 1 ; j ← j − 1
  Ciklus vége
Eljárás vége
```

`[1 2 3 4 5]` → `[5 4 3 2 1]`

</div>
<div>

**Forgatás balra k hellyel** – három megfordítással

`[1 2 | 3 4 5]`, k = 2

1. első k elem megfordítása: `[2 1 | 3 4 5]`
2. a többi megfordítása: `[2 1 | 5 4 3]`
3. az egész megfordítása: `[3 4 5 1 2]` ✓

<span class="halvany">Segédtömb nélkül, O(n) lépésben.</span>

</div>
</div>

---

<!-- _class: fejezet -->

# Többdimenziós tömbök

---

## Kétdimenziós tömb (mátrix)

![w:1080](kepek/h03_matrix.svg)

- A memória **egydimenziós** – a mátrixot sorozattá kell „lapítani”
- **Sorfolytonos** tárolás (C, Java, Go): előbb az első sor, aztán a második …
- **Oszlopfolytonos** tárolás (Fortran, MATLAB): előbb az első oszlop …

---

## Címszámítás: általános képlet

Egy *N* × *M*-es mátrix (N sor, M oszlop), elemméret *s*, kezdőcím *k*:

| | 0-tól indexelve | 1-től indexelve |
|---|---|---|
| Sorfolytonos | k + (i · M + j) · s | k + ((i − 1) · M + (j − 1)) · s |
| Oszlopfolytonos | k + (j · N + i) · s | k + ((j − 1) · N + (i − 1)) · s |

<div class="doboz">

**Példa:** `int A[10][20]` (4 bájtos elemek), kezdőcím 2000, sorfolytonos, 0-tól indexelve.
cím(A[3][5]) = 2000 + (3 · 20 + 5) · 4 = 2000 + 260 = **2260**

</div>

Háromdimenziós tömb `A[i][j][l]`, méretek N × M × L: k + ((i · M + j) · L + l) · s

---

## 2D tömbök Java-ban: tömbök tömbje

![w:850](kepek/h03_java_jagged.svg)

```java
int[][] m = new int[3][4];          // 3 sor, mindegyik 4 hosszú
int[][] jagged = { {1, 2, 3}, {4, 5}, {6, 7, 8, 9} };
```

- Minden sor **külön objektum** → a sorok hossza eltérhet (*fogazott tömb*)
- `m.length` a sorok száma, `m[i].length` az *i*-edik sor hossza

---

## 2D tömbök Go-ban

<div class="ket-hasab">
<div>

**Valódi 2D tömb** – egy folytonos blokk

```go
var grid [3][4]int
grid[1][2] = 7
```

- A méret fordításkor ismert
- Pontosan sorfolytonos tárolás

</div>
<div>

**Szeletek szelete** – mint Java-ban

```go
m := make([][]int, rows)
for i := range m {
    m[i] = make([]int, cols)
}
```

- A méret futás közben adható meg
- A sorok hossza eltérhet

</div>
</div>

<div class="doboz tipp">

Mátrix bejárásakor a **sorfolytonos** sorrend (külső ciklus a sorokon) gyorsabb, mert jobban kihasználja a processzor gyorsítótárát (cache).

</div>

---

<!-- _class: kicsi -->

## Mátrixműveletek

<div class="ket-hasab">
<div>

**Főátló és mellékátló** – O(n)

```text
Ciklus i ← 1-től n-ig
  fő ← fő + A[i, i]
  mellék ← mellék + A[i, n − i + 1]
Ciklus vége
```

**Transzponálás** – O(n · m)

```text
Ciklus i ← 1-től n-ig
  Ciklus j ← 1-től m-ig
    T[j, i] ← A[i, j]
  Ciklus vége
Ciklus vége
```

</div>
<div>

**Mátrixszorzás** – (n×k) · (k×m), **O(n · k · m)**

```text
Ciklus i ← 1-től n-ig
  Ciklus j ← 1-től m-ig
    C[i, j] ← 0
    Ciklus x ← 1-től k-ig
      C[i, j] ← C[i, j] + A[i, x] · B[x, j]
    Ciklus vége
  Ciklus vége
Ciklus vége
```

Négyzetes mátrixokra **O(n³)** – három egymásba ágyazott ciklus.

</div>
</div>

---

<!-- _class: fejezet -->

# Dinamikus tömb

---

## A probléma: a tömb mérete rögzített

- Gyakran **nem tudjuk előre**, hány elemet kell tárolni (pl. beolvasott adatok)
- Túl kicsi tömb → nem fér el · túl nagy tömb → pazarlás

**Megoldás: dinamikus tömb** – egy tömb, amelyet szükség esetén **nagyobbra cserélünk**

- `size` (hossz): hány elem van benne ténylegesen
- `capacity` (kapacitás): mekkora a háttértömb

Java: `ArrayList` · Go: szelet + `append` · C++: `vector` · Python: `list`

---

## A dinamikus tömb működése

![w:1000](kepek/h03_dinamikus.svg)

- Ha egyesével növelnénk: 1 + 2 + 3 + … + n = **O(n²)** másolás összesen
- **Duplázással:** 1 + 2 + 4 + … + n < 2n → összesen O(n), elemenként **O(1)**

---

<!-- _class: kicsi -->

## Saját dinamikus tömb

<div class="ket-hasab">
<div>

<span class="cimke java">Java</span>

```java
class DynamicArray {
    private int[] data = new int[1];
    private int size = 0;

    void add(int x) {
        if (size == data.length) {
            int[] bigger =
                new int[2 * data.length];
            for (int i = 0; i < size; i++)
                bigger[i] = data[i];
            data = bigger;
        }
        data[size++] = x;
    }
    int get(int i) { return data[i]; }
}
```

</div>
<div>

<span class="cimke go">Go</span>

```go
type DynamicArray struct {
    data []int
    size int
}

func (d *DynamicArray) Add(x int) {
    if d.size == len(d.data) {
        bigger := make([]int, 2*len(d.data))
        copy(bigger, d.data[:d.size])
        d.data = bigger
    }
    d.data[d.size] = x
    d.size++
}
```

Mérés: 1 000 000 `add` → **1 048 575** másolás, elemenként **1,05**

</div>
</div>

---

## Go szelet: hossz, kapacitás, háttértömb

![w:1000](kepek/h03_go_slice.svg)

- A szelet három adatból áll: **mutató** a háttértömbre, **hossz** (`len`), **kapacitás** (`cap`)
- `append` csak akkor foglal új tömböt, ha a kapacitás elfogyott
- Ezért mindig így írjuk: `s = append(s, x)` – az eredményt vissza kell tenni!

---

## Java `ArrayList`

```java
ArrayList<Integer> list = new ArrayList<>();
list.add(5);          // végére – amortizáltan O(1)
list.add(0, 3);       // beszúrás az elejére – O(n)
list.get(1);          // olvasás – O(1)
list.set(1, 9);       // írás – O(1)
list.remove(0);       // törlés index szerint – O(n)
list.size();          // elemszám
```

- Csak **objektumot** tárol: `int` helyett `Integer` (automatikus be- és kicsomagolás)
- Belül egy `Object[]` tömb, amit 1,5-szeresére növel, ha betelik

---

## Összefoglalás

- A tömb **homogén, statikus, folytonos, közvetlen elérésű** adatszerkezet
- Címszámítás: `kezdőcím + index · elemméret` → elérés **O(1)**
- Beszúrás és törlés a közepén **O(n)** – elemeket kell mozgatni
- Mátrix: **sorfolytonos** tárolás, cím = k + (i · M + j) · s
- Java: 2D tömb = tömbök tömbje · Go: `[N][M]T` vagy `[][]T`
- **Dinamikus tömb:** kapacitásduplázás → hozzáfűzés amortizáltan **O(1)**

**Következő hét:** stringek – karakterek sorozata, kódolás, műveletek, mintakeresés.

---

## Ellenőrző kérdések

1. Igaz vagy hamis: a tömb elemei szétszórtan helyezkednek el a memóriában.
2. Mekkora a lépésszáma egy *n* elemű tömb első elemének törlésének?
3. Egy `int A[5][8]` mátrix sorfolytonosan van tárolva a 100-as címtől, 4 bájtos elemekkel, 0-tól indexelve. Mi az `A[2][3]` elem címe?
4. Miért kell beszúráskor hátulról kezdeni az elemek mozgatását?
5. Miért duplázzuk a dinamikus tömb kapacitását, és miért nem növeljük eggyel?
6. Mit ír ki? `s := []int{1,2,3}; t := s; t[0] = 9; fmt.Println(s[0])`

<!--
Megoldás: 1. H (folytonos)  2. O(n)  3. 100 + (2·8 + 3)·4 = 100 + 76 = 176
4. Különben az első eltolás felülírja a következő elemet, és mindenhová ugyanaz az érték kerül.
5. Eggyel növelve összesen O(n²) másolás, duplázva O(n) – elemenként amortizált O(1).
6. 9 – a szelet értékadása nem másolja az elemeket (közös háttértömb).
-->

---

<!-- _class: fejezet -->
<!-- _footer: "" -->

# Gyakorlat

---

<!-- _class: gyak -->

## Bemutató programok

| Program | Java | Go | Mit mutat? |
|---|---|---|---|
| Alapok | `ArrayBasics.java` | `h03/arraybasics` | létrehozás, alapértékek, indexhatár, másolás |
| Műveletek | `ArrayOps.java` | `h03/arrayops` | beszúrás, törlés, megfordítás, forgatás |
| Mátrix | `Matrix.java` | `h03/matrix` | átlók, transzponálás, szorzás, fogazott tömb |
| Dinamikus tömb | `DynamicArray.java` | `h03/dynarray` | kapacitásduplázás, másolások száma, `append` |

<div class="doboz tipp">

A `dynarray` Go programban figyeld meg, hogyan nő a beépített `append` kapacitása, és mi történik a közös háttértömbbel!

</div>

---

<!-- _class: gyak -->

## Feladatok

1. **Átlag:** számítsd ki egy egészekből álló tömb elemeinek átlagát!
2. **Tartalmazás:** döntsd el, hogy a tömb tartalmaz-e egy adott értéket!
3. **Második legnagyobb:** keresd meg a második legnagyobb (különböző) elemet **egyetlen** bejárással!
4. **Ismétlődések törlése:** egy **rendezett** tömbből töröld helyben az ismétlődő elemeket, és add vissza az új hosszt! (`[1,1,2,3,3,3,5] → [1,2,3,5]`)
5. **Összefésülés:** fésülj össze két rendezett tömböt egy rendezett tömbbé O(n + m) lépésben!
6. **Sor- és oszlopösszegek:** számítsd ki egy mátrix minden sorának és oszlopának összegét!
7. **Spirál:** írd ki egy mátrix elemeit spirál sorrendben! (`1 2 3 6 9 8 7 4 5`)

Megoldások: `Exercises03.java`, `h03/exercises`

---

<!-- _class: gyak -->

## Házi feladat

1. Egészítsd ki a saját `DynamicArray` osztályt `insert(i, x)` és `remove(i)` műveletekkel! Mi a lépésszámuk?
2. Írd meg a `remove` műveletet úgy, hogy ha a tömb **negyedéig** ürül, a kapacitás feleződjön! Miért nem már félig ürült állapotban felezünk?
3. Írj programot, amely egy *n* × *n*-es mátrixot **helyben** 90 fokkal elforgat az óramutató járásával megegyezően! (Tipp: transzponálás + a sorok megfordítása.)
4. Számold ki: `double T[50][40]` (8 bájtos elemek) oszlopfolytonosan, 1-től indexelve, kezdőcím 5000. Mi a `T[12][7]` címe?

<!--
Megoldás:
1. insert O(n) (eltolás + esetleg duplázás), remove O(n).
2. Ha félig ürüléskor felezünk, akkor a határon váltakozó add/remove minden lépésben átméretezést okozna (O(n) műveletenként). Negyednél felezve az amortizált költség O(1) marad.
3. for i: for j>i: csere(m[i][j], m[j][i]); majd minden sor megfordítása.
4. 5000 + ((7−1)·50 + (12−1))·8 = 5000 + (300 + 11)·8 = 5000 + 2488 = 7488
-->