Dynamische Datenstrukturen

Question 1

Aufgrund welches Kriteriums ist ein Vektor eine dynamische Datenstruktur?

Answer 1

Da sich die Grösse des Vektors zur Laufzeit ändern kann (durch Operationen wie 𝚙𝚞𝚜𝚑_𝚋𝚊𝚌𝚔), ist ein Vektor eine dynamische Datenstruktur.

Question 2

Was ist ein Array und was macht der 𝚗𝚎𝚠-Ausdruck?

Answer 2

Mit dem 𝚗𝚎𝚠-Operator kann man einen neuen, zusammenhängenden Bereich im Speicher für n Elemente allozieren (reservieren). Dieser Speicherbereich wird Array genannt.

Question 3

Was ist 𝚙 im Ausdruck 𝚙 = 𝚗𝚎𝚠 𝚒𝚗𝚝[𝟽]?

Answer 3

Der Wert von 𝚙 ist die Startadresse des (neu angelegten) Speicherblocks des Typs 𝚒𝚗𝚝 mit 7 Elementen.

Question 4

Was ist der Unterschied zwischen dem 𝚗𝚎𝚠-Ausruck und einem Vektor?

Answer 4

Beim 𝚗𝚎𝚠-Ausdruck lebt der Speicher nicht nur innerhalb des Scopes des Ausdrucks, sondern bis Ende Programm oder bis der mit 𝚗𝚎𝚠 allozierte Speicher explizit freigegeben wird (mit der 𝚍𝚎𝚕𝚎𝚝𝚎-Funktion).
Zum Vergleich lebt beim Vektor der Speicher nur innerhalb des Funktionsaufrufs.

Question 5

Was ist ein Zeiger und wie sieht ein Zeiger syntaktisch aus?

Answer 5

Ein Zeiger ist ein Ausdruck und wird mit 𝚃* 𝚟𝚗𝚊𝚖𝚎 initialisiert, wobei 𝚃 der dem Pointer zugrunde liegende Typ ist und 𝚟𝚗𝚊𝚖𝚎 die Variable des Zeigers.

Question 6

Was ist der Adress-Operator und wie ist sieht er syntaktisch aus?

Answer 6

Der Adress-Operator &𝚟𝚗𝚊𝚖𝚎 gibt die Adresse eines bestehenden Ausdrucks 𝚟𝚗𝚊𝚖𝚎 bekannt.
Es ist ein L-Wert, d.h. man kann mit der Adresse des Ausdrucks auch weiterarbeiten.

Question 7

Sei 𝚒 ein Ausduck des Typs 𝚒𝚗𝚝 mit Wert 𝚒 = 𝟻. Wie würde man syntaktisch einen Pointer 𝚙 mit der Adresse von 𝚒 initialisieren?

Answer 7

𝚒𝚗𝚝* 𝚙 = &𝚒

Ein Zeiger 𝚙 mit Adresse von 𝚒 als Wert

Question 8

Was macht der Dereferenz-Operator und wie sieht er syntaktisch aus?

Answer 8

Der Dereferenz-Operator * hat als Wert den Wert des Ausdrucks an der Adresse von p. (Achtung: Hier steht der Stern vor dem bereits initialisierten Ausdruck, der Typ muss also nicht angegeben werden!)

Zum Beispiel ist 𝚒𝚗𝚝 𝚒 = 𝟻 und 𝚒𝚗𝚝* 𝚙 = &𝚒 ein Zeiger auf die Adresse von 𝚒, dann ist *𝚙 wiederum der Wert mit Typ von 𝚒, sprich *𝚙 = 𝟻 mit Typ 𝚒𝚗𝚝.

Question 9

Was ist der Null-Zeiger und wie sieht er syntaktisch aus und was gilt es bei seiner Verwendung zu beachten?

Answer 9

