ARRAYS IN C

19.01

First a few simple examples to get an idea how arrays can be declared 
and initialized in the language C.

	int A[10];
	
declares an array A that can contain 10 elements of type int.
The name of the array is A.
The elements are not initialized.

If you want to initialize all elements on value 0 you must write

	int A[10] = {0};
	
If you write 

	int A[10] = {0, 10, 20, 30, 40};

then the first 5 elements are initialized as given and the remaining elements
are set to 0.

19.01

TABLE OF CONTENTS HC 19

19.02

INITIALIZATION AND MEMORY MAP

19.02

If you want to initialize all elements on values of your own choice you can
do so by writing something like

	int A[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};


In C the elements of an array are counted starting at indexvalue 0.
In array A above the first element is A[0] and the last one is A[9].


	

19.01

TABLE OF CONTENTS HC 19

19.03

ARRAY ELEMENTS A[i]

19.03

Elements can be retrieved and modified using the representation A[i].

•		int temp = A[7];   // assigns value 70 to temp

•		A[7] *= 7;         // changes A[7] from 70 to 490

•		int i = 10, 
		    sum = 0;
		do 
			sum += A[--i]; 
		while (i);
	
	determines the sum of all array elements

•	etc., etc.

19.02

TABLE OF CONTENTS HC 19

19.04

COMMON DECLARATIONS

19.04

 
1	#define MAX_SIZE ...  // some positive integer constant
	elt_type A[MAX_SIZE]; // array of MAX_SIZE elts of elt_type
	
2	typedef elt_type elt_array_type[MAX_SIZE];

defines the new type elt_array_type 
as an array of MAX_SIZE elements of elt_type
and
	elt_array_type A, B;

then declares two arrays of this type.

Example:
	typedef int int_vec32[32];
	int_vec32 v1, v2;

defines type int_vec32 as an array of 32 integers
and two vectors v1 and v2 of this new type.

19.03

TABLE OF CONTENTS HC 19

19.05

INTERMEZZO: sizeof()

19.05

sizeof() a function that takes one argument, a type, avariable or an
expression, and returns the size of this argument in bytes:

	nc = sizeof()(char);        // nc ==  1
	ns = sizeof()(short);       // ns ==  2
	ni = sizeof()(int);         // ni ==  4
	nf = sizeof()(float);       // nf ==  4
	nd = sizeof()(double);      // nd == 12

The type argument can also be a user-defined type:

	typedef double     elt;   // type elt is double
	typedef elt*      pelt;   // type pelt is pointer to elt
	typedef elt eltarr[32];   // type eltarr is array of 32 elt
	
	elt     e, *ep;           // e and *ep are type elt
	elt     e1[],             // e1 is type array of elt
	        e2[1024];         // e2 is type array of elt
	eltarr  x, y;             // x and y are vars of type eltarr
	                          // i.e., arrays of 32 elt
                            

19.04

TABLE OF CONTENTS HC 19

19.06

sizeof()

19.06

Now:
•	sizeof(elt)  == sizeof(e)  == sizeof(*ep)  == 12
	since type elt has been defined as type double, and
	e is a variable of type elt and
	*ep is an expression that yields a value of type elt
	
•	sizeof(elt*) == sizeof(pelt) == sizeof(ep) == 4
	since the size of any pointer is 4 (an address is 4 bytes)
	
•	SURPRISES:
	sizeof(e) == sizeof(e1) == sizeof(e2) == 4
	The array identifiers e, e1 and e2 are pointer constants!!
	These constants are chosen by the compiler at the moment that the
	arrays are declared. 
	The name of an array stands for a pointer constant, actually, 
	the base-address (address of element [0]) of the array,
	and	sizeof(x) == 32 * sizeof(x[0]) == 384
	and	dimension == sizeof(x) / sizeof(x[0]) == 32
	since 
	x and y are of type eltarr defined as array of 32 elt!

19.05

TABLE OF CONTENTS HC 19

19.07

ARRAYS HAVE SPECIAL PROPERTIES

19.07

