Zweidimensionales Array (Strings) sortieren

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

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?

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.

HighLigerBiMBam

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

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

@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

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

HighLigerBiMBam

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

scimansix

DirkB schrieb:

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

Genau, der Compiler muss nur den größten Index kennen, wenn es sich um ein auf dem Stack abgelegtes, nicht dynamisches Array (z. B. char [][]) handelt. Dort werden die Zeilen nämlich direkt hintereinander abgelegt.

Bei einem dynamisch allozierten Array (char **) handelt es sich um ein Array von Arrays, wo lediglich die Pointer dereferenziert werden müssen, ohne umständlich die Position eines Elementes über die Zeilenlänge zu berechnen.

Die von Ing0 zuerst vorgeschlagene Lösung zur Reservierung des Speichers für das Array war also völlig richtig.

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

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

Also ist das völlig korrekt?

Wie sieht denn dann die korrekte Zuweisung von char * aus, also das Einfügen von Strings?

scimansix

Ja, ist es, bis auf eine Kleinigkeit. Die erste Zeile sollte

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

lauten. Und wie gesagt, bei

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

fehlen noch Klammern und es ist ein Sternchen zu viel, also

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

An der Zuweisung mit

values[rows][cols] = insert;

ist auch nichts auszusetzen, da es sich bei values ja um ein String ** (bzw. char ***) handelt und bei zweifacher Dereferenzierung nur noch char * überbleibt.

Warum Valgrind meckert, kann ich mir allerdings auch nicht erklären.

Ok, ich werd das mal ändern und schauen, ob ich noch was finde.
Vielen Dank euch erstmal für die Tipps & Erklärungen.

Nochmal kurz zu folgenden Zeilen:

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

In Zeile 6 meldet valgrind mir weiterhin eine Meldung, aber nur "665 bytes in 115 blocks are indirectly lost" (vorher war es immer "definitely" statt indirectly). Seltsame Geschichte.

Ich muss doch eigentlich den String insert wieder freigeben? Oder nicht? Wenn ich versuche, den String am Ende der Verarbeitung mittel free() freizugeben, verhält sich das ganze Programm unstablil, dh er würfelt alles durcheinander.

Das Programm verhält sich ansonsten an allen anderen Stellen vollkommen korrekt, Einfügen, Löschen, Anfügen von Daten in das 2D Array läuft tadellos.

Hm, keiner eine Idee?

Zu jedem malloc() gehört doch eigentlich ein free(), oder?

HighLigerBiMBam

Ing0 schrieb:

Hm, keiner eine Idee?

Zu jedem malloc() gehört doch eigentlich ein free(), oder?

Ja. Poste eine komplettes Minimalbeispiel, welches den Fehler reproduziert.

So, hier ein kleines Beispiel, der Fehler tritt auch hier auf.
In Zeile 23 ist der Ursprung, hier meldet valgrind:

==1903== 38 (4 direct, 34 indirect) bytes in 1 blocks are definitely lost in loss record 3 of 3

int main ()
{
	char * token = NULL;
	char * line = NULL;
	char ***values;
	char * insert = NULL;
	int i,j;
	int rows = 1;
	int cols = 4;
	int col_cnt = 0;
	int row_cnt = 0;

	line = malloc(30 * sizeof(char));
	strcpy(line,"Dies,ist,ein,Test");
	values = malloc(rows * sizeof(char**));

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

	token = strtok(line, ",");

	while (token) {

		insert = malloc(strlen(token)+1 * sizeof(char)); /* Hier: Ursprung */
		strcpy(insert,token);
		values[row_cnt][col_cnt] = insert; /* bzw. hier*/
		/* free(insert); --> Alles futsch */ 
		col_cnt++;
		token = strtok(NULL, ",");
	}
	row_cnt++;
	/* free(insert); --> letzter Eintrag ("Test") ist futsch*/
	for(i=0;i<row_cnt;i++){
		for(j=0;j<col_cnt; j++)

		printf("%s,",values[i][j] );
	}
	printf("\n");

	/* Array freigeben */
	for (i = 0; i < row_cnt; i++) {
     		free(values[i]);
	}
	free(values);

	/* free(insert); --> keine Veränderung  */ 
	free(line);
	return 0;
}

Die auskommentierten free's verdeutlichen den Effekt.
(Theorie: Wert des 2D Arrays bekommt Adresse von insert, wenn ich insert freigebe, sind die letzten Datensätze futsch weil ich die Adresse lösche?)
Hm, hab schon einiges probiert, aber immer der selbe Effekt.

scimansix

Solange du die Strings noch verwendest, darfst du deren Speicher natürlich nicht freigeben. Im Array steht nur die Adresse des Speicherbereichs, das ist richtig. Deshalb ist ja auch jedes Element des Arrays vom Typ char *. Nach der Verwendung (in deinem Fall nachdem du die Werte ausgegeben hast) kannst du den Speicher aller Strings freigeben.

Edit: Fügt man folgenden Code nach der for-Schleife, in der die Werte ausgegeben werden, ein, meckert Valgrind nicht mehr:

for (i = 0; i < row_cnt; i++) {
  for (j = 0; j < col_cnt; j++)
    free(values[i][j]);
}

Achja, daran habe ich gar nicht gedacht, jetzt funktionierts endlich.
Ich habe die ganze Zeit an der falschen Stelle geguckt bzw. ich habe
mich zu sehr an dem Beispiel mit int's orientiert.

Danke danke danke danke!