4. Zweidimensionales Array (Strings) sortieren

Zweidimensionales Array (Strings) sortieren

  • S

    Ich habe mir ein kleines "Drumherum" geschrieben, da lief der Code einwandfrei. Allerdings habe ich kein dynamisch reserviertes Array benutzt und auch nur eine Zeile betrachtet.

    Es könnte also sein, dass der Fehler in einem ganz anderen Programmteil liegt. Hilfreich wäre es, wenn du mal etwas mehr Code posten könntest, den man dann auch kompilieren und ausführen kann.

    0
  • ?

    Bei mir läuft es auch, nur was mir valgrind dazu sagt, ist sehr verdächtig.
    In der Zeile:

    insert = malloc(strlen(token)+1 * sizeof(char*));

    meldet valgrind: 421 bytes in 48 blocks are definitely lost.

    Ich weiss einfach nicht mehr, woran es liegt. Habe schon soviel ausprobiert, verzweifel langsam. Ich reserviere vorher meinen Speicher für das Array:

    values = malloc(row_cnt * sizeof(char*));

for (i=0;i < row_cnt; i++) {
values[i] = malloc(col_cnt * sizeof(char*));
}

    Das ist eigentlich alles, außer ein paar Ueberpruefungen, und dann das Speichern:

    while (fgets(line,fsize,file) {
   cols = 0;
   token = strtok(zeile, separator);

   while (token) {
      insert = malloc(strlen(token)+1 * sizeof(char));
      strcpy(insert,token);
      values[rows][cols] = insert;
      ++cols;
      token = strtok(NULL, separator);
   }
   ++rows; 
}

    In diesem Bereich haut einfach was nicht hin, zwar läuft das Programm, aber dieses fiese Memory Leak, welches Valgrind meldet, macht mir echt Sorgen. Ich danke auch für die Vorschläge, aber irgendwie klappts nicht. Langsam bin ich soweit und rufe wirklich bei 9live an :p

    0
  • ?

    Jetzt zeig endlich mal wie du das Array deklariert hast.

    0

  • Mal ein Beispiel für ein nutzererweitertes qsort;
    um die Komplexität zu verringern wäre es einfacher, wenn du deine Strings zuvor NICHT separierst sondern die Auflösung in Spalten in der Vergleichfunktion anhand des Gesamtstrings vornimmst, du sparst du dann 1 Dimension bei den Zeigern:

    /* erweitertes (nichtoptimiertes) qsort mit Nutzervorgaben als Parameter void* */
void qsort_p(void *array,size_t anzahl,unsigned groesse, int(*cmp)(const void*,const void*,const void*), const void *p )
{
  unsigned char *links=array,
                *rechts=array+ --anzahl*groesse,
                *mitte=array+ (anzahl>>1)*groesse,
                *beginn = links,
                *ende = rechts;
  do {
    while( links != mitte && (*cmp)(links,mitte,p) < 0 )  links+=groesse;
    while( rechts!= mitte && (*cmp)(rechts,mitte,p) > 0 ) rechts-=groesse;
    if( links < rechts )
    {
      if( (*cmp)(links,rechts,p) )
      {
        unsigned char *temp = malloc(groesse);
        memcpy(temp,links,groesse);
        memcpy(links,rechts,groesse);
        memcpy(rechts,temp,groesse);
        free(temp);
        if( mitte == links )  mitte=rechts;
        else if( mitte == rechts )  mitte=links;
      }
      links+=groesse;
      rechts-=groesse;
    }
  }
  while( links < rechts );
  if( links == rechts )
    if( links != mitte && (*cmp)(links,mitte,p) > 0 )  rechts-=groesse; else links+=groesse;
  if( rechts > beginn )  qsort_p(beginn,(rechts-beginn)/groesse+1,groesse,cmp,p);
  if( ende > links )  qsort_p(beginn,(ende-links)/groesse+1,groesse,cmp,p);
}

int cmp(const void *a,const void *b,const void *p)
{
  char **x=*(char***)a;
  char **y=*(char***)b;
  int spalte = *(int*)p;
  return strcmp( x[spalte],y[spalte] );
}

int main()
{
  char *s[][3] = {{"9","4","3"},{"8","5","2"},{"7","6","1"} };
  char ***a[] = { &s[0], &s[1], &s[2] };
  int i;

  for(i=0;i<3; printf("\n%s,%s,%s", (*(char***)&a[i])[0],(*(char***)&a[i])[1],(*(char***)&a[i])[2] ),++i);
  i=0; qsort_p(a,3,sizeof*a,cmp,&i); /* sortieren nach "Spalte" 0 */
  for(i=0;i<3; printf("\n%s,%s,%s", (*(char***)&a[i])[0],(*(char***)&a[i])[1],(*(char***)&a[i])[2] ),++i);
  i=1; qsort_p(a,3,sizeof*a,cmp,&i); /* sortieren nach "Spalte" 1 */
  for(i=0;i<3; printf("\n%s,%s,%s", (*(char***)&a[i])[0],(*(char***)&a[i])[1],(*(char***)&a[i])[2] ),++i);
  i=2; qsort_p(a,3,sizeof*a,cmp,&i); /* sortieren nach "Spalte" 2 */
  for(i=0;i<3; printf("\n%s,%s,%s", (*(char***)&a[i])[0],(*(char***)&a[i])[1],(*(char***)&a[i])[2] ),++i);
  return 0;
}
    0
  • H

    Der Code von Wutz ist natürlich nur dazu da den TA zu verstören und abzuschrecken... Wie soll er das

    (*(char***)&a[i])[0]
char **x=*(char***)a;

    verstehen, wenn er schon Probleme bei ** hat?

    Siehe Frage zweidimensionales Array String. Ein einfaches Beispiel hätte da sicher genügt.

    0
  • ?

    Jetzt geht der Thread ganz auseinander, sorry für den internen Themenwechsel, ich hätte doch ein neues Thema eröffnen sollen.
    Wie in meinem letzten Post beschrieben, habe ich ein Problem beim Einfuegen in das 2D Array. Das Problem des Quicksorts habe ich nun gelöst, ähnlich dem Code von Wutz.So sehr schreckt mich der Code nun nicht ab.

    Aber nun gut, mein Problem liegt nach wie vor beim Einfuegen (Code im letzten Post) von Strings ganz am Anfang, ohne Sortierung.

    Achja, das Array ist wie folgt deklariert:
    String **values; (wobei Srting ein typedef auf char * ist).

    0
  • ?

    Und woher soll der Compiler bei values[rows][cols] = insert; wissen bis zu welchem Wert cols gehen kann?

    0
  • ?

    Ich habe das Array in einem struct deklariert, dort wird das Array
    mit row_cnt und col_cnt verwaltet. Dies ist Teil eines Listenelements.
    Die ganze Kiste wird dann über eine Liste verwaltet.

    0
  • ?

    Das ganze hängt daran wie der Speicher mit deinem value verarbeitet wird.
    Und du kommst nicht damit heraus wie das ganze zugewiesen wird.

    Einmal machst du

    values = malloc(row_cnt * sizeof(char*));

    dann ist das wieder

    values[rows][cols] = insert;

    Das passt irgendwie nicht zusammen.

    Darum nochmal die Frage:
    Wie ist das Array wirklich deklariert.

    0
  • ?

    So wie ich das aufgefasst habe, wird so Speicher fuer ein 2D Array
    reserviert, sprich erst fuer die char-Zeiger (zeile) und dann in der Schleife
    Speicher für die einzelnen Spalten der Zeilen.

    Das Array ist in diesem Stuct:

    struct Data
{
   String **values; /* String = char* */
   int row_cnt;
   int col_cnt;
};

    Verwaltet wird dieses Struct ueber ein weiteres, welches einem Listenelement meiner verketteten Liste entspricht:

    struct Element 
{
	String id;
	Data data; 
};

    Hier nochmal der Code fuer das Reservieren und Einfuegen:

    Element e; 

e.data.values = malloc(max_row_cnt * sizeof(char*));
/*max_row_cnt wird vorher ermittelt, entspricht später e.data.row_cnt */

for (i=0;i < max_row_cnt; i++) {
   e.data.values[i] = malloc(max_col_cnt * sizeof(char*));
}   
/*max_col_cnt wird ebenfalls vorher ermittelt */

while (fgets(line,fsize,file) {
   e.data.col_cnt = 0;
   token = strtok(zeile, separator);

   while (token) {
      insert = malloc(strlen(token)+1 * sizeof(char));
      strcpy(insert,token);
      e.data.values[e.data.row_cnt][e.data.col_cnt] = insert;
      ++e.data.col_cnt;
      token = strtok(NULL, separator);
   }
   ++e.data.row_cnt;
}

    Das Element e wird dann in die Liste eingefuegt.

    0
  • ?

    Ein 2D-Array ist sowas:

    #define MAX_X 10
#define MAX_Y 20
int x,y;

int feld[MAX_X][MAX_Y];

    Das ergibt einen Block von MAX_X * MAX_Y (also 200) int, der gleich reserviert wird.

    // Du kannst darauf als Feld zugreifen:
feld[x][y] = 5;
// oder als Zeiger;
*(feld+x*MAX_Y+y) = 5; // Beachte das da steht: x * MAX_[b]Y[/b] (und [b]nicht [/b]x * MAX_X)

    Bei dem Zugriff als Feld muss der Compiler aber wissen wie groß das Feld beim höchsten Index ist (Hier der 2. Index MAX_Y)

    Du schreibst:

    String **values; /* String = char* */
...
e.data.values = malloc(max_row_cnt * sizeof(char*));    // geht noch  (String**)
...
e.data.values[i] = malloc(max_col_cnt * sizeof(char*)); // geht auch noch (String*)
...
e.data.values[e.data.row_cnt][e.data.col_cnt] = insert;  // Hier weiß der Compiler doch gar nicht wie groß dein letzter Index ist. :warning:
// Außerdem ist das immer noch ein String* und du wolltest ein einfachen String haben
    0
  • ?

    Ok, langsam leuchtet es mir ein, aber ich kann die Groesse via #define
    nicht festlegen, weil ich zur Complierzeit noch nicht weiss, wie groß das 2D Array wird, sondern erst, wenn ich weiss, wieviele Zeilen + Spalten in der Datei stehen, die ich einlese.

    0
  • ?

    Ich beziehe mich hier auf dieses Beispiel (dort als int):

    http://openbook.galileocomputing.de/c_von_a_bis_z/014_c_dyn_speicherverwaltung_011.htm#mj8c39512a8855f67117c0abd122d4b01e

    0
  • ?

    Nachdem ich einiges über zweidimensionale Arrays gelesen habe, wird mir klar, das man das so wohl nicht machen kann, und ich wirklich die Groesse via define festlegen muss.

    Aber, was wäre, wenn ich sage:

    #define MAX_X 30
    #define MAX_Y 20

    aber, was ich noch nicht wisse, nur 10 Zeilen und 5 Spalten benötige? Ist das so legitim, kann man das so machen?

    0
  • ?

    Du brauchst die #defines nicht. Das war nur ein Beispiel.

    Du kannst auch diese MAX_ auch als Variablen machen

    int max_row, max_col;
int *feld;

int row,col;

  max_row = 20;
  max_col = 10;

  feld = malloc(max_row * max_col * sizeof(int));

  row = 2;
  col=6;

  *(feld r*max_col+c) = 100;

    Die Idee ein Spalten-Array mit Zeigern auf Zeilen-Arrays zu machen ist schon in Ordnung. Nur hast du das nur noch nicht richtig implementiert.

    0
  • H

    Ich würde mich wesentlich besser fühlen, wenn diese dann auch "const" wären. Anstelle von defines versteht sich.

    0
  • ?

    Ok, dann ist meine Datenstruktur vielleicht doch noch zu retten. Ich werd mich mal ransetzen und schauen, ob es es hinkriege.

    0
  • ?

    @DirkB Irgendwie stehe ich gerade auf dem Schlauch. Also dein Beispiel soll ein 2D-Array von int's verdeutlichen? Wie ist denn die letzte Zeile zu interpretieren?

    Weiss jetzt nicht konkret, wie ich das umsetzen soll - wahrscheinlich habe ich heute einfach zu lange daran gesessen und mit den Kopf zerbrochen, Luft ist echt raus 😞

    0
  • ?

    Da muss noch ein + hin (feld+rmax_col+c) = 100;

    Ing0 schrieb:

    ..., Luft ist echt raus 😞

    Geht mir gerade genauso, denn ....
    was ich geschrieben stimmt für Arrays.

    In dem Beispiel aus dem Buch wir ja von einem (Doppel-)Zeiger ausgegangen und da dereferenziert jedes [] wieder. Darum funktioniert das auch.
    Asche auf mein Haupt :p

    0
  • H

    in der letzten Zeile hat er zwei kleine Fehler gemacht (falsche namen). Du musst dir den Array als Folge im Speicher vorstellen.

    x 0 1 2 3 4 5
    0 0 1 2 3 4 5
    1 6 7 8 9 10 11

    Im Speicher sieht das dann aber so aus:

    0 1 2 3 4 5 6 7 8 9 10 11

    Wenn du nun die Zweite Zeile ansprechen willst musst du dementsprechend row * max_col nehmen.

    0 1 2 3 4 5 6 7 8 9 10 11
    ---------------|row * max_col

    Wenn du die Zeile hast, dann muss noch der Offset zur Spalte mit rein.

    0 1 2 3 4 5 6 7 8 9 10 11 ...
    --------------------|row * max_col + col

    Im Beispiel wäre es dann:

    0 1 2 3 4 5 6 7 8 9 10 11 ...
    --------------------|1 * 6 + 2

    Das Ergebnis ist 8.

    const int max_row = 2;
    const int max_col = 6; 
	int *feld; 

	int row, col; 
	int i, y;

	feld = (int*)malloc(max_row * max_col * sizeof(int)); 

	for(i = 0; i < max_row; ++i)
		for(y = 0; y < max_col; ++y)
			*(feld + i * max_col + y) = i * max_col + y; //steigender Wert 0 - 11

	row = 1; // 0 bis max_row - 1
	col = 2; // 0 bis max_col - 1

	printf("%i", *(feld + row * max_col + col));
    0
Anmelden zum Antworten