JAVA predavanje 8

java_thumbVeč o tabelah

 

TABELE

Tabela je sestavljena podatkovna struktura, ki združuje elemente (podatke) istega tipa.

 

 

Primeri programov, ki uporabljajo enodimenzionalne tabele:
- Met Kocke
- Iskanje podatkov v tabeli:zaporedje z metodo bisekcije
- urejanje (sortiranje) podatkov

Iskanje podatka v tabeli

 


Dana je tabela celih števil t in število x; zanima nas ali se število x nahaja v tabeli t. Rešitev sprogramiramo v obliki metode, ki vrne indeks tistega elementa, v katerem se nahaja x, če elementa ne najde vrne -1.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	//Prvi način (Pascallski-nima stavka return):
public static int poisci(int[] t, int x){
int i=0;
while (i<t.length && t[1]!=x) i++;
 
if(i<t.length) //return (i
return i; //pogojni operator:
else // ? :
return -1;
}
 
//Drugi način:
public static int poisci(int[] t, int x){
for(int i=0; i<t.length; i++){
if(x==t[i]){
return i;
}
}
return -1;
}

 

 

 

Binarno iskanje (Metoda bisekcije)


Učinkovitejše od zaporednega vendar zahteva, da je tabela urejena (npr. od najmanjšega proti največjemu)

Binarno iskanje temelji na razpolavljanju intervala. Na začetku je interval obsega celotno tabelo, potem pa ga na vsakem koraku razpolovimo:


1. Začetni interval obsega celotno tabelo
2. Izračunamo indeks elementa, ki se nahaja na sredini intervala
3. Če je element na sredini intervala enak x, je postopek končan.
4. Če je iskani element, x, manjši od elementa na sredini, nadaljujemo z iskanjem v levi polovici prvotnega intervala.
5. Če je x večji od elementa na sredini, nadaljujemo z iskanjem v desni polovici prvotnega intervala.
6. Postopek ponavljamo, dokler ne najdemo x ali dokler leva meja intervala ne preseže desne

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	public static int poisciBinarno(int[] t, int x){
int l=0;
int d=t.length-1;
while(l<=d){
int s=(l+d)/2; //poševnica predstavlja celoštevilsko
if(t[s]==x){ //deljenje
return s;
}
else if(x<t[s]){
d=s-1;
}
else{
l=s+1;
}
}
return -1;
}

 

 

Čas, ki ga potrebujemo za iskanje T=0 (log(2)(n) - število potrebnih poskusov, n = številoelementov v tabeli)
Pri zaporednem iskanju t=0 (n).

 

 

Sortiranje oz. urejanje podatkov v tabeli


Dana je tabela celih števil a, števila želimo urediti naraščajoče(najmanjši->največji)
Uporabili bomo algoritem za sortiranje z navadnim izbiranjem.
1. Poišči najmanjši element in ga zamenjaj z izhodiščnim.
2. Izhodiščni element je najprej prvi element nato drugi itd..
3. Postopek se zadnjič ponovi, ko je izhodiščni element predzadnji element v tabeli

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
	for(int i=0, i<a.length-1; i++){
//poišči najmanjši element in ga zamenjaj z a[i]
}
//poišči najmanjši element
int vMin=a[i];
int iMin=i;
for(int j=i+1; j<a.length; j++){
if(a[j]<vMin){
vMin=a[j];
iMin=j;
}
}
//Zamenjaj najmanjši element ta izhodiščni
a[iMin]=a[i];
a[i]=vMin;
 

 

 

 

 

DVODIMENZIONALNE TABELE


1.način: kot razporeditev elementov v vrstice in stolpc
Primer: Tabela z osebnimi dohodki delavcev (za vsak mesec) za 10 let

 

tabela1

 

1
double[][] od=new double[10][12]

 

 

2.Način:dvodimenzionalna tabela je enodimenzionalna tabela, katere elementi so enodimenzionalne tabele

 

tabela2

 

Atribut length


od.length    -->    10
od[0].length    -->    12    št.stolpcev

 

 

Tipična shema za obdelavo elementov dvodimenzionalne tabele:

 

1
2
3
4
5
    for(int i=0; i<od.length; i++){
for(int j=0; j<od[i].length; j++){
obdelaj element od[i][j]
}
}

 

 

 

MetiKockeSTabelo.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.Scanner;
public class MetiKockeSTabelo{
public static void main(String[] args){
 
//deklaracija tabele števcev
int[] st={0, 0, 0, 0, 0, 0};
 
//branje števila metov
Scanner scan=new Scanner(System.in);
System.out.print("Stevilo metov: ");
int n=scan.nextInt();
 
//zanka v kateri simuliramo mete
for(int i=0; i<n; i++){
int met=(int)(Math.random()*6+1); //int met=(int)(Math.random()*6)
st[met-1]++; //st[met]++
}
//izpis vrednosti vseh stevcev(elementov tabele st)
for(int i=0; i<st.length; i++){
System.out.println(i+1+" se pojavi "+st[i]+" -krat");
}
}
}

 

Vsi vodiči so na voljo BREZPLAČNO!
Pišite mi

Želite mnenje ali pomoč pri vašem projektu?

Pišite mi in bom pomagal, kakor bom v tistem trenutku lahko.