Programming Forums > Application Development > C

darthsabbath · Jun 2nd, 2006, 3:35 AM

Hi, all. I don't so much have a problem. My code works (or at least, it does in all tests I've ran so far), but as I'm still working on some of the examples in K&R, I'm just looking for some comments. Criticisms especially. If I've done something dumb, I want to know about it. Any feedback is helpful

.

Please note that I'm not using pointers, functions, or anything that has not been introduced yet at this time in the book... trying to play fair.

Anywhoo... here's the assignment, from the K&R text.

Quote:

Write a program to print a histogram of the lengths of words in its input. It is easy to draw the histogram with the bars horizontal; a vertical orientation is more challenging.

And here's my program.

(Toggle Plain Text)

/* K&R
 * Chapter 1
 * Exercise 1-13
 * Prints a histogram of word sizes
 */
#include <stdio.h>

#define		MAXSIZE		10		/* Maximum word size */

int main(void)
{
	int arr[MAXSIZE+1];				/* 10 sizes of words, plus a >MAXSIZE field */
	int i, j, nc, c;			/* Loop counters, number of characters, character */
	int highest = 0;					/* Used to get the highest value in arr[] */
	
	/* initialize arr[] to 0*/
	for (i = 0; i <= MAXSIZE; ++i)
		arr[i] = 0;
	
	nc = 0;

	while ((c = getchar()) != EOF) {
		++nc; /* Here we increment with each character until we hit a blank... */
		if (c == ' ' || c == '\n' || c == '\t' || c == EOF){
			--nc; /* ...then drop the blank */
			if (nc <= MAXSIZE) { 
				arr[nc-1]++;
				nc = 0;
			} else if (nc > MAXSIZE) {
				arr[MAXSIZE]++;
				nc = 0;
			}
		}
	}
	
	/* Let's see what the highest number in arr[] is */
	for (i = 0; i <= MAXSIZE; ++i) {
		if (arr[i] > highest)
			highest = arr[i];
	}

	/*Now let's do a vertical histogram */
	while (highest > 0) {
		printf("\t%3d: ", highest);
		for (i = 0; i <= MAXSIZE; ++i) {
			if (highest > arr[i])
				printf("     ");
			else 
				printf("  |  ");
		}
		printf("\n");
		highest--;
	}

	/* And now, the footer */
	printf("\t  --------------------------------------------------------\n\t     ");
	for(i = 0; i <= MAXSIZE; ++i) {
		if (i < MAXSIZE)
			printf("  %d  ", i+1);
		else
			printf(">%d ", MAXSIZE);
	}
	return 0;
}

Thanks,
Phil

grumpy · Jun 2nd, 2006, 3:59 AM

1) Declare your array to be of dimension MAXSIZE rather than MAXSIZE+1, and set loop conditions accordingly. For example, your first loop would be;

(Toggle Plain Text)

   for (i = 0; i < MAXSIZE; ++i)
		arr[i] = 0;

2) Favour preincrement (eg ++arr[nc-1]) over postincrement (eg arr[nc-1]++) unless you need to use the previous value.

3) If the first character in your input is a space, then the logic will be (commented)

(Toggle Plain Text)

   nc = 0;
   while ((c = getchar()) != EOF) {
		++nc;    /*  nc now 1 */
		if (c == ' ' || c == '\n' || c == '\t' || c == EOF){   /*  we've entered a space, so ... */
			--nc; /* nc now zero */
			if (nc <= MAXSIZE) {     /* this test is true */
				arr[nc-1]++;      /*  arr[-1]++ */

so your code exhibits undefined behaviour at this point.

4) Rather than testing against various whitespace characters, try the function isspace() which is in <ctype.h>

5) Compute the max value in your array like this;

(Toggle Plain Text)

        highest = arr[i];
	for (i = 1; i < MAXSIZE; ++i) {    /* end condition corrected as per first tip */
		if (arr[i] > highest)
			highest = arr[i];
	}

This allows the computation to work even if (say) you should change your program so it can hold negative values in the array. Your form will not.

6) Better yet, eliminate the computation of max and simply sort the array (but retain duplicate values). Then the values will contain values in order that you want to print them, and you simply need to count the number of times a value is in sequence to get the value for your histogram. This will be more efficient than what you're doing (printing highest, searching the whole array for that value, decrementing highest, and going over and over again).

darthsabbath · Jun 2nd, 2006, 3:43 PM

Quote:

Originally Posted by grumpy

3) If the first character in your input is a space, then the logic will be (commented)

