Dünn besetzte Matrix

B

baker333

Bekanntes Mitglied
Guten Tag,

ich habe ein Verständnisproblem bei der folgenden Aufgabe. In diesem Unterkurs eines Java-Moduls wird (warum auch immer) eine Pseudocodenotation
verwendet und nicht die Java-Notation. Sollte aber bei der Lösung keine Rolle spielen.

Ich verstehe das so, dass in "zahlen" Paare aus dem Index mit dem dazugehörigen Wert gespeichert werden.
Jetzt frage ich mich aber wie die entsprechende Spalte eingebzogen wird? Es kann ja beispielsweise in Spalte 1 mehrere Paare (mit Zeilenindex und Wert) geben.
In der While-Schleife wird aber direkt die Spalte erhöht und nicht durch die einzelnen Zeilen gegangen?

Versteht jemand mein Verständnisproblem? :D

Danke

Aufgabentext und Lösung:

Eine dünn besetzte Matrix mit 1000 Zeilen, 2000 Spalten und einer Besetzungsdichte
von weniger als 1 Prozent enthalte Zahlen vom Typ INTEGER. Die Nichtnullelemente
seien spaltenweise in der in Abb. 3.4 gezeigten Form abgespeichert.
Gegeben seien folgende, zur Manipulation der Matrix notwendige Typen und Variablen:

Code:
DATA
TYPE
   ZEILENINDEX = [1..1000];
   SPALTENINDEX = [1..2000];
   ELEMENTINDEX = [1..20000]; {1% von Anzahl (Spalten • Zeilen)}
   SPALTENADRESSEN = ARRAY [0..2000] OF ELEMENTINDEX;
   PAAR = RECORD
       paarind : ZEILENINDEX;
       element : INTEGER;
       END;
    MATRIX = ARRAY [1..20000] OF PAAR;

VARIABLE
   zeilenind : ZEILENINDEX;
   spaltenind : SPALTENINDEX;
   zeigerspalte, folgespalte : ELEMENTINDEX;
   advektor: SPALTENADRESSEN;
   zahlen : MATRIX;

Formulieren Sie ein Algorithmusfragment zur Suche eines beliebigen Matrixelements
mit dem Zeilenindex zeilenind und dem Spaltenindex spaltenind. Mit zeigerspalte
und folgespalte seien die Zeiger bezeichnet, die je auf das erste Element
der zutreffenden Spalte und der folgenden Spalte verweisen.

Lösung:

Code:
FUNCTION such_elem( zeilenind: ZEILENINDEX;
                spaltenind : SPALTENINDEX): ELEMENTINDEX;
DATA
    VARIABLE
        zeigerspalte, folgespalte : ELEMENTINDEX;
BEGIN
    zeigerspalte := advektor[spaltenind]; {Zugriff auf Spaltenadessvektoren}
    IF (spaltenind ≤ 2000) THEN {Vermeiden von Indexüberlauf}
        folgespalte := advektor[spaltenind + 1];
    ELSE
        folgespalte := 0;
    ENDIF;
    WHILE (zahlen[zeigerspalte].paarind < zeilenind) AND
        (zeigerspalte < folgespalte) DO {Lesen des jeweils nächsten Paares und}
        zeigerspalte := zeigerspalte + 1; {Vergleich der Zeilen- und Spalten-}
    ENDWHILE; {indizes mit den gesuchten Werten}
    IF (zahlen[zeigerspalte].paarind = zeilenind) THEN
        RETURN zeigerspalte; {Element gefunden }
    ELSE
        RETURN 0; {Element nicht gefunden}
    ENDIF;
END such_elem;
 
kneitzel

kneitzel

Top Contributor
Ja, super, dass der Text auf Abb 3.4 verweist und Du uns die Informationen vorenthältst...

Nun sollen wir uns das aus den Fragmenten zusammen reimen?

Aber so sollte es aussehen:
Du hast zahlen - das sind die Elemente aus Zeilenindex und Wert.

Du hast den advektor - der gibt für jede Spalte an, ab wo er anfängt.

Daher bei der Suche zuerst geschaut von wo bis wo die Zahlen der Spalte sind.

