周立功教授數年之心血之作《程序設計與數據結構》以及《面向AMetal框架與接口的編程(上)》,書本內容公開后,在電子行業掀起一片學習熱潮。經周立功教授授權,本公眾號特對《程序設計與數據結構》一書內容進行連載,愿共勉之。
第三章為算法與數據結構,本文為3.3 雙向鏈表。
>>> 3.3 雙向鏈表
單向鏈表的添加、刪除操作,都必須找到當前結點的上一個結點,以便修改上一個結點的p_next指針完成相應的操作。由于單向鏈表的結點沒有指向其上一個結點的指針,因此只有從頭結點開始遍歷鏈表。當某一結點的p_next指向當前結點時,表明它為當前結點的上一個結點。顯然每次都要從頭開始遍歷,其效率極為低下。在單向鏈表中,之所以可以直接獲取單向鏈表中當前結點的下一個結點,是因為結點中包含了指向下一個結點的指針p_next。如果在雙向鏈表的結點中再增加一個指向它的前一個結點的前向指針p_prev,則一切問題將迎刃而解。那么,既有指向下一個結點的指針,又有指向前一個結點的指針的鏈表稱之為雙向鏈表,示意圖詳見圖3.15。
圖3.15 雙向鏈表示意圖
與單向鏈表一樣,雙向鏈表也定義了一個頭結點,基于單向鏈表將應用數據與鏈表結構相關數據完全分離的設計思想,則雙向鏈表結點僅保留p_next和p_prev指針。其數據結構定義如下:
其中,dlist是double list 的縮寫,表明該結點是雙向鏈表結點。由此可見,雖然前向指針使得尋找鏈表的上一個結點變得非常容易,但由于結點中新增了一個指針,因此其內存開銷將會是單向鏈表的兩倍。在實際應用中,應該權衡效率與內存空間,在內存資源非常緊缺的場合,如果結點的添加、刪除操作很少,一點效率的影響可以接受,則選擇使用單向鏈表。而不是一味地追求效率,認為雙向鏈表比單向鏈表好,始終選擇使用雙向鏈表。
在圖3.15中,頭結點的p_prev和尾結點的p_next直接被設置為了NULL,此時,如果要直接由頭結點找到尾結點,或者由尾結點找到頭結點,都必須遍歷整個鏈表。可以對這兩個指針稍加利用,使頭結點的p_prev指向尾結點,尾結點的p_next指向頭結點,此時,該雙向鏈表就成了一個循環雙向鏈表,示意圖詳見圖3.16。
圖3.16 循環雙向鏈表示意圖
由于循環雙向鏈表的效率更高,可以直接從頭結點找到尾結點,或者從尾結點找到頭結點,且沒有額外的內存空間消耗,僅僅是使用了兩個不打算使用的指針,算是廢物利用,因此下面介紹的雙向鏈表均視為循環雙向鏈表。
類似于單向鏈表,雖然頭結點與普通結點的內容完全相同,但它們的含義卻有所區別,頭結點是鏈表的頭,代表了整個鏈表,擁有此頭結點,就表示其擁有了整個鏈表。為了便于區分頭結點與普通結點,可以單獨定義一個頭結點類型。比如:
當需要使用雙向鏈表時,首先需要使用該類型定義一個頭結點。比如:
由于此時還沒有添加其它任何結點,僅存在一個頭結點,因此該頭結點既是第一個結點(頭結點),又是最后一個結點(尾結點)。按照循環鏈表的定義,尾結點的p_next指向頭結點,頭結點的p_prev指向尾結點,僅有一個結點的示意圖詳見圖3.17。
圖3.17 空鏈表
顯然,僅有頭結點時,其p_next和p_prev都指向本身。即:
為了避免用戶直接操作成員,需要定義一個初始化函數,專門用于初始化鏈表頭結點中各個成員的值,其函數原型(dlist.h)為:
其中,p_head指向待初始化的鏈表頭結點。其調用形式如下:
dlist_init()函數的實現詳見程序清單3.33。
程序清單3.33 雙向鏈表初始化函數
與單向鏈表類似,將提供一些基礎的操作接口,它們的函數原型如下:
對于dlist_prev_get()和dlist_next_get(),在鏈表結點中已經存在指向前驅后后繼的指針,詳見程序清單3.34。
程序清單3.34 得到結點前驅和后繼的函數實現
dlist_tail_get()函數用于得到鏈表的尾結點,在循環雙向鏈表中,頭結點的p_reev即指向了尾結點,詳見程序清單3.35。
程序清單3.35 dlist_tail_get()函數實現
dlist_begin_get()函數用于得到第一個用戶結點,詳見程序清單3.36。
程序清單3.36 dlist_begin_get()函數實現
dlist_end_get()用于得到鏈表的結束位置,當雙向鏈表設計為循環雙向鏈表時,則頭結點的p_prev和尾結點的p_next都被有效地利用了,任何有效結點的p_next和p_prev都不再為NULL。顯然,不能再以NULL作為結束位置了,當從第一個結點開始順序訪問鏈表的各個結點時,尾結點的下一個結點就是鏈表頭結點(head),因此結束位置就是頭結點本身。dlist_end_get()的實現詳見程序清單3.37。
程序清單3.37 dlist_end_get()函數實現
3.3.1 添加結點
假定還是將結點添加到鏈表尾部,其函數原型為:
其中,p_head為指向鏈表頭結點的指針,p_node為指向待添加結點的指針,其使用范例詳見程序清單3.38。
程序清單3.38 dlist_add_tail()函數使用范例
為了實現該函數,可以先查看添加結點前后鏈表的變化,詳見圖3.18。
圖3.18 添加結點示意圖
由此可見,添加一個結點至鏈表尾部,需要4個指針(圖中虛線箭頭):
-
新結點的p_prev指向尾結點;
-
新結點的p_next指向頭結點;
-
尾結點的p_next由指向頭結點變為指向新結點;
-
頭結點的p_prev由指向尾結點修改為指向新結點。
通過這些操作后,當結點添加到鏈表尾部后,就成為了新的尾結點,詳見程序清單3.39。
程序清單3.39 dlist_add_tail()函數實現
實際上循環鏈表,無論是頭結點、尾結點還是普通結點,其本質上都是一樣的,均為p_next成員指向下一個結點,p_prev成員指向其上一個結點。因此,對于添加結點而言,無論將結點添加到鏈表頭、鏈表尾還是其它任意位置,其操作方法完全相同。為此,需要提供一個更加通用的函數,可以將結點添加到任意結點之后,其函數原型為:
其中,p_head為指向鏈表頭結點的指針,p_pos指定了添加的位置,新結點即添加在該指針指向的結點之后;p_node為指向待添加結點的指針。比如,同樣將結點添加到鏈表尾部,其使用范例詳見程序清單3.40。
程序清單3.40 dlist_add()函數使用范例
由此可見,將尾結點作為結點添加的位置,同樣可以將結點添加至尾結點之后,即添加到鏈表尾部。顯然,也就沒有必要再編寫dlist_add_tail()實現代碼了,使用dlisd_add()即可,修改dlist_add_tail()函數的實現,詳見程序清單3.41。
程序清單3.41 dlist_add_tail()函數實現
為了實現dlist_add()函數,可以先查看添加一個結點到任意結點之后的情況,詳見圖3.19。圖中展示的是一種通用的情況,由于結點的添加位置(頭、尾或其它任意位置)與添加結點的方法沒有關系,因此沒有特別標明頭結點和尾結點。
圖3.19 添加結點示意圖
其實,對比圖3.18和圖3.19可以發現,圖3.18展示的只是圖3.19的一個特例,即恰好圖3.19中的新結點之前的結點就是尾結點,添加結點的過程同樣需要修改4個指針的值。為便于描述,將新結點前的結點稱之為前結點,新結點之后的結點稱之為后結點。顯然,在添加新結點之前,前結點的下一個結點即為后結點。對設置4個指針值的描述如下:
-
新結點的p_prev指向前結點;
-
新結點的p_next指向后結點;
-
前結點的p_next由指向后結點變為指向新結點;
-
后結點的p_prev由指向前結點修改為指向新結點。
對比將結點添加到鏈表尾部的描述,只要將描述中的“前結點”換為“尾結點”,“后結點”換為“頭結點”,它們的含義則完全一樣,顯然將結點添加到鏈表尾部只是這里的一個特例,添加結點的函數實現詳見程序清單3.42。
程序清單3.42 dlist_add()函數實現
盡管上面的函數在實現時并沒有用到參數p_head,但還是將p_head參數傳進來了,因為實現其它的功能時將會用到p_head參數,比如,判斷p_pos是否在鏈表中。
有了該函數,添加結點到任意位置就非常靈活了,比如,提供一個添加結點到鏈表的頭部,使其作為鏈表的第一個結點的函數,其函數原型為:
此時,頭結點即為新添加結點的前結點,直接調用dlist_add()即可實現,其實現范例詳見程序清單3.43。
程序清單3.43 dlist_add_head()函數實現
3.3.2 刪除結點
基于添加結點到任意位置的思想,需要實現一個刪除任意結點的函數。其函數原型為:
其中,p_head為指向鏈表頭結點的指針, p_node為指向待刪除結點的指針,使用范例詳見程序清單3.44。
程序清單3.44 dlist_del()使用范例程序
為了實現dlisd_del()函數,可以先查看刪除任意結點的示意圖,圖 3.20(1)為刪除節點前的示意圖,圖 3.20(2)為刪除節點后的示意圖。
圖 3.20添加結點示意圖
由此可見,僅需要修改兩個指針的值:
-
將“刪除結點”的前結點的p_next修改為指向“刪除結點”的后結點;
-
將“刪除結點”的后結點的p_prev修改為指向“刪除結點”的前結點。
刪除結點函數的實現詳見程序清單3.45。
程序清單3.45 dlist_del()函數實現
為了防止刪除頭結點,程序中對p_head與p_node進行了比較,當p_node為頭結點時,則直接返回錯誤。
3.3.3 遍歷鏈表
與單向鏈表類似,需要一個遍歷鏈表各個結點的函數,其函數原型(dlist.h)為:
其中,p_head指向鏈表頭結點,pfn_node_process為結點處理回調函數,每遍歷到一個結點時,均會調用該函數,便于用戶處理結點。dlist_node_process_t類型定義如下:
dlist_node_process_t類型參數為一個p_arg指針和一個結點指針,返回值為int類型的函數指針。每遍歷到一個結點均會調用pfn_node_process指向的函數,便于用戶根據需要自行處理結點數據。當調用該回調函數時,傳遞給p_arg的值即為用戶參數,其值與dlist_traverse()函數的第3個參數一樣,即該參數的值完全是由用戶決定的;傳遞給p_node 的值即為指向當前遍歷到的結點的指針。當遍歷到某個結點時,如果用戶希望終止遍歷,此時,只要在回調函數中返回負值即可終止繼續遍歷。一般地,若要繼續遍歷,則函數執行結束后返回0即可。dlist_foreach()函數的實現詳見程序清單3.46。
程序清單3.46 鏈表遍歷函數的實現
為了便于查閱,如程序清單3.47所示展示了dlist.h文件的內容。
程序清單3.47 dlist.h文件內容
同樣以int類型數據為例,來展示這些接口的使用方法。為了使用鏈表,首先應該定義一個結構體,將鏈表結點作為其一個成員,此外,再添加一些應用相關的數據,如定義如下包含鏈表結點和int型數據的結構體:
綜合范例程序詳見程序清單3.48。
程序清單3.48 綜合范例程序
與單向鏈表的綜合范例程序比較可以發現,程序主體是完全一樣的,僅僅是各個結點的類型發生了改變。對于實際的應用,如果由使用單向鏈表升級為雙向鏈表,雖然程序主體沒有發生改變,但由于類型的變化,則不得不修改所有程序代碼。這是由于應用與具體數據結構沒有分離造成的,因此可以進一步將實際應用與具體的數據結構分離,將鏈表等數據結構抽象為“容器”的概念。
-
周立功
+關注
關注
38文章
130瀏覽量
37616 -
鏈表
+關注
關注
0文章
80瀏覽量
10558
原文標題:周立功:高效使用雙向鏈表
文章出處:【微信號:ZLG_zhiyuan,微信公眾號:ZLG致遠電子】歡迎添加關注!文章轉載請注明出處。
發布評論請先 登錄
相關推薦
評論