數據結構--鏈表_ZenDei技術網路在線

網上關於鏈表的文章很多，比我寫的好的前輩也多不勝數。工作一年總是感覺前面學的後面忘，於是就誕生了寫博客的想法，把自己的工作學習歷程記下來互勉。思來想去還是把鏈表作為我的處女博吧，畢竟這是我踏入程式員路上寫的第一個數據結構，以下內容在忐忑、羞射的心情下編寫。如果有什麼不能忍的地方歡迎大家指正! --與 ...

　　網上關於鏈表的文章很多，比我寫的好的前輩也多不勝數。工作一年總是感覺前面學的後面忘，於是就誕生了寫博客的想法，把自己的工作學習歷程記下來互勉。思來想去還是把鏈表作為我的處女博吧，畢竟這是我踏入程式員路上寫的第一個數據結構，以下內容在忐忑、羞射的心情下編寫。如果有什麼不能忍的地方歡迎大家指正!

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　--與鏈表無關純屬矯情

　　談到鏈表之前，就想先說一下線性表。線性表是最基本、也是最常用的一種數據結構。一個線性表是多個數據的集合，除了第一個和最後一個數據元素之外，其它數據元素都是首尾相接的。線性表有兩種存儲方式，一種是順序存儲結構，另一種是鏈式存儲結構。

　　我們常用的數組就是一種典型的順序存儲結構。鏈表就是下麵要詳細說的鏈式存儲結構。

　　順序存儲結構就是兩個相鄰的元素在記憶體中也是相鄰的，這種存儲方式的優點是查詢比較方便，通過首地址和偏移量就可以訪問到某個元素，匹配的查找演算法也有好多，最快的可以達到O(logn)。缺點是插入刪除很不方便，複雜度最壞能達到O(n)，例如你想在某個位置插入/刪除元素，你需要將這個位置之後的所有元素都後移/前移一位。另外一個不方便的地方是元素數量的確定，必須在使用前創建一個足夠大的數組放置所有的元素，但是開闢的數組空間往往不能夠充分的利用造成資源浪費。

　　鏈式存儲結構就是相鄰的兩個元素在記憶體中不一定相鄰，這種存儲方式的優點是只需要操作指針就可以添加刪除元素，比較方便，時間複雜度為O(1)；另外一個優點就是節省記憶體，元素在需要添加的時候才開闢記憶體，不需要的時候就釋放，也不需要事先預估元素的數量，相對於順序存儲結構要靈活許多。缺點就是查找的演算法比較少，一般只能通過遍歷查找，時間複雜度為O(n)，還有一個缺點就是申請或者釋放記憶體會消耗時間，如果頻繁的對記憶體申請釋放，消耗的時間是很可觀的。

　　鏈表中的元素稱為結點，一般由兩部分組成：指針域和值域，值域可以是基本數據類型也可以是結構體等複雜數據類型，存放需要的具體數據；指針域為指向下一個節點的指針。根據指針域的不同鏈表可以分為單向鏈表，雙向鏈表，迴圈鏈表等等。

　　如上圖所示就是一個由四個節點組成的單向鏈表，其中每個Data和Next為一個節點，第一個節點稱為頭節點，最後一個節點稱為尾節點，Head為一個指向頭節點的指針。Data為節點的值域，用來存放數據；Next為節點的指針域，指向下一個節點。尾節點的指針域為空。

　　鏈表的操作主要是圍繞著指針域和對記憶體的申請釋放進行，一般的操作就是增、刪、改、查。頭節點可以與其他的節點數據類型不同，頭節點的值域中可以存放一些鏈表的信息，比如說鏈表的長度，創建時間，創建人等等。

　　下麵還是以一個簡單的C程式來具體操作一下。

　　整個程式由三個文件組成Chain——chain.h　　存放一些類型、函數等的聲明

　　　　　　　　　　　　　　　 |——chain.c　　存放函數的具體實現

