色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

周立功闡釋高效的雙向鏈表如何用

UtFs_Zlgmcu7890 ? 來源:互聯(lián)網(wǎng) ? 作者:佚名 ? 2017-09-25 14:14 ? 次閱讀

近日周立功教授公開了數(shù)年的心血之作《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》,電子版已無償性分享到電子工程師與高校群體下載,經(jīng)周立功教授授權(quán),特對本書內(nèi)容進(jìn)行連載。

>>>>1.1.1 添加結(jié)點

假定還是將結(jié)點添加到鏈表尾部,其函數(shù)原型為:

int dlist_add_tail(dlist_head_t *p_head, dlist_node_t *p_node);

其中,p_head為指向鏈表頭結(jié)點的指針,p_node為指向待添加結(jié)點的指針,其使用范例詳見程序清單3.38

程序清單3.38 dlist_add_tail()函數(shù)使用范例

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add_tail(&head, &node);

8 // ……

9 }

為了實現(xiàn)該函數(shù),可以先查看添加結(jié)點前后鏈表的變化,詳見圖3.18

圖3.18 添加結(jié)點示意圖

由此可見,添加一個結(jié)點至鏈表尾部,需要4個指針(圖中虛線箭頭):

● 新結(jié)點的p_prev指向尾結(jié)點;

● 新結(jié)點的p_next指向頭結(jié)點;

● 尾結(jié)點的p_next由指向頭結(jié)點變?yōu)橹?/span>

向新結(jié)點;

● 頭結(jié)點的p_prev由指向尾結(jié)點修改為指向新結(jié)點。

通過這些操作后,當(dāng)結(jié)點添加到鏈表尾部后,就成為了新的尾結(jié)點,詳見程序清單3.39

程序清單3.39 dlist_add_tail()函數(shù)實現(xiàn)

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 if (p_head == NULL){

4 return -1;

5 }

6 p_node -> p_prev = p_head->p_prev; // 新結(jié)點的p_prev指向尾結(jié)點

7 p_node -> p_next = p_head; // 新結(jié)點的p_next指向頭結(jié)點

8 p_head -> p_prev->p_next = p_node; // 尾結(jié)點的p_next指向新結(jié)點

9 p_head -> p_prev = p_node; // 頭結(jié)點的p_prev指向新結(jié)點

10 return 0;

11 }

實際上循環(huán)鏈表,無論是頭結(jié)點、尾結(jié)點還是普通結(jié)點,其本質(zhì)上都是一樣的,均為p_next成員指向下一個結(jié)點,p_prev成員指向其上一個結(jié)點。因此,對于添加結(jié)點而言,無論將結(jié)點添加到鏈表頭、鏈表尾還是其它任意位置,其操作方法完全相同。為此,需要提供一個更加通用的函數(shù),可以將結(jié)點添加到任意結(jié)點之后,其函數(shù)原型為:

int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node);

其中,p_head為指向鏈表頭結(jié)點的指針,p_pos指定了添加的位置,新結(jié)點即添加在該指針指向的結(jié)點之后;p_node為指向待添加結(jié)點的指針。比如,同樣將結(jié)點添加到鏈表尾部,其使用范例詳見程序清單3.40

程序清單3.40 dlist_add()函數(shù)使用范例

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5

6 dlist_init(&head);

7 dlist_add(&head, &(head.p_prev), &node);

8 // ……

9 }

由此可見,將尾結(jié)點作為結(jié)點添加的位置,同樣可以將結(jié)點添加至尾結(jié)點之后,即添加到鏈表尾部。顯然,也就沒有必要再編寫dlist_add_tail()實現(xiàn)代碼了使用dlisd_add()即可,修改dlist_add_tail()函數(shù)的實現(xiàn)詳見程序清單3.41

程序清單3.41 dlist_add_tail()函數(shù)實現(xiàn)

1 int dlist_add_tail (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head->p_prev, p_node);

4 }

為了實現(xiàn)dlist_add()函數(shù),可以先查看添加一個結(jié)點到任意結(jié)點之后的情況,詳見圖3.19。圖中展示的是一種通用的情況,由于結(jié)點的添加位置(頭、尾或其它任意位置)與添加結(jié)點的方法沒有關(guān)系,因此沒有特別標(biāo)明頭結(jié)點和尾結(jié)點。

其實,對比圖3.18圖3.19可以發(fā)現(xiàn),圖3.18展示的只是圖3.19一個特例,即恰好圖3.19中的新結(jié)點之前的結(jié)點就是尾結(jié)點,添加結(jié)點的過程同樣需要修改4個指針的值。為便于描述,將新結(jié)點前的結(jié)點稱之為前結(jié)點,新結(jié)點之后的結(jié)點稱之為后結(jié)點。顯然,在添加新結(jié)點之前,前結(jié)點的下一個結(jié)點即為后結(jié)點。對設(shè)置4個指針值的描述如下:

● 新結(jié)點的p_prev指向前結(jié)點;

● 新結(jié)點的p_next指向后結(jié)點;

● 前結(jié)點的p_next由指向后結(jié)點變?yōu)橹赶蛐陆Y(jié)點;

● 后結(jié)點的p_prev由指向前結(jié)點修改為指向新結(jié)點。

對比將結(jié)點添加到鏈表尾部的描述,只要將描述中的“前結(jié)點”換為“尾結(jié)點”,“后結(jié)點”換為“頭結(jié)點”,它們的含義則完全一樣,顯然將結(jié)點添加到鏈表尾部只是這里的一個特例,添加結(jié)點的函數(shù)實現(xiàn)詳見程序清單3.42

程序清單3.42 dlist_add()函數(shù)實現(xiàn)

1 int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node)

2 {

3 if ((p_head == NULL) || (p_pos == NULL) || (p_node == NULL)){

4 return -1;

5 }

6 p_node->p_prev = p_pos; // 新結(jié)點的p_prev指向前結(jié)點

7 p_node->p_next = p_pos->p_next; // 新結(jié)點的p_next指向后結(jié)點

8 p_pos->p_next->p_prev = p_node; // 后結(jié)點的p_prev指向新結(jié)點

9 p_pos->p_next = p_node; // 前結(jié)點的p_next指向新結(jié)點

10 return 0;

11 }

盡管上面的函數(shù)在實現(xiàn)時并沒有用到參數(shù)p_head但還是將p_head參數(shù)傳進(jìn)來了因為實現(xiàn)其它的功能時將會用到p_head參數(shù)比如判斷p_pos是否在鏈表中。

有了該函數(shù),添加結(jié)點到任意位置就非常靈活了,比如,提供一個添加結(jié)點到鏈表的頭部,使其作為鏈表的第一個結(jié)點的函數(shù),其函數(shù)原型為:

int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node);

此時,頭結(jié)點即為新添加結(jié)點的前結(jié)點,直接調(diào)用dlist_add()即可實現(xiàn),其實現(xiàn)范例詳見程序清單3.43

程序清單3.43 dlist_add_head()函數(shù)實現(xiàn)

1 int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 return dlist_add(p_head, p_head, p_node);

4 }

>>>>1.1.2 刪除結(jié)點

基于添加結(jié)點到任意位置的思想,需要實現(xiàn)一個刪除任意結(jié)點的函數(shù)。其函數(shù)原型為:

int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node);

其中,p_head為指向鏈表頭結(jié)點的指針, p_node為指向待刪除結(jié)點的指針,使用范例詳見程序清單3.44

程序清單3.44 dlist_del()使用范例程序

1 int main(int argc, char *argv[])

2 {

3 dlist_head_t head;

4 dlist_node_t node;

5 dlist_init(&head);

6 dlist_add_tail(&head, &node);

7 dlist_del(&head, &node);

8 //......

9 return 0;

10 }

為了實現(xiàn)dlisd_del()函數(shù),可以先查看刪除任意結(jié)點的示意圖,圖 3.20(1)為刪除節(jié)點前的示意圖,圖 3.20(2)為刪除節(jié)點后的示意圖。

圖 3.20添加結(jié)點示意圖

由此可見,僅需要修改兩個指針的值:

● 將“刪除結(jié)點”的前結(jié)點的p_next修改為指向“刪除結(jié)點”的后結(jié)點;

● 將“刪除結(jié)點”的后結(jié)點的p_prev修改為指向“刪除結(jié)點”的前結(jié)點。

刪除結(jié)點函數(shù)的實現(xiàn)詳見程序清單3.45

程序清單3.45 dlist_del()函數(shù)實現(xiàn)

1 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node)

2 {

3 if ((p_head == NULL) || (p_node == NULL) || (p_node == p_head)){

4 return -1;

5 }

6 p_node->p_prev->p_next = p_node->p_next; // 前結(jié)點的p_next修改為指向后結(jié)點

7 p_node->p_next->p_prev = p_node->p_prev; // 后結(jié)點的p_prev修改為指向前結(jié)點

8

9 p_node->p_next = NULL;

10 p_node->p_prev = NULL;

11 return 0;

12 }

為了防止刪除頭結(jié)點,程序中對p_head與p_node進(jìn)行了比較,當(dāng)p_node為頭結(jié)點時,則直接返回錯誤。

