Dünn besetzte Matrix

[baker333]

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:

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:

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]

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?

 

[baker333]

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

Die Lösung ist die Musterlösung des Skripts.

 

[baker333]

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

 

[kneitzel]

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.

 

[baker333]

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]

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]

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.