用C寫一個鏈表

鏈表(Linked List)是一種非連續(xù)的線性數(shù)據(jù)結(jié)構(gòu)，相對于數(shù)組，它允許數(shù)據(jù)在內(nèi)存中非連續(xù)存儲，但是不支持隨機讀取。

鏈表

鏈表由一個個節(jié)點(Node)組成，每個節(jié)點除了記錄數(shù)據(jù)以外，還需要記錄下一個節(jié)點的位置（如果是雙向鏈表，還需要記錄上一個節(jié)點的位置）

struct _Node;
typedef struct _Node Node;

struct _Node{
    int data; //記錄整型數(shù)據(jù)
    Node *next;
};

對于第一個節(jié)點，我們有一個指針指向它的地址，對于最后一個節(jié)點，它需要指向NULL，表示鏈表結(jié)束了。

typedef struct _List {
    Node *head;  //記錄頭地址
    Node *tail;  //記錄尾巴地址
    int num;
} List;

有了鏈表的數(shù)據(jù)結(jié)構(gòu)后，我們需要定義三個基本函數(shù)，用于創(chuàng)建鏈表，往鏈表中加入數(shù)據(jù)和刪除鏈表

創(chuàng)建鏈表比較簡單，就是為鏈表分配內(nèi)存，并將其賦值給一個指針，然后返回

// 創(chuàng)建鏈表
List *CreateList()
{
    List *list;
    list = (List*)malloc( sizeof(List) );
    list->num = 0;
    return list;
}

加入數(shù)據(jù)時，我們需要先聲明兩個節(jié)點指針，第一個用于記錄當(dāng)前節(jié)點的位置，第二個是記錄新節(jié)點的位置。如果鏈表中沒有節(jié)點，也就是head指向為NULL，那么直接插入新節(jié)點即可。如果鏈表中已經(jīng)有了節(jié)點，那么獲取最后第一個節(jié)點的位置, 然后在它的后面加入節(jié)點，同時將tail指向新的節(jié)點。

bool AddNode(List *list, int data)
{
    Node *node;
    Node *new_node;

    new_node = (Node *)malloc( sizeof(Node) );
    if ( new_node == NULL) return false;
    new_node->data = data;
    new_node->next = NULL;

    //獲取鏈表head
    node = list->head ;
    //如果head指向NULL, 則直接插入到下一個
    if ( node == NULL){
        list->head = new_node;
        list->tail = new_node;
        list->num = 1;
        return true;
    }
    // 否則在尾部插入節(jié)點
    node = list->tail ;
    node->next = new_node;
    list->tail = new_node;
    list->num+=1;

    return true;

}

刪除列表分為兩步，先刪除節(jié)點內(nèi)容，然后刪除列表這個結(jié)構(gòu)。如果節(jié)點存放的數(shù)據(jù)是其他結(jié)構(gòu)，那么還需要先刪除節(jié)點存放的其他數(shù)據(jù)。

void DestroyList(List *list)
{
    Node *current;
    Node *next;
    current = list->head;
    while (current->next != NULL){
        next = current->next;
        free(current);
        current = next;
    }
    free(list);
}

我們還可以定一個輸出函數(shù)，將鏈表里存放的數(shù)據(jù)依次輸出

//打印整個鏈表
void dump(List *list){
    Node *node;
    node = list->head;
    while (node != NULL){
        printf("%08d\n", node->data);
        node = node->next;
    }
}

有了上面的基本函數(shù)時候，我們就能夠讀取存放數(shù)字的文本，將其加入到鏈表中。

