Duomenų struktūros ir „Java“ algoritmai, 2 dalis, pristatė įvairiausias viendimensinių masyvų paieškos ir rūšiavimo metodus, kurie yra paprasčiausi masyvai. Šioje pamokoje tyrinėsite daugiamačius masyvus. Aš jums parodysiu tris daugialypių masyvų kūrimo būdus, tada sužinosite, kaip naudoti Matricos daugybos algoritmą dauginant elementus dvimatėje masyve. Taip pat pristatysiu nelygius masyvus ir sužinosite, kodėl jie populiarūs didžiųjų duomenų programose. Galiausiai mes apsvarstysime klausimą, ar masyvas yra ar nėra „Java“ objektas.
Šiame straipsnyje nustatoma 4 dalis, kurioje pristatoma paieška ir rūšiavimas naudojant atskirai susietus sąrašus.
Daugiamatės masyvai
A daugiamatis masyvas susieja kiekvieną masyvo elementą su keliais indeksais. Dažniausiai naudojamas daugiamatis masyvas yra dvimatis masyvas, taip pat žinomas kaip a stalo arba matrica. Dvimatis masyvas susieja kiekvieną jo elementą su dviem rodyklėmis.
Dvimatę masyvą galime suvokti kaip stačiakampį elementų tinklelį, padalytą į eilutes ir stulpelius. Mes naudojame (Eilute stulpelis) žymėjimas elementui identifikuoti, kaip parodyta 1 paveiksle.
Kadangi dvimatės masyvai yra taip dažnai naudojami, aš sutelksiu dėmesį į juos. Tai, ką sužinosite apie dvimates masyvus, galima apibendrinti iki aukštesnių matmenų.
Dvimačių masyvų kūrimas
Yra trys būdai, kaip sukurti dviejų matmenų masyvą „Java“:
- Inicializatoriaus naudojimas
- Naudojant raktinį žodį
naujas - Naudojant raktinį žodį
naujassu inicializatoriumi
Inicializatoriaus naudojimas kuriant dvimatį masyvą
Tik inicializatoriaus požiūris kuriant dvimatį masyvą turi tokią sintaksę:
'{' [rowInitializer (',' rowInitializer)*] '}'rowInitializer turi šią sintaksę:
'{' [išr (',' išr)*] '}'Šioje sintaksėje teigiama, kad dviejų matmenų masyvas yra pasirenkamas kableliais atskirtas eilučių iniciatorių, rodomų tarp atvirojo ir uždarojo skliaustų simbolių, sąrašas. Be to, kiekvienos eilutės inicialas yra pasirenkamas kableliais atskirtų išraiškų, rodomų tarp atvirojo ir uždarojo skliaustų simbolių, sąrašas. Kaip ir vienmatiai masyvai, visos išraiškos turi būti vertinamos pagal suderinamus tipus.
Štai dviejų matmenų masyvo pavyzdys:
{ { 20.5, 30.6, 28.3 }, { -38.7, -18.3, -16.2 } }Šis pavyzdys sukuria lentelę su dviem eilutėmis ir trimis stulpeliais. 2 paveiksle pateikiamas koncepcinis šios lentelės vaizdas kartu su atminties vaizdu, rodančiu, kaip „Java“ išdėsto šią (ir kiekvieną) lentelę atmintyje.
2 paveiksle parodyta, kad „Java“ vaizduoja dvimatį masyvą kaip vienos dimensijos eilučių masyvą, kurio elementai nurodo vienmates stulpelių masyvus. Eilučių indeksas identifikuoja stulpelių masyvą; stulpelio rodyklė nurodo duomenų elementą.
Tik naujų raktinių žodžių kūrimas
Raktinis žodis naujas paskirsto atmintį dvimačiam masyvui ir grąžina jo nuorodą. Šis požiūris turi tokią sintaksę:
„naujas“ tipo '[' int_expr1 ']' '['int_expr2 ']'Ši sintaksė teigia, kad dviejų matmenų masyvas yra (teigiamo) regionas int_expr1 eilučių elementai ir (teigiami) int_expr2 stulpelio elementai, kurie visi turi tą patį tipo. Be to, visi elementai yra nuliniai. Štai pavyzdys:
naujas dvigubas [2] [3] // Sukurkite lentelę dviem eilėmis po tris stulpelius.Naujų žodžių ir inicialų kūrimas
Raktinis žodis naujas naudojant inicializatoriaus metodą, yra tokia sintaksė:
„naujas“ tipo '[' ']' [' ']' '{' [rowInitializer (',' rowInitializer)*] '}'kur rowInitializer turi šią sintaksę:
'{' [išr (',' išr)*] '}'Ši sintaksė sujungia du ankstesnius pavyzdžius. Kadangi elementų skaičių galima nustatyti iš kableliais atskirtų išraiškų sąrašų, nepateikiate tarpt tarp bet kurios laužtinių skliaustų poros. Štai pavyzdys:
naujas dvigubas [] [] {{20.5, 30.6, 28.3}, {-38.7, -18.3, -16.2}}Dvimatės masyvai ir masyvo kintamieji
Pats savaime naujai sukurtas dvimatis masyvas nenaudingas. Jo nuoroda turi būti priskirta masyvo kintamasis suderinamo tipo, tiesiogiai arba per metodo skambutį. Šios sintaksės rodo, kaip deklaruotumėte šį kintamąjį:
tipovar_name '[' ']' '[' ']' tipo '[' ']' '[' ']' var_nameKiekviena sintaksė skelbia masyvo kintamąjį, kuriame saugoma nuoroda į dvimatį masyvą. Pageidautina, kad laužtiniai skliaustai būtų po tipo. Apsvarstykite šiuos pavyzdžius:
dviguba [] [] temperatūra1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}}; dviguba [] [] temperatūra2 = nauja dviguba [2] [3]; dviguba [] [] temperatūra3 = nauja dviguba [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3, -16,2}};Kaip ir vienmatiai masyvo kintamieji, dvimatis masyvo kintamasis siejamas su a .ilgis ypatybė, kuri pateikia eilutės masyvo ilgį. Pavyzdžiui, temperatūra1.ilgis grąžina 2. Kiekvienas eilutės elementas taip pat yra masyvo kintamasis su a .ilgis ypatybė, kuri pateikia eilutės elementui priskirtą stulpelių masyvo stulpelių skaičių. Pavyzdžiui, temperatūra1 [0] .ilgis grąžina 3.
Atsižvelgdami į masyvo kintamąjį, galite pasiekti bet kurį dviejų matmenų masyvo elementą, nurodydami išraišką, kuri sutampa su šia sintakse:
masyvas_var '[' line_index ']' '[' col_index ']'Abu indeksai yra teigiami tarpts, kurie svyruoja nuo 0 iki vieno mažesnio nei vertė, grąžinta iš atitinkamo .ilgis savybes. Apsvarstykite kitus du pavyzdžius:
dviguba temperatūra = temperatūra1 [0] [1]; // Gaukite vertę. temperatūra1 [0] [1] = 75,0; // Nustatyti vertę.Pirmasis pavyzdys grąžina vertę pirmosios eilutės antrame stulpelyje (30.6). Antrasis pavyzdys pakeičia šią vertę 75.0.
Jei nurodysite neigiamą indeksą arba indeksą, kuris yra didesnis arba lygus masyvo kintamojo grąžintai vertei .ilgis nuosavybę, Java sukuria ir išmeta „ArrayIndexOutOfBoundsException“ objektas.
Dauginant dviejų matmenų masyvus
Vienos matricos padauginimas iš kitos matricos yra įprasta operacija srityse, pradedant kompiuterine grafika, baigiant ekonomika ir baigiant transporto pramone. Kūrėjai šiai operacijai paprastai naudoja matricos daugybos algoritmą.
Kaip veikia matricos daugyba? Tegul A reiškia matricą m eilučių ir p stulpeliai. Panašiai tegul B reiškia matricą su p eilučių ir n stulpeliai. Padauginkite A iš B, kad gautumėte C matricą su m eilučių ir n stulpeliai. Kiekvienas cij C įrašas gaunamas padauginus visus A įrašus -osios eilutėje įrašydami atitinkamus B įrašus Dž stulpelį, tada pridedami rezultatai. 3 paveiksle pavaizduotos šios operacijos.
Kairiosios matricos stulpeliai turi būti lygūs dešinės matricos eilutėms
Matricos dauginimas reikalauja, kad kairiosios matricos (A) stulpelių skaičius (p) būtų lygus dešinės matricos (B) eilučių skaičiui (p). Kitu atveju šis algoritmas neveiks.
Šis pseudokodas išreiškia matricos dauginimą 2 eilutėse po 2 stulpelius ir 2 eilutes po 1 stulpelį lentelės kontekste. (Prisiminkime, kad pseudokodą įvedžiau 1 dalyje.)
// == == == == == == // | 10 30 | | 5 | | 10 x 5 + 30 x 7 (260) | // | | X | | = | | // | 20 40 | | 7 | | 20 x 5 + 40 * 7 (380) | // == == == == == == PASKELBTI INTEGERĮ a [] [] = [10, 30] [20, 40] PASKELBTI INTEGERĮ b [] [] = [5, 7] PASKELBTI INTEGERĮ m = 2 // Eilių skaičius kairėje matricoje (a) DEKLARUOKITE INTEGERĮ p = 2 // Stulpelių skaičius kairėje matricoje (a) // Eilių skaičius dešinėje matricoje (b) DEKLARUOKITE INTEGERĮ matrica (b) PATEIKIUOTI INTEGRĄ c [m] [n] // c turi 2 eilutes po 1 stulpelį // Visi elementai inicializuojami į 0 FOR i = 0 TO m - 1 FOR j = 0 TO n - 1 K = 0 TO p - 1 c [i] [j] = c [i] [j] + a [i] [k] * b [k] [j] KITAS k KITAS j KITAS i PABAIGADėl trijų DĖL kilpos, Matricos daugybos laiko sudėtingumas yra O (n3), kuris tariamas „Big Oh of n "Matricos daugyba siūlo kubinį našumą, kuris brangėja laiko atžvilgiu, kai dauginamos didelės matricos. Tai suteikia erdvės sudėtingumą O (nm), kuris tariamas „Big Oh of n*m, "saugoti papildomą n eilučių m stulpeliai. Tai tampa O (n2) kvadratinėms matricoms.
Aš sukūriau a MatMult „Java“ programa, leidžianti eksperimentuoti su „Matrix Multiplication“. 1 sąraše pateikiamas šios programos šaltinio kodas.
Sąrašas 1. „Java“ programa, skirta eksperimentuoti su „Matrix Multiplication“ (MatMult.java)
public final class MatMult {public static void main (String [] args) {int [] [] a = {{10, 30}, {20, 40}}; int [] [] b = {{5}, {7}}; sąvartynas (a); System.out.println (); sąvartynas (b); System.out.println (); int [] [] c = dauginti (a, b); sąvartynas (c); } private static void dump (int [] [] x) {if (x == null) {System.err.println ("masyvas yra niekinis"); grįžti; } // Matricos elemento reikšmes perkelkite į standartinę išvestį lentelių // tvarka. 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 (); }} privatus statinis int [] [] padauginti (int [] [] a, int [] [] b) {// ====================== ================================================= // 1. a.length yra eilučių skaičius // // 2. a [0] .length (arba bet kuris kitas galiojančio x [x] .length) yra a's // stulpelių skaičius // // b.length yra b eilučių skaičius // // 4. b [0] .length (arba bet kuris kitas b [x] .length galiojančiam x) yra b's // stulpelių skaičius // ============ ==================================================== ====== // Jei a stulpelių skaičius! = B eilučių skaičius, gelbėkite, jei (a [0] .length! = B.length) {System.err.println ("a stulpelių skaičius! = B eilučių skaičius "); return null; } // Paskirstykite rezultato matricą, kurios dydis lygus a eilutės skaičiaus kartui b // stulpelių skaičius int [] [] rezultatas = naujas int [a.length] []; už (int i = 0; i <rezultatas.ilgis; i ++) rezultatą [i] = naujas int [b [0]. ilgis]; // Atlikite (int i = 0; i <a.length; i ++) (int j = 0; j <b [0] .length; j ++) dauginimą ir pridėjimą (int k = 0; k <a [0]. Ilgis; k ++) // arba k <b. Ilgio rezultatas [i] [j] + = a [i] [k] * b [k] [j]; // Grąžinti rezultatų matricos grąžinimo rezultatą; }}MatMult deklaruoja matricų porą ir išverčia jų reikšmes į standartinę išvestį. Tada jis padaugina abi matricas ir išmeta rezultatų matricą į standartinę išvestį.
Sudarykite 1 sąrašą taip:
javac MatMult.javaPaleiskite gautą programą taip:
java MatMultTurėtumėte stebėti šį rezultatą:
10 30 20 40 5 7 260 380Matricos daugybos pavyzdys
Panagrinėkime problemą, kurią geriausiai išspręsti dauginant matricą. Pagal šį scenarijų vaisių augintojas Floridoje pakrauna porą puspriekabių su 1 250 dėžių apelsinų, 400 dėžių persikų ir 250 dėžių greipfrutų. 4 paveiksle parodyta kiekvienos rūšies vaisių dėžutės rinkos kainos diagrama keturiuose skirtinguose miestuose.
Mūsų problema yra nustatyti, kur vaisiai turėtų būti gabenami ir parduodami, kad gautų maksimalias bendras pajamas. Norėdami išspręsti šią problemą, pirmiausia rekonstruojame diagramą iš 4 paveikslo kaip keturių eilučių ir trijų stulpelių kainų matricą. Iš to galime sukonstruoti trijų eilučių vieno stulpelio kiekio matricą, kuri rodoma žemiau:
== == | 1250 | | | | 400 | | | | 250 | == ==Turėdami abi matricas, mes tiesiog padauginame kainos matricą iš kiekio matricos, kad gautume bendrųjų pajamų matricą:
== == == == | 10.00 8.00 12.00 | == == | 18700,00 | Niujorkas | | | 1250 | | | | 11.00 8.50 11.55 | | | | 20037.50 | Los Andželas | | X | 400 | = | | | 8,75 6,90 10,00 | | | | 16197,50 | Majamis | | | 250 | | | | 10,50 8,25 11,75 | == == | 19362.50 | Čikaga == == == ==Siunčiant abi puspriekabes į Los Andželą bus gaunamos didžiausios bendrosios pajamos. Bet kai atsižvelgiama į atstumą ir degalų sąnaudas, galbūt Niujorkas yra geresnis pasirinkimas norint gauti didžiausias pajamas.
Skaldyti masyvai
Sužinoję apie dvimates masyvus, dabar galite pagalvoti, ar įmanoma eilės masyvo elementams priskirti skirtingo ilgio vienmates stulpelių masyvus. Atsakymas yra teigiamas. Apsvarstykite šiuos pavyzdžius:
dviguba [] [] temperatūra1 = {{20,5, 30,6, 28,3}, {-38,7, -18,3}}; dviguba [] [] temperatūra2 = nauja dviguba [2] []; dviguba [] [] temperatūra3 = nauja dviguba [] [] {{20,5, 30,6, 28,3}, {-38,7, -18,3}};Pirmasis ir trečiasis pavyzdžiai sukuria dvimatį masyvą, kuriame pirmoje eilutėje yra trys stulpeliai, o antroje - du stulpeliai. Antrasis pavyzdys sukuria masyvą su dviem eilutėmis ir nenurodytu stulpelių skaičiumi.
Sukūrus temperatūra2eilutės masyvas, jo elementai turi būti užpildyti nuorodomis į naujus stulpelių masyvus. Šis pavyzdys rodo, kad 3 stulpeliai priskiriami pirmai eilutei ir 2 stulpeliai antrai eilutei:
temperatūra2 [0] = naujas dvigubas [3]; temperatūra2 [1] = naujas dvigubas [2];Gautas dvimatis masyvas yra žinomas kaip a nuskuręs masyvas. Štai antras pavyzdys:
