Programmēšana

Datu struktūras un algoritmi Java, 3. daļa: Daudzdimensionāli masīvi

Datu struktūras un algoritmi Java 2. daļā ieviesa dažādas metodes viendimensiju masīvu meklēšanai un šķirošanai, kas ir vienkāršākie masīvi. Šajā apmācībā jūs izpētīsit daudzdimensiju masīvus. Es jums parādīšu trīs veidus, kā izveidot daudzdimensiju masīvus, pēc tam jūs uzzināsiet, kā izmantot Matricas reizināšanas algoritmu elementu reizināšanai divdimensiju masīvā. Es iepazīstināšu arī ar nedrošiem masīviem, un jūs uzzināsiet, kāpēc tie ir populāri lielo datu lietojumprogrammām. Visbeidzot, mēs apsvērsim jautājumu par to, vai masīvs ir vai nav Java objektu.

Šis raksts ir paredzēts 4. daļai, kurā ir ievadīta meklēšana un kārtošana, izmantojot atsevišķi saistītos sarakstus.

Daudzdimensionāli masīvi

A daudzdimensionāls masīvs katru masīva elementu saista ar vairākiem indeksiem. Visbiežāk izmantotais daudzdimensionālais masīvs ir divdimensiju masīvs, pazīstams arī kā a tabula vai matrica. Divdimensiju masīvs saista katru tā elementu ar diviem indeksiem.

Divdimensionālu masīvu mēs varam konceptualizēt kā taisnstūrveida elementu režģi, kas sadalīti rindās un kolonnās. Mēs izmantojam (rinda, kolonna) apzīmējums elementa identificēšanai, kā parādīts 1. attēlā.

Tā kā divdimensiju bloki tiek izmantoti tik bieži, es pievērsīšos tiem. Ko jūs uzzināt par divdimensiju masīviem, var vispārināt uz augstākas dimensijas.

Divdimensiju masīvu izveidošana

Divdimensiju masīva izveidošanai Java ir trīs paņēmieni:

  • Inicializētāja izmantošana
  • Izmantojot atslēgvārdu jauns
  • Izmantojot atslēgvārdu jauns ar inicializatoru

Inicializētāja izmantošana, lai izveidotu divdimensiju masīvu

Tikai inicializētāja pieejai divdimensiju masīva izveidošanai ir šāda sintakse:

'{' [rowInitializer (',' rowInitializer)*] '}'

rowInitializer ir šāda sintakse:

'{' [izteikt (',' izteikt)*] '}'

Šajā sintaksē teikts, ka divdimensiju masīvs ir izvēles, ar komatiem atdalīts rindu inicializētāju saraksts, kas parādās starp atvērto un aizvērto zīmju rakstzīmēm. Turklāt katras rindas inicializētājs ir neobligāts, ar komatiem atdalīts izteicienu saraksts, kas parādās starp atvērto un aizvērto rakstzīmju rakstzīmēm. Tāpat kā viendimensiju masīvi, arī visām izteiksmēm ir jānodrošina savietojamības veidi.

Šeit ir divdimensiju masīva piemērs:

{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }

Šis piemērs izveido tabulu ar divām rindām un trim kolonnām. 2. attēlā parādīts šīs tabulas konceptuāls skats kopā ar atmiņas skatu, kas parāda, kā Java šo (un katru) tabulu izklāj atmiņā.

2. attēlā redzams, ka Java attēlo divdimensiju masīvu kā viendimensiju rindu masīvu, kura elementi atsaucas uz viendimensiju kolonnu masīviem. Rindu indekss identificē kolonnu masīvu; kolonnas indekss identificē datu vienumu.

Atslēgvārds tikai izveidošana

Atslēgvārds jauns piešķir atmiņu divdimensiju masīvam un atgriež tā atsauci. Šai pieejai ir šāda sintakse:

"jauns" tips '[' int_expr1 ']' '['int_expr2 ']'