Wenn Du also in advektor hast, dass die dritte Spalte bei Wert 17 losgeht und die vierte Spalte ab Wert 20, dann musst Du nur die zahlen mit Index ab 17 bis einschließlich 19 prüfen.

advektor ist also sowas wie ein Register, das angibt von wo bis wo eine Spalte geht.

Die Lösung kommt von Dir? Denn ich glaube, da ist ein Fehler. Bei der letzten Spalte gibt es keinen Folgeeintrag. Daher muss man da einen anderen Wert nehmen. Der darf aber nicht 0 sein so wie in der Lösung, denn dann wird in der letzten Spalte kein Wert gefunden (zeigerspalte < folgespalte trifft nie zu!). Da muss der Index des letzten Wertes + 1 gesetzt werden.

Also spaltenindex = 2000 -> es gibt keine folgende Spalte. Aber es kann in der Spalte 2000 ja Werte geben ...

Wurde das so deutlich?
 
B

baker333

Bekanntes Mitglied
Vielen Dank. Die Abbildung habe ich vergessen, habe sie jetzt angehängt.

Die Lösung ist die Musterlösung des Skripts.
Unbenannt.PNG
 
B

baker333

Bekanntes Mitglied
Der advektor gibt also für jede Spalte die passenden Nichtnullelemente inkl. Zeilenindex an?
 
kneitzel

kneitzel

Top Contributor
Ok, das bestätigt, wie die Daten gespeichert werden. Aber die Angaben im Text sind dann fehlerhaft.

Bei 2000 Spalten braucht man also ein Array mit 2001 Elementen (n = 2000, n+1 Eintrag wird benötigt)

Daher scheint mir die Aufgabe schlecht durchdacht / nicht wirklich geprüft worden sein. Aber evtl. kann da jemand mit mehr Erfahrung mit solchen Aufgaben etwas mehr dazu sagen.

Aber meine Erläuterung bezüglich Speicherung sind korrekt.

Und advektor gibt ab, ab welchem Punkt in zahlen die Werte für die Spalte zu finden sind.
 
B

baker333

Bekanntes Mitglied
Danke
Und advektor gibt ab, ab welchem Punkt in zahlen die Werte für die Spalte zu finden sind.
Also ab welcher Zeile Werte gespeichert sind, oder? Nimmt er also nur Zeilen auf oder ist doch auch der entsprechende Wert zu einer Zeile in der entsprechenden Spalte gespeichert.

Der Rest des Skripts ist besser aber dieser Algorithmus verwirrt mich nur.
 
mihe7

mihe7

Top Contributor
Ein ähnliches Problem sehe ich auch beim Rückgabewert: der Typ ELEMENTINDEX lässt ja nur valide Werte zu, 0 ist also gar nicht möglich.
 
kneitzel

kneitzel

Top Contributor
Sieh das wie ein Register. Stell Dir vor, der Dozent macht sich Notizen zu Studenten. Aus Gründen des Datenschutz schreibt er aber keine Namen auf die Zettel.

Also macht er sich eine separate Liste mit den Namen und dazu ein Hinweis, auwelchem Blatt die Notizen für den Student anfangen.
Anton 1
Michael 1
Nicole 3
Friedhelm 7
...

Anton geht von Blatt 1 ... der nächste (Michael) hat die 1.
Die Blätter, die zu Anton haben, haben Positionen mit 1<=pos<1
==> Es gibt keine Blätter zu Anton

Blätter von Michael: 1 <= pos < 3 ==> Blätter 1 und 2 sind von Michael ....

u.s.w.

Das kann man sich visuell vorstellen. Das können Registerkarten sein. Und die kommen dann immer vor das Blatt mit der angegebenen Nummer ....

Also
Register Anton
Register Michael
Blätter 1, 2
Register Nicole
Blätter 3,4,5,6
....

Hilf diese Visualisierung?

