CHAPTER 6
=========

array declaration and usage
---------------------------

- Goal: store many variables with the same type and meaning.
- a[N] => 0 to N-1. a[i] - content of cell i.
- occupies a contigious area in the memory

#define N 100

int a[N];       /* space for a[0], ..., a[99] is allocated */

for (i = 0; i< N; i++)
            
   sum += a[i];        /* process element a[i] */

-----------------------------------------------

initialization
--------------

- not (necessarily) initialized by the system.
- size can be determined by initialization
- special initialization for strings

float f[5] = {0.0, 1.0, 2.0, 3.0, 4.0};

int a[100] = {0};

int a[] = {2, 3, 5, -7}; 

char s[] = "abc"; //equiv. to char s[] = {'a', 'b', 'c', '\0'};

===============================================================

pointers
--------

- Goal: access to memory; manipulation of memory addresses and content.
- &v - reference operator; unary
- *p - dereference operator; unary
- 0/NULL - no pointing
- address is typically unsigned int => sizeof(int *)=word size (4)

  p      i
|---|  |---|
|   |->|   |
|---|  |---|
 &i     *p  


int *p;

p = 0;
p = NULL;       /* equivalent to p = 0 */
p = &i;
p = (int *) 1776; /* an absolute address in memory */

-----------------------------------

int a = 1, b = 2, *p;

p = &a;

b = *p; //is equivalent to b = a;

======================================================================

(location.c) 

// printing the address of the integer i using %u, %p and %x

#include <stdio.h>

int main(void)
{
   int   i = 7, *p;

   p = &i;
   printf("%s%d\n%s%u (%%d: %d)\n",
      "   Value of i: ", *p,
      "Location of i: ",  p, p);

   printf("\nLocation of i with the %%p format:%p\n",p);
   printf("Location of i with the %%x format:%x\n",p);

   return 0;
}

-----------------------

   Value of i: 7
Location of i: 3221223460 (%d: -1073743836)

Location of i with the %p format:0xbffff824
Location of i with the %x format:bffff824

======================================================================

Declaration and inialization
----------------------------

int     i = 3, j = 5, *p = &i, *q = &j, *r;
double  x;

expression              equivalent expression           value
-------------------------------------------------------------

p == & i                p == (& i)                      1

* * & p                 * (* (& p))                     3

r = & x                 r = (& x)                /* illegal */

7 * * p / * q + 7       (((7 * (* p))) / (* q)) + 7     11

* (r = & j) *= * p      (* (r = (& j))) *= (*p)         15

==================================================================

Declaration
-----------

int *p;
float *q;
void *v;


Legal assignments               Illegal assignments
-----------------               -------------------

p = 0;                          p = 1;

p = (int *) 1;                  v = 1;

p = v = q;                      p = q;

p = (int *) q;


- no pointing to constants, expressions and registers.

More illegal:
&3,
&(k + 99), 

register v;
&v

- pointer-assign-and-use.c - accessing an invented address causes
  a segmentation fault.

============================================================

pointers and arrays
-------------------

#define N 80
int a[N];
int *p;
int i;

a[i] <=> *(a+i)
p[i] <=> *(p+i)

- the BASE ADDRESS of an array a is the address of the element a[0]

p=a; <=> p=&a[0];
p=a+1; <=> p=&a[1];


(i)
for (p=a; p<&a[N]; ++p)
  sum += *p;

(ii)
for (i=0; i<N; ++i)
  sum += *(a+i);

(iii)
p=a;
for (i=0; i<N; ++i)
  sum += p[i];

-------------------------

- The major difference between a pointer and an array:
  - a pointer variable can be assigned different addresses
  - the array identifier is a CONSTANT pointer and cannot be modified

the following is illegal:
a=p;
++a;
&a;

============================================================

- p+1 = address of next element of same type.
- p-1 = address of previous element of same type.
- p-q = number of elements between p and q.
- +,* are not allowed on pointers.

pointer arithmetic
------------------

(pointer-arith.c)

#include <stdio.h>

int main(void)
{
  int a[2], *p1=&a[0], *p2=&a[1];

  printf(" p2-p1 = %u\n", p2-p1);
  printf(" (int)p2-(int)p1 = %d\n", (int)p2-(int)p1);
  
  return 0;
}

============================================================

call by reference
-----------------

- steps: 1. define pointer as param.
         2. use derefenced value in the body of the function.
	 3. pass address as argument to function


#include <stdio.h>

void   swap(int *, int *);

int main(void)
{
   int   i = 3, j = 5;

   swap(&i, &j);
   printf("%d %d\n", i, j); /* 5  3  is printed */  
   return 0;
}


void swap(int *p, int *q)
{
   int   tmp;

   tmp = *p;
   *p = *q;
   *q = tmp;
}

======================================================================

passing an array to a function
------------------------------

