Array umsortieren?

Jens Gast 16.04.2006 21:27 #364823

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

Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden

Μαtthias W. (matthias) 16.04.2006 22:41 #364824

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

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Simon K. (simon) 17.04.2006 01:13 #364825

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 :-)

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Roland P. (pram) 17.04.2006 02:26 #364826

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

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Nico Schümann Gast 17.04.2006 14:20 #364827

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^^

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Μαtthias W. (matthias) 17.04.2006 14:28 #364828

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

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Ingo Gast 18.04.2006 13:34 #364829

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

Antwort Zitieren Bearbeiten Löschen Beitrag melden

Array umsortieren?

Antwort schreiben