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?
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:
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:
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?
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;