- base address is passed call by value.
- array is not copied!
- double *a is an equiv. form

double sum(double a[], int n)     /* n is the size a[] */
{
   int      i;
   double   sum = 0.0;

   for (i = 0; i < n; ++i)
      sum += a[i];
   return sum;
}

======================================================================

dynamic allocation
------------------

- void * - generic pointer; should cast to required type
- size_t is typically unsigned int
- all return NULL on failure

#include <stdlib.h>

void *calloc(size_t n, size_t el_size); // space initialized with all
                                        // bits set to zero

void *malloc(size_t size); // space not initialized

void free( void *ptr );

void *realloc(void *ptr, size_t size);

======================================================================

(merge-sort.c)

//merge sort for an array of ints

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

#define   KEYSIZE   16

void   mergesort(int *, int);
void   merge(int *, int *, int *, int, int);
void   print_array(char *, int *, int);

int main(void)
{
   int   i, key[] = { 4, 3, 1, 67, 55, 8, 0, 4,
                     -5, 37, 7, 4, 2, 9, 1, -1 };

   print_array("before mergesort",key,KEYSIZE);
   mergesort(key, KEYSIZE);
   print_array("after mergesort",key,KEYSIZE);
   return 0;
}

// mergesort: Use merge() to sort an array of size n
void mergesort(int key[], int n)
{ 
   int    j, k, m, *w;

   for (m = 1; m < n; m *= 2)
      ;
   if (m != n) {
      printf("ERROR: Size of the array is not a power of 2 - bye!\n");
      exit(1);
   }
   w = calloc(n, sizeof(int));                /* allocate workspace */
   assert(w != NULL);
   for (k = 1; k < n; k *= 2) {
      for (j = 0; j < n - k; j += 2 * k)
         merge(key + j, key + j + k, w + j, k, k);  /* merge into w */
      for (j = 0; j < n; ++j)
         key[j] = w[j];                    /* write w back into key */
      print_array("intermediate:",key,KEYSIZE);
   }
   free(w);                                   /* free the workspace */
}

// merge a[] of size m and b[] of size n into c[]
void merge(int a[], int b[], int c[], int m, int n)
{
   int   i = 0, j = 0, k = 0;

   while (i < m && j < n)
      if (a[i] < b[j])
         c[k++] = a[i++];
      else
         c[k++] = b[j++]; 
   while (i < m)               /* pick up any remainder */
      c[k++] = a[i++];
   while (j < n)
      c[k++] = b[j++];
}

void print_array(char *title, int *key, int n_elem)
{
  int i;

   printf("\n %s:\n",title);
   for (i = 0; i < n_elem; ++i)
      printf("%4d", key[i]);
   putchar('\n');
}

======================================================================

tyepdef
-------

typedef double vector[3]; // vector is an aray of 3 doubles

double dot_product(vector x, vector y)
{
  int i;
  double sum=0.0;

  for (i=0; i<3; ++i)
    sum += x[i]*y[i];

  return sum;
}

======================================================================

Strings
-------

- one dimensional arrays of type char; end with '\0'
- string size is its length + 1.

(count-word.c)

// count the number of words in a string

#include <stdio.h>
#include <ctype.h> // included for isspace
 
int word_cnt(char *s);

int main(void)
{
  char s[] = "the room is big";

  printf(" the number of words in the string \"%s\" is %d\n",
         s, word_cnt(s));

  return 0;
}

int word_cnt(char *s)
{
   int    cnt = 0;

   while (*s != '\0') {
      while (isspace(*s))     /* skip white space */
         ++s;
      if (*s != '\0') {           /* found a word */
         ++cnt;
         while (!isspace(*s) && *s != '\0')
            ++s;                 /* skip the word */
      }
   }
   return cnt;
}

======================================================================

String functions
----------------

#include <string.h> 

unsigned strlen(const char *s)
{
   register int   n;

   for (n = 0; *s != '\0'; ++s)
      ++n;
   return n;
}

-----------------------------------------------

char   *strcat(char *s1, const char *s2)
{
   register char   *p = s1;

   while (*p)
      ++p;
   while (*p++ = *s2++)
      ;
   return s1;
}

-----------------------------------------------

char *strcpy(char *dest, const char *src);
int strcmp(const char *s1, const char *s2); 
char *strdup(const char *s);

-----------------------------------------------

(str.c)

#include <string.h>
#include <stdio.h>

int main( void )
{
  char s1[] = "beautiful big sky country",
	s2[] = "how now brown cow";

  printf("%s\n",s1+10);
  strcpy(s1+10,s2+8);
  strcat(s1,"s!");
  printf("%s\n",s1);
}

======================================================================

multidimensional arrays
-----------------------

int a[3][5];

a[i][j] is equivalent to:
*(&a[0][0]+5*i+j)

initialization:
int a[2][2] = {{1,0},{3,0}} <=> {{1},{3}}

