(guest@joequery.me)~ $| Learning C (Part 3): K&R Ch1 Exercises (This post is part of the learning c series.) This article will provide solutions and explanations of K&R ch 1 exercises that I find interesting. Exercise 1-6 Verify that the expression getchar() != EOF is 0 or 1. The purpose of this exercise is to demonstrate that the resulting value of a conditional statement can only be 0 or 1.  1 2 3 4 5 6 7 8 9 #include int main(){ int expr_val, c; printf("Input a character and press enter: "); expr_val = (getchar() != EOF); printf("expr_val: %d\n", expr_val); return 0; }  $ ./a.out
Input a character and press enter: h
expr_val: 1
$./a.out # I press CTRL-D to send EOF Input a character and press enter: expr_val: 0  Exercise 1-8 Write a program to count blanks, tabs, and newlines. The purpose of this exercise is to test your ability to do a few things: • continuously get input from the keyboard • know when to stop • comparing the value from the keyboard with character literals • storing the count of the characters mentioned   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include int main(){ int c, num_tabs, num_blanks, num_newlines; num_tabs = num_blanks = num_newlines = 0; printf("Enter text. Press CTRL-D when finished\n> "); while( (c = getchar()) != EOF ){ if(c == '\n') printf("> "); switch(c){ case '\t': num_tabs++; break; case ' ': num_blanks++; break; case '\n': num_newlines++; break; } } printf("EOF sent\n"); printf("num_tabs: %d\n", num_tabs); printf("num_blanks: %d\n", num_blanks); printf("num_newlines: %d\n", num_newlines); return 0; }  $ ./a.out
Enter text. Press CTRL-D when finished
> Hello there. How are you doing today?
> Really? That's great!
> EOF sent
num_tabs: 0
num_blanks: 8
num_newlines: 2

$./a.out Enter text. Press CTRL-D when finished > I Love > Whitespace Formatting > EOF sent num_tabs: 2 num_blanks: 0 num_newlines: 2  Exercise 1-12 We will naively consider the word separating characters to be , \n, and \t. Also, as always, we must check for EOF. In this exercise, I will use a helper function named is_word_separator. This will be a good time to demonstrate writing simple tests via the standard library's assert() function. The assert() function takes an expression, generally some sort of comparison, and will stop program execution if the expression evaluates to False. Additionally, assert() will print out the failed assertion.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include #include // access to assert() function int main(){ int account_balance = 10; int product_cost = 20; // account_balance isn't allowed to be negative assert(account_balance > 0); // buy a product... account_balance -= product_cost; assert(account_balance > 0); return 0; }  $ ./a.out
a.out: assertion-ex.c:13: main: Assertion account_balance > 0' failed.
Aborted (core dumped)


