C sortowanie słów alfabetycznie

Odpowiedz Nowy wątek
2011-09-02 15:14
Newb
0

Jestem w trakcie pisania programu do sortowania alfabetycznego słów w języku C, dialekcie C99.

Wstępnie kod wygląda tak:

#define _GNU_SOURCE
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
void usage() {
  fprintf(stderr, "Usage: sortlist source target\n");
  exit(0);
}
 
int compare(const char* a, const char* b) {
 
}
 
int main(int argc, char** argv)
{
  if(argc != 3) usage();
 
  FILE* fp = NULL;
  char* line = NULL;
  size_t len = 0;
  char** words_array = NULL;
  int i = 0;
 
  // read list from file
  if( ( fp = fopen(argv[1], "r") ) == NULL ) {
    fprintf(stderr, "Cannot open source file!\n");
    exit(1);
  }
 
  for(; getline(&line, &len, fp) != -1; ++i) {
    // put word in array
    words_array = realloc(words_array, sizeof(char*) * (i + 1) );
    words_array[i] = strdup(line);
  }
  fclose(fp);
  free(line);
 
  // sort it
  qsort(words_array, i, sizeof(char*), compare);
 
  // display
  for(int j = 0; j < i; ++j) printf("Stored data: %s", words_array[j]);
 
  // write to file
 
  // free dynamically allocated memory
  for(int j = 0; j < i; ++j)
    free(words_array[j]);
  free(words_array);
 
  return 0;
}

Myślę o użyciu funkcji z biblioteki standardowej o prototype:

void qsort(void *base, size_t nmemb, size_t size,
                  int(*compar)(const void *, const void *));

Kompilator wyrzuca mi warning:

main.c:43:3: warning: passing argument 4 of ‘qsort’ from incompatible pointer type [enabled by default]
/usr/include/stdlib.h:761:13: note: expected ‘__compar_fn_t’ but argument is of type ‘int (*)(const char *, const char *)’
  1. Czy można zrobić to za pomocą funkcji qsort?
  2. Za bardzo nie wiem jak się za to zabrać, będę wdzięczny za wskazówkę - jak mniej więcej powinna wyglądać funkcja porównująca.

Wydaje mi się, że możnaby tu wykorzystać właśności kodów ASCII czy jest jakiś prosty i sprawdzony sposób.

Pozdrawiam,

Pozostało 580 znaków

2011-09-02 15:27
0

http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/

Zobacz jaką postać ma funkcja porównująca. Musisz sobie rzutować odpowiednio.


"(...) otherwise, the behavior is undefined".

Pozostało 580 znaków

2011-09-02 17:17
Newb
0

wziĄłem domyślny argument funkcji tzn.

int comparator ( const void * elem1, const void * elem2 );

i teraz nie mam warninga. Zrzutuje w trakcie działania funkcji.

Teraz chciałbym wrócić do tematu tzn. do posortowania tablicy.

"The return value of this function should represent whether elem1 is considered less than, equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value."

W tej chwili zastanawiam się nad rozwiązaniem porównywania słów. I chwila przerwy.

Aktualny kod:

#define _GNU_SOURCE
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
void usage() {
  fprintf(stderr, "Usage: sortlist source target\n");
  exit(0);
}
 
int comparator ( const void * elem1, const void * elem2 )
{
  const char* p1 = elem1;
  const char* p2 = elem2;
 
  if(strcmp(p1, p2) == 0)
    return 0;
 
}
 
