數(shù)據(jù)結(jié)構(gòu)作為嵌入式工程師必修課程之一，今天，我們就來講一講數(shù)據(jù)結(jié)構(gòu)中最簡單的鏈表，包含鏈表的初始化、插入和遍歷操作。 鏈表在項(xiàng)目開發(fā)中使用的場景很多，跟數(shù)組相比，它的優(yōu)點(diǎn)就是，容量沒有限制，插入刪除效率比較高。

? 數(shù)組在內(nèi)存中是一塊連續(xù)的存儲空間，而且隨著存儲數(shù)據(jù)的不斷增多，想要找到這么一大塊的連續(xù)內(nèi)存也比較困難。

? 但是鏈表就能解決這個問題，它由節(jié)點(diǎn)組成，每個節(jié)點(diǎn)占用的內(nèi)存不會很大，而且各個節(jié)點(diǎn)之間也不需要連續(xù)，為了方便訪問，只要把下一個節(jié)點(diǎn)的地址記在上一個節(jié)點(diǎn)的指針域中就行，這樣，所有節(jié)點(diǎn)之間就像有跟線一樣串聯(lián)起來。

? 跟數(shù)組相比，它的隨機(jī)插入效率也要高很多。比如數(shù)組有100個元素，想要在第一個位置插入一個元素，那么每個元素都得向后移動一個位置，把第一個位置騰出來，數(shù)據(jù)量越大，移動的效率越低。 鏈表的插入完全不一樣，不管在什么位置插入，只要適當(dāng)?shù)男薷膸讉€指針就能解決問題。

? 鏈表可以有頭節(jié)點(diǎn)，也可以沒有頭節(jié)點(diǎn)，為了方便編程，我們一般都會加上頭節(jié)點(diǎn)。

? 有了頭節(jié)點(diǎn)，就有了頭指針，用來保存頭節(jié)點(diǎn)的地址。

? 既然鏈表是由很多個節(jié)點(diǎn)組成，第一步就得用代碼來表示節(jié)點(diǎn)。節(jié)點(diǎn)分為數(shù)據(jù)域和指針域，數(shù)據(jù)域可以是任意類型，我們就用int吧，指針域保存下一個節(jié)點(diǎn)的地址，把這兩個成員放在結(jié)構(gòu)體中，后面就用Node來表示節(jié)點(diǎn)。

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

? 所謂鏈表的初始化，就是形成一個空的鏈表，空的鏈表只有一個頭節(jié)點(diǎn)，數(shù)據(jù)域沒有數(shù)據(jù)，指針域?yàn)榭铡?br />

? 定義頭指針head，初始化的時候，因?yàn)橐薷膆ead的數(shù)值，所以必須傳它的地址。

Node *head = NULL;


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

? 先申請一個節(jié)點(diǎn)，把節(jié)點(diǎn)的地址保存在head中，節(jié)點(diǎn)的指針域?yàn)镹ULL，初始化的工作就完成了。

int InitLink(Node **h)
{
    if (NULL == h)
        return FAILURE;


    (*h) = (Node *)malloc(sizeof(Node));
    if ((*h) == NULL)
    {   
        return FAILURE;
    }   


    (*h)->next = NULL;


    return SUCCESS;
}

? 鏈表的插入操作是一個經(jīng)典的筆試題。

? 過程就是：定義指針指向頭節(jié)點(diǎn)，把指針移動到要插入位置的前一個位置，同時判斷插入的位置是否合法，申請新的節(jié)點(diǎn)，填好指針域和數(shù)據(jù)域，最后再修改前一個節(jié)點(diǎn)的指針域，形成一個新的鏈表。

? 繼續(xù)寫代碼，主函數(shù)中通過for循環(huán)，往鏈表中插入10個節(jié)點(diǎn)，插入的數(shù)據(jù)隨機(jī)生成，位置就指定為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);
    }   
}

? 來實(shí)現(xiàn)插入的功能。

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

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;
}

? 運(yùn)行看下現(xiàn)象，10個節(jié)點(diǎn)都顯示插入成功。

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

? 但是到底有沒有形成鏈表，還得遍歷看下。

? 遍歷操作只需要借助指針，每經(jīng)過一個節(jié)點(diǎn)，打印該節(jié)點(diǎn)的數(shù)據(jù)就行。定義指針p，指向第一個節(jié)點(diǎn)，注意，第一個節(jié)點(diǎn)不是頭節(jié)點(diǎn)，而是第一個保存數(shù)據(jù)的節(jié)點(diǎn)。只要指針p不為空，就說明鏈表還沒有到最后，打印該節(jié)點(diǎn)數(shù)據(jù)，然后讓p繼續(xù)往下。

void TraverseLink(Node *h) 
{
    if (NULL == h)
        return;


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

? 運(yùn)行看下結(jié)果，也沒有問題。

? 這就是鏈表的幾個基本操作，尤其是插入操作，基本是筆試必考，如果你有就業(yè)的需求，不妨把這段代碼背下來。
? ?

　　審核編輯：湯梓紅

?