Der Null-Zeiger ist ein spezieller Zeigertyp, der angibt, dass noch auf kein Objekt gezeigt wird. Er wird zur Problemfindung und zur Fehlerbehebung gebraucht, um undefiniertes Verhalten zu vermeiden. Syntaktisch wird er durch 𝚃* 𝚙 = 𝚗𝚞𝚕𝚕𝚙𝚝𝚛 initialisiert.
Achtung: Der Null-Zeiger kann aufgrund der soeben genannten Eigenschaften nicht dereferenziert werden, da ansonsten ein Laufzeitfehler auftritt.

Question 10

Wie kann man mit Zeigern arithmetische Operationen durchführen und was ist der Nutzen davon?

Answer 10

Da ein neuer Zeiger 𝚃* 𝚙 = 𝚗𝚎𝚠 𝚃[𝚗] immer auf den ersten Block des neuen Speichers zeigt, kann man mit arithmetischen Operationen wie z.B. der Addition auf hintere Blöcke zugreifen. So gibt z.B. *(𝚙 + 𝟹) den Wert des vierten Blocks aus.
(Zählung wie bei Vektoren bei null beginnend.)

Question 11

Welches sind die drei Zeigeroperatoren (abgesehen der arithmetischen Operatoren) und welche Stelligkeit, Präzedenz und Assoziativität haben sie? Welche Art von Werten werden welcher Art von Werten zugeordnet (L- / R-Wert)?

Answer 11

Die drei Zeigeroperatoren sind: (In Klammern Stelligkeit, Präzendenz, Assoziativität und Zuordnung in dieser Reihenfolge)

• Subskript [𝚗] (2, 17, links, R → L)
• Dereferenzierung * (1, 16, rechts, R → L)
• Adresse & (1, 16, rechts, L → R)

Bemerke, dass der Subskript-Operator eine “direkte Form” des Dereferenzierungs-Operators ist:
*(𝚙 + 𝚒) ⇔ 𝚙[𝚒].

Question 12

Wie kann man über ein Array iterieren? Beantworte die Frage an einem Beispiel, wie der Codeausschnitt eines Programms aussehen würde, das den Durchschnitt von fünf in einem Array gespeicherten Zahlen ermitteln will?

Answer 12

Man lässt eine Schlaufe über alle Adressen des Arrays gehen und wertet diese mit dem Dereferenzierungs-Operator aus. Für besagtes Programm mit einem Pointer 𝚙 könnte man verwenden:

𝚏𝚘𝚛 (𝚒𝚗𝚝 𝚒 = 0; 𝚒 < 𝟻; 𝚒++) {
𝚜𝚞𝚖 += 𝚙[𝚒];
}
𝚛𝚎𝚝𝚞𝚛𝚗 (𝚜𝚞𝚖 / 𝟻);

Question 13

Was ist Random Access und sequentieller Zugriff? Weshalb ist sequentieller Zugriff für eine Zeigeriteration besser geeignet als Random Access?

Answer 13

Random Access (dt.: Wahlfreier Zugriff) beschreibt das “Springen” an beliebige Adressen des Arrays, wo hingegen sequentieller Zugriff immer nur zur nächsten bzw. vorherigen Adresse springt.

Syntaktisch:
Random Access → 𝚙[0], 𝚙[𝟷] oder *(𝚙+0), *(𝚙+𝟷), …
Sequentiell → ++𝚙, ++𝚙, ++𝚙, …

Beim Iterieren ist der sequentielle Zugriff schneller, da die immer nur addiert werden muss. Als Metapher nehme man ein Buch, das man liest. Beim sequentiellen Zugriff blättert man einfach immer auf die nächste Seite, wohingegen man beim Random Access das Buch immer wieder zuklappt, bevor man die nächste Seite öffnet.

Question 14

Was ist der hauptsächliche Unterschied (und auch Nachteil) eines statischen Arrays zu einem dynamischen Array?

Answer 14

Bei einem statischen Array ist ein grosser Nachteil, dass die Grösse des Arrays konstant sein muss, z.B. 𝟻 oder 𝟺*𝟹+𝟸, jedoch kein erst später eingelesener Wert, wie z.B. 𝚜𝚝𝚍::𝚌𝚒𝚗&raquo_space; 𝚗.