　　　　　　　　　　　　　　　 |——main.c　　調用、測試實現的函數

　　　　　　　　　　　　　　　 |____Makefile　　MakeFile文件，編譯的時候使用，如果是初次接觸的話請忽略，後續的博客中會更新。

　　以下為chain.h文件

#ifndef _CHAIN_H_
#define _CHAIN_H_

/*聲明一些數據類型*/
typedef int datatype;//聲明鏈表存儲的數據類型
typedef unsigned short uint16;
typedef unsigned char bool;
/*返回結果*/
typedef enum
{
    TRUE,
    FALSE
}bool_val;

/*聲明鏈表節點*/
typedef struct node
{
    datatype data;
    struct node* next;
}ListNode;

/*聲明鏈表頭*/
typedef struct head
{
    char info[20];
    unsigned short length;
    ListNode* next;
}ListHead;

/*一下為一些鏈表操作函數的聲明*/
ListHead* CreateList();//創建鏈表
bool ViewList(ListHead* head);//遍歷鏈表
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data);//在指定位置添加節點
bool DelNodeByLoc(ListHead* head, uint16 loc);//刪除指定位置的節點
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data);//修改指定位置的節點數據
datatype FindDataByLoc(ListHead* head, uint16 loc);//返回指定位置的節點數據
bool DestoryList(ListHead* head);//銷毀鏈表



#endif

chain.h

　　以下為chain.c文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "chain.h"

/*創建鏈表*/
ListHead* CreateList()
{
    ListHead* head =  NULL;
    head = (ListHead*)malloc(sizeof(ListHead));    //申請記憶體
    memset(head, 0, sizeof(head));
    
    /*初始化鏈表信息*/
    head -> length = 0;
    strcpy(head -> info, "CangLing's List");
    head -> next = NULL;
    return head;
}

/*遍歷鏈表*/
bool ViewList(ListHead* head)
{
    /*合法性判斷*/
    if(head == NULL)
    {
        return FALSE;
    }
    ListNode* p = NULL;
    
    /*列印鏈表信息*/
    printf("The List Info is %s\n",head -> info);
    printf("The List Length is %d\n",head -> length);

    /*輸出節點內容*/
    p = head -> next;
    while(p != NULL)
    {
        printf("%d\n",p -> data);
        p = p -> next;
    }

    return TRUE;
}

/*根據位置添加節點，大於鏈表長度的位置添加在鏈表末尾*/
bool AddNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* node = head -> next;
    ListNode* tmp = NULL;
    /*初始化要創建的節點*/
    ListNode* p = (ListNode*)malloc(sizeof(ListNode));
    p -> data = data;
    p -> next = NULL;

    if(head -> length == 0)//對只有頭節點的鏈表進行處理
    {
        head -> next = p;
        p -> next = NULL;
    }
    else if(loc <= head -> length)//對1<loc<length的情況進行處理
    {
        /*添加在頭節點之後*/
        if(loc == 1)
        {
            head -> next = p;
            p -> next = node;
        }
        else
        {
            /*尋找對應位置的前一個節點*/
            while(loc > 2)
            {
                loc--;
                node = node -> next;
            }
            tmp = node -> next;//保存loc位置的節點地址
            node -> next = p;//將要添加的節點放在loc位置
            p -> next = tmp;
        }

    }
    else//對loc>length的情況進行處理
    {
        while(node -> next != NULL)
        {
            node = node -> next;
        }

        node -> next = p;
    }

    head -> length++;//修改鏈表信息
    ret = TRUE;

    return ret;

}