•	ARRAYS ARE NOT VALUE TYPES BUT POINTER TYPES 0
	ARRAY IDENTIFIERS ARE CONSTANT POINTERS
	Actually when you declare
	
	int theArray[10] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
	
	the compiler 
	•	selects a free block of memory to store 10 integers contiguously!
	•	base address, &theArray[0], is assigned to the name of the array
	•	theArray == &theArray[0] is a constant that cannot be changed.
	
	The corresponding memory map (with A iso theArray) looks like:

	

19.06

TABLE OF CONTENTS HC 19

19.08

ADDRESSES OF ARRAY ELEMENTS

19.08

With theArray equal to the address of its first element &theArray[0]
we also have
                       theArray + i == &theArray[i]
Values are given by
                       theArray[i]      as usual
but also by
                     *(theArray + i)    i.e. by dereferencing the address

The fact that an array identifier is a constant pointer has some consequences!

•	Let
		int a[10], b[10]; 
	then
		a = b;
		b = a;
	are forbidden assignments! Why?
	Well, 
		a and b stand for constant pointers, and
		did you ever write 13 = 18;? No, never!

19.07

TABLE OF CONTENTS HC 19

19.09

ARRAY AND POINTER

19.09

•	Let
		int a[10], *b; 
	then
		a = b;
	is a forbidden assignment! Why?
	Well, 
		a stands for a constant pointer, and
		did you ever write int n; 13 = n;? No, never!
	But
		b = a;
	is oke!! However it does not yield a copy of array a of course!
	         it assigns &a[0] to the pointer b!
	Indeed, 
		variable = value; and
		there is nothing wrong with n = 13;
	
	Assigning an array name to a pointer variable
	can be very useful!
	

19.08

TABLE OF CONTENTS HC 19

19.10

ARRAY AND POINTER

19.10

•	Let 
	int a[] = {0, 10, 20, 30, 40, 50, 60, 70, 80, 90};
	int *p;  // a pointer to int not yet initialized
	p = a;   // now p points to element a[0] of array a
	         // i.e. p == &a[0] and *p == a[0]
	         // and  p+i == &a[i] and *(p+i) == a[i] 
		     // but *(p+i) and *p+i are different things!!
	
	When you think that consecutive elements, starting from element a[0],
	can be reached using ++a; or a++; you are dead-wrong.
	Did you ever try something like ++13; or 13++;? Never!
	
	But p is a common pointer variable and 
	•	if the assignment p = a; has been executed 
		then both ++p; and p++; will result in 
		p pointing to the next element in the array.

19.09

TABLE OF CONTENTS HC 19

19.11

PRINTING ARRAY ELEMENTS

19.11

•	Consider printing array elements:
	
	•	for (i = 0; i < n; i++) printf("%4d",   a[i]);
	•	for (i = 0; i < n; i++) printf("%4d",   p[i]);
	•	for (i = 0; i < n; i++) printf("%4d", *(a+i));
	•	for (i = 0; i < n; i++) printf("%4d", *(p+i));

•	Consider the last print statement:
	You might argue that you also can write:
	
	•	for (i = 0; i < n; i++) {printf("%4d", *p); p = p+1;}
	•	for (i = 0; i < n; i++) {printf("%4d", *p); p++;}
	•	for (i = 0; i < n; i++) {printf("%4d", *p++);}

Indeed:
•	n = *p++;        is equivalent to {n = *p; p = p+1;}
	                  	the value of n becomes *p and pointer p is advanced
also
•	n = *(p++);      is equivalent to {n = *p; p = p+1;}

But!	

19.10

TABLE OF CONTENTS HC 19

19.12

ARRAY AND POINTER

19.12

•	n = (*p)++;       is equivalent to {n = *p; *p = *p+1;}
	                  		n becomes equal to *p, 
	                  		the value to which p points is increased
	                  		but the pointer remains in position!

Summary:
•	*(p++)    retrieves the int value *p and advances the pointer p
•	(*p)++    increments the value *p pointed at by p
and
•	++(*p)    increments the value *p pointed at by p
•	*(++p)    advances the pointer and retrieves the value *p of next elt!

Do you like pointer cryptography? 
Try this one        (*(p++))++,
and this one        ++(*(++p)),
and what about      ++((*p)++)?

At last consider the following program:

19.11

TABLE OF CONTENTS HC 19

19.13

