CS 2213/2211 -- Recitation 4

CS 2213/2211
Advanced Programming
Spring 2005
Recitation 4: Pointers
    Week 4: Feb 8-10
Due (on time): 2005-02-15  23:59:59
Due (late):        2005-02-20  23:59:59

Recitation 4 should be submitted following directions at: submissions with deadlines

2005-02-15 23:59:59 (that's Tuesday, 15 February 2005, 11:59:59 pm) for full credit.
2005-02-20 23:59:59 (that's Sunday, 20 February 2005, 11:59:59 pm) for 75% credit.

Introduction: This recitation works on five areas:

Working with pointers in C.
Working with separate header and source files.
Working with input/output facilities.
Using command-line arguments in C.
Understanding and modifying sophisticated C code.

This recitation gives 4 steps for you to go through. It is important that you do these steps individually, so that no single part is overwhelming. You should keep code for the 4 parts separate (preferably in separate directories) so you can include the separate parts in your submission. There will be substantial credit for this recitation even if you don't finish all 4 parts.

Initial Code to Work From: The following two files form the basis for this recitation:

Get integer example: getint.c Header file getint.h, and Output

Get integer example: `getint.c`	Header file `getint.h`, and Output
/* getint.c: fetch next int / #include <ctype.h> #include <stdio.h> #include "getint.h" static int getch(void); static void ungetch(int c); / getint: get next integer from input into pn / int getint(int pn) { int c, sign; while (isspace(c = getch())) / skip white space / ; if (!isdigit(c) && c != EOF && c != '+' && c != '-'){ ungetch(c); / it is not a number / return 0; } sign = (c == '-') ? -1 : 1; if (c == '+' \|\| c == '-') c = getch(); for (pn = 0; isdigit(c); c = getch()) pn = 10 pn + (c - '0'); pn = sign; if (c != EOF) ungetch(c); return c; } / getch and ungetch functions are also required. / #include <stdio.h> #define BUFSIZE 100 char buf[BUFSIZE]; / buffer for ungetch / int bufp = 0; / next free position in buf / static int getch(void) {/(possibly pushed-back) char / return (bufp > 0) ? buf[--bufp] : getchar(); } static void ungetch(int c) {/push char back on input */ if (bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; }	*/ getint.h: header for getint.c / int getint(int pn); ------------------------------------- Sample Run for First Step % cat rec4_input.txt 53 314159 -453 0 0123 % cc -o getint getint.c getint_test.c % getint_test < rec4_input.txt Next integer: 53 Next integer: 314159 Next integer: -453 Next integer: 0 Next integer: 123 Th-th-th-th-that's-all-folks ------------------------------------- Sample Runs for Second Step % getint_test 8 77 100 101 7777 [CTRL-D] Base: 8 Next integer: 63 Next integer: 64 Next integer: 65 Next integer: 4095 % getint_test 2 1000 1111 1010101 111111111 [CTRL-D] Base: 2 Next integer: 8 Next integer: 15 Next integer: 85 Next integer: 511 % getint_test 4 3333 123 11 1000 [CTRL-D] Next integer: 255 Next integer: 27 Next integer: 5 Next integer: 64 % getint_test 8 2222 38 Next integer: 1170 Next integer: 3 # just processing the 3 before 8 Not an integer # processing the 8**

/* getint.c: fetch next int */
#include <ctype.h>
#include <stdio.h>
#include "getint.h"
static int getch(void);
static void ungetch(int c);

/* getint:  get next integer from input into *pn */
int getint(int *pn) {
   int c, sign;

   while (isspace(c = getch()))   /* skip white space */
      ;
   if (!isdigit(c) && c != EOF && c != '+' && c != '-'){
      ungetch(c);  /* it is not a number */
      return 0;
   }
   sign = (c == '-') ? -1 : 1;
   if (c == '+' || c == '-')
      c = getch();
   for (*pn = 0; isdigit(c); c = getch())
      *pn = 10 * *pn + (c - '0');
   *pn *= sign;
   if (c != EOF)
      ungetch(c);
   return c;
}

/* getch and ungetch functions are also required. */
#include <stdio.h>
#define BUFSIZE 100
char buf[BUFSIZE];      /* buffer for ungetch */
int bufp = 0;           /* next free position in buf */

static int getch(void) {/*(possibly pushed-back) char */
   return (bufp > 0) ? buf[--bufp] : getchar();
}

static void ungetch(int c) {/*push char back on input */
   if (bufp >= BUFSIZE)
      printf("ungetch: too many characters\n");
   else
      buf[bufp++] = c;
}

/* getint.h: header for getint.c */
int getint(int *pn);
-------------------------------------
Sample Run for First Step
% cat rec4_input.txt
53  314159  -453
0  0123
% cc -o getint getint.c getint_test.c
% getint_test < rec4_input.txt
Next integer: 53
Next integer: 314159
Next integer: -453
Next integer: 0
Next integer: 123
Th-th-th-th-that's-all-folks
-------------------------------------
Sample Runs for Second Step
% getint_test  8
77    100   101   7777  [CTRL-D]
Base: 8
Next integer: 63
Next integer: 64
Next integer: 65
Next integer: 4095
% getint_test  2
1000  1111 1010101 111111111 [CTRL-D]
Base: 2
Next integer: 8
Next integer: 15
Next integer: 85
Next integer: 511
% getint_test 4
3333  123  11  1000 [CTRL-D]
Next integer: 255
Next integer: 27
Next integer: 5
Next integer: 64
% getint_test 8
2222  38
Next integer: 1170
Next integer: 3  # just processing the 3 before 8 
Not an integer   # processing the 8

This C code comes from the book The C Programming Language, by Kernighan and Ritchie. The only function that can be called from this file (the only one with a prototype in the header file) is getint(). The other two functions, getch() and ungetch() are "helper" functions, defined to be static, and so are not accessible from outside the file. None of the data members are declared extern, so they also are not accessible from the outside.

The function getint() must be called with the address of an int as its actual parameter. The function attempts to read an int from the standard input (called stdin), reading character-at-a-time, and the value of this integer should "pop" into the integer variable whose address was provided. The function returns one of three values:

EOF (actually a -1), indicating the end-of-file on reading input,
The number 0, indicating a failure to read an integer, or
A positive value, indicating success in reading an integer.

The "helper" functions, getch() and ungetch() are similar to the C library functions: getchar() and ungetc(), except the standard "push-back' function only allows one to push a single character back into the input, where the next getchar() will read it. The ungetch() function, in contrast, allows you to push back as many as 100 characters.

First Step for the Recitation: First create a file with a main function whose purpose is to exercise the function getint(). This file should include the header file getint.h. You should repeatedly call the function to fetch integers from input until end-of-file, and print their values, using printf. The table above (upper right) shows a run of such a program, although your run doesn't have to look exactly the same as this one.

Second Step: Use a number base between 2 and 10 (inclusive) on input: Typically one would use 2, 8, or 10, but any base between 2 and 10 (inclusive) should be accepted by your program. This relatively small change still requires working on several issues. Sample runs are show in the second part of table above (at the lower right).

Command-line arguments: The base to be used should be provided as a command-line argument, a decimal number. The following program illustrates the use of a single command line argument. We will study this more in the next few weeks:

Command-line argument, with execution
/* clarg.c: command-line argument / #include <stdio.h> int main(int argc, char argv[]) { int base; if (argc != 2) { printf("Usage: clarg base\n"); exit(1); } base = atoi(argv[1]); printf("Command-line argument: %i\n", base); }	% cc -o clarg clarg.c % clarg Usage: clarg base % clarg 8 Command-line argument: 8

Command-line argument, with execution

/* clarg.c: command-line argument */
#include <stdio.h>

int main(int argc, char *argv[]) {
   int base;
   if (argc != 2) {
      printf("Usage: clarg base\n");
      exit(1);
   }
   base = atoi(argv[1]);
   printf("Command-line argument: %i\n",
      base);
}

% cc -o clarg clarg.c
% clarg
Usage: clarg base
% clarg 8
Command-line argument: 8

Changes to the getint function: getint should now have a second argument, an ordinary int, not a pointer, that is the number base to use. The header file must be changed also.

Inside this function, where a 10 appears, of course now the actual base must be used.

Finally, to make the program work perfectly, you should use your own function for the function isdigit(c), so that it will return 1 (true) only in case of an input digit from 0 to base-1 inclusive, where base is the number base on the command line. The final run above shows using a number base of 8, and trying to read a digit 8, which of course should not be accepted, and it is not.

Third Step: Use an arbitrary number base on input: For this third step, you are to handle an arbitrary input number base, any integer number base from 2 to 36 inclusive. Here we need to represent "digits" from 10 to 35, and one usually uses the letters from a to z for this.

Further changes inside the getint function: There are two remaining problems:

isdigit(c) for an integer representing a char should now check for the correct range corresponding to the base (thus with base 12 you would be checking for one of 0123456789ab, while with base 16 you would be checking for one of 0123456789abcdef, and so forth.
You need to convert the code for a character to the integer value of the character, which is done in the program above just using the expression: (c - '0'). Now we need a more powerful technique.

I wrote a function with outline as follows, although of course there are other ways to do this):

Lookup function, with necessary array
char a[] = {'0','1','2','3','4','5','6','7','8','9', 'a','b','c','d','e','f','g','h','i','j', 'k','l','m','n','o','p','q','r','s','t', 'u','v','w','x','y','z'}; static int lookup(int ch, int base) { /* look up ch in the array a from index 0 to base-1, returning the index if found, and a -1 otherwise */ }

Lookup function, with necessary array

char a[] = {'0','1','2','3','4','5','6','7','8','9',
            'a','b','c','d','e','f','g','h','i','j',
            'k','l','m','n','o','p','q','r','s','t',
            'u','v','w','x','y','z'};
static int lookup(int ch, int base) {
   /* look up ch in the array a from index 0 to base-1,
     returning the index if found, and a -1 otherwise */
}

I used this function for both of the two purposes above. An additional advantage is that this function doesn't depend on the Ascii code, but would work for any character code. (Later we will get a better way to define the array a.) Here is a set of sample runs using number bases bigger than 10. (Of course you should test that bases 2 through 10 are still working.)

Possible output for Third Step
% getint_test 16 100 ff ffff 10101 [CTRL-D] Base: 16 Next integer: 256 Next integer: 255 Next integer: 65535 Next integer: 65793 % getint_test 36 10 z zz 11 100 [CTRL-D] Base: 36 Next integer: 36 Next integer: 35 Next integer: 1295 Next integer: 37 Next integer: 1296 % getint_test 16 100 fg Next integer: 256 Next integer: 15 # just processing the f before g Not an integer # processing the g

Possible output for Third Step

% getint_test  16
100  ff  ffff  10101  [CTRL-D]
Base: 16
Next integer: 256
Next integer: 255
Next integer: 65535
Next integer: 65793
% getint_test  36
10  z  zz  11  100 [CTRL-D]
Base: 36
Next integer: 36
Next integer: 35
Next integer: 1295
Next integer: 37
Next integer: 1296
% getint_test 16
100  fg
Next integer: 256
Next integer: 15  # just processing the f before g 
Not an integer    # processing the g

Fourth Step: Use an arbitrary number base on Output: For this final step, add another public (that is, not static) function to the file getint.c, call it putint(), with prototype:

void putint(int n, int base);

Of course the prototype goes into the header file: getint.h. With this function you can print an integer to whatever base you want. Here is a recursive function that prints its integer argument base 10. (Normally I would write such a function to return a string instead of directly writing, so that one could do whatever was desired with the string.)

Print base 10
#include <stdio.h> void putint(int n) { if (n > 0) { putint(n/10); putchar(n%10 + '0'); } } int main() { int n; scanf("%i", &n); putint(n); putchar('\n'); }	% cc -o putint putint.c % putint 314159 314159

Print base 10

#include <stdio.h>
void putint(int n) {
   if (n > 0) {
      putint(n/10);
      putchar(n%10 + '0');
   }
}

int main() {
   int n;
   scanf("%i", &n);
   putint(n);
   putchar('\n');
}

% cc -o putint putint.c
% putint
314159
314159

To make this work for an arbitrary base, you need to add an extra parameter, but more importantly, you can make good use of the same array a defined above. To demonstrate this final step, run most of the same data as for Steps 2 and 3 above, but print the answers base 2, 8, 10, 16, and 36, as shown below:

Possible output for Fourth Step
% getint_test 8 77 100 101 7777 Base: 8 Next int (base), 111111(2), 77(8), 63(10), 3f(16), 1r(36) Next int (base), 1000000(2), 100(8), 64(10), 40(16), 1s(36) Next int (base), 1000001(2), 101(8), 65(10), 41(16), 1t(36) Next int (base), 111111111111(2), 7777(8), 4095(10), fff(16), 35r(36) % getint_test 2 1000 1111 1010101 111111111 Base: 2 Next int (base), 1000(2), 10(8), 8(10), 8(16), 8(36) Next int (base), 1111(2), 17(8), 15(10), f(16), f(36) Next int (base), 1010101(2), 125(8), 85(10), 55(16), 2d(36) Next int (base), 111111111(2), 777(8), 511(10), 1ff(16), e7(36) % getint_test 16 100 ff ffff 10101 Base: 16 Next int (base), 100000000(2), 400(8), 256(10), 100(16), 74(36) Next int (base), 11111111(2), 377(8), 255(10), ff(16), 73(36) Next int (base), 1111111111111111(2), 177777(8), 65535(10), ffff(16), 1ekf(36) Next int (base), 10000000100000001(2), 200401(8), 65793(10), 10101(16), 1erl(36) % getint_test 36 10 z zz 11 100 Base: 36 Next int (base), 100100(2), 44(8), 36(10), 24(16), 10(36) Next int (base), 100011(2), 43(8), 35(10), 23(16), z(36) Next int (base), 10100001111(2), 2417(8), 1295(10), 50f(16), zz(36) Next int (base), 100101(2), 45(8), 37(10), 25(16), 11(36) Next int (base), 10100010000(2), 2420(8), 1296(10), 510(16), 100(36)

Possible output for Fourth Step

% getint_test 8
77    100   101   7777
Base: 8
Next int (base), 111111(2), 77(8), 63(10), 3f(16), 1r(36)
Next int (base), 1000000(2), 100(8), 64(10), 40(16), 1s(36)
Next int (base), 1000001(2), 101(8), 65(10), 41(16), 1t(36)
Next int (base), 111111111111(2), 7777(8), 4095(10), fff(16), 35r(36)
% getint_test 2
1000  1111 1010101 111111111
Base: 2
Next int (base), 1000(2), 10(8), 8(10), 8(16), 8(36)
Next int (base), 1111(2), 17(8), 15(10), f(16), f(36)
Next int (base), 1010101(2), 125(8), 85(10), 55(16), 2d(36)
Next int (base), 111111111(2), 777(8), 511(10), 1ff(16), e7(36)
% getint_test 16
100  ff  ffff  10101
Base: 16
Next int (base), 100000000(2), 400(8), 256(10), 100(16), 74(36)
Next int (base), 11111111(2), 377(8), 255(10), ff(16), 73(36)
Next int (base), 1111111111111111(2), 177777(8), 65535(10), ffff(16), 1ekf(36)
Next int (base), 10000000100000001(2), 200401(8), 65793(10), 10101(16), 1erl(36)

% getint_test 36
10  z  zz  11  100
Base: 36
Next int (base), 100100(2), 44(8), 36(10), 24(16), 10(36)
Next int (base), 100011(2), 43(8), 35(10), 23(16), z(36)
Next int (base), 10100001111(2), 2417(8), 1295(10), 50f(16), zz(36)
Next int (base), 100101(2), 45(8), 37(10), 25(16), 11(36)
Next int (base), 10100010000(2), 2420(8), 1296(10), 510(16), 100(36)

What you should submit: Refer to the submissions directions and to deadlines at the top of this page. The text file that you submit should first have Your Name, the Course Number, and the Recitation Number. The rest of the file should have the following in it, in the order below, and clearly labeled, including at the beginning the appropriate item letters: a, b, c, etc.

Contents of email submission for Recitation 1:
Last Name, First Name; Course Number; Recitation Number.
a. Results for Step 1, namely the source file getint_test.c and results of a run as shown at the top right in the first table above (results of a run using the input file rec4_input.txt).
b. Results for Step 2, namely the source files getint.c and getint_test.c, followed by results of runs as shown at the bottom right in the first table above (runs with bases 8, 2, 4, and 8 (with final error).
c. Results for Step 3, namely the source files getint.c and getint_test.c, followed by results of runs as shown in the table above labeled "Possible output for Third Step" (runs with bases 16, 36, and 16 (with final error).
d. Results for Step 4, namely the source files getint.c and getint_test.c, followed by results of runs as shown in the table above labeled "Possible output for Fourth Step" (a number of runs with no errors).

Revision date: 2005-02-05. (Please use ISO 8601, the International Standard.)