(資料圖片僅供參考)

數據結構作為嵌入式工程師必修課程之一，今天，我們就來講一講數據結構中最簡單的鏈表，包含鏈表的初始化、插入和遍歷操作。 鏈表在項目開發中使用的場景很多，跟數組相比，它的優點就是，容量沒有限制，插入刪除效率比較高。 數組在內存中是一塊連續的存儲空間，而且隨著存儲數據的不斷增多，想要找到這么一大塊的連續內存也比較困難。 但是鏈表就能解決這個問題，它由節點組成，每個節點占用的內存不會很大，而且各個節點之間也不需要連續，為了方便訪問，只要把下一個節點的地址記在上一個節點的指針域中就行，這樣，所有節點之間就像有跟線一樣串聯起來。 跟數組相比，它的隨機插入效率也要高很多。比如數組有100個元素，想要在第一個位置插入一個元素，那么每個元素都得向后移動一個位置，把第一個位置騰出來，數據量越大，移動的效率越低。 鏈表的插入完全不一樣，不管在什么位置插入，只要適當的修改幾個指針就能解決問題。 鏈表可以有頭節點，也可以沒有頭節點，為了方便編程，我們一般都會加上頭節點。 有了頭節點，就有了頭指針，用來保存頭節點的地址。 既然鏈表是由很多個節點組成，第一步就得用代碼來表示節點。節點分為數據域和指針域，數據域可以是任意類型，我們就用int吧，指針域保存下一個節點的地址，把這兩個成員放在結構體中，后面就用Node來表示節點。

typedef struct Node{    int data;    struct Node *next;}Node;

所謂鏈表的初始化，就是形成一個空的鏈表，空的鏈表只有一個頭節點，數據域沒有數據，指針域為空。 定義頭指針head，初始化的時候，因為要修改head的數值，所以必須傳它的地址。

Node *head = NULL;int ret = InitLink(&head);if (SUCCESS == ret){       printf("鏈表初始化成功");}   else{       printf("鏈表初始化失敗");}

先申請一個節點，把節點的地址保存在head中，節點的指針域為NULL，初始化的工作就完成了。

int InitLink(Node **h){    if (NULL == h)        return FAILURE;    (*h) = (Node *)malloc(sizeof(Node));    if ((*h) == NULL)    {           return FAILURE;    }       (*h)->next = NULL;    return SUCCESS;}

鏈表的插入操作是一個經典的筆試題。 過程就是：定義指針指向頭節點，把指針移動到要插入位置的前一個位置，同時判斷插入的位置是否合法，申請新的節點，填好指針域和數據域，最后再修改前一個節點的指針域，形成一個新的鏈表。 繼續寫代碼，主函數中通過for循環，往鏈表中插入10個節點，插入的數據隨機生成，位置就指定為i + 1，意思就是第一次往第一個位置插入，第二次往第二個位置插入，這種插入方法我們把它稱作尾插法。

srand(time(NULL));int num;for (int i = 0; i < 10; i++){       num = rand() % 20;     ret = InsertLink(head, i + 1, num);    if (SUCCESS == ret)    {           printf("插入 %d 成功", num);    }       else    {           printf("插入 %d 失敗", num);    }   }

來實現插入的功能。 先定義一個指針，指向頭節點，根據插入的位置移動移動指針。接下來就是判斷插入的位置是否合法，有兩種情況要排除，一種是插入的位置小于等于0，一種是插入的位置太大，比如鏈表一共5個節點，在第七個位置插入肯定不行。然后在堆空間申請一個新的節點，填寫數據域和指針域，最后把q指向的節點指針域改成新申請的節點，插入的操作就完成了。

int InsertLink(Node *h, int p, int num){    if (NULL == h)        return FAILURE;    Node *q = h;    int k = 1;    while (k < p && q)    {           q = q->next;        k++;    }       if (!q || k > p)    {        return FAILURE;    }    Node *n = (Node *)malloc(sizeof(Node) * 1);    if (NULL == n)    {        return FAILURE;    }    n->data = num;    n->next = q->next;    q->next = n;    return SUCCESS;}

運行看下現象，10個節點都顯示插入成功。

root@Turbo:test# ./main鏈表初始化成功插入 1 成功插入 3 成功插入 4 成功插入 8 成功插入 18 成功插入 0 成功插入 16 成功插入 5 成功插入 6 成功插入 1 成功

但是到底有沒有形成鏈表，還得遍歷看下。 遍歷操作只需要借助指針，每經過一個節點，打印該節點的數據就行。定義指針p，指向第一個節點，注意，第一個節點不是頭節點，而是第一個保存數據的節點。只要指針p不為空，就說明鏈表還沒有到最后，打印該節點數據，然后讓p繼續往下。

void TraverseLink(Node *h) {    if (NULL == h)        return;    Node *p = h->next;    while (p)     {           printf("%d ", p->data);        p = p->next;    }       printf("");}

運行看下結果，也沒有問題。 這就是鏈表的幾個基本操作，尤其是插入操作，基本是筆試必考，如果你有就業的需求，不妨把這段代碼背下來。

審核編輯：湯梓紅