TEST YOUR KNOWLEDGE

19.13

int main() {

	int a[] = {99, 10, 20, 30, 40, 50, 60, 70, 80, 90};
	int i, *p = a;
	
//	print header
	printf("\n                    i        ");
	for (i=0; i<10; i++) printf("%4d",i);
	printf("     a[0]\n");
	printf("=======================================");
	printf("=======================================\n");
	printf("\n                 a[i]        ");
	for (i=0; i<10; i++) 
		printf("%4d",   a[i]); printf("%8d",a[0]);
	printf("\n               *(p+i)        ");
	for (i=0; i<10; i++) 
		printf("%4d", *(p+i)); printf("%8d",a[0]);
	printf("\n-------------");

19.12

TABLE OF CONTENTS HC 19

19.14

PREDICT ...

19.14

printf("\nExp1:    *p++        "); p = a;
for (i=0; i<10; i++) printf("%4d",*p++);   printf("%8d",a[0]);
printf("\nExp2:  (*p)++        "); p = a;
for (i=0; i<10; i++) printf("%4d",(*p)++); printf("%8d",a[0]);
printf("\nExp3:  *(p++)        "); p = a;
for (i=0; i<10; i++) printf("%4d",*(p++)); printf("%8d",a[0]);
printf("\n-------------");
printf("\nExp4:    ++*p        "); p = a;
for (i=0; i<10; i++) printf("%4d",++*p);   printf("%8d",a[0]);
printf("\nExp5:  ++(*p)        "); p = a;
for (i=0; i<10; i++) printf("%4d",++(*p)); printf("%8d",a[0]);
printf("\n-------------");
printf("\nExp6:    *++p        "); p = a;
for (i=0; i<10; i++) printf("%4d",*++p);   printf("%8d",a[0]);
printf("\nExp7:  *(++p)        "); p = a;
for (i=0; i<10; i++) printf("%4d",*(++p)); printf("%8d",a[0]);
printf("\n\n");
printf("=======================================");
printf("=======================================\n");
}
Try to predict/explain the output before reading the next sheet:

19.13

TABLE OF CONTENTS HC 19

19.15

AND COMPARE

19.15

            i     0   1   2   3   4   5   6   7   8   9   a[0]
==============================================================

         a[i]    99  10  20  30  40  50  60  70  80  90    99
       *(p+i)    99  10  20  30  40  50  60  70  80  90    99
-------------
Exp1:    *p++    99  10  20  30  40  50  60  70  80  90    99
Exp2:  (*p)++    99 100 101 102 103 104 105 106 107 108   109
Exp3:  *(p++)   109  10  20  30  40  50  60  70  80  90   109
-------------
Exp4:    ++*p   110 111 112 113 114 115 116 117 118 119   119
Exp5:  ++(*p)   120 121 122 123 124 125 126 127 128 129   129
-------------
Exp6:    *++p    10  20  30  40  50  60  70  80  90   ?   129
Exp7:  *(++p)    10  20  30  40  50  60  70  80  90   ?   129

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

19.14

TABLE OF CONTENTS HC 19

19.16

ARRAYS ARE POINTER TYPES (1)

19.16

•	ARRAYS ARE NOT VALUE TYPES BUT POINTER TYPES 1
	ARRAYS ARE PASSED BY REFERENCE
	
	void print   (int a[], int n); // print  elts a[0..n-1]
	void process (int a[], int n); // square elts a[0..n-1]
	
	int main(void) {
		int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9},
		    N    = 9;
		printf("Array before processing:"); print(A, N);
		process(theArray, theSize);
		printf("Array after  processing:"); print(A, N);
		return(0);
	}
	void print(int a[], int n) {
		int i;
		for (i = 0; i < n; i++) printf("%3d", a[i]);
		printf("\n");
	}
	void process(int a[], int n) {
		int i;
		for (i = 0; i < n; i++) a[i] = a[i] * a[i];
	}

19.15

TABLE OF CONTENTS HC 19

19.17

ARRAYS ARE PASSED BY REFERENCE

19.17

OUTPUT:
		Array before processing:  1  2  3  4  5  6  7  8  9
		Array after  processing:  1  4  9 16 25 36 49 64 81
	
