|
除了個別天才程序員外，沒有人一開始就能寫出讓人驚嘆的代碼，都是從模仿開始的!不要相信你身邊的人說他能很輕松的自己編寫出讓人驚嘆的代碼而不用任何的參考資料，因為我相信在你我的身邊沒有這樣的天才程序員，所以我們都選擇從模仿和閱讀源代碼開始。就好比一個優秀的作家不是一開始就能寫出好的文章，他也是閱讀了很多優秀的文章之后才能寫出優秀作品的。一開始我想詳細的講解雙鏈表部分，但是我發現由于代碼的原因，使得文章的篇幅過大，所以在此就選擇一些易錯和場用的知識點來進行講解，如果一開始你發現閱讀代碼時很吃力，請不要放棄!我們要有毅力去把它消化掉，融會貫通之后再寫出我們自己的雙鏈表，當然我給出的僅僅只是一個參考而已。 在此也要特地感謝下編程浪子朱云翔老師，閱讀我博客后提出的寶貴意見，根據你的建議我接下來的博客中都把代碼部分放到了代碼框中，使得代碼看起來更加的悅目。 前一篇博客中我們講解了單鏈表，那么接下來還是按照我們之前的安排講解雙鏈表部分， 在開始講解之前，我們先來簡單的回顧下上一篇博客中的雙鏈表，雙鏈表是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。對雙鏈表做了一個簡單的回顧之后那么接下來我們就來開始講解雙鏈表了，在這里我們也同樣遵循一個原則，就是用簡單易懂的代碼和文字描述來講解，我們要突出代碼的重點是在編程的過程中我們的易錯點。 因為雙鏈表的使用相對于單鏈表操作來說要復雜和常用些，所以在這里我采用逐漸添加功能模塊的方法來進行講解，從易到難，讓讀者理解起來更加輕松，同時我們在這里也使用我前面博客中提到的一些方法，學以致用嘛，學了就要在代碼中盡可能的使用起來，要不然學了有什么用呢，接下來我們先來看看一個最為簡單的雙鏈表的創建。 特此說明： 1、如果在接下來的代碼中發現一些不懂而我又沒有給出提示信息的，如自己定義枚舉型的數據結構DListReturn作為返回類型等，那么請你看我的前一篇博客《C語言的那些小秘密之鏈表(一)》。 2、由于文章在編輯的時候可以對代碼部分使用顏色標記，但是發表后好像顯示不出來，我試圖修改，但還是不行，所以在此說明下，代碼中被“” 和“ ”框起來的部分為有色部分。讀者自己在閱讀代碼的時候注意下，自己對比也能找到新加入的代碼。 #include #include typedef enum _DListReturn { DLIST_RETURN_OK, DLIST_RETURN_FAIL }DListReturn; typedef struct _DStu { int score; }DStu; typedef struct _DListNode { struct _DListNode* prev; struct _DListNode* next; DStu* data; }DListNode; typedef struct _DList { DListNode* head; }DList; typedef DListReturn (*DListPrintFunction)(void* data); DListNode* dlist_node_create(void* data) { DListNode* node; if((node = (DListNode*) malloc(sizeof(DListNode)))==NULL) { printf("分配空間失敗!"); exit(0); } if(node != NULL) { node->prev = NULL; node->next = NULL; node->data =(DStu*)data; } return node; } DList* dlist_head_create(void) { DList* thiz; if((thiz = (DList*)malloc(sizeof(DList)))==NULL) { printf("分配空間失敗!"); exit(0); } if(thiz != NULL) { thiz->head = NULL; } return thiz; } DListReturn dlist_append(DList* thiz, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; if((node = dlist_node_create(data)) == NULL) { return DLIST_RETURN_OK; } if(thiz->head == NULL) { thiz->head = node; return DLIST_RETURN_OK; } cursor = thiz->head; while(cursor != NULL && cursor->next != NULL) { cursor = cursor->next; } cursor->next = node; node->prev = cursor; return DLIST_RETURN_OK; } DListReturn dlist_print(DList* thiz, DListPrintFunction print) { DListNode* iter = thiz->head; while(iter != NULL) { print(iter->data); iter = iter->next; } printf("\n"); return DLIST_RETURN_OK; } DListReturn print_int(void* data) { DStu* ss=(DStu*)data; printf("%d\t ", ss->score); return DLIST_RETURN_OK; } int main(int argc, char* argv[]) { int i = 0; DList* dlist = dlist_head_create(); for(i = 0; i score = i; dlist_append(dlist, (void*)stu); } dlist_print(dlist, print_int); return 0; } 運行結果為： 0 1 2 3 4 5 6 Press any key to continue 可能有的讀者認為上面得代碼有點復雜化了，其實不然，我們僅僅是寫出了我們要講解的雙鏈表實現中最簡單的部分，其實現的功能是創建一個鏈表，在鏈表末端添加結點，然后打印出鏈表中結點里存放的數據項，對代碼的總體動能有了一個大概的了解之后，現在我們來逐一分析代碼，為接下來添加功能模塊打開思路。 從main()函數開始，通過 DList* dlist = dlist_head_create();我們創建了一個頭節點。值得注意的是，為了鏈表更加通用和符合實際需求，我們在此創建的鏈表存放的是結構，因為現實中在使用鏈表時，絕大部分都是存放結構的，而前一篇文章中我們創建單鏈表時我們存放的是數據，所以這一點讀者是要引起注意的，接下來是一個for循環語句，在for循環語句中我們首先使用DStu* stu =(DStu*) malloc(sizeof(DStu));為stu分配了空間，這也是很多讀者的一個易錯點，不分配就使用下面的stu->score = i;語句，從而導致出錯，如果讀者對于指針還不是很了解的話可以看看我前面的文章《C語言的那些小秘密之指針》，在往下看dlist_append(dlist, (void*)stu);語句，從函數名稱我們也可以看出它的功能是在鏈表的末端添加結點的，在函數里面我們使用了一個if判斷語句來看分配的結點是否成功，如果成功繼續往下執行，如果失敗則返回DLIST_RETURN_FAIL。對于第一次分配的節點我們使用了 thiz->head = node;語句使其變為頭結點，在第二次調用dlist_append(dlist, (void*)stu)函數分配結點之后，由于頭結點已經不再為空，那么跳過if(thiz->head == NULL)語句，執行以下語句： cursor = thiz->head; while(cursor != NULL && cursor->next != NULL) { cursor = cursor->next; } 其功能為查找末端結點，然后使用 cursor->next = node; node->prev = cursor;語句來將剛剛創建的新結點node作為尾結點。main()函數中的for循環語句執行完之后就輪到了調用dlist_print(dlist, print_int)函數打印我們創建的雙向鏈表保存的數據值了，在這里的時候我們用了前面我博客中提到的函數指針作為參數的使用，如果有對函數指針不熟悉的讀者可以參考我之前寫的一篇博客《C語言的那些小秘密之函數指針》，到此讀者應該都理解了上面的代碼，但是其中有個值得注意的地方，那就是main()函數中使用dlist_append(dlist, (void*)stu);的時候，我們傳遞的是一個無類型的指針，在創建新結點的時候，我們使用了一句node->data =(DStu*)data;進行一個強制轉換，使得鏈表中的數據域指向的就是我們使用DStu* stu =(DStu*) malloc(sizeof(DStu));所創建的空間。創建了空間之后當然要釋放掉，所以接下來我們就添加一個釋放功能模塊。新添加的代碼我們用紅色部分來標記。以便于讀者的閱讀 #include #include typedef enum _DListReturn { DLIST_RETURN_OK, DLIST_RETURN_FAIL }DListReturn; typedef struct _DStu { int score; }DStu; typedef struct _DListNode { struct _DListNode* prev; struct _DListNode* next; DStu* data; }DListNode; typedef struct _DList { DListNode* head; }DList; typedef DListReturn (*DListPrintFunction)(void* data); DListNode* dlist_node_create(void* data) { DListNode* node; if((node = (DListNode*) malloc(sizeof(DListNode)))==NULL) { printf("分配空間失敗!"); exit(0); } if(node != NULL) { node->prev = NULL; node->next = NULL; node->data =(DStu*)data; } return node; } DList* dlist_head_create(void) { DList* thiz; if((thiz = (DList*)malloc(sizeof(DList)))==NULL) { printf("分配空間失敗!"); exit(0); } if(thiz != NULL) { thiz->head = NULL; } return thiz; } DListReturn dlist_append(DList* thiz, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; if((node = dlist_node_create(data)) == NULL) { return DLIST_RETURN_FAIL; } if(thiz->head == NULL) { thiz->head = node; return DLIST_RETURN_OK; } cursor = thiz->head; while(cursor != NULL && cursor->next != NULL) { cursor = cursor->next; } cursor->next = node; node->prev = cursor; return DLIST_RETURN_OK; } DListReturn dlist_prepend(DList* thiz, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; if((node = dlist_node_create(data)) == NULL) { return DLIST_RETURN_FAIL; } if(thiz->head == NULL) { thiz->head = node; return DLIST_RETURN_OK; } cursor = thiz->head; if(thiz->head == cursor) thiz->head = node; node->next = cursor; cursor->prev = node; return DLIST_RETURN_OK; } DListReturn dlist_print(DList* thiz, DListPrintFunction print) { DListNode* iter = thiz->head; while(iter != NULL) { print(iter->data); iter = iter->next; } printf("\n"); return DLIST_RETURN_OK; } DListReturn print_int(void* data) { DStu* ss=(DStu*)data; printf("%d\t ", ss->score); return DLIST_RETURN_OK; } DListReturn dlist_node_destroy(DListNode* node) { if(node != NULL) { node->next = NULL; node->prev = NULL; free(node); } return DLIST_RETURN_OK; } DListReturn dlist_destroy(DList* thiz) { DListNode* iter = thiz->head; DListNode* next = NULL; while(iter != NULL) { next = iter->next; dlist_node_destroy(iter); iter = next; } thiz->head = NULL; free(thiz); return DLIST_RETURN_OK; } int main(int argc, char* argv[]) { int i = 0; int n = 10; DList* dlist = dlist_head_create(); DStu* stu[7]; for(i = 0; i score = i; dlist_append(dlist, (void*)stu); } dlist_print(dlist, print_int); for(i = 0; i 在使用dlist_append(dlist, (void*)stu);語句的時候我們傳遞的是stu的指針，所以在創建結點的時候我們使用的node->data =(DStu*)data;語句使得data強制轉換為了DStu結構類型指針，即在結點創建函數中我們僅僅是使數據域的結構指針data指向了stu所分配的存儲空間，和stu指向的是同一個空間，但是在釋放結點時，我們僅僅是釋放掉了存放data指針變量的空間，并沒有釋放掉data所指向的空間，所以我們在main函數中我們最后使用了一個for循環語句來釋放data所指向的存儲空間。在此也講講之前我給出的以下代碼和我們雙鏈表釋放方式的區別。 #include #include int main() { int *pointer_1=(int *)malloc(sizeof(int)); int *pointer_2=(int *)malloc(sizeof(int)); pointer_1=pointer_2; printf("%d\n",pointer_1); printf("%d\n",pointer_2); printf("%d\n",&pointer_1); printf("%d\n",&pointer_2); //free(pointer_1); free(pointer_2); return 0; } 運行結果為： 3674136 3674136 1245052 1245048 Press any key to continue 雖然兩個指針變量存放在不同的單元，但是它們都指向同一個存儲單元，所以在釋放的時候只能釋放一次，如果釋放兩次就會出錯。注意切不可同時使用free(pointer_1);和 free(pointer_2);，否則將會出現內存錯誤。對出錯原因不懂的可以參考我前面的文章《C語言的那些小秘密之指針》。這個代碼和我們雙鏈表的最大區別是它只能使用free()函數進行一次釋放，而我們雙鏈表中看似使用了兩次，但實則一次而已。原因就在于我們在對頭結點分配空間的時候分配的是存放data指針變量的存儲空間(注意：所有的指針變量在分配的時候均分配4字節大小的存儲空間，如果有什么疑惑可以參考我之前寫的《C語言的那些小秘密之指針》)。所以釋放的時候也是釋放的存放指針變量data的存儲空間，并沒有釋放掉指針變量data所指向的存儲空間。所以在釋放data指向的存儲空間時，我們只需要在main()函數中對stu所指向的存儲空間使用free()函數即可，因為data和它指向的是同一個存儲空間。 接下來我們來添加一個在頭結點添加結點的模塊。 #include #include typedef enum _DListReturn { DLIST_RETURN_OK, DLIST_RETURN_FAIL }DListReturn; typedef struct _DStu { int score; }DStu; typedef struct _DListNode { struct _DListNode* prev; struct _DListNode* next; DStu* data; }DListNode; typedef struct _DList { DListNode* head; }DList; typedef DListReturn (*DListPrintFunction)(void* data); DListNode* dlist_node_create(void* data) { DListNode* node; if((node = (DListNode*) malloc(sizeof(DListNode)))==NULL) { printf("分配空間失敗!"); exit(0); } if(node != NULL) { node->prev = NULL; node->next = NULL; node->data =(DStu*)data; } return node; } DList* dlist_head_create(void) { DList* thiz; if((thiz = (DList*)malloc(sizeof(DList)))==NULL) { printf("分配空間失敗!"); exit(0); } if(thiz != NULL) { thiz->head = NULL; } return thiz; } DListReturn dlist_append(DList* thiz, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; if((node = dlist_node_create(data)) == NULL) { return DLIST_RETURN_FAIL; } if(thiz->head == NULL) { thiz->head = node; return DLIST_RETURN_OK; } cursor = thiz->head; while(cursor != NULL && cursor->next != NULL) { cursor = cursor->next; } cursor->next = node; node->prev = cursor; return DLIST_RETURN_OK; } DListReturn dlist_prepend(DList* thiz, void* data) { DListNode* node = NULL; DListNode* cursor = NULL; if((node = dlist_node_create(data)) == NULL) { return DLIST_RETURN_FAIL; } if(thiz->head == NULL) { thiz->head = node; return DLIST_RETURN_OK; } cursor = thiz->head; if(thiz->head == cursor) thiz->head = node; node->next = cursor; cursor->prev = node; return DLIST_RETURN_OK; } DListReturn dlist_print(DList* thiz, DListPrintFunction print) { DListNode* iter = thiz->head; while(iter != NULL) { print(iter->data); iter = iter->next; } printf("\n"); return DLIST_RETURN_OK; } DListReturn print_int(void* data) { DStu* ss=(DStu*)data; printf("%d\t ", ss->score); return DLIST_RETURN_OK; } DListReturn dlist_node_destroy(DListNode* node) { if(node != NULL) { node->next = NULL; node->prev = NULL; free(node); } return DLIST_RETURN_OK; } DListReturn dlist_destroy(DList* thiz) { DListNode* iter = thiz->head; DListNode* next = NULL; while(iter != NULL) { next = iter->next; dlist_node_destroy(iter); iter = next; } thiz->head = NULL; free(thiz); return DLIST_RETURN_OK; } int main(int argc, char* argv[]) { int i = 0; DList* dlist = dlist_head_create(); for(i = 0; i { DStu* stu =(DStu*) malloc(sizeof(DStu)); stu->score = i; dlist_append(dlist, (void*)stu); } for(i = 0; i { DStu* stu =(DStu*) malloc(sizeof(DStu)); stu->score = i; dlist_prepend(dlist, (void*)stu); } dlist_print(dlist, print_int); dlist_destroy(dlist); return 0; } 我們在上一段代碼添加了紅色部分代碼后，使得其在已經生成的雙鏈表的頭結點處添加結點，運行結果如下： 6 5 4 3 2 1 0 0 1 2 3 4 5 6 Press any key to continue 可以看出結果與我們的要求完全符合。如果你認真分析了代碼的話你就會發現，我們的兩種添加方式中有公共代碼出現，那就說明我們的代碼可以繼續改進，把公共代碼放到一個函數中，讀者可以另外編寫一個函數來實現，使得我們編寫的代碼得到充分的利用。 篇幅似乎有些過長了，接下來我就不再一一講解了，我在這里只是想起一個引路的作用，讀者完全可以在此基礎之上繼續編寫雙鏈表其余部分的功能，其他的功能模塊讀者可以在此基礎上一一添加上去，到下一篇的時候我們將走進linux內核鏈表，繼續鏈表之旅的最后一站。由于本人水平有限，博客中的不妥或錯誤之處在所難免，殷切希望讀者批評指正。同時也歡迎讀者共同探討相關的內容，如果樂意交流的話請留下你寶貴的意見。 |
