Sissejuhatus andmestruktuuridesse ja algoritmidesse

1: Mis see on?

1. Mis on andmestruktuur: andmete paigutus arvutimälus või ketas (massiiv, lingitud nimekiri, virn, binaarpuu jne).

2. Mis on algoritm: erinevate andmete töötlemine nende struktuuridega.

2: Funktsioon

1. Reaalse elu andmete salvestamine: personaliosakond sisestab töötaja faili asjakohase info, sisestab uute toodete andmed supermarketis salvestussüsteemi jne, ning need süsteemid koosnevad paljudest andmestruktuuridest.

2. Arendaja tööriistad: mida kasutab programm ise, andmestruktuure kasutatakse mõningate programmiarenduse toimingute lihtsustamiseks.

3. Modelleerimine: Diagrammide kasutamine võimaldab luua mägede teekaarte, lennukite marsruutide kaarte jne.

Andmesalvestusstruktuuride massiivi

a. Massiivid on kõige lihtsamad andmesalvestusstruktuurid võrreldes teiste struktuuridega ning need on lihtsad ja kergesti mõistetavad.

Diagramm viib sind selle struktuuri analüüsini.

Otsing: Oletame, et defineeritakse tõusev järjestatud massiivi – kui otsitakse väärtust 80, algab indeks nullist kuni 7 leiab vastava väärtuse.

b. Kuidas mängida

Süntaks 1: dataType[] arrayRefVar = new dataType[arraySize];

Süntaks 2: dataType[] arrayRefVar = {value0, value1, ..., valuek};

Teine tõhus otsing massiivi suhtelise lineaarse otsingu jaoks – dikotoomne otsing

Dihhotoomse algoritmi eeldus on, et massiiv on korrapäraselt sorteeritud ning kõige klassikalisem on arvamismäng 1-100.

Algoritm on järgmine:

1. Määra otsinguvahemik front=0, end=N-1 ja arvuta mid=(front+end)/2.

2. Kui a[mid]=x või front>=end, siis otsing lõpeb; Vastasel juhul jätka allapoole.

3. Kui a[mid]x, võib leitava elemendi väärtus olla ainult vahemikus, mis on väiksem kui keskmine element, määra lõpp-väärtuseks keskmine 1, arvuta keskmine uuesti ja liigume sammu 2-le.