Thus:
	the function process has changed all elements of the actual array
	and this is what we always have called pass by reference!!
	
Swapping integer values has been discussed before:

	void swap(int n1, int n2) { // incorrect swap
		int temp = n1; n1 = n2; n2 = temp;
	}
has no effect outside this function on account of call-by-value.
but 
	void swap(int* n1, int* n2) { // correct swap
		int temp = *n1; *n1 = *n2; *n2 = temp;
	}
has the desired effect outside this function on account of call-by-ref.

19.16

TABLE OF CONTENTS HC 19

19.18

SWAPPING ARRAY ELEMENTS

19.18

Now suppose we want to swap elements j and k of an array.

One possibility is to call the swap function above, either as
	
		swap(&a[j], &a[k]);  // addresses of elements j and k
or as
		swap(a+j, a+k);      // addresses of elements j and k
	
Another possibility is to design a swap-function that imports the array and
two index values

	void swap(int a[], int j, int k) {
		int temp = a[j]; a[j] = a[k]; a[k] = temp;
	}

which is then used as

		swap(a, j, k);

and this simply works because array parameters are passed call-by-reference.

19.17

TABLE OF CONTENTS HC 19

19.19

ARRAYS ARE POINTER TYPES (2)

19.19

•	ARRAYS ARE NOT VALUE TYPES BUT POINTER TYPES 2
	ARRAYS AS FORMAL PARAMETERS
In a function like return_type fun(elt_type x[], int n);
the formal array parameter x is treated as a common pointer variable. 
Thus, when an actual array elts is passed as an argument then the formal
parameter x receives a copy of &elts[0] == elts.
Important observations:
•	elts is a constant pointer and at the moment that the function
	is called &elts[0] is assigned to x. 
•	x is a common pointer that happens to be initialized on the base
	address of array elts. The value of elts cannot be changed 
	but x can be modified at any moment!

Example: determine the maximal element in an array of natural numbers.

	int max (int a[], int n) {
		int maxsofar = 0;          // init maxsofar on 0
		while (n) {
			if (*a > maxsofar) 
				maxsofar = *a;
			n--; a++;
		}
	}

19.18

TABLE OF CONTENTS HC 19

19.20

FORMAL ARRAY PARAMETERS

19.20

Some remarks:

The function declarations

•	ret_type fun(elt_type x[32]); // compiler reads elt_type*
•	ret_type fun(elt_type x[]);   // compiler reads elt_type*
•	ret_type fun(elt_type* x);    // compiler reads elt_type*

The compiler ignores the size and does not know the size!!
You always have to inform the function about how many 
elements must be processed:

•	process the first n elements x[0..n):

		return_type fun(elt_type* x, int n);
		
•	process all elements from lbnd to ubnd inclusive

		return_type fun(elt_type* x, int lbnd, int ubnd); 

19.19

TABLE OF CONTENTS HC 19

19.21

POINTER ARITHMETIC

19.21

•	POINTER ARITHMETIC:

Since you have informed the compiler about the type of elements (elt_type)
that are stored in array x it will use the following address arithmetic:
	
	&x[j] - &x[0] = x+j - x = j
		j what?
			j elements, and
			j * sizeof(elt_type) bytes.
		
The following operations are defined on pointer values:

•	ptr + int    x + j    j elements to the right of x
•	ptr - int    y - k    k elements to the left  of y
•	ptr - ptr    x - y    number of elements from x to y
•	ptr < ptr    x < y    and all other comarison operators
	                      and equality and inequality testing.

Forbidden:

•	ptr * int,  ptr / int, ptr % int,
•	ptr + ptr, etc.

19.20

TABLE OF CONTENTS HC 19

19.22

ARRAYS ARE POINTER TYPES (3)

19.22

Question: If lbnd and ubnd are indexvalues to the first and last element  
of an array segment, then what is the index value of the middle element?
Well:
	int mid = (lbnd + ubnd) / 2;

Question: If lbnd and ubnd are pointers to the first and last element of an 
array segment, then what is the pointer to the middle element?
Well:
	int* mid = lbnd + (ubnd - lbnd) / 2;

•	ARRAYS ARE NOT VALUE TYPES BUT POINTER TYPES 3
	ARRAYS AS FUNCTION RETURN TYPES
	