Šajā sintaksē teikts, ka divdimensiju masīvs ir (pozitīvā) reģions int_expr1 rindas elementi un (pozitīvi) int_expr2 kolonnu elementi, kuriem visiem ir viens un tas pats tips. Turklāt visi elementi tiek nulle. Lūk, piemērs:

jauns dubultā [2] [3] // Izveidojiet divu rindu pa trīs kolonnu tabulu.

Atslēgvārda jauna un inicializētāja izveide

Atslēgvārds jauns ar inicializētāja pieeju ir šāda sintakse:

"jauns" tips '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'

kur rowInitializer ir šāda sintakse:

'{' [izteikt (',' izteikt)*] '}'

Šī sintakse apvieno divus iepriekšējos piemērus. Tā kā elementu skaitu var noteikt no komatiem atdalītiem izteicienu sarakstiem, jūs to nenorādat int_pateikt starp kvadrātiekavu pāri. Šeit ir piemērs:

jauns dubultnieks [] [] {{20.5, 30.6, 28.3}, {-38,7, -18,3, -16,2}}

Divdimensiju masīvi un masīvu mainīgie

Pats par sevi jaunizveidots divdimensiju masīvs ir bezjēdzīgs. Tās atsauce jāpiešķir masīva mainīgais saderīga tipa vai nu tieši, vai izmantojot metodes zvanu. Šīs sintakses parāda, kā jūs deklarējat šo mainīgo:

tipsvar_name '[' ']' '[' ']' tips '[' ']' '[' ']' var_name

Katra sintakse deklarē masīva mainīgo, kurā glabājas atsauce uz divdimensiju masīvu. Vēlams kvadrātiekavas ievietot aiz tips. Apsveriet šādus piemērus:

dubultā [] [] temperatūra1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; dubultā [] [] temperatūra2 = jauna dubultā [2] [3]; dubultā [] [] temperatūra3 = jauna dubultā [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}};

Tāpat kā viendimensiju masīva mainīgie, divdimensiju masīva mainīgie ir saistīti ar .garums rekvizīts, kas atgriež rindas masīva garumu. Piemēram, temperatūras1.garums atgriež 2. Katrs rindas elements ir arī masīva mainīgais ar a .garums rekvizīts, kas atgriež kolonnu masīva kolonnu skaitu, kas piešķirts rindas elementam. Piemēram, temperatūras1 [0] .garums atgriež 3.

Ņemot vērā masīva mainīgo, varat piekļūt jebkuram divdimensiju masīva elementam, norādot izteiksmi, kas atbilst šādai sintaksei:

masīvs_var '[' rindas_indekss ']' '[' col_index ']'

Abi indeksi ir pozitīvi ints, kas svārstās no 0 līdz vienam mazāk par vērtību, kas atgriezta no attiecīgā .garums īpašības. Apsveriet divus nākamos piemērus:

dubultā temp = temperatūra1 [0] [1]; // Iegūstiet vērtību. temperatūra1 [0] [1] = 75,0; // Iestatīt vērtību.

Pirmais piemērs atgriež vērtību pirmās rindas otrajā kolonnā (30.6). Otrais piemērs aizstāj šo vērtību ar 75.0.

Ja norādāt negatīvu indeksu vai indeksu, kas ir lielāks vai vienāds ar masīva mainīgā atgriezto vērtību .garums īpašumu, Java izveido un iemet ArrayIndexOutOfBoundsException objekts.

Divdimensiju masīvu reizināšana

Vienas matricas reizināšana ar citu matricu ir izplatīta darbība jomās, sākot no datorgrafikas, līdz ekonomikai un transporta nozarei. Izstrādātāji šai operācijai parasti izmanto Matricas reizināšanas algoritmu.

