Microsoft Word - About_C_DynamicMemoryAllocation.doc

Size: px

Start display at page:

Download "Microsoft Word - About_C_DynamicMemoryAllocation.doc"

瞬窦
6 years ago
Views:

1 (*) 動態記憶體配置為什麼需要使用動態記憶體配置? 更有效率的使用記憶體, 這包括可以在需要時才根據需求來配置適量的記憶體, 而不必一開始就宣告可容納最大可能大小的陣列 ; 另一個重要的情況則是可以突破堆疊 (stack) 的大小限制, 在堆積 (heap) 上宣告目前可用記憶體容許的最大空間在 C 中, 實現動態記憶體配置的方法 : DataType *ptr = (DataType*) malloc( 所需的記憶空間的 bytes 數 ); 其中 malloc(.) 如果成功會傳回型態是 void* 的位址 ; 若失敗則傳回 NULL 上述宣告中的 ptr 當配置成功時, 就會指向系統所給予這塊記憶體的起始位址精確地說, 這塊連續的記憶體空間可以用任意的資料型態來進行存取, 不過此刻為避免模糊了焦點, 所以就單純地以原來設定的方式來使用它例如 : 要配置 2000 個整數 (int) 型態的記憶體空間可以使用下列的程式碼 : int *data = (int*) malloc( sizeof(int)*2000); 這時我們發現到 sizeof(.) 重要性在此突顯出來了! 另外, 一個好的習慣希望大家在配置記憶體時能夠養成 : 宣告後要做配置成功與否的檢查! if ( ptr==null ) // 當失敗時該做的收尾工作! ; 此外, 有件大家必須牢記也是在學習 C 語言記憶體配置時最容易犯錯的事情 : 忘記釋放之前配置的記憶體, 造成記憶體漏失的問題! 這些向系統請求的記憶體空間, 必須要由程式設計者自己釋放它們記憶體漏失問題有時就發生在 : 1) 或許過早釋放這些記憶體導致稍後讀不到它們 ; 2) 或者是使用後竟忘了釋放它們對系統而言, 這些記憶體原則上被為視為使用者專屬, 系統不再具有控制權, 因此釋放的動作要由程式寫作者來決定與實作一旦因記憶體漏失而破壞記憶體的連續性時, 可能使得稍後要使用的記憶體空間遭到截斷, 以致於接下來系統能再配置的記憶空間大小受到很大的影響, 甚或更嚴重時的發生配置失敗的狀況以實例說明動態記憶體配置與釋放的過程 : int *data = (int*) malloc( sizeof(int)*2000); if ( data==null ) // 配置失敗時要進行的處置! ; // 對配置的記憶體進行需要的操作! : free(data); // 釋放已配置的記憶體 In C++, int *data = new int[2000]; if ( data==null ) // 配置失敗時要進行的處置! ; // 對配置的記憶體進行需要的操作! : delete [] data;

2 (*)C/C++ 隨機數值 (random number) 的產生與應用 1) 提供的函式 (function): int rand(void): 傳回介於 0 到 RAND_MAX(0x7FFF) 的正整數 void srand(unsigned seed): 指定的種子值即起始狀態 2) 使用 rand(), srand(.) 時, 需引用的 Header File: #include <stdlib.h> Part of file stdlib.h is listed below,... /* * RAND_MAX is the maximum value that may be returned by rand. * The minimum is zero. */ 4) 一個利用 rand() 產生十個隨機數的例子 : #include <stdlib.h> #include <stdio.h> int main(void) printf("ten random numbers from 0 to 99\n\n"); for (int i=0; i<10; i++) printf("%d\n", rand() % 100); system( pause ); return 0; // 每次執行的結果是否相同? #include <stdlib.h> #include <stdio.h> int main(void) srand(1); // 重新設定隨機數的產生順序 printf("ten random numbers from 0 to 99\n\n"); for (int i=0; i<10; i++) printf("%d\n", rand() % 100); system( pause ); return 0; // srand(1) 參數的值會影響每次執行的結果嗎? 5) 一個讓每次執行均能產生不同隨機數的函式 :randomize() #include <stdlib.h> #include <stdio.h> #include <time.h> // for time_t // 利用擷取現在時間, 作為任意指定的 seed 值, 如此則每次執行所產生的 // 隨機數就會不一樣 void randomize() int i; time_t t; srand((unsigned) time(&t)); int main(void) randomize(); printf("ten random numbers from 0 to 99\n\n"); for (int i=0; i<10; i++) printf("%d\n", rand() % 100); system( pause ); return 0;