/*刪除loc位置的節點*/
bool DelNodeByLoc(ListHead* head, uint16 loc)
{
    /*進行合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }

    bool_val ret = FALSE;
    ListNode* tmp = head -> next;
    ListNode* freenode = NULL;

    if(loc == 1)//針對第一個節點的處理
    {
        freenode = tmp;
        head -> next = tmp -> next;
    }
    else//對1<loc<length的情況進行處理
    {
        while(loc > 2)//找到loc的前一個節點
        {
            loc--;
            tmp = tmp -> next;
        }

        freenode = tmp -> next;//保存要釋放的節點地址
        tmp -> next = freenode -> next;
    }

    /*釋放節點並修改鏈表信息*/
    free(freenode);
    head -> length --;

    return ret;
}

/*修改loc位置的節點信息*/
bool ModNodeByLoc(ListHead* head, uint16 loc, datatype data)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    bool_val ret = FALSE;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc節點
    {
        tmp = tmp -> next;
        loc --;
    }

    tmp -> data = data;//修改節點數據
    return ret;
}

/*返回loc節點的數據*/
datatype FindDataByLoc(ListHead* head, uint16 loc)
{
    /*合法性判斷*/
    if((head == NULL) || (loc == 0) || (loc > head -> length))
    {
        return FALSE;
    }
    datatype ret = 0;
    ListNode* tmp = head -> next;

    while(loc > 1)//找到loc節點
    {
        tmp = tmp -> next;
        loc --;
    }

    ret = tmp -> data;

    return ret;
}

bool DestoryList(ListHead* head)
{
    ListNode* p = NULL;
    ListNode* node = NULL;
    if(head == NULL)
    {
        return TRUE;
    }

    /*釋放除頭節點之外的節點*/
    p = head -> next;

    while(p != NULL)
    {
        node = p;
        p = p -> next;
        free(node);
    }

    /*釋放頭節點*/
    free(head);

    return TRUE;
}

chain.c

　　以下為main.c文件

#include <stdio.h>
#include "chain.h"

int main()
{
    int i = 0;
    ListHead* head =  NULL;
    head = CreateList();//創建鏈表

    printf("Now we will Add four Nodes\n");
    for(i = 1; i < 5; i++)
    {
        AddNodeByLoc(head, i, i);//添加鏈表節點
    }
    ViewList(head);//遍歷鏈表

    printf("Now we will Delete the third Node\n");
    DelNodeByLoc(head, 3);//刪除鏈表的第三個節點
    ViewList(head);

    printf("Now we will modify the third Node to 5\n");
    ModNodeByLoc(head, 3, 5);//將第三個節點的信息修改為5
    ViewList(head);

    printf("Now we will view the second Node\n");
    printf("%d\n",FindDataByLoc(head, 2));//查看第二個節點的數據
    DestoryList(head);//銷毀鏈表
}

main.c

　　以下為MakeFile文件

main: chain.o main.o    #生成main依賴的文件
#執行命令cc chain.o main.o -o main生成最終的可執行文件main
    cc chain.o main.o -o main
main.o: main.c chain.h    #生成main.o依賴的文件

chain.o: chain.c chain.h    #生成chain.o依賴的文件

#刪除生成的中間文件
clean:    
    rm *.o main

MakeFile

　　上面的四個文件我在Linux的環境下使用，將上面的文件放在同一個文件夾下，輸入make運行，完成後生成chain.o main.o以及可執行文件main，運行make clean清除三個編譯生成的文件。

　　這裡我簡單說一下什麼是Makefile。在Windows下編譯工作都由IDE來完成，例如VC6.0編譯工程，你不需要管文件之間的依賴關係。但是在Linux環境下這部分工作由MakeFile完成。MakeFile關係到整個工程的編譯規則，一個工程下文件不計其數，按模塊、類型、功能分放在不同的目錄下，MakeFile指定了一系列規則來指定哪些文件先編譯，哪些文件需要後編譯，哪些文件需要重新編譯，甚至還有一些更複雜的功能操作。它帶來的好處就是“自動化編譯”，一旦寫好MakeFile文件，工程的編譯只需要一個make命令，整個工程就會全自動編譯。上面就是我為鏈表寫的一個很簡單的MakeFile文件，後續的博客中會更新MakeFile的相關用法。