Kā darbojas matricas reizināšana? Ļaujiet A attēlot matricu ar m rindas un lpp kolonnas. Tāpat ļaujiet B attēlot matricu ar lpp rindas un n kolonnas. Reiziniet A ar B, lai iegūtu matricu C ar m rindas un n kolonnas. Katrs cij ierakstu C iegūst, reizinot visus A ierakstus ie rindā ar atbilstošajiem ierakstiem B j kolonnā, pēc tam pievienojot rezultātus. Šīs operācijas ilustrē 3. attēls.

Kreisās matricas kolonnām jābūt vienādām ar labās matricas rindām

Matricas reizināšanai ir nepieciešams, lai kolonnu (p) skaits kreisajā matricā (A) būtu vienāds ar rindu skaitu (p) labajā matricā (B). Pretējā gadījumā šis algoritms nedarbosies.

Šis pseidokods matricas reizināšanu izsaka tabulas kontekstā 2 rindas pa 2 kolonnām un 2 rindas pa 1 kolonnām. (Atgādināsim, ka es ieviesu pseidokodu 1. daļā.)

// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == DEKLARĒT INTEGRU a [] [] = [10, 30] [20, 40] DEKLARĀT INTEGRU b [] [] = [5, 7] PAZIŅOTI INTEGRU // Rindu skaits kreisajā matricā (a) DECLARE INTEGER p = 2 // Kolonnu skaits kreisajā matricā (a) // Rindu skaits labajā matricā (b) DECLARE INTEGER n = 1 // Kolonnu skaits pa labi matrica (b) DECLARE INTEGER p - 1 c [i] [j] = c [i] [j] + a [i] [k] * b [k] [j] NEXT k NEXT j NEXT i END

Trīs dēļ PRIEKŠ cilpas, Matricas reizināšanas laika sarežģītība ir O (n3), kuru izrunā "Big Oh of n "Matricas reizināšana piedāvā kubisko veiktspēju, kas laika gaitā kļūst dārga, ja lielas matricas tiek reizinātas. Tas piedāvā telpas sarežģītību O (nm), kuru izrunā "Big Oh of n*m, "papildu matricas glabāšanai n rindas pa m kolonnas. Tas kļūst O (n2) kvadrātveida matricām.

Esmu izveidojis MatMult Java programma, kas ļauj eksperimentēt ar Matricas reizināšanu. 1. saraksts parāda šīs lietojumprogrammas pirmkodu.

Saraksts 1. Java lietojumprogramma eksperimentēšanai ar Matricas reizināšanu (MatMult.java)

