這篇文章依然介紹線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)-單鏈表

單鏈表的整表創(chuàng)建

線性表順序存儲結(jié)構(gòu)的創(chuàng)建，其實就是一個數(shù)組的初始化，即聲明一個類型和容量確定的數(shù)組并賦值的過程。單鏈表和線性表順序存儲結(jié)構(gòu)不一樣，它不像單鏈表那樣內(nèi)存地址是連續(xù)的，元素存儲的地址比較分散，可以存儲在內(nèi)存中未被使用的任意位置，它的大小和位置不是預(yù)先分配好的，而是根據(jù)實際需求即時生成，因此單鏈表是一個 動態(tài)表，創(chuàng)建單鏈表的過程就是一個動態(tài)生成鏈表的過程，從 空表 的初始狀態(tài)，依次建立各元素結(jié)點(diǎn)，并插入鏈表
單鏈表整表創(chuàng)建的過程需要用到我們前面文章中介紹到的 頭插法 與 尾插法：
頭插法創(chuàng)建單鏈表
1.聲明一個結(jié)點(diǎn) p 和 計數(shù)器變量 i
2.初始化一個空鏈表 L
3.將 L 頭結(jié)點(diǎn)的指針域指向 NULL，建立一個帶有頭結(jié)點(diǎn)的單鏈表
4.循環(huán)：

• 生成一個新結(jié)點(diǎn)賦值給 p
• 隨機(jī)生成一個數(shù)字賦值給結(jié)點(diǎn)p的數(shù)據(jù)域 p->data
• 將 p 插入到頭結(jié)點(diǎn)與前一新結(jié)點(diǎn)之間
  實現(xiàn)代碼如下：

// 定義一個鏈表結(jié)構(gòu)
typedef struct ListNode
{
    int date;              // 鏈表一個結(jié)點(diǎn)的數(shù)據(jù)域
    struct ListNode *next; // 指向下一個結(jié)點(diǎn)的指針域,即存儲的是下一個結(jié)點(diǎn)的內(nèi)存地址
} Node, *ListLink;         // 結(jié)構(gòu)體變量

// 創(chuàng)建一個新鏈表
void CreateListHead(int n) {
    // 使用malloc函數(shù)為鏈表結(jié)構(gòu)動態(tài)分配一塊內(nèi)存空間，分配成功則返回一個指向該鏈表結(jié)構(gòu)的指針，該指針指向該分配內(nèi)存空間的首地址
    // 即 *L 是頭指針
    *L = (ListLink)malloc(sizeof(Node));
    // 將該結(jié)構(gòu)體的next置為NULL,創(chuàng)建一個包含頭結(jié)點(diǎn)的單鏈表
    (*L)->next = NULL;

    // 初始化隨機(jī)數(shù)種子
    srand(time(0));

    // 循環(huán)
    for (int i = 0; i < n; ++i)
    {
        *p = (ListLink)malloc(sizeof(Node));// 生成新結(jié)點(diǎn)
        (*p)->data = rand() % 100 + 1; // 隨機(jī)生成 100 以內(nèi)的數(shù)據(jù),并將數(shù)據(jù)元素賦值給新結(jié)點(diǎn)的數(shù)據(jù)域

        // 執(zhí)行插入操作
        (*p)->next = (*L)->next;
        (*L)->next = p; 
    }
}

尾插法實現(xiàn)單鏈表創(chuàng)建
代碼實現(xiàn)如下：

// 定義一個鏈表結(jié)構(gòu)
typedef struct ListNode
{
    int date;              // 鏈表一個結(jié)點(diǎn)的數(shù)據(jù)域
    struct ListNode *next; // 指向下一個結(jié)點(diǎn)的指針域,即存儲的是下一個結(jié)點(diǎn)的內(nèi)存地址
} Node, *ListLink;         // 結(jié)構(gòu)體變量

