練習34：動態數組 · 笨辦法學C

# 練習34：動態數組 > 原文：[Exercise 34: Dynamic Array](http://c.learncodethehardway.org/book/ex34.html) > 譯者：[飛龍](https://github.com/wizardforcel) 動態數組是自增長的數組，它與鏈表有很多相同的特性。它通常占據更少的空間，跑得更快，還有一些其它的優勢屬性。這個練習會涉及到它的一些缺點，比如從開頭移除元素會很慢，并給出解決方案（只從末尾移除）。動態數組簡單地實現為`void **`指針的數組，它是預分配內存的，并且指向數據。在鏈表中你創建了完整的結構體來儲存`void *value`指針，但是動態數組中你只需要一個儲存它們的單個數組。也就是說，你并不需要創建任何其它的指針儲存上一個或下一個元素。它們可以直接索引。我會給你頭文件作為起始，你需要為實現打下它們： ```c #ifndef _DArray_h #define _DArray_h #include <stdlib.h> #include <assert.h> #include <lcthw/dbg.h> typedef struct DArray { int end; int max; size_t element_size; size_t expand_rate; void **contents; } DArray; DArray *DArray_create(size_t element_size, size_t initial_max); void DArray_destroy(DArray *array); void DArray_clear(DArray *array); int DArray_expand(DArray *array); int DArray_contract(DArray *array); int DArray_push(DArray *array, void *el); void *DArray_pop(DArray *array); void DArray_clear_destroy(DArray *array); #define DArray_last(A) ((A)->contents[(A)->end - 1]) #define DArray_first(A) ((A)->contents[0]) #define DArray_end(A) ((A)->end) #define DArray_count(A) DArray_end(A) #define DArray_max(A) ((A)->max) #define DEFAULT_EXPAND_RATE 300 static inline void DArray_set(DArray *array, int i, void *el) { check(i < array->max, "darray attempt to set past max"); if(i > array->end) array->end = i; array->contents[i] = el; error: return; } static inline void *DArray_get(DArray *array, int i) { check(i < array->max, "darray attempt to get past max"); return array->contents[i]; error: return NULL; } static inline void *DArray_remove(DArray *array, int i) { void *el = array->contents[i]; array->contents[i] = NULL; return el; } static inline void *DArray_new(DArray *array) { check(array->element_size > 0, "Can't use DArray_new on 0 size darrays."); return calloc(1, array->element_size); error: return NULL; } #define DArray_free(E) free((E)) #endif ``` 這個頭文件向你展示了`static inline`的新技巧，它就類似`#define`宏的工作方式，但是它們更清楚，并且易于編寫。如果你需要創建一塊代碼作為宏，并且不需要代碼生成，可以使用`static inline`函數。為鏈表生成`for`循環的`LIST_FOREACH`不可能寫為`static inline`函數，因為它需要生成循環的內部代碼塊。實現它的唯一方式是灰調函數，但是這不夠塊，并且難以使用。之后我會修改代碼，并且讓你創建`DArray`的單元測試。 ```c #include "minunit.h" #include <lcthw/darray.h> static DArray *array = NULL; static int *val1 = NULL; static int *val2 = NULL; char *test_create() { array = DArray_create(sizeof(int), 100); mu_assert(array != NULL, "DArray_create failed."); mu_assert(array->contents != NULL, "contents are wrong in darray"); mu_assert(array->end == 0, "end isn't at the right spot"); mu_assert(array->element_size == sizeof(int), "element size is wrong."); mu_assert(array->max == 100, "wrong max length on initial size"); return NULL; } char *test_destroy() { DArray_destroy(array); return NULL; } char *test_new() { val1 = DArray_new(array); mu_assert(val1 != NULL, "failed to make a new element"); val2 = DArray_new(array); mu_assert(val2 != NULL, "failed to make a new element"); return NULL; } char *test_set() { DArray_set(array, 0, val1); DArray_set(array, 1, val2); return NULL; } char *test_get() { mu_assert(DArray_get(array, 0) == val1, "Wrong first value."); mu_assert(DArray_get(array, 1) == val2, "Wrong second value."); return NULL; } char *test_remove() { int *val_check = DArray_remove(array, 0); mu_assert(val_check != NULL, "Should not get NULL."); mu_assert(*val_check == *val1, "Should get the first value."); mu_assert(DArray_get(array, 0) == NULL, "Should be gone."); DArray_free(val_check); val_check = DArray_remove(array, 1); mu_assert(val_check != NULL, "Should not get NULL."); mu_assert(*val_check == *val2, "Should get the first value."); mu_assert(DArray_get(array, 1) == NULL, "Should be gone."); DArray_free(val_check); return NULL; } char *test_expand_contract() { int old_max = array->max; DArray_expand(array); mu_assert((unsigned int)array->max == old_max + array->expand_rate, "Wrong size after expand."); DArray_contract(array); mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least."); DArray_contract(array); mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least."); return NULL; } char *test_push_pop() { int i = 0; for(i = 0; i < 1000; i++) { int *val = DArray_new(array); *val = i * 333; DArray_push(array, val); } mu_assert(array->max == 1201, "Wrong max size."); for(i = 999; i >= 0; i--) { int *val = DArray_pop(array); mu_assert(val != NULL, "Shouldn't get a NULL."); mu_assert(*val == i * 333, "Wrong value."); DArray_free(val); } return NULL; } char * all_tests() { mu_suite_start(); mu_run_test(test_create); mu_run_test(test_new); mu_run_test(test_set); mu_run_test(test_get); mu_run_test(test_remove); mu_run_test(test_expand_contract); mu_run_test(test_push_pop); mu_run_test(test_destroy); return NULL; } RUN_TESTS(all_tests); ``` 這向你展示了所有操作都如何使用，它會使`DArray`的實現變得容易： ```c #include <lcthw/darray.h> #include <assert.h> DArray *DArray_create(size_t element_size, size_t initial_max) { DArray *array = malloc(sizeof(DArray)); check_mem(array); array->max = initial_max; check(array->max > 0, "You must set an initial_max > 0."); array->contents = calloc(initial_max, sizeof(void *)); check_mem(array->contents); array->end = 0; array->element_size = element_size; array->expand_rate = DEFAULT_EXPAND_RATE; return array; error: if(array) free(array); return NULL; } void DArray_clear(DArray *array) { int i = 0; if(array->element_size > 0) { for(i = 0; i < array->max; i++) { if(array->contents[i] != NULL) { free(array->contents[i]); } } } } static inline int DArray_resize(DArray *array, size_t newsize) { array->max = newsize; check(array->max > 0, "The newsize must be > 0."); void *contents = realloc(array->contents, array->max * sizeof(void *)); // check contents and assume realloc doesn't harm the original on error check_mem(contents); array->contents = contents; return 0; error: return -1; } int DArray_expand(DArray *array) { size_t old_max = array->max; check(DArray_resize(array, array->max + array->expand_rate) == 0, "Failed to expand array to new size: %d", array->max + (int)array->expand_rate); memset(array->contents + old_max, 0, array->expand_rate + 1); return 0; error: return -1; } int DArray_contract(DArray *array) { int new_size = array->end < (int)array->expand_rate ? (int)array->expand_rate : array->end; return DArray_resize(array, new_size + 1); } void DArray_destroy(DArray *array) { if(array) { if(array->contents) free(array->contents); free(array); } } void DArray_clear_destroy(DArray *array) { DArray_clear(array); DArray_destroy(array); } int DArray_push(DArray *array, void *el) { array->contents[array->end] = el; array->end++; if(DArray_end(array) >= DArray_max(array)) { return DArray_expand(array); } else { return 0; } } void *DArray_pop(DArray *array) { check(array->end - 1 >= 0, "Attempt to pop from empty array."); void *el = DArray_remove(array, array->end - 1); array->end--; if(DArray_end(array) > (int)array->expand_rate && DArray_end(array) % array->expand_rate) { DArray_contract(array); } return el; error: return NULL; } ``` 這占你展示了另一種處理復雜代碼的方法，觀察頭文件并閱讀單元測試，而不是一頭扎進`.c`實現中。這種“具體的抽象”讓你理解代碼如何一起工作，并且更容易記住。 ## 優點和缺點 `DArray`在你需要這些操作時占優勢。 + 迭代。你可以僅僅使用基本的`for`循環，使用`DArray_count`和`DArray_get`來完成任務。不需要任何特殊的宏。并且由于不處理指針，它非常快。 + 索引。你可以使用`DArray_get`和`DArray_set`來隨機訪問任何元素，但是`List`上你就必須經過第N個元素來訪問第N+1個元素。 + 銷毀。你只需要以兩個操作銷毀結構體和`content`。但是`List`需要一些列的`free`調用同時遍歷每個元素。 + 克隆。你只需要復制結構體和`content`，用兩步復制整個結構。`List`需要遍歷所有元素并且復制每個`ListNode`和值。 + 排序。你已經見過了，如果你需要對數據排序，`List`非常麻煩。`DArray`上可以實現所有高效的排序算法，因為你可以隨機訪問任何元素。 + 大量數據。如果你需要儲存大量數據，`DArray`由于基于`content`，比起相同數量的`ListNode`占用更少空間而占優。然而`List`在這些操作上占優勢。 + 在開頭插入和移除元素。`DArray`需要特殊的優化來高效地完成它，并且通常還需要一些復制操作。 + 分割和連接。`List`只需要復制一些指針就能完成，但是`DArray`需要復制涉及到的所有數組。 + 少量數據。如果你只需要存儲幾個元素，通常使用`List`所需的空間要少于`DArray`，因為`DArray`需要考慮到日后的添加而擴展背后的空間，但是`List`只需要元素所需的空間。考慮到這些，我更傾向使用`DArray`來完成其它人使用`List`所做的大部分事情。對于任何需要少量節點并且在兩端插入刪除的，我會使用`List`。我會想你展示兩個相似的數據結構，叫做`Stack`和`Queue`，它們也很重要。 ## 如何改進像往常一樣，瀏覽每個函數和操作，并且執行防御性編程檢查，以及添加先決條件、不變量等任何可以使實現更健壯的東西。 ## 附加題 + 改進單元測試來覆蓋耕作操作，并使用`for`循環來測試迭代。 + 研究`DArray`上如何實現冒泡排序和歸并排序，但是不要馬上實現它們。我會在下一張實現`DArray`的算法，之后你可以完成它。 + 為一些常用的操作編寫一些性能測試，并與`List`中的相同操作比較。你已經做過很多次了，但是這次需要編寫重復執行所涉及操作的單元測試，之后在主運行器中計時。 + 觀察`DArray_expand`如何使用固定增長（`size + 300`）來實現。通常動態數組都以倍數增長（`size * 2`）的方式實現，但是我發現它會花費無用的內存并且沒有真正取得性能收益。測試我的斷言，并且看看什么情況下需要倍數增長而不是固定增長。