Speicherbedarf eines Strings? (als Byteangabe oder über andere Datentypen)

Bashar

e86 schrieb:

Zweifle langsam daran, dass ich die Aufgabe richtig bearbeite. Wir haben hier eine "einfaches verkettete Liste" aus Wörtern (also Strings). Und davor sollen wir (formell?) den Speicherbedarf berechnen. Es gibt hingegen keine Angabe für eine Sprache oder ein Sprachsystem (Latin, UTF...)

Kannst du mal bitte den Aufgabentext zitieren?

e86

Ja, gern.

1. (6 Punkte) Verkettete Listen: Gegeben sei eine einfach verkettete leere Liste zum Speichern von Strings mit einem Zeiger auf das erste Listenelement. Fügen Sie nacheinander die folgenden Elemente in diese Liste ein: Elbe Spree Pleiße Aue Elster Parthe

b.) (2 Punkte) Wie viel zusätzlicher Speicherplatz wird bei dieser Art von
Speicherung benötigt? Rechnen Sie auch den konkreten zusätzlichen Platz für die
obige Liste aus, inklusive des Zeigers auf die Liste selbst.

Gregor

e86 schrieb:

Danke für den ausführlichen Beitrag.

Du gehst von einem Array aus. Nur bin ich mir grad nicht so sicher, ob dass nicht nur für Arrays gilt und "einfach verkettete Listen" anders behandelt werden? Laut unseren Skripten wird da unterschieden. Andererseits könnte es ja auch sein, dass Java da nicht unterscheidet (unterscheiden kann) und man verkettete Listen nur in Form von Arrays implementieren kann.

Du hast doch eine Liste von Strings und nicht einen String, der aus einer Liste besteht? Oder habe ich das falsch verstanden? Natürlich kann man Strings auch über Listen implementieren. Und natürlich kann man Listen auch in Java implementieren (siehe z.B. java.util.LinkedList). Ich habe eher das angegeben, was ich in der Referenzimplementierung vermute. Ich glaube nicht, dass Strings in Java über eine Liste implementiert sind. Das würde alleine deshalb schon keinen Sinn machen, weil Strings immutable sind. Listen haben aber gerade dann einen Vorteil, wenn man damit in der Art arbeitet, dass man hier mal etwas ausschneidet oder da mal etwas dazwischensteckt oder ähnliches macht.

Gregor

e86 schrieb:

b.) (2 Punkte) Wie viel zusätzlicher Speicherplatz wird bei dieser Art von
Speicherung benötigt? Rechnen Sie auch den konkreten zusätzlichen Platz für die
obige Liste aus, inklusive des Zeigers auf die Liste selbst.

Der Trick liegt hier vermutlich im Wort "zusätzlich". Was ist die Alternative, mit der man da vergleichen soll?

e86

Alternative? Meinst du eine andere Vorgehensweise in einer anderen Sprache oder ähnlichem? Die Problematik mit den Zeigern habe ich erstmal herausgelassen, da ich mich erstmal um die Strings an sich kümmern wollte. Aber solangsam denke ich, sind die Zeiger sehr wichtig und müssen mit rein. (und können nicht erst am Ende "dazuaddiert" werden.)

Gregor

e86 schrieb:

Alternative? Meinst du eine andere Vorgehensweise in einer anderen Sprache oder ähnlichem? Die Problematik mit den Zeigern habe ich erstmal herausgelassen, da ich mich erstmal um die Strings an sich kümmern wollte. Aber solangsam denke ich, sind die Zeiger sehr wichtig und müssen mit rein. (und können nicht erst am Ende "dazuaddiert" werden.)

Du wirst Dich gar nicht um die Strings kümmern müssen. Wenn sie nach dem zusätzlichen Speicherplatz fragen, dann ist die Ausgangssituation definitiv so, dass die Strings schon existieren und nicht für den _zusätzlichen_ Speicherbedarf relevant sind. Es geht letztendlich nur um die Liste.

Vermutlich sollst Du da mal zeigen, dass Du weißt, wie so eine Liste aufgebaut ist. Was wird wo in einer Liste referenziert usw..

Th

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

Th schrieb:

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

selbst dann ist die aufgabe schlecht formuliert. ist es nun ein:

struct list_entry
{
  struct list_entry *next;
  char *string;
};

oder ein

struct list_entry
{
  struct list_entry *next;
  char string[MAX];
};

?
und ausserdem ist nirgends erwähnt, wie breit ein pointer ist.

Bei fehlenden Angaben bitte selbst eine Annahme treffen und diese aufschreiben.

Blue-Tiger

mies gemachte aufgabe schrieb:

Th schrieb:

Ich glaube, du hast die Aufgabe etwas mißverstanden.
Ich denke gemeint ist, daß du den zusätzlichen Speicherbedarf für die Linked-List angeben sollst, d.h. dass jedes Element der Liste einen Zeiger auf das nächste Element verwalten muß. (im Gegensatz zu einem Array)

selbst dann ist die aufgabe schlecht formuliert. ist es nun ein:
struct list_entry
{
  struct list_entry *next;
  char *string;
};
oder ein
struct list_entry
{
  struct list_entry *next;
  char string[MAX];
};
?
und ausserdem ist nirgends erwähnt, wie breit ein pointer ist.

Ich find die Aufgabe eindeutig formuliert: da wir von Java reden, wird dir der gesunde Menschenverstand sagen, dass ein Listenelement aus einer Referenz zum naechsten Element sowie einer Referenz auf den String besteht (und weil das nach einer Einfuehrungs-Vorlesung klingt, wirds vermutlich keine Rolle spielen dass jedes Element zusaetzlich noch 16 Bytes benoetigt).
Und wie Breit eine Referenz ist, spielt auch keine Rolle, weil er die Groesse ja in sizeof(Reference) angeben kann.

Zeus

Sind die Aufagben aus der Theoretische Informatik? Wenn ja dann will dein Prof evtl. sowas sehen

String speichern in Array:
Speicherbedarf: O(N+1)

String in eine Liste:
Speicherbedarf: O(NP+2) bei SingleLinked
O(N2P+2) bei DoubleLinked

Th

Den Speicherbedarf mit Hilfe der O-Notation zu beschreiben, macht absolut keinen Sinn.
Und wie groß der Speicherbedarf für einen Zeiger ist, ist auch (für diese Frage) irrelevant, nur daß er eben pro Listenelement benötigt wird.