Pointers Data Structure 補充單元 2019/1/1

Introduction If you want to be proficient in the writing of code in the C programming language, you must have a thorough working knowledge of how to use pointers Unfortunately, C pointers appear to be rather unfriendly Here, let try to introduce for the first time what pointer is all about … 2019/1/1

get a feeling on C’s variables … A variable in a program is something with a name, the value of which can vary. When we declare a variable we inform the compiler of two things, the name of the variable the type of the variable. 2019/1/1

get a feeling on C’s variables … The way the compiler and linker handles this is that it assigns a specific block of memory within the computer to hold the value of that variable The variable size of that block depends on the range over which the is allowed to vary 2019/1/1

Assigning specific blocks of memory to variables int i; short j; i=100; i j 2019/1/1

Size of Integer 2019/1/1

get a feeling on C’s variables … For example, we declare a variable of type integer with the name k by writing: int k On seeing the "int" part of this statement the compiler sets aside 4 bytes of memory (on a PC) to hold the value of the integer. It also sets up a symbol table. In that table it adds the symbol k and the relative address in memory where those 4 bytes were set aside. 2019/1/1

get a feeling on C’s variables … Int k, m; k = 2; m = k; There are two "values" associated with the object k. One is the value of the integer stored there (2 in the above example) and the other the "value" of the memory location, i.e., the address of k. 2019/1/1

get a feeling on C’s variables … int j, k; k = 2; j = 7; <-- line 1 k = j; <-- line 2 In line 1, j is interpreted as the “address” of j In line 2, j is interpreted as the “value” stored in address of j 2019/1/1

Example 我如何將 variable (變數) 的 address (位址) 列印出來? Int i; printf(“%p”,&i) 2019/1/1

2019/1/1

32-bit vs 64-bit #include <stdio.h> int main() { int i; long j; printf("size of int = %d\n", sizeof(i)); printf("size of long = %d\n", sizeof(j)); printf(“Address of variable I = %p\n", &i); printf(“Address of variable J = %p\n", &j); } 2019/1/1

32-bit vs 64-bit 2019/1/1

%gcc -m32 -o out32 c.c %gcc -m64 -o out64 c.c 32-bit vs 64-bit 2019/1/1

32-bit vs 64-bit %./out32 size of int = 4 size of long = 4 address of variable I = 0xffffdc10 address of variable J = 0xffffdc0c FreeBSD AMD64 supports up to 1 TB MM %./out64 size of int = 4 size of long = 8 address of variable I = 0x7fffffffeaec address of variable J = 0x7fffffffeae0 2019/1/1

思考一下 … 所以, 當我們看到一個 C 的變數時, 它有時代表的意義是該變數的 “位址”,有時則代表該變數內存的 “值” 通常當變數出現在 “=” 左邊時,其意義是該變數的 “位址” 而通常當變數出現在 “=” 右邊時,其意義是該變數的 “值” 看來, 有點自由心證味道! 那, 我們可不可以有個變數, 它很明確地就是儲存 “位址”? 2019/1/1

儲存 “位址” 的變數 Yes! Such a variable is called a pointer variable In C when we define a pointer variable we do so by preceding its name with an asterisk (*). In C we also give our pointer a type which, in this case, refers to the type of data stored at the address we will be storing in our pointer. For example, consider the variable declaration: int *ptr; ptr : A pointer variable that point to address of an integer *ptr : value stores in the memory pointed to by ptr 2019/1/1

Example Int *ptr; int k; ptr = &k;  ptr stores address of k *ptr = 7;  *ptr store its “value” 可以這樣做類比 ptr  &k *ptr  k 注意 : ptr 如果沒有給初值, 預設值是 null (or 0) if (ptr == NULL) … 2019/1/1

Assigning specific blocks of memory to variables int *ptr; int k; ptr = &k; *ptr=7; 1004 ptr 7 k 2019/1/1

Example 2019/1/1

為什麼需要宣告 pointer 的 type? 因為事先宣告 ptr 指向的是 integer, 址值 + 4 byte 2019/1/1

Void pointer? void *ptr; Void : 空的 較好的解釋是 : generic pointer (不是某種特定型態, 例如 integer or character, 的 pointer) You cannot compare an integer pointer to a character pointer But you can compare them to a void pointer 2019/1/1

Dynamic Allocation of Memory There are times when it is convenient to allocate memory at run time using malloc(), calloc() Using this approach permits postponing the decision on the size of the memory block need to store an array, for example, until run time. Or it permits using a section of memory for the storage of an array of integers at one point in time, and then when that memory is no longer needed it can be freed up for other uses, such as the storage of an array of structures. 2019/1/1

Pointers and Dynamic Allocation (配置) of Memory When memory is allocated, the allocating function (such as malloc(), calloc(), etc.) returns a pointer. 2019/1/1

