lang/C/the.ansi.c.programming.language/c.programming.notes/homework/PS6a.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 #6 Answers</title>
  10 </head>
  11 <body>
  12 <H1>Assignment #6 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 #6 ANSWERS
  25 </B><br>
  26 <br>
  27 <p>Question 1.
  28 <I>If we say
  29 <TT>int i = 5;
  30 int *ip = &amp;i;
  31 </TT>then what is <TT>ip</TT>?
  32 What is its value?
  33 </I><p><TT>ip</TT> is a variable which can point to an <TT>int</TT>
  34 (that is, its value will be a pointer to an <TT>int</TT>;
  35 or informally, we say that <TT>ip</TT> <em>is</em>
  36 ``a pointer to an <TT>int</TT>'').
  37 Its value is a pointer which points to the variable <TT>i</TT>.
  38 <p>Question 2.
  39 <I>If ip is a pointer to an int, what does <TT>ip++</TT> mean?
  40 What does
  41 <TT>*ip++ = 0</TT>
  42 do?
  43 </I><p><TT>ip++</TT> means about the same as it does for any other variable:
  44 increment it by 1,
  45 that is,
  46 as if we had written <TT>ip = ip + 1</TT>.
  47 In
  48 the case of a pointer,
  49 this means to
  50 make it point to the object (the <TT>int</TT>)
  51 one past the one it used to.
  52 <TT>*ip++ = 0</TT> sets the <TT>int</TT> variable pointed to
  53 by <TT>ip</TT> to 0,
  54 and then increments <TT>ip</TT>
  55 to point to the next <TT>int</TT>.
  56 <p>Question 3.
  57 <I>How much memory does the call <TT>malloc(10)</TT> allocate?
  58 What if you want enough memory for 10 <TT>int</TT>s?
  59 </I><p><TT>malloc(10)</TT> allocates 10 bytes,
  60 which is
  61 enough space for 10 <TT>char</TT>s.
  62 To allocate space for 10 <TT>int</TT>s,
  63 you could call <TT>malloc(10 * sizeof(int))</TT>
  64 .
  65 <p>Question 4.
  66 <I>If <TT>char</TT> and <TT>int</TT> pointers are different,
  67 how is it possible to write
  68 </I><pre>
  69         char *cp = malloc(10);
  70         int *ip = malloc(sizeof(int));
  71 </pre>
  72 <I>without error on either line?
  73 </I><p><TT>malloc</TT> is declared as returning the special,
  74 ``generic'' pointer type <TT>void *</TT>,
  75 which can be
  76 (and is)
  77 automatically converted to different pointer types,
  78 as needed.
  79 <p>Exercise 1.
  80 <I>Write a program to read lines
  81 and print only those containing a certain word.
  82 </I><br>
  83 <br>
  84 <pre>
  85 #include &lt;stdio.h&gt;
  86 #include &lt;string.h&gt;
  87
  88 extern int getline(char [], int);
  89
  90 int main()
  91 {
  92         char line[100];
  93         char *pat = "hello";
  94
  95         while(getline(line, 100) != EOF)
  96                 {
  97                 if(strstr(line, pat) != NULL)
  98                         printf("%s\n", line);
  99                 }
 100
 101         return 0;
 102 }</pre>
 103 <p>Exercise 2.
 104 <I>Rewrite the checkbook-balancing program
 105 to use the <TT>getwords</TT> function
 106 to make it easy to take the word ``check'' or ``deposit'',
 107 and the amount, from a single line.
 108 </I><br>
 109 <br>
 110 <pre>
 111 #include &lt;stdio.h&gt;
 112 #include &lt;stdlib.h&gt;       /* for atof() */
 113
 114 #define MAXLINE 100
 115 #define MAXWORDS 10
 116
 117 extern int getline(char [], int);
 118 extern int getwords(char *, char *[], int);
 119
 120 int main()
 121 {
 122         double balance = 0.0;
 123         char line[MAXLINE];
 124         char *words[MAXWORDS];
 125         int nwords;
 126
 127         while (getline(line, MAXLINE) &gt; 0)
 128                 {
 129                 nwords = getwords(line, words, MAXWORDS);
 130
 131                 if(nwords == 0) /* blank line */
 132                         continue;
 133
 134                 if(strcmp(words[0], "deposit") == 0)
 135                         {
 136                         if(nwords &lt; 2)
 137                                 {
 138                                 printf("missing amount\n");
 139                                 continue;
 140                                 }
 141                         balance += atof(words[1]);
 142                         }
 143                 else if(strcmp(words[0], "check") == 0)
 144                         {
 145                         if(nwords &lt; 2)
 146                                 {
 147                                 printf("missing amount\n");
 148                                 continue;
 149                                 }
 150                         balance -= atof(words[1]);
 151                         }
 152                 else    {
 153                         printf("bad data line: \"%s\"\n", words[0]);
 154                         continue;
 155                         }
 156
 157                 printf("balance: %.2f\n", balance);
 158                 }
 159
 160         return 0;
 161 }</pre>
 162 <p>Exercise 3.
 163 <I>Rewrite the line-reversing function to use pointers.
 164 </I><p>Here is one way:
 165 <pre>
 166 int reverse(char *string)
 167 {
 168         char *lp = string;                      /* left pointer */
 169         char *rp = &amp;string[strlen(string)-1];       /* right pointer */
 170         char tmp;
 171         while(lp &lt; rp)
 172                 {
 173                 tmp = *lp;
 174                 *lp = *rp;
 175                 *rp = tmp;
 176                 lp++;
 177                 rp--;
 178                 }
 179         return 0;
 180 }
 181 </pre>
 182 <p>Exercise 4.
 183 <I>Rewrite the character-counting function to use pointers.
 184 </I><br>
 185 <br>
 186 <pre>
 187 int countnchars(char *string, int ch)
 188 {
 189         char *p;
 190         int count = 0;
 191         for(p = string; *p != '\0'; p++)
 192                 {
 193                 if(*p == ch)
 194                         count++;
 195                 }
 196         return count;
 197 }
 198 </pre>
 199 <p>Exercise 5.
 200 <I>Rewrite the string concatenation program
 201 to call <TT>malloc</TT> to allocate memory
 202 for the concatenated result.
 203 </I><p><pre>
 204 #include &lt;stdio.h&gt;
 205 #include &lt;stdlib.h&gt;       /* for malloc */
 206 #include &lt;string.h&gt;       /* for strcpy and strcat */
 207
 208 #define MAXLINE 100
 209
 210 extern int getline(char [], int);
 211
 212 int main()
 213 {
 214         char string1[MAXLINE], string2[MAXLINE];
 215         int len1, len2;
 216         char *newstring;
 217
 218         printf("enter first string:\n");
 219         len1 = getline(string1, 100);
 220         printf("enter second string:\n");
 221         len2 = getline(string2, 100);
 222
 223         if(len1 == EOF || len2 == EOF)
 224                 exit(1);
 225
 226         newstring = malloc(len1 + len2 + 1);    /* +1 for \0 */
 227
 228         if(newstring == NULL)
 229                 {
 230                 printf("out of memory\n");
 231                 exit(1);
 232                 }
 233
 234         strcpy(newstring, string1);
 235         strcat(newstring, string2);
 236
 237         printf("%s\n", newstring);
 238
 239         return 0;
 240 }</pre>
 241 <p>Exercise 6.
 242 <I>Rewrite the string-replacing function to use pointers.
 243 </I><p>Here is one way:
 244 <pre>
 245 void replace(char string[], char *from, char *to)
 246 {
 247         char *start, *p1, *p2;
 248         for(start = string; *start != '\0'; start++)
 249                 {
 250                 p1 = from;
 251                 p2 = start;
 252                 while(*p1 != '\0')
 253                         {
 254                         if(*p1 != *p2)
 255                                 break;
 256                         p1++;
 257                         p2++;
 258                         }
 259                 if(*p1 == '\0')
 260                         {
 261                         for(p1 = to; *p1 != '\0'; p1++)
 262                                 *start++ = *p1;
 263                         return;
 264                         }
 265                 }
 266 }
 267 </pre>
 268 The bulk of this code is a copy of
 269 the <TT>mystrstr</TT>
 270 function
 271 in the notes, chapter 10, section 10.4, p. 8.
 272 (Since <TT>strstr</TT>'s job is to find one string within
 273 another, it's a natural for the first half of <TT>replace</TT>.)
 274 We could also call <TT>strstr</TT> directly, simplifying <TT>replace</TT>:
 275 <pre>
 276 #include &lt;string.h&gt;
 277
 278 void replace(char string[], char *from, char *to)
 279 {
 280         char *p1;
 281         char *start = strstr(string, from);
 282         if(start != NULL)
 283                 {
 284                 for(p1 = to; *p1 != '\0'; p1++)
 285                         *start++ = *p1;
 286                 return;
 287                 }
 288 }
 289 </pre>
 290 Again,
 291 we might wonder about the case when the string to be
 292 edited contains multiple occurrences of the <TT>from</TT> string,
 293 and ask whether <TT>replace</TT> should replace the first one,
 294 or all of them.
 295 The problem statement didn't make this detail clear.
 296 Our first
 297 two implementations have
 298 replaced only the first occurrence.
 299 It happens, though, that it's trivial to rewrite our first version
 300 to make it replace all occurrences--just omit the
 301 <TT>return</TT> after the first string has been replaced:
 302 <pre>
 303 void replace(char string[], char *from, char *to)
 304 {
 305         char *start, *p1, *p2;
 306         for(start = string; *start != '\0'; start++)
 307                 {
 308                 p1 = from;
 309                 p2 = start;
 310                 while(*p1 != '\0')
 311                         {
 312                         if(*p1 != *p2)
 313                                 break;
 314                         p1++;
 315                         p2++;
 316                         }
 317                 if(*p1 == '\0')
 318                         {
 319                         for(p1 = to; *p1 != '\0'; p1++)
 320                                 *start++ = *p1;
 321                         }
 322                 }
 323 }
 324 </pre>
 325 Rewriting the second version wouldn't be much harder.
 326 <p>Exercise 7.
 327 <I>Write a program to read lines of text up to EOF,
 328 and then print them out in reverse order.
 329 </I><p>One of the reasons this program is harder
 330 is that it uses pointers to pointers.
 331 When we used pointers to simulate an array of integers,
 332 we used pointers to integers.
 333 In this program, we want to simulate an array of strings,
 334 or an array of pointers to characters.
 335 Therefore, we use <em>pointers</em> to pointers to characters,
 336 or <TT>char **</TT>.
 337 <pre>
 338 #include &lt;stdio.h&gt;
 339 #include &lt;stdlib.h&gt;
 340
 341 extern int getline(char [], int);
 342
 343 #define MAXLINE 100
 344
 345 int main()
 346 {
 347 int i;
 348 char line[MAXLINE];
 349 char **lines;
 350 int nalloc, nitems;
 351
 352 nalloc = 10;
 353 lines = malloc(nalloc * sizeof(char *));
 354 if(lines == NULL)
 355         {
 356         printf("out of memory\n");
 357         exit(1);
 358         }
 359
 360 nitems = 0;
 361
 362 while(getline(line, MAXLINE) != EOF)
 363         {
 364         if(nitems &gt;= nalloc)
 365                 {
 366                 char **newp;
 367                 nalloc += 10;
 368                 newp = realloc(lines, nalloc * sizeof(char *));
 369                 if(newp == NULL)
 370                         {
 371                         printf("out of memory\n");
 372                         exit(1);
 373                         }
 374                 lines = newp;
 375                 }
 376
 377         lines[nitems] = malloc(strlen(line) + 1);
 378         strcpy(lines[nitems], line);
 379         nitems++;
 380         }
 381
 382 for(i = nitems - 1; i &gt;= 0; i--)
 383         printf("%s\n", lines[i]);
 384
 385 return 0;
 386 }
 387 </pre>
 388 Notice that for each line we read,
 389 we call <TT>malloc</TT> to allocate space for a copy of it,
 390 and then use <TT>strcpy</TT> to make the copy.
 391 We could not simply set
 392 <pre>
 393         lines[nitems++] = line;
 394 </pre>
 395 each time,
 396 because <TT>line</TT> is a single array,
 397 which can only hold one line,
 398 and it gets overwritten with the contents of each input line.
 399 (In other words,
 400 if we didn't call <TT>malloc</TT> and make a copy,
 401 we'd end up at the end with only the last line.
 402 You might try it to see what happens.)
 403 <p><I>Extra credit:
 404 remove the restriction imposed by the fixed-size array;
 405 allow the program to accept
 406 arbitrarily-long lines.
 407 </I><p>First we will write another version of <TT>getline</TT>,
 408 called <TT>mgetline</TT>.
 409 <TT>mgetline</TT> calls <TT>malloc</TT> and <TT>realloc</TT>
 410 to get enough memory for the line it's currently reading,
 411 regardless of how long that line is.
 412 <TT>mgetline</TT> returns a pointer to the allocated memory;
 413 therefore,
 414 the caller does not have to pass an array for
 415 <TT>mgetline</TT> to read into.
 416 (It will be the caller's responsibility to <TT>free</TT> the
 417 memory when it doesn't need the line of text any more.)
 418 <pre>
 419 #include &lt;stdio.h&gt;
 420 #include &lt;stdlib.h&gt;
 421
 422 char *mgetline()
 423 {
 424 char *line;
 425 int nalloc = 10;
 426 int nch = 0;
 427 int c;
 428
 429 line = malloc(nalloc + 1);
 430 if(line == NULL)
 431         {
 432         printf("out of memory\n");
 433         exit(1);
 434         }
 435
 436 while((c = getchar()) != EOF)
 437         {
 438         if(c == '\n')
 439                 break;
 440
 441         if(nch &gt;= nalloc)
 442                 {
 443                 char *newp;
 444                 nalloc += 10;
 445                 newp = realloc(line, nalloc + 1);
 446                 if(newp == NULL)
 447                         {
 448                         printf("out of memory\n");
 449                         exit(1);
 450                         }
 451                 line = newp;
 452                 }
 453         line[nch++] = c;
 454         }
 455
 456 if(c == EOF &amp;&amp; nch == 0)
 457         {
 458         free(line);
 459         return NULL;
 460         }
 461
 462 line[nch] = '\0';
 463
 464 return line;
 465 }
 466 </pre>
 467 Now we can rewrite the line-reversing program to call <TT>mgetline</TT>.
 468 Note that we no longer need the local <TT>line</TT> array.
 469 Instead, we use a pointer, <TT>linep</TT>,
 470 which holds the return value from <TT>mgetline</TT>.
 471 Since <TT>mgetline</TT> returns a new pointer to a new block
 472 of memory each time we call it,
 473 in this program
 474 (unlike the previous one)
 475 we <em>can</em> set
 476 <pre>
 477         lines[nitems++] = linep;
 478 </pre>
 479 without overwriting anything.
 480 <pre>
 481 #include &lt;stdio.h&gt;
 482 #include &lt;stdlib.h&gt;
 483
 484 extern char *mgetline();
 485
 486 int main()
 487 {
 488 int i;
 489 char *linep;
 490 char **lines;
 491 int nalloc, nitems;
 492
 493 nalloc = 10;
 494 lines = malloc(nalloc * sizeof(char *));
 495 if(lines == NULL)
 496         {
 497         printf("out of memory\n");
 498         exit(1);
 499         }
 500
 501 nitems = 0;
 502
 503 while((linep = mgetline()) != NULL)
 504         {
 505         if(nitems &gt;= nalloc)
 506                 {
 507                 char **newp;
 508                 nalloc += 10;
 509                 newp = realloc(lines, nalloc * sizeof(char *));
 510                 if(newp == NULL)
 511                         {
 512                         printf("out of memory\n");
 513                         exit(1);
 514                         }
 515                 lines = newp;
 516                 }
 517
 518         lines[nitems++] = linep;
 519         }
 520
 521 for(i = nitems - 1; i &gt;= 0; i--)
 522         printf("%s\n", lines[i]);
 523
 524 return 0;
 525 }
 526 </pre>
 527 <hr>
 528 <hr>
 529 <p>
 530 This page by <a href="http://www.eskimo.com/~scs/">Steve Summit</a>
 531 // <a href="copyright.html">Copyright</a> 1995-9
 532 // <a href="mailto:scs@eskimo.com">mail feedback</a>
 533 </p>
 534 </body>
 535 </html>