C functions cannot return arrays, but
C functions can return a pointer to the first element of an array!
Thus:
		elt_type[] fun( .. )  is forbidden in C
		
		elt_type*   fun( .. )  is oke and has the desired functionality.

19.21

TABLE OF CONTENTS HC 19

19.23

ARRAY AS FUNCTION RETURN TYPE

19.23

Important remark:

	elt_type*  fun( .. ) {
		elt_type elt_array[32];
		// do whatever you want to do with array a
		return elt_array;
	}

holds a nasty surprise!!
Array elt_array is a local variable of fun and local variables have a lifetime 
that is restricted to the lifetime of the function. After termination  
of the function local variables do not exist any longer!

Here you have to allocate global memory (to be discussed later):

elt_type* elt_array = (elt_type*) malloc(32 * sizeof(elt_type));

19.22

TABLE OF CONTENTS HC 19

19.24

ARRAYS ARE POINTER TYPES (4)

19.24

 
•	ARRAYS ARE NOT VALUE TYPES BUT POINTER TYPES 4
	ASSIGNING AND COPYING ARRAYS
In  
	int n1 = 13, 
	    n2;
	n2 = n1;

the value of n1 is assigned to n2.
In  
	int n1[5] = {0, 1, 2, 3, 4}, 
	    n2[5];
	n2 = n1;

the value of n1 is not assigned to n2.
The values of n1 and n2 are constant pointers
and did you ever write an assignment like 13 = 17;?

Question: How do you copy arrays in C?
First answer: inline and elementwise!

19.23

TABLE OF CONTENTS HC 19

19.25

COPYING AN ARRAY

19.25

Inline and elementwise!

	int i; for (i = 0; i < 5; i++) n2[i] = n1[i];
	
A second answer: define a functions to copy arrays.
Now you have to make some design decisions!!
•	Do you want your function to allocate memory for the copy?
	or is the memory to store a copy already available?
•	Do you want your function to return the copy as its return value?
	or do you prefer a reference parameter?
	Here I treat the situation that memory to store a copy is already declared
	elt_type elts[32], copy[32];

After initializing and processing the array elts you want to make a copy.

	void make_copy(elt_type* dst, elt_type* src, int n) {
		while (--n >=0) 
			dst[n] = src[n]; 
	}
Usage:
	make_copy(copy, elts);

19.24

TABLE OF CONTENTS HC 19

19.26

STRINGS

19.26

A sequence of characters delimited by double quotes, like

	"Programming in C is fun!"

is called a string (the double quotes do not belong to the string).
Technically a string is just an array of char but in C arrays of char and strings 
are different. The internal representation of a string has the null-character '\0' 
at the end. This is the character with ascii-code 0.
The value of this character is 0 (the 1-byte 0!). Anyway its value is FALSE!
In the sequel we define and use the macro

	#define EOS  '\0'   // where EOS means End Of String

Notes:
•	char message[] = {'H','e','l','l','o','!'}
	is an array of char of length 6,
•	char message[] = {'H','e','l','l','o','!','\0'}
	is a string of length 6,
and
	char empty_message[] = {'\0'}
	is a character array of length 1 and a string of length 0!

19.25

TABLE OF CONTENTS HC 19

19.27

INITIALIZING STRINGS

19.27

Strings allow easier initializations 

	char message[] = {"Hello!"};
	char message[] =  "Hello!";

and the preferred size can be given as well

	char message[13] = "Hello there!";
	char message[64] = "Hello there!";
but
	char message[12] = "Hello there!"; // not a string!!

Usually however we will not use char array but we prefer char*.
Thus:

	char* s = "The string to be copied.";
	char* t = "The string to receive a copy.";

In both cases the internal representation is an array of char where the size
is given by the number of characters plus 1 (to accomodate EOS).

19.26

TABLE OF CONTENTS HC 19

19.28

THE LENGTH OF A STRING

19.28

 
The length of a string:

	int length(char* s) {
		int i = 0;
		while(s[i] != EOS) 
			++i;
		return(i);
	}

NOTES:
•	the test (s[i] != EOS) can be abbreviated to (s[i]) 
	since EOS == FALSE,