Question 15

Wie würde eine Funktion aussehen, mit der man ein Intervall eines Arrays mit Werten füllt?

Answer 15

𝚟𝚘𝚒𝚍 𝚏𝚒𝚕𝚕(𝚒𝚗𝚝* 𝚋𝚎𝚐𝚒𝚗, 𝚒𝚗𝚝* 𝚎𝚗𝚍, 𝚒𝚗𝚝 𝚟𝚊𝚕𝚞𝚎) {
𝚏𝚘𝚛 (𝚒𝚗𝚝* 𝚙 = 𝚋𝚎𝚐𝚒𝚗; 𝚙 != 𝚎𝚗𝚍; ++𝚙)
*𝚙 = 𝚟𝚊𝚕𝚞𝚎;
}

Man definiert folglich Anfang und Ende des Intervalls und füllt die Blöcke dazwischen mit dem gewünschten Wert.

Question 16

Wie unterscheiden sich folgende Deklarationen?

(1) 𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝 𝚙;
(2) 𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝* 𝚙;
(3) 𝚒𝚗𝚝* 𝚌𝚘𝚗𝚜𝚝 𝚙;
(4) 𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝* 𝚌𝚘𝚗𝚜𝚝 𝚙;

Answer 16

Für
(1)  𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝 𝚙;
(2) 𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝* 𝚙;
(3) 𝚒𝚗𝚝* 𝚌𝚘𝚗𝚜𝚝 𝚙;
(4) 𝚒𝚗𝚝 𝚌𝚘𝚗𝚜𝚝* 𝚌𝚘𝚗𝚜𝚝 𝚙;
sind die vier Ausschnitte wie folgt deklariert:

(1) 𝚙 ist eine konstante Ganzzahl.
(2) 𝚙 ist ein Zeiger auf eine konstante Ganzzahl.
(3) 𝚙 ist ein konstanter Zeiger auf eine Ganzzahl.
(4) 𝚙 ist eine konstanter Zeiger auf eine konstante Ganzzahl.

Question 17

Was bringt es, einen Zeiger auf einen konstanten Ausdruck zu deklarieren?

Answer 17

Viele Zeiger werden auch gebraucht, um Daten nur zu lesen und nicht zu verändern. Dann definiert man einen Zeiger auf einen konstanten Wert (oder mehrere konstante Werte).

Question 18

Wie würde eine Funktion aussehen, die ein eingegebenes Wort auf die Eigenschaft eines Palindroms überprüft (d.h., das Wort muss rückwärts und vorwärts gleich sein)?

Answer 18

𝚋𝚘𝚘𝚕 𝚒𝚜_𝚙𝚊𝚕𝚒𝚗𝚍𝚛𝚘𝚖𝚎 (𝚌𝚘𝚗𝚜𝚝 𝚌𝚑𝚊𝚛* 𝚋𝚎𝚐𝚒𝚗, 𝚌𝚘𝚗𝚜𝚝 𝚌𝚑𝚊𝚛* 𝚎𝚗𝚍) {
𝚠𝚑𝚒𝚕𝚎 (𝚋𝚎𝚐𝚒𝚗 < 𝚎𝚗𝚍)
𝚒𝚏 (*(𝚋𝚎𝚐𝚒𝚗++) != *(–𝚎𝚗𝚍)) 𝚛𝚎𝚝𝚞𝚛𝚗 𝚏𝚊𝚕𝚜𝚎;
𝚛𝚎𝚝𝚞𝚛𝚗 𝚝𝚛𝚞𝚎;
}

Die Funktion überprüft also mittels eines Zeigers, ob jeweils der erste und letzte, zweite und zweitletzte, usw. Buchstabe gleich sind. Falls ja, wird 𝚝𝚛𝚞𝚎 zurückgegeben.

Question 19

Wie definiert man syntaktisch einen eigenen Vektor 𝚊𝚟𝚎𝚌, der auf einem Array basiert?
Tipp: Klasse

Answer 19

