www.mikrocontroller.net

Forum: Compiler & IDEs Array umsortieren?


Autor: Jens (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Simon K. (simon) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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 :-)

Autor: Roland Praml (pram)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Nico Schümann (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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^^

Autor: Μαtthias W. (matthias) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Ingo (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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 schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.