20141006:TP:C:Pointers:Array:EN

Forewords

In order to compile your code in this session, and probably the coming ones, you should use the following Makefile:

# Basic Makefile
 
CPPFLAGS=
CC=clang
CFLAGS= -Wall -Wextra -std=c99 -O2
LDFLAGS=
LDLIBS=
 
# empty all rule to prevent clean being the default rule
all:
 
clean:
	rm -f *~ *.o
 
# END

Pointers

Pointers are mandatory in C: they are used in a lot of place and can't be avoided. This first practical session about will try to cover basic usage of pointers and arrays.

Syntax Survey

There are two operators for manipulating pointers: * for dereferencing and & for referencing. The star is also used for variable declarations.

Here is a little toy example of pointer usage:

/* basic_pointers.c */
 
# include <stdio.h>
# include <stdlib.h>
 
 
int main() {
  // Simple integer
  int           x = 42;
  // A pointer to an integer
  int          *p;
 
  // Referencing: take the address of a left value
  p = &x;
 
  // Print the value of x
  printf("x = %d\n", x);
 
  // Dereferencing: follow the pointer to access the stored value
  printf("*p = %d\n", *p);
 
  // Dereferencing can be used to modify the pointed value
  *p = 0;
 
  printf("x = %d\n", x);
  printf("*p = %d\n", *p);
 
  // Pointers are values
  int          *q;
  // q contains the same address as p
  q = p;
 
  // Print the address in p, then the referenced value
  printf("p : %p (%d)\n", p, *p);
 
  // Print the address in q, then the referenced value
  printf("q : %p (%d)\n", q, *q);
 
  return 0;
}

Compile, run and try to understand this example.

Simple Usage: Passing Pointers

Start with a classical example: swap.

• Implement the following function

/*
 * swap the content pointed by a and b
 */
void swap(int *a, int *b);

Here is a small main function testing you swap function:

/* swap.c */
 
# include <stdio.h>
# include <stdlib.h>
 
void swap(int *a, int *b) {
  // FIX ME
}
 
int main() {
  int           x = 1, y = 2;
  // will print: x = 1 and y = 2
  printf("x = %d and y = %d\n", x, y);
  // swap
  swap(&x, &y);
  // should print: x = 2 and y = 1
  printf("x = %d and y = %d\n", x, y);
 
  return 0;
}

Another classical example: returning more than one value using pointer.

Here are two classical power functions:

/*
 * compute a^b using linear algorithm
 */
unsigned power(unsigned a, unsigned b) {
  if (b == 0) return 1;
  return a * power(a, b - 1);
}
 
/*
 * compute a^b using logarithmic algorithm
 */
unsigned quick_power(unsigned a, unsigned b) {
  unsigned              r = 1;
  if (b > 0) {
    r = quick_power(a * a, b / 2);
    if ( b % 2 != 0)
      r *= a;
  }
  return r;
}

Your goal is to extends these two functions so that they count the number of recursive calls:

• Implement the following functions

/*
 * compute a^b using linear algorithm
 * count the number of call
 */
unsigned power_c(unsigned a, unsigned b, unsigned *count);
 
/*
 * compute a^b using logarithmic algorithm
 * count the number of call
 */
unsigned quick_power_c(unsigned a, unsigned b, unsigned *count);

Finally, here is a main function designed to test you functions:

int main() {
  unsigned              a = 2, b = 15;
  unsigned              c0 = 0, c1 = 0;
 
  printf("power_c(%u, %u, &c0) = %u\n", a, b, power_c(a, b, &c0));
  printf("  c0 = %u\n", c0);
  printf("quick_power_c(%u, %u, &c1) = %u\n", a, b, quick_power_c(a, b, &c1));
  printf("  c1 = %u\n", c1);
 
  return 0;
}

Strings

Survey

In C there is not native type for strings. Strings are represented as arrays of characters terminated by a special character (the character of ASCII code 0, often noted as '\0'.)