Die Namen sind also die Spalten ... auf dem Blatt steht Zeile und Wert.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
F Adjunkte Matrix erstellen Java Basics - Anfänger-Themen 3
M Matrix Java Basics - Anfänger-Themen 3
F Matrix Multiplikation Java Basics - Anfänger-Themen 3
Al3xand3r01 Matrix, Nachbarelemente Java Basics - Anfänger-Themen 16
E Rückwärtsmultiplikation einer invertierten matrix Java Basics - Anfänger-Themen 2
U Dreiecks-Matrix mit Array Java Basics - Anfänger-Themen 3
Z Matrix Klasse mit Mehrdimensionalen Array (Addition, Multiplikation, to String) Java Basics - Anfänger-Themen 57
E 2D Array - char durch die Matrix "wandern" lassen Java Basics - Anfänger-Themen 7
M Matrix auf 4 Elemente untersuchen mit offenen Enden Java Basics - Anfänger-Themen 8
B Diskrete Faltung (Matrix) Randfälle Java Basics - Anfänger-Themen 8
M Matrix Elemente vergleichen Java Basics - Anfänger-Themen 11
N Quadratische Matrix inkl Summe Java Basics - Anfänger-Themen 8
J Methoden Moving a n integer matrix Java Basics - Anfänger-Themen 3
D Methoden Matrix Multiplikation Java Basics - Anfänger-Themen 27
O Matrix, Vektor Java Basics - Anfänger-Themen 9
H 2D Array, Symmetrische Matrix Java Basics - Anfänger-Themen 12
S Matrix spaltenweise befüllen Java Basics - Anfänger-Themen 1
T Zufällige Matrix in neue Matrix schreiben Java Basics - Anfänger-Themen 6
C Matrix-Werte werden nicht wie erwartet ausgegeben Java Basics - Anfänger-Themen 7
C Matrix erstellen Spaltensumme, Zeilensumme, Diagonale Java Basics - Anfänger-Themen 1
S Methoden Transponierte Matrix Java Basics - Anfänger-Themen 3
N Vererbung Submatrix mit Verweis auf Matrix erstellen Java Basics - Anfänger-Themen 9
J Matrix erstellen Java Java Basics - Anfänger-Themen 7
B Transponiertes Matrix Java Basics - Anfänger-Themen 12
J Überprüfen, ob eine 2D Matrix ein Baum ist Java Basics - Anfänger-Themen 5
C Matrix transponieren - Hilfe Java Basics - Anfänger-Themen 1
D Ausgabe einer Matrix mit System.out.println Java Basics - Anfänger-Themen 6
T Art 4 Felder Matrix Memory Java Basics - Anfänger-Themen 2
U Ist diese Methode zur Matrix Vektor Multiplikation korrekt ? Java Basics - Anfänger-Themen 5
L Matrix(Array) minimieren... Java Basics - Anfänger-Themen 9
E Matrix mit Vektor multiplizieren Java Basics - Anfänger-Themen 7
S eingegebene Matrix anzeigen Java Basics - Anfänger-Themen 4
J Matrix für Schachbrett Java Basics - Anfänger-Themen 6
G tga Datei lesen und in eine matrix umwandeln Java Basics - Anfänger-Themen 1
G Bilddaten in Matrix umwandeln Java Basics - Anfänger-Themen 1
T Eine String Matrix erstellen die eine boolean Funtion verwendet Java Basics - Anfänger-Themen 10
O Matrix Multiplizieren Java Basics - Anfänger-Themen 4
S LWJGL - Matrix vom Matrixstack laden Java Basics - Anfänger-Themen 3
T Matrix auf Symmetrie überprüfen Java Basics - Anfänger-Themen 6
V Matrix Transponieren Java Basics - Anfänger-Themen 3
V Methoden Matrix als 1D Array mit Werten füllen Java Basics - Anfänger-Themen 12
W Zweidimensionale Arrays als Matrix ausgeben Java Basics - Anfänger-Themen 8
R Matrix-Vektor-Multiplikation Java Basics - Anfänger-Themen 13
O Matrix ordnen Java Basics - Anfänger-Themen 4
M Symmetrische Matrix Java Basics - Anfänger-Themen 2
W Methoden Rang von einer Matrix mit Gauss Java Basics - Anfänger-Themen 0
U Matrix Subtrahieren Java Basics - Anfänger-Themen 12
E Input/Output convert string to two dimensional char and output = matrix Java Basics - Anfänger-Themen 2
A daten vom 1d array in 2d matrix speichern Java Basics - Anfänger-Themen 3
I Matrix überprüfen Java Basics - Anfänger-Themen 8
Z Matrix mit Vektor multiplizieren Java Basics - Anfänger-Themen 13
K Methoden Einlesen einer unbegrenzten Matrix über Konsole Java Basics - Anfänger-Themen 6
O Einlesen einer Matrix von der Console Java Basics - Anfänger-Themen 18
N Matrix/Vektoren Java Basics - Anfänger-Themen 3
N Matrix Java Basics - Anfänger-Themen 14
T Methode, die eine 2 dimensionale Matrix kopiert. Java Basics - Anfänger-Themen 16
J Matrix Java Java Basics - Anfänger-Themen 3
D 2 mehrdimensionale Matrix einlesen Java Basics - Anfänger-Themen 2
A N*N Matrix Determinante berechnen Java Basics - Anfänger-Themen 47
K Quadratische Matrix um 90° drehen Java Basics - Anfänger-Themen 5
C Programm zur Berechnung der Spur einer Matrix Java Basics - Anfänger-Themen 4
B Zeilenumbruch (zweidim. Matrix) Java Basics - Anfänger-Themen 2
O Java Matrix mal Matrix über while Schleife... Java Basics - Anfänger-Themen 10
O Transponieren einer Matrix per While-Schleife Java Basics - Anfänger-Themen 3
M Matrix - Probelm Java Basics - Anfänger-Themen 7
O 2D Matrix befüllen mit geraden Zahlen!? Java Basics - Anfänger-Themen 14
J Java Matrix befüllen Java Basics - Anfänger-Themen 5
M Matrix Matrix Multiplikation Java Basics - Anfänger-Themen 6
F Matrix Java Basics - Anfänger-Themen 11
E Array als Matrix Java Basics - Anfänger-Themen 21
G OOP Parameter Matrix Java Basics - Anfänger-Themen 2
N Matrix Klasse Java Basics - Anfänger-Themen 4
B Maske an eine Matrix anpassen Java Basics - Anfänger-Themen 5
W Matrix übergeben Java Basics - Anfänger-Themen 7
T Matrix transponieren Java Basics - Anfänger-Themen 17
W Eine Methode schreiben, ob eine Matrix eine Diagonalmatrix ist.? Java Basics - Anfänger-Themen 3
M String Datei in Float-Matrix umwandeln Java Basics - Anfänger-Themen 8
D Problem: Werte eine Matrix vergleichen! Java Basics - Anfänger-Themen 5
B Matrix Java Basics - Anfänger-Themen 2
Semox Matrix multiplizieren Java Basics - Anfänger-Themen 4
N Matrix an toString Java Basics - Anfänger-Themen 7
C Diagonale in einem NxN Matrix Java Basics - Anfänger-Themen 6
F Einträgen von Matrix zu sotieren Java Basics - Anfänger-Themen 2
D JUnit auf Matrix anwenden Java Basics - Anfänger-Themen 5
J Spezielle Matrix ausgeben ! Java Basics - Anfänger-Themen 8
S Problem bei Matrix Addition Java Basics - Anfänger-Themen 5
F matrix werte übergeben Java Basics - Anfänger-Themen 5
M Hauptdiagonale Matrix berechnen Java Basics - Anfänger-Themen 6
M Klassenerstellung für Matrix mit Rechenopperationen Java Basics - Anfänger-Themen 42
D Matrix .bat datei erstellen und öffnen Java Basics - Anfänger-Themen 2
J Matrix ausgeben Java Basics - Anfänger-Themen 9
N Matrix Matrix Produkt Java Basics - Anfänger-Themen 7
N prüfe ob etwas in einer Matrix steht... Java Basics - Anfänger-Themen 14
L rechtecke zeichnen anhand von matrix Java Basics - Anfänger-Themen 27
J Matrix aus Datei einlesen mit StreamTokenizer Java Basics - Anfänger-Themen 3
K Transponiere Matrix Java Basics - Anfänger-Themen 4
Z mehrdimensionales Array, Matrix "invertieren" Java Basics - Anfänger-Themen 4
P Initialisierung einer 5*5 Matrix mit best. Werten Java Basics - Anfänger-Themen 2
B Matrix package ? Java Basics - Anfänger-Themen 7
N Initialisieren einer zufälligen Matrix Java Basics - Anfänger-Themen 12

Ähnliche Java Themen

Anzeige

Neue Themen


Oben