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.
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
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.
1 | for (i=0;i<max_array_laenge;i++) |
2 | {
|
3 | for (j=i;j<=max_array_laene,j++) |
4 | {
|
5 | if (array[i] == array[j]) |
6 | {
|
7 | array[j] = 0; |
8 | }
|
9 | }
|
10 | }
|
wie wäre es damit? ungetestet MW
@ 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
Michael Wilhelm wrote:
>
1 | > for (i=0;i<max_array_laenge;i++) |
2 | > { |
3 | > for (j=i;j<=max_array_laene,j++) |
4 | > { |
5 | > if (array[i] == array[j]) |
6 | > { |
7 | > array[j] = 0; |
8 | > } |
9 | > } |
10 | > } |
11 | >
|
> > 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
Stimmt, das Array wurde zwar von redundanten Daten befreit, aber nicht zusammengeschoben. MW
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--; } } }
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.
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 ;)
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]
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 ?
1 | if (a[0] == a[1]) { |
2 | a[1] = 0; |
3 | }
|
4 | if (a[0] == a[2]) { |
5 | a[2] = 0; |
6 | }
|
7 | if (a[0] == a[3]) { |
8 | a[3] = 0; |
9 | }
|
10 | |
11 | // überflüssig
|
12 | if (a[1] == a[0]) { |
13 | a[0] = 0; |
14 | }
|
15 | if (a[1] == a[2]) { |
16 | a[2] = 0; |
17 | }
|
18 | if (a[1] == a[3]) { |
19 | a[3] = 0; |
20 | }
|
21 | |
22 | // überflüssig
|
23 | if (a[2] == a[0]) { |
24 | a[0] = 0; |
25 | }
|
26 | // überflüssig
|
27 | if (a[2] == a[1]) { |
28 | a[1] = 0; |
29 | }
|
30 | if (a[2] == a[3]) { |
31 | a[3] = 0; |
32 | }
|
33 | |
34 | // überflüssig
|
35 | if (a[3] == a[0]) { |
36 | a[0] = 0; |
37 | }
|
38 | // überflüssig
|
39 | if (a[3] == a[1]) { |
40 | a[1] = 0; |
41 | }
|
42 | // überflüssig
|
43 | if (a[3] == a[2]) { |
44 | a[2] = 0; |
45 | }
|
46 | |
47 | // also
|
48 | for (int i = 0; i < n - 1; i++) { |
49 | for (int j = i + 1; j < n; j++) { |
50 | if (a[i] == a[j]) { |
51 | a[j] = 0; |
52 | }
|
53 | }
|
54 | }
|
55 | // noch genug Speicher? ;-)
|
56 | int j = 0; |
57 | for (int i = 0; i < n; i++) { |
58 | if (a[i] != 0) temp[j++] = a[i]; |
59 | }
|
60 | // fehlt nur noch den Rest von temp zu nullen und umzukopieren
|
61 | // 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
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
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.