Mehrdimensionale, dynamische Arrays

[Dennis S. (eltio)]

Guten Morgen,

ich habe eine kleines Problem bei dem ich nicht weiterkomme. Es geht 
darum eine gewissen Datenmenge (Größe nicht bekannt) zu sortieren. Die 
Daten haben folgende Struktur:

1 -> 0
2 -> 17563
3 -> 3059
4 -> 300
3 -> 127
4 -> 168
3 -> 248
...

Die Zielstruktur soll sein:

1 -> 0,
2 -> 17563, 
3 -> 3059, 127, 248
4 -> 300, 168

Die Beispiele die ich bisher gefunden habe waren für C++ und nicht für 
C. Kann mir jemand einenn Tip geben?`

Gruß

[Udo S. (urschmitt)]

Die Suchworte sind Hashtables, verkettete Listen, dynamische Arrays.

Gibts in C nicht als Standard, muss man selber programmieren, in C# C++ 
oder Java ist sowas schon mit dabei.

[Rene (Gast)]

Mir erschliesst sich nicht ganz, wie die Zielstruktur zustande kommt. 
Entweder bin ich zu blöd oder ein paar nähere Erläuterungen wären gut.

Grüsse,
R.

[Dennis S. (eltio)]

Udo Schmitt schrieb:
> Gibts in C nicht als Standard, muss man selber programmieren
Deswegen frage ich ja. Die Beispiele  die ich gefunden haben bezogen 
sich immer auf C++ mit "new" und "free".

Rene schrieb:
> Mir erschliesst sich nicht ganz, wie die Zielstruktur zustande kommt.
Es geht um eine Clusterung der Daten in ersten Spalte. Nach dem Motto

Durchlaufe alle Zeilen der Daten
   Wenn Wert in erster Spalte nicht vorhanden: lege neues Array an
   wenn vorhanden: hänge den Wert an das bestehende Array an

Ich habe mal folgendes "übersetzt", ist aber nur der erste Schritt. Das 
Problem ist, dass das Programm nach Ausgabe der Zahl abstürzt. Ich nehme 
mal an, dass liegt an dem free in der Schleife?

#include <stdio.h>
#include <stdlib.h>
int main() {
    int FirstDim = 4;
    int SecDim = 5;
    int i, j;

    // 1. Schritt: Dynamische Array von Zeigern anlegen:
    int **p2DimArr = malloc(FirstDim);

    // 2. Schritt: An jeden Zeiger ein Array hängen
    for (i = 0; i < FirstDim ; i++) {
        p2DimArr[i] = malloc(SecDim);
    }

    // mit dem neuen 2-dimensionalen Array arbeiten
    p2DimArr[0][0] = 42;
    //...

    printf("%d", p2DimArr[0][0]);

    // alles wieder löschen
    for (j = 0; j < FirstDim ; j++) {
        free (p2DimArr[j]);
    }
    free(p2DimArr);

return 0;
}

[Rene (Gast)]

    // 1. Schritt: Dynamische Array von Zeigern anlegen:
    int **p2DimArr = malloc(FirstDim);

Das wird so wohl kaum klappen. Du allokierst ein array von 5 Bytes. Ein 
Zeiger wird aber, je nach System, sicher 2 - 4 Bytes brauchen.

Grüsse,
R.

[Dennis S. (eltio)]

Rene schrieb:
> Das wird so wohl kaum klappen. Du allokierst ein array von 5 Bytes. Ein
> Zeiger wird aber, je nach System, sicher 2 - 4 Bytes brauchen.
>
> Grüsse,
> R.

    int **p2DimArr = malloc(FirstDim * sizeof(int));

:-)

[Udo S. (urschmitt)]

Wenn du mit alloc Speicher für Arrays allozieren willst, brauchst du die 
Anzahl der Elemente und die Größe des einzelnen Elements.
Die beiden musst du multiplizieren.
Schau dir sizeof() an.

[Rene (Gast)]

Mach ein sizeof(int*), das ist schöner.

Grüsse,
R.

[Udo S. (urschmitt)]

Dennis S. schrieb:
> sizeof(int)

Falsch, denn in dem Array sind doch keine Ints sondern Zeiger auf ints 
oder?

[Udo S. (urschmitt)]

Rene schrieb:
> Mach ein sizeof(int*), das ist schöner.

Nein richtiger! Es gibt durchaus Systeme auf denen sizeof(int) und 
sizeof(int *) unterschiedliche Größe bringen.
Ich sage mal AS400 :-)

[Dennis S. (eltio)]

Danke schon mal!

[Rene (Gast)]

Das stimmt. Aber ich vermute mal nicht, das er solche Übungen auf einem 
AS400 macht :-).

Grüsse,
R.

[Karl H. (kbuchegg)]

Rene schrieb:
> Das stimmt. Aber ich vermute mal nicht, das er solche Übungen auf einem
> AS400 macht :-).

Ist aber eigentlich ziemlich egal.
Da malloc die zu allokierende Größe in Bytes haben will, lautet die 
einfache Formel für die zu allokierende Größe

     malloc( Anzahl_Elemente * sizeof( Einzelelement ) )

[Karl H. (kbuchegg)]

Wobei.
Wenn du es so machst

int main() {
    int FirstDim = 4;
    int SecDim = 5;
    int i, j;

    // 1. Schritt: Dynamische Array von Zeigern anlegen:
    int **p2DimArr = malloc(FirstDim);

    // 2. Schritt: An jeden Zeiger ein Array hängen
    for (i = 0; i < FirstDim ; i++) {
        p2DimArr[i] = malloc(SecDim);
    }

wozu dann überhaupt dynamisch allokieren :-)

Der Knackpunkt in deinem Programm ist ja, dass sich die Allokierungen im 
Programmlauf vergrößern müssen, wenn neue Daten dazukommen. realloc() 
ist dein Freund.

* Der 'Key' in deinen Daten (also die erste Zahl). Ist die immer 
beginnend bei 1 und aufsteigend? Oder könnte deine Zuordnung zb auch so 
aussehen:

     98  ->  178
      5  ->  234
     23  ->   45
     98  ->  675

mit dem Ergebnis

     98   178, 675
      5   234
     23    45

wenn ja, dann wirst du dir auch die erste Zahl irgendwo merken müssen. 
Momentan tust du das nicht.

Weiters ist die Fragestellung die, ob das Ergebnis dieser letzten Daten 
so aussehen soll wie gepostet, oder ob es nicht eher so aussehen soll

      5   234
     23    45
     98   178, 675

(Also auch noch sortiert nach dem Key. Etwas was sich in deinem 
ursprünglichen Fall, durch die 'Vorsortierung' der Eingangsdaten 
automatisch ergibt, nicht notwendigerweise aber im allgemeinen Fall 
vorhanden ist. Ich ignorier den Fall mal, denn in diesem Fall würde sich 
eine komplett andere Vorgangsweise sowohl algorithmisch als auch Form 
der Datenstruktur aufdrängen)


Da empfehle ich doch glatt für die erste 'Dimension' des 2D-Arrays keine 
einfachen Pointer, sondern eine Struktur

struct SingleData
{
  int   key;
  int*  values;
  int   nrValues;
};

struct DataSet
{
  struct SingleData* content;
  int                contentLen;
}

void InsertPair( struct DataSet* data, int key, int value )
{
   .....
}

int main()
{
  struct DataSet data = { NULL, 0 };

  InsertPair( &data, 98, 178 );
  InsertPair( &data,  5, 234 );
  InsertPair( &data, 23,  45 );
  InsertPair( &data, 98, 675 );

  PrintDataSet( &data );

  FreeDataSet( &data );
}

* und eine Aufteilung in Funktionen wär auch nicht schlecht. Zumindest 
eine Funktion zum Finden eines 'key' in den Daten braucht man praktisch 
immer. Und dann gibt es 2 Fälle:
+ entweder der Key wurde gefunden, dann wird an dessen 'data' ein neues 
Element angehängt und der Wert eingetragen
+ oder es gibt ihn noch nicht, dann wird das DataSet um 1 Eintrag 
erweitert, der key eingetragen und der Wert angehängt.

den letzten Punkt, das Anhängen des Wertes an ein struct DataSet 
erledigt am besten wieder eine Funktion, den dieser Vorgang wird in 
beiden Fällen gebraucht.

Eine ganz brauchbare Strategie ist es, sich erst mal in Form von 
Kommentaren umgangssprachlich klar zu machen, wie denn der ganze Vorgang 
laufen muss ....

void InsertPair( struct DataSet* data, int key, int value )
{
  // gibt es den key schon in den Daten?

  // wenn ja, dann einfach den value an diesen Eintrag anhängen

  // wenn nein, dann einen neuen Eintrag erzeugen, und dort den
  // Wert value anhängen

}

... und erst, nachdem in dieser groben Form das Ganze in Gedanken 
klappt, die Programmfragmente zu den Kommentaren zu ergänzen.

void InsertPair( struct DataSet* data, int key, int value )
{
  // gibt es den key schon in den Daten?
  struct SingleData* existingKey = NULL;
  existingKey = FindKey( data, key );

  // wenn ja, dann einfach den value an diesen Eintrag anhängen
  if( existingKey != NULL )
    AddValue( existingKey, value );

  // wenn nein, dann einen neuen Eintrag erzeugen, und dort den
  // Wert value anhängen
  else {
    // Also: neuen Eintrag erzeugen ...
    data->contentLen++;
    data->content = realloc( data->content, data->contentLen * sizeof( struct SingleData ) );

    // ... Verwaltungsinfo eintragen ...
    existingKey = &data->content[ data->contenLen-1 ];
    existingKey->key = key;
    existingKey->values = NULL;
    existingKey->nrValues = 0;
    

    // ... und zugehörigen Wert anhängen
    AddValue( existingKey, value );
  }
}

Du schreibst jetzt noch die Funktionen

  FindKey()
  AddValue()
  PrintDataSet()
  FreeDataSet()

kümmerst dich noch um Fehlerbehandlung und fertig ist die Laube.

(
und den ganzen Programmblock um den Nein-Zweig solltes du in eine eigene 
Funktion 'AddKey' auslagern ...

  struct SingleData* AddKey( struct DataSet* data, int key )
  {
    ...
  }

... so dass sich die Funktion InsertPair wie folgt abmagert

void InsertPair( struct DataSet* data, int key, int value )
{
  // gibt es den key schon in den Daten?
  struct SingleData* existingKey = NULL;
  existingKey = FindKey( data, key );

  // wenn ja, dann einfach den value an diesen Eintrag anhängen
  if( existingKey != NULL )
    AddValue( existingKey, value );

  // wenn nein, dann einen neuen Eintrag erzeugen, und dort den
  // Wert value anhängen
  else {
    existingKey = AddKey( data, key );
    AddValue( existingKey, value );
  }
}

dann bemerkt man auch, dass AddValue in beiden Fällen jeweils am Ende 
steht und daher zusammengefasst werden kann, wodurch sich InsertPair 
vereinfacht zu

void InsertPair( struct DataSet* data, int key, int value )
{
  // gibt es den key schon in den Daten?
  struct SingleData* existingKey = NULL;
  existingKey = FindKey( data, key );

  // wenn es für diesen key noch keinen Eintrag gibt, dann
  // erzeuge einen neuen dafür.
  if( existingKey == NULL )
    existingKey = AddKey( data, key );

  // und den zugehörigen Wert eintragen
  AddValue( existingKey, value );
}

und das ist ja nun wirklich einfach genug, damit man sich laut 
Augenschein davon überzeugen kann, dass diese 'Logik' grundsätzlich 
(d.h. ohne die Behandlung von Fehlern) richtig ist. Und in dem Fall kann 
man dann auch die Kommentare weglassen, weil meiner Meinung nach der 
Programmtext recht eindeutig beschreibt, was hier passiert. Mit gut 
gewählten Funktions-, Member- und Variablennamen erzählt der Code selber 
die Geschichte, wie er funktioniert und was er eigentlich macht.

void InsertPair( struct DataSet* data, int key, int value )
{
  struct SingleData* existingKey = NULL;

  existingKey = FindKey( data, key );
  if( existingKey == NULL )
    existingKey = AddKey( data, key );

  AddValue( existingKey, value );
}

)


Und du siehst schon:
mit einem 2D-Array hat das Ganze eigentlich nur noch im weitesten Sinne 
irgendwas zu tun. Löse dich von der Vorstellung, dass alles einfach nur 
n-dimensionale Arrays sind. Dieser Gedanke hindert dich mehr als er dir 
nützt. Mach dir statt dessen lieber Gedanken um einen vernünftigen 
Aufbau der Datenstruktur. Ein paar Zeichnungen und Skizzen dazu sind 
viel hilfreicher als nach "C 2D Array" zu googeln und nicht weiter zu 
kommen. Mal dir auf, wie deine Datenorganisation aussehen soll, 
übersetze die Knoten in vernünftige Strukturen, so dass an jedem Knoten 
(und damit in den Strukturen) die jeweils benötigten Member enthalten 
sind und dann kommst du auch weiter. Ihr fangt immer viel zu schnell an 
Code zu schreiben, ohne euch über das was zu tun ist, bzw. den Aufbau 
der Datenstrukturen im klaren zu sein.

[Dennis S. (eltio)]

Karl Heinz Buchegger schrieb:
> Wobei.
> Wenn du es so machst wozu dann überhaupt dynamisch allokieren :-)
Ich esse den Elefanten Stück für Stück... ;-)

> Der Knackpunkt in deinem Programm ist ja, dass sich die Allokierungen im
> Programmlauf vergrößern müssen, wenn neue Daten dazukommen. realloc()
> ist dein Freund.
Richtig. Mein Gedanke war jetzt: baue ich das in irgendeiner Form in 
eine lineare Liste ein oder gibt es die Möglichkeit das "einfacher" zu 
lösen.

> * Der 'Key' in deinen Daten (also die erste Zahl). Ist die immer
> beginnend bei 1 und aufsteigend?
Die originale Datenbasis ist bezüglich der Reihenfolge des "Key" völlig 
frei! Gleiches gilt für die Länge (Anzahl der Zeilen) und Anzahl des 
Auftretens eines bestimmten Key.

> Weiters ist die Fragestellung die, ob das Ergebnis dieser letzten Daten
> so aussehen soll wie gepostet, oder ob es nicht eher so aussehen soll
Das ist prinzipiell egal. Ich muss den Key natürlich wiederfinden 
können..

Aus deinen ausführlichen (danke dafür!) Erläuterungen schließe ich: ich 
werde das Ganze in einer Liste organisieren.

Gruß

[Karl H. (kbuchegg)]

Dennis S. schrieb:

> Ich esse den Elefanten Stück für Stück... ;-)

Wobei du angenommen hast, dass du einen Elefanten vor dir hast. In 
Wirklichkeit hast du es aber mit gar keinem Elefanten zu tun. Daher 
versteifst du dich auf das falsche Besteck.

> Richtig. Mein Gedanke war jetzt: baue ich das in irgendeiner Form in
> eine lineare Liste ein oder gibt es die Möglichkeit das "einfacher" zu
> lösen.

Machs erst mal mit größer werdenden Arrays :-)
Danach kannst du die Einzelteile immer noch gegen richtige verkettete 
lineare Listen austauschen. Mit einer ordentlichen Code-Organisation ist 
das überhaupt kein Problem (zb. verändert das die Funktion InsertPair 
nicht im geringsten). Man kann dann sogar in Schritten vorgehen: erst 
mal die key-values-Knoten auf eine Liste umstellen und dann die values 
selber auf eine Liste umstellen.

Aber bei deinem Kenntnissstand solltest du erst mal gehen lernen, ehe du 
dich zum Marathon anmeldest.

[Dennis S. (eltio)]

Danke für deinen Rat. Aber die Liste habe ich bereits fertig 
programmiert und ausgiebig getestet.. ;-) Ich hatte einfach das Gefühl, 
dass das überdimensioniert ist wenn man mehr oder weniger nur ein paar 
Werte in einer Matrix (das ist es ja im Prinzip) anhängen will.

Gruß

[Rolf M. (rmagnus)]

Rene schrieb:
> Aber ich vermute mal nicht, das er solche Übungen auf einem
> AS400 macht :-).

Dann nehmen wir doch einfach was gebräuchlicheres, wie z.B. einen PC. 
Bei den gängigen 64-Bit-Betriebssystemen ist dort ein Zeiger doppelt so 
groß wie ein int.

[D. I. (Gast)]

def cluster(kvPairs)
  result = {}
  kvPairs.each { |pair| result.has_key?(pair.key) ? result[pair.key] << pair.value : result[pair.key] = [pair.value] }
  return result
end

Ups falsche Sprache :)

[Rene H. (Gast)]

Rolf Magnus schrieb:
> Rene schrieb:
>> Aber ich vermute mal nicht, das er solche Übungen auf einem
>> AS400 macht :-).
>
> Dann nehmen wir doch einfach was gebräuchlicheres, wie z.B. einen PC.
> Bei den gängigen 64-Bit-Betriebssystemen ist dort ein Zeiger doppelt so
> groß wie ein int.

Mann Jungs, was hängt ihr euch jetzt an dem auf. Ihr sucht spezial Fälle 
raus. Selbst heute kompiliert kaum einer mit 64Bit. Sicher nicht jemand 
der solche Fragen stellt.

Ich bin Schweizer und wollte lediglich den diplomatischen Hinweis geben, 
es wäre besser mit (int *).
Man muss da echt kein Fass über "schöner" oder "richtiger" aufmachen. 
Ich entwickle genug lange in C/C++ auf verschiedenen Systemen um Code 
portabel zu erstellen. Das war allerdings nicht die Frage (ich darf auf 
den sehr guten Artikel von Cyberlord hinweisen).

Auch kenne ich den Unterschied zwischen Adressbus und Datenbus und deren 
Breite.

Grüsse,
R.

[Karl H. (kbuchegg)]

Rene H. schrieb:


> Ich bin Schweizer und wollte lediglich den diplomatischen Hinweis geben,
> es wäre besser mit (int *).

Du darfst ruhig an dieser Stelle die Diplomatie beiseite lassen.
Sei T irgendein Datentyp, dann kann man seinen Allerwertesten darauf 
verwetten, dass bei einer Allokierung, die nicht so aussieht 
(sizeof-mässig, mit der Ausnahme von T == char)

   T * pVar = malloc( Anzahl * sizeof( T ) );

etwas im Argen liegt.

Bei ihm ist T gleich int*, also muss der int* auch im sizeof vorkommen. 
Ganz einfache Regel. Da ist Diplomatie fehl am Platze.

[Rene H. (Gast)]

Karl Heinz Buchegger schrieb:
> Rene H. schrieb:
>
>
>> Ich bin Schweizer und wollte lediglich den diplomatischen Hinweis geben,
>> es wäre besser mit (int *).
>
> Du darfst ruhig an dieser Stelle die Diplomatie beiseite lassen.
> Sei T irgendein Datentyp, dann kann man seinen Allerwertesten darauf
> verwetten, dass bei einer Allokierung, die nicht so aussieht
> (sizeof-mässig, mit der Ausnahme von T == char)
>
>    T * pVar = malloc( Anzahl * sizeof( T ) );
>
> etwas im Argen liegt.
>
> Bei ihm ist T gleich int*, also muss der int* auch im sizeof vorkommen.
> Ganz einfache Regel. Da ist Diplomatie fehl am Platze.

<offtopic> Das ist schon klar. Das wird der Grund sein weshalb sich mein 
"lecker Kölsch Mädschen" sich dauernd mit mir zankt. </offtopic>

Ich bin auf 7X24 Realtime Systeme spezialisiert (Unix) und bin mir 
dessen "Kleinigkeiten" sehr wohl bewusst.

Nun gut, ich wollte niemanden vor den Kopf stossen, sondern lediglich 
darauf Hinweisen.

Grüsse,
R.

[Karl H. (kbuchegg)]

Rene H. schrieb:

> Ich bin auf 7X24 Realtime Systeme spezialisiert (Unix) und bin mir
> dessen "Kleinigkeiten" sehr wohl bewusst.

Darum gehts nicht.

> Nun gut, ich wollte niemanden vor den Kopf stossen

darum schon eher.
Das war ein ganz klarer Fehler von Dennis. Mit 'Diplomatie' hast du es 
zu einem Schönheitsfehler gewandelt. Das war es aber nicht. Es war 
schlicht und ergreifend falsch. Das darf man ruhig auch so sagen, 
deswegen ist keiner böse.

[Dennis S. (eltio)]

Karl Heinz Buchegger schrieb:
> Das war ein ganz klarer Fehler von Dennis.
Und ein Vermeidbarer noch dazu, schließlich ist mir die "Regel" mit 
sizeof natürlich bekannt.

> Das darf man ruhig auch so sagen, deswegen ist keiner böse.
Richtig!

Gruß Dennis