>>>>1.1.3 遍歷鏈表

與單向鏈表類似,需要一個遍歷鏈表各個結(jié)點的函數(shù),其函數(shù)原型(dlist.h)為:

int dlist_foreach (dlist_head_t *p_head,

dlist_node_process_t pfn_node_process,

void *p_arg);

其中,p_head指向鏈表頭結(jié)點,pfn_node_process為結(jié)點處理回調(diào)函數(shù),每遍歷到一個結(jié)點時,均會調(diào)用該函數(shù),便于用戶處理結(jié)點。dlist_node_process_t類型定義如下

typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

dlist_node_process_t類型參數(shù)為一個p_arg指針和一個結(jié)點指針,返回值為int類型的函數(shù)指針。每遍歷到一個結(jié)點均會調(diào)用pfn_node_process指向的函數(shù),便于用戶根據(jù)需要自行處理結(jié)點數(shù)據(jù)。當(dāng)調(diào)用該回調(diào)函數(shù)時,傳遞給p_arg的值即為用戶參數(shù),其值與dlist_traverse()函數(shù)的第3個參數(shù)一樣,即該參數(shù)的值完全是由用戶決定的;傳遞給p_node 的值即為指向當(dāng)前遍歷到的結(jié)點的指針。當(dāng)遍歷到某個結(jié)點時,如果用戶希望終止遍歷,此時,只要在回調(diào)函數(shù)中返回負(fù)值即可終止繼續(xù)遍歷。一般地,若要繼續(xù)遍歷,則函數(shù)執(zhí)行結(jié)束后返回0即可。dlist_foreach()函數(shù)的實現(xiàn)詳見程序清單3.46

程序清單3.46 鏈表遍歷函數(shù)的實現(xiàn)

1 int dlist_foreach (dlist_head_t *p_head,

2 dlist_node_process_t pfn_node_process,

3 void *p_arg)

4 {

5 dlist_node_t *p_tmp, *p_end;

6 int ret;

7

8 if ((p_head == NULL) || (pfn_node_process == NULL)) {

9 return -1;

10 }

11

12 p_tmp = dlist_begin_get(p_head);

13 p_end = dlist_end_get(p_head);

14

15 while (p_tmp != p_end) {

16 ret = pfn_node_process(p_arg, p_tmp);

17 if (ret < 0) {??????????????????????????? // 不再繼續(xù)遍歷

18 return ret;

19 }

20 p_tmp = dlist_next_get(p_head, p_tmp); // 繼續(xù)下一個結(jié)點

21 }

22 return 0;

23 }

為了便于查閱,如程序清單3.47所示展示了dlist.h文件的內(nèi)容。

程序清單3.47 dlist.h文件內(nèi)容

1 #ipragma once

2 #include

3 #include

4

5 typedef struct _dlist_node{

6 struct _dlist_node *p_next; // 指向下一個結(jié)點的指針

7 struct _dlist_node *p_prev; // 指向下一個結(jié)點的指針

8 }dlist_node_t;

9

10 typedef dlist_node_t dlist_head_t;

11

12 // 鏈表遍歷時的回調(diào)函數(shù)類型

13 typedef int (*dlist_node_process_t) (void *p_arg, dlist_node_t *p_node);

14

15 int dlist_init (dlist_head_t *p_head); // 鏈表初始化

16

17 int dlist_add (dlist_head_t *p_head, dlist_node_t *p_pos, dlist_node_t *p_node); // 添加結(jié)點至指定位置

18 int dlist_add_tail(dlist_head_t *p_head, dlist_node_t *p_node); // 添加結(jié)點至鏈表尾部

19 int dlist_add_head (dlist_head_t *p_head, dlist_node_t *p_node); // 添加結(jié)點至鏈表頭部

20 int dlist_del (dlist_head_t *p_head, dlist_node_t *p_node); // 刪除一個結(jié)點

21

22 dlist_node_t *dlist_prev_get (dlist_head_t *p_head, dlist_node_t *p_pos); // 尋找某一結(jié)點的前一結(jié)點

23 dlist_node_t *dlist_next_get (dlist_head_t *p_head, dlist_node_t *p_pos); // 尋找某一結(jié)點的后一結(jié)點

24 dlist_node_t *dlist_tail_get (dlist_head_t *p_head); // 獲取尾結(jié)點

25 dlist_node_t *dlist_begin_get (dlist_head_t *p_head); // 獲取開始位置,第一個用戶結(jié)點

26 dlist_node_t *dlist_end_get (dlist_head_t *p_head); // 獲取結(jié)束位置,尾結(jié)點下一個結(jié)點的位置

27