- show array-address.c (row-wise storage)

(2d-array.c)

#include <stdio.h>

void f( int a[][5] ) //equiv form: int (*a)[5]
{
  printf("in f: a[1][0]=%d\n", a[1][0]);
}

int main(void) 
{
  int a[3][5]={{1,2,3,4,5},{6},{5}};
  
  printf("a[1][0]=%d\t *(&a[0][0]+5)=%d\n\n", a[1][0], *(&a[0][0]+5));
  printf("*a=%p\t a[0]=%p\n\n", *a, a[0]);
  printf("**a=%d\t\t **(a+1)=%d\t *a[1]=%d\n\n", **a, **(a+1), *a[1]);
  f(a);
  return 0;
}

======================================================================

arrays of pointers
------------------

(lexi-sort.c)

// sort words lexicographically

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

#define   MAXWORD   50         /* max word size */
#define   N         1000       /* array size */

void   sort_words(char *[], int);
void   swap(char **, char **);

int main(void)
{
   char   *w[N];               /* an array of pointers */
   char   word[MAXWORD];       /* work space */
   int    n;                   /* number of words to be sorted */
   int    i;

   for (i = 0; scanf("%s", word) == 1; ++i) {
      if (i >= N) {
         printf("Sorry, at most %d words can be sorted.", N);
         exit(1);
      }
      w[i] = calloc(strlen(word) + 1, sizeof(char));
      strcpy(w[i], word);
   }
   n = i;
   sort_words(w, n);
   for (i = 0; i < n; ++i)      /* print the sorted words */
      printf("%s\n", w[i]);
   return 0;
}

void sort_words(char *w[], int n)   
/* n elements are to be sorted */
{
   int    i, j;

   for (i = 0; i < n; ++i)
      for (j = i + 1; j < n; ++j)
         if (strcmp(w[i], w[j]) > 0)
	   swap(&w[i], &w[j]);
}

void swap(char **p, char **q)
{
   char   *temp;

   temp = *p;
   *p = *q;
   *q = temp;
}
======================================================================

(echo.c)

// printing the command line arguments

#include <stdio.h>

void main(int argc, char *argv[])
{
   int   i;

   printf("argc = %d\n", argc);
   for (i = 0; i < argc; ++i)
      printf("argv[%d] = %s\n", i, argv[i]);
}

======================================================================

functions as arguments
----------------------

// find a root of f() by the bisection method

#include <stdio.h>

#define   EPS   1e-12               /* epsilon */

double   p(double);
double   root(double (*)(double), double, double);

int main(void)
{
   double   x;

   x = root(p, 0.0, 3.0);
   printf("%s%.16f\n%s%.16f\n",
      "Approximate root: ", x,
      "  Function value: ", p(x));
   return 0;
}

double root(double f(double), double a, double b)
{
   double   m = (a + b) / 2.0;     /* midpoint */

   if (f(m) == 0.0 || b - a < EPS)
      return m;
   else if (f(a) * f(m) < 0.0)
     //return root(f, a, m);
     root(f, a, m);
   else
     // return root(f, m, b);
     root(f, m, b);
}

// a polynomial p 
double p(double x)
{
 return (x * x * x * x * x  -  7.0 * x  -  3.0);
}

======================================================================

const
-----

- type qualifier; comes after storage class

static const int k=3;

const int a = 7;
int *p = &a;        /* compiler warning */

const int a = 7;
const int *p = &a;  /* ok */

int a=7;
int * const p = &a;

int a=7;
const int * const p = &a;  

======================================================================

qsort: a generic sorting procedure
----------------------------------

qsort's prototype in stdlib.h (using size_t from stddef.h):
void qsort(void *array,
           size_t n_elem,
           size_t elem_size,
           int compare(const void *, const void *));
compare(a,b) returns negative int if a<b
             returns 0            if a=b
             returns positive int if a>b


(int-qsort.c)

// qsort an array of ints

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

#define   KEYSIZE   16

int compare_int(const void *p1, const void *p2);
void print_array(char *title, int *key, int n_elem);

int main(void)
{
   int   key[] = { 4, 3, 1, 67, 55, 8, 0, 4,
                  -5, 37, 7, 4, 2, 9, 1, -1 };

   print_array("before ",key,KEYSIZE);
   qsort(key, KEYSIZE, sizeof(int), compare_int);
   print_array("after ",key,KEYSIZE);
   return 0;
}

void print_array(char *title, int *key, int n_elem)
{
  int i;

   printf("\n %s:\n",title);
   for (i = 0; i < n_elem; ++i)
      printf("%4d", key[i]);
   putchar('\n');
}

// the compare function to be passed as a parameter to qosrt
int compare_int(const void *p1, const void *p2)
{
  const int *q1 = p1, *q2 = p2;
  
  return ((*q1)-(*q2));
}