qsort problem

This is a discussion on qsort problem within the C Programming forums, part of the General Programming Boards category; Can someone tell me what am I doing wrong here? Thanks. Code: #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXINPUT ...

  1. #1
    Registered User
    Join Date
    Jan 2005
    Posts
    204

    qsort problem

    Can someone tell me what am I doing wrong here? Thanks.
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXINPUT 80
    #define MAXLINES 200
    
    int compare(const void *name1, const void *name2)
    {
        return strcmp((char *)name1, (char *)name2);
    }
    
    int main(void)
    {
        FILE *fp;
        char *p;
        char input[MAXINPUT];
        char *lineptr[MAXLINES];
        int i;
        int nlines = 0;
    
        printf("Name of file with names to sort: ");
        fgets(input, MAXINPUT, stdin);
    
        if ((p = strchr(input, '\n')) != NULL)
            *p = '\0';
    
        fp = fopen(input, "r");
        if (fp == NULL) {
            printf("%s could not be found...", input);
            getchar();
            return 1;
        }
    
        while ((fgets(input, MAXINPUT, fp)) != NULL) {
            p = (char *)malloc(1 * sizeof(input));
            strcpy(p, input);
            lineptr[nlines++] = p;
        }
    
        fclose(fp);
    
        qsort((void *)lineptr, nlines, sizeof(lineptr) / sizeof(lineptr[0]), compare);
    
        fp = fopen("names.txt", "w");
        if (fp == NULL) {
            printf("names.txt could not be created...");
            getchar();
            return 1;
        }
    
        for (i = 0; i < nlines; i++)
            fprintf(fp, "%s", lineptr[i]);
    
        fclose(fp);
    
        return 0;
    }

  2. #2
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    I omitted some user input:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXINPUT 80
    #define MAXLINES 200
    
    int compare(const void *name1, const void *name2)
    {
       char *const *x = name1;
       char *const *y = name2;
       return strcmp(*x, *y);
    }
    
    int main(void)
    {
       FILE *fp;
       char *p;
       char input[MAXINPUT] = "file.txt";
       char *lineptr[MAXLINES];
       int i;
       int nlines = 0;
    
       fp = fopen(input, "r");
       if ( fp )
       {
          while ( fgets(input, MAXINPUT, fp) != NULL )
          {
             p = malloc(strlen(input) + 1);
             if ( p )
             {
                strcpy(p, input);
                lineptr[nlines++] = p;
             }
          }
          fclose(fp);
          qsort(lineptr, nlines, sizeof *lineptr, compare);
          fp = fopen("names.txt", "w");
          if ( fp )
          {
             for ( i = 0; i < nlines; i++ )
                fprintf(fp, "%s", lineptr[i]);
             fclose(fp);
          }
       }
       return 0;
    }
    Quote Originally Posted by file.txt
    baker
    foxtrot
    xray
    gamma
    able
    charlie
    Quote Originally Posted by names.txt
    able
    baker
    charlie
    foxtrot
    gamma
    xray
    It would also be prudent to free the memory that was allocated.
    Last edited by Dave_Sinkula; 08-17-2005 at 11:34 PM. Reason: Added output.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Thanks, Dave. Here's what my code looks like now:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    #define MAXINPUT 80
    #define MAXLINES 200
    
    int compare(const void *name1, const void *name2)
    {
        char *const *x = (char * const *)name1;
        char *const *y = (char * const *)name2;
    
        return strcmp(*x, *y);
    }
    
    int main(void)
    {
        FILE *fp;
        char *p;
        char input[MAXINPUT];
        char *lineptr[MAXLINES];
        int i;
        int nlines = 0;
    
        printf("Name of file with names to sort: ");
        fgets(input, MAXINPUT, stdin);
    
        if ((p = strchr(input, '\n')) != NULL)
            *p = '\0';
    
        fp = fopen(input, "r");
        if (fp) {
            while ((fgets(input, MAXINPUT, fp)) != NULL) {
                p = (char *)malloc(strlen(input) + 1);
                strcpy(p, input);
                lineptr[nlines++] = p;
            }
    
            fclose(fp);
        }
    
        qsort((void *)lineptr, nlines, sizeof(*lineptr), compare);
    
        fp = fopen("names.txt", "w");
        if (fp) {
            for (i = 0; i < nlines; i++)
                fprintf(fp, "%s", lineptr[i]);
    
            fclose(fp);
        }
    
        for (i = 0; i < nlines; i++)
            free(lineptr[i]);
    
        return 0;
    }
    I hope I'm freeing the memory that was allocated correctly. I have a couple of questions for you or anyone else willing to answer them:

    1- Why do I need to declare local variables in the compare function and why do they have to be of that specific type?

    2- Why, when allocating memory with malloc, did you add one to the size returned by strlen?

    3- Why didn't you use parentheses with sizeof?

    Thanks

  4. #4
    the hat of redundancy hat nvoigt's Avatar
    Join Date
    Aug 2001
    Location
    Hannover, Germany
    Posts
    3,139
    1) You are sorting an array of character pointers. The qsort function will call your compare function with the address of two of it's elements. So the parameter you get in the compare function is in fact a char** ( pointer to a pointer to character ) wrapped into a void*. Your function wants to compare the elements, so you have to get the element from the address by using the * operator on the ( pointer to pointer to character ) that you got.

    Only you know what type each element is, so you have to cast the void pointers you get to a pointer to your element. Then you need to get the value this pointers point to and compare them.

    2) A string is an array of characters terminated by a trailing zero character. The strlen function returns the number of characters up to the zero character, so if you need to reserve memory, you need to allocate one character more for the trailing zero.
    hth
    -nv

    She was so Blonde, she spent 20 minutes looking at the orange juice can because it said "Concentrate."

    When in doubt, read the FAQ.
    Then ask a smart question.

  5. #5
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    Since he is assigning to an object his casts are not necesary. It looks like he's trying to compile C on a C++ compiler. He should stop this at once.

  6. #6
    Supermassive black hole cboard_member's Avatar
    Join Date
    Jul 2005
    Posts
    1,709
    http://www.eternallyconfuzzled.com/tuts/sorting.html - A great tutorial courtesy of Prelude
    Good class architecture is not like a Swiss Army Knife; it should be more like a well balanced throwing knife.

    - Mike McShaffry

  7. #7
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    I'm glad nvoigt explained of the type already, so I'll just add a couple bits here and there.
    Quote Originally Posted by caduardo21
    Code:
    int compare(const void *name1, const void *name2)
    {
        char *const *x = (char * const *)name1;
        char *const *y = (char * const *)name2;
    
        return strcmp(*x, *y);
    }
    1- Why do I need to declare local variables in the compare function and why do they have to be of that specific type?
    You don't need to declare local variables, I just find the syntax easier. Also I do it to help avoid casting that may be erroneous and that hides any of the compiler's diagnostic messages. And as noted, in C the cast is not necessary in each assignment. But if you were to do this without the locals, you would need the casts.
    Code:
    int compare(const void *name1, const void *name2)
    {
       return strcmp(*(char *const *)name1, *(char *const *)name2);
    }
    Note that I also choose not to cast away constness.

    Quote Originally Posted by caduardo21
    2- Why, when allocating memory with malloc, did you add one to the size returned by strlen?
    As already explained, it's to make room for the null terminator.

    Quote Originally Posted by caduardo21
    3- Why didn't you use parentheses with sizeof?
    The parentheses are necessary only for types; they are optional for objects. I choose not to use them with objects.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    204
    Why do you cast it to (char *const *) and not (const * char *) if the parameter for the compare function is const void?

  9. #9
    Registered User
    Join Date
    Nov 2002
    Posts
    491
    becuse const * char * is not a valid type.

  10. #10
    Just Lurking Dave_Sinkula's Avatar
    Join Date
    Oct 2002
    Posts
    5,006
    Quote Originally Posted by caduardo21
    Why do you cast it to (char *const *) and not (const * char *) if the parameter for the compare function is const void?
    Quote Originally Posted by orbitz
    becuse const * char * is not a valid type.
    Well there's that.
    Code:
    int compare(const void *name1, const void *name2)
    {
        return strcmp(*(char * const *)name1, *(char * const *)name2);
    }
    The thing being compared is passed via a pointer to const. This thing is a char*. Since it is a pointer to a pointer, and you want to compare what the pointer is pointing to (the string), you need to dereference it back to a pointer (to the string).

    [I hope that was a correct explanation for my fellow pedants.]
    Last edited by Dave_Sinkula; 08-18-2005 at 09:58 PM.
    7. It is easier to write an incorrect program than understand a correct one.
    40. There are two ways to write error-free programs; only the third one works.*

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  2. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  3. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM
  4. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  5. Replies: 5
    Last Post: 11-07-2005, 11:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21