28 int dlist_foreach (dlist_head_t *p_head,

29 dlist_node_process_t pfn_node_process,

30 void *p_arg);

同樣以int類型數(shù)據(jù)為例,來展示這些接口的使用方法。為了使用鏈表,首先應(yīng)該定義一個結(jié)構(gòu)體,將鏈表結(jié)點作為其一個成員,此外,再添加一些應(yīng)用相關(guān)的數(shù)據(jù),如定義如下包含鏈表結(jié)點和int型數(shù)據(jù)的結(jié)構(gòu)體:

typedef struct _dlist_int{

dlist_node_t node; // 包含鏈表結(jié)點

int data; // int類型數(shù)據(jù)

}dlist_int_t;

綜合范例程序詳見程序清單3.48

程序清單3.48 綜合范例程序

1 #include

2 #include "dlist.h"

3

4 typedef struct _dlist_int{

5 dlist_node_t node; // 包含鏈表結(jié)點

7 int data; // int類型數(shù)據(jù)

8 }dlist_int_t;

9

10 int list_node_process (void *p_arg, dlist_node_t *p_node)

11 {

12 printf("%d ", ((dlist_int_t *)p_node) -> data);

13 return 0;

14 }

15

16 int main(int argc, char *argv[])

17 {

18 dlist_head_t head; // 定義鏈表頭結(jié)點

19 dlist_int_t node1, node2, node3;

20 dlist_init(&head);

21

22 node1.data = 1;

23 dlist_add_tail(&head, &(node1.node));

24 node2.data = 2;

25 dlist_add_tail(&head, &(node2.node));

26 node3.data = 3;

27 dlist_add_tail(&head, &(node3.node));

28

29 dlist_del(&head, &(node2.node)); // 刪除node2結(jié)點

30 dlist_foreach(&head, list_node_process, NULL); // 遍歷鏈表,用戶參數(shù)為NULL

31 return 0;

32 }

與單向鏈表的綜合范例程序比較可以發(fā)現(xiàn)程序主體是完全一樣的僅僅是各個結(jié)點的類型發(fā)生了改變。對于實際的應(yīng)用如果由使用單向鏈表升級為雙向鏈表雖然程序主體沒有發(fā)生改變但由于類型的變化則不得不修改所有程序代碼。這是由于應(yīng)用與具體數(shù)據(jù)結(jié)構(gòu)沒有分離造成的,因此可以進(jìn)一步將實際應(yīng)用與具體的數(shù)據(jù)結(jié)構(gòu)分離,將鏈表等數(shù)據(jù)結(jié)構(gòu)抽象為“容器”的概念。

在公眾號后臺回復(fù)關(guān)鍵字“程序設(shè)計”,即可在線閱讀《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》;回復(fù)關(guān)鍵字“編程”,即可在線閱讀《面向AMetal框架與接口的編程(上)》。

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 程序
    +關(guān)注

    關(guān)注

    117

    文章

    3785

    瀏覽量

    81005
  • 周立功
    +關(guān)注

    關(guān)注

    38

    文章

    130

    瀏覽量

    37616
  • 鏈表
    +關(guān)注

    關(guān)注

    0

    文章

    80

    瀏覽量

    10558

原文標(biāo)題:周立功:高效的雙向鏈表就應(yīng)該這樣用

文章出處:【微信號:Zlgmcu7890,微信公眾號:周立功單片機】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。