int main(int argc, char** argv)
{
  if(argc != 3) usage();
 
  FILE* fp = NULL;
  char* line = NULL;
  size_t len = 0;
  char** words_array = NULL;
  int i = 0; // number of elements
 
  // read list from file
  if( ( fp = fopen(argv[1], "r") ) == NULL ) {
    fprintf(stderr, "Cannot open source file!\n");
    exit(1);
  }
 
  for(; getline(&line, &len, fp) != -1; ++i) {
    // put word in array
    words_array = realloc(words_array, sizeof(char*) * (i + 1) );
    words_array[i] = strdup(line);
  }
  fclose(fp);
  free(line);
 
  // display
  for(int j = 0; j < i; ++j) printf("Stored data: %s", words_array[j]);
 
  // sort it
  qsort(words_array, i, sizeof(char*), comparator);
 
  // free dynamically allocated memory
  for(int j = 0; j < i; ++j)
    free(words_array[j]);
  free(words_array);
 
  return 0;
}

Pozostało 580 znaków

2011-09-02 17:28
Rev
0

Zwróć po prostu wynik funkcji strcmp, nie cuduj.


Samo rzutowanie strcmp powinno wystarczyć, choć w C już dawno nic nie robiłem. - Zjarek 2011-09-02 21:28
Nie wystarczy. - Rev 2011-09-02 21:28
Prawda, qsort potrzebuje funkcji pobierającej (przez void*) wskaźniki do sortowanych typów, w tym wypadku const char **) Ale z tego wynika też błąd w kodzie post wyżej. - Zjarek 2011-09-02 21:43

Pozostało 580 znaków

2011-09-02 23:36
Newb
0

Nie rozumiem, gdzie zrobiłem błąd.

Aktualny kod:

#define _GNU_SOURCE
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
 
void usage() {
  fprintf(stderr, "Usage: sortlist source target\n");
  exit(0);
}
 
int comparator ( const void * elem1, const void * elem2 )
{
  return strcmp( (char*) elem1, (char*) elem2);
}
 
int main(int argc, char** argv)
{
  if(argc != 3) usage();
 
  FILE* fp = NULL;
  char* line = NULL;
  size_t len = 0;
  char** words_array = NULL;
  int i = 0; // number of elements
 
  // read list from file
  if( ( fp = fopen(argv[1], "r") ) == NULL ) {
    fprintf(stderr, "Cannot open source file %s!\n", argv[1]);
    exit(1);
  }
 
  for(; getline(&line, &len, fp) != -1; ++i) {
    // put word in array
    words_array = realloc(words_array, sizeof(char*) * (i + 1) );
    words_array[i] = strdup(line);
  }
  fclose(fp);
  free(line);
 
  // sort it
  qsort(words_array, i, sizeof(char*), comparator);
 
  if( ( fp = fopen(argv[2], "a+") ) == NULL ) {
    fprintf(stderr, "Cannot open source file %s!\n", argv[2]);
    exit(1);
  }
 
  // write to file and free dynamically allocated memory
  for(int j = 0; j < i; ++j) {
    fprintf(fp, "%s", words_array[j]);
    free(words_array[j]);
  }
  free(words_array);
  fclose(fp);
 
  return 0;
}

Funkcja zwraca liczbę mniejszą od zera, gdy s1 < s2, 0 gdy s1 jest taki sam jak s2 oraz liczbę większą od zera gdy s1 > s2.

Raczej tym nie posortuje alfabetycznie, tylko spodziewam się otrzymać posortowany od najkrótszego do najdłuższego. A patrząc po danych mam coś innego. Czyli raczej muszę pisać własną funkcję?

Dla danych wejściowych:

mrowka
jablko
analfabeta
zwierz
koperta
maslo
krowa
as
marta
alojzy
zdzichu
bekon

otrzymałem:

krowa
jablko
alojzy
analfabeta
zdzichu
as
koperta
marta
bekon
zwierz
maslo
mrowka

To nie sortuje alfabetycznie.

Pozostało 580 znaków

2011-09-03 00:02
Rev
0

Bo próbujesz porównywać wskaźniki traktując je jako napisy. Funkcja porównująca w argumentach otrzyma wskaźnik do porównywanych wartości, czyli.. wskaźników.

return strcmp( *(char**) elem1, *(char**) elem2);

Pozostało 580 znaków

2011-09-03 00:38
Newb
0

Już rozumiem swój błąd, dzięki.

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0