public final class MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; izgāztuve (a); System.out.println (); izgāztuve (b); System.out.println (); int [] [] c = reizināt (a, b); izgāzt (c); } private static void dump (int [] [] x) {if (x == null) {System.err.println ("masīvs nav derīgs"); atgriešanās; } // Matricas elementa vērtības izmetiet standarta izvadē tabulā // secībā. for (int i = 0; i <x.length; i ++) {for (int j = 0; j <x [0] .length; j ++) System.out.print (x [i] [j] + "" ); System.out.println (); }} private static int [] [] reizināt (int [] [] a, int [] [] b) {// ====================== =============================================== // 1. a.length satur rindu skaitu // // 2. a [0] .length (vai jebkuru citu a [x] .length derīgam x) satur a's // kolonnu skaitu // // b.length satur b rindu skaits // // 4. b [0] .length (vai jebkurš cits b [x] .length derīgam x) satur b // kolonnu skaitu // ============ ==================================================== ====== // Ja a sleju skaits! = B rindu skaits, glābiet, ja (a [0] .length! = B.length) {System.err.println ("a kolonnu skaits! = B rindu skaits "); return null; } // Piešķiriet rezultātu matricu, kuras lielums ir vienāds ar rindu skaitu reizēm ar b's // kolonnu skaits int [] [] rezultāts = jauns int [a.length] []; par (int i = 0; i <rezultāts.garums; i ++) rezultātu [i] = jauns int [b [0] .garums]; // Veiciet (int i = 0; i <a.length; i ++) reizināšanu un saskaitīšanu (int j = 0; j <b [0] .length; j ++) (int k = 0; k <a [0] .garums; k ++) // vai k <b. Garuma rezultāts [i] [j] + = a [i] [k] * b [k] [j]; // Atgrieziet rezultātu matricas atgriešanās rezultātu; }}

MatMult deklarē matricu pāri un izmet to vērtības standarta izvadā. Pēc tam tā reizina abas matricas un izgāž rezultātu matricu standarta izvadā.

Apkopojiet 1. sarakstu šādi:

javac MatMult.java

Palaidiet iegūto lietojumprogrammu šādi:

java MatMult

Jums jāievēro šāda izeja:

10 30 20 40 5 7 260 380

Matricas reizināšanas piemērs

Izpētīsim problēmu, kuru vislabāk atrisināt ar matricas reizināšanu. Šajā scenārijā augļu audzētājs Floridā ielādē pāris puspiekabes ar 1250 kastēm apelsīnu, 400 kastēm persiku un 250 kastēm greipfrūtu. 4. attēlā parādīta tirgus cena par kastīti katram augļu veidam četrās dažādās pilsētās.

Mūsu problēma ir noteikt, kur augļi jānosūta un jāpārdod, lai iegūtu maksimālos bruto ienākumus. Lai atrisinātu šo problēmu, vispirms mēs rekonstruējam diagrammu no 4. attēla kā četru rindu ar trīs kolonnu cenu matricu. No tā mēs varam izveidot trīs rindu ar vienas kolonnas daudzuma matricu, kas parādās zemāk:

== == | 1250 | | | | 400 | | | | 250 | == ==

Izmantojot abas matricas, mēs vienkārši reizinām cenu matricu ar daudzuma matricu, lai iegūtu bruto ienākumu matricu:

== == == == | | 10.00 8.00 12.00 | == == | 18700.00 | Ņujorka | | | 1250 | | | | 11.00 8.50 11.55 | | | | 20037.50 | Losandželosa | | X | 400 | = | | | 8,75 6,90 10,00 | | | | 16197.50 | Maiami | | | 250 | | | | 10.50 8.25 11.75 | == == | 19362.50 | Čikāga == == == ==

Nosūtot abus puspiekabes uz Losandželosu, tiks gūti visaugstākie bruto ienākumi. Bet, ja ņem vērā attālumu un degvielas izmaksas, iespējams, ka Ņujorka ir labāka izvēle, lai gūtu visaugstākos ienākumus.

Ragged masīvi

Uzzinot par divdimensiju masīviem, tagad jūs varētu domāt, vai rindu masīva elementiem ir iespējams piešķirt viendimensiju kolonnu masīvus ar dažādu garumu. Atbilde ir jā. Apsveriet šos piemērus:

dubultā [] [] temperatūra1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; dubultā [] [] temperatūra2 = jauna dubultā [2] []; dubultā [] [] temperatūra3 = jauna dubultā [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};

Pirmais un trešais piemērs izveido divdimensiju masīvu, kur pirmajā rindā ir trīs kolonnas, bet otrajā - divas kolonnas. Otrais piemērs izveido masīvu ar divām rindām un nenoteiktu kolonnu skaitu.

Pēc izveidošanas temperatūra2rindu masīvā, tā elementi jāaizpilda ar atsaucēm uz jauniem kolonnu masīviem. Šis piemērs parāda, piešķirot 3 kolonnas pirmajai rindai un 2 kolonnas otrajai rindai:

temperatūras2 [0] = jauns dubultā [3]; temperatūras2 [1] = jauns dubultā [2];

Iegūtais divdimensiju masīvs ir pazīstams kā a noplucis masīvs. Šeit ir otrais piemērs:

$config[zx-auto] not found$config[zx-overlay] not found