mikrocontroller.net

Forum: Compiler & IDEs doppelte Einträge in Array löschen


Autor: Kai (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich versuche eine Funktion zu schreiben, der ich ein Array übergeben 
kann und diese mir dann das Array sortiert. Es soll dabei nach doppelten 
Einträgen gesucht werden. Es handelt sich um ein Byte Array. Wird ein 
doppelter Eintrag gefunden so wird dieser gelöscht und der Rest des 
Arrays soll um einen Platz weiter rutschen. Der Rest wird mit Nullen 
aufgefüllt. Die Grösse des Arrays ist immer 4.

z.B

vor Funktion:
a[0] = 0x04
a[1] = 0x08
a[2] = 0x02
a[3] = 0x08

a[0] = 0x04
a[1] = 0x08
a[2] = 0x02
a[3] = 0x00

Aber irgendwie stehe ich auf dem Schlauch. Ich hoffe sehr auf eure 
Hilfe.

Autor: Michael J. (jogibaer)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

ohne groß nachzudenken würde ich das so machen.

Einfach mit dem ersten Wert beginnen, und diesen dann mit allen 
nachfolgenden
Positionen vergleichen.Wenn doppelt umkopieren.
Dann den nächsten Eintrag u.s.w..

Ich denke mal, die Vorgehensweise ist auch davon abhänig, wie schnell 
das erfolgen soll.

Muß die Reihenfolge der "nicht doppelten" erhalten bleiben ?

Jogibär

Autor: Kai (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo,

die Reihenfolge ist egal.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
OK. So eine Funktion ist ja nicht weiter schwer.
Wie sieht dein Versuch aus?

Hinweis: Mal dir die Situation doch mal auf einem Blatt
Papier auf und spiel mal in Gedanken durch, was alles zu
passieren hat.

Hinweis2: Eine Hilfsfunktion, die in einem Array ab einem
bestimmten Index alle Elemente um eine Position nach vorne
kopiert, wird sich als nützliches Werkzeug erweisen. Ich
würde mal mit dieser Hilfsfunktion anfangen.

Autor: Michael Wilhelm (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
for (i=0;i<max_array_laenge;i++)
{
  for (j=i;j<=max_array_laene,j++)
  {
    if (array[i] == array[j])
    {
       array[j] = 0;
    }
  }
}

wie wäre es damit? ungetestet

MW

Autor: Falk Brunner (falk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
@ Kai (Gast)

>ich versuche eine Funktion zu schreiben, der ich ein Array übergeben
>kann und diese mir dann das Array sortiert. Es soll dabei nach doppelten
>Einträgen gesucht werden. Es handelt sich um ein Byte Array. Wird ein
>doppelter Eintrag gefunden so wird dieser gelöscht und der Rest des
>Arrays soll um einen Platz weiter rutschen. Der Rest wird mit Nullen
>aufgefüllt. Die Grösse des Arrays ist immer 4.

Sowas ist zufällig auch hier drin.

Soft-PWM

MFG
Falk

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Michael Wilhelm wrote:
>
> for (i=0;i<max_array_laenge;i++)
> {
>   for (j=i;j<=max_array_laene,j++)
>   {
>     if (array[i] == array[j])
>     {
>        array[j] = 0;
>     }
>   }
> }
> 
>
> wie wäre es damit?

Äh, nein.
Erfüllt nicht die Anforderungen.

(nicht ernst gemeint)
Man könnte hinten nach noch einen Sortier Lauf machen, der
die ganzen 0-en noch ans Ende des Arrays sortiert, dann würde
es stimmen

Autor: Michael Wilhelm (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stimmt, das Array wurde zwar von redundanten Daten befreit, aber nicht 
zusammengeschoben.

MW

Autor: Stefan L. (piwinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nur so eine Idee :
Wäre das mit Zeigern nicht besser ?
Das würde zumindest hinterher das sortieren sparen ;)

Nicht getestet und natürlich ohne Garantie.

ptr1 = &a[0];
ptr2 = &a[3];

for( ;ptr1 < ptr2; ptr1++)
{
  ptr3 = ptr1;
  for( ;ptr3 < ptr2; ptr3++)
  {
    if(*ptr3 == *ptr2)
    {
      *ptr2=0;
      ptr2--;
    }
  }
}

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stefan Lücke wrote:
> Nur so eine Idee :
> Wäre das mit Zeigern nicht besser ?

Nein.

> ptr1 = &a[0];
> ptr2 = &a[3];
>
> for( ;ptr1 < ptr2; ptr1++)
> {
>   ptr3 = ptr1;
>   for( ;ptr3 < ptr2; ptr3++)
>   {
>     if(*ptr3 == *ptr2)
>     {
>       *ptr2=0;
>       ptr2--;
>     }
>   }
> }

In deinem Code kommt immer noch keine Stelle vor, die das
Zusammenschieben der Elemente bewirkt.

Malt euch das Teil auf und probiert es am Papier durch!
Das ist wirklich nicht schwer.

Autor: Stefan L. (piwinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Man brauch es ja auch nicht zusammenschieben, wenn man durch :

>     if(*ptr3 == *ptr2)
>     {
>       *ptr2=0;
>       ptr2--;
>     }

immer den letzten Arrayeintrag auf 0 setzt und den Pointer, der auf 
diesen zeigt nach vorne schiebt.

[4][8][2][8]
 ^        ^
 |        |
 |        |
 ptr1    ptr2

---

[4][8][2][0]
       ^
       |
       |
      ptr2

Ich hoffe jemand versteht mich ;)

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Stefan Lücke wrote:
> Man brauch es ja auch nicht zusammenschieben, wenn man durch :
>

> immer den letzten Arrayeintrag auf 0 setzt und den Pointer, der auf
> diesen zeigt nach vorne schiebt.
>
> [4][8][2][8]
>  ^        ^
>  |        |
>  |        |
>  ptr1    ptr2
>
> ---
>
> [4][8][2][0]
>        ^
>        |
>        |
>       ptr2
>

Und jetzt machst du das ganze mal mit dem Array

  [8][4][8][2]

Autor: Stefan L. (piwinger)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, hast gewonnen ;)
Muss ich wohl doch nochmal überdenken.

War ja nicht böse gemeint, sondern lediglich eine Idee.

Edit:

Aber würde er hier

> for (i=0;i<max_array_laenge;i++)
> {
>   for (j=i;j<=max_array_laene,j++)
>   {
>     if (array[i] == array[j])
>     {
>        array[j] = 0;
>     }
>   }
> }
>

nicht alles mit 0en überschreiben ?

Weil Beispielsweise beim ersten durchlauf i=j=0 wäre
und er somit das array[i=0] mit dem array[j=0] vergleichen würde und 
dieses dann auf 0 setzt ?

Autor: Arc Net (arc)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
if (a[0] == a[1]) {
   a[1] = 0;
}
if (a[0] == a[2]) {
   a[2] = 0;
}
if (a[0] == a[3]) {
   a[3] = 0;
}

// überflüssig
if (a[1] == a[0]) {
   a[0] = 0;
}
if (a[1] == a[2]) {
   a[2] = 0;
}
if (a[1] == a[3]) {
   a[3] = 0;
}

// überflüssig
if (a[2] == a[0]) {
   a[0] = 0;
}
// überflüssig
if (a[2] == a[1]) {
   a[1] = 0;
}
if (a[2] == a[3]) {
   a[3] = 0;
}

// überflüssig
if (a[3] == a[0]) {
   a[0] = 0;
}
// überflüssig
if (a[3] == a[1]) {
   a[1] = 0;
}
// überflüssig
if (a[3] == a[2]) {
   a[2] = 0;
}

// also 
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] == a[j]) {
           a[j] = 0;
        }
    }
}
// noch genug Speicher? ;-)
int j = 0;
for (int i = 0; i < n; i++) {
    if (a[i] != 0) temp[j++] = a[i];
}
// fehlt nur noch den Rest von temp zu nullen und umzukopieren
// Laufzeit ist mit (n^2 - n)/2 + n denkbar schlecht

Bei größeren Arrays und passender Schlüssellänge empfiehlt sich
z.B. (In-Place) Radixsort oder Counting Sort mit anschließendem
umkopieren/zusammenschieben des Arrays

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.