doppelte Einträge in Array löschen

[Kai (Gast)]

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.

[Michael J. (jogibaer)]

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

[Kai (Gast)]

Hallo,

die Reihenfolge ist egal.

[Karl H. (kbuchegg)]

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.

[Michael Wilhelm (Gast)]

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

[Falk B. (falk)]

@ 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

[Karl H. (kbuchegg)]

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

[Michael Wilhelm (Gast)]

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

MW

[Stefan L. (piwinger)]

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--;
    }
  }
}

[Karl H. (kbuchegg)]

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.

[Stefan L. (piwinger)]

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

[Karl H. (kbuchegg)]

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]

[Stefan L. (piwinger)]

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 ?

[Arc N. (arc)]

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