Forum: Compiler & IDEs Array umsortieren?


von Jens (Gast)


Lesenswert?

Moin moin,
ich habe hier ein zweidimensionales Char-Array(liste[8][10]) wo ich
nach und nach kurze Texte speichere (Speicherplatz 0...7). Dabei habe
ich noch eine Merkervariable, welches der nächste Speicherplatz ist.
Nach 7 kommt wieder 0, also ein Ringspeicher.
Die Ausgabe auf einem LC-Display erfolgt dann "Rückwerts", so dass
der zuletzt gespeicherte Text zuerst ausgegeben wird.
Jetzt will ich aber beim Hinzufügen eines Textes prüfen, ob dieser
schon in der Liste ist (geht bereits mit strcmp) und wenn dies der Fall
ist, den alten eintrag löschen, den Rest aufrücken und den neuen Eintrag
einfügen, wobei die Zeitliche Reihenfolge erhalten bleiben soll.
Ich hoffe, dass war jetzt nicht zu kompliziert erklärt...

Bsp, so sieht meine Liste nach einiger Zeit aus (vereinfacht):
0  AAA
1  BBB
2  CCC
3  DDD
4  EEE
5  FFF
6  GGG
7  HHH
Merker steht auf 4, und es kommt ein "GGG" hinzu. Dann müsste die
Liste danach so aussehen:
0  AAA
1  BBB
2  CCC
3  DDD
4  GGG
5  EEE
6  FFF
7  HHH
Merker steht jetzt auf 5.

Wie mache ich das jetzt möglichst sparsam? Ich habe zwar einen Mega128,
jedoch endet das bei mir bisher immer in einem wilden kopieren mit viel
Speicherbedarf.

Lösungsvorschläge sind willkommen, Danke! ;=)

mfg Jens

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

Hi

deine Liste ist ja im Prinzip nichts (naja, nicht viel) anderes als
eine Liste aus char *. Du brauchst jetzt also nur die Pointer umhängen.
Ich seh aber auch nicht wo du bei der Umkopiererei viel Speicher
brauchst.

Du benötigst halt einen zusätzlichen 10 Zeichen großen
Zwischenspeicher. Den kann man ja auf dem Stack anlegen. Der Vorteil
der Pointerumhängerei ist allerdings das du etwas schneller sein
dürftest was aber bei einer Stringlänge von 10 zu vernachlässigen sein
dürfte.

Und wenns nicht auf Geschwindigkeit ankommt kannst du das Umkopieren
auch mit dem "XOR-Trick" machen. Dann brauchts garkeinen zusätzlichen
Speicher.

Matthias

von Simon K. (simon) Benutzerseite


Lesenswert?

>>Und wenns nicht auf Geschwindigkeit ankommt kannst du das Umkopieren
auch mit dem "XOR-Trick" machen. Dann brauchts garkeinen
zusätzlichen
Speicher.

Hu? Erzähl ma :-)

von Roland P. (pram)


Lesenswert?

Ich denk er meint so:
mem1 = A
mem2 = B

mem1 = mem1 ^ mem2;  // mem1 = (A^B)
mem2 = mem2 ^ mem1;  // mem2 = (B ^ (A^B) )  = A
mem1 = mem1 ^ mem2;  // mem1 = (A^B) ^ A = B

Gruß
Roland

von Nico Schümann (Gast)


Lesenswert?

Aber XOR kann doch garnicht viel langsamer sein als sich erstmal neuen
Speicher zu holen und dann umzukompieren, oder denke ich da falsch?
Habs eben mal aufm Zettel nachgemacht.. Genial, was man mit
Bitmanipulation so hinbekommt^^

von Μαtthias W. (matthias) Benutzerseite


Lesenswert?

Hi

den Speicher den du dir vom Stack holst bekommst du "umsonst" da es
im Prinzip egal ist ob du Speicher für eine oder für 20 lokale
Variablen besorgst. Das mit dem XOR ist zwar im Prinzip nett bedeutet
aber das du eben die drei Operationen auch wirklich durchführen musst
während das reine Umkopieren auf zwei Load- und zwei Store-Operartionen
hinauslaufen sollte wenn der Compiler das ordentlich optimiert.

Matthias

von Ingo (Gast)


Lesenswert?

Am einfachsten geht das, mittels umhängen der Adressen der Strings.

Mal als (fast) C-Code und ohne Fehlerabfragen:

// erst mal initial den Speicher holen
char* liste[8];
for (i = 0; i<8; i++)
{
  liste[i] = malloc(10*sizeof(char));
}

...

//
i = 0;
do
{
  //strcmp, found zeigt an, ob der Strin gefunden wurde
} while (i<8 && !found);


// jetzt Umhängen der Zeiger, hier muss noch auf den Ringpuffer
erweitert werden. Der code stellt nur das Prinzip dar
char* help = liste[i];
while(i>merker)
{
  liste[i] = liste[i-1]; // hier werden nur Zeiger umgehangen. Es wird
nicht kopiert
  i--;
}
liste[merker] = help; // hier wird jetzt der Zeiger für GGG gesetzt

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.