Keyword counting with structures

This is a discussion on Keyword counting with structures within the C Programming forums, part of the General Programming Boards category; Good morning. I have two problems: The program isn't printing the members of the key structure and I don't know ...

  1. #1
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193

    Question Keyword counting with structures

    Good morning. I have two problems: The program isn't printing the members of the key structure and I don't know how exactly the for below works because keytab + NKEYS is a bit strange to me (iterating with the condition that the pointer has to be less than the structure array + the nkeys ? how's that?)

    Code:
      for(p = keytab; p < keytab + NKEYS; p++)
    Code:
    struct key { 
      
      char* word;
      int count;    
        
    } keytab[] = { 
        
        "auto", 0, 
        "break", 0,
        "case", 0, 
        "char", 0,
        "const", 0, 
        "continue", 0,
        "default", 0,
        "unsigned", 0,
        "void", 0, 
        "volatile", 0,
        "while", 0
     };
      
      #include <stdio.h> 
      #include <ctype.h> 
      #include <string.h>
      
     #define MAXWORD 100
     #define NKEYS (sizeof keytab / sizeof keytab[0])
     #define BUFSIZE 100
     
     char buf[BUFSIZE];
     int bufp = 0;
     
     int getword(char*, int); 
     struct key* binsearch(char*, struct key*, int);
     int getch(void); 
     void ungetch(int);          
     
    /* the program counts how many times 
        a word from the structure array appears 
        and outputs the words and the respective count.
     */
    
    int main()
    { 
      char word[MAXWORD];
      struct key* p;
      while(getword(word, MAXWORD) != EOF)
        if(isalpha(word[0]))
         if((p = binsearch(word, keytab, NKEYS)) != NULL)
           p->count++;
      for(p = keytab; p < keytab + NKEYS; p++) 
         if(p->count > 0) 
            printf("%4d %s\n", p->count, p->word);       
      return 0;
    }                 
    
    /* binsearch: find word in tab[0]...tab[n-1] */
    struct key* binsearch(char* word, struct key* tab, int n) 
    { 
      int cond;
      struct key* low = &tab[0];
      struct key* high = &tab[n];
      struct key* mid;
      
      while(low < mid) 
      { 
        mid = low + (high-low) / 2;  
        if((cond = strcmp(word, mid->word)) < 0) 
          high = mid - 1;
        else if(cond > 0) 
          low = mid + 1;
        else 
          return mid;    
      }
      return NULL;           
    }          
    
    int getch(void) /* get a (possibly pushed back) character */
    {
      return (bufp > 0) ? buf[--bufp] : getchar();
    }
    
    void ungetch(int c) /* push character back on input */
    {
      if(bufp >= BUFSIZE)
        printf("ungetch: too many characters\n");
      else
        buf[bufp++] = c;
    }
    
    /* getword: get next word or character from input */
    int getword(char* word, int lim) 
    { 
      int c, getch(void);
      void ungetch(int);
      char* w = word;
      
      while(isspace(c = getch()))
       ; 
      if(c != EOF) 
        *w++ = c;  
      if(!isalpha(c)) {
        *w = '\0';            
        return c;
      }
      for(; --lim > 0; w++) 
        if(!isalnum(*w = getch()))
        {
          ungetch(*w);
          break;
        }
       *w = '\0';
       return word[0];                 
    }

  2. #2
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    Array names in many uses decay to a pointer to their first element.

    So, in the expression p = keytab, p gets assigned the address of the first element of the array;

    In the expression keytab + NKEYS, p decays and it's then just pointer arithmetic (the effect is the same as &keytab[NKEYS]).

    The third expression in the for, is just plain pointer arithmetic. It gets p to point to each successive member of the array.

  3. #3
    Registered User
    Join Date
    Oct 2011
    Posts
    830
    Quote Originally Posted by thames View Post
    keytab + NKEYS is a bit strange to me (iterating with the condition that the pointer has to be less than the structure array + the nkeys ? how's that?)
    It is pointer arithmetic.

    p is a pointer to a struct key, right? p = keytab starts the loop by setting it to the start of the keytab array.

    p++ advances the pointer p by one structure. Remember, (p + 5) and &p[5] are the exact same thing: pointers to the sixth structure counting from p .

    So, keytab + NKEYS is the same as &keytab[NKEYS] and is the pointer to the NKEYS'th element in the array. It is perfectly valid for a pointer to point to just after the array like that in C.

    Edit: qny beat me to the explanation.

  4. #4
    Registered User
    Join Date
    May 2012
    Posts
    1,066
    Quote Originally Posted by thames View Post
    The program isn't printing the members of the key structure
    The reason is your faulty binary search:
    Code:
    /* binsearch: find word in tab[0]...tab[n-1] */
    struct key* binsearch(char* word, struct key* tab, int n) 
    { 
      int cond;
      struct key* low = &tab[0];
      struct key* high = &tab[n];
    "high" points to an element just outside your array because you call binsearch() with NKEYS. NKEYS is the number of elements in your array and when you start indexing with 0 (as C does), the last valid index is number of elements - 1. Try your program with an input which compares bigger than "while" (e.g. "x") and you will probably get an seg fault.

    Code:
      struct key* mid;
      
      while(low < mid)
    At the first iteration, "mid" is uninitialized. But the real problem is, that your condition is wrong. You have to loop as long as low <= high (or high >= low)
    See https://en.wikipedia.org/wiki/Binary...ithm#Iterative

    Bye, Andreas

  5. #5
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    You're awesome people. Many thanks.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Counting Numbers in Array, not counting last number!
    By metaljester in forum C++ Programming
    Replies: 11
    Last Post: 10-18-2006, 11:25 AM
  2. Best Keyword
    By Eibro in forum C++ Programming
    Replies: 19
    Last Post: 11-27-2002, 07:28 AM
  3. extern keyword and structures
    By GuitGentlyWeeps in forum C Programming
    Replies: 2
    Last Post: 01-30-2002, 06:02 AM
  4. the far keyword
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 01-08-2002, 07:27 PM
  5. new keyword
    By Unregistered in forum C++ Programming
    Replies: 7
    Last Post: 10-31-2001, 10:58 AM

Tags for this Thread


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