|
在嵌入式linux內核中，鏈表是一種常見的重要數據結構，它可以動態地進行存儲分配，根據需要開辟內存單元，還可以方便地實現數據的增加和刪除。鏈表中的每個元素都由兩部分組成：數據域和指針域。
其中，數據域用于存儲數據元素的信息，指針域用于存儲該元素的直接后繼元素的位置。其整體結構就是用指針相鏈接起來的線性表，如圖1.1所示。
圖1.1 鏈表結構
由圖中，大家可以清楚地看到，每個鏈表都有一個頭指針Head，其用于指示鏈表中第一個節點的存儲位置。之后，鏈表由第一個節點指向第二個節點，依此類推。鏈表的后一個數據元素由于沒有直接后繼節點，因此其節點的指針為空（NULL）。本文主要介紹的是單項鏈表！
1、 單鏈表的組織與存儲
單向鏈表的每個節點中除信息域以外還有一個指針域，用來指向其后續節點，其后一個節點的指針域為空（NULL）。
單向鏈表由頭指針惟一確定，因此單向鏈表可以用頭指針的名字來命名，頭指針指向單向鏈表的第一個節點。
在用C語言實現時，首先說明一個結構類型，在這個結構類型中包含一個（或多個）信息成員以及一個指針成員如下所示：
typedef struct _link_node
{
element_type data; /* element_type為有效數據類型*/
struct _link_node *next;
} link_node;
typedef link_node *link_list;
鏈表結構中包含指針型的結構成員，類型為指向相同結構類型的指針。根據C語言的語法要求，結構的成員不能是結構自身類型，即結構不能自己定義自己，因為這樣將導致一個無窮的遞歸定義，但結構的成員可以是結構自身的指針類型，通過指針引用自身這種類型的結構。
2、 單鏈表常見操作
（1）節點初始化
由于鏈表是一種動態分配數據的數據結構，因此單鏈表中各個節點的初始化通常使用malloc()函數，把節點中的next指針賦為NULL，同時再把數據域的部分初始化為需要的數值，通常使用memset()函數。
int init_link(link_list *list)
{
/*用malloc分配函數分配節點*/
*list = (link_list)malloc(sizeof(link_node));
/*若分配失敗，返回*/
if (!list)
{
return -1;
}
/*初始化鏈表節點的數據域*/
memset(&((*list)->data), 0, sizeof(element_type));
/*初始化鏈表節點的指針域*/
(*list)->next = NULL;
return 0;
}
（2）數據查詢
在操作鏈表時，通常需要檢查在鏈表中是否存在某種數據，這時，可以通過順序遍歷鏈表來取得所需要的元素。
int get_element(link_list list, int i, element_type *elem)
{
/* list為帶頭節點的單鏈表的頭指針 */
/*當第i個元素存在時，其值賦給elem并返回*/
link_list p = NULL;
int j = 0;
/*初始化，指向鏈表的第一個節點，j為計數器*/
p = list->next;
/* 為防止i過大，通過判斷p是否為空來確定是否到達鏈表的尾部 */
while ((j++ < i) && (p = p->next));
/* 若第i個元素不存在，返回 */
if (!p || (j <= i))
{
return -1;
}
/*取得第i個元素*/
*elem = p->data;
return 0;
}
（3）鏈表的插入與刪除
鏈表的插入與刪除是鏈表中常見的操作，也是能體現鏈表靈活性的操作。
在單向鏈表中插入一個節點要引起插入位置前面節點的指針的變化，如圖1.2所示。
圖1.2 鏈表的節點插入過程
由圖中可以看出，在鏈表中增加一個節點會依次完成如下操作。
●創建新節點C
●使C指向B：C→next = A→next。
●使A指向C：A→next = C。
int link_insert(link_list list, int i, element_type elem)
{
/* list為帶頭節點的單鏈表的頭指針 */
/* i為要插入的元素位置，elem為要插入的元素*/
link_list p = list, new_node;
int j = 0;
/* 找到第i位 */
while ((j++ < i) && (p = p->next));
if (!p || (j <= i))
{
return 0;
}
/* 初始化鏈表節點 */
new_node = (link_list)malloc(sizeof(link_node));
new_node->data = elem;
/* 將s插入鏈表，并修改原先的指針 */
new_node->next = p->next;
p->next = new_node;
return 1;
}
刪除的過程也類似，如圖1.3所示。
圖1.3 鏈表的節點刪除過程
同樣，鏈表中元素的指針會依次有以下變化。
●使A指向C：A→next = B->next。
●使B指向NULL：B->next = NULL 或（若不再需要該節點）釋放節點B。
（4）其他操作
將幾個單鏈表合并也是鏈表操作中的一個常見的操作之一。
下面將兩個單鏈表根據標識符ID順序合并成一個單鏈表。在合并的過程中，實際上新建了一個鏈表，然后將兩個鏈表的元素依次進行比較，并且將ID較小的節點插入到新的鏈表中。如果其中一個鏈表的元素已經全部插入，則另一個鏈表的剩余操作只需順序將剩余元素插入即可。
該過程如圖1.4所示：
圖1.4 鏈表的合并過程
void merge_list(link_list list_a, link_list list_b, link_list *list_c)
{
/* 合并單鏈表list_a和list_b到list_c中 */
link_list pa, pb, pc;
/* 初始化pa、pb，指向鏈表的第一個元素 */
pa = list_a->next;
pb = list_b->next;
*list_c = pc = list_a;
/* 判斷兩個鏈表是否到達末尾 */
while (pa && pb)
{
/*若鏈表list_a的元素小于鏈表list_b的元素，
則把鏈表list_a的元素插入到list_c中*/
if (less_equal_list(&pa->data, &pb->data))
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
/* 若鏈表list_a的元素大于鏈表list_b的元素，
則把鏈表list_b的元素插入到list_c中*/
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
/* 將還未到達末尾的鏈表連入list_c中，若兩個鏈表都到達末尾，pc->next為NULL*/
pc->next = pa?pa:pb;
}
熱點鏈接：
1、Linux內核模塊程序結構
2、嵌入式Linux內核如何編譯
3、典型嵌入式Linux系統設置
更多新聞>> |