3 6) 產生任意範圍的隨機數 : 要產生 0 ~ 99 的隨機數 :rand() % 100 要產生 0 ~ N-1 的隨機數 :rand() % N 要產生 a ~ b 的隨機數 :a + (rand() % (b-a+1)) 所以要產生 1 ~ 6 的隨機數 :( 可以用來模擬骰子的投擲點數 ) 1 + (rand() % (6-1+1)) => 1 + (rand() % 6) #include <stdlib.h> #include <stdio.h> #include <time.h> // for time_t void randomize() int i; time_t t; srand((unsigned) time(&t)); int random(int N) // return the value between 0 ~ N-1 return ( rand() % N ); int main(void) int k, number[6], index, total=1000; for (k=0; k<6; ++k) number[k]=0; // 設初始値 randomize(); for (k=0; k<total; ++k) index = random(6); // get the value between 0~5 number[index] = number[index] + 1; printf(" 模擬骰子投擲 %d 次的結果 \n\n", total); for (k=0; k<6; ++k) printf("[%d]:%4d\n", k+1, number[k]); system( pause ); return 0; 7) 試問如何產生小數點以下三位, 且值小於 1 的隨機小數? ( 提示 : 產生 0~999 的隨機整數, 再除以 1000 即可 ) (*) srand(int seed) 隨機數是透過一開始給定的種子值 seed, 接著進行後續的迭代計算來求出下一個隨機數這也就是說儒果每次開始的狀態都一樣, 即種子值相同時那麼接續產生的隨機數列也會是一樣的! 這對於希望能儘可能每次出現不同莊況的應用而言, 應該是不樂見的結果不過如果我們希望可以在稍後重現這個隨機數列, 如重印考試座位表或輪班表時, 固定的種子值能夠讓我們再次得到某一特定的隨機數列

4 例題 : 產生 10 個元素的 double 陣列, 將 1 到 10 的常用對數值存入其中並印出 #include <stdlib.h> // for malloc(.) and free(.) #include <math.h> // for log(.) void showdoubleten() int k, n = 10; // 動態配置記憶體, 用法同一般陣列 double *data = (double*) malloc( sizeof(double)*n ); // 檢查記憶體配置是否成功? if ( data==null ) return; for (k=0; k<n; ++k) data[k] = log(k+1) / log(10); printf("data[%d]= %.4f\n", k, data[k]); free( data ); // 勿忘! 釋放動態配置的記憶體! 例題 : 隨機產生元素 int 陣列的值, 並找出與你學號末碼相同的項數共有幾個? #include <stdlib.h> // for malloc(.) and free(.) #include <math.h> // for log(.) #include <time.h> // for time_t void randomize() int i; time_t t; srand((unsigned) time(&t)); int random(int N) // return the value between 0 ~ N-1 return ( rand() % N ); void showyourno(int no) int k, found=0, n = 10000; // 動態配置記憶體, 用法同一般陣列 int *data = (int*) malloc( sizeof(int)*n ); // 檢查記憶體配置是否成功? if ( data==null ) return; randomize(); for (k=0; k<n; ++k) data[k] = random(100); if ( no==data[k] ) printf("data[%d]=%d\n", k, data[k]); ++found; printf(" 共找到 %d 項!\n", found); free( data ); // 勿忘! 釋放動態配置的記憶體!

5 (*) 可以宣告多大的陣列 ( 靜態與動態 )? #include <stdio.h> #include <stdlib.h> void bigarrayinfunction() // stack int ary1[ 10000]; // stored in stack //int ary2[100000]; //int ary3[200000]; //int ary4[400000]; //int ary6[600000]; void dynamicarrayinfunction() int * ary; ary = (int*) malloc(sizeof(int)*600000); // stored in heap system("pause"); free(ary); int main(int argc, char *argv[]) bigarrayinfunction(); dynamicarrayinfunction(); system("pause"); return 0; 透過動態記憶體配置的方式, 可以宣告不受堆疊大小限制的陣列, 實用上非常重要!

6 (*) 不公平的骰子 (an unfair die) 例題 : 模擬一不公平骰子, 希望某一點數出現的機率是其他點數的兩倍 void unfairdie() int k, value, n=700; int dice[6] = 0; // 將所有的陣列元素設成 0 //randomize(); // 產生任意的隨機數 //srand(1); // 產生特定順序的隨機數 for (k=0; k<n; ++k) value = random(7); // 產生介於 0~6 的隨機數 switch( value ) case 0: case 1: ++dice[0]; break; // 機率是其他的兩倍, 包括 0 與 1 case 2: ++dice[1]; break; case 3: ++dice[2]; break; case 4: ++dice[3]; break; case 5: ++dice[4]; break; case 6: ++dice[5]; break; ; printf(" 模擬不公平骰子擲 %d 次的結果 \n\n", n); for (k=0; k<6; ++k) printf("point %d:%4d\n", k+1, dice[k]);