•	s[i] can be written *(s+i), and
•	what about a further abbreviation of the loop to

	int length(char* s) {
		int i = 0;
		while(s[i++]) ;
		return(i);
	}

19.27

TABLE OF CONTENTS HC 19

19.29

COPYING STRINGS

19.29

Copying strings: 
	void stringcopy(char* dst, char *src) {
		int i = 0;
		while(src[i] != EOS) {    // copy chars
			dst[i] = src[i];
			i++;
		}
		dst[i] = src[i];          // copy EOS
	}

should do the job if the actual argument that corresponds to the 
formal parameter dst can accomodate the content of src.

The next modification is of interest 
	void stringcopy(char* dst, char *src) {
		int i = 0;
		while((dst[i] = src[i]) != EOS) { // copy all!!
			i++;
		}
	}
	
Since copying takes place before the test, 
EOS is copied as the last character just before the loop terminates. 

19.28

TABLE OF CONTENTS HC 19

19.30

COPYING STRINGS

19.30

In that case explicit testing against EOS is superfluous as well! 

	void stringcopy(char* dst, char *src) {
	
		while(*(dst++) = *(src++)) ; // copy, update, test
	}

Tricky? Yes! But this is sophisticated C, man!

•	*dst = *src; copy current character *src into dst 

•	src++;       continue with next char from src
	dst++;       to be copied into next position in dst

•	any expression has a value and the value of 
		*(dst++) = *(src++)
	is the value of its lefthand side i.e. the character that has just been 
	copied and if this character is EOS the loop exits on FALSE!

19.29

TABLE OF CONTENTS HC 19

19.31

SURPRISES

19.31

Suppose the following code has been executed: 

	char* s = "The string to be copied.";
	char* t = "The string to receive a copy.";
	
	int s_length = length(s);      // yields 24 I believe
	int t_length = length(t);      // yields 29 I believe
	
	printf("string s reads: %s\n", s);
	printf("string t reads: %s\n", t);
	
	stringcopy(t, s);

	printf("string s reads: %s\n", s);
	printf("string t reads: %s\n", t);
	
Then what dou you expect for output from string t?

19.30

TABLE OF CONTENTS HC 19

19.32

COMPARING STRINGS

19.32

And what output do you expect when the characters of string t are 
printed one after the other?
	
	int i;
	for (i = 0; i < t_length; i++) 
		printf("%c", t[i]);
	printf("\n");

Comparing strings:
Return the ascii-code difference for the first character in which two strings
differ and 0 if they are equal.

	int stringcompare(char* s, char* t) {
		while (*s == *t) {
			if (*s == EOS) // equal and eos 
				return(0);
			s++; 
			t++;
		}
		return((int)(*s - *t)); // nog effe sjekke
	}
	

19.31

TABLE OF CONTENTS HC 19

19.33

CONCATENATING STRINGS

19.33

Suppose string s has enough memory to append the characters of string t
to it on its rigth hand side.

Proof that the following function performs a correct job
	void stringconcat(char s[], char t[]) {
		int i = 0, j = 0;
		for ( ; s[i]; i++) ;
		for ( ; s[i] = s[j]; i++, j++) ;	
	}

Transform this function into the even more sophisticated definition
	void stringconcat(char s[], char t[]) {
		while (*s) s++;
		while (*s++ = *t++) ;
	}

What about?
	void stringconcat(char s[], char t[]) {
		while (*s++) ;
		while (*s++ = *t++) ;
	}
	

19.32

TABLE OF CONTENTS HC 19

19.34

TEST jpg

19.34

reallocated to 20.01
test

	
test

19.33

TABLE OF CONTENTS HC 19

19.35

19.35

reallocated to 20.02

19.34

TABLE OF CONTENTS HC 19

19.36

INSERTION SORT

19.36

reallocated to 20.03

19.35

TABLE OF CONTENTS HC 19

19.37

BINARY SEARCH

19.37

reallocated to 20.04

19.36

TABLE OF CONTENTS HC 19

19.38

BINARY SEARCH

19.38

reallocated to 20.05

19.37

TABLE OF CONTENTS HC 19

19.01

TABLE OF CONTENT HC 19

TOC

TOC