電子發(fā)燒友App
大家好，我是LinuxZn。
本次分享sys/queue.h：
什么是sys/queue.h？
queue.h是Linux、FreeBSD中的一個(gè)頭文件。
FreeBSD：FreeBSD 是一種類 UNIX操作系統(tǒng)。
這是一個(gè)很實(shí)用的頭文件，因?yàn)檫@個(gè)頭文件里全是宏定義操作，所以其不僅可以使用在Linux/嵌入式Linux項(xiàng)目中，也可以使用在單片機(jī)項(xiàng)目中，我也是因?yàn)樵谖覀兊膯纹瑱C(jī)項(xiàng)目中看到，才知道有這么一個(gè)頭文件的。我覺(jué)得挺實(shí)用的，與大家分享。
它使用宏實(shí)現(xiàn)了如下數(shù)據(jù)結(jié)構(gòu)：
SLIST：?jiǎn)蜗驘o(wú)尾鏈表
LIST：雙向無(wú)尾鏈表
STAILQ：?jiǎn)蜗蛴形叉湵恚勺麝?duì)列使用）
TAILQ：雙向有尾鏈表（可作隊(duì)列使用）
所有的數(shù)據(jù)結(jié)構(gòu)都支持如下功能：
在鏈表頭插入節(jié)點(diǎn)
在任意節(jié)點(diǎn)后插入節(jié)點(diǎn)
刪除節(jié)點(diǎn)
遍歷節(jié)點(diǎn)
我們可以在Linux系統(tǒng)的如下路徑中找到這個(gè)頭文件：
/usr/include/sys/queue.h
也可以通過(guò)如下網(wǎng)址查看：
https://code.woboq.org/userspace/glibc/misc/sys/queue.h.html
sys/queue.h的使用
下面我們基于SLIST來(lái)演示其使用。
SLIST相關(guān)宏定義：
/* ?*?Singly-linked?List?definitions. ?*/ #define?SLIST_HEAD(name,?type)????????? struct?name?{??????????????????? ?struct?type?*slh_first;?/*?first?element?*/???????? } #define?SLIST_HEAD_INITIALIZER(head)??????? ?{?NULL?} #define?SLIST_ENTRY(type)?????????? struct?{?????????????? ?struct?type?*sle_next;?/*?next?element?*/????? } /* ?*?Singly-linked?List?functions. ?*/ #define?SLIST_INIT(head)?do?{????????? ?(head)->slh_first?=?NULL;????????? }?while?(/*CONSTCOND*/0) #define?SLIST_INSERT_AFTER(slistelm,?elm,?field)?do?{??? ?(elm)->field.sle_next?=?(slistelm)->field.sle_next;??? ?(slistelm)->field.sle_next?=?(elm);??????? }?while?(/*CONSTCOND*/0) #define?SLIST_INSERT_HEAD(head,?elm,?field)?do?{???? ?(elm)->field.sle_next?=?(head)->slh_first;????? ?(head)->slh_first?=?(elm);????????? }?while?(/*CONSTCOND*/0) #define?SLIST_REMOVE_HEAD(head,?field)?do?{?????? ?(head)->slh_first?=?(head)->slh_first->field.sle_next;?? }?while?(/*CONSTCOND*/0) #define?SLIST_REMOVE(head,?elm,?type,?field)?do?{???? ?if?((head)->slh_first?==?(elm))?{??????? ??SLIST_REMOVE_HEAD((head),?field);?????? ?}??????????????? ?else?{?????????????? ??struct?type?*curelm?=?(head)->slh_first;???? ??while(curelm->field.sle_next?!=?(elm))????? ???curelm?=?curelm->field.sle_next;????? ??curelm->field.sle_next?=???????? ??????curelm->field.sle_next->field.sle_next;???? ?}??????????????? }?while?(/*CONSTCOND*/0) #define?SLIST_FOREACH(var,?head,?field)??????? ?for((var)?=?(head)->slh_first;?(var);?(var)?=?(var)->field.sle_next) /* ?*?Singly-linked?List?access?methods. ?*/ #define?SLIST_EMPTY(head)?((head)->slh_first?==?NULL) #define?SLIST_FIRST(head)?((head)->slh_first) #define?SLIST_NEXT(elm,?field)?((elm)->field.sle_next)
?
下面我們通過(guò)實(shí)例來(lái)操作。
首先，創(chuàng)建鏈表頭節(jié)點(diǎn)、其它節(jié)點(diǎn)結(jié)構(gòu)體，用到SLIST_HEAD與SLIST_ENTRY這兩個(gè)宏定義：
?
#define?ELEM_TYPE?int
/*?鏈表節(jié)點(diǎn)?*/
typedef?struct?node?
{
????ELEM_TYPE?data;
????SLIST_ENTRY(node)?field;?
}node_st;
/*?鏈表頭?*/
typedef?SLIST_HEAD(head,?node)?head_st;
?
鏈表數(shù)據(jù)域類型我們定義為int，field表示的是指針域。
① 創(chuàng)建一個(gè)頭結(jié)點(diǎn)：
?
/*?創(chuàng)建鏈表頭節(jié)點(diǎn)并初始化?*/ head_st?*head?=?(head_st?*)malloc(sizeof(head_st)); SLIST_INIT(head);
?
頭節(jié)點(diǎn)：不存任何數(shù)據(jù)的空節(jié)點(diǎn)，通常作為鏈表的第一個(gè)節(jié)點(diǎn)。
② 在鏈表頭部分別插入節(jié)點(diǎn)node1、node2：
?
/*?頭插法插入一個(gè)節(jié)點(diǎn)node1?*/ node_st?*node1?=?(node_st?*)malloc(sizeof(node_st)); node1->data?=?1; SLIST_INSERT_HEAD(head,?node1,?field); /*?頭插法插入一個(gè)節(jié)點(diǎn)node2?*/ node_st?*node2?=?(node_st?*)malloc(sizeof(node_st)); node2->data?=?2; SLIST_INSERT_HEAD(head,?node2,?field);
?
頭指針：永遠(yuǎn)指向鏈表第一個(gè)節(jié)點(diǎn)的位置。
SLIST_INSERT_HEAD是從鏈表頭部插入節(jié)點(diǎn)，新節(jié)點(diǎn)總是從頭結(jié)點(diǎn)之后插入。
③ 在鏈表節(jié)點(diǎn)node2之后插入節(jié)點(diǎn)node3：
?
node_st?*node3?=?(node_st?*)malloc(sizeof(node_st)); node3->data?=?3; SLIST_INSERT_AFTER(node2,?node3,?field);
?
SLIST_INSERT_AFTER是從指定節(jié)點(diǎn)slistelm之后插入新節(jié)點(diǎn)elm。
④ 遍歷鏈表：
?
node_st?*tmp_elm;
SLIST_FOREACH(tmp_elm,?head,?field)
{
?printf("%d?",?tmp_elm->data);
}
?
輸出為tmp_elm，訪問(wèn)tmp_elm即可。
⑤ 刪除某個(gè)節(jié)點(diǎn)node2
?
SLIST_REMOVE(head,?node2,?node,?field); free(node2); node2?=?NULL;
?
⑥ 銷毀整個(gè)鏈表
?
while?(!SLIST_EMPTY(head))?
{????
????node_st?*p?=?SLIST_FIRST(head);
????SLIST_REMOVE_HEAD(head,?field);
????free(p);
????p?=?NULL;
}
free(head);
head?=?NULL;
?
完整測(cè)試代碼：
?
#include?#include? #include? #define?ELEM_TYPE?int /*?鏈表節(jié)點(diǎn)?*/ typedef?struct?node? { ????ELEM_TYPE?data; ????SLIST_ENTRY(node)?field;? }node_st; /*?鏈表頭?*/ typedef?SLIST_HEAD(head,?node)?head_st; int?main(void) { ????/*?創(chuàng)建鏈表頭節(jié)點(diǎn)并初始化?*/ ????head_st?*head?=?(head_st?*)malloc(sizeof(head_st)); ????SLIST_INIT(head); ????/*?頭插法插入一個(gè)節(jié)點(diǎn)node1?*/ ????node_st?*node1?=?(node_st?*)malloc(sizeof(node_st)); ????node1->data?=?1; ????SLIST_INSERT_HEAD(head,?node1,?field); ????/*?頭插法插入一個(gè)節(jié)點(diǎn)node2?*/ ????node_st?*node2?=?(node_st?*)malloc(sizeof(node_st)); ????node2->data?=?2; ????SLIST_INSERT_HEAD(head,?node2,?field); ????/*?遍歷打印當(dāng)前鏈表節(jié)點(diǎn)?*/ ????printf("list: "); ????node_st?*tmp_elm; ????SLIST_FOREACH(tmp_elm,?head,?field) ????{ ????????printf("%d?",?tmp_elm->data); ????} ????printf(" "); ????/*?尾插法插入一個(gè)節(jié)點(diǎn)node3?*/ ????printf("insert?node3: "); ????node_st?*node3?=?(node_st?*)malloc(sizeof(node_st)); ????node3->data?=?3; ????SLIST_INSERT_AFTER(node2,?node3,?field); ????SLIST_FOREACH(tmp_elm,?head,?field) ????{ ????????printf("%d?",?tmp_elm->data); ????} ????printf(" "); ????/*?刪除node2?*/ ????printf("delete?node2: "); ????SLIST_REMOVE(head,?node2,?node,?field); ????free(node2); ????node2?=?NULL; ????SLIST_FOREACH(tmp_elm,?head,?field) ????{ ????????printf("%d?",?tmp_elm->data); ????} ????printf(" "); ????/*?銷毀鏈表?*/ ????while?(!SLIST_EMPTY(head))? ????{???? ????????node_st?*p?=?SLIST_FIRST(head); ????????SLIST_REMOVE_HEAD(head,?field); ????????free(p); ????????p?=?NULL; ????} ????free(head); ????head?=?NULL; ????return?0; }
?
編譯、運(yùn)行：
運(yùn)行結(jié)果與我們上面分析的一致。
本次我們只分享queue.h里最簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)。其它幾種數(shù)據(jù)結(jié)構(gòu)的使用例子及相關(guān)宏說(shuō)明可以通過(guò)man命令查看。
man是Linux下的幫助命令。
我們輸入 man queue 即可查到queue.h的相關(guān)說(shuō)明：
可以看到，man命令很強(qiáng)大，可查到queue的幫助說(shuō)明很詳細(xì)，有宏的說(shuō)明及使用示例等。
以上就是本次的分享，文章如有錯(cuò)誤，歡迎支持，謝謝！我們下期見(jiàn)~
審核編輯：湯梓紅
工商網(wǎng)監(jiān)
評(píng)論