The exercise solution:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 #include #include int is_word_separator(char c); void test_word_separator(); int main(){ int c, status; // First, we test our is_word_separator function. // If program execution makes it past this line, our is_word_separator // function is good! test_word_separator(); printf("Type words! CTRL-D to exit.\n"); printf("> "); status = 0; // 0 => out of word, 1 => inside word while( (c = getchar()) != EOF ){ // status can be 0 or 1, c can be word separator or not, so we have // 2x2=4 cases total to consider. if(status){ if(is_word_separator(c)){ status = 0; // Just for presentation! :) if(c == '\n') printf("\n> "); else printf("\n"); } else{ printf("%c", c); } } else{ if(is_word_separator(c)){ // Just for presentation! :) if(c == '\n') printf("> "); } else{ status = 1; printf("%c", c); } } } printf("EOF sent.\n"); return 0; } int is_word_separator(char c){ switch(c){ case '\n': case '\t': case ' ': return 1; default: return 0; } } void test_word_separator(){ assert(is_word_separator('x') == 0); assert(is_word_separator(' ') == 1); assert(is_word_separator('\n') == 1); assert(is_word_separator('\t') == 1); assert(is_word_separator('A') == 0); } 
$./a.out Type words! CTRL-D to exit. > Hello there! How are you doing today? Hello there! How are you doing today? > I'm doing pretty awesome, thanks! I'm doing pretty awesome, thanks! > > > > > > Tabs are pretty cool, man Tabs are pretty cool, man > EOF sent.  Exercise 1-13 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. We'll skip the horizontal representation for now. To further clarify, if we recieve 1 word of length one, 2 words of length two, 3 words of length three, etc, the histogram would look like so:  | || ||| 123  Here's an$O(n^2)$way of solving it. Note that it's really important you don't attempt to take on the entire exercise at once. Here's an intermediate program that prints the histogram from a hardcoded array. This facilitates quicker development and testing since keyboard input is easy but time-consuming.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 #include void make_histogram(int arr[], size_t n); int main(){ int word_lengths[] = {0, 3, 6, 5}; make_histogram(word_lengths, 4); return 0; } // 3 <= n <= 9 void make_histogram(int arr[], size_t n){ int i, maxval; // 0 length words don't mean anything, skipping over them. maxval = arr[1]; for(i=2; i maxval) maxval = arr[i]; while(maxval > 0){ for(i=1; i= maxval) putchar('|'); else putchar(' '); } putchar('\n'); maxval--; } // Print footer for(i=1; i  | || || ||| ||| ||| 123  Now that we have verified the make_histogram function works as intended, lets make a separate intermediate program that can take user input and count words. We can use a majority of the code from exercise 1-12, with some slight modifications, to facilitate this.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include int is_word_separator(char c); void get_word_lengths(int word_lengths[], size_t n); int main(){ int i; // Up to length 9. Initialize all to 0. int word_lengths[10] = {0}; get_word_lengths(word_lengths, 10); // Print the array elements for(i=1; i<10; i++) printf("Num words of length %d - %d\n", i, word_lengths[i]); return 0; } int is_word_separator(char c){ switch(c){ case '\n': case '\t': case ' ': return 1; default: return 0; } } void get_word_lengths(int word_lengths[], size_t n){ int c, status, length, i; printf("Type words! CTRL-D to exit.\n"); printf("> "); status = 0; // 0 => out of word, 1 => inside word length = 0; // current word length while( (c = getchar()) != EOF ){ if(status){ if(is_word_separator(c)){ status = 0; // We are at the end of the word. This is how we keep a tally. // Draw it out on a piece of paper if you don't understand :) ++word_lengths[length]; // Reset the word length since we are now finished with the // current word. length = 0; if(c == '\n') printf("> "); } else{ length++; } } else{ if(is_word_separator(c)){ if(c == '\n') printf("> "); } else{ status = 1; // We just encountered our first character of the new word length = 1; } } } }  $ ./a.out
Type words! CTRL-D to exit.
> a ab abc a ab abc
> EOF sent.
Num words of length 1 - 2
Num words of length 2 - 2
Num words of length 3 - 2
Num words of length 4 - 0
Num words of length 5 - 0
Num words of length 6 - 0
Num words of length 7 - 0
Num words of length 8 - 0
Num words of length 9 - 0

$./a.out Type words! CTRL-D to exit. > Hello there. How are you doing today? > EOF sent. Num words of length 1 - 0 Num words of length 2 - 0 Num words of length 3 - 3 Num words of length 4 - 0 Num words of length 5 - 2 Num words of length 6 - 2 Num words of length 7 - 0 Num words of length 8 - 0 Num words of length 9 - 0  Now, with both the histogram and word length counting individually verified, we can combine them without much effort at all! I only made some minor output changes to the functions for presentational purposes.   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 #include int is_word_separator(char c); void get_word_lengths(int word_lengths[], size_t n); void make_histogram(int arr[], size_t n); int main(){ // Up to length 9. Initialize all to 0. int word_lengths[10] = {0}; get_word_lengths(word_lengths, 10); putchar('\n'); make_histogram(word_lengths, 10); return 0; } // 3 <= n <= 9 void make_histogram(int arr[], size_t n){ int i, maxval; // 0 length words don't mean anything, skipping over them. maxval = arr[1]; for(i=2; i maxval) maxval = arr[i]; while(maxval > 0){ for(i=1; i= maxval) putchar('|'); else putchar(' '); } putchar('\n'); maxval--; } // Print footer for(i=1; i "); status = 0; // 0 => out of word, 1 => inside word length = 0; // current word length while( (c = getchar()) != EOF ){ if(status){ if(is_word_separator(c)){ status = 0; // We are at the end of the word. This is how we keep a tally. // Draw it out on a piece of paper if you don't understand :) ++word_lengths[length]; // Reset the word length since we are now finished with the // current word. length = 0; if(c == '\n') printf("> "); } else{ length++; } } else{ if(is_word_separator(c)){ if(c == '\n') printf("> "); } else{ status = 1; // We just encountered our first character of the new word length = 1; } } } }  $ ./a.out
Type words! CTRL-D to exit.
> a ab abc a ab abc
>
|||
|||
123456789

$./a.out Type words! CTRL-D to exit. > Hello there. How are you doing today? > | | || | || 123456789$ ./a.out
Type words! CTRL-D to exit.
> Hello there! How are you doing today, friend? I hope you are enjoying your
> C lessons. It is very good practice. These exercises will enhance your C skills for sure.
>
||
||
|||
| ||||
|||||||||
|||||||||
123456789


