Uvod v podatkovne strukture in algoritme

1: Kaj je?

1. Kaj je podatkovna struktura: razporeditev podatkov v računalniškem pomnilniku ali disku (tabela, povezani seznam, sklad, binarno drevo itd.).

2. Kaj je algoritem: različna obdelava podatkov s temi strukturami.

2: Funkcija

1. Shranjevanje podatkov v resničnem življenju: kadrovska služba vnaša relevantne podatke iz dosjeja zaposlenega, vnaša podatke o novih izdelkih v supermarketu v sistem shranjevanja itd., ti sistemi pa so sestavljeni iz številnih podatkovnih struktur.

2. Orodja za razvijalce: podatkovne strukture, ki jih uporablja sam program, se uporabljajo za poenostavitev nekaterih operacij razvoja programa.

3. Modeliranje: Uporaba diagramov lahko ustvari gorske cestne zemljevide, letalske poti letal itd.

Niz struktur za shranjevanje podatkov

a. Polja so najpreprostejše strukture za shranjevanje podatkov v primerjavi z drugimi strukturami in so preproste ter lahko razumljive.

Diagram vas bo popeljal v analizo te strukture.

Iskanje: Predpostavimo, da je definirano naraščajoče urejeno polje, pri iskanju vrednosti 80 indeks začne pri 0, dokler 7 ne najde ustrezne vrednosti.

b. Kako igrati

Sintaksa 1: dataType[] arrayRefVar = new dataType[arraySize];

Sintaksa 2: dataType[] arrayRefVar = {value0, value1, ..., valuek};

Še eno učinkovito iskanje za relativno linearno iskanje po polju je dikotomno iskanje

Predpostavka dikotomnega algoritma je, da je polje urejeno na urejen način, najbolj klasična pa je igra ugibanja od 1 do 100.

Algoritem je naslednji:

1. Določite območje iskanja=0, end=N-1 in izračunajte mid=(front+end)/2.

2. Če je a[mid]=x ali front>=end, se iskanje konča; V nasprotnem primeru nadaljuj navzdol.

3. Če je a[sredina]x, je vrednost elementa, ki ga najdemo, lahko le znotraj območja, manjšega od srednjega elementa, dodelimo vrednost sredine 1 koncu, ponovno izračunamo srednjo vrednost in premaknite se na korak 2.