Es soll eine Klasse programmiert werden, mit der dünn besetzte Matrizen günstig gespeichert werden können.
Es sind außerdem Routinen zum Laden und Speichern und zum Addieren und Mischen von Elementen zu implementieren.
Hier der Programmtext:
Datenstruktur Element
public class Element
{
// Klassenvariablen:
private int iPosX, iPosY; // Position in der Matrix
private double dValue; // Wert des Elements
public Element (int iPosX, int iPosY, double dValue)
{ // Konstruktor: Element MUSS mit vollständigem Wertesatz
// initialisiert werden
this.iPosX = iPosX;
this.iPosY = iPosY;
this.dValue = dValue;
} // end Konstruktor
// get- und set- Funktionen
public int getX()
{
return this.iPosX;
}
public int getY()
{
return this.iPosY;
}
public double getValue()
{
return this.dValue;
}
public void setValue(double dValue)
{
this.dValue = dValue;
}
} // end class Element
Datenstruktur Matrix
import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.Locale;
import java.util.Scanner;
import java.util.Vector;
public class Matrix
{
// Klassenvariablen:
public static int stop = 0;
private int iDim; // Dimension
private Vector<Element> elmElemente; // Vektor der Elemente
// Konstruktoren:
public Matrix()
{ // Standardkonstruktor
elmElemente = new Vector<Element>();
}
public Matrix(int iDim)
{ // Konstruktor mit fester Dimension der Matrix
elmElemente = new Vector<Element>();
this.iDim = iDim;
}
public int getDim()
{
return this.iDim;
}
public void einlesen(String sDateiName)
{ // Matrix wird aus Datei mit übergebenem Dateinamen geladen
try
{
Scanner scnEingabe = new Scanner(new File(sDateiName));
this.iDim = scnEingabe.nextInt();
scnEingabe.useLocale(Locale.ENGLISH);
while (scnEingabe.hasNext())
elmElemente.add(new Element(scnEingabe.nextInt(),
scnEingabe.nextInt(), scnEingabe.nextDouble() ));
}
catch (FileNotFoundException e)
{
System.out.println("Datei nicht gefunden!");
e.printStackTrace();
}
} // end einlesen
public void addiereElement(Element e)
{ // fügt neues Element e ein. Prüft zunächst, ob bei dem Index schon ein
// Element vorhanden ist und addiert dieses gegebenenfalls
boolean bDone = false;
for (int i = 0; i < this.elmElemente.size(); ++ i)
if (this.elmElemente.elementAt(i).getX() == e.getX())
if (this.elmElemente.elementAt(i).getY() == e.getY())
{
this.elmElemente.elementAt(i).setValue(
this.elmElemente.elementAt(i).getValue()+e.getValue());
bDone = true;
}
if (!bDone)
this.elmElemente.add(e);
} // end addiereElement
public void addiereMatrix(Matrix B)
{ // addiert zur ursprünglichen Matrix die übergebene Matrix B,
// indem alle Elemente von B einzeln addiert werden
if (Matrix.gleicheDimension(this, B))
for (int i = 0; i < B.elmElemente.size(); ++ i)
this.addiereElement(B.elmElemente.elementAt(i));
} // end addiereMatrix
public static void mische(Element[] elmListe)
{ // Zufällige Neusortierung der Elemente
for (int i = 0; i < elmListe.length; ++ i)
{
int iAlt = i;
int iNeu = i+(int)(Math.random() * elmListe.length-i);
Element temp = elmListe[iAlt];
elmListe[iAlt] = elmListe[iNeu];
elmListe[iNeu] = temp;
}
}
public void sortiere()
{ // sortiert die Elemente der Matrix aufsteigend nach Zeile (Quicksort),
// höhere Geschwindigkeit durch Nutzung eines statischen Arrays
Element[] elmListe =
elmElemente.toArray(new Element[elmElemente.size()]);
// Optimierung: Liste wird vor der sortierung gemischt:
mische(elmListe);
// Aufruf der rekursiven Sortierfunktion mit Startwerten
quickSort(elmListe, 0, elmListe.length-1, 1);
// Sortieren der Zeilenblöcke
int j = -1;
for (int i = 1; i < this.iDim; ++ i)
{
System.out.println(" i "+i);
int jAlt = j;
while (elmListe[j+1].getX() == i)
{
++ j;
System.out.println("j "+j);
}
if (j > jAlt+1)
{
System.out.println("[ "+(int)(jAlt+1)+" , "+j+" ]");
quickSort(elmListe, jAlt+1, j, 2);
}
}
// Array wird wieder in Vector umgewandelt
elmElemente.clear();
for (int i = 0; i < elmListe.length; ++ i)
elmElemente.add(elmListe[i]);
} // end sortiere
public static void quickSort(Element[] elmListe, int iLinks, int iRechts,
int iTyp)
{ // Rekursive Funktion sortiert Arrayelemente im übergebenen Intervall
if (iLinks < iRechts)
{
int p = partition(elmListe, iLinks, iRechts, iTyp);
quickSort(elmListe, iLinks, p-1, iTyp);
quickSort(elmListe, p+1, iRechts, iTyp);
}
} // end quickSort
public static int partition(Element[] elmListe, int iLinks, int iRechts,
int iTyp)
{
int iPivot;
int iTauschI = 0;
if (iTyp == 1) // es wird nach Zeilen sortiert
{
int iWert1 = elmListe[iLinks].getX();
int iWert2 = elmListe[iRechts].getX();
int iWert3 = elmListe[(iLinks+iRechts) / 2].getX();
// Pivot wird mit "Median-of-three" ermittelt
if ((iWert1 >= iWert2 && iWert1 <= iWert3)
|| (iWert1 <= iWert2 && iWert1 >= iWert3))
iPivot = iLinks;
else if ((iWert2 >= iWert1 && iWert2 <= iWert3)
|| (iWert2 <= iWert1 && iWert2 >= iWert3))
iPivot = iRechts;
else
iPivot = (iLinks+iRechts) / 2;
int i = iLinks-1; // damit die erste Schleife ganz links anfängt
int j = iRechts+1; // damit die zweite Schleife ganz rechts anfängt
while (i < j)
{
while (elmListe[++ i].getX() <= elmListe[iPivot].getX())
if (i == iRechts)
break;
while (elmListe[iPivot].getX() <= elmListe[-- j].getX())
if (j == iLinks)
break;
if (i < j)
{ // zwei Elemente werden vertauscht
Element temp = elmListe[i];
elmListe[i] = elmListe[j];
elmListe[j] = temp;
} // end if
} // end while
// neue Position iTauschI für das Pivotelement wird ermittelt
for (int a = iLinks; a <= iRechts; ++ a)
if (elmListe[a].getX() > elmListe[iPivot].getX())
{
if (iPivot > a)
iTauschI = a;
else if (iPivot < a)
iTauschI = a-1;
break;
} // end if
} // end if
else
{ // Elemente der Zeilen werden nach Spalten sortiert
int iWert1 = elmListe[iLinks].getY();
int iWert2 = elmListe[iRechts].getY();
int iWert3 = elmListe[(iLinks+iRechts) / 2].getY();
// Pivot wird mit "Median-of-three" ermittelt
if ((iWert1 >= iWert2 && iWert1 <= iWert3)
|| (iWert1 <= iWert2 && iWert1 >= iWert3))
iPivot = iLinks;
else if ((iWert2 >= iWert1 && iWert2 <= iWert3)
|| (iWert2 <= iWert1 && iWert2 >= iWert3))
iPivot = iRechts;
else
iPivot = (iLinks+iRechts) / 2;
int i = iLinks-1; // damit die erste Schleife ganz links anfängt
int j = iRechts+1; // damit die zweite Schleife ganz rechts anfängt
while (i < j)
{
while (elmListe[++ i].getY() <= elmListe[iPivot].getY())
if (i == iRechts)
break;
while (elmListe[iPivot].getY() <= elmListe[-- j].getY())
if (j == iLinks)
break;
if (i < j)
{ // zwei Elemente werden vertauscht
Element temp = elmListe[i];
elmListe[i] = elmListe[j];
elmListe[j] = temp;
} // end if
} // end while
// neue Position iTauschI für das Pivotelement wird ermittelt
for (int a = iLinks; a <= iRechts; ++ a)
if (elmListe[a].getY() > elmListe[iPivot].getY())
{
if (iPivot > a)
iTauschI = a;
else if (iPivot < a)
iTauschI = a-1;
break;
} // end if
}
if (iTauschI == 0)
iTauschI = iRechts;
Element temp = elmListe[iPivot];
elmListe[iPivot] = elmListe[iTauschI];
elmListe[iTauschI] = temp;
return iTauschI;
} // end partition
public void speichere(String sDateiName, boolean bSortiert)
{ // speichert die Matrix unter übergebenem Dateinamen
try
{
PrintStream pstAusgabe = new PrintStream(new File(sDateiName));
pstAusgabe.println(this.getDim());
if (bSortiert)
{ // wenn gewünscht, wird die Matrix zuerst sortiert
pstAusgabe.println(this.anzahlDerElemente());
this.sortiere();
}
for (int i = 0; i < this.elmElemente.size(); ++ i)
pstAusgabe.println(this.elmElemente.elementAt(i).getX()+" "
+this.elmElemente.elementAt(i).getY()+" "
+this.elmElemente.elementAt(i).getValue());
} // end try
catch (FileNotFoundException e)
{
System.out.println("Datei konnte nicht geschrieben werden!");
e.printStackTrace();
}
} // end speichere
public double summeDerElemente()
{ // berechnet die Summe aller Matrixelemente
double dSumme = 0;
for (int i = 0; i < this.elmElemente.size(); ++ i)
dSumme += this.elmElemente.elementAt(i).getValue();
return dSumme;
} // end summeDerElemente
public int anzahlDerElemente()
{ // ermittelt die Anzahl der Matrixelemente
return this.elmElemente.size();
} // end anzahlElemente
public static boolean gleicheDimension(Matrix A, Matrix B)
{ // prüft zwei quadratische Matrizen auf Dimensionsgleichheit
return (A.getDim() == B.getDim());
} // end gleicheDimension
public static Matrix zufallsMatrix(int iDim, int iElemente, double dMax)
{ // erstelle eine zufällige Matrix mit übergebenen Spezifikationen
Matrix mZufall = new Matrix(iDim);
for (int i = 0; i < iElemente; ++ i)
{
while (true)
{
int iX = (int)(Math.random() * (iDim-1))+1;
int iY = (int)(Math.random() * (iDim-1))+1;
// es wird geprüft, ob der zufällige Index schon vorhanden ist:
boolean bDone = true;
for (int j = 0; j < mZufall.elmElemente.size(); ++ j)
if (mZufall.elmElemente.elementAt(j).getX() == iX)
if (mZufall.elmElemente.elementAt(j).getY() == iY)
bDone = false;
if (bDone)
{ // Wenn der Index noch nicht benutzt wurde:
double dV = Math.random() * dMax;
mZufall.elmElemente.add(new Element(iX, iY, dV));
break;
} // end if
} // end while
} // end for
return mZufall;
} // end zufallsMatrix
} // end class Matrix
Testprogramm
public class MatrixTest
{
public static void main(String args[])
{
long lStartMS = System.nanoTime();
Matrix A = new Matrix();
A.einlesen("A.txt");
System.out.println("Matrix 1: Summe der "+A.anzahlDerElemente()
+" Elemente: "+A.summeDerElemente());
Matrix B = new Matrix();
B.einlesen("B.txt");
System.out.println("Matrix 2: Summe der "+B.anzahlDerElemente()
+" Elemente: "+B.summeDerElemente());
A.addiereMatrix(B);
System.out.println("Matrix 1+2: Summe der "+A.anzahlDerElemente()
+" Elemente des Ergebnisses: "
+A.summeDerElemente());
A.speichere("AplusB.txt", true);
long lEndMS = System.nanoTime();
long lMS = lEndMS-lStartMS;
System.out.println(" -> Rechenzeit: "+lMS);
}
}