6.087 Practical Programming in C, lec5

Pointers and memory addressing. Arrays and pointer arithmetic. Strings.

Searching and sorting algorithms.

Pointers and addresses

• Pointer: memory address of a variable

• Address can be used to access/modify a variable from anywhere

• Extremely useful, especially for data structures

• Well known for obfuscating code

C中的指针很迷人，神秘而又强大。它自身其实很简单，就是内存的地址。这使得人们可以直接修改内存，从而可以在理论上做任何事情。其缺点是复杂性大幅上升。

Physical and virtual memory

• Physical memory: physical resources where data can be storedand accessed by your computer

• cache

• RAM

• hard disk

• removable storage

• Virtual memory: abstraction by OS, addressable spaceaccessible by your code

随内存的价格不断下降，计算机能用的内存将更多地取决于虚拟内存，32位的寻址空间太小，将逐渐被64位取代。

Virtual memory

• How much physical memory do I have?

Answer: 2 MB (cache) + 2 GB (RAM) +100 GB (hard drive) + . . .

• How much virtual memory do I have?

Answer: <4 GB (32-bit OS),typically 2 GB for Windows, 3-4 GB for linux

• Virtual memory maps to different parts of physical memory

• Usable parts of virtual memory: stack and heap

• stack: where declared variables go

• heap: where dynamic memory goes

利用栈的特性可以方便地控制程序的执行顺序，堆则用来分配较大的数据和静态数据。堆中的指针存储在栈中，我想这也是C中使用指针的一个重要原因。

我认为C程序的执行过程可以看作遍历一棵Block树的过程，栈可以方便地实现这个遍历过程，因此将内存分配为栈空间是很自然的。

Addressing variables

• Every variable residing in memory has an address!

• What doesn’t have an address?

• register variables

• constants/literals/preprocessordefines

• expressions (unless result is avariable)

• How to find an address of a variable? The & operator

int n = 4 ;

double pi = 3.14159;

int ∗pn = &n ; / ∗ address of integer n ∗ /

double ∗ ppi = &pi ; / ∗address of double pi ∗ /

• Address of a variable of type t has type t *

C中除register类型外，其它变量都有地址。

Dereferencing pointers

• Accessing/modifying addressed variable:

dereferencing/indirection operator *

/ ∗ prints "pi = 3.14159\n" ∗ /

printf ( "pi = %g\n" ,∗ ppi ) ;

/ ∗ p i now equals 7.14159 ∗ /

∗ppi = ∗ppi + ∗pn;

• Dereferenced pointer like any other variable

• null pointer, i.e. 0 (NULL): pointer that does not referenceanything

*操作符的实现应该有两步，首先确定指针的类型，其次从指针的地址开始从内存中读取相应类型大小的数据段。这里也体现了类型的方便之处，可以确定变量的大小，从而使对内存的操作更为容易。

Variables passing out of scope

• What is wrong with this code?

#include < s t d i o . h>

char ∗ get_message ( ) {

char msg [ ] = "Aren’tpointers fun?" ;

return msg ;

}

int main (void) {

char ∗ string = get_message ( ) ;

puts(string) ;

return 0;

}

• Pointer invalid after variable passes out of scope

传自动变量的地址出来是C程序中常见的错误，如果想返回一个地址，那么可以返回堆中的地址，如malloc分配的，但这样也有一个风险，就是malloc和free不在同一个程序块中，free操作容易出错，所以这种方式也不鼓励。

The sizeof() operator

• For primitive types/variables, size of type in bytes:

int s = sizeof(char); /∗ == 1 ∗/

double f; /∗ sizeof ( f ) == 8 ∗/(64-bit OS)

• For primitive arrays, size of array in bytes:

int arr [8]; /∗ sizeof ( arr ) ==32 ∗/ (64-bit OS)

long arr [5]; /∗ sizeof ( arr ) ==40 ∗/ (64-bit OS)

• Array length:

#define array_length(arr) (sizeof (arr)==0 ? 0 : sizeof(arr)/sizeof((arr)[0]))

sizeof是我在写C代码时常用的一个运算符，因为我对内存的分配总是感到很恐怖，好在sizeof帮助了我。使用sizeof的一个重要好处就是增强了程序的通用性，这对于早期的C至关重要。我想sizeof是通过读取程序内部的类型表，从而获得类型的大小，而不是通过计算获得。看来，不同大小的数组其类型也是不一样的.

Pointer arithmetic

• Suppose int ∗pa = arr ;

• Pointer not an int, but can add or subtract an int from apointer:

pa + i points to arr[i]

• Address value increments by i times size of data type

Suppose arr[0] has address 100. Thenarr[3] has address 112.

指针的代数运算又一次影响了我对+运算符的看法，这里的+运算符的确是重载了。在执行+时，编译器检查两个变量，如果有一个是指针，那么就启动指针的代数运算。

Discussion of quicksort

• Not stable (equal-valued elements can get switched) inpresent form

• Can sort in-place – especially desirable for low-memoryenvironments

• Choice of pivot influences performance; can use random pivot

• Divide and conquer algorithm; easily parallelizeable

• Recursive; in worst case, can cause stack overflow on largearray

记得在IBM面试时他们让我写QuickSort，当时我用了两个数组，当时面试官就指出可以本地排序，那会儿要是复习一下该多好。