Algorithmus: Array-Elemente verschieben

Wissenschaft Informatik
1

Hallo,

ich habe folgendes Problem, das ich nicht lösen kann:
Ich soll einen Algorithmus angeben, der die ersten k Elemente
eines Feldes

INPUT:

an das Ende des Feldes verschiebt

OUTPUT:

dabei nur den Speicherbereich des Feldes nutzt und eine Laufzeit von O(n) haben soll.

Da ich nach mehreren Versuchen ratlos bin, frage ich mich, ob das Problem nicht doch lösbar ist, und einer von Euch vielleicht die Lösung weiß…

Viele Grüße,
Thorsten

2

Hallo,

ich habe folgendes Problem, das ich nicht lösen kann:
Ich soll einen Algorithmus angeben, der die ersten k Elemente
eines Feldes

INPUT:

an das Ende des Feldes verschiebt

OUTPUT:

dabei nur den Speicherbereich des Feldes nutzt und eine
Laufzeit von O(n) haben soll.

Kommt drauf an, wie das Feld gegeben ist:

  1. Verkettete Liste (jeglicher Art): Kein Problem. Einfach den HeadPointer auf ak+1 richten, an mit a1 verlinken und den ponter von ak loeschen (auf das Dummy-element richten).

  2. Array von Bitstrings (incl. Pointer, Abstr.datentypen etc. via
    Typecast zu Bitsring (ist aber echt uebel)):

Via 3*xor kann man zwei Bitsrings inPlace vertauschen - du brauchst aber eine zusaetzliche Variable in der du dir merkst, wo Du gerade am vertauschen bist - also nicht ganz ohne zusätzlichen Speicher - aber ich glaube das ist im Sinne der Aufgabe ok.

MFG
Martin