qsort problems... help!

This is a discussion on qsort problems... help! within the C Programming forums, part of the General Programming Boards category; Hi im new to this board but ive heard great things about it, and hopefully someone can help me out ...

  1. #1
    Registered User
    Join Date
    Jun 2003
    Posts
    5

    qsort problems... help!

    Hi im new to this board but ive heard great things about it, and hopefully someone can help me out here:

    Im trying to use the built in c function qsort to sort my table of characters and their frequencies (writting the Huffman's Algorithm) . But for some reason my code core dumps inside my compare function. I debugged it and it says the value of a is a null pointer. Here's my struct, tablecount for how many elements, and the freqTable:

    typedef struct tableItem {
    char myChar;
    int freq;
    } tableItem;

    static int tableCount = 0;

    tableItem** freqTable;


    Here is my compare function:

    int compareT(const void *a,const void *b)
    {
    tableItem * const *first = a;
    tableItem * const *second = b;

    int retVal;

    retVal = (*second)->freq - (*first)->freq;
    return retVal;
    }

    And here is how i am calling qsort:
    ...
    void* tblptr = freqTable;
    ...

    qsort(tblptr, tableCount-1, sizeof(tableItem*), compareT);

    ...


    I print out all the items, qsort it, then print out again, and here is as far as my output goes:

    [a:3]
    [b:1]
    [c:2]
    [f:3]
    [z:1]
    [u:2]
    [r:6]
    [e:1]
    -------------
    Segmentation fault (core dumped)


    I debugged and it tells me i am seg faulting inside compareT at line:

    retVal = (*second)->freq - (*first)->freq;

    Any help will be appreciated.. thanks!

  2. #2
    Registered User
    Join Date
    Jun 2003
    Posts
    5
    Ok.. here's the whole program:
    (I know my checks for NULL after malloc and realloc are screwy, but i dont think that would be the cause of the problem.)
    Code:
    #include <stdlib.h>
    #include <stdio.h>
    
    typedef struct tableItem {
      char myChar;
      int freq;
    } tableItem;
    
    static int tableCount = 0;
    
    tableItem** freqTable;
    
    
    /*returns index in freqTable of either next open spot or where current character is */
    
    int findInTable(char toFind)
    {
      int index = 0;
    
      while(index < tableCount && freqTable[index] != NULL)
        {
          if(freqTable[index]->myChar == toFind)
            break;
          else
            index++;
        }
      return index;
    }
    
    
    /*adds character to table by getting index from findInTable*/ 
    void addToTable(char toAdd)
    {
    
      int where = 0;
      void* temp;
    
      where = findInTable(toAdd);
    
      if((temp = realloc(freqTable, tableCount*sizeof(tableItem*) + sizeof(tableItem*))) == NULL)
        {
          free(freqTable);
          printf("screw it");
          exit(1);
        }
      freqTable = temp;
      if(freqTable[where] == NULL)
        {
          if((temp = malloc(sizeof(tableItem))) == NULL)
            {
              free(freqTable);
              printf("screw it");
              exit(1);
            }
          freqTable[where] = temp;
          freqTable[where]->myChar = toAdd;
          freqTable[where]->freq = 1;
          tableCount++;
        }
      else
        {
          freqTable[where]->freq++;
        }
    }
    
    
    
    void printTable()
    {
      int index = 0;
      tableItem* temp;
    
      while(index < tableCount && freqTable[index] != NULL)
        {
          temp = freqTable[index];
          printf("[%c:%d]\n", temp->myChar, temp->freq);
          index++;
        }
    }
    
    
    
    /* ok i commented out that part and just made it one line of code, it works but qsort is switching all the wrong things, doesn't sort it.  Ill put the output at the bottom */
    
    int compareT(const void *a,const void *b)
    {
      /*tableItem * const *first = a;
      tableItem * const *second = b;
    
      int retVal;
    
      retVal = *(*second).freq - *(*first).freq;
    
      return retVal;*/
    
      return ((*(tableItem*)a).freq - (*(tableItem*)b).freq);
    }
    
    
    int
    main(int argc, char **argv)
    {
    
      addToTable('a');
      addToTable('b');
      addToTable('c');
      addToTable('f');
      addToTable('c');
      addToTable('a');
      addToTable('f');
      addToTable('a');
      addToTable('f');
      addToTable('z');
      addToTable('u');
      addToTable('u');
      addToTable('r');
      addToTable('e');
    
      addToTable('r');
      addToTable('r');
      addToTable('r');
      addToTable('r');
      addToTable('r');
    
      printTable();
      printf("-------------\n");
    
      qsort((void *)freqTable, tableCount-1, sizeof(freqTable[0]), compareT);
    
      printTable();
    
     return 0;
    }
    Ok now the program doesn't core dump, but it doesn't sort either, here is my output:

    [a:3]
    [b:1]
    [c:2]
    [f:3]
    [z:1]
    [u:2]
    [r:6]
    [e:1]
    ------------- /*sort occurs here */
    [c:2]
    [b:1]
    [a:3]
    [z:1]
    [r:6]
    [u:2]
    [f:3]
    [e:1]

    thanks for any help!!

  3. #3
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    ((*(tableItem**)a)->freq - (*(tableItem**)b)->freq);
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  4. #4
    Registered User
    Join Date
    Jun 2003
    Posts
    5
    If i do that, then i get this error at compilation:

    hw6.c:205: invalid type argument of `->'
    hw6.c:205: invalid type argument of `->'
    hw6.c:207: warning: control reaches end of non-void function

  5. #5
    Registered User
    Join Date
    Jun 2003
    Posts
    5
    Also im compiling with these options:

    gcc -ansi -pedantic -Wall -O2



    if that helps.. thanks for any replies

  6. #6
    Registered User
    Join Date
    Jun 2003
    Posts
    5

    Thumbs up

    Thank you so much!!! Works perfectly! I like the way you did it much much better Thanks again

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. No clue how to make a code to solve problems!
    By ctnzn in forum C Programming
    Replies: 8
    Last Post: 10-16-2008, 03:59 AM
  2. Problems with qsort
    By samus250 in forum C Programming
    Replies: 8
    Last Post: 04-28-2008, 05:41 PM
  3. An interesting problem of qsort()
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 03-05-2008, 12:09 PM
  4. Throw away members in qsort
    By xxxrugby in forum C Programming
    Replies: 4
    Last Post: 04-24-2005, 07:08 AM
  5. C++ link error with qsort
    By bvnorth in forum C++ Programming
    Replies: 7
    Last Post: 10-24-2003, 03:22 AM

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