5: Arrays

5.1: Sequences as a model of linear data structures

5.1.1: The length of a sequence

5.1.2: Accessing an element of a sequence

5.1.3: Updating an element of a sequence

5.1.4: The concatenation of two sequences

5.1.5: The subsequence

5.2: Sequences as arrays in SML

5.2.1: Creating an SML array

SML array type
(* array : int * 'a -> 'a array *)
SML tabulate type
(* tabulate : int * (int->'a) -> 'a array *)

5.2.2: The length of an SML array

SML length type
(* length : 'a array -> int *)

5.2.3: Accessing an element of an SML array

SML sub type
(* sub : 'a array * int -> 'a *)

5.2.4: Updating an element of an SML array

SML upd
(* upd : 'a array * int * 'a -> 'a array *)
fun upd(s,k,v) = let
                    val n   = length(s)
                    fun f i = if i = k
                                 then v
                                 else sub(s,i)
                 in
                    tabulate(n,f)
                 end ;

5.2.5: Destructive updates in SML

SML update
(* update : 'a array * int * 'a -> unit *)

5.3: Sequences as arrays in C

5.3.1: Declaring a C array

C uninitialised array declaration
t a[n] ;
C initialised array declaration
t a[n] = { v_0, v_1, ... } ;
C initialised array declaration without bound
t a[] = { v_0, v_1, ... } ;
C array argument type
t a[]

5.3.2: Accessing an element of a C array

C array subscript
a[e]

5.4: Basic array operations : Arithmetic mean

SML mean
(* mean : real array -> real *)
fun mean s
    = let
         val n = length s ;
         fun add_element sum i = sum + sub(s,i)
      in
         foldl add_element 0.0 (0 -- n-1) / real(n)
      end ;
C nearly complete mean
double mean( double s[] ) {
  int n = /* length s */ ;
  int i ;
  double sum = 0.0 ;
  for( i=0 ; i < n ; i++ ) {
    sum = sum + s[i] ;
  }
  return sum/n ;
}
C mean declaration
double s[]
C mean
double mean( double s[], int n ) {
  int i ;
  double sum = 0.0 ;
  for( i=0 ; i < n ; i++ ) {
    sum = sum + s[i] ;
  }
  return sum/n ;
}
C for loop of mean
for( i=0 ; i < n ; i++ ) {
C for loop 0
for( i = 0 ; i < n ; i++ )
C for loop 1
for( i = 1 ; i <= n  ; i++ )
C mean main
int main( void ) {
  /* constant 4 used in the next line */
  double data[4] = { 55.0, 90.0, 83.0, 74.0 } ;
  /* same constant 4 used in the next line */
  printf( "%f\n", mean( data, 4 ) ) ;
  return 0 ;
}
C array declaration
double data[ 4 ] = { 55.0, 90.0, 83.0, 74.0 } ;
C incorrect array declaration
int main( void ) {
  const int array_length = 4 ;
  double data[array_length] = { 55.0, 90.0, 83.0, 74.0 } ;
  printf( "%f\n", mean( data, array_length ) ) ;
  return 0 ;
}
C correct compile time constant declaration
#define array_length 4

int main( void ) {
  double data[array_length] = { 55.0, 90.0, 83.0, 74.0 } ;
  printf( "%f\n", mean( data, array_length ) ) ;
  return 0 ;
}

5.5: Strings

SML string length
(* strlen : string -> int *)
fun strlen a = size a ;
C function that determines the string length
int strlen( char string[] ) {
  int i=0 ;
  while( string[i] != '\0' ) {
    i++ ;
  }
  return i ;
}

5.5.1: Comparing strings

C include string
#include <string.h>
C strcmp example
strcmp( "monkey", "donkey" )     > 0,
strcmp( "multiple", "multiply" ) < 0,
strcmp( "multi", "multiple" )    < 0,
strcmp( "51", "3" )              > 0,
strcmp( "51", "312" )            > 0
C strncmp example
strncmp( "multiple", "multiply", 8 ) < 0,
strncmp( "multiple", "multiply", 7 ) == 0

5.5.2: Returning strings; more properties of arrays

C program to copy a string
void strcpy( char output[], char input[] ) {
  int i = 0 ;
  while( input[i] != '\0' ) {
    output[i] = input[i] ;
    i = i + 1 ;
  }
  output[i] = '\0' ;
}

int main( void ) {
  char s[ 10 ] ;
  strcpy( s, "Monkey" ) ;
  printf( "The string '%s'\n", s ) ;
  return 0 ;
}

5.5.3: An application of arrays and strings: argc and argv

C main void
int main( void )
C main argc argv
int main( int argc, char * argv[] )
C echo program
#include <stdlib.h>

int main( int argc, char * argv[] ) {
  int i ;
  printf("program %s", argv[0] ) ;
  for( i = 1; i < argc; i++ ) {
    printf(" %s", argv[i] ) ;
  }
  printf(".\n") ;
  return 0 ;
}
SH execute echo
a.out one two three !
C execute echo output
program a.out one two three !.

Answer to exercise 5.4

C card program
#include <stdlib.h>

typedef enum { false=0, true=1 } bool ;

#define n_number 4
#define n_card 3
typedef int deck[n_card][n_number] ;

const deck card = {{1,3,5,7},{2,3,6,7},{4,5,6,7}} ;

bool player_B( int c, int n ) {
  int i ;
  for( i = 0; i < n_number; i++ ) {
    if( card[c][i] == n ) {
      return true ;
    }
  }
  return false ;
}

int player_A( int secret ) {
  int guess = 0 ;
  int power = 1 ;
  int c ;
  for( c = 0; c < n_card; c++ ) {
    if( player_B( c, secret ) ) {
      guess += power ;
    }
    power *= 2 ;
  }
  return guess ;
}

int main( int argc, char * argv [] ) {
  if( argc != 2 ) {
    printf( "usage: %s [0..7]\n", argv[0] ) ;
  } else {
    int secret = argv[1][0] - '0' ;
    printf( "the secret number is: %d\n", player_A( secret ) ) ;
  }
  return 0 ;
}

5.6: Manipulating array bounds, bound checks

SML increment array element
(* inc : int array -> int -> int array *)
fun inc s i = upd(s,i,sub(s,i) + 1) ;
SML histogram
(* histogram : char array -> int -> int -> int array *)
fun histogram input l u
    = let
         val n = length input
         val empty = array(u - l + 1,0)
         fun tally hist i = inc hist (ord(sub(input,i))-l)
      in
         foldl tally empty (0 -- n-1)
      end ;
C incomplete histogram
void histogram( char input[], int hist[], int l, int u ) {
  int i ;
  /*  Make an empty histogram */
  for( i=0 ; input[i] != '\0' ; i++ ) {
    /*  Incorporate input[ i ] in the histogram */
  }
}
C histogram main
#define lower  'a'
#define upper  'z'
#define number (upper - lower + 1)

int main( void ) {
  int hstgrm[ number ] ;
  histogram( "abracadabra", hstgrm, lower, upper ) ;
  print_histogram( hstgrm, lower, upper ) ;
  return 0 ;
}
C Make an empty histogram
for( i=0 ; i<=u-l ; i++ ) {
  hist[i] = 0 ;
}
C body of histogram
hist = /* hist with one added at index input[i] */ ;
C increment hist at index
hist[ /* index */ ] ++ ;
C Incorporate input[ i ] in the histogram
if( input[i] < l || input[i] > u ) {
  abort() ;
}
hist[ input[i] - l ] ++ ;
C histogram program
#include <stdio.h>

void histogram( char input[], int hist[], int l, int u) {
  int i ;
  for( i=0 ; i<=u-l ; i++ ) {
    hist[i] = 0 ;                       /* Exercise \ref{exercise:bounds} */
  }
  for( i=0 ; input[i] != '\0' ; i++ ) {
    if( input[i] < l || input[i] > u ) {/* Exercise \ref{exercise:bounds} */
      abort() ;
    }
    hist[ input[i] - l ] ++ ;           /* Exercise \ref{exercise:bounds} */
  }
}

void print_xs( int n ) {
  int i ;
  for( i=0 ; i<n ; i++ ) {
    printf( "X" ) ;
  }
}

void print_histogram( int hist[], int l, int u ) {
  int i ;
  for( i=0 ; i<=u-l ; i++ ) {
    printf( "%c: %d ", i+l, hist[i] ) ; /* Exercise \ref{exercise:bounds} */
    print_xs( hist[i] ) ;               /* Exercise \ref{exercise:bounds} */
    printf( "\n" ) ;
  }
}

#define lower   'a'
#define upper   'z'
#define number  (upper - lower + 1)

int main( void ) {
  int hstgrm[ number ] ;
  histogram( "abracadabra", hstgrm, lower, upper ) ;
  print_histogram( hstgrm, lower, upper ) ;
  return 0 ;
}

5.7: Dynamic memory

5.7.1: The allocation of dynamic arrays

SML dynamic array type
type dynamic_array = int array * int * int ;
C dynamic array type
typedef struct {
  int *data ;           /* The zero-based array */
  int  lb ;             /* Lower bound of dynamic array */
  int  ub ;             /* Upper bound */
} dynamic_array ;
SML dynamic array allocation
(* array_alloc : int -> int -> dynamic_array *)
fun array_alloc l u = (array(u-l+1,0),l,u) ;
C dynamic array allocation
#include <stdlib.h>

dynamic_array array_alloc( int l, int u ) {
  dynamic_array da ;
  da.lb = l ;
  da.ub = u ;
  da.data = calloc( u - l + 1, sizeof( int ) ) ;
  if( da.data == NULL ) {
    abort() ;
  }
  return da ;
}
C sizeof int
sizeof( int )
C sizeof dynamic array
sizeof( dynamic_array )
C wrong dynamic array
dynamic_array x ; /* WRONG */
C right dynamic array
dynamic_array x = array_alloc( l, u ) ;

5.7.2: The extension of dynamic arrays

SML dynamic array extension
(* extend : dynamic_array -> int -> int -> dynamic_array *)
fun extend (old,old_lb,old_ub) l u
    = let
         fun copy new i = upd(new,i-l,sub(old,i-old_lb))
      in
         (foldl copy (array(u-l+1,0)) (old_lb -- old_ub),l,u)
      end ;
C dynamic array extension
dynamic_array extend( dynamic_array old, int l, int u ) {
  dynamic_array new = array_alloc( l, u ) ;
  int i ;
  for( i=old.lb ; i<=old.ub ; i++ ) {
    new.data[ i - l ] = old.data[ i - old.lb ] ;
  }
  return new ;
}
C dynamic array based histogram
dynamic_array histogram( char input[], int n ) {
  dynamic_array hist = array_alloc( input[0], input[0] ) ;
  int i ;
  for( i=0 ; i<n ; i++ ) {
    if( input[i] < hist.lb ) {
      hist = extend( hist, input[i], hist.ub ) ; /*Leak!*/
    } else if( input[i] > hist.ub ) {
      hist = extend( hist, hist.lb, input[i] ) ; /*Leak!*/
    }
    hist.data[ input[i] - hist.lb ] ++ ;
  }
  return hist ;
}
C plus-plus
hist.data[ input[i] - hist.lb ] ++ ;
C plus-plus in full
hist.data[ input[i] - hist.lb ] =
                      hist.data[ input[i] - hist.lb ] + 1 ;
C dynamic array based histogram program
int main( void ) {
  dynamic_array hist = histogram( "abracadabra", 11 ) ;
  int i ;
  for( i = hist.lb ; i <= hist.ub ; i++ ) {
    printf( "%c: %d\n", i, hist.data[ i - hist.lb ] ) ;
  }
  return 0 ;
}

5.7.3: The deallocation of dynamic arrays

C free hist.data
free( hist.data ) ;
C inner for loop of histogram without memory leak
dynamic_array new ;
if( input[i] < hist.lb ) {
  new = extend( hist, input[i], hist.ub ) ;
  free( hist.data ) ;
  hist = new ;
} else if( input[i] > hist.ub ) {
  new = extend( hist, hist.lb, input[i] ) ;
  free( hist.data ) ;
  hist = new ;
}
C extend so that it deallocates the data
dynamic_array extend( dynamic_array hist, int l, int u ) {
  dynamic_array new ;
  /* Make the new dynamic array */
  free( hist.data ) ;
  return new ;
}
C histogram with proper deallocation
void extend( dynamic_array * old, int l, int u ) {
  dynamic_array new = array_alloc( l, u ) ;
  int i ;
  for( i=old->lb ; i<=old->ub ; i++ ) {
    new.data[ i - l ] = old->data[ i - old->lb ] ;
  }
  free( old->data ) ;
  *old = new ;
}

dynamic_array histogram( char input[], int n ) {
  dynamic_array hist = array_alloc( input[0], input[0] ) ;
  int i ;
  for( i=0 ; i<n ; i++ ) {
    if( input[i] < hist.lb ) {
      extend( &hist, input[i], hist.ub ) ;
    } else if( input[i] > hist.ub ) {
      extend( &hist, hist.lb, input[i] ) ;
    }
    hist.data[ input[i] - hist.lb ] ++ ;
  }
  return hist ;
}

5.7.4: Explicit versus implicit memory management

5.7.5: Efficiency aspects of dynamic memory

5.8: Slicing arrays: pointer arithmetic

SML search string
(* search : char array -> char array -> int -> int *)
fun search w t i
    = if i > length t - length w
         then ~1
         else if slice (t,i,(i+length w-1)) = w
                 then i
                 else search w t (i+1)
C search string
int search( char *w, char *t, int i ) {
  while( true ) {
    if( i > strlen( t ) - strlen( w ) ) {
      return -1 ;
    } else if( /* slice of t equals w */ ) {
      return i ;
    } else {
      i = i + 1 ;
    }
  }
}
C array of 6 characters
int hello( void ) {
  char q[6] = "Hello" ;
  char * r = q+2 ;
  return r[0] == q[2] ;
}
slice of t equals w
strncmp( t+i, w, strlen(w) ) == 0
C efficient and complete search string
int search( char *w, char *t, int i ) {
  const int length_w = strlen( w ) ;
  const int length_t = strlen( t ) ;
  while( true ) {
    if( i > length_t - length_w ) {
      return -1 ;
    } else if( strncmp( t+i, w, length_w ) == 0 ) {
      return i ;
    } else {
      i = i + 1 ;
    }
  }
}
C efficient and complete search string main
int main( int argc, char *argv[] ) {
  if( argc != 3 ) {
    printf( "Wrong number of arguments\n" ) ;
    return 1 ;
  } else {
    if( search( argv[1], argv[2], 0 ) != -1 ) {
      printf( "%s occurs\n", argv[1] ) ;
    } else {
      printf( "%s does not occur\n", argv[1] ) ;
    }
    return 0 ;
  }
}
C strstr main
int main( int argc, char *argv[] ) {
  if( argc != 3 ) {
    printf( "Wrong number of arguments\n" ) ;
    return 1 ;
  } else {
    if( strstr( argv[2], argv[1] ) != NULL ) {
      printf( "%s occurs\n", argv[1] ) ;
    } else {
      printf( "%s does not occur\n", argv[1] ) ;
    }
    return 0 ;
  }
}
C example use of strstr
int main( void ) {
  char *q = "What a wonderful world!" ;
  char *r = strstr( q, "wonderful" ) ;
  char *s = strstr( q, "world" ) ;
  printf("Indexes %d %d, diff %d\n", r-q, s-q, s-r ) ;
  return 0 ;
}
C function to copy a string, no bound checks
void copystring( char *out, char *in ) {
  while( *out++ = *in++ ) {
    /* Nothing more to do */
  }
}

5.9: Combining arrays and structures

SML database
type employee  = (string * real * int * int array) ;
type personnel = employee array ;

(* mean : int array -> real *)
fun mean s
    = let
         val n = length s
         fun add_element sum i = sum + real(sub(s,i))
      in
         foldl add_element 0.0 (0 -- n-1) / real(n)
      end ;

(* enough_sales : employee -> bool *)
fun enough_sales (name, salary, birth, sales)
    = mean sales > 100.0 ;

(* payrise : employee -> real -> employee *)
fun payrise (name, salary, birth, sales) percent
    = (name, salary * (1.0+percent/100.0), birth, sales) ;

(* update_single : personnel -> int -> personnel *)
fun update_single p i
    = if enough_sales (sub(p,i))
         then upd(p,i,payrise (sub(p,i)) 10.0)
         else p ;

(* increase : personnel -> personnel *)
fun increase p = let
                    val n = length p
                 in
                    foldl update_single p (0 -- n-1)
                 end ;
C database declarations
#define n_name     10
#define n_sales     5
#define n_personnel 4

typedef struct {
  char   name[n_name] ;
  double salary ;
  int    year_of_birth ;
  int    sold[n_sales] ;
} employee ;

typedef employee personnel[n_personnel] ;
C an arry of 4 employees
employee x[4] ;
C incorrect database update
personnel update_single( personnel p, int i ) {
  if( enough_sales( p[i] ) ) {
    p[i] = payrise( p[i] ) ;
  }
  return p ;                        /* INCORRECT C */
}

personnel increase( personnel old, int n ) {
  int i ;
  personnel new = old ;             /* INCORRECT C */
  for( i=0 ; i<n ; i++ ) {
    new = update_single( new, i ) ; /* INCORRECT C */
  }
  return new ;                      /* INCORRECT C */
}
C correct update
void update_single( personnel p, int i ) {
  if( enough_sales( p[i] ) ) {
    p[i] = payrise( p[i] ) ;
  }
}

personnel increase( personnel old, int n ) {
  int i ;
  personnel new = old ;             /* INCORRECT C */
  for( i=0 ; i<n ; i++ ) {
    update_single( new, i ) ;
  }
  return new ;                      /* INCORRECT C */
}
C incorrect first alternative
void increase( personnel old, int n, personnel new ) {
  int i ;
  new = old ;                     /* INCORRECT C */
  for( i=0 ; i<n ; i++ ) {
    update_single( new, i ) ;
  }
}
C correct first alternative
void increase( personnel old, int n, personnel new ) {
  int i ;
  for( i=0 ; i<n ; i++ ) {
    new[i] = old[i] ;
  }
  for( i=0 ; i<n ; i++ ) {
    update_single( new, i ) ;
  }
}
C correct second alternative
void increase( personnel old, int n ) {
  int i ;
  for( i=0 ; i<n ; i++ ) {
    update_single( old, i ) ;
  }
}
C database data handling functions
double mean( int s[], int n ) {
  int i ;
  int sum = 0 ;
  for( i=0 ; i < n ; i++ ) {
    sum = sum + s[i] ;
  }
  return (double)sum/n ;
}

bool enough_sales( employee e ) {
  return mean( e.sold, n_sales ) > 100.0 ;
}

void payrise( employee *e, double percent ) {
  e->salary = e->salary * (1 + percent/100) ;
}

void update_single( personnel p, int i ) {
  if( enough_sales( p[i] ) ) {
    payrise( &p[i], 10 ) ;
  }
}

void increase( personnel p, int n ) {
  int i ;
  for( i=0 ; i<n ; i++ ) {
    update_single( p, i ) ;
  }
}
C mean return
return (double)sum/n ;
C database IO functions
void print_employee( employee e ) {
  int i ;
  printf( "%s, %f, %d, [ ", e.name, e.salary,
                            e.year_of_birth ) ;
  for( i=0 ; i<n_sales ; i++ ) {
    printf( "%d ", e.sold[i] ) ;
  }
  printf( "]\n" ) ;
}

void print_personnel( personnel p, int n ) {
  int i ;
  for( i=0 ; i<n ; i++ ) {
    print_employee( p[i] ) ;
  }
}

int main( void ) {
  personnel p = {
    { "John" , 18813.00, 1963, {  80,  90,  75, 20, 69 } },
    { "Mary" , 19900.00, 1946, {  72,  83,  75, 18, 75 } },
    { "Bob"  , 12055.45, 1969, { 120, 110, 100, 99, 99 } },
    { "Alice", 15133.50, 1972, { 200, 230,  75, 11, 35 } }
  } ;
  increase( p, n_personnel ) ;
  print_personnel( p, n_personnel ) ;
  return 0 ;
}
C more efficient version of print_employee
void print_employee( employee *e ) {
  int i ;
  printf( "%s, %f, %d, [ ", e->name, e->salary,
                            e->year_of_birth ) ;
  for( i=0 ; i<n_sales ; i++ ) {
    printf( "%d ", e->sold[i] ) ;
  }
  printf( "]\n" ) ;
}
C call to print_employee
print_employee( &p[i] ) ;

5.10: Multi-dimensional arrays with fixed bounds

C matrix
#define ROW 3
#define COL 5
typedef int matrix[ROW][COL] ;
C matrix initialisation
matrix m = { {11,12,13,14,15},
             {21,22,23,24,25},
             {31,32,33,34,35} } ;
C printing a matrix
void print_matrix( matrix m ) {
  int i,k ;
  for( i = 0; i < ROW; i++) {
    printf( "row %d:", i ) ;
    for( k = 0; k < COL; k++) {
      printf( "\t%d", m[i][k] ) ;
    }
    printf( "\n" ) ;
  }
}

Summary

Further exercises

Exercise 5.10

C sample output
Jan. has 31 days
Feb. has 29 days
/* ... rest of months */
Dec. has 31 days
This year has 366 days

Exercise 5.11

C bisection command
a.out a.1 a.2 a.3 a.4 a.out b.1

Answer to exercise 5.11

C discrete bisection program
#include <stdlib.h>
#include <string.h>

typedef enum { false=0, true=1 } bool ;

int extra_bisection( int (*f)( void *, int ),
                     void *x, int l, int h  ) {
  int m ;
  int f_m ;
  while( true ) {
    m = (l + h) / 2 ;
    f_m = f( x, m ) ;
    if(  f_m == 0 ) {
      return m ;
    } else if( h-l <= 1 ) {
      return m ;
    } else if( f_m < 0 ) {
      l = m ;
    } else {
      h = m ;
    }
  }
}

int direction( void *p, int i ) {
  char ** data = p ;
  return strcmp( data[i] , data[0] ) ;
}

int main( int argc, char *argv[] ) {
  int i = extra_bisection( direction, argv, 1, argc ) ;
  printf( "%d\n", i ) ;
  return 0 ;
}

Answer to exercise 5.12

C find the break
int findbreak( void *p, int i ) {
  if( brk( i ) == 0 ) {
    return -1 ;
  }
  return 1 ;
}

int main( void ) {
  int b = extra_bisection( findbreak, NULL, 0, 0x7FFFFFFF ) ;
  printf( "Break: %x\n", b ) ;
  return 0 ;
}