15.txt

一個計算機系教授的上課講義 主要是教導學生使用C語言編寫程序

CS 1355
Introduction to Programming in C
Monday 2006.10.30 (Week 8)
Lecture notes (at http://r638-2.cs.nthu.edu.tw/C/notes/15.txt)

Chapter 7: Pointers

- Pointer declarations
- Pointer operators
- Simulating passing parameters by reference

What is a pointer?
- a pointer is a "memory address"
  - conceptually, an unsigned integer
  - the value of the memory address has an R-value,
  - a pointer variable has both an L-value and an R-value
- indirect access
  - to "reference" a memory location
  - to "dereference" a pointer

Declaration:
- to declare an integer
	int N;
- to declare a "pointer to an integer"
	int *p;
  => this declares p as a pointer variable to an integer.

What can you assign to a pointer variable?
	p = &N;
  => this means p (as a pointer) is assigned 
     the "address of" integer variable N.
& is the "address-of" operator (right-associative)
  &N  where the N must have an L-value
  it is an error to say  &23  or &"hello world"
  &N  has an R-value (that is, it's an address),
      but no L-value!!
  (you can't say &N = 3; )

Once you have a pointer, you can dereference it as
	*p
  *p is the "content-of" operator (also right-associative)
  *p is really like the original variable (in this case N)
  it has both L-value and R-value

NULL pointer:
- NULL is a pre-defined macro name
- it has the value of 0 (false value).

Example:
void increment(int *n) {
	(*n)++;
}
int main() {
	int i;
	for (i=0; i<10; increment(&i)) {
		printf("%d ", i);
	}
	printf("\n");
}

Note:
increment(int *n) takes a "pointer of" an integer variable
  (*n) is the same as i in main()
  (*n)++ effectively does i++ for main()

What if you wrote it as
void increment(int n) {
	n++;
}
int main() {
	int i;
	for (i=0; i<10; increment(i)) {
		printf("%d ", i);
	}
	printf("\n");
}

=> it will go into an infinite loop!!
  because increment(i) passes the "R-value" of i to the function,
  and the parameter n (a local variable of increment()) copies the R-value.
=> since n is local to increment(), n++ is local and does not affect
   main()'s variable i.
=> therefore, i never changes, and it loops forever.

Book example
- Cube by Value (use function's return value)
- Cube by Reference (pass a pointer, modify the variable)

Cube by Value:
	int cube(int n) {
		return n * n * n;
	}
You can call it with any int R-value (expression); no need to
decare any variable
	int main() {
		printf("%d\n", cube(10));
	}

Cube by Reference: must put the value in a variable, pass the pointer,
and the cubeByRefernce() function modifies it.
	void cubeByReference(int *p) {
		*p = (*p) * (*p) * (*p);
	}
	/* no return value */
To call it, you must declare an int variable, put the value into it,
and pass reference 
	int main() {
		int x = 3;
		cubeByReference(&x);
		printf("%d\n", x);
	}


const usage: (const means "constant")
- pointer may be const or nonconst
- data may be const or nonconst

Therefore, four possible combinations of pointer variable vs. data privileges)
- const pointer to const data (neither pointer nor data can change)
- const pointer to nonconst data (pointer can't change, data can)
- nonconst pointer to constant data (pointer variable can change,
  but data must be immutable data -- e.g., string literal)
- nonconst pointer to nonconst data (no restrictions)

What is constant depends on where the qualifier is placed.
	const int const *p;
This means
	const int: the data being referenced is const
	const *p:  the pointer variable itself should not change.


Pointers may also be assigned, not just passed:
Example: use pointers instead of index

int totalGrade(int g[ ], int size) {
	int *p, total = 0;
	for (p = &g[0]; p < &p[size]; p++) {
		total += *p;
	}
}

Why use pointer instead of index?
- potentially faster: 
  - in the case of index, it may have to
    compute address (&g + i * 4), dereference,
    then add to total.
  - in the case of pointer, it just needs to
    compute p++ (which actually means p += 4 because int is 4 bytes)
- for dynamic data structures, 
  where you establish links

"const" qualifier
- has two meanings
  1. as a variable,
     it means the value is a constant
     (has only R-value, no L-value)
  2. as a parameter,
     it means the function promises to use it as a constant (use R-value only),
     whether or not the R-value comes from a constant or a variable.
  => however! it is only a promise.
     A pointer may violate this primise!

An array initializer:
        const char k[] = "hello world\n";
  a 13-element char-array is allocated and initialized

A pointer-variable initializer:
        char *p = "world peace\n";
  the string "world peace\n" is set up as read-only data,
  and p references this location.

The C language may try to prevent access, 
but the data may still be modified through a pointer!
(the compiler may generate a warning)




Instead of char s[ ], if you declare a "pointer"
	char *t = "hello";

Important: t is a "pointer" (variable that contains a memory address)
Difference:
- t itself is 4 bytes (on most machines). 
  it contains a memory address.
- t does not contain the string itself; t contains the "location of" the string.
- t gets initialized to the address of a string constant (immutable)
- s[0], s[1], ...s[5] actually get initialized individually.


gets(char *buf)   means "get string" (s = string)
 Try it out:
#include <stdio.h>
int main() {
	char s[10];
	printf("type something: ");
	gets(s);
	printf("you typed %s\n",s);
}
=> similar problem as scanf(): array size is not checked!!
   When you run, you may get the warning
% ./a.out
warning: this program uses gets(), which is unsafe.
type something: abc
you typed abc

Better way is to use
fgets(char *buf, int len, FILE* stream)
=>  specifies size explicitly, safer to use.
#include <stdio.h>
int main() {
	char s[10];
	printf("type something: ");
	fgets(s, 10, stdin);
	printf("you typed %s\n",s);
}

./a.out
type something: abc
you typed abc

(fgets() includes the \n, whereas gets() does not)

But, if you try passing a pointer to constant data, you will
get a runtime error ("Bus error")
e.g.,	fgets("hello world", 12, stdin);


Book example:
Bubble sort using call by reference
(see lecture 13)

we had the routine
1	void
2	bubbleUp(int a[], int i) {
3		/* 
4		   purpose: compare a[i] and a[i+1], 
5		   switch them if a[i] > a[i+1]
6		   assumption: a has at least i+2 elements
7		 */
8		if (a[i] > a[i+1]) {
9			int temp = a[i];
10			a[i] = a[i+1];
11			a[i+1] = temp;
12		}
13	}

Lines 9-11 could be replaced with
	swap(&a[i], &a[i+1]);
where swap() is defined as

void swap(int *x, int *y) {
	int temp = *x;
	*x = *y;
	*y = temp;
}

How it works:
  &a[i] is the memory address of a[i]
  &a[i+1] is the memory address of a[i+1].
swap() takes the two addresses,
- first copy the content at x into a temporary
- overwrite the content at address x with content at address y
- overwrite the content at address y with original content of x (now in temp)

bubbleUp() works with only elements within array a[ ], 
but swap() works with any integer variables, inside or outside array a[ ].

Review: sizeof() operator
 tells you how big (how many bytes) the variable, type, or expression is.

sizeof(char) => 1 byte
sizeof(int) => 4 bytes
sizeof(2345) => also 4 bytes, because it is an int literal
sizeof("hello world") => 12 bytes, including \0
sizeof(char*) => usually 4 bytes

Pointer arithmetic:
you can actually apply +, -, operators on pointer expressions
Example: print an array of integers. previously, we would do
#include <stdio.h>
void printIntArray(int A[ ], int count) {
	int i;
	for (i = 0; i < count; ; i++) {
		printf("%d\n", A[i]);
	}
}

We could also do
#include <stdio.h>
void printIntArray(int A[ ], int count) {
	int *p; 
	for (p = A; p < &A[count]; p++) {
		printf("%d\n", *p);
	}
}

Note: p++ => what does this mean!??
it does not mean +1; 
it actually means +sizeof(int)!!
(normally sizeof(int) is 4, so p++ actually adds 4 to the value of p!!)

Pointer arithmetic: when you do + or - operator on pointers,
  you are actually scaling the RHS by sizeof the data type.
  Actually, both
	p + 3 
	3 + p 
  give you the same result.
However, you should not try to add two pointers together!

	int A[10];
	int *p = A, *q = A;
	printf("%p\n", p+q);

it is totally meaningless to add two pointers together.
You will get a compiler error ("invalid operands to binary +")

We could write the code above also as
#include <stdio.h>
void printIntArray(int A[ ], int count) {
	int *p;
	for (p = A; p < A + count; p++) {
		printf("%d\n", *p);
	}
}

(slightly easier to read than &A[count])
i.e., &A[count] is identical to A+count

For pointer subtraction, you can get the "number of elements between
the two pointers"

#include <stdio.h>
int elementsBetween(int *p, int *q) {
	return p - q;
}

if you call elementsBetween(&A[20], &A[30]),
you get -10
(even though the addresses are -40 apart.)

pointer minus integer => pointer
pointer minus pointer => integer

Book example: copying a string to a string buffer

void copy1(char *s1, const char *s2) {
	/* copy s2 to s1. use index */
	int i;
	for (i = 0; s2[i] != '\0'; i++) {
		s1[i] = s[2];
	}
}

the loop can also be written as
	for (i = 0; s1[i] = s[2]; i++) {
	}

because s1[i] = s2[i] is an assignment expression, 
yields the value of s[2],
and it is interpreted as a boolean (implies comparison with '\0')
true if != '\0', false if ==.

The pointer version

void copy2(char* p1, char* p2) {
	for ( ; (*p1 = *p2) ; p1++, p2++ ) {
	}
}

note that *p1 = *p2 is the same as p1[0] = p2[0].

Array of pointers
Example

char *suit[4] = { "Hearts", "Diamonds", "Clubs", "Spades" };

what does this mean:
- this declares a 4-element array named suit,
  each element suit[0], ... suit[3] is a (char*) character-pointer
- This does not mean "a pointer to an array of 4 characters!
  How to declare it?
	typedef char BufferType[4]; 
	BufferType *ptr; /* pointer to 4-char buffer */

It initializes each element of suit to a string.

Question: if you have the same string literal multiple times,
	do you get the same address or different address?
Answer: should be the same
Why?  because string literals are kept in a "constant pool".
  The literals are known at compile time.
  They are stored just once.

This is not the same as two-dimensional array!
	char matrix[4][9] = { "Hearts", "Diamonds", "Clubs", "Spades" };
because this allocates a matrix of 36 bytes (= 4 rows x 9 columns)
and matrix[0], ... matrix[3] have only R-value; they have no L-value!
(but matrix[0][0], ... matrix[3][8] have L-value)

In the case of suit[0] ... suit[3] has L-value, 
but suit[i][j] might not actually exist, depending on whether
suit[i] itself is a null pointer, and if not, depends on 
whether suit[i] points to a buffer with at least j+1 elements.