7 (*) 動態產生二維陣列先動態產生所需的列, 再設定各列要對應或指向的動態配置記憶區塊原則上 : 釋放記憶體的順序要與原先配置的順序反過來 DataType ** pptr; 指標的指標, 或者想成是指向某一陣列的指標 1) 具有相同 column 數的二維陣列 ( 矩形 ) (a) 動態產生各列所需的記憶體區塊 ( 產生 row 列, 再逐一設定 col 行 ) int** gen2darray(int row, int col) int r, c; int ** ary2d = (int**) malloc( (row)*sizeof(int*)); if ( ary2d==null ) return NULL; ary2d[r] = (int*) malloc( col*sizeof(int) ); if ( ary2d[r]==null ) // 一旦出錯所有稍早成功的配置均須釋放! for (c=r-1; c>=0; --c) free(ary2d[c]); return NULL; return ary2d; void release2darray(int** ary2d, int row) int r; free(ary2d[r]); void test2darray(int row, int col) int r, c; int** data = gen2darray(row, col); for (c=0; c<col; ++c) data[r][c] = r*10 + c; for (c=0; c<col; ++c) printf("data[%d][%d]=%2d ", r, c, data[r][c]); printf("\n"); release2darray(data, row);

8 (b) 先配置記憶區塊, 再將各列指標指向該區塊適當位址 ( 產生 row+1 列 ) int** gen2darray(int row, int col) int r, c; int ** ary2d = (int**) malloc( (row+1)* sizeof(int*)); if ( ary2d==null ) return NULL; ary2d[row] = (int*) malloc( row*col*sizeof(int) ); if ( ary2d[row]==null ) return NULL; ary2d[0] = ary2d[row]; for (r=1; r<row; ++r) ary2d[r] = ary2d[r-1] + col; // 指標的加減 return ary2d; void release2darray(int** ary2d, int row) free(ary2d[row]); void test2darray(int row, int col) int r, c; int** data = gen2darray(row, col); for (c=0; c<col; ++c) data[r][c] = r*10 + c; for (c=0; c<col; ++c) printf("data[%d][%d]=%2d ", r, c, data[r][c]); printf("\n"); 測試例 : test2darray(int row, int col); => test2darray(10, 5);

9 2) 可以有不同 column 數的二維陣列 ( 非矩形或鋸齒形 ) int** gen2darrayvar(int row, int col[]) // 此處的 col 是陣列! int r, c; int ** ary2d = (int**) malloc( (row)*sizeof(int*)); if ( ary2d==null ) return NULL; ary2d[r] = (int*) malloc( col[r]*sizeof(int) ); if ( ary2d[r]==null ) for (c=r-1; c>=0; --c) free(ary2d[c]); return NULL; return ary2d; void release2darrayvar(int** ary2d, int row) int r; free(ary2d[r]); void test2darrayvar(int row, int col[]) int r, c; int** data = gen2darrayvar(row, col); for (c=0; c<col[r]; ++c) data[r][c] = r*10 + c; for (c=0; c<col[r]; ++c) printf("data[%d][%d]=%2d ", r, c, data[r][c]); printf("\n"); 測試例 : int cols[] = 5,4,3,5,2; test2darrayvar(int row, int col[]); => test2darrayvar(5, cols);

10 (*) 一維陣列的記憶體配置與釋放 int *ptr=null; ptr = (int*) malloc( N*sizeof(int) ); if ( ptr==null ) return; free(ptr); (*) 二維陣列 (row, col) 的記憶體配置與釋放 - 方法 1 1) 記憶體的配置 : int ** ary2d = (int**) malloc( row *sizeof(int*)); ary2d[r] = (int*) malloc( col *sizeof(int) ); // 逐一配置 2) 記憶體的釋放 : free(ary2d[r]); (*) 二維陣列 (row, col) 的記憶體配置與釋放 - 方法 2 1) 記憶體的配置 : int ** ary2d = (int**) malloc( (row+1) *sizeof(int*)); // 先配置一塊連續的記憶體 : ary2d[row] = (int*) malloc( row*col *sizeof(int) ); // 將各個陣列指標指向各列正確的位址 : ary2d[0] = ary2d[row]; for (r=1; r<row; ++r) ary2d[r] = ary2d[r-1] + col; // 指標的加減 2) 記憶體的釋放 : free(ary2d[row]); (*) 在配置記憶體後, 要立即檢查是否正確配置 ; 使用後務必記得釋放該配置的記憶體

11 連續的記憶連續的記憶體連續的記憶體C 程式語言 - 動態記憶體配置介紹 (richwang) ptr Heap( 堆積 ) ptr2d ptr2d+1 ptr2d+2 ptr2d+row-1 體不L 1 L 2 尚未或忘了釋放的記憶體此時雖有最大為 L 的空間, 也僅能一次選用 L 1 或 L 3 L L 3 ptr2d+row ptr2d ptr2d+1 ptr2d+2 記憶體配置的說明圖示

12 (*) 利用 typedef 簡化資料的表示 struct StudentS char no[11+1]; int chi; int eng; int math; ; // 分號 ; 不可或缺! 使用法 :(In C) struct StudentS stu, *pstu; // pstu 是指標 typedef struct char no[11+1]; int chi; int eng; int math; Student, *pstudent; // Student, pstudent 現在都是自訂的資料型態使用法 : Student stu; pstudent pstu; // pstu 是指標 void genstudent(int N) // 有三種使用方式 : Student *stu = (Student*) malloc(sizeof(student) * N); //struct StudentS *stu = (Student*) malloc(sizeof(struct StudentS)*N); //pstudent stu = (pstudent) malloc(sizeof(student) * N); if ( stu==null ) printf("memory allocation failed!\n"); return; int k, c; randomize(); for (k=0; k<n; ++k) sprintf(stu[k].no, "S9917%03d", k+1 ); // 另一種寫法 stu[k].chi = random(101); stu[k].eng = random(101); stu[k].math = random(101); printf("%s: %d, %d, %d.\n", stu[k].no, stu[k].chi, stu[k].eng, stu[k].math); free(stu); // 有借要還! 一定要記得釋放記憶體! (*) sprintf( 儲存輸出的字串變數, 格式字串 [, 參數列 ]); sprintf(.) 的功能全同於 printf(.) 差別在 :printf 會將結果送往 stdout( 通常就是螢幕 ); 而 sprintf 會將相同的結果寫入字串變數中不過要注意的是, 用來儲存輸出的字串的空間不可太小以免資訊無法正確存入, 導致訊息失真

13 (*) C 語言中對記憶體內容的操作 1) 設定記憶體資料的方法 : void *memset(void *s, int c, size_t n); fromaddr, tovalue, bytes 2) 搬移記憶體資料的方法 : void *memmove(void *dest, const void *src, size_t n); toaddr, fromaddr, bytes (destination: 目的地 ; source: 來源 ) // // #include <mem.h> // for using memset(.) and memmove(.) // 或直接使用 #include <string.h> 即可 void testmemfun() char buffer[] = "Hello world!\n"; // 最後有換行字元! printf("buffer before memset: %s\n", buffer); memset(buffer, '#', strlen(buffer) - 1); // strlen 求字串長度 printf("buffer after memset: %s\n", buffer); //========================================================== char dest[] = "abcdefghijklmnopqrstuvwxyz "; char src[] = "******************************"; printf("destination prior to memmove: %s\n", dest); memmove(dest, src, 26); // memmove(toaddr, fromaddr, bytes) printf("destination after memmove: %s\n", dest); //========================================================== (*) 以記憶體搬移的方式實作陣列的元素插入在資料 c 前插入資料 x: 陣列或記憶體中原來的資料 :data[k] a b c d e f (1) 先把資料搬到後面 (memmove) a b c c d e f memmove(&data[3], &data[2], sizeof(int)*4); or memmove(data+3, data+2, sizeof(int)*4); 或逐一搬移資料, for (k=4; k>0; --k) data[2+k] = data[2+k -1]; (2) 插入資料 x: a b x c d e f data[2] = x; 或者是在將一陣列中某個元素的內容移到最前面時, 也可以用相同的方式這時需要更精確知道陣列的大小與哪個元素需要被搬移到哪個位置等資訊, 請同學自己想想看! value = data[index]; // index 從 0 開始! memmove(&data[1], &data[0], index*sizeof(datatype)); data[0] = value;

新・明解Ｃ言語入門編『索引』

新・明解Ｃ言語入門編『索引』 !... 75!=... 48 "... 234 " "... 9, 84, 240 #define... 118, 213 #include... 148 %... 23 %... 23, 24 %%... 23 %d... 4 %f... 29 %ld... 177 %lf... 31 %lu... 177 %o... 196 %p... 262 %s... 242, 244 %u... 177