收藏 人收藏

    評論

    相關(guān)推薦

    立功教授談迭代器模式設(shè)計

    近日立功教授公開了數(shù)年的心血之作《程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)》,電子版已無償性分享到電子工程師與高校群體下載,經(jīng)立功教授授權(quán),特對本書內(nèi)容進(jìn)行連載。
    的頭像 發(fā)表于 09-26 13:51 ?6298次閱讀
    <b class='flag-5'>周</b><b class='flag-5'>立功</b>教授談迭代器模式設(shè)計

    【Linux高級編譯】list.h的高效應(yīng)用—雙向鏈表的實現(xiàn)

    【Linux高級編譯】Linux內(nèi)核的list.h的高效應(yīng)用——雙向鏈表的實現(xiàn)
    的頭像 發(fā)表于 09-15 10:00 ?2599次閱讀
    【Linux高級編譯】list.h的<b class='flag-5'>高效</b>應(yīng)用—<b class='flag-5'>雙向</b><b class='flag-5'>鏈表</b>的實現(xiàn)

    立功大師EASY FPGA原理圖

    本帖最后由 eehome 于 2013-1-5 09:47 編輯 立功EASYFPGA原理圖立功大師經(jīng)典力作,F(xiàn)PGA原理圖。歡迎大家下載學(xué)習(xí)
    發(fā)表于 03-16 11:02

    立功的NIOS視頻

    立功的NIOS視頻
    發(fā)表于 07-19 09:55

    立功CANTest軟件

    立功CANTest軟件
    發(fā)表于 01-15 16:52

    立功CANTest軟件

    立功CANTest軟件
    發(fā)表于 02-27 09:26

    【HarmonyOS】雙向循環(huán)鏈表

    了一個個雙向循環(huán)鏈表,把指針的高效能運用到了極致,這也許就是編程的藝術(shù)吧!致敬鴻蒙內(nèi)核開發(fā)者貢獻(xiàn)了如此優(yōu)秀的源碼,鴻蒙內(nèi)核源碼可作為大學(xué)C語言,操作系統(tǒng),數(shù)據(jù)結(jié)構(gòu)三門課的教學(xué)項目
    發(fā)表于 10-20 15:39

    立功ARM培訓(xùn)精華

    立功ARM培訓(xùn)精華 ppt模式,還需下載分段壓縮才可以查看
    發(fā)表于 02-11 09:13 ?108次下載

    TinyM0配套教程大全 立功

    TinyM0配套教程大全 立功
    發(fā)表于 04-20 16:30 ?0次下載

    立功ARM培訓(xùn)精華

    立功ARM培訓(xùn)精華,有需要的下來看看。
    發(fā)表于 01-13 17:23 ?41次下載

    算法與數(shù)據(jù)結(jié)構(gòu)——雙向鏈表

    第三章為算法與數(shù)據(jù)結(jié)構(gòu),本文為3.3 雙向鏈表
    的頭像 發(fā)表于 09-19 17:56 ?7291次閱讀
    算法與數(shù)據(jù)結(jié)構(gòu)——<b class='flag-5'>雙向</b><b class='flag-5'>鏈表</b>

    立功新著內(nèi)容分享:雙向鏈表是什么?

    單向鏈表的添加、刪除操作,都必須找到當(dāng)前結(jié)點的上一個結(jié)點,以便修改上一個結(jié)點的p_next指針完成相應(yīng)的操作。
    的頭像 發(fā)表于 09-22 18:24 ?5984次閱讀

    了解Linux通用的雙向循環(huán)鏈表

    在linux內(nèi)核中,有一種通用的雙向循環(huán)鏈表,構(gòu)成了各種隊列的基礎(chǔ)。鏈表的結(jié)構(gòu)定義和相關(guān)函數(shù)均在include/linux/list.h中,下面就來全面的介紹這一鏈表的各種API。
    發(fā)表于 05-07 10:44 ?672次閱讀

    單片機教程 立功

    單片機教程 立功
    發(fā)表于 11-19 14:17 ?0次下載

    雙向循環(huán)鏈表的創(chuàng)建

    需要注意的是,雖然雙向循環(huán)鏈表成環(huán)狀,但本質(zhì)上還是雙向鏈表,因此在雙向循環(huán)鏈表中,依然能夠找到頭
    的頭像 發(fā)表于 05-24 16:27 ?2101次閱讀
    主站蜘蛛池模板: 久久vs国产| 欧美性XXXXX极品娇小| 飘雪韩国在线观看免费高清完整版| 熟女人妻久久精品AV天堂| 一本道高清码v京东热| 阿v天堂2017在无码| 极品虎白在线观看| 欧美牲交A欧美牲交| 亚洲高清无码在线 视频| 99国产精品综合AV无码| 国产色精品VR一区二区| 蜜桃臀无码内射一区二区三区| 四虎影视国产精品亚洲精品hd| 在线观看国产高清免费不卡| 动漫美女被吸奶| 狼与美女谐音歌词| 我就去色色| 99热在线播放| 精品国产乱码久久久久久免费| 啪啪激情婷婷久久婷婷色五月| 亚洲色图19p| 大肚婆孕妇网| 快播性爱电影| 亚洲 自拍 清纯 综合图区| 99国产强伦姧在线看RAPE| 国精产品一区一区三区有限公司| 欧美黄色一级| 伊人不卡久久大香线蕉综合影院| 丰满的女朋友 在线播放| 麻豆XXXX乱女少妇精品| 亚洲 欧美 国产在线视频 | 国产成人精品一区二区三区视频| 久久婷婷五月综合色精品首页| 无码AV毛片色欲欧洲美洲| 9久久免费国产精品特黄| 久草在线福利资站免费视频| 视频三区 国产盗摄| CHINA中国东北GURMA| 绝色娇嫩美人妻老师| 亚洲精品视频在线播放| 囯产精品久久久久免费蜜桃 |