C/the.ansi.c.programming.language/c.programming.notes/homework/PS4a.html

   1 <!DOCTYPE HTML PUBLIC "-//W3O//DTD W3 HTML 2.0//EN">
   2 <!-- This collection of hypertext pages is Copyright 1995-7 by Steve Summit. -->
   3 <!-- This material may be freely redistributed and used -->
   4 <!-- but may not be republished or sold without permission. -->
   5 <html>
   6 <head>
   7 <link rev="owner" href="mailto:scs@eskimo.com">
   8 <link rev="made" href="mailto:scs@eskimo.com">
   9 <title>Assignment #4 Answers</title>
  10 </head>
  11 <body>
  12 <H1>Assignment #4 Answers</H1>
  13
  14
  15
  16
  17
  18 <B>Introductory C Programming
  19 <br>
  20 <br>
  21 UW Experimental College
  22 <br>
  23 <br>
  24 Assignment #4 ANSWERS
  25 </B><br>
  26 <br>
  27 <p>Question 1.
  28 <I>What would the expression
  29 <pre>
  30         c = getchar() != EOF
  31 </pre>
  32 </I><I>do?
  33 </I><p>It would read one character and compare it to the constant <TT>EOF</TT>.
  34 If the character read was equal to <TT>EOF</TT>,
  35 it would set <TT>c</TT> to 0,
  36 otherwise
  37 (i.e. for any other character)
  38 it would set <TT>c</TT> to 1.
  39 What it would <em>not</em> do is read a character,
  40 assign it to <TT>c</TT>,
  41 and then test it against <TT>EOF</TT>,
  42 which is what you usually want to do,
  43 and which you need to write
  44 <pre>
  45         (c = getchar()) != EOF
  46 </pre>
  47 to do.
  48 <p>Question 2.
  49 <I>Why must the variable used to hold <TT>getchar</TT>'s return value
  50 be type <TT>int</TT>?
  51 </I><p>So that it can reliably store the value <TT>EOF</TT>.
  52 <p>Variables of type <TT>char</TT> are typically 8 bits large,
  53 which means that they can hold 2<tt>&lt;sup&gt;</tt>8<tt>&lt;/sup&gt;</tt>,
  54 or 256 different character values.
  55 Furthermore, on an 8-bit system,
  56 <TT>getchar</TT> can theoretically return
  57 characters having any of these 256 character values.
  58 However, <TT>getchar</TT> can also return a 257th value, <TT>EOF</TT>,
  59 which is not a character value but rather an indication that there are no
  60 more characters to get.
  61 You can no more reliably store
  62 <TT>getchar</TT>'s 257 return values in a
  63 variable of type <TT>char</TT> than you can store 13 eggs in a
  64 carton that holds a dozen.
  65
  66 If you tried to assign <TT>getchar</TT>'s return value
  67 to a <TT>char</TT>,
  68 you could either mistake a real character value for <TT>EOF</TT>
  69 or <TT>EOF</TT> for a real character value,
  70 resulting either in premature termination of input or an infinite loop.
  71 <p>An <TT>int</TT>, on the other hand, is on the vast majority of
  72 machines larger than a <TT>char</TT>, so it can comfortably hold
  73 all 256 character values, <em>plus</em> <TT>EOF</TT>.
  74 <p>Question 3.
  75 <I>What is the difference
  76 between the prefix and postfix forms of the <TT>++</TT> operator?
  77 </I><p>The prefix form increments first,
  78 and the incremented value goes on to participate in the
  79 surrounding expression (if any).
  80 The postfix form increments later;
  81 the previous value
  82 goes on to participate in the surrounding expression.
  83 <p>Question 4.
  84 <I>What would the expression
  85 <pre>
  86         i = i++
  87 </pre>
  88 do?
  89 </I><p>Nothing, or at least, nothing useful.
  90 Since it tries to modify <TT>i</TT> twice,
  91 it's undefined.
  92 <p>Question 5.
  93 <I>What is the definition of a string in C?
  94 </I><br>
  95 <br>
  96 An array of characters,
  97 terminated with the null character <TT>\0</TT>.
  98 <p>Question 6.
  99 <I>What will the <TT>getline</TT> function
 100 do
 101 if successive calls to <TT>getchar</TT> return the four values
 102 <TT>'a'</TT>, <TT>'b'</TT>, <TT>'c'</TT>, and <TT>EOF</TT>?
 103 </I><p>The first three characters are placed in the <TT>line</TT> array,
 104 as usual,
 105 and when the <TT>EOF</TT> indicator is read,
 106 <TT>getline</TT> breaks out of its loop,
 107 also as usual.
 108 Although <TT>c</TT> is now <TT>EOF</TT>,
 109 <TT>nch</TT> is 3,
 110 so the condition <TT>c == EOF &amp;&amp; nch == 0</TT>
 111 is false.
 112 <TT>getline</TT> therefore does not return <TT>EOF</TT>,
 113 but rather terminates the line with <TT>\0</TT>
 114 and returns its length,
 115 just as it does with a normal line
 116 which it finds <TT>\n</TT> at the end of.
 117 <br>
 118 <br>
 119 Can this situation ever occur?
 120 One way to answer a question like this is not to try too hard to answer it,
 121 to err on the side of conservatism,
 122 to assume that if we can't prove that the unusual situation won't arise,
 123 we might as well be safe and arrange that our code can handle it
 124 <em>if</em> it somehow comes up.
 125 (There's obviously little or no harm in writing code
 126 to handle a situation that never comes up,
 127 while the reverse--neglecting
 128 to write code to handle a situation that <em>does</em> come up--can
 129 of course be very harmful.)
 130 <br>
 131 <br>
 132 In any case,
 133 under Unix at least,
 134 this situation can in fact come up.
 135 Unix does not enforce any notion of a ``text file'';
 136 the sequence <TT>a</TT>, <TT>b</TT>, <TT>c</TT>, <TT>EOF</TT>
 137 at the end of a file
 138 is no more or less favored
 139 (by the operating system, that is)
 140 than the sequence <TT>a</TT>, <TT>b</TT>, <TT>c</TT>, <TT>\n</TT>, <TT>EOF</TT>.
 141 Furthermore, there are some programs
 142 (e.g. full-screen text editors such as EMACS)
 143 which make it easy to create a text file without a final newline
 144 (if only by accident).
 145 (But there are also examples of programs
 146 which inadvertently ignore the last line of a file
 147 whose last line does not end in <TT>\n</TT>,
 148 and this is a bug which can cause data loss.)
 149 So writing <TT>getline</TT> to treat a ``line'' ending in <TT>EOF</TT>
 150 (but no <TT>\n</TT>)
 151 is not only reasonable, but useful.
 152 <p>Tutorial 2.
 153 <I>Improve the <TT>myatoi</TT> function so that it can handle negative numbers.
 154 </I><p>[You've seen the answer already, because I accidentally left
 155 the sign-handling code--within <TT>#ifdef SIGN</TT>--turned
 156 on in the copy of the code printed in the assignment.
 157 Oops.]
 158 <pre>
 159 #include &lt;ctype.h&gt;
 160
 161 int myatoi(char str[])
 162 {
 163         int i;
 164         int retval = 0;
 165         int negflag = 0;
 166
 167         for(i = 0; str[i] != '\0'; i = i + 1)
 168                 {
 169                 if(!isspace(str[i]))
 170                         break;
 171                 }
 172
 173         if(str[i] == '-')
 174                 {
 175                 negflag = 1;
 176                 i = i + 1;
 177                 }
 178
 179         for(; str[i] != '\0'; i = i + 1)
 180                 {
 181                 if(!isdigit(str[i]))
 182                         break;
 183                 retval = 10 * retval + (str[i] - '0');
 184                 }
 185
 186         if(negflag)
 187                 retval = -retval;
 188
 189         return retval;
 190 }
 191 </pre>
 192 <p>Tutorial 3.
 193 <I>Modify the ``word zipping'' program
 194 to move the word from right to left instead of left to right.
 195 </I><pre>
 196 #include &lt;stdio.h&gt;
 197
 198 extern int getline(char [], int);
 199
 200 int main()
 201 {
 202         char word[20];
 203         int len;
 204         int i, j;
 205
 206         printf("type something: ");
 207         len = getline(word, 20);
 208         for(i = 80 - len - 1; i &gt;= 0; i--)
 209                 {
 210                 for(j = 0; j &lt; i; j++)
 211                         printf(" ");
 212                 printf("%s \r", word);
 213                 }
 214         printf("\n");
 215
 216         return 0;
 217 }</pre>
 218 <p>Exercise 4.
 219 <I>Write a program
 220 which computes the average
 221 (and standard deviation)
 222 of a series of numbers.
 223 </I><pre>
 224 #include &lt;stdio.h&gt;
 225 #include &lt;stdlib.h&gt;
 226 #include &lt;math.h&gt;
 227
 228 extern int getline(char [], int);
 229
 230 int main()
 231 {
 232         char line[100];
 233         int x;
 234         double sum, sumsq;
 235         int n;
 236         double mean, stdev;
 237
 238         sum = sumsq = 0.0;
 239         n = 0;
 240
 241         while(getline(line, 100) != EOF)
 242                 {
 243                 x = atoi(line);
 244                 sum = sum + x;
 245                 sumsq = sumsq + x * x;
 246                 n = n + 1;
 247                 }
 248
 249         mean = sum / n;
 250         stdev = sqrt((sumsq - sum * sum / n) / (n - 1));
 251
 252         printf("mean: %f\n", mean);
 253         printf("std. dev.: %f\n", stdev);
 254
 255         return 0;
 256 }
 257
 258 </pre>
 259 <p>Exercise 5.
 260 <I>Write
 261 your own version of the <TT>atoi</TT> function.
 262 </I><p>[Obviously I should have removed this exercise when I added Tutorial 2.
 263 Apologies for the duplication.]
 264 <p>Here is a simple implementation:
 265 <pre>
 266 int myatoi(char str[])
 267 {
 268         int retval = 0;
 269         int i = 0;
 270
 271         while(str[i] != '\0')
 272                 {
 273                 int digit = str[i] - '0';
 274                 retval = 10 * retval + digit;
 275                 i++;
 276                 }
 277
 278         return retval;
 279 }
 280 </pre>
 281 Remember that characters are represented by small integers
 282 representing their values in the machine's character set.
 283 We shouldn't have to know what these values are,
 284 but if we assume that the characters
 285 <TT>'0'</TT>, <TT>'1'</TT>, <TT>'2'</TT>, ... <TT>'9'</TT>
 286 have consecutive values
 287 (which, as it happens, is a perfectly valid assumption)
 288 then subtracting the value of the character <TT>'0'</TT>
 289 from any digit character will give us that digit's value.
 290 For example, <TT>'1' - '0'</TT> is 1,
 291 <TT>'2' - '0'</TT> is 2,
 292 and of course <TT>'0' - '0'</TT> is 0.
 293 If <TT>str[i]</TT> is a digit character,
 294 then <TT>str[i] - '0'</TT> is its value.
 295 (In all of these subtractions,
 296 we are using the constant <TT>'0'</TT> to mean
 297 ``the value of the character <TT>'0',</TT>''
 298 which is,
 299 in fact,
 300 exactly what it means.)
 301 <br>
 302 <br>
 303 The operation of the function is simple:
 304 it moves through the string from left to right,
 305 converting each digit character to a digit value
 306 and building up the return value.
 307 Each time we find another digit character,
 308 it (obviously) indicates that
 309 the number we're converting <em>has</em> another digit,
 310 so we multiply the number we've converted so far by 10,
 311 and add in the new digit.
 312 (Walk through this algorithm to convince yourself that it works.
 313 For example, if the string to be converted is <TT>"123"</TT>,
 314 we'll make three trips through the loop,
 315 and <TT>retval</TT> will successively take on the values 1, 12, and finally 123.)
 316 <br>
 317 <br>
 318 Here is a little test program to read strings from the user,
 319 convert them to numbers using <TT>myatoi</TT>,
 320 and print out the converted numbers:
 321 <pre>
 322 #include &lt;stdio.h&gt;
 323
 324 int main()
 325 {
 326         char line[100];
 327         int n;
 328
 329         while(1)
 330                 {
 331                 printf("type a number:\n");
 332                 if(getline(line, 100) == EOF)
 333                         break;
 334                 n = myatoi(line);
 335                 printf("you typed %d\n", n);
 336                 }
 337
 338         return 0;
 339 }
 340 </pre>
 341 <br>
 342 <br>
 343 This first implementation of <TT>myatoi</TT> works,
 344 but only if the string contains digits and only digits.
 345 If the string contains any character other than a digit,
 346 the expression <TT>str[i] - '0'</TT>
 347 will result in a meaningless digit value.
 348 Therefore, a better implementation of <TT>myatoi</TT>
 349 would ensure that it only attempted to convert digits.
 350 <br>
 351 <br>
 352 There are in fact several situations under which the string might
 353 contain characters other than digits.
 354 It might contain some spaces before the number to be converted
 355 (e.g. <TT>"  123"</TT>),
 356 or the number to be converted might begin with a minus sign.
 357 In any case, the caller might carelessly pass a string which
 358 contained some non-digit characters
 359 (perhaps at the end, following some digit characters).
 360 We will next look at an improved version of <TT>myatoi</TT>
 361 which allows for these possibilities.
 362 <br>
 363 <br>
 364 The standard library contains several functions
 365 which test for various classes of characters.
 366 The <TT>isspace</TT> function returns nonzero
 367 (i.e. ``true'')
 368 for a whitespace character (e.g. space or tab).
 369 Similarly, the <TT>isdigit</TT> function returns nonzero
 370 (i.e. ``true'')
 371 for a digit character.
 372 These functions are declared in the header <TT>&lt;ctype.h&gt;</TT>.
 373 Here is an improved version of <TT>myatoi</TT>
 374 which uses <TT>isspace</TT> to skip leading whitespace
 375 and <TT>isdigit</TT> to ensure that it attempts to convert only digits.
 376 It also checks for a leading minus sign
 377 (but after checking for leading whitespace).
 378 <pre>
 379 #include &lt;ctype.h&gt;
 380
 381 int myatoi(char str[])
 382 {
 383         int retval = 0;
 384         int i = 0;
 385         int negflag = 0;
 386
 387         while(isspace(str[i]))  /* skip leading whitespace */
 388                 i++;
 389
 390         if(str[i] == '-')       /* look for - sign */
 391                 {
 392                 negflag = 1;
 393                 i++;
 394                 }
 395
 396         while(str[i] != '\0' &amp;&amp; isdigit(str[i]))
 397                 {
 398                 int digit = str[i] - '0';
 399                 retval = 10 * retval + digit;
 400                 i++;
 401                 }
 402
 403         if(negflag)
 404                 retval = -retval;
 405
 406         return retval;
 407 }
 408 </pre>
 409 Notice that <TT>negflag</TT> is an example of a
 410 ``Boolean'' variable--we store a 0 or 1 in it to
 411 represent a ``false'' or ``true'' condition
 412 which we then test for later.
 413 (If we find a minus sign,
 414 we find it before we scan and convert the digits,
 415 but it's easier to make use of the fact that we saw a minus sign--to
 416 make use of it, that is,
 417 by actually negating the number we converted--after
 418 we convert it.)
 419 <br>
 420 <br>
 421 Since the improved function scans and converts digits only as
 422 long as they <em>are</em> digits
 423 (as confirmed by <TT>isdigit</TT>),
 424 this version will quietly ignore any trailing non-digits.
 425 That is, <TT>atoi("123xyz")</TT> will simply return 123.
 426 (This is exactly the way the standard <TT>atoi</TT> function behaves.)
 427 Furthermore,
 428 calling <TT>myatoi</TT>
 429 (or <TT>atoi</TT>)
 430 with a string containing no digits at all,
 431 such as <TT>"abcxyz"</TT>,
 432 will quietly
 433 return 0.
 434 <p>Exercise 6.
 435 <I>Write a rudimentary checkbook balancing program.
 436 </I><br>
 437 <br>
 438 <pre>
 439 #include &lt;stdio.h&gt;
 440 #include &lt;stdlib.h&gt;       /* for atof() */
 441
 442 #define MAXLINE 100
 443
 444 extern int getline(char [], int);
 445
 446 int main()
 447 {
 448         double balance = 0.0;
 449         char line1[MAXLINE], line2[MAXLINE];
 450
 451         while(getline(line1, MAXLINE) &gt; 0)
 452                 {
 453                 getline(line2, MAXLINE);
 454
 455                 if(strcmp(line1, "deposit") == 0)
 456                         balance += atof(line2);
 457                 else if(strcmp(line1, "check") == 0)
 458                         balance -= atof(line2);
 459                 else    {
 460                         printf("bad data line: not \"check\" or \"deposit\"\n");
 461                         continue;
 462                         }
 463
 464                 printf("balance: %.2f\n", balance);
 465                 }
 466
 467         return 0;
 468 }</pre>
 469 <p>Reading the key word and the amount from the same line
 470 would be surprisingly difficult,
 471 using only the tools we have in hand so far.
 472 We'll see a clean way of doing it in a week or two.
 473 <p>Exercise 7.
 474 <I>Rewrite the ``compass'' code
 475 to use <TT>strcpy</TT> and <TT>strcat</TT>.
 476 </I><br>
 477 <br>
 478 <pre>
 479 char word[20];
 480
 481 if(y &gt; 0)
 482         strcpy(word, "north");
 483 else if(y &lt; 0)
 484         strcpy(word, "south");
 485 else    strcpy(word, "");               /* empty string */
 486
 487 if(x &gt; 0)
 488         strcat(word, "east");
 489 else if(x &lt; 0)
 490         strcat(word, "west");
 491 else    strcat(word, "");               /* empty string */
 492
 493 printf("%s\n", word);
 494 </pre>
 495 <p>Exercise 8.
 496 <I>Write a program to read its input,
 497 one character at a time,
 498 and print each character and its decimal value.
 499 </I><br>
 500 <br>
 501 <pre>
 502 #include &lt;stdio.h&gt;
 503
 504 int main()
 505 {
 506         int c;
 507
 508         while((c = getchar()) != EOF)
 509                 printf("character %c has value %d\n", c, c);
 510
 511         return 0;
 512 }</pre>
 513 You will notice that this program prints a funny line or two
 514 for each new line (<TT>'\n'</TT>) in the input,
 515 because when the <TT>%c</TT> in the <TT>printf</TT> call
 516 finds itself printing a <TT>\n</TT> character that we've just read,
 517 it naturally prints a newline at that point.
 518 <p>Exercise 9.
 519 <I>Write a program to read its input,
 520 one line at a time,
 521 and print each line backwards.
 522 </I><p>Here is one way of doing it,
 523 using only what we've seen so far:
 524 <pre>
 525 #include &lt;stdio.h&gt;
 526
 527 extern int getline(char [], int);
 528 extern int reverse(char [], int);
 529
 530 int main()
 531 {
 532         char line[100];
 533         int len;
 534
 535         while((len = getline(line, 100)) != EOF)
 536                 {
 537                 reverse(line, len);
 538                 printf("%s\n", line);
 539                 }
 540
 541         return 0;
 542 }
 543
 544 int reverse(char string[], int len)
 545 {
 546         int i;
 547         char tmp;
 548         for(i = 0; i &lt; len / 2; i = i + 1)
 549                 {
 550                 tmp = string[i];
 551                 string[i] = string[len - i - 1];
 552                 string[len - i - 1] = tmp;
 553                 }
 554         return 0;
 555 }
 556 </pre>
 557 In practice, it would be a nuisance to have to pass the length
 558 of the string to the <TT>reverse</TT> function.
 559 Strings in C are always terminated by the ``zero'' or
 560 ``nul'' character, represented by <TT>\0</TT>.
 561 Therefore, <TT>reverse</TT> (or any piece of code)
 562 can always compute the length of a string, either by searching
 563 for the <TT>\0</TT>,
 564 or by calling the library function <TT>strlen</TT>,
 565 which computes the length of a string by searching for the
 566 <TT>\0</TT>.
 567 Here is how the program might look if the <TT>reverse</TT>
 568 function did not require that the length of the string be
 569 passed in:
 570 <pre>
 571 #include &lt;stdio.h&gt;
 572 #include &lt;string.h&gt;
 573
 574 extern int getline(char [], int);
 575 extern int reverse(char []);
 576
 577 int main()
 578 {
 579         char line[100];
 580
 581         while(getline(line, 100) != EOF)
 582                 {
 583                 reverse(line);
 584                 printf("%s\n", line);
 585                 }
 586
 587         return 0;
 588 }
 589
 590 int reverse(char string[])
 591 {
 592         int len = strlen(string);
 593         int i;
 594         char tmp;
 595         for(i = 0; i &lt; len / 2; i = i + 1)
 596                 {
 597                 tmp = string[i];
 598                 string[i] = string[len - i - 1];
 599                 string[len - i - 1] = tmp;
 600                 }
 601         return 0;
 602 }
 603 </pre>
 604 <hr>
 605 <hr>
 606 <p>
 607 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 608 // <a href="copyright.html">Copyright</a> 1995-9
 609 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 610 </p>
 611 </body>
 612 </html>