一起來看看C語言線性表的線性鏈表

Posted on by

定義

鏈表是通過一組任意的存儲單元來存儲線性表中的數據元素，每一個結點包含兩個域：存放數據元素信息的域稱為數據域，存放其後繼元素地址的域稱為指針域。因此n個元素的線性表通過每個結點的指針域連接成瞭一個“鏈條”，稱為鏈表。若此鏈表的每個結點中隻包含一個指針域，則被稱為線性鏈表或單鏈表。

線性表的鏈式存儲結構，它不需要用地址連續的存儲單元來實現，因為它不要求邏輯上相鄰的兩個數據元素物理位置上也相鄰，它是通過“指針”建立起數據元素之間的邏輯關系。

鏈表是由一個個結點構成的，結點定義如下：

typedef struct node
{
    DataType data;
    struct node *next;
} Linklist;

線性鏈表的存取必須從表頭指針開始，表頭指針指示線性鏈表中第一個結點的存儲單位置。由於線性表最後一個數據元素沒有直接後繼，則線性鏈表中的最後一個結點的指針域為“空”（NULL）。

為瞭使用方便可以在第一個元素的前面增加一個結點（被稱為頭節點），該節點的數據域為空，指針域中存儲線性鏈表的第一個元素所在的結點（表頭結點）的存儲地址。如果為空表，則指針域為空。

因此空鏈表也分為帶有頭結點的空鏈表和不帶頭結點的空鏈表。若有頭結點，頭結點的數據域為空，指針域為空，則說明該鏈表為空鏈表；若沒有頭結點，表頭指針為空指針，則說明該鏈表為空鏈表。

1.插入

假設要在線性表的兩個數據元素a和b之間插入一個數據元素x，p為指向結點a的指針。為瞭插入數據元素x，首先要生成一個數據域為x的新結點，s為指向新增節點的指針，然後使新增節點的指針域指向b(p->next)，結點a的指針域指向新增節點(s)。

int InsertLinkList(LinkList *H, int i, DataType x)
/*在有頭結點的線性鏈表H中第i個位置前插入元素x*/
{
    LinkList *p;
    LinkList *s;
    int j = 0;
    p = H;
    while (p && j<i-1)
    {
        p = p->next;
        j++;
    }/*循環直到p指向第i-1個元素*/
    if (!p)
        return -1;/*i大於表長加1*/
    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = x;
    s->next = p->next;/*插入數據元素x*/
    p->next = s;
    return 1;
}

2.建立線性鏈表

1)頭插法

建立線性鏈表應從空表開始，每讀入一個數據元素則申請一個結點，然後插在鏈表的頭結點與第一個結點之間。記頭結點為H，申請的結點為s，按照上述插入算法，操作步驟為：

s->next = H->next; H->next = s;

再加上新建頭結點、讀入數據元素、申請結點等步驟，可編程如下：

LinkList *CreateLinkList_front()
{
    LinkList *H;/*H表示頭結點*/
    LinkList *s;
    char x;/*設數據元素的類型為char*/
    H = (LinkList *)malloc(sizeof(LinkList));/*為頭結點申請內存空間*/
    H->next = NULL;
    scanf(" %c", &x);
    while (x!=flag)/*flag為結束創建過程的標志，如'#'等*/
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = x;
        s->next = H->next;
        H->next = s;
        scanf(" %c", &x);
    }
    return H;
}

因為是在鏈表的頭部插入，讀入數據的順序和線性表中的邏輯順序是相反的。

2)尾插法

在表頭插入建立線性鏈表方法簡單，但讀入數據元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插法。因為每次是將新結點插入到鏈表的尾部，所以需加入一個指針用來始終指向鏈表中的尾結點，以便能夠將新結點插入到鏈表的尾部。

在前面，我們介紹瞭插入算法，在這裡可以通過調用插入算法，即定義一個變量int i = 1;，調用前面的函數InsertLinkList(H, i, x);，每插入一個數據元素，便使i++;，這樣就可一直保持在鏈表的尾部插入。

LinkList *CreateLinkList_rear()
{
    LinkList *H;
    DataType x;/*設DataType為數據元素的類型*/
    int i = 1;
    H = (LinkList *)malloc(sizeof(LinkList));
    H->next = NULL;
    scanf(&x);/*讀入數據元素的值*/
    while (x!=flag)
    {
        InsertLinkList(H, i, x);/*調用插入算法*/
        i++;
        scanf(&x);
    }
    return H;
}