Exercise 1-19

Write a function reverse(s) that reverses the character string s. Use it to write a program that reverses its input a line at a time.

This will be a good time to draw a picture to get some ideas of how we would like to approach this. Consider the char array ['T', 'a', 'b', 'l', 'e', 't']. This is what reversing it would look like.

We can see that index 0 of s goes to index 5 of reverse(s), and so on. Generalizing this mapping is key to coming up with an algorithm for an arbitrary length string. Let's look at another example and see if you can catch on the pattern. (Hint: Use the length of the string)

So the index mapping can be formulized as x => max_index - x. So, for ['A', 'w', 'e', 's', 'o', 'm', 'e'], a char array of length 8 (thus with max index 7), element 2 ('e') would go to 7-2 == 5.

Also important to note, you'll see pairs of mappings in the index mappings. You see in the ['T', 'a', 'b', 'l', 'e', 't'] example that 0 goes to 5, and 5 goes to 0, 2 goes to 3, 3 goes to 2, etc. We can instead say 0 is swapped with 5, and 2 is swapped with 3. We can essentially cut our index mapping in half and use "swaps" instead of "goes to", while still providing the same information

A couple more warnings before we start coding.

Even/odd length char arrays

I intentionally chose char arrays of even lengths since the index mapping is easier to explain that way. However, our reverse() function needs to be able to handle odd-length char arrays. So let's examine ['H', 'e', 'l', 'l', 'o'].

Verify for yourself that max_index/2 stays put when reversing odd-length char arrays.

null-termination character

All strings are char arrays, but not all char arrays are strings: The difference is the terminating null character '\0' present in the char array. These examples so far have not been strings. When dealing with reversing strings, we need to ensure the null character doesn't move. Reversing a string should not change its length, so there's no need to move the null character.

Solution exercise

I will take advantage of the assert() function yet again to demonstrate the usefulness of automated testing. We can set up test-cases that let us know when we have reached our goal. Additionally, we can put ourselves in the "tester" mindset and focus on edge cases where our code may break.

Let's write our tests. We will use the strcmp() standard library function for string comparison. strcmp() takes two strings and returns 0 when they are equal. Additionally, strcpy will be used to copy string literals into an array, since string literals are read only.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 #include #include #include void test_reverse(); void reverse(char str[], size_t n); int main(){ test_reverse(); printf("reverse() works!\n"); return 0; } /* * Reverse a string str with array string length n (don't include null char!) * Note: the string passed is altered. */ void reverse(char str[], size_t n){ // To be implemented... } /* * Set up test cases to help us verify our reverse function works. */ void test_reverse(){ char str[10] = {0}; // Init all elements to \0 int testnum = 1; // Can the function handle odd-length strings? strcpy(str, "hello"); reverse(str, 5); assert(strcmp("olleh", str) == 0); printf("test %d pass\n", testnum++); // Can the function handle even-length strings? strcpy(str, "tablet"); reverse(str, 6); assert(strcmp("telbat", str) == 0); printf("test %d pass\n", testnum++); // What about shorter strings? strcpy(str, "hi"); reverse(str, 2); assert(strcmp("ih", str) == 0); printf("test %d pass\n", testnum++); strcpy(str, "hey"); reverse(str, 3); assert(strcmp("yeh", str) == 0); printf("test %d pass\n", testnum++); // What about 1-length strings? strcpy(str, "i"); reverse(str, 1); assert(strcmp("i", str) == 0); printf("test %d pass\n", testnum++); // And empty strings? strcpy(str, ""); reverse(str, 0); assert(strcmp("", str) == 0); printf("test %d pass\n", testnum++); } 
a.out: ex1-19-testcases.c:32: test_reverse: Assertion strcmp("olleh", str) ==
0' failed.
Aborted (core dumped)


We have now set up our code in such a way that once all the assertions pass, (and we can thus make "reverse() works!" print out), we can be confident that our reverse() function is correct! It is much easier to program a solution when you have created a roadmap such as this for yourself.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 #include #include #include void test_reverse(); void reverse(char str[], size_t n); int main(){ test_reverse(); printf("reverse() works!\n"); char str[] = "Hello there"; reverse(str, 11); printf("%s\n", str); return 0; } /* * Reverse a string str with array string length n (don't include null char!) * Note: the string passed is altered. */ void reverse(char str[], size_t n){ int i, tmp; // Remember / is integer division: 5/2 = 2 for(i=0; i
test 1 pass
test 2 pass
test 3 pass
test 4 pass
test 5 pass
test 6 pass
reverse() works!
ereht olleH


(This post is part of the learning c series.)

Date published - November 27, 2013