int main(int argc, char const *argv[])
{
    /* code */
    if (argc == 1) exit(EXIT_FAILURE);

    FILE *fp;
    fp = fopen(argv[1], "r");
    if (fp == NULL){
        perror(argv[1]);
        exit(EXIT_FAILURE);
    }
    int data;
    List *list;
    list = CreateList();
    while (fscanf(fp, "%d", &data) != EOF){
        AddNode(list, data);
    }
    dump(list)
    return 0;

我們的鏈表還應(yīng)該支持插入操作和刪除操作。對于插入操作，我們要分為是插入到給定位置前，還是給定位置后。對于刪除而言，也就是都是刪除當(dāng)前節(jié)點，而為了刪除當(dāng)前節(jié)點，我們需要前一個節(jié)點的位置。

無論是插入還是刪除，我們都需要知道插入的位置和刪除的位置，因此我們還需要一個搜索函數(shù)，用于搜索等于給定值的節(jié)點位置或者是上一個位置。

// 查找元素
// situ=true時, 返回當(dāng)前位置, false, 則返回上一個位置
Node *Search(List *list, int data, bool situ)
{
    Node *node;
    node = list->head;
    if ( situ ){
        while ( node->next != NULL ){
            if ( node->data == data)
                return node;
            node = node->next;
        }
    } else {
        while ( node->next->next != NULL) {
            if (node->next->data == data) 
                return node;
            node = node->next;
        }
    }
    return NULL;
}

我們先寫一個刪除操作, 用于刪除等于給定的節(jié)點。

//刪除節(jié)點
bool DeleteNode( List* list, int data){

    Node *node;
    Node *tmp;
    node = list->head;
    // 判斷這個節(jié)點是否是首節(jié)點
    if ( node->data == data ){
        free(list->head);
        list->head = NULL;
        list->tail = list->head;
        list->num = 0;
        return true;
    }
    // 查找給定節(jié)點的前一個節(jié)點
    node = Search(list, data, false);
    // 找不到節(jié)點
    if (  node  == NULL){
        return false;
    }
    //刪除
    tmp = node->next->next;
    free(node->next);
    node->next = tmp;
    return true;
}

然后將元素加入函數(shù)分為兩種，一種是插入（當(dāng)前位置前），一種是追加（當(dāng)前位置后）

//在給定元素前加節(jié)點
bool InsertNode( List* list, int query, int data){

    Node *node;
    Node *new_node;

    // 為新節(jié)點分配內(nèi)存
    new_node = (Node *)malloc( sizeof(Node) );
    if ( new_node == NULL) return false;
    new_node->data = data;

    node = list->head;
    // 判斷這個節(jié)點是否是首節(jié)點
    if ( node->data == query ){
        new_node->next = node->next ;
        node->next = new_node;
        return true;
    }

    // 查找給定節(jié)點的前一個節(jié)點
    node = Search(list, query, false);
    // 找不到節(jié)點
    if (  node  == NULL){
        return false;
    }
    new_node->next = node->next ;
    node->next = new_node;   

    return true;

}

//在給定元素后加
bool AppendNode( List* list, int query, int data){

    Node *node;
    Node *new_node;

    // 為新節(jié)點分配內(nèi)存
    new_node = (Node *)malloc( sizeof(Node) );
    if ( new_node == NULL) return false;
    new_node->data = data;

    // 查找給定節(jié)點的位置
    node = Search(list, query, true);
    // 找不到節(jié)點
    if (  node  == NULL){
        return false;
    }
    new_node->next = node->next;
    node->next = new_node;

    return true;

}

進階操作

上面都是鏈表的基礎(chǔ)操作，創(chuàng)建、摧毀，增加，刪除。下面幾個則是考驗對鏈表對深刻理解，

單鏈表反轉(zhuǎn)
鏈表中環(huán)的檢測
兩個有序鏈表的合并
刪除鏈表倒數(shù)第N個結(jié)點
求鏈表的中間結(jié)點

單鏈表反轉(zhuǎn)

如果要將單鏈表進行反轉(zhuǎn)，每次移動的時候需要三個位置，前一個位置，當(dāng)前位置和head。每次將head向后移動，記錄了當(dāng)前位置的下一個節(jié)點，然后將當(dāng)前位置指向前一個位置。最后將前一個位置和當(dāng)前位置向后移動。圖解如下，首先head指向鏈表第一個節(jié)點

head賦值

然后將cur設(shè)置到當(dāng)前的head

賦值cur

接著將head往后移動一個位置，保存了原本在cur后面的位置

head后移

然后將cur指向到res，也就是前面的位置

cur指向res

上面的操作后，就將res和cur的順序反轉(zhuǎn)了。接著就是將res和cur往后移動

移動cur和res

代碼為

List* reverseList(List* list){

    Node *curr, *res;
    res = NULL;
    curr = list->head;
    //尾巴是之前的開頭
    list->tail = list->head;
    while ( curr ){
        //移動head
        list->head = list->head->next;
        //將當(dāng)前位置指向前一個位置
        curr->next = res;
        //依次向后移動res和curr
        res = curr;
        curr = list->head;
    }
    list->head = res;
    return list;
}

中間節(jié)點

為了尋找中間節(jié)點，我們可以定義兩個指針，快指針和慢指針。慢指針一次一步，快指針一次兩步. 如果是偶數(shù)，那么快指針最后是NULL，如果是奇數(shù)，那么快指針的下一個是NULL。

Node *FindMidlle(List *list)
{
    if (list->num == 0) return NULL;
    Node *fast = list->head;
    Node *slow = list->head;
    while ( fast != NULL && fast->next != NULL){
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;

}

刪除倒數(shù)第N個指針

同上，也是快慢兩個指針，快指針先走N步，然后兩個指針再一起走。

bool RemoveLastN(List *list, int n)
{
    //刪除第一個
    if ( list->num == n){
        list->head = list->head->next;
        return true;
    }
    Node *fast = list->head;
    Node *slow = list->head;
    Node *tmp;
    while (n-- > 0){
        fast = fast->next;
    }
    while (fast->next != NULL){
        fast = fast->next;
        slow = slow->next;
    }
    tmp = slow->next;
    slow->next = slow->next->next;
    free(tmp);
    return true;
}

有序鏈表合并

假設(shè)兩個有序鏈表分別為1->3->5->7->8，2->3->4->5->8, 那么合并之后應(yīng)該是1->2->3->3->4->5->7->8.

我們需要創(chuàng)建一個新的鏈表用于存放兩個鏈表排序的結(jié)果

//合并兩個鏈表
List *MergeSortedList(List *list_a, List *list_b)
{
    List *list_c;
    list_c = CreateList();
    Node *node_a, *node_b, *node_c;
    node_a = list_a->head;
    node_b = list_b->head;

    //確定新列表的head
    if ( node_a->data < node_b->data ){
        list_c->head = node_a;
        node_a = node_a->next;
    } else {
        list_c->head = node_b;
        node_b = node_b->next;

    }
    node_c = list_c->head;
    while( true ){
        if (node_a->data < node_b->data){
            node_c->next = node_a;
            node_a = node_a->next;
            if  (node_a == NULL) break;
        } else{
            node_c->next = node_b;
            node_b = node_b->next;
            if  (node_b == NULL) break;
        }
            node_c = node_c->next;
    }
    while ( node_a != NULL){
        node_c->next = node_a;
        node_a = node_a->next;
        node_c = node_c->next;

    }
    while ( node_b != NULL){
        node_c->next = node_b;
        node_b = node_b->next;
        node_c = node_c->next;
    }
    return list_c;
}

為了測試這個代碼正確性，我寫了一個測試函數(shù)

int MergeTest( const char *file1, const char *file2){
    FILE *f1;
    FILE *f2;

    int data;
    f1 = fopen(file1, "r");

    List *list1;
    list1 = CreateList();
    //讀取數(shù)據(jù)
    while (fscanf(f1, "%d", &data) != EOF){
        AddNode(list1, data);
    }
    dump(list1);
    fclose(f1);

    f2 = fopen(file2, "r");
    if (f2 == NULL){
        perror(file2);
        exit(EXIT_FAILURE);
    }
    List *list2;
    list2 = CreateList();

    //讀取數(shù)據(jù)
    while (fscanf(f2, "%d", &data) != EOF){
        AddNode(list2, data);
    }
    dump(list2);
    fclose(f2);

    List *res;
    res = MergeSortedList(list1, list2);
    dump(res);
    return 0;

}

最終的代碼在GitHub上https://github.com/xuzhougeng/learn-algo/blob/master/link_list.c

LeetCode和鏈表有關(guān)的幾個題目

單鏈表反轉(zhuǎn): https://leetcode-cn.com/problems/reverse-linked-list/
https://leetcode-cn.com/problems/swap-nodes-in-pairs
鏈表中環(huán)的檢測: https://leetcode-cn.com/problems/linked-list-cycle
https://leetcode-cn.com/problems/linked-list-cycle-ii
https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

用C語言實現(xiàn)單鏈表操作

用C語言實現(xiàn)單鏈表操作

用C寫一個鏈表

進階操作

單鏈表反轉(zhuǎn)

中間節(jié)點

刪除倒數(shù)第N個指針

有序鏈表合并

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

用C語言實現(xiàn)單鏈表操作

用C寫一個鏈表

進階操作

單鏈表反轉(zhuǎn)

中間節(jié)點

刪除倒數(shù)第N個指針

有序鏈表合并

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av