Wir generieren eine Klasse 𝚊𝚟𝚎𝚌, die alle Eigenschaften und Funktionen eines Vektors enthält (hier mit Zeilennummerierung):

𝟷   𝚌𝚕𝚊𝚜𝚜 𝚊𝚟𝚎𝚌 {
𝟸     𝚙𝚛𝚒𝚟𝚊𝚝𝚎:
𝟹       𝚒𝚗𝚝* 𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜;
𝟺       𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚌𝚘𝚞𝚗𝚝;
𝟻     𝚙𝚞𝚋𝚕𝚒𝚌:
𝟼       𝚊𝚟𝚎𝚌(𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚜𝚒𝚣𝚎);
𝟽       𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚜𝚒𝚣𝚎() 𝚌𝚘𝚗𝚜𝚝;
𝟾       𝚒𝚗𝚝& 𝚘𝚙𝚎𝚛𝚊𝚝𝚘𝚛[] (𝚒𝚗𝚝 𝚒);
𝟿       𝚟𝚘𝚒𝚍 𝚙𝚛𝚒𝚗𝚝(𝚜𝚝𝚍::𝚘𝚜𝚝𝚛𝚎𝚊𝚖& 𝚜𝚒𝚗𝚔) 𝚌𝚘𝚗𝚜𝚝;
𝟷0   }

Dabei ist...
... 𝟹 ein Pointer zum ersten Element.
... 𝟺 die Anzahl Elemente.
... 𝟼 der Konstruktor für den Vektor.
... 𝟽 die Grösse des Vektors.
... 𝟾 das Überladen des Index-Operators [].
... 𝟿 das Ausgeben der Elemente.

Question 20

Was ist 𝚝𝚑𝚒𝚜 und was macht es?

Answer 20

𝚝𝚑𝚒𝚜 ist ein Zeiger, der auf Membervariablen zugreift. Da dieser Zeiger so häufig gebraucht wird, hat er einen eigenen Namen.
Will man z.B. auf die Member-Variable 𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜 in einer Klasse zugreifen, so kann man dem Zeiger 𝚝𝚑𝚒𝚜 zu der gewünschten Member-Variable folgen und diese dereferenzieren, sprich:
𝚝𝚑𝚒𝚜->𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜 ⇔ (*𝚝𝚑𝚒𝚜).𝚎𝚕𝚎𝚖𝚎𝚗𝚝𝚜.

Achtung: 𝚝𝚑𝚒𝚜 greift jeweils auf die Member-Variablen derselben Klasse zu, über die “geschrieben” wird (z.B. in einer Funktion). Sprich: “In DIESER Klasse, greife auf die Member-Variable xy zu”.

Question 21

Weswegen sollte man bei der Konstruktion einer Klasse für Array-basierte Vektoren beim Überladen des []-Operators mit Referenzen arbeiten?

Answer 21

Da dies benötigt wird, um später in den Vektor schreiben zu können:
𝚒𝚗𝚝& 𝚊𝚟𝚎𝚌::𝚘𝚙𝚎𝚛𝚊𝚝𝚘𝚛[] (𝚒𝚗𝚝 𝚒)

Question 22

Betrachte folgendes Zitat aus der Vorlesung:

“(…), denn man kann nicht einfach sagen: Ey Speicherblock, wachs mal!”
(Schwerhoff, 26.11.2019).

Wie kann dies interpretiert werden?

Answer 22

Ein allozierter Speicherblock (z.B. 𝚗𝚎𝚠 𝚒𝚗𝚝[𝟹]) kann nachträglich nicht mehr vergrössert oder verkleinert werden. Will man also nachträglich mehr Speicher, so muss man neuen, grösseren Speicher allozieren.

Question 23

Wie muss man vorgehen, will man Elemente in einem Array löschen bzw. neue Elemente an beliebiger Position einfügen?

Answer 23

Man kann nicht einfach beliebige Elemente “aus der Mitte heraus” löschen bzw. einfügen, denn man muss in einem Array stets alle vorherigen oder nachfolgenden Elemente verschieben.