void CreateListTail(int n) {
    // 初始化一個空鏈表
    *L = (ListLink)malloc(sizeof(ListNode));
    // 將該結(jié)構(gòu)體的next設(shè)為 NULL 創(chuàng)建一個帶有頭結(jié)點(diǎn)的單鏈表
    (*L)->next = NULL;

    // 定義尾結(jié)點(diǎn)
    ListLink end = NULL;

    // 將頭結(jié)點(diǎn)賦值給尾結(jié)點(diǎn)
    // 在沒有創(chuàng)建其他結(jié)點(diǎn)之前,只有頭結(jié)點(diǎn),這個時候頭結(jié)點(diǎn)就是尾結(jié)點(diǎn),尾結(jié)點(diǎn)就是頭結(jié)點(diǎn)
    end = *L;

    // 初始化隨機(jī)種子
    srand(time(0));
    
    // 循環(huán)
    for (int i = 0; i < n; ++i)
    {
        // 創(chuàng)建新結(jié)點(diǎn)
        *p = (ListLink)malloc(sizeof(ListNode));
        (*p)->next = rand() % 100 + 1; // 隨機(jī)生成 100 以內(nèi)的數(shù)據(jù),并將數(shù)據(jù)元素賦值給新結(jié)點(diǎn)的數(shù)據(jù)域

        // 執(zhí)行插入操作
        end->next = (*p);
        end = (*p);
    }
    end->next = NULL;
}

注意：在循環(huán)結(jié)束后我們要把尾結(jié)點(diǎn)的指針域置為 NULL,置為 NULL 的原因方便以后遍歷時能確認(rèn)其是尾部

單鏈表的整表刪除

單鏈表整表刪除的算法思路如下：
1.聲明兩個結(jié)點(diǎn) p 和 q
2.將鏈表的第一個結(jié)點(diǎn)賦值給 p
3.循環(huán)：

• 將下一個結(jié)點(diǎn)賦值給 q
• 使用 free 函數(shù)將 p 釋放
• 將 q 賦值給 p
  代碼實現(xiàn)如下：

// 單鏈表的整表刪除
Status DeleteList(ListLink *L) {
    // 聲明兩個結(jié)點(diǎn) p 和 q
    ListLink p,q;

    //將鏈表的第一個節(jié)點(diǎn)賦值給 p
    p = (*L)->next;

    while(p) {
        // 將下一個結(jié)點(diǎn)賦值給 q
        q = p->next;
        // 使用 free 函數(shù)將 p 釋放
        free(p);
        q=p;
    }

    // 當(dāng) p 為空時跳出循環(huán)

    // 頭結(jié)點(diǎn)指針域為空
    (*L)->next = NULL;
}

總結(jié)

通過上面的介紹我們簡單的對線性表的順序存儲結(jié)構(gòu)和單鏈表做下對比

存儲方式

• 順序存儲結(jié)構(gòu)用一塊連續(xù)的存儲單元存儲線性表的數(shù)據(jù)元素
• 單鏈表采用鏈?zhǔn)酱鎯Ψ绞?，用一組任意的存儲單元存放線性表的數(shù)據(jù)元素

時間性能

1.查找

• 順序存儲結(jié)構(gòu) O(1)
• 單鏈表 O(n)
  2.插入和刪除
• 順序存儲結(jié)構(gòu) O(n)
• 單鏈表在第一次查找到需要操作的元素位置后,插入和刪除操作的時間復(fù)雜度僅為 O(1)

空間性能

• 順序存儲結(jié)構(gòu)需要預(yù)先分配存儲空間，分大了，浪費(fèi)空間，分小了，容易溢出
• 單鏈表不需要預(yù)先分配空間，根據(jù)實際需求分配

通過上面的比對，我們可以得到幾點(diǎn)經(jīng)驗性的結(jié)論：

• 若線性表頻繁的查找，插入和刪除操作比較少，那么我們可以選擇順序存儲結(jié)構(gòu)。若插入和刪除操作頻繁時，可以選擇單鏈表。這些都是線性表不同存儲方式的優(yōu)缺點(diǎn)，實際開發(fā)中的數(shù)據(jù)存儲結(jié)構(gòu)肯定更加復(fù)雜我們需要根據(jù)具體的場景選擇適合的數(shù)據(jù)存儲結(jié)構(gòu)
• 當(dāng)線性表中的元素我們不清楚具體有多少時或者線性表的數(shù)據(jù)元素個數(shù)變化比較大的時候，最好選擇單鏈表結(jié)構(gòu)；而對于那些事先就能知道其數(shù)據(jù)元素個數(shù)，可以選擇順序存儲結(jié)構(gòu)