一起來看看C語言線性表的線性連結串列

2022-02-10 19:00:37

定義

連結串列是通過一組任意的儲存單元來儲存線性表中的資料元素，每一個結點包含兩個域：存放資料元素資訊的域稱為資料域，存放其後繼元素地址的域稱為指標域。因此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;
}

總結

本篇文章就到這裡了，希望能夠給你帶來幫助，也希望您能夠多多關注it145.com的更多內容!