Thread: 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];                 
}

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.

Originally Posted by thames

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.

Originally Posted by thames

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

You're awesome people. Many thanks.