Zweidimensionales Array (Strings) sortieren

_--

wenn du alles in einer sortierfunktion verwurstest, wirds leider auch nicht schneller

In einer Sortierfunktion möchte ich das ja gar nicht verwursten, aber
das Ding ist: ich kann nicht einfach die Anzahl der Spalten auf <= 15
beschränken und 15 Funktionen implementieren (naja, können schon, aber
das ist aufgrund von einzuhalten Vorgaben nicht gegeben).

Wutz

Was du anscheinend brauchst, ist eine parametrisierbare Vergleichsfunktion, dass leistet die Standardbibliothek mit qsort (ohne häßliche Hacks) nicht, es gibt aber ausreichend Alternativen mit ANSI C, z.B. libavl von Ben Pfaff (GNU-Lizenz), dort ist z.B. solche eine Parametrisierbarkeit enthalten (im Gegensatz zu qsort):

int rb_comparison_func (const void *rb_a, const void *rb_b ,void *rb_param);

_--

nimm doch einfach ne db z.b. sqlite, oder ist das auf euerem vorgabenzettel unter verboten gelistet

@ _-- ich muss das schon programmieren, sei es mit Hilfe eines qsort() oder ähnlichem.

Man kann doch sicherlich den Quicksort-Algo selber implementieren und auf seine Anforderungen umstellen?

Wutz

Ja, kann man.

also doch verwursten :p

Eine andere Lösung sehe ich momentan nicht.

Ich habe da noch eine andere Frage, wollte dafür keinen neues Thema für erstellen (vorerst). Es geht um zweidimensionale Arrays und zwar das Einfügen von Strings.

Irgendwie hat das zwar hin, aber mir geht dadurch Speicher verloren.

array2D[row][col] = einzufuegenderString;

Das mit der Zuweisung ist glaube ich definitiv falsch. Wenn ich es so versuche:
strcpy(array2D[row][col],einzufuegenderString);
knallt mir das Programm komischerweise weg. Also, wie macht man es richtig? Belehrt mich

scimansix

Am Anfang meintest du ja, die Strings seien dynamisch alloziert, also gehe ich mal davon aus, dass es sich bei array2D um ein zweidimensionales Array handelt, das Pointer vom Typ char * enthält, richtig?

Dann kannst du, zum Beispiel um zwei Strings zu vertauschen, einfach die entsprechenden Pointer neu setzen.

Willst du hingegen einen String im Array ganz ersetzen, solltest du zuerst den Speicher für den alten String mit free() freigeben und anschließend den Pointer neu setzen. Das geht dann mit einer einfachen Zuweisung.

strcpy() schlägt wahrscheinlich deshalb fehl, weil der String, in den du kopieren möchtest, nicht genug Platz für den neuen String bietet. Möchtest du das Problem mit strcpy() lösen, solltest du vorher mit realloc() sicherstellen, dass genug Platz vorhanden ist, um den String zu kopieren.

Das alles gilt aber nur, wenn der Hauptspeicher für die Strings wirklich dynamisch alloziert ist!?

Ja, der Speicher ist dynamisch alloziert.

Das dynamisch allozierte Array (2D) ist praktisch noch "leer". Das heisst, ich habe Speicher reserviert und möchte nun das Array fuellen, indem ich ein String an die gewünschte Position einfuege.

Hier der konkrete Code:

token = strtok(zeile, separator,strlength);

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

values ist hierbei das 2D dynamisch allozierte Array von Strings.
Ich fuelle praktisch erst die Spalten einer Zeile mit Strings und mittels row++ geh ich dann in die nächste Zeile.

Was ist daran nun falsch?

scimansix

Achso, sorry, da hatte ich dich wohl falsch verstanden.

Bei dem Aufruf von malloc() solltest du strlen(token)+1 in Klammern setzen (Punktrechnung vor Strichrechnung). Das ist zwar nicht des Rätsels Lösung, weil sizeof(char) auf den meisten Systemen 1 ist, aber darauf verlassen kann man sich nicht.

strtok() erwartet - wenn mich nicht alles täuscht - nur zwei Parameter, nämlich den zu teilenden String und den Separator.

Achso, ja sollte eigentlich empty_strtok statt strtok heissen, ist eine modifizierte Variante von strtok, die 3 Parameter erwartet, aber das tut soweit nichts zur Sache.

Weiterhin würd ich mich über des Rätsels Lösung sehr freuen!

Ing0 schrieb:

Weiterhin würd ich mich über des Rätsels Lösung sehr freuen!

du hast bereits gute vorschläge erhalten. umsetzen musst sie leider selbst. für nen ratefux ruf bei 9 live an!

scimansix

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.

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

Jetzt zeig endlich mal wie du das Array deklariert hast.

Wutz

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

HighLigerBiMBam

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.

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