Example void *ptr; ptr = (void *)malloc(10 * sizeof(int)); if (ptr == NULL) { ………. } 動態地 allocates 10 個 integers 的空間 <重要>動態建立的 memory 不用時, 記得要 set it “free” free (ptr); 2019/1/1

Dynamic Array 動態陣列 #include <stdio.h> #include <stdlib.h> int main() { int *ptr, size,i; printf("Please input the array size:"); scanf("%d", &size); ptr = (int *)malloc(sizeof(int)*size); for (i=0; i<size; i++) ptr[i]=i; // *(ptr+i) = i; for (i=0; i<size; i++) printf("ptr[%d]=%d\n", i,ptr[i]); } 2019/1/1

Pointers and Structures 繼續討論之前, 先 “醞釀” 一下 C 語言之主程式/副程式呼叫(另一)副程式時參數的傳遞是採 call by value (傳值) 假設, 我們需要在副程式呼叫時傳遞一個很大的 structure (e.g., 100 bytes 那麼大), 且頻率很高  BAD IDEA! 那 … 怎麼辦? 何不傳遞一個指向特定 structure 的 pointer! 2019/1/1

Int maximum(int x, int y) int max; if (x>= y) max = x; else max=y; main() { int max, x[10000],y[10000]; …. max = maximum(x, y); } Int maximum(int x, int y) int max; if (x>= y) max = x; else max=y; return (max); 2019/1/1

But, what is a structure? Let’s see array first … To represent somebody’s name no more than 20 characters … char name[20]; How about representing 50 students’ name in a class? char name[50][20]; 2019/1/1

Now, what about representing more of 50 students’ …? Include name, ID, gender, address, etc char name[50][20]; char ID[50][10]; int gender[50]; char address[50][100]; A bit awkward, right? 2019/1/1

How about this … Define a new data types, like “student_type”, which aggregate name, ID, gender & address together?  This is what structure does For example: struct student_type { char name[20];       char ID[10];      int gender char address[100]; } 2019/1/1

Then … In 宣告： To access: struct student_type student[50]; student[0]->name student[10]->ID student[49]->gender etc 2019/1/1

Structure Data Type 2019/1/1

curr = (NODE *)malloc(sizeof(item)); curr->data = i; void main() { NODE * curr, * head; int i; head = NULL; for(i=1;i<=10;i++) { curr = (NODE *)malloc(sizeof(item)); curr->data = i; curr->next = head; head = curr; } curr = head; while(curr) { printf("%d\n", curr->data); curr = curr->next ; #include <stdlib.h> #include <stdio.h> typedef struct node { int data; struct node * next; } NODE; NODE *next; data NODE *next 2019/1/1

2019/1/1

以下所有討論前提… under “32-bit 作業系統” 2019/1/1

Sample Code & Explanation 定義一個新的 data type, 名稱為 NODE, 包含一整數及一指標 2019/1/1

程式執行前 2019/1/1

Sample Code & Explanation 定義一個新的 data type, 名稱為 NODE, 包含一整數及一指標 這段程式 不會 在記憶體新增佔用空間 2019/1/1

NODE 宣告完後 NO Change 2019/1/1

Sample Code & Explanation 宣告 curr 及 head 為指向某一 NODE 的指標 這段程式 會 在記憶體新增佔用空間 2019/1/1

NODE *curr, *head 宣告完後 curr head 佔用空間多大? Why? 2019/1/1

如果是這樣宣告 … NODE curr, head; curr head 佔用空間多大? Why? 2019/1/1

Sample Code & Explanation 動態地向系統要一個 NODE 的記憶空間, 並將此記憶空間的位置儲存在 curr 中 這段程式 會 在記憶體新增佔用空間 2019/1/1

malloc 宣告完後 NODE 的大小(佔的記憶空間) = 4 bytes (int) + 4 bytes (address) 1016 2019/1/1

Sample Code & Explanation For loop 之 i=0 iteration 執行完後 … 2019/1/1

For loop 之 i=0 執行完後 … curr head 將 0 儲存至透過 malloc新獲得之NODE記憶位置的 data 欄位 讓 head 也指向此新獲得之記憶位置, 換句話說, head 所在位置儲存的資料內容是 1016, 也就是新增 NODE 之 address (Next Slide) 2019/1/1

For loop 之 i=0 執行完後 … curr 1016 1016 head 2019/1/1

For loop 之 i=0 執行完後 … Address curr 1016 1016 head 2019/1/1

Sample Code & Explanation For loop 之 i=1 iteration 執行過程 … head = curr 執行前 2019/1/1

For loop 之 i=1 執行過程 … curr 2004 1016 head 1 1016 2019/1/1

For loop 之 i=1 執行完後 … curr 2004 2004 head 1 1016 2019/1/1

用熟悉的表示方式 … (i=1) curr head 1 2019/1/1