但是這樣使得算法的時間復雜度比頭插法要高出瞭一個數量級，因為每次在尾部插入數據元素時，都要重新調用InsertLinkList()函數，使指針重新從表頭指針開始指向尾結點。

因此我們可以使指針（記為p）一直指向鏈表中的尾結點，然後讓新結點（記為s）按照插入算法插入鏈表的尾部。隻需修改上述代碼的while循環即可實現：

LinkList *CreateLinkList_rear()
{
    LinkList *H, *p, *s;
    DataType x;/*設DataType為數據元素的類型*/
    H = (LinkList *)malloc(sizeof(LinkList));
    H->next = NULL;
    scanf(&x);/*讀入數據元素的值*/
    p = H;
    while (x!=flag)
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = x;
        s->next = NULL;
        p->next = s;
        p = p->next;
        scanf(&x);
    }
    return H;
}

3.刪除

假設鏈表中有a, b, c3個數據元素，要刪除數據元素a和數據元素c中間的數據元素b時，僅需修改數據元素a所在的結點的指針域。假設指針p指向數據元素a，用語句表示就是：

p->next = p->next->next;

添加一個指針變量q，讓q指向數據元素b，當改變數據元素a所在的結點的指針域後，即可釋放q的內存，即釋放數據元素b所占的內存。進一步地，調用函數時傳入標志變量i，可實現刪除第i個數據元素。

int DeleteLinkList(LinkList *H, int i)
/*在有頭結點的線性鏈表H中刪除第i個元素*/
{
    LinkList *p;
    LinkList *q;
    int j = 0;
    p = H;
    while (p->next && j<i-1)
    {
        p = p->next;
        j++;
    }/*循環直到p指向第i-1個元素*/
    if (!(p->next))
        return -1;/*刪除節點不合法*/
    q = p->next;
    p->next = q->next;/*刪除第i個數據元素*/
    free(q);/*釋放第i個數據元素所占內存*/
    return 1;
}

對比插入算法和刪除算法，while循環的功能同樣是使p指向第i-1個元素，為什麼插入算法的循環條件為p && j<i-1，而刪除算法的循環條件是p->next && j<i-1？能否將刪除算法的循環條件也改為p && j<i-1？

這是因為，在鏈表根本沒有i-1個元素的情況下，循環條件為p && j<i-1的循環運行結果為p指向尾結點的下一個結點即p=NULL，而循環條件為p->next && j<i-1的循環運行結果為p指向尾結點即p≠NULL。若將刪除算法的循環條件也改為p && j<i-1，在鏈表根本沒有i-1個元素的情況下，while循環後面的語句if (!(p->next))將會造成非法內存訪問，因為此時p=NULL，我們無法訪問空指針指向的內容。

4.查找

查找結點使用的算法是線性查找法（順序查找法），即從鏈表的第一個結點開始，順著指針鏈一個一個比較，相等則查找成功，返回結點位置；如果比較到最後也沒有相等的，則查找不成功，返回空。

LinkList *SearchLinkList(LinkList *H, DataType x)
/*在線性鏈表H中查找值為x的結點，找到後返回其指針，否則返回空*/
{
    LinkList *p = H->next;/*p指向線性鏈表的第一個數據元素*/
    while (p!=NULL && p->data!=x)
        p = p->next;
    return p;
}

若要返回值為x的結點在鏈表中的位序，則可使用一個標記變量i，記錄結點的位序；若找不到則返回-1。修改程序如下：

int SearchLinkList(LinkList *H, DataType x)
/*在線性鏈表H中查找值為x的結點，找到後返回其在鏈表中的位序，否則返回-1*/
{
    LinkList *p = H->next;/*p指向線性鏈表的第一個數據元素*/
    int i = 1;
    while (p!=NULL && p->data!=x)
    {
        p = p->next;
        i++;
    }
    if (p != NULL)
        return i;
    else
        return -1;
}

5.求線性鏈表的表長

設H是帶頭結點的線性鏈表（線性表的長度不包括頭結點），求線性鏈表的表長的操作與上述查找某結點在鏈表中的位序相似。

int LinkListLength(LinkList *H)
{
    LinkList *p = H;/*p指向頭結點*/
    int n = 0;
    while (p->next)
    {
        p = p->next;
        n++;
    }/*p所指的是第n個結點*/
    return n;
}

總結

本篇文章就到這裡瞭，希望能夠給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容!     

推薦閱讀：