Ich implementiere mehrere Datenstrukturen und ein Grundelement, das ich verwenden möchte, ist das Folgende: Ich habe einen Speicherblock A [N] (er hat eine variable Länge, aber ich nehme 100 für meine Beispiele) und in diesem Block befindet sich ein kleinerer Teil C der Länge K (sagen wir 30), die ich verschieben möchte, ohne zusätzlichen Speicher zu verwenden.

Die zusätzliche Schwierigkeit besteht darin, dass A "umschließt", das heißt, C kann bei A [80] beginnen, und dann sind die ersten 20 Elemente von C die Elemente A [80..100] und die letzten 10 Elemente sind die Elemente A [ 0..10]. Darüber hinaus kann der Zielbereich auch in irgendeiner Weise mit C "umwickeln" und überlappen. Außerdem möchte ich nicht mehr als eine konstante Menge zusätzlichen Speichers verwenden, alles sollte an Ort und Stelle geschehen. Außerdem kann der Teil von A, der weder im Zielbereich noch im Quellbereich liegt, etwas Wichtiges enthalten, sodass er auch nicht verwendet werden kann. Ein Fall wäre also der folgende:

A sieht so aus:

| 456789ABCDEF0123456789AB | ----- | 0123 |

Und sollte dazu transformiert werden:

| 89AB | ----- | 0123456789ABCDEF01234567 |

Die einfache Delegierung an eine Bibliothek oder die Verwendung einer anderen Datenstruktur aus einer Bibliothek ist hier keine Option. Ich möchte das Problem selbst verstehen. Auf den ersten Blick dachte ich, dass es vielleicht nicht trivial ist, aber sobald Sie ein paar Fälle unterscheiden, wird es klar, aber jetzt habe ich ernsthafte Probleme. Natürlich gibt es die trivialen Fälle, wenn sie sich nicht überlappen oder nicht umbrechen, aber zumindest, wenn beide gleichzeitig auftreten, wird es chaotisch. Sie könnten mit einem freien Platz beginnen und das dazugehörige Teil dorthin verschieben, aber dann erstellen Sie ein anderes freies Teil an einer anderen Stelle, und es wird schwierig, den Überblick darüber zu behalten, welche Teile Sie noch verwenden können.

Vielleicht fehlt mir etwas komplett, aber selbst mein Sonderfall, wenn der Zielbereich nicht umbrochen wird, besteht aus fast 100 Zeilen (die Hälfte davon sind Behauptungen und Kommentare), und ich könnte ihn aktualisieren, sodass er auch den allgemeinen Fall mit einigen zusätzlichen Zeilen behandelt Indexberechnungen, aber wenn jemand eine elegante und kurze Lösung hat, würde ich etwas Hilfe schätzen. Intuitiv denke ich, dass dies irgendwie trivial sein sollte, aber ich sehe nur noch nicht die beste Lösung.

Hinweis: Der interessante Fall ist natürlich, wenn C fast so groß ist wie A. Wenn | C | <N / 2, es ist trivial.

edit: Das Verwenden von mehr als einer konstanten Menge zusätzlicher Flags / Indizes zählt als zusätzlicher Speicher und ich möchte dies nach Möglichkeit vermeiden.

edit: Einige Leute wollten meinen Code sehen. Meine Frage ist eher abstrakt, deshalb wollte ich sie nicht posten, aber vielleicht sieht jemand, wie man sie verbessern kann. Es ist schrecklich, es funktioniert nur für den Fall, dass das Ziel am Anfang beginnt (was jedoch leicht geändert werden kann) und schrecklich lang ist, aber es erledigt die Arbeit ohne zusätzlichen Speicher in O (n).

#include <stddef.h>
#include <stdio.h>
#include <string.h>
#include <assert.h>

void move_part(int* A, size_t N, size_t target, size_t source, size_t size, int show_steps)
{
  assert(source + size <= N);
  assert(target + size <= N);
  if (show_steps) {
    printf("Moving size %d from %d to %d.\n", size, source, target);
  }
  memmove(A + target, A + source, size * sizeof(int));
}

void swap_parts(int* A, size_t N, size_t first_begin, size_t second_begin, size_t size, int show_steps)
{
  if (show_steps) {
    printf("Swapping size %d at %d and %d.\n", size, first_begin, second_begin);
  }
  assert(first_begin + size <= N);
  assert(second_begin + size <= N);
  size_t i;
  for (i = 0; i < size; ++i) {
    int x = A[first_begin + i];
    A[first_begin + i] = A[second_begin + i];
    A[second_begin + i] = x;
  }
}

void move_to_beginning(int* A, size_t N, size_t begin, size_t size, int show_steps)
{
  assert(begin <= N);
  assert(size <= N);
  // Denotes the start of our "working range". Increases during
  // the algorithm and becomes N
  size_t part_start = 0;
  // Note: Keeping the size is crucial since begin == end could
  // mean that the range is empty or full.
  size_t end = (begin + size) % N;
  while (part_start != N) {
    size_t i;
    if (show_steps) {
      for (i = 0; i < N; ++i) {
    printf("%d ", A[i]);
      }
      printf("\n");
      printf("part_start %d  begin %d  end %d  size %d\n", part_start, begin, end, size);
    }
    // loop invariants
    assert(part_start < N);
    // The two pointers are in our range
    assert(part_start <= begin && begin <= N);
    assert(part_start <= end && end <= N);
    // size is valid (wrapped case, non-empty, non-full case)
    assert(begin <= end || (N - begin) + (end - part_start) == size);
    // size is valid (non wrapped case, non-empty, non-full case)
    assert(begin >= end || end - begin == size);
    // size is valid (working range is full or empty case)
    assert(begin != end || size == 0 || part_start + size == N);
    if (size == 0 || begin == N || begin == part_start) {
      // ##|1234|# -> 1234### ||
      if (show_steps) {
    printf("Case 1:\nTerminating\n");
      }
      // #||# -> ## ||
      // 12|##| -> 12## ||
      // |12|## -> 12## ||
      break;
      /* Not necessary any more, but would be the correct transformation:
     part_start = N;
     begin = N;
     end = N;
     size = 0;*/
    } else if (end == part_start) {
      // |##|123 -> ##|123|
      if (show_steps) {
    printf("Case 2:\n");
    printf("Setting end to %d.\n", N);
      }
      end = N;
    } else if (begin < end) {
      // ##|1234|# -> 1234### ||
      if (show_steps) {
    printf("Case 3:\n");
      }
      move_part(A, N, part_start, begin, size, show_steps);
      break;
      /* Not necessary any more, but would be the correct transformation:
     part_start = N;
     begin = N;
     end = N;
     size = 0;*/
    } else {
      size_t end_size = end - part_start;
      size_t begin_size = N - begin;
      assert(begin_size + end_size == size);
      if (end_size >= begin_size) {
    // 345|#|12 -> 12 5|#|34
    if (show_steps) {
      printf("Case 4:\n");
    }
    swap_parts(A, N, part_start, begin, begin_size, show_steps);
    assert(begin_size > 0); // Necessary for progress
    part_start += begin_size;
    size = end_size;
    // begin, end remain unchanged
      } else if (begin - part_start <= begin_size) {
    // 56|#|1234 -> 123 56|#|4
    size_t size_moved = begin - part_start;
    assert(size_moved >= end_size); // else the next step would be more efficient
    if (show_steps) {
      printf("Case 5\n");
    }
    swap_parts(A, N, part_start, begin, end_size, show_steps);
    move_part(A, N, end, begin + end_size, begin - end, show_steps);
    assert(end_size + (begin - end) == size_moved);
    size -= size_moved;
    part_start = begin;
    begin += size_moved;
    end += size_moved;
      } else if (end_size <= begin_size) {
    // 45|##|123 -> 123 #|45|# 
    if (show_steps) {
      printf("Case 6\n");
    }
    swap_parts(A, N, part_start, begin, end_size, show_steps);
    move_part(A, N, end, begin + end_size, begin_size - end_size, show_steps);
    part_start += begin_size;
    size = end_size;
    end = begin + end_size;
    // begin remains unchanged
      } else {
    // No case applies, this should never happen
    assert(0);
      }
    }
  }
}


int main()
{
  int N = 20;
  int A[20];
  size_t size = 17;
  size_t begin = 15;
  size_t i;
  for (i = 0; i < size; ++i) {
    A[(begin + i) % N] = i;
  }
  move_to_beginning(A, N, begin, size, 0);
  for (i = 0; i < size; ++i) {
    printf("%d ", A[i]);
  }
  printf("\n");
  return 0;
}