Java programmētāji izmanto datu struktūras datu glabāšanai un organizēšanai, un mēs izmantojam algoritmus, lai manipulētu ar datiem šajās struktūrās. Jo vairāk jūs saprotat par datu struktūrām un algoritmiem un to, kā tie darbojas kopā, jo efektīvākas būs jūsu Java programmas.
Šajā apmācībā tiek uzsākta īsa sērija, kurā tiek ieviestas datu struktūras un algoritmi. 1. daļā jūs uzzināsiet, kas ir datu struktūra un kā datu struktūras tiek klasificētas. Jūs arī uzzināsiet, kas ir algoritms, kā tiek attēloti algoritmi un kā izmantot laika un telpas sarežģītības funkcijas, lai salīdzinātu līdzīgus algoritmus. Kad būsiet apguvis šos pamatus, 2. daļā būsiet gatavs uzzināt par meklēšanu un šķirošanu ar viendimensiju masīviem.
Kas ir datu struktūra?
Datu struktūru pamatā ir abstrakti datu tipi (ADT), kurus Vikipēdija definē šādi:
[A] matemātiskais modelis datu tipiem, kur datu tipu nosaka tā uzvedība (semantika) no datu lietotāja viedokļa, īpaši attiecībā uz iespējamām vērtībām, iespējamām darbībām ar šāda veida datiem un uzvedību no šīm operācijām.ADT nav svarīgi, vai atmiņā attēlotas tās vērtības vai kā tiek īstenotas tās darbības. Tas ir kā Java interfeiss, kas ir datu tips, kas ir atvienots no jebkuras ieviešanas. Turpretī a datu struktūra ir konkrēta viena vai vairāku ADT ieviešana, līdzīgi kā Java klases ievieš saskarnes.
ADT piemēri ir Darbinieks, Transportlīdzeklis, Masīvs un Saraksts. Apsveriet sarakstu ADT (pazīstams arī kā Sequence ADT), kurā aprakstīta sakārtota elementu kolekcija, kam ir kopīgs tips. Katram šīs kolekcijas elementam ir sava pozīcija, un ir atļauti elementu dublikāti. Pamatdarbības, ko atbalsta saraksta ADT, ir šādas:
- Jauna un tukša saraksta izveide
- Vērtības pievienošana saraksta beigām
- Vērtības ievietošana sarakstā
- Vērtības dzēšana no saraksta
- Atkārtojas pār sarakstu
- Saraksta iznīcināšana
Datu struktūras, kas var ieviest ADT sarakstu, ietver fiksēta lieluma un dinamiski izmērītus viendimensiju masīvus un atsevišķi saistītus sarakstus. (Jūs iepazīstināsit ar masīviem 2. daļā un saistītajiem sarakstiem 3. daļā.)
Datu struktūru klasificēšana
Ir daudz dažādu datu struktūru, sākot no atsevišķiem mainīgajiem līdz masīviem vai saistītiem objektu sarakstiem, kas satur vairākus laukus. Visas datu struktūras var klasificēt kā primitīvus vai agregātus, un dažas tās klasificē kā konteinerus.
Primitīvi pret agregātiem
Vienkāršākā veida datu struktūra glabā atsevišķus datu objektus; piemēram, mainīgais, kas saglabā Būla vērtību, vai mainīgais, kas glabā veselu skaitli. Es atsaucos uz tādām datu struktūrām kā primitīvi.
Daudzas datu struktūras spēj uzglabāt vairākus datu objektus. Piemēram, masīvs var glabāt vairākus datu vienumus dažādos laika nišos, un objekts caur saviem laukiem var saglabāt vairākus datu vienumus. Es atsaucos uz šīm datu struktūrām kā agregāti.
Visas datu struktūras, kuras aplūkosim šajā sērijā, ir apkopotas.
Konteineri
Viss, no kura tiek glabāti un izgūti datu vienumi, var tikt uzskatīts par datu struktūru. Piemēri ietver datu struktūras, kas iegūtas no iepriekš minētajiem darbiniekiem, transportlīdzekļiem, masīviem un saraksta ADT.
Daudzas datu struktūras ir paredzētas dažādu entītiju aprakstīšanai. Gadījumi Darbinieks klase ir datu struktūras, kas pastāv, piemēram, dažādu darbinieku raksturošanai. Turpretī dažas datu struktūras pastāv kā vispārējas glabāšanas tvertnes citām datu struktūrām. Piemēram, masīvā var saglabāt primitīvas vērtības vai objektu atsauces. Es atsaucos uz šo pēdējo datu struktūru kategoriju kā konteineri.
Visas datu struktūras, kuras aplūkosim šajā sērijā, ir ne tikai apkopojumi, bet arī konteineri.
Datu struktūras un algoritmi Java kolekcijās
Java kolekciju ietvars atbalsta daudzu veidu uz konteineriem orientētas datu struktūras un saistītos algoritmus. Šī sērija palīdzēs jums labāk izprast šo ietvaru.
Dizaina modeļi un datu struktūras
Diezgan bieži ir izmantoti dizaina modeļi, lai iepazīstinātu universitātes studentus ar datu struktūrām. Brauna universitātes dokumentā ir apskatīti vairāki dizaina modeļi, kas ir noderīgi augstas kvalitātes datu struktūru projektēšanai. Cita starpā dokuments parāda, ka Adapter modelis ir noderīgs kaudzīšu un rindu projektēšanai. Demonstrācijas kods ir parādīts 1. sarakstā.
Saraksts 1. Adaptera modeļa izmantošana kaudzēm un rindām (DequeStack.java)
publiskā klase DequeStack īsteno Stack {Deque D; // tur kaudzes elementi public DequeStack () {D = new MyDeque (); } @Orride public int size () {return D.size (); } @Orride public Boolean isEmpty () {return D.isEmpty (); } @Orride public void push (Object obj) {D.insertLast (obj); } @Orride public Object top () throws StackEmptyException {try {return D.lastElement (); } catch (DequeEmptyException err) {mest jaunu StackEmptyException (); }} @Orride public Object pop () throws StackEmptyException {try {return D.removeLast (); } catch (DequeEmptyException err) {mest jaunu StackEmptyException (); }}}1. saraksta fragmenti ir Brauna universitātes dokumenti DequeStack klase, kas demonstrē Adaptera modeli. Pieraksti to Kaudze un Deque ir saskarnes, kas apraksta Stack un Deque ADT. MyDeque ir klase, kas īsteno Deque.
Svarīgākas saskarnes metodes
Sākotnējais kods, uz kura balstās 1. saraksts, neuzrādīja pirmkodu Kaudze, Deque, un MyDeque. Skaidrības labad es esmu ieviesis @ Pārvarēt anotācijas, lai parādītu, ka visas DequeStacknekonstruktora metodes ignorē Kaudze metodes.
DequeStack pielāgojas MyDeque lai to varētu īstenot Kaudze. Viss no DequeStackmetode ir vienas līnijas zvani uz Deque saskarnes metodes. Tomēr ir neliela grumbiņa, kurā Deque izņēmumi tiek pārveidoti par Kaudze izņēmumiem.
Kas ir algoritms?
Vēsturiski kā matemātiskās aprēķināšanas rīku izmantotie algoritmi ir cieši saistīti ar datorzinātnēm un jo īpaši ar datu struktūrām. An algoritms ir instrukciju secība, kas izpilda uzdevumu ierobežotā laika posmā. Algoritma īpašības ir šādas:
- Saņem nulles vai vairāk ieejas
- Izgatavo vismaz vienu izvadi
- Sastāv no skaidrām un nepārprotamām instrukcijām
- Pārtraucas pēc noteikta skaita darbību
- Vai tas ir pietiekami vienkāršs, lai cilvēks to varētu paveikt, izmantojot zīmuli un papīru
Ņemiet vērā, ka, lai arī programmas pēc būtības var būt algoritmiskas, daudzas programmas nebeidz darboties bez ārējas iejaukšanās.
Daudzas kodu sekvences kvalificējas kā algoritmi. Viens piemērs ir kodu secība, kas izdrukā pārskatu. Vēl slavenāk, ka Eiklida algoritmu izmanto, lai aprēķinātu matemātiski lielāko kopīgo dalītāju. Varētu pat apgalvot, ka datu struktūras pamatdarbības (piemēram, glabāt vērtību masīva slotā) ir algoritmi. Šajā sērijā lielākoties pievērsīšos augstāka līmeņa algoritmiem, ko izmanto datu struktūru apstrādei, piemēram, bināro meklēšanas un matricu reizināšanas algoritmiem.
Blokshēmas un pseidokods
Kā jūs pārstāvat algoritmu? Rakstot kodu, pirms pilnībā izprotat tā algoritmu, var rasties kļūdas, un kas tad ir labāka alternatīva? Divas iespējas ir blokshēmas un pseidokods.
Blokshēmu izmantošana algoritmu attēlošanai
A blokshēma ir algoritma vadības plūsmas vizuāls attēlojums. Šis attēlojums ilustrē paziņojumus, kas jāizpilda, lēmumus, kas jāpieņem, loģisko plūsmu (iterācijas un citiem mērķiem) un terminālus, kas norāda sākuma un beigu punktus. 1. attēlā ir parādīti dažādi simboli, kurus blokshēmas izmanto algoritmu vizualizēšanai.
Apsveriet algoritmu, kas inicializē skaitītāju 0, rakstzīmes lasa līdz jaunai rindai (\ n) ir redzams, palielina skaitītāju katram izlasītajam cipara rakstzīmei un izdrukā skaitītāja vērtību pēc jaunās līnijas rakstzīmes nolasīšanas. 2. zīmējuma blokshēma parāda šī algoritma vadības plūsmu.
Bloku diagrammas vienkāršība un spēja vizuāli attēlot algoritma vadības plūsmu (tā, lai to būtu viegli sekot) ir tās galvenās priekšrocības. Blokshēmām ir arī vairāki trūkumi:
- Ļoti detalizētās blokshēmās ir viegli ieviest kļūdas vai neprecizitātes, jo garlaicība ir saistīta ar to zīmēšanu.
- Plūsmas diagrammas simbolu novietošana, iezīmēšana un savienošana prasa laiku, pat izmantojot rīkus, lai paātrinātu šo procesu. Šī kavēšanās var palēnināt izpratni par algoritmu.
- Blokshēmas pieder strukturētās programmēšanas laikmetam un nav tik noderīgas objektorientētā kontekstā. Turpretī vienotā modelēšanas valoda (UML) ir piemērotāka objektorientētu vizuālo attēlojumu veidošanai.
Pseidokoda izmantošana algoritmu attēlošanai
Alternatīva blokshēmām ir pseidokods, kas ir teksta attēlojums algoritmam, kas tuvina galīgo pirmkodu. Pseidokods ir noderīgs, lai ātri pierakstītu algoritma attēlojumu. Tā kā sintakse neraizējas, pseidokoda rakstīšanai nav stingru noteikumu.
Rakstot pseidokodu, jums jācenšas panākt konsekvenci. Konsekvence ļaus daudz vieglāk pārveidot pseidokodu reālā avota kodā. Piemēram, ņemiet vērā iepriekšējās pretorientētās blokshēmas pseidokoda attēlojumu:
DECLARE CHARACTER ch = '' DECLARE INTEGER count = 0 NOLASĪT ch, ja ch GE '0' UN ch LE '9' TAD skaitlis = skaits + 1 BEIGS, JA LĪDZ CH EQ 'Pseidokods vispirms uzrāda pāris DEKLARĒT paziņojumi, kas ievieš mainīgos ch un skaitīt, inicializēts pēc noklusējuma vērtībām. Pēc tam tajā tiek parādīts a DARI cilpa, kas tiek izpildīta LĪDZch satur \ n (jaunās līnijas raksturs), kurā brīdī cilpa beidzas un a PRINT pārskata izvadi skaitītvērtība.
Par katru cikla atkārtojumu LASIET izraisa rakstzīmi, kas tiek nolasīta no tastatūras (vai varbūt faila - šajā gadījumā nav svarīgi, kas ir pamatā esošais ievades avots) un piešķirts ch. Ja šī rakstzīme ir cipars (viens no 0 cauri 9), skaitīt tiek palielināts par 1.
Pareiza algoritma izvēle
Jūsu izmantotās datu struktūras un algoritmi kritiski ietekmē divus jūsu lietojumprogrammu faktorus:
- Atmiņas izmantošana (datu struktūrām).
- CPU laiks (algoritmiem, kas mijiedarbojas ar šīm datu struktūrām).
No tā izriet, ka jums īpaši jāņem vērā algoritmi un datu struktūras, ko izmantojat lietojumprogrammām, kas apstrādās daudz datu. Tie ietver lietojumprogrammas, kuras izmanto lielajiem datiem, un lietu internetu.
Atmiņas un CPU līdzsvarošana
Izvēloties datu struktūru vai algoritmu, jūs dažreiz atklājat apgrieztās attiecības starp atmiņas lietojumu un CPU laiku: jo mazāk atmiņas izmanto datu struktūra, jo vairāk ar CPU laiku saistītiem algoritmiem jāapstrādā datu struktūras datu vienumi. Turklāt, jo vairāk atmiņas izmanto datu struktūra, jo mazāk ar CPU laiku saistītiem algoritmiem būs jāapstrādā datu vienumi, lai iegūtu ātrākus algoritmu rezultātus.
Cik vien iespējams, jums vajadzētu censties līdzsvarot atmiņas izmantošanu ar CPU laiku. Šo uzdevumu varat vienkāršot, analizējot algoritmus, lai noteiktu to efektivitāti. Cik labi viens algoritms darbojas pret citu līdzīga rakstura algoritmu? Atbildēšana uz šo jautājumu palīdzēs jums izdarīt labas izvēles, ņemot vērā izvēli starp vairākiem algoritmiem.
Algoritma efektivitātes mērīšana
Daži algoritmi darbojas labāk nekā citi. Piemēram, binārās meklēšanas algoritms gandrīz vienmēr ir efektīvāks nekā lineārās meklēšanas algoritms - kaut ko, ko jūs pats redzēsiet 2. daļā. Jūs vēlaties izvēlēties visefektīvāko algoritmu savas lietojumprogrammas vajadzībām, taču šī izvēle var nebūt tik acīmredzama kā jūs domājat.
Piemēram, ko tas nozīmē, ja Selection Sort algoritms (ieviests 2. daļā) prasa 0,4 sekundes, lai kārtotu 10 000 veselus skaitļus attiecīgajā mašīnā? Šis etalons ir derīgs tikai šai konkrētajai mašīnai, algoritma konkrētajai ieviešanai un ievades datu lielumam.
Kā datorzinātnieks mēs izmantojam laika sarežģītību un telpas sarežģītību, lai izmērītu algoritma efektivitāti, destilējot tos sarežģītības funkcijas abstraktai ieviešanai un izpildlaika vides detaļām. Sarežģītības funkcijas atklāj algoritma laika un vietas prasību dispersiju, pamatojoties uz ievades datu daudzumu:
- A laika sarežģītības funkcija mēra algoritmu laika sarežģītība- nozīmē, cik ilgi algoritms ir jāpabeidz.
- A telpas sarežģītības funkcija mēra algoritmu kosmosa sarežģītība- nozīmē atmiņas pieskaitāmo izmēru daudzumu, kas algoritmam nepieciešams sava uzdevuma veikšanai.
Abas sarežģītības funkcijas ir balstītas uz ievades lielumu (n), kas kaut kā atspoguļo ievades datu daudzumu. Apsveriet šādu pseidokodu masīva drukāšanai:
DEKLARĀT INTEGER i, x [] = [10, 15, -1, 32] PAR i = 0 līdz GARUMAM (x) - 1 PRINT x [i] NEXT i ENDLaika sarežģītības un laika sarežģītības funkcijas
Jūs varat izteikt šī algoritma laika sarežģītību, norādot laika sarežģītības funkciju t (n) = an+ b, kur a (konstants reizinātājs) norāda laika daudzumu, lai pabeigtu vienas cilpas atkārtojumu, un b apzīmē algoritma iestatīšanas laiku. Šajā piemērā laika sarežģītība ir lineāra.
