Laboratory: An Introduction to Arrays

Summary: This lab reviews some basics of the C language, particularly as they pertain to arrays and functions.

Citation: Much of this lab is closely based on chapter 1 of

Kernighan, Brian W. and Ritchie, Dennis M. (1988). The C Programming Language, Second Edition: ANSI C. Englewood Cliffs, NJ: Prentice-Hall. ISBN: 0-13-1110362-8.

Contents:

• Exercises
  • Exercise 0: Preparation
  • Exercise 1: Counting Characters
  • Exercise 2: Splinting
  • Exercise 3: Further Reflection
  • Exercise 4: Counting Punctuation
  • Exercise 5: Counting Letters
  • Exercise 6: Functions
  • Exercise 7: Exponentiation
  • Exercise 8: Prototypes
  • Exercise 9: Separate Compilation
  • Exercise 10: More Fun with Make
  • Exercise 11: Updating power
  • Exercise 12: A More Efficient Exponentiation Procedure
• If You Finish Early

Exercises

Exercise 0: Preparation

Create a new directory for this laboratory (e.g., intro-arrays. Initially, this directory should be empty.

Exercise 1: Counting Characters

Here is a simple C program that counts various kinds of input characters, based on a similar program from page 12 of K&R. It has been extended from that program with my incredibly verbose commenting style.

/*
 * File:
 *   countstuff.c
 * Authors:
 *   Brian W. Kernighan
 *   Dennis M. Ritchie
 *   Samuel A. Rebelsky
 * Version:
 *   1.1 of 31 January 2003
 * Summary:
 *   Counts various kinds of input characters taken from standard input.
 *   Currently counts digit characters ('0' ... '9'), white space, and
 *     "everything else".
 * Citation:
 *   Closely based on an unnamed program on page 22 of K&R.
 */

/* +---------+--------------------------------------------------------
 * | Headers |
 * +---------+
 */

#include <stdio.h>
#include <stdlib.h>


/* +------+-----------------------------------------------------------
 * | Main |
 * +------+
 */
main()
{
  int ch;	/* Temporary variable for input characters. */
  int i;	/* Counter variable for loops. */
  int nwhite;	/* The number of whitespace characters. */
  int ndigit[10];
		/* The number of each digit character.  ndigit[0]
		 * contains the number of '0' characters, ndigit[1]
		 * contains the number of '1' characters, and so
		 * on and so forth.
		 */
  int nother;	/* The number of "other" characters. */

  /* Initialize key variables. */
  nwhite = nother = 0;
  for (i = 0; i < 10; ++i)
    ndigit[i] = 0;
  
  /* Read input and count characters. */
  while ((ch = getchar()) != EOF) {
    /* If it's a digit, increment the appropriate counter. */
    if ((ch >= '0') && (ch <= '9'))
      ++ndigit[ch-'0'];
    /* If it's a whitespace character (space, newline, tab),
     * increment the whitespace counter. */
    else if ((ch == ' ') || (ch == '\n') || (ch == '\t'))
      ++nwhite;
    /* Otherwise, it's something else. */
    else
      ++nother;
  } /* while */

  /* Summarize data. */
  printf("digits: ");
  for (i = 0; i < 10; ++i)
    printf("'%c'=%d ", '0'+i, ndigit[i]);
  printf("\n");
  printf("white space = %d\n", nwhite);
  printf("other = %d\n", nother);

  /* Clean up. */
  exit(EXIT_SUCCESS);
} /* main */

a. Save this code in a file named countstuff.c

b. Compile the program, making sure to call the executable countstuff.

c. Run the program, typing information on standard input. (You end the input by typing Control-D.)

d. Run the program using itself as input with

% countstuff < countstuff.c

e. What do you expect to happen if you run countstuff on its executable, as in the following?

% countstuff < countstuff

f. Verify your answer to the prior question by experimentation.

Exercise 2: Splinting

Check the program with splint and correct any potential problems it reports.

Exercise 3: Further Reflection

a. What does the following line do? Does that suggest anything about the associativity of the = operation?

nwhite = nother = 0;

b. What does the following line do? What does that suggest about the relationship of characters and numbers?

++ndigit[ch-'0'];

c. Summarize the changes I made to the program on p. 22 of K&R and suggest why I made each change.

Exercise 4: Counting Punctuation

Extend countstuff.c to count punctuation symbols (as a group, as in the case of whitespace).

Exercise 5: Counting Letters

Extend countstuff.c to report on the frequencies of the different letters in the input.

Warning: You will need to find a way to count 'a' and 'A' as the same letter.

Exercise 6: Functions

Rather than using the

if ((ch == ' ') || (ch == '\n') || (ch == '\t'))

it might be clearer to add an is_whitespace procedure and use a call to that procedure instead.

Make that change.

Exercise 7: Exponentiation

Here's a slight variant of the program from page 26 of K&R.

/*
 * File:
 *   testpower.c
 * Authors:
 *   Brian W. Kernighan
 *   Dennis M. Ritchie
 *   Samuel A. Rebelsky
 * Version:
 *   1.1 of 31 January 2003
 * Summary:
 *   Print out various tests of the power function.
 * Citation:
 *   Closely based on an unnamed program on page 24 of K&R.
 */

/* +---------+--------------------------------------------------------
 * | Headers |
 * +---------+
 */

#include <stdio.h>
#include <stdlib.h>


/* +-----------------+------------------------------------------------
 * | Predeclarations |
 * +-----------------+
 */

/*
 * Procedure:
 *   power
 * Parameters:
 *   base, an integer
 *   expt, an integer
 * Purpose:
 *   Computes base^expt
 * Produces:
 *   result, an integer
 * Preconditions:
 *   expt is non-negative
 * Postconditions:
 *   result = base^expt
 *   That is, result = base*base* ... * base, with expt copies of base.
 */
int power(int base, int expt);


/* +------+-----------------------------------------------------------
 * | Main |
 * +------+
 */

main()
{
  int i;	/* Counter variable for for loops. */
  for (i = 0; i < 10; ++i) 
    printf("i: %d | 2^%d: %6d | -3^%d: %6d\n", 
           i, i, power(2,i), i, power(-3,i));
  exit(EXIT_SUCCESS);
} /* main */

/* +------------+-----------------------------------------------------
 * | Procedures |
 * +------------+
 */

/* Compute base^expt. */
int power(int base, int expt)
{
  int result = 1;	/* Result, both intermediate and final. */
  int i;		/* Counter variable for loops. */

  for (i = 1; i <= expt; ++i)
    result *= base;

  return result;
} /* power(int,int) */

a. Save this program in the file (say testpower.c).

b. Check it with splint. Fix any errors it reports.

c. Compile it and save the executable as power.

d. Run it and observe the output.

Exercise 8: Prototypes

a. What do you expect to happen if you remove the prototype for power?

b. Verify your answer through experimentation.

Exercise 9: Separate Compilation

a. Create a file, power.h that contains only the declaration of power. (The declaration is the prototype.) Remove the declaration from testpower.c.

b. Create a file, power.c that contains the definition of power. Remove that definition from testpower.c.

c. Add the following to power.c and testpower.c. #include "power.h"

d. Run splint on power.c and testpower.c Correct any errors it reports.

e. What do you expect to happen if you try to compile power.c using the technique that you've used previously?

f. Verify your answer experimentally.

g. What do you expect to happen if you try to compile testpower.c using the technique that you've used previously?

h. Verify your answer experimentally.

i. Create a makefile containing the following lines:

testpower: testpower.o power.o
	cc -o testpower testpower.o power.o

j. Remove testpower and type

% make testpower

What happens?

k. Try running testpower

l. What do your experiences on this exercise suggest?

Exercise 10: More Fun with Make

a. Add the following two lines to your Makefile

testpower.o: power.h
power.o: power.h

b. Run make testpower. What happens? Is that what you expected?

c. Change power.h (e.g., add an introductory comment).

d. Run make testpower. What happens? Is that what you expected?

e. What do your experiences in this exercise suggest?

Exercise 11: Updating power

a. Rewrite power in power.c so that it is recursive rather than iterative.

b. Try make testpower and observe what happens. What do your results suggest?

Exercise 12: A More Efficient Exponentiation Procedure

Here's a different way to think about exponentiation:

x⁰ = 1 x^2k = (x^k)² xⁿ⁺¹ = x*xⁿ for odd n

Rewrite power recursively to take advantage of this improvement.

If You Finish Early

Write a program to print a histogram of the lengths of words in its input.

Rewrite power iteratively to take advantage of the improvement mentioned earlier.