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