C structs

A struct in C is a compound data type made up of one or more fields. A struct is appropriate to use when you want to describe some entity that can be uniquely characterized by specifying a set of data values.

An example of a situation in which it is natural to define a struct is a program that has to work with points in 2. Each point is described by an x coordinate and a y coordinate. The point struct allows us to bundle these two related pieces of data together into a single entity.

typedef struct
{
  float x;
  float y;
} point;

This structure definition has to appear before the first use of the point data type in the program, so struct definitions typically appear at the top of source code files before any function definitions.

To declare a variable of type point we use the usual syntax for declaring variables:

point p;

Since a point is really a bundle of two coordinates that travel around together we work with a point by accessing the x and y fields that make up the point. We use the following syntax to access the fields of a point struct:

p.x = 2.5;
p.y = 3.0;

We can pass points as parameters to a function just as we would any other data type. Here is a function definition for a function that computes the distance from the origin to a point p:

float distance(point p)
{
  return sqrt(p.x*p.x + p.y*p.y);
}

We can also create arrays of points:

point A[100]; // A is an array of 100 points

To access the fields of a point stored in an array we use the syntax

A[0].x = 2.0;
A[0].y = 3.5;

Example Program

The following example program uses the point struct to solve a simple problem. The file "points.txt" contains a list of points. The program reads these points into an array and then determines the radius of the smallest circle centered at the origin that would just contain the points.

#include <stdio.h>
#include <math.h>

typedef struct
{
  float x;
  float y;
} point;

// Compute the distance from the origin to
// the given point
float distance(point p)
{
  return sqrt(p.x*p.x + p.y*p.y);
}

// Read up to N points from the file input.
// Return a count of how many points were read.
int readPoints(point A[],int N,FILE *input)
{
  int n;
  float xCoord, yCoord;

  n = 0;
  while(n < N && !feof(input))
  {
    fscanf(input,"%f %f",&xCoord,&yCoord);
    A[n].x = xCoord;
    A[n].y = yCoord;
    n++;
  }

  return n;
}

int main (int argc, const char * argv[]) 
{ 
  point P[1000];
  int k, count;
  float largest;
  FILE *input;

  // Read the points from the file
  input = fopen("points.txt","r");
  count = readPoints(P,1000,input);
  fclose(input);

  // Find the point that is farthest from the origin.
  largest = 0.0;
  for(k = 0;k < count;k++)
    if(distance(P[k]) > largest)
      largest = distance(P[k]);

  // Print results.
  printf("The points will fit in a circle ");
  printf("of radius %f.\n",largest);

  return 0;
}

The complex data type

A little further down in these notes I am going to show an example program that does a calculation with complex numbers. That program and most of the example code shown below comes from the text Introduction to Scientific Programming by Joseph L. Zachary.

In preparation for the example we will need to create a struct definition for the complex data type.

typedef struct {
  float real; // Real component of complex number
  float imag; // Imaginary component of complex number
} complex;

One complication of creating a new data type is that many operations that are defined for simple data types such as int and float are not defined for structs. For example, the following code will not compile:

complex a,b,c;
a.real = 1.0;
a.imag = -2.0;
b.real = 2.0;
b.imag = -1.0;
c = a*b; // Error - * is not defined for type complex

The only way to get this code to work is to define a function that does multiplication for complex numbers.

complex mul (complex c1, complex c2)
{
  complex result;
  result.real = c1.real*c2.real - c1.imag*c2.imag;
  result.imag = c1.real*c2.imag + c1.imag*c2.real;
  return result;
}

With this function defined we can multiply two complex numbers:

complex a,b,c;
a.real = 1.0;
a.imag = -2.0;
b.real = 2.0;
b.imag = -1.0;
c = mul(a,b);

Similarly, we will need to write function definitions for addition, subtraction, and division.

Another convenience function we can create is a function for initializing complex numbers.

complex make (float real, float imaginary)
{
  complex c;
  c.real = real;
  c.imag = imaginary;
  return c;
}

