Voir la source de 20141006:TP:C:Pointers:Array:EN

[[category:EPITA:TP:20142015]]

== Forewords ==

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

<source lang="make">
# 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
</source>

== 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: <tt>*</tt> for dereferencing and <tt>&</tt> for referencing. The star is also used for variable declarations.

Here is a little toy example of pointer usage:

<source lang="C">
/* 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;
}
</source>

'''Compile, run and try to understand this example.'''

=== Simple Usage: Passing Pointers ===

Start with a classical example: <tt>swap</tt>.

* '''Implement the following function'''
<source lang="C">
/*
 * swap the content pointed by a and b
 */
void swap(int *a, int *b);
</source>

Here is a small <tt>main</tt> function testing you swap function:

<source lang="C">
/* 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;
}
</source>

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

Here are two classical power functions:

<source lang="C">
/*
 * 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;
}
</source>

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

* '''Implement the following functions'''
<source lang="C">
/*
 * 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);
</source>

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

<source lang="C">
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;
}
</source>

== 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 <tt>0</tt>, often noted as <tt>'\0'</tt>.)

Remember that in C, array notation (using <tt>[]</tt>) 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:

<source lang="C">
  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 */
  }
</source>

* '''Implement the following functions:'''

<source lang="C">
/*
 * 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);
</source>

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

=== Operations ===

* '''Rewrite the following classical string operations of <tt>string.h</tt>'''

<source lang="C">
/*
 * 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);
</source>



== 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 <tt>malloc(3)</tt> or <tt>calloc(3)</tt> (take a look at the man page for further information.) <tt>malloc(size)</tt> allocates <tt>size</tt> contiguous bytes and returns the pointer to the first byte, <tt>calloc(number, size)</tt> allocates <tt>number * size</tt> contiguous bytes, set them to <tt>0</tt> and returns a pointer to the first byte. Memory allocated with <tt>malloc(3)</tt> or <tt>calloc(3)</tt> must be freed using <tt>free(3)</tt>.

<source lang="C">
  // 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);
</source>

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

<source lang="C">
# 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;
}
</source>

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

=== Array Manipulations ===

* '''Implement the following functions'''

<source lang="C">
/*
 * 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);
</source>