小白也能學會的鏈表（C/CPP）

構造鏈表

鏈表的基本單元就是節(jié)點，也就是說鏈表是由一個一個節(jié)點構成的。

而對于節(jié)點來說，里面至少會包含一個指針和一個數(shù)據(jù)元素，也就是如下圖所示：

其中數(shù)據(jù)域用來存放數(shù)據(jù)元素，指針域用來存放指向下一個節(jié)點的指針，這樣一個一個連接起來的就是鏈表。如下圖所示：

既然我們知道了節(jié)點的結構，那我們也就可以利用代碼實現(xiàn)一個結構體作為節(jié)點了。

struct ListNode {
    int value; // 數(shù)據(jù)
    struct ListNode* next; // 指針，指向下一個節(jié)點
};

然后，我們就可以利用這個結構體構建出我們需要的鏈表了。

struct ListNode* BuildLinkList() {
    // 先創(chuàng)建一個頭指針，指向第一個節(jié)點
    struct ListNode* head = nullptr;
    
    // 創(chuàng)建頭結點，并將頭指針指向該節(jié)點
    struct ListNode* node = new ListNode();
    node->value = 0;
    node->next = nullptr;
    
    // 將頭指針指向頭節(jié)點
    head = node;
    
    // 繼續(xù)創(chuàng)建節(jié)點
    for (int i = 1; i < 5; ++i) {
        struct ListNode* tempNode = new ListNode();
    	tempNode->value = i;
    	tempNode->next = nullptr;
        
        // 將節(jié)點加入到鏈表中
        node->next = tempNode;
        node = tempNode;
    }
    
    // 返回頭節(jié)點，通過頭節(jié)點即可使用構建好的鏈表
    return head;
}

對于創(chuàng)建好的鏈表，我們應該如何使用呢？接下來，我們就實現(xiàn)一下鏈表的遍歷，同時驗證一下通過BuildLinkList創(chuàng)建的鏈表是否正確。

我們知道，鏈表的節(jié)點是前一個指向后一個的，所以我們只需要從頭節(jié)點開始，通過拿去next指針，就能依次訪問所有的節(jié)點，直到最后一個節(jié)點。

void TraverseLinkList(struct ListNode* head) {
    // 以頭結點作為起始節(jié)點遍歷整個鏈表
    struct ListNode* p = head;
    
    // 當p不為空時，證明還有節(jié)點沒有遍歷完
    while (p != nullptr) {
        // 輸出當前節(jié)點的值
        cout << p->value << endl;
        
        // 找到后一個節(jié)點
        p = p->next;
    }
}

通過上面的代碼，我們就完成了單鏈表最基本的定義以及使用，那我們來跑一下看輸出什么樣的結果。

int main() {
    
    // 創(chuàng)建鏈表
    struct ListNode* head = BuildLinkList();
    
    // 遍歷輸出鏈表中的數(shù)據(jù)
    TraverseLinkList(head);
    
    return 0;
}

文章來源地址http://www.zghlxwxcb.cn/news/detail-596871.html

到了這里，關于算法通關村第一關——鏈表青銅挑戰(zhàn)筆記的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！