Bài giảng Kỹ Thuật lập trình - Chương 3, Phần 2: Các kỹ thuật xây dựng chương trình phần mềm - Vũ Thị Hương Giang

và một số dòng trống được bỏ qua vì những hạn chế không gian • Phải tôn trọng các quy tắc trình bày mã nguồn khi viết CT thực tế – Trình tự thiết kế là lý tưởng • Trong thực tế, nhiều backtracking sẽ xảy ra Mức đỉnh • Phác thảo hàm main() int main(void) { for (;;) { if () { return 0; } if () { } } return 0; } Tinh chỉnh từng bước - Đọc 1 từ • nghĩa là gì? • Việc này khá phức tạp nên cần tách thành 1 hàm riêng #include enum {MAX_WORD_LEN = 20}; int main(void) { char word[MAX_WORD_LEN + 1]; int wordLen; for (;;) { wordLen = ReadWord(word); if () { return 0; } if () { } } return 0; } int ReadWord(char *word) { } The “End-of-File Character” • Các files không kết thúc bằng “EOF character”, vì không tồn tại ký tự đó • EOF là: – Một giá trị đặc biệt được hàm getchar() hoặc các hàm liên quan trả về để chỉ ra 1 lỗi vào ra – Được định nghĩa trong stdio.h (thường với giá trị -1) – Trong môi trường windows, có thể tương đương với mã ASCII của cụm phím tắt Ctl + Z Using EOF • Correct code • Equivalent idiom • Incorrect code int c; c = getchar(); while (c != EOF) { c = getchar(); } int c; while ((c = getchar()) != EOF) { } getchar() trả lại giá trị kiểu int cho tất cả các ký tự và ký hiệu EOF char c; while ((c = getchar()) != EOF) { } Tại sao ? Tinh chỉnh từng bước - Đọc 1 từ • ReadWord() function int ReadWord(char *word) { int ch, pos = 0; /* Bỏ qua whitespace. */ ch = getchar(); while ((ch == ' ') || (ch == '\n') || (ch == '\t')) ch = getchar(); /* Lưu các ký tự vào từ cho đến MAX_WORD_LEN . */ while ((ch != ' ') && (ch != '\n') && (ch != '\t') && (ch != EOF)) { if (pos < MAX_WORD_LEN) { word[pos] = (char)ch; pos++; } ch = getchar(); } word[pos] = '\0'; /* Trả về độ dài từ. */ return pos; } Tinh chỉnh từng bước - Đọc 1 từ • Hmmm. ReadWord() chứa 1 vài đoạn code lặp lại => tách thành 1 hàm riêng : IsWhitespace(ch) int ReadWord(char *word) { int ch, pos = 0; /* Bỏ qua whitespace. */ ch = getchar(); while (IsWhitespace(ch)) ch = getchar(); /* Lưu các ký tự vào từ cho đến MAX_WORD_LEN . */ while (!IsWhitespace(ch) && (ch != EOF)) { if (pos < MAX_WORD_LEN) { word[pos] = (char)ch; pos++; } ch = getchar(); } word[pos] = '\0'; /* trả về đọ dài từ. */ return pos; } int IsWhitespace(int ch) { return (ch == ' ') || (ch == '\n') || (ch == '\t'); } Có thật sự phải tự viết hàm kiểm tra này không ? ctype.h cung cấp hàm isspace( ) với chức năng tương đương Tinh chỉnh từng bước: Nhớ từ • Quay lại main(). <Thêm từ vào dòng> có nghĩa là gì ? • Tạo 1 hàm riêng cho việc đó : AddWord(word, line, &lineLen) #include #include enum {MAX_WORD_LEN = 20}; enum {MAX_LINE_LEN = 50}; int main(void) { char word[MAX_WORD_LEN + 1]; int wordLen; char line[MAX_LINE_LEN + 1]; int lineLen = 0; for (;;) { wordLen = ReadWord(word); if () { return 0; } if (<Từ không vừa dòng) { } AddWord(word, line, &lineLen); } return 0; } void AddWord(const char *word, char *line, int *lineLen) { strcat(line, word); (*lineLen) += strlen(word); } Tinh chỉnh từng bước: Nhớ từ • AddWord() void AddWord(const char *word, char *line, int *lineLen) { /* Nếu dòng đã chứa 1 số từ, thêm 1 dấu trắng. */ if (*lineLen > 0) { line[*lineLen] = ' '; line[*lineLen + 1] = '\0'; (*lineLen)++; } strcat(line, word); (*lineLen) += strlen(word); } Tinh chỉnh từng bước: In dòng cuối cùng • và <In dòng không căn lề> nghĩa là gì ? • Tạo các hàm để thực hiện int main(void) { char word[MAX_WORD_LEN + 1]; int wordLen; char line[MAX_LINE_LEN + 1]; int lineLen = 0; for (;;) { wordLen = ReadWord(word); /* Nếu hết từ, in dòng không căn lề. */ if ((wordLen == 0) && (lineLen > 0)) { puts(line); return 0; } if () { } AddWord(word, line, &lineLen); } return 0; } Tinh chỉnh từng bước: - Quyết định khi nào thì in • <Từ không vừa dòng> Nghĩa là gì? int main(void) { char word[MAX_WORD_LEN + 1]; int wordLen; char line[MAX_LINE_LEN + 1]; int lineLen = 0; for (;;) { wordLen = ReadWord(word); /* If no more words, print line with no justification. */ if ((wordLen == 0) && (lineLen > 0)) { puts(line); return 0; } /* Nếu từ không vừa dòng, thì */ if ((wordLen + 1 + lineLen) > MAX_LINE_LEN) { } AddWord(word, line, &lineLen); } return 0; } Tinh chỉnh từng bước: - In dòng có căn lề • nghĩa là gì ? • Rõ ràng hàm này cần biết trong dòng hiện tại có bao nhiêu từ. Vì vậy ta thêm numWords vào hàm main int main(void) { int numWords = 0; for (;;) { /* Nếu từ không vừa dòng, thì */ if ((wordLen + 1 + lineLen) > MAX_LINE_LEN) { WriteLine(line, lineLen, numWords); } AddWord(word, line, &lineLen); numWords++; } return 0; } Tinh chỉnh từng bước: - In dòng có căn lề • Viết pseudocode cho WriteLine() void WriteLine(const char *line, int lineLen, int numWords) { for (i = 0; i < lineLen; i++) { if () else { } } } Printing with Justification (cont.) • Hoàn tất hàm WriteLine() void WriteLine(const char *line, int lineLen, int numWords) { int extraSpaces, spacesToInsert, i, j; /* Tính số khoảng trống dư thừa cho dòng. */ extraSpaces = MAX_LINE_LEN - lineLen; for (i = 0; i < lineLen; i++) { if (line[i] != ' ') putchar(line[i]); else { /* Tính số khoảng trống cần thêm. */ spacesToInsert = extraSpaces / (numWords - 1); /* In 1 space, cộng thêm các spaces phụ. */ for (j = 1; j <= spacesToInsert + 1; j++) putchar(' '); /* Giảm bớt spaces và đếm từ. */ extraSpaces -= spacesToInsert; numWords--; } } putchar('\n'); } Số lượng các khoảng trống VD: Nếu extraSpaces = 10 và numWords = 5, thì space bù sẽ là 2, 2, 3, and 3 tương ứng Clearing the Line • Cuối cùng. nghĩa là gì ? • Tuy đơn giản, nhưng ta cũng viết thành 1 hàm int main(void) { int numWords = 0; ClearLine(line, &lineLen, &numWords); for (;;) { /* If word doesn't fit on this line, then */ if ((wordLen + 1 + lineLen) > MAX_LINE_LEN) { WriteLine(line, lineLen, numWords); ClearLine(line, &lineLen, &numWords); } addWord(word, line, &lineLen); numWords++; } return 0; } void ClearLine(char *line, int *lineLen, int *numWords) { [0] = '\0'; *lineLen = 0; *numWords = 0; } Cấu trúc chương trình dựa trên phương pháp modul hóa • Với người sử dụng CT – Input: Văn bản với định dạng lộn xộn – Output: Cùng nội dung, nhưng trình bày căn lề trái, phải, rõ ràng, sáng sủa • Giữa các phần của CT – Các hàm xử lý từ : Word-handling functions – Các hàm xử lý dòng : Line-handling functions – main() function • Lợi ích của modularity – Đọc code: dễ ràng, qua cac mẩu nhỏ, riêng biệt – Testing : Test từng hàm riêng biệt – Tăng tốc độ: Chỉ tập trung vào các phần tốc độ còn chậm – Mở rộng: Chỉ thay đổi các phần liên quan • Bài toán: cho các bộ dữ liệu mẫu như sau: – (tên sinh viên, điểm) • (“john smith”, 84) • (“jane doe”, 93) • (“bill clinton”, 81) • – (tên cầu thủ, vị trí chơi trên sân) • (“Ruth”, 3) • (“Gehrig”, 4) • (“Mantle”, 7) • – (tên biến, giá trị) • (“maxLength”, 2000) • (“i”, 7) • (“j”, -10) • – • Cần thiết kế cấu trúc dữ liệu cho phép thực hiện các thao tác sau: – Create: Tạo mới các bộ dữ liệu – Add: Thêm mới các dữ liệu thành phần – Search: Tìm kiếm các dữ liệu thành phần – Free: Hủy cấu trúc dữ liệu 3. Thiết kế dữ liệu • Bài toán: cho các bộ dữ liệu mẫu như sau: – (tên sinh viên, điểm) • (“john smith”, 84) • (“jane doe”, 93) • (“bill clinton”, 81) • – (tên cầu thủ, vị trí chơi trên sân) • (“Ruth”, 3) • (“Gehrig”, 4) • (“Mantle”, 7) • – (tên biến, giá trị) • (“maxLength”, 2000) • (“i”, 7) • (“j”, -10) • – • Cấu trúc dữ liệu: cho phép lưu trữ các bảng có chứa các cặp: khóa (key) và giá trị tương ứng với khóa (value) – Mỗi khóa là 1 xâu, mỗi giá trị là 1 số nguyên – Không biết trước số cặp khóa/giá trị – Có/Không cho phép có khóa trùng lặp  Linked list  Hash table  Expanding array 3. Thiết kế dữ liệu Data Structure #1: Linked List • Data structure: Các nút, mỗi nút chứa cặp key/value và con trỏ trỏ đến nút tiếp theo • Algorithms: – Create: Cấp phát nút giả trỏ đến nút thật đầu tiên – Add: Tạo nút mới, thêm vào đầu danh sách – Search: Tìm kiếm tuyến tính – Free: Giải phóng các nút trong khi duyệt, giải phóng các nút giả 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" Linked List: Data Structure struct Node { const char *key; int value; struct Node *next; }; struct Table { struct Node *first; }; Linked List: Create (1) STACK HEAP t struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->first = NULL; return t; } struct Table *t; t = Table_create(); Linked List: Create (2) STACK HEAP t t struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->first = NULL; return t; } struct Table *t; t = Table_create(); Linked List: Create (3) STACK HEAP t t NULL struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->first = NULL; return t; } struct Table *t; t = Table_create(); Linked List: Create (4) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->first = NULL; return t; } struct Table *t; t = Table_create(); STACK HEAP t NULL Linked List: Add (1) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL Các con trỏ trỏ đến các xâu nằm trong vùng RODATA Linked List: Add (2) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t "Mantle" key 7 value Con trỏ trỏ đến xâu nằm trong vùng nhớ RODATA Linked List: Add (3) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t "Mantle" key 7 value 7 "Mantle" p Linked List: Add (4) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t "Mantle" key 7 value 7 "Mantle" p Linked List: Add (5) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t "Mantle" key 7 value 7 "Mantle" p Linked List: Add (6) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; p->value = value; p->next = t->first; t->first = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" Linked List: Search (1) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; for (p = t->first; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" value found Linked List: Search (2) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; for (p = t->first; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" value found t "Gehrig" key value Linked List: Search (3) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; for (p = t->first; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" value found t "Gehrig" key value p Linked List: Search (4) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; for (p = t->first; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" 4 value found t "Gehrig" key value p Linked List: Search (5) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; for (p = t->first; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" 4 value 1 found Linked List: Free (1) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" Linked List: Free (2) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" t Linked List: Free (3) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" t p nextp Linked List: Free (4) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL 7 "Mantle" t p nextp Linked List: Free (5) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t p nextp Linked List: Free (6) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t 4 "Gehrig" 3 "Ruth" NULL t p nextp Linked List: Free (7) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t t NULL p NULL nextp Linked List: Free (8) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t t NULL p NULL nextp Linked List: Free (9) struct Table *t; Table_free(t); void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; for (p = t->first; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); /* Free the dummy node */ } STACK HEAP t Hiệu năng của chương trình khi cài đặt CTDL bằng Linked List • Phân tích độ phức tạp về thời gian: – Create: O(1), nhanh – Add: O(1), nhanh – Search: O(n), chậm – Free: O(n), chậm • Giải pháp khác: luôn giữ các nút được sắp xếp theo thứ tự tăng/giảm dần của khóa – Create: O(1), nhanh – Add: O(n), chậm; cần duyệt danh sách trước khi tìm được chỗ để thêm – Search: O(n), vẫn chậm; cần duyệt một phần danh sách – Free: O(n), chậm Data Structure #2: Bảng băm (Hash Table) • Mảng có kích thước cố định, mỗi phần tử của mảng trỏ đến một danh sách móc nối • Hàm ánh xạ một khóa vào 1 chỉ số mảng – Vì khóa là xâu, tìm hàm băm hợp lý – Tìm đến phần tử i của mảng để thực hiện các thao tác, tức là thao tác trên danh sách móc nối hashtab[i] 0 ARRAYSIZE-1 struct Node *array[ARRAYSIZE]; Băm khóa kiểu string thành giá trị kiểu int • Hàm băm đơn giản sẽ không đưa ra được nhiều khóa phân biệt – Số các ký tự trong xâu % ARRAYSIZE – Tổng các giá trị ASCII của các ký tự trong xâu % ARRAYSIZE – • Hàm băm hợp lý – Tổng các giá trị có tính đến trọng số của các ký tự trong xâu: xi giá trị ASCII của ký tự, a trọng số của ký tự, i vị trí trong xâu • ( aixi) mod ARRAYSIZE – Trường hợp tốt nhất: a và ARRAYSIZE đều là số nguyên tố • E.g., a = 65599, ARRAYSIZE = 1024 Cài đặt hàm băm • Phải trả giá đắt cho việc tính ai cho mỗi chỉ số i – Thay vì tính ai cho mỗi chỉ số i – Tính (((x[0] * 65599 + x[1]) * 65599 + x[2]) * 65599 + x[3]) * unsigned int hash(const char *x) { int i; unsigned int h = 0U; for (i=0; x[i]!='\0'; i++) h = h * 65599 + (unsigned char)x[i]; return h % 1024; } Ví dụ về bảng băm Cho ARRAYSIZE = 7 Tìm kiếm và thêm vào nếu không tìm thấy các xâu sau: the, cat, in, the, hat Bảng băm ban đầu là rỗng Từ 1: hash(“the”) = 965156977. 965156977 % 7 = 1. Tìm xâu “the” trong DS móc nối table[1] : không tìm thấy 0 1 2 3 4 5 6 Ví dụ về bảng băm Cho ARRAYSIZE = 7 Tìm kiếm và thêm vào nếu không tìm thấy các xâu sau: the, cat, in, the, hat Bảng băm ban đầu là rỗng Từ 1: hash(“the”) = 965156977. 965156977 % 7 = 1. Tìm xâu “the” trong DS móc nối table[1] : không tìm thấy Now: table[1] = makelink(key, value, table[1]) 0 1 2 3 4 5 6 the Ví dụ về bảng băm Từ 2: “cat”. hash(“cat”) = 3895848756. 3895848756 % 7 = 2. Tìm trong DS móc nối table[2] xâu “cat”: không tìm thấy Now: table[2] = makelink(key, value, table[2]) 0 1 2 3 4 5 6 the Ví dụ về bảng băm Từ 3: “in”. hash(“in”) = 6888005. 6888005% 7 = 5. Tìm xâu “in” trong DS móc nối table[5]: không thấy Now: table[5] = makelink(key, value, table[5]) 0 1 2 3 4 5 6 the cat Ví dụ về bảng băm Từ 4: “the”. hash(“the”) = 965156977. 965156977 % 7 = 1. Tìm xâu “the” trong DS móc nối table[1] ; có thấy 0 1 2 3 4 5 6 the cat in Ví dụ về bảng băm Từ 4: “hat”. hash(“hat”) = 865559739. 865559739 % 7 = 2. Tìm xâu “hat” trong DS móc nối table[2]; không thấy Now: Thêm “hat” vào table[2]. Thêm vào đâu ? Đầu hay cuối danh sách ? 0 1 2 3 4 5 6 the cat in Ví dụ về bảng băm Thêm vào đầu danh sách dễ hơn 0 1 2 3 4 5 6 the hat in cat Bảng băm: cấu trúc dữ liệu enum {BUCKET_COUNT = 1024}; struct Node { const char *key; int value; struct Node *next; }; struct Table { struct Node *array[BUCKET_COUNT]; }; Bảng băm: Create (1) struct Table *Table_create(void) { struct Table *t; t = (struct Table*)calloc(1, sizeof(struct Table)); return t; } struct Table *t; t = Table_create(); STACK HEAP t Hash Table: Create (2) struct Table *Table_create(void) { struct Table *t; t = (struct Table*)calloc(1, sizeof(struct Table)); return t; } struct Table *t; t = Table_create(); STACK HEAP t t Hash Table: Create (3) struct Table *Table_create(void) { struct Table *t; t = (struct Table*)calloc(1, sizeof(struct Table)); return t; } struct Table *t; t = Table_create(); STACK HEAP t NULL t NULL NULL 0 1 1023 Bảng băm: Create (4) struct Table *Table_create(void) { struct Table *t; t = (struct Table*)calloc(1, sizeof(struct Table)); return t; } struct Table *t; t = Table_create(); STACK HEAP t NULL NULL NULL 0 1 1023 Bảng băm: Add (1) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t NULL 4 "Gehrig" NULL 3 "Ruth" NULL NULL NULL 0 1 806 23 723 NULL 1023 Con trỏ trỏ đến các xâu trong vùng nhớ RODATA "Mantle" 7 Bảng băm: Add (2) void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL t key value NULL NULL NULL 0 1 806 23 723 NULL 1023 Con trỏ trỏ đến các xâu trong vùng nhớ RODATA void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } "Mantle" 7 Bảng băm: Add (3) STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" t key value p 806 h NULL NULL NULL 0 1 806 23 723 NULL 1023 struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Mantle" 7 Bảng băm: Add (4) STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL t key value p 806 h NULL NULL NULL 0 1 806 23 723 NULL 1023 void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Mantle" 7 Bảng băm: Add (5) STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL t key value p 806 h NULL NULL 0 1 806 23 723 NULL 1023 void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); int h = hash(key); p->key = key; p->value = value; p->next = t->array[h]; t->array[h] = p; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); Bảng băm: Add (6) STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 Bảng băm: Search (1) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found Bảng băm: Search (2) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found t "Gehrig" key value Bảng băm: Search (3) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found t "Gehrig" key value p 723 h Bảng băm: Search (4) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found t "Gehrig" key value p 723 h 4 Bảng băm: Search (5) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found t "Gehrig" key value p 723 h 4 1 Bảng băm: Search (6) int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); for (p = t->array[h]; p != NULL; p = p->next) if (strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 value found Bảng băm: Free (1) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 Bảng băm: Free (2) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 t Bảng băm: Free (3) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t 4 "Gehrig" NULL 3 "Ruth" NULL 7 "Mantle" NULL NULL NULL 0 1 806 23 723 NULL 1023 t p nextp b 1024 Bảng băm: Free (4) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t NULL NULL 0 1 806 23 723 NULL 1023 t p nextp b 1024 Bảng băm: Free (5) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t t p nextp b Bảng băm: Free (6) void Table_free(struct Table *t) { struct Node *p; struct Node *nextp; int b; for (b = 0; b < BUCKET_COUNT; b++) for (p = t->array[b]; p != NULL; p = nextp) { nextp = p->next; free(p); } free(t); } struct Table *t; Table_free(t); STACK HEAP t Bảng băm: hiệu năng • Create: O(1), nhanh • Add: O(1), nhanh • Search: O(1), nhanh trong trường hợp kích thước nhỏ • Free: O(n), chậm Key Ownership • Lưu ý: Hàm Table_add() – Key là tham số đầu vào (con trỏ trỏ đến ô nhớ chứa xâu) – Table_add() chỉ lưu trong bảng địa chỉ của xâu đó void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = key; } Key Ownership (cont.) • Problem: Xét đoạn mã sau – Vấn đề trong bảng băm • Khóa của nút hiện tại đổi từ “Ruth” thành “Gehrig” • Nút hiện có đặt sai chỗ • Bảng băm bị hỏng!!! – Vấn đề này có thể xảy ra đối với các cấu trúc dữ liệu khác struct Table t; char k[100] = "Ruth"; Table_add(t, k, 3); strcpy(k, "Gehrig"); Sau khi gọi Table_add(), bảng chứa địa chỉ ô nhớ k LTV thay đổi xâu tại địa chỉ ô nhớ k Rồi LTV thay đổi khóa trong bảng Key Ownership (cont.) • Giải pháp: Table_add() lưu lại bản sao giá trị của khóa – Nếu LTV thay đổi xâu tại địa chỉ ô nhớ k, cấu trúc dữ liệu không bị ảnh hưởng • Trong trường hợp này, cấu trúc dữ liệu quản lý bản sao của khóa, tức là: – CTDL chịu trách nhiệm giải phóng ô nhớ chứa bản sao – Hàm Table_free() phải giải phóng bản sao void Table_add(struct Table *t, const char *key, int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); p->key = (const char*)malloc(strlen(key) + 1); strcpy(p->key, key); } Cho phép lưu phần tử cuối Tóm tắt • Các cấu trúc dữ liệu phổ biến và các giải thuật liên quan – Linked list • Unsorted => thêm mới nhanh, tìm kiếm chậm • Sorted => thêm mới chậm, tìm kiếm chậm – Hash table • Thêm mới nhanh, tìm kiếm nhanh nếu hàm băm hoạt động tốt • Khó đánh giá việc lưu trữ các cặp khóa/giá trị • Rất phổ biến • Các chủ để liên quan: – Giải thuật băm – Quản lý bộ nhớ • Khác – #1: tiểu xảo tạo ra các hàm băm nhanh hơn – #2: ví dụ về cấu trúc dữ liệu khác #1: Xem lại các hàm băm • Tính “mod c” có vẻ mất nhiều thời gian – Bao gồm việc thực hiện phép chia với số chia là c và lưu trữ số dư – Sẽ dễ hơn nếu c là lũy thừa của 2 (e.g., 16 = 24) • Đề xuất giải pháp thay thế: – 53 = 32 + 16 + 4 + 1 – 53 % 16 = 5, chính là giá trị chứa trong 4 bits cuối – Nếu có thể dễ dàng tác ra 4 bits này 0 0 1 1 0 1 0 1 1 2 4 8 16 32 0 0 0 0 0 1 0 1 1 2 4 8 16 32 Recall: Bitwise Operators in C • Bitwise AND (&) – Thực hiện phép chia lấy dư, nhưng ít tốn kém hơn • E.g., h = 53 & 15; • Bitwise OR (|) & 0 1 0 1 0 0 0 1 | 0 1 0 1 0 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 1 1 1 1 53 & 15 0 0 0 0 0 1 0 1 5 Cách khác Đảo 0 thành 1, 1 thành 0 E.g., đặt 3 bits cuối thành 0 x = x & ~7; Hàm băm nhanh hơn • Chú ý: không viết “h & 1024” unsigned int hash(const char *x) { int i; unsigned int h = 0U; for (i=0; x[i]!='\0'; i++) h = h * 65599 + (unsigned char)x[i]; return h % 1024; } unsigned int hash(const char *x) { int i; unsigned int h = 0U; for (i=0; x[i]!='\0'; i++) h = h * 65599 + (unsigned char)x[i]; return h & 1023; } Nhanh hơn Previous version Tăng tốc việc so sánh các khóa • Cho mọi hàm so sánh giá trị không tầm thường • Trick: lưu trữ toàn bộ giá trị băm trong CTDL int Table_search(struct Table *t, const char *key, int *value) { struct Node *p; int h = hash(key); /* No % in hash function */ for (p = t->array[h%1024]; p != NULL; p = p->next) if ((p->hash == h) && strcmp(p->key, key) == 0) { *value = p->value; return 1; } return 0; } # 2: Cấu trúc dữ liệu khác • Expanding array Expanding Array • Ý tưởng • Cấu trúc dữ liệu: mảng có thể mở rộng kích thước khi cần • Giải thuật Create: cấp phát mảng lưu trữ các cặp khóa/giá trị, ban đầu có rất ít phần tử • Giải thuật Add: Nếu hết chỗ để lưu trữ thêm phần tử mới, thì tăng gấp đôi kích thước mảng và đặt cặp khóa/giá trị cần thêm vào vào trong phần tử đầu tiên chưa sử dụng – Để tăng tính hiệu quả, không nên mở rộng mảng theo kiểu tuyến tính • Giải thuật Search: tìm kiếm tuyến tính • Giải thuật Free: giải phóng mảng Expanding Array: Data Structure enum {INITIAL_SIZE = 2}; enum {GROWTH_FACTOR = 2}; struct Pair { const char *key; int value; }; struct Table { int pairCount; /* Number of pairs in table */ int arraySize; /* Physical size of array */ struct Pair *array; /* Address of array */ }; Expanding Array: Create (1) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->pairCount = 0; t->arraySize = INITIAL_SIZE; t->array = (struct Pair*) calloc(INITIAL_SIZE, sizeof(struct Pair)); return t; } { struct Table *t; t = Table_create(); } STACK HEAP t Expanding Array: Create (2) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->pairCount = 0; t->arraySize = INITIAL_SIZE; t->array = (struct Pair*) calloc(INITIAL_SIZE, sizeof(struct Pair)); return t; } { struct Table *t; t = Table_create(); } STACK HEAP t t Expanding Array: Create (3) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->pairCount = 0; t->arraySize = INITIAL_SIZE; t->array = (struct Pair*) calloc(INITIAL_SIZE, sizeof(struct Pair)); return t; } { struct Table *t; t = Table_create(); } STACK HEAP t t 2 0 Expanding Array: Create (4) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->pairCount = 0; t->arraySize = INITIAL_SIZE; t->array = (struct Pair*) calloc(INITIAL_SIZE, sizeof(struct Pair)); return t; } { struct Table *t; t = Table_create(); } STACK HEAP t t 2 0 Expanding Array: Create (5) struct Table *Table_create(void) { struct Table *t; t = (struct Table*) malloc(sizeof(struct Table)); t->pairCount = 0; t->arraySize = INITIAL_SIZE; t->array = (struct Pair*) calloc(INITIAL_SIZE, sizeof(struct Pair)); return t; } { struct Table *t; t = Table_create(); } STACK HEAP t 2 0 Expanding Array: Add (1) void Table_add(struct Table *t, const char *key, int value) { /* Expand if necessary. */ if (t->pairCount == t->arraySize) { t->arraySize *= GROWTH_FACTOR; t->array = (struct Pair*)realloc(t->array, t->arraySize * sizeof(struct Pair)); } t->array[t->pairCount].key = key; t->array[t->pairCount].value = value; t->pairCount++; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); t "Ruth" 3 2 2 "Gehrig" 4 STACK HEAP These are pointers to strings that exist in the RODATA section t Expanding Array: Add (2) void Table_add(struct Table *t, const char *key, int value) { /* Expand if necessary. */ if (t->pairCount == t->arraySize) { t->arraySize *= GROWTH_FACTOR; t->array = (struct Pair*)realloc(t->array, t->arraySize * sizeof(struct Pair)); } t->array[t->pairCount].key = key; t->array[t->pairCount].value = value; t->pairCount++; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Ruth" 3 2 2 "Gehrig" 4 STACK HEAP t "Mantle" 7 key value This is a pointer to a string that exists in the RODATA section t Expanding Array: Add (3) void Table_add(struct Table *t, const char *key, int value) { /* Expand if necessary. */ if (t->pairCount == t->arraySize) { t->arraySize *= GROWTH_FACTOR; t->array = (struct Pair*)realloc(t->array, t->arraySize * sizeof(struct Pair)); } t->array[t->pairCount].key = key; t->array[t->pairCount].value = value; t->pairCount++; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Ruth" 3 4 2 "Gehrig" 4 STACK HEAP t "Mantle" 7 key value "Ruth" 3 "Gehrig" 4 t Expanding Array: Add (4) void Table_add(struct Table *t, const char *key, int value) { /* Expand if necessary. */ if (t->pairCount == t->arraySize) { t->arraySize *= GROWTH_FACTOR; t->array = (struct Pair*)realloc(t->array, t->arraySize * sizeof(struct Pair)); } t->array[t->pairCount].key = key; t->array[t->pairCount].value = value; t->pairCount++; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t "Mantle" 7 key value Expanding Array: Add (5) void Table_add(struct Table *t, const char *key, int value) { /* Expand if necessary. */ if (t->pairCount == t->arraySize) { t->arraySize *= GROWTH_FACTOR; t->array = (struct Pair*)realloc(t->array, t->arraySize * sizeof(struct Pair)); } t->array[t->pairCount].key = key; t->array[t->pairCount].value = value; t->pairCount++; } struct Table *t; Table_add(t, "Ruth", 3); Table_add(t, "Gehrig", 4); Table_add(t, "Mantle", 7); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t Expanding Array: Search (1) int Table_search(struct Table *t, const char *key, int *value) { int i; for (i = 0; i pairCount; i++) { struct Pair p = t->array[i]; if (strcmp(p.key, key) == 0) { *value = p.value; return 1; } } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); STACK HEAP 4 3 "Gehrig" "Mantle" 4 7 t value found "Ruth" 3 Expanding Array: Search (2) int Table_search(struct Table *t, const char *key, int *value) { int i; for (i = 0; i pairCount; i++) { struct Pair p = t->array[i]; if (strcmp(p.key, key) == 0) { *value = p.value; return 1; } } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t value found "Gehrig" t key value Expanding Array: Search (3) int Table_search(struct Table *t, const char *key, int *value) { int i; for (i = 0; i pairCount; i++) { struct Pair p = t->array[i]; if (strcmp(p.key, key) == 0) { *value = p.value; return 1; } } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t value found "Gehrig" t key value 1 i p 4 Expanding Array: Search (4) int Table_search(struct Table *t, const char *key, int *value) { int i; for (i = 0; i pairCount; i++) { struct Pair p = t->array[i]; if (strcmp(p.key, key) == 0) { *value = p.value; return 1; } } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t value found "Gehrig" t key value 1 i p 4 1 Expanding Array: Search (5) int Table_search(struct Table *t, const char *key, int *value) { int i; for (i = 0; i pairCount; i++) { struct Pair p = t->array[i]; if (strcmp(p.key, key) == 0) { *value = p.value; return 1; } } return 0; } struct Table *t; int value; int found; found = Table_search(t, "Gehrig", &value); "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t value found Expanding Array: Free (1) struct Table *t; Table_free(t); void Table_free(struct Table *t) { free(t->array); free(t); } "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t Expanding Array: Free (2) struct Table *t; Table_free(t); void Table_free(struct Table *t) { free(t->array); free(t); } "Ruth" 3 4 3 "Gehrig" "Mantle" 4 7 STACK HEAP t t Expanding Array: Free (3) struct Table *t; Table_free(t); void Table_free(struct Table *t) { free(t->array); free(t); } 4 3 STACK HEAP t t Expanding Array: Free (4) struct Table *t; Table_free(t); void Table_free(struct Table *t) { free(t->array); free(t); } STACK HEAP t t Expanding Array: Free (5) struct Table *t; Table_free(t); void Table_free(struct Table *t) { free(t->array); free(t); } STACK HEAP t Expanding Array: hiệu năng • Thời gian tính toán – Create: O(1), nhanh – Add: O(1), nhanh – Search: O(n), chậm – Free: O(1), nhanh • Giải pháp khác: Sắp xếp mảng theo khóa – Create: O(1), nhanh – Add: O(n), chậm; cần phải dịch 1 cặp khóa/ giá trị để có chỗ thêm mới – Search: O(log n), chấp nhận được, có thể sử dụng tìm kiếm nhị phân – Free: O(1), nhanh 5. Quản lý bộ nhớ động • Một số hạn chế khi sử dụng mảng trong C: – Kích thước của mảng cần biết trước – Kích thước của mảng không thể thay đổi trong chương trình • Cần: – Cấp phát bộ nhớ đúng như lượng cần khi chạy – Giải phóng bộ nhớ ngay khi không cần dùng – Chương trình không cần phải viết lại để xử lý lượng dữ liệu lớn hơn Quản lý bộ nhớ động (dynamic memory)  C: Dùng malloc(), calloc(), realloc() và free()  C++: Dùng new và delete 5.1. Quản lý bộ nhớ động trong C Trong thư viện stdlib.h malloc(size_t n), calloc(size_t m, size_t n)  Cấp phát một vùng nhớ mới. realloc(void * ptr, size_t n)  Thay đổi kích thước cho một vùng nhớ đã được cấp phát free(void * ptr)  Giải phóng cho vùng nhớ đã được cấp phát size_t là kiểu dữ liệu chứa kích thước đối tượng (số byte) size_t sizeof(doi_tuong): Kích thước của doi_tuong Ví dụ: sizeof(int)  2 5.1.1. Cấp phát vùng nhớ void *malloc(size_t n); Lấy về một vùng nhớ liên tục có kích thước ít nhất là n byte Chỉ xin cấp phát vùng nhớ chứ nội dung vùng nhớ vẫn chưa được xác định void *calloc(size_t m, size_t n); Lấy về một vùng nhớ có kích thước ít nhất là m x n byte. Vùng nhớ này đủ để chứa một mảng gồm m phần tử, mỗi phần tử chiếm n byte. Mỗi byte nhớ được khởi tạo với giá trị 0 Hai hàm trên trả về con trỏ null khi có lỗi trong quá trình cấp phát vùng nhớ Bộ nhớ động được quản lý bởi hệ điều hành trong môi trường đa nhiệm  được chia sẻ giữa hàng loạt các ứng dụng  Có thể thiếu bộ nhớ #include #include void main() { int i, kthuoc; int *a; double *dPtr = malloc(sizeof(double)); printf("Hay nhap vao kich thuoc cua mang: "); scanf("%d", &kthuoc); a = (int *) calloc(kthuoc, sizeof(int)); if (a == NULL || dPtr == NULL ) //Khong du bo nho printf("Khong du bo nho"); else // Da duoc cap phat du { *dPtr = -8.67; for (i=0;i<kthuoc;i++) a[i] = i; a[kthuoc-1] = *dPtr; for (i=0; i<kthuoc; i++) printf("%d", a[i]); } getch(); } 5.1.1. Cấp phát vùng nhớ (2) Cấp phát vùng nhớ thành công sẽ trả về một con trỏ trỏ đến byte đầu tiên của vùng nhớ Bất cứ một kiểu đối tượng nào cũng có thể lưu vào vùng nhớ được cấp phát (con trỏ void). Vùng nhớ được cấp phát được giữ cho chương trình của bạn cho tới khi bạn giải phóng nó bằng việc gọi hàm free( ) hoặc realloc( ) hoặc khi kết thúc chương trình 5.1.2. Thay đổi và giải phóng bộ nhớ void free(void * ptr); Giải phóng vùng nhớ động bắt đầu từ địa chỉ ptr Nếu ptr là con trỏ null thì lời gọi hàm là vô nghĩa. void *realloc(void * ptr, size_t n); Giải phóng vùng nhớ từ địa chỉ ptr và cấp phát một vùng nhớ mới n byte và trả về địa chỉ của vùng nhớ đó Vùng nhớ mới có thể bắt đầu giống địa chỉ của vùng nhớ cũ. Giữ nguyên nội dung của vùng nhớ cũ cho tới kích thước của vùng nhớ nào nhỏ hơn  Nếu vùng nhớ mới không bắt đầu từ địa chỉ của vùng nhớ cũ thì hàm realloc( ) sao chép nội dung vùng nhớ cũ sang vùng nhơ mới.  Nếu vùng nhớ mới lớn hơn vùng nhớ cũ thì giá trị của các byte dư ra không được xác định. Nếu ptr là con trỏ null thì hàm này giống như hàm malloc() #include #include #include void main() { char *p = malloc(17); if(p == NULL) { printf("Co loi khi cap phat bo nho\n"); exit(1); } strcpy(p, "Xau gom 16 ky tu"); p = realloc(p, 18); if(!p) { printf("Co loi khi cap phat bo nho\n"); exit(1); } strcat(p, "!!"); printf(p); free(p); getch(); } #include #include #include void main() { char dong[80], *tbao; puts(“Nhap vao mot dong: "); gets(dong); tbao = realloc(NULL, strlen(dong)+1); strcpy(tbao, dong); puts(tbao); puts(“Nhap vao mot dong khac: "); gets(dong); tbao = realloc(tbao,(strlen(tbao) + strlen(dong)+1)); strcat(tbao, dong); puts(tbao); getch(); } 5.2. Quản lý bộ nhớ động trong C++ Trong thư viện Xin cấp phát bộ nhớ: Toán tử new bienConTro = new kieuDL;  xin cấp phát một vùng nhớ cho một biến đơn bienConTro = new kieuDL[kichThuoc];  xin cấp phát cho một mảng các phần tử có cùng kiểu với kiểu dữ liệu Khi có lỗi về việc cấp phát bộ nhớ, toán tử new sẽ trả về con trỏ NULL. Giải phóng bộ nhớ: Toán tử delete delete bienConTro; // xóa 1 biến đơn delete []bienMang; // xóa 1 biến mảng Ví dụ - Quản lý bộ nhớ động trong C++ #include int main() { int i,n; long total=100,x,*ptr; cout > n; ptr = new long [n]; if (ptr==NULL) exit(1); for (i=0;i<n;i++){ cout <<“\n Vao so thu ”<< i+1 <<“ :”; cin >> ptr[i] } cout << “Danh sach cac so : \n” for (i=0;i<n;i++) cout << ptr[i] << “,”; delete [] ptr; return 0; } Dùng bộ nhớ động cho mảng Ta có thể coi một mảng 2 chiều là 1 mảng 1 chiều như hình sau: Gọi X là mảng hai chiều có kích thước m dòng và n cột. A là mảng một chiều tương ứng ,thì X[i][j] = A[ i*n + j]