Remember that in C, array notation (using []) is a shorthand for pointers, thus a pointer to character is also an array of characters (they got the same type).

Most operation of strings consist of a loop of the form:

  char         *s = "a string";
 
  // Classical loop on a string
 
  for (unsigned i = 0; s[i] != '\0'; ++i) {
    /* do clever things here */
  }
 
  // '\0' == 0 and 0 is false
  // we can rewrite the previous loop as
 
  for (unsigned i = 0; s[i]; ++i) {
    /* do clever things here */
  }

• Implement the following functions:

/*
 * change in place every lower case letter to the corresponding upper case
 * letter.
 */
void to_upper(char *s);
 
/*
 * apply in place the rot13 translation
 * preserves lower and upper case
 */
void rot13(char *s);

For to_upper and rot13 note that a character is in fact an integer and thus 'a' + 1 is 'b' and 'A' + 1 is 'B'.

Operations

• Rewrite the following classical string operations of string.h

/*
 * For more precise definition of these functions read their man pages.
 * (note mystrlen is strlen(3) and so on ... )
 */
 
// string length
size_t mystrlen(const char *s);
 
// copy atmost n bytes from src to dest
// 0 pad dest if src contains less than n bytes
char *mystrncpy(char *dest, const char *src, size_t n);
 
// copy atmost n bytes of src at the end of dest
// always add the final 0 at the end of dest
char *mystrncat(char *dest, const char *src, size_t n);
 
// compare lexicographically atmost n bytes of s1 and s2
// returns: 0 equal, negative s1 is smaller, positive otherwise
int mystrncmp(const char *s1, const char *s2, size_t n);
 
// returns the pointer to first occurrence of c in s
// returns NULL if c is not found
char *mystrchr(const char *s, int c);
// Same as above but return the last occurrence
char *mystrrchr(const char *s, int c);
 
// returns a copy of s allocated with malloc(3)
char *mystrdup(const char *s);

Arrays

Arrays creation

We have several way of creating arrays: dynamically or statically. We'll see the real difference later, but for now consider that static arrays have fixed size and are local to their creation context.

In order to allocate dynamic arrays, we use malloc(3) or calloc(3) (take a look at the man page for further information.) malloc(size) allocates size contiguous bytes and returns the pointer to the first byte, calloc(number, size) allocates number * size contiguous bytes, set them to 0 and returns a pointer to the first byte. Memory allocated with malloc(3) or calloc(3) must be freed using free(3).

  // Some examples
 
  // static array
  int           stab[256];
 
  // dynamic array
  int          *dtab;
 
  // Allocate rooms for 256 int
  // sizeof (int) returns the size of an int in bytes.
  dtab = malloc(256 * sizeof (int));
  // free dtab
  free(dtab);
 
  // The same alloation with calloc
  dtab = calloc(256, sizeof (int));
  // free dtab
  free(dtab);

The following functions allocate and fill an array of random integer, note the mandatory define before the include in order to use the random(3) function (which gives better randomness than rand(3).

# define _XOPEN_SOURCE 500
 
# include <stdlib.h>
 
/*
 * allocate and fill an array of size int
 */
int* create_random_array(size_t size) {
  int          *tab;
  tab = malloc(size * sizeof (int));
  for (size_t i = 0; i < size; ++i)
    // use % 256 to avoid big values
    tab[i] = random() % 256;
  return tab;
}

You'll use this function to build arrays while testing the functions in the following exercise.

Array Manipulations

• Implement the following functions

/*
 * compute the sum of the element of the given array
 */
int array_sum(int tab[], size_t size);
 
/*
 * reverse, in place, the array
 * you can reuse the swap function
 */
void array_reverse(int tab[], size_t size);
 
/*
 * binary search: use a dichotomic algorithm to search for the value x in a
 * sorted array tab.
 * Returns a pointer to the cell containing the searched value, or NULL if not
 * found.
 * You should search between the left (included) and right (excluded) bounds.
 */
int* binary_search(int x, int tab[], size_t left, size_t right);