(Toggle Plain Text)

   nc = 0;
   while ((c = getchar()) != EOF) {
	++nc;    /*  nc now 1 */
	if (c == ' ' || c == '\n' || c == '\t' || c == EOF){   /*  we've entered a space, so ... */
	--nc; /* nc now zero */
	if (nc <= MAXSIZE) {     /* this test is true */
		arr[nc-1]++;      /*  arr[-1]++ */

so your code exhibits undefined behaviour at this point.
that value, decrementing highest, and going over and over again).

So, using the ctype.h header and the isspace() function, would this be what you're getting at? (Sorry, I'm not at a computer with a compiler, so I can't test this)

(Toggle Plain Text)

while ((c = getchar()) != EOF) { 
   ++nc;
   if (isspace(c) ){  		
      --nc; 
      if ((nc > 0) && (nc < MAXSIZE)) {     
         ++arr[nc-1];
         nc = 0;
      } else if (nc > MAXSIZE) {
          arr[MAXSIZE]++;
          nc = 0;
      }
   }
}

Phil

grumpy · Jun 2nd, 2006, 5:31 PM

My third comment is about a real problem in your code; that problem is a showstopper. If your user inputs a space as the first character (or a '\n' or a '\t' ....) the program yields undefined behaviour. This is because of a basic flaw in your program logic. Read the comments in the code snippet I gave to see why.

The point of my 4th comment is to use isspace() from <ctype.h>. That is a minor improvement, which has nothing to do with addressing the preceding problem of undefined behaviour.

darthsabbath · Jun 2nd, 2006, 6:55 PM

Quote:

Originally Posted by grumpy

My third comment is about a real problem in your code; that problem is a showstopper. If your user inputs a space as the first character (or a '\n' or a '\t' ....) the program yields undefined behaviour. This is because of a basic flaw in your program logic. Read the comments in the code snippet I gave to see why.

The point of my 4th comment is to use isspace() from <ctype.h>. That is a minor improvement, which has nothing to do with addressing the preceding problem of undefined behaviour.

Sorry, I was actually trying to solve both 3. and 4. Shows what I get for trying to do this on break. :-) I should have been more clear.

At any rate, I added an additional test to the second if statement (see comments), only entering the statement if nc is between 0 and MAXSIZE.

When I get home I'm going to work on this some more. I do appreciate the help, though! :-)

(Toggle Plain Text)

 
while ((c = getchar()) != EOF) { 
   ++nc; /* Increment to 1*/
   if (isspace(c) ){   	 	
      --nc; /* Toss out the space, nc is now 0 */
      if ((nc > 0) && (nc < MAXSIZE)) { /* This test fails if nc is 0, correct? */
         ++arr[nc-1];
         nc = 0;
      } else if (nc > MAXSIZE) {
          arr[MAXSIZE]++;
          nc = 0;
      }
   }
}

grumpy · Jun 3rd, 2006, 3:16 AM

A couple more comments

1) If you use a test case that contains two or more spaces in sequence, the histogram will not be correct. I'm guessing all your test cases only have one space between two words.

2) Something that works along the lines;

(Toggle Plain Text)

  ++x;
  if (some_condition)
  {
        --x;
        more_stuff();
  }

can be expressed more cleanly in the form;
[code]

(Toggle Plain Text)

  if (some_condition)
  {
        more_stuff();
  }
  else
  {
      ++x;
  }

Your last code snippet is in that form .....

Jun 2nd, 2006, 3:59 AM	#2
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,198 Rep Power: 5	1) Declare your array to be of dimension MAXSIZE rather than MAXSIZE+1, and set loop conditions accordingly. For example, your first loop would be; (Toggle Plain Text) for (i = 0; i < MAXSIZE; ++i) arr[i] = 0; for (i = 0; i < MAXSIZE; ++i) arr[i] = 0; 2) Favour preincrement (eg ++arr[nc-1]) over postincrement (eg arr[nc-1]++) unless you need to use the previous value. 3) If the first character in your input is a space, then the logic will be (commented) (Toggle Plain Text) nc = 0; while ((c = getchar()) != EOF) { ++nc; /* nc now 1 / if (c == ' ' \|\| c == '\n' \|\| c == '\t' \|\| c == EOF){ / we've entered a space, so ... / --nc; / nc now zero / if (nc <= MAXSIZE) { / this test is true / arr[nc-1]++; / arr[-1]++ / nc = 0; while ((c = getchar()) != EOF) { ++nc; / nc now 1 / if (c == ' ' \|\| c == '\n' \|\| c == '\t' \|\| c == EOF){ / we've entered a space, so ... / --nc; / nc now zero / if (nc <= MAXSIZE) { / this test is true / arr[nc-1]++; / arr[-1]++ / so your code exhibits undefined behaviour at this point. 4) Rather than testing against various whitespace characters, try the function isspace() which is in <ctype.h> 5) Compute the max value in your array like this; (Toggle Plain Text) highest = arr[i]; for (i = 1; i < MAXSIZE; ++i) { / end condition corrected as per first tip / if (arr[i] > highest) highest = arr[i]; } highest = arr[i]; for (i = 1; i < MAXSIZE; ++i) { / end condition corrected as per first tip */ if (arr[i] > highest) highest = arr[i]; } This allows the computation to work even if (say) you should change your program so it can hold negative values in the array. Your form will not. 6) Better yet, eliminate the computation of max and simply sort the array (but retain duplicate values). Then the values will contain values in order that you want to print them, and you simply need to count the number of times a value is in sequence to get the value for your histogram. This will be more efficient than what you're doing (printing highest, searching the whole array for that value, decrementing highest, and going over and over again).

Jun 3rd, 2006, 3:16 AM	#6
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,198 Rep Power: 5	A couple more comments 1) If you use a test case that contains two or more spaces in sequence, the histogram will not be correct. I'm guessing all your test cases only have one space between two words. 2) Something that works along the lines; (Toggle Plain Text) ++x; if (some_condition) { --x; more_stuff(); } ++x; if (some_condition) { --x; more_stuff(); } can be expressed more cleanly in the form; [code] (Toggle Plain Text) if (some_condition) { more_stuff(); } else { ++x; } if (some_condition) { more_stuff(); } else { ++x; } Your last code snippet is in that form .....

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Jun 2nd, 2006, 5:31 PM	#4
grumpy Programming Guru Join Date: Jun 2005 Location: Adelaide, South Australia Posts: 1,198 Rep Power: 5	My third comment is about a real problem in your code; that problem is a showstopper. If your user inputs a space as the first character (or a '\n' or a '\t' ....) the program yields undefined behaviour. This is because of a basic flaw in your program logic. Read the comments in the code snippet I gave to see why. The point of my 4th comment is to use isspace() from <ctype.h>. That is a minor improvement, which has nothing to do with addressing the preceding problem of undefined behaviour.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

Code Critique