Array Links/Rechtsverschiebung
-
nachdem scheinbar eh keine sentinels verwendet werden sollen würde ich mir überlegen evtl. memmove/memcpy zu verwenden.
-
Wenn du immer nur um eine Stelle verschieben möchtest, reicht es, den ersten Wert zu speichern und in einer Schleife alle Werte zu verschieben.
void shl1(int* v, size_t s) { int i=0; int fst = v[0]; for(;i<(s-1);++i) v[i] = v[i+1]; v[s-1] = fst; }Wenn der "shift" größer sein sollte, könnte man erst einmal temporären Speicher anfordern:
int shl(int* v, size_t s, size_t shift) { int i=0; int* p = malloc(s*sizeof(int)); if(!p) return 0; for(;i<s;++i) p[i] = v[(i+shift)%s]; memcpy(v,p,s*sizeof(int)); free(p); return 1; }Es fällt aber auf, dass dies Verschwendung ist. Wenn wir uns, wie im ersten Beispiel, merken würden, was überschrieben wird, reicht auch das Anfordern von (shift Elementen):
int shl(int* v, size_t s, size_t shift) { int i=0; int* p; shift%=s; // shift darf maximal s-1 sein, bei 0 Abbruch, da es keinen Effekt hätte if(!shift) return 1; p = malloc(shift*sizeof(int)); if(!p) return 0; memcpy(p,v,shift*sizeof(int)); for(;i<s-shift;++i) v[i] = v[(i+shift)%s]; memcpy(&(v[s-shift]),p,shift*sizeof(int)); free(p); return 1; }Der Rechtsshift funktioniert genau so, nur umgekehrt
(Auch bei Codepad getestet).
-
Vicious Falcon schrieb:
Wenn der "shift" größer sein sollte, könnte man erst einmal temporären Speicher anfordern:
...Wenn man die mem*-Funktionen verwenden will, empfehle ich, auf _-- zu hören und memmove zu nehmen. Das kümmert sich automatisch darum.
-
Eine 1-shift Verschiebung ohne malloc
void left_shift(int *v, size_t size) { int v1 = v[0]; memmove(v, v+1, (size - 1) * sizeof *v); v[size - 1] = v1; } void right_shift(int *v, size_t size) { int vn = v[size - 1]; memmove(v+1, v, (size - 1) * sizeof *v); v[0] = vn; }
-
Vicious Falcon schrieb:
Wenn wir uns, wie im ersten Beispiel, merken würden, was überschrieben wird, reicht auch das Anfordern von (shift Elementen)
Rein theoretisch reicht das Anfordern von einem einzigen Element:
#define SWAP(type, a, b) do{type tmp=(a);(a)=(b);(b)=tmp;}while(0) static void reverse(int *v, size_t n) { size_t i, j; for (i = 0, j = n - 1; i <= j; ++i, --j) SWAP (int, v[i], v[j]); } void right_shift (int *v, size_t n, size_t shift) { reverse (v , shift); reverse (v + shift, n - shift); reverse (v , n ); } void left_shift (int *v, size_t n, size_t shift) { reverse (v , n ); reverse (v + shift, n - shift); reverse (v , shift); }Übrigens eine arbitrary-shift Verschiebung ohne malloc.
Da hier scheinbar alle eine Verifizierung auf codepad verlangen, hier auch mein Testprogramm: http://codepad.org/4UktlOqb
-
auweia, das muss ich erstmal verdauen..
ich versuch das ganze erstmal zu verstehen und dann umzusetzen, wenn ich auf Probleme stoße werd ich mich sicher nochmal melden
-
space_optimized schrieb:
#define SWAP(type, a, b) do{type tmp=(a);(a)=(b);(b)=tmp;}while(0) static void reverse(int *v, size_t n) { size_t i, j; for (i = 0, j = n - 1; i <= j; ++i, --j) SWAP (int, v[i], v[j]); }Wtf? Ein dreckiges Makro, das einen Namen fängt, aber nur einmal verwendet wird?
-
void main (){ int a, i, j, safe, v[10] = {1,2,3,4,5,6,7,8,9,10}, max=10; printf("Vektor - linksrotation\n"); for (i = 0; i < max; i++) // Vektor ohne Verschiebung ausgeben printf("%d ",v[i]); printf("\n"); for (j = 0; j < max; j++) // Schleife um das ganze 10 mal zu wiederholen { int i; // 2te -mal deklariert warum??? safe = v[0]; for (i = 0; i < max; i++) // Linksverschiebung initialisieren { if (i == max-1) v[i] = safe; else { v[i] = v[i+1]; } printf ("%d ", v[i]); // Ausgabe des neuen Vektors } printf ("\n"); } wait(a=1); // Dummy Fkt damit Fenster in visual geöffnet bleibt }Die Linksverschiebung funktioniert!
Ich frag mich nur warum ich in der "for (j =..." Schleife noch einmal i deklarieren muss, obwohl ich das ja am Anfang in der Main schon getan hab.
-
Nicht schön zweimal i zu verwenden. Die Sache bei dir ist so, dass das zweite i das erste überlagert. Du musst es nicht nochmal deklarieren in diesem Fall, sondern es nur nochmal 0 setzen. Da du dies in der Schleife schon machst ist die Deklarierung einfach überflüssig.
-
Gradiee schrieb:
Ich frag mich nur warum ich in der "for (j =..." Schleife noch einmal i deklarieren muss, obwohl ich das ja am Anfang in der Main schon getan hab.
Musst du gar nicht.
-
ok stimmt, der Compiler hat da wohl vorhin bisschen gesponnen
-
Wurde eigentlich schon in Betracht gezogen, das Array selbst gar nicht zu verschieben, sondern einfach nur einen Index zu verschieben?
#define VECTOR_LENGTH 10 typedef struct { int data[VECTOR_LENGTH]; size_t offset; } vector_t; int vector_get_at (vector_t *obj, size_t pos) { return obj->data[(pos + obj->offset)%VECTOR_LENGTH]; } void vector_set_at (vector_t *obj, int val, size_t pos) { obj->data[(pos + obj->offset)%VECTOR_LENGTH] = val; return; } void vector_rol (vector_t *obj) { obj->offset = (obj->offset + 1)%VECTOR_LENGTH; return; } void vector_ror (vector_t *obj) { obj->offset = (obj->offset + VECTOR_LENGTH - 1)%VECTOR_LENGTH; return; }Code nicht getestet, noch nichtmal kompilier.
-
Ich versteh nix von deinem Code
-
@Tim: hmmm, interessanter Ansatz, hab nicht dran gedacht.
-
Gradiee schrieb:
Ich versteh nix von deinem Code
Ja, etwas unglücklich. Ich hätte es besser erklären sollen. Die Idee ist, dass man nicht die Werte im Vektor verschiebt, sondern nur den "Blickwinkel" auf den Vektor, also wie man die Werte im Vektor interpretiert. Beispiel. Du hast ein Vektor[10]:
1 5 3 7 2 6 7 2 8 0Gleichzeitig haben wir im Ausgangszustand einen offset von 0:
1 5 3 7 2 6 7 2 8 0 ^Anstatt jetzt die Werte zu kopieren, ändern wir einfach nur den offset:
1 5 3 7 2 6 7 2 8 0 ^Wenn wir jetzt über den Vektor iterieren (Funktion
vector_get_at) würden wir das bekommen:5 3 7 2 6 7 2 8 0 1Also gleichbedeutend mit einem verschieben nach links.
Andersrum (offset wird "kleiner", darf aber nicht negativ werden, also muss 0-1 zu 9 werden):
1 5 3 7 2 6 7 2 8 0 ^Würde das Ergebnis einem verschieben nach rechts gleichkommen:
0 1 5 3 7 2 6 7 2 8Jetzt etwas klarer?
Diese Variante muss nicht schneller sein als einfaches umkopieren. Für kleine Vektorgrößen wird das umkopieren wahrscheinlich meist schneller sein. Auch hängt es davon ab wie oft aus dem Vektor gelesen bzw. in den Vektor geschrieben wird. "Shiftet" man beispielsweise oft um, und liest/schreibt nur selten, dann hätte "meine" Variante Vorteile. Wenn man aber Viel liest/schreibt und nur selten "shiftet" wäre die Kopiervariante vorteilhaft. "Meine" Variante hat u.U. auch Nachteile wenn die Vektorgröße keine Zweierpotenz ist. Unterm Strich wirst du wahrscheinlich bei der Kopiervariante bleiben, aber andere Ansätze zu kennen ist wichtig, weil man sowas immer mal brauchen kann.
-
Ja danke sehr gut erklärt
-
Ok naechstes Problem ..
Das ganze wird jetzt in ein Menue gepackt, einfach der Uebung wegen..char* wahl="[1] Vektor anzeigen\n"\ // Menue Auswahl "t2 - links rotieren\n"\ "\t3 - rechts rotieren\n"\ "\t4 - Mehrfache Links-/ Rechts-Rotation\n"\ "\t5 - Element l\224schen\n"\ "\t6 - Element einf\201gen\n"\ "\t0 - Beenden\n\n";uns wurde gezeigt man kann ein ganzes Menue einfach in ne Variable speichern, wobei das \ zeigen soll, das noch etwas kommt.
Mir sagt er aber, das das ein unbekanntes Token ist.
Muss ich jetzt noch eine Datei einbinden, oder warum geht das nicht?
-
Das Problem ist der Kommentar dahinter, mach den mal weg. Der Compiler versucht wegen des Backslashs, eine Escapesequenz zu bilden.
const char* wahl= "[1] Vektor anzeigen\n"\ "\t2 - links rotieren\n"\ "\t3 - rechts rotieren\n"\ "\t4 - Mehrfache Links-/ Rechts-Rotation\n"\ "\t5 - Element l\224schen\n"\ "\t6 - Element einf\201gen\n"\ "\t0 - Beenden\n\n";Edit: Das Literal sollte gleich als const deklariert werden.
-
Das Problem ist der Backslash dahinter, mach den mal weg. Der Compiler versucht wegen des Backslashs, eine Escapesequenz zu bilden.
char wahl[] = "[1] Vektor anzeigen\n" /* Menue Auswahl */ "[2] - links rotieren\n" "[3] - rechts rotieren\n" "[4] - Mehrfache Links-/ Rechts-Rotation\n" "[5] - Element l\224schen\n" "[6] - Element einf\201gen\n" "[0] - Beenden\n\n";