With this function defined we can further simplify our example.

complex a,b,c;
a = make(1.0,-2.0);
b = make(2.0,-1.0);
c = mul(a,b);

Multiple source code files

Since the complex type we defined above is going to require that we define a set of associated functions for doing common operations with complex numbers, any program we write to work with complex numbers is going to contain a lot of function definitions. In an effort to reduce the clutter in our main source code file we are going to move the function definitions for these functions to a separate source code file named complex.c. This will also make it easier to reuse this code in other projects: we can take the complex.c source code file and drop it into another project to gain easy access to these functions.

Whenever we create a source code file containing a set of functions we will also need to create an associated header file. The header file complex.h contains the structure definition for the complex data type and a list of function prototypes for the functions we will define in complex.c. A function prototype is essentially a function definition without a function body. Function prototypes serve to alert the compiler to the fact that definitions for the associated functions will appear in another file in the project.

Here is the code for Zachary's complex.h header file.

/* This is "complex.h", written to accompany Introduction to
   Scientific Programming by Joseph L. Zachary. */

/* This file declares the interface to a complex number ADT. */

/* This structure is used as the representation of the complex
   number ADT.  The details of the representation (i.e., the
   fields of the structure) are relevant only to "complex.c",
   which implements the ADT.  All other programs should
   manipulate complex numbers only with the interface functions
   declared below. */

typedef struct {
  float real;      /* Real component of complex number */
  float imag;      /* Imaginary component of complex number */
} complex;

/* Returns the complex number whose real part is "real" and whose
   imaginary part is "imaginary". */
complex make (float real, float imaginary);

/* Reads a complex number from the keyboard and returns it.  The
   number should be entered in the form a+bi or a-bi, where a and
   b stand for arbitrary floats. */
complex read (void);

/* Writes "c" to the display in the form a+bi or a-bi, where a and
   b stand for arbitrary floats. */
void write (complex c);

/* Returns c1+c2. */
complex add (complex c1, complex c2);

/* Returns c1-c2. */
complex sub (complex c1, complex c2);

/* Returns c1*c2. */
complex mul (complex c1, complex c2);

/* Returns c1/c2. */
complex div (complex c1, complex c2);

/* Returns |c|. */
float absval (complex c);

Here now is the code for the complex.c source file, which contains the function definitions for all of the functions declared in complex.h. Note that complex.c has to include complex.h to gain access to the structure definition for the complex data type.

/* This is "complex.c", written to accompany Introduction to
   Scientific Programming by Joseph L. Zachary. */

/* This file implements the complex number ADT whose interface
   appears in "complex.h". */

#include <stdio.h>
#include <math.h>
#include "complex.h"

/* Returns the complex number whose real part is "real" and whose
   imaginary part is "imaginary". */
complex make (float real, float imaginary)
{
  complex c;
  c.real = real;
  c.imag = imaginary;
  return c;
}

/* Reads a complex number from the keyboard and returns it.  The
   number should be entered in the form a+bi or a-bi, where a and
   b stand for arbitrary floats. */
complex read (void)
{
  complex c;
  scanf("%f%fi", &c.real, &c.imag);
  return c;
}

/* Writes "c" to the display in the form a+bi or a-bi, where a and
   b stand for arbitrary floats. */
void write (complex c)
{
  printf("%f%+fi", c.real, c.imag);
}

/* Returns c1+c2. */
complex add (complex c1, complex c2)
{
  complex result;
  result.real = c1.real + c2.real;
  result.imag = c1.imag + c2.imag;
  return result;
}

/* Returns c1-c2. */
complex sub (complex c1, complex c2)
{
  complex result;
  result.real = c1.real - c2.real;
  result.imag = c1.imag - c2.imag;
  return result;
}

/* Returns c1*c2. */
complex mul (complex c1, complex c2)
{
  complex result;
  result.real = c1.real*c2.real - c1.imag*c2.imag;
  result.imag = c1.real*c2.imag + c1.imag*c2.real;
  return result;
}

/* Returns c1/c2. */
complex div (complex c1, complex c2)
{
  complex result;
  float denom;

  denom = c2.real*c2.real + c2.imag*c2.imag;
  result.real = (c1.real*c2.real + c1.imag*c2.imag) /
                   denom;
  result.imag = (c1.imag*c2.real - c1.real*c2.imag) /
                   denom;

  return result;
}

/* Returns |c|. */
float absval (complex c) {
  return sqrt(c.real*c.real + c.imag*c.imag);
}

Any project that we create that makes use of these functions will have to contain the two source files complex.h and complex.c. Any other source file in the project that wants to use the functions defined in complex.c will have to include complex.h.

With a full set of functions available to work with complex numbers Zachary then shows an example program that uses these functions to find a complex root of a second degree polynomial by Newton's method.

/* This is "newton9.c", written to accompany Introduction to
   Scientific Programming by Joseph L. Zachary. */

/* Together with "complex.h" and "complex.c", this is an
   implementation and test driver for Newton's method with complex
   numbers as described in Chapter 16 of the text. */

#include <stdio.h>
#include <math.h>
#include "complex.h"

/* This is x^2 - 6x + 13, whose root we seek. */
complex f (complex x)
{
  complex c6, c13;

  c6 = make(6,0);
  c13 = make(13, 0);

  return(add(sub(mul(x,x), mul(c6,x)), c13));
}

/* This is 2x - 6, which is the first derivative of f. */
complex fprime (complex x)
{
  complex c2, c6;

  c2 = make(2,0);
  c6 = make(6,0);

  return(sub(mul(c2,x), c6));
}

/* An implementation of Newton's method that finds complex roots.
   It improves the guess "g0" for the root of "f" until the
   absolute value of the difference between two successive
   guesses becomes small relative to the first of the two
   guesses.  It then returns the improved guess. */
complex newton (complex g0)
{
  complex oldg0; /* The value of g0 during the previous           
                    iteration. */

  do {
    oldg0 = g0;
    g0 = sub(g0, div(f(g0), fprime(g0)));
  }
  while (absval(div(sub(g0, oldg0), g0)) > 1e-10);

  return g0;
}

/* A test driver that uses "newton" to find a complex root
   of "f" given a guess read from the keyboard. */
int main (int argc, const char * argv[]) 
{
  complex guess, root;

  printf("Please enter an initial guess: ");
  guess = read();
  root = newton(guess);
  printf("An approximate root is ");
  write(root);
  printf("\n");

  return 0;
}

Programming Assignment

For this assignment we are going to define a structure type that can be used to represent rational numbers.

typedef struct {
  int numerator;
  int denominator;
} rational;

We are going to be doing some mathematical computations with rational numbers, so you will have to construct a set of functions that allow you to do arithmetic with rationals. In addition, your program should make use of the following make() function:

rational make (int num, int denom)
{
  int a,b,temp, gcd;
  rational result;
  // Compute the gcd of num and denom
  a = abs(num);
  b = abs(denom);
  if(a < b) {
    temp = a;
    a = b;
    b = temp;
  }
  while(b > 0) {
    temp = a%b;
    a = b;
    b = temp;
  }
  gcd = a;
  
  result.numerator = num/gcd;
  result.denominator = denom/gcd;
  return result;
}

To check whether or not your rational arithmetic functions are working correctly, write a program to compute two rational approximations for π. One way to estimate the value of π is to use this formula, which was discovered by Leibniz:

Another method is due to Wallis:

As you increase the number of terms in each of these approximations you will end up generating a sequence of rational numbers that approach π. Write a program that uses these two methods to construct two sequences of rational approximations for π. Both sequences will start with 4. On each round, compute and print the next rational number in the sequence and print that rational number as a double as well through the use of this function:

double toReal(rational r) {
  double n = r.numerator;
  return n/r.denominator;
}