Thread: qsort and array

  1. #1
    Registered User
    Join Date
    Aug 2010
    Posts
    17

    Question qsort and array

    Hi i have an array of structs which i am trying to sort. It contains various strings of words and i wan to put them in alpha order. My code compiles fine but it crashes when i call the qsort. Just wondering if anybody could point me to where i am going wrong

    Code:
    /* Structure definitions. */
    typedef struct wordStruct* WordTypePtr;
    
    typedef struct wordStruct
    {
       char* word;
       unsigned count;
       WordTypePtr nextWord;
    } WordType;
    I am filling the array from a linked list. When i do a printf the strings in in the array
    Code:
    WordType *conductor;
    //array deceleration
    WordType wordArray[index->totalWords];
    //further down
    wordArray[j].word=conductor->word;
    My qsort
    index->totalWords is the count of how big the array is
    Code:
    qsort(*wordArray->word, index->totalWords, sizeof(*wordArray), comp);
    comp function
    Code:
     int comp(const void *s1, const void *s2)
     {
         return (strcmp(*(char **)s1, *(char **)s2));
     }

  2. #2
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Can you post the complete code?

  3. #3
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    The qsort is at 00000159

    Code:
    00000010 #include "index.h"
    00000011 #include "index_options.h"
    00000012 #include "index_utility.h"
    00000013 
    00000014 /****************************************************************************
    ****************************************************************************/
    00000019 void readRestOfLine()
    00000020 {
    00000021    int c;
    00000022 
    00000023    /* Read until the end of the line or end-of-file. */   
    00000024    while ((c = fgetc(stdin)) != '\n' && c != EOF)
    00000025       ;
    00000026 
    00000027    /* Clear the error and end-of-file flags. */
    00000028    clearerr(stdin);
    00000029 }
    00000030 
    00000031 
    00000032 /****************************************************************************
    00000033 * Initialises the index to a safe empty state.
    00000034 ****************************************************************************/
    00000035 void systemInit(IndexType* index)
    00000036 {
    00000037      index->uniqueWords=0;
    00000038 
    00000039 }
    00000040 
    00000041 
    00000042 /****************************************************************************
    00000043 * Loads all data into the index.
    00000044 ****************************************************************************/
    00000045 int loadData(IndexType* index, char* trecFile)
    00000046     {
    00000047     WordType * curr, * head;
    00000048 
    00000049         WordType *root;
    00000050         index->headWord=root;
    00000051         WordType *conductor;
    00000052         
    00000053         root = (WordType *)malloc(sizeof(WordType));
    00000054         root->nextWord=0;
    00000055         root->word=NULL;
    00000056         
    00000057         index->headWord=root;
    00000058         
    00000059         conductor=root;
    00000060         
    00000061          if ( conductor != 0 ) {
    00000062     while ( conductor->nextWord != 0)
    00000063       conductor = conductor->nextWord;
    00000064   }
    00000065 
    00000066         
    00000067     char wordvar[MAX_SIZE];
    00000068     int j=0;
    00000069     int k=0;
    00000070     char c; 
    00000071     int tag=0;
    00000072     FILE *fp;
    00000073     printf("%s\n",trecFile);
    00000074     fp = fopen(trecFile, "r"); 
    00000075     if ( fp == NULL) 
    00000076     {
    00000077         fprintf(stderr, "\nUnable to open file %s\n", trecFile); 
    00000078         system("PAUSE");	
    00000079         return EXIT_SUCCESS;
    00000080         }
    00000081         else
    00000082         {
    00000083         printf("\nFile %s open\n",trecFile);
    00000084         while(( c = getc(fp)) != EOF)
    00000085         {
    00000086          if(c=='<'){
    00000087                     tag=1;
    00000088                     }
    00000089          if (1 !=tag){
    00000090                    if(tolower(c)>96 && tolower(c) <123){
    00000091                                     /*printf("%c",tolower(c));*/
    00000092                                     wordvar[j]=tolower(c);
    00000093                                     j++;
    00000094                                     }
    00000095          
    00000096                  if (c==' '){
    00000097                           wordvar[j+1]='\0';
    00000098                           curr = (WordType *)malloc(sizeof(WordType));
    00000099                           /*curr->count++;*/
    00000100                           curr->word = (char*) malloc ( MAX_SIZE*sizeof( char ) );
    00000101                           if (wordvar[0]>96 && wordvar[0]<123){
    00000102                                          strncpy( curr->word, wordvar, MAX_SIZE-1 );
    00000103                                          index->totalWords++;
    00000104                                          conductor->nextWord = (WordType *)malloc(sizeof(WordType));  
    00000105                                          conductor = conductor->nextWord; 
    00000106                                          conductor->nextWord = 0;        
    00000107                                          conductor->word = strncpy( curr->word, wordvar, MAX_SIZE-1 ); 
    00000108                                          curr->nextWord  = head;
    00000109                                          }
    00000110                              for(j=0;j<=MAX_SIZE-1;j++) {
    00000111                              wordvar[j]=NULL;
    00000112                                                   }
    00000113                           j=0;
    00000114                           }
    00000115                           
    00000116                  }
    00000117                  if(c=='>'){
    00000118                             tag=0;
    00000119                             }
    00000120       }
    00000121 
    00000122    }
    00000123    
    00000124       fclose(fp);/* closes stream fp */
    00000125       /*finalise linked list*/
    00000126       conductor->nextWord = (WordType *)malloc(sizeof(WordType));  
    00000127       conductor = conductor->nextWord; 
    00000128       conductor->nextWord = 0;        
    00000129       conductor->word = NULL;
    00000130       
    00000131 
    00000132       
    00000133       
    00000134       printf("Total Words: %d\n\n",index->totalWords);
    00000135       
    00000136       /*array of words*/
    00000137       WordType wordArray[index->totalWords];
    00000138       for(k=0;k<=index->totalWords-1;k++) {
    00000139                                 wordArray[j].count=0; 
    00000140                                 wordArray[j].word="gdfgdg";
    00000141                                 /*printf("word: %s\n",wordArray[j].word); */        
    00000142                                           }
    00000143                                           
    00000144       conductor=root;
    00000145       conductor = conductor->nextWord;
    00000146       if ( conductor != 0 ) { 
    00000147          while ( conductor->nextWord != 0 ) {
    00000148          printf("%s\n",conductor->word);
    00000149          /*for(k=0;k<=index->totalWords-1;k++) {*/
    00000150                                              
    00000151                                              wordArray[j].word=conductor->word;
    00000152                                              printf("word: %s\n",wordArray[j].word); 
    00000153                                              /*}*/
    00000154 
    00000155          conductor = conductor->nextWord;
    00000156          }
    00000157          printf("%s\n",conductor->word);                
    00000158                                                         }
    00000159          qsort(*wordArray->word, index->totalWords, sizeof(*wordArray), comp);                                                                 
    00000160     
    00000161    
    00000162     return SUCCESS;
    00000163 }
    00000164 
    00000165 
    00000166 /****************************************************************************
    00000167 * Deallocates memory used in the index.
    00000168 ****************************************************************************/
    00000169 void systemFree(IndexType* index)
    00000170 {
    00000171    WordTypePtr current, next;    
    00000172    current = index->headWord; 
    00000173    while (current != NULL) 
    00000174    { 
    00000175       next = current->nextWord;   
    00000176       free(current);    
    00000177       current = next; 
    00000178    } 
    00000179    index->headWord = NULL; 
    00000180    index->totalWords = 0;
    00000181 }
    00000182  int comp(const void *s1, const void *s2)
    00000183  {
    00000184      return (strcmp(*(char **)s1, *(char **)s2));
    00000185  }

  4. #4
    Registered User
    Join Date
    Jun 2010
    Location
    Michigan, USA
    Posts
    143
    Why is the first parameter to qsort( ) *wordArray->word? It should probably be wordArray.

    Edit: Since the string word is what you want to compare on, you are going to have to improve your comp( ) function to compare what is pointed to by word. Your comp( ) will have to do the comparison using the base address of two elements of wordArray (for example, &wordArray[n] and &wordArray[m]). So its declaration should be something like:

    int comp( wordTypePtr w1, wordTypePtr w2 );

    To anyone with variable length array experience, does qsort( ) in a C99 implementation support variable length arrays?
    Last edited by pheininger; 08-13-2010 at 07:21 AM. Reason: Added an Edit about the comp( ) function.

  5. #5
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    VLA or fixed array, that's not problem at all. Since array is decayed to pointer if you passed to function.

  6. #6
    Registered User
    Join Date
    Jun 2010
    Location
    Michigan, USA
    Posts
    143
    Your fundamentatl problem is that qsort( ) is intended to sort an array. You are using an array to store a linked list. qsort( ) is not designed to sort a linked list. You will either have to remove the links (since they will not make sense after sorting), write your own sort function to sort your linked list, or rebuild the links after the qsort( ) is complete.

  7. #7
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    Quote Originally Posted by pheininger View Post
    Your fundamentatl problem is that qsort( ) is intended to sort an array. You are using an array to store a linked list. qsort( ) is not designed to sort a linked list. You will either have to remove the links (since they will not make sense after sorting), write your own sort function to sort your linked list, or rebuild the links after the qsort( ) is complete.
    I suppose thats were i was thinking.

    Take the values from the linked list an out into an array
    qsort array
    create another link list

    I thought that is what i did but guess i have made an array of structs...

  8. #8
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    plan 2 is not working...
    MAX_SIZE 1024

    Code:
    char wordArray1[MAX_SIZE][index->totalWords];
    i have tried various ways to get data in but it crashes.
    Code:
    for(k=0;k<=index->totalWords-1;k++) {
    strncpy(wordArray1[][j],"lkj",3);
    }
    What i want to do is copy the string form my linked list to the array then do the qsort...

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by ollie View Post
    plan 2 is not working...
    MAX_SIZE 1024

    Code:
    char wordArray1[MAX_SIZE][index->totalWords];
    i have tried various ways to get data in but it crashes.
    Code:
    for(k=0;k<=index->totalWords-1;k++) {
    strncpy(wordArray1[][j],"lkj",3);
    }
    What i want to do is copy the string form my linked list to the array then do the qsort...
    Put a number into the second dimension. Looks like you have the columns mixed up with the rows.

    Rows go first (that's the number of total words in your list), then the columns go in the second set of brackets for the wordArray.

    Then it's:
    Code:
    for(i=0;i<NumberOfWords;i++) {
       //code to get to the next Node in the list
      strcpy(wordArray1[i], textFromYourNextNodeInTheList);
    }
    That will require that the words in the list are marked with the proper end of string char, and you should have enough columns in your array to allow for the same, as well.

  10. #10
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    hmmm, i am having slow progress.
    I have made an array of chars but i still find it crashes when i get the qsort... any ideas?

    Code:
          WordType wordArray[index->totalWords];
          char wordArray1[index->totalWords][MAX_SIZE];
          j=0;      
          conductor=root;
          conductor = conductor->nextWord;
          if ( conductor != 0 ) { 
             while ( conductor->nextWord != 0 ) {
             printf("j:%d\n",j);
             printf("%s\n",conductor->word);   
             wordArray[j].word=conductor->word;
             wordArray[j].word=wordArray[j].word+'\0';
             strncpy(wordArray1[j],wordArray[j].word,MAX_SIZE);
             while (chkcar==0){
                  if (wordArray1[j][charcounter]=='\0'){
                     chkcar=1;
                  }else{
                  printf("%c",wordArray1[j][charcounter]);
                  charcounter++;
                  }      
             }    
             printf("\nword: %s\n",wordArray[j].word); 
             j++;
             charcounter=0;
             chkcar=0;
             conductor = conductor->nextWord;
             }
             printf("%s\n",conductor->word);                
                                                            }
             qsort(wordArray1, index->totalWords, sizeof(*wordArray1), comp);

  11. #11
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Why don't you just sort the linked list directly???
    qsort example

  12. #12
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    Quote Originally Posted by Bayint Naung View Post
    Why don't you just sort the linked list directly???
    qsort example
    I will take a look. I did not think it was possible.

  13. #13
    Registered User
    Join Date
    Aug 2010
    Posts
    17
    Now i am really confused. That examples is for an array of structs not a linked list?

  14. #14
    Registered User
    Join Date
    May 2010
    Location
    Naypyidaw
    Posts
    1,314
    Yes.
    You can try insertion sort for linked list Example Linked List Problems
    Last edited by Bayint Naung; 08-14-2010 at 06:26 AM.

  15. #15
    Registered User
    Join Date
    Aug 2010
    Location
    England
    Posts
    90
    You just need a temporary struct pointer, called say swappointer

    if test a to b is true
    then
    swappointer equals struct pointer a
    struct pointer a equals struct pointer b
    struct pointer b equals swap

    end

    Code:
    // Declared in header
    static struct STR_LINEAR
    {
    int     LIN_STRIPRECNO;
    int     LIN_STRIPWIDTH;
    int     LIN_STRIPDEPTH;
    int     LIN_TOTWASTE;
    int     LIN_QTY;
    int     LIN_PIECEQTY;
    int     LIN_CURRSTRIPRECNO;
    int     LIN_STRIPHEIGHT;
    int     LIN_VWPIECEQTY;
    } LINEAR[ MAXLINEARSIZE + 1 ], LINTEMP;
    
    // Test in shell sort
    if( LINEAR[a].LIN_STRIPWIDTH < LINEAR[a + shelljump].LIN_STRIPWIDTH )
              {
               LINTEMP = LINEAR[a];
               LINEAR[a] = LINEAR[a+shelljump];
                LINEAR[a+shelljump] = LINTEMP;
    
                trutest = TRUE;
              }
    This code fragment is an example of swapping elements of an array - could do the same thing with an array of pointers - which way you go will depend on the application. Using arrays of pointers is faster because the code above requires the contents of each array elent to be copied and if the structure is large its a lot of copying.

    In the example above, the sort only deals with a maximum of 15 elements, so it doesn't matter.
    Never re-write code unless the user benefits

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem with qsort and array via calloc
    By Zimbobo in forum C Programming
    Replies: 2
    Last Post: 11-23-2009, 12:25 AM
  2. qsort() in Array of Pointer to String
    By vb.bajpai in forum C Programming
    Replies: 8
    Last Post: 06-16-2007, 04:18 PM
  3. malloced 2d array passed to qsort
    By jamie85 in forum C Programming
    Replies: 7
    Last Post: 11-25-2005, 01:55 PM
  4. using qsort to sort an array of strings
    By bobthebullet990 in forum C Programming
    Replies: 6
    Last Post: 11-25-2005, 08:31 AM
  5. qsort( ) on a structured array
    By Thumper333 in forum C Programming
    Replies: 2
    Last Post: 10-21-2004, 07:39 PM