系统程序员成长计划-组合的威力
在《設計模式-可復用面向對象軟件的基礎》的序言里提到軟件設計的兩個基本原則:
針對接口編程,而不是針對實現編程。接口是抽象的,因為抽象所以簡單。接口是對象的本質,因為是本質所以穩定。接口是降低復雜度和隔離變化的有力武器,C語言里沒有接口的概念,不是因為接口不重要,而是C語言把它視為理所當然的東西(函數指針無所不在), 正所謂玫瑰不叫玫瑰,依然芳香如故。在前面我們已經看到,C語言里的接口是相當直觀和優雅的。
優先使用組合,而不是類繼承。與組合相比,繼承更為復雜,特別是多重繼承和多層繼承,甚至會帶來一些歧義,給理解上造成困難。與組合相比,繼承缺乏靈活性,繼承在編譯時就綁定了父類和子類之間的關系,而組合卻可以在運行時動態改變。C語言沒有繼承的概念(當然可以實現繼承),自然大量使用組合來構建大型系統,這在客觀上恰恰與設計原則是一致的。
本章節將借助隊列,棧和哈表來練習這種基本的重用方法。請讀者實現隊列,棧和哈表,要求重用前面的鏈表實現。
隊列
隊列是一種很常用的數據,操作系統用隊列來管理運行的進程,驅動程序用隊列來管理要傳輸的數據包,GUI框架用隊列來管理各種GUI事件。隊列是一種先進先出(FIFO, First in First out)的數據結構,數據只能從隊列頭取,向隊列尾追加。隊列的名稱很形象的表達了它的意義,就像排隊上車一樣,前面的先上,后來的站在后面排隊。
隊列主要的接口函數有:
o 創建隊列:queue_create
o 取隊列頭的元素:queue_head
o 追加一個元素到隊列尾:queue_push
o 刪除隊列頭元素:queue_pop
o 取隊列中元素個數(同時也可以判斷隊列是否為空):queue_length
o 遍歷隊列中的元素:queue_foreach;
o 銷毀隊列 queue_destroy
隊列看起來比鏈表和數組要高級一點,其實它只不過是鏈表和數組的一種特殊形式而已,下面我們重用鏈表來實現隊列:
o 隊列的數據結構
struct _Queue {DList* dlist; };這里隊列只是對雙向鏈表的一個包裝。
o 創建隊列
Queue* queue_create(DataDestroyFunc data_destroy, void* ctx) {Queue* thiz = (Queue*)malloc(sizeof(Queue));if(thiz != NULL){if((thiz->dlist = dlist_create(data_destroy, ctx)) == NULL){free(thiz);thiz = NULL;}}return thiz; }創建隊列時,除了分配自己的空間外,就是簡單的創建一個雙向鏈表。
o 取隊列頭的元素
Ret queue_head(Queue* thiz, void** data) {return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);return dlist_get_by_index(thiz->dlist, 0, data); }我們認為鏈表的第一個元素是隊列頭,取隊列頭的元素就是取鏈表的第一個元素。
o 追加一個元素到隊列尾
Ret queue_push(Queue* thiz, void* data) {return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);return dlist_append(thiz->dlist, data); }我們認為鏈表的最后一個元素是隊列尾,追加一個元素到隊列尾就是追加一個元素到鏈表尾。
o 刪除隊列頭元素
Ret queue_pop(Queue* thiz) {return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);return dlist_delete(thiz->dlist, 0); }刪除隊列頭的元素就是刪除鏈表的第一個元素。
o 取隊列中元素個數
size_t queue_length(Queue* thiz) {return_val_if_fail(thiz != NULL, 0);return dlist_length(thiz->dlist); }隊列中元素的個數等同于鏈表元素的個數。
o 遍歷隊列中的元素
Ret queue_foreach(Queue* thiz, DataVisitFunc visit, void* ctx) {return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);return dlist_foreach(thiz->dlist, visit, ctx); }遍歷隊列中的元素等同于遍歷鏈表中的元素。
o 銷毀隊列
void queue_destroy(Queue* thiz) {if(thiz != NULL){dlist_destroy(thiz->dlist);thiz->dlist = NULL;free(thiz);}return; }銷毀鏈表然后釋放自身的空間。
用組合的方式實現隊列很簡單吧,不用半小時就可以寫出來。雖然鏈表已經通過了自動測試,隊列的自動測試也不能省,在這里我們就不列出代碼了。
上面我們實現的是通用隊列,除了通用隊列外,還有幾種特殊隊列應用也非常廣泛:
o 優先級隊列。它的不同之外在于,插入元素時,不必追加到隊尾,而是根據元素的優先級插到隊列的適當位置。這個就像排隊上車時,后面來了個老人,大家讓他先上一樣的。內核的進程管理器通常采用估先級隊列管理進程。
o 循環隊列。循環隊列的特點是最大元素個數是固定的。這個我們在前面學習同步時已經提過,它的優點是兩個并發的實體(線程或進程),按一個讀一個寫的方式訪問,不需要加鎖。設備驅動程序經常使用循環隊列來管理數據包。
棧
棧是一種后進先出(LIFO, last in first out)的數據結構,與隊列的先進先出(FIFO)相比,這種規則似乎不太公平,計算機可不管這個。事實上,棧是最重要的數據結構之一:沒有棧,基于下推自動機的編譯器不能工作,我們只能寫匯編程序。沒有棧,無法實現遞歸/多級函數調用,程序根本就無法工作。
棧主要的接口函數有:
o 創建棧 stack_create
o 取棧頂元素 stack_top
o 放入元素到棧頂stack_push
o 刪棧棧頂元素stack_pop
o 取棧中元素個數 stack_length
o 遍歷棧中的元素stack_foreach
o 銷毀棧 stack_destroy
棧同樣是鏈表和數組的一種特殊形式而已,下面我們重用鏈表來實現棧:
o 棧的數據結構
struct _Stack {DList* dlist; };這里和隊列的數據結構一樣,由一個鏈表組成。
o 創建棧
Stack* stack_create(DataDestroyFunc data_destroy, void* ctx) {Stack* thiz = (Stack*)malloc(sizeof(Stack));if(thiz != NULL){if((thiz->dlist = dlist_create(data_destroy, ctx)) == NULL){free(thiz);thiz = NULL;}}return thiz; }創建棧時,除了分配自己的空間外,就是簡單的創建一個雙向鏈表。
o 取棧頂元素
Ret stack_top(Stack* thiz, void** data) {return_val_if_fail(thiz != NULL && data != NULL, RET_INVALID_PARAMS);return dlist_get_by_index(thiz->dlist, 0, data); }我們認為鏈表的第一個元素是棧頂,取棧頂的元素就是取鏈表的第一個元素。
o 放入元素到棧頂
Ret stack_push(Stack* thiz, void* data) {return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);return dlist_prepend(thiz->dlist, data); }放入元素到棧頂就是插入一個元素到鏈表頭。
o 刪棧棧頂元素
Ret stack_pop(Stack* thiz) {return_val_if_fail(thiz != NULL, RET_INVALID_PARAMS);return dlist_delete(thiz->dlist, 0); }刪棧棧頂元素就是刪除鏈表的第一個元素。
o 取棧中元素個數
size_t stack_length(Stack* thiz) {return_val_if_fail(thiz != NULL, 0);return dlist_length(thiz->dlist); }棧中的個數等同于鏈表的個數。
o 遍歷棧中的元素
Ret stack_foreach(Stack* thiz, DataVisitFunc visit, void* ctx) {return_val_if_fail(thiz != NULL && visit != NULL, RET_INVALID_PARAMS);return dlist_foreach(thiz->dlist, visit, ctx); }遍歷棧中的元素等同于遍歷鏈表中的元素。
o 銷毀棧
void stack_destroy(Stack* thiz) {if(thiz != NULL){dlist_destroy(thiz->dlist);thiz->dlist = NULL;free(thiz);}return; }銷毀雙向鏈表然后釋放自身的空間。
棧是一個非常重要的數據,但奇怪的是我們很少有機會去寫它。事實上,我從來沒有在工作中寫過一個棧。這是怎么回事呢?原因是我們的計算機本身是基于棧的,很多事情計算機已經在我們不知道的情況下幫我們處理了,比如函數調用(特殊是遞歸調用),計算機幫我們處理了。用遞歸下降進行的語法分析利用了函數調用的遞歸性,也不需要顯式的構造棧。
《新程序員》:云原生和全面數字化實踐50位技術專家共同創作,文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的系统程序员成长计划-组合的威力的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: C语言回调函数
- 下一篇: 教你打造 Android 中的 IOC