C語(yǔ)言線性表的線性鏈表是什么

這篇文章主要介紹“C語(yǔ)言線性表的線性鏈表是什么”，在日常操作中，相信很多人在C語(yǔ)言線性表的線性鏈表是什么問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C語(yǔ)言線性表的線性鏈表是什么”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

定義

鏈表是通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素，每一個(gè)結(jié)點(diǎn)包含兩個(gè)域：存放數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存放其后繼元素地址的域稱為指針域。因此n個(gè)元素的線性表通過(guò)每個(gè)結(jié)點(diǎn)的指針域連接成了一個(gè)“鏈條”，稱為鏈表。若此鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域，則被稱為線性鏈表或單鏈表。

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它不需要用地址連續(xù)的存儲(chǔ)單元來(lái)實(shí)現(xiàn)，因?yàn)樗?strong>不要求邏輯上相鄰的兩個(gè)數(shù)據(jù)元素物理位置上也相鄰，它是通過(guò)“指針”建立起數(shù)據(jù)元素之間的邏輯關(guān)系。

鏈表是由一個(gè)個(gè)結(jié)點(diǎn)構(gòu)成的，結(jié)點(diǎn)定義如下：

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

線性鏈表的存取必須從表頭指針開(kāi)始，表頭指針指示線性鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)單位置。由于線性表最后一個(gè)數(shù)據(jù)元素沒(méi)有直接后繼，則線性鏈表中的最后一個(gè)結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL）。

為了使用方便可以在第一個(gè)元素的前面增加一個(gè)結(jié)點(diǎn)（被稱為頭節(jié)點(diǎn)），該節(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?/strong>，指針域中存儲(chǔ)線性鏈表的第一個(gè)元素所在的結(jié)點(diǎn)（表頭結(jié)點(diǎn)）的存儲(chǔ)地址。如果為空表，則指針域?yàn)榭铡?/p>

因此空鏈表也分為帶有頭結(jié)點(diǎn)的空鏈表和不帶頭結(jié)點(diǎn)的空鏈表。若有頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域?yàn)榭?，指針域?yàn)榭眨瑒t說(shuō)明該鏈表為空鏈表；若沒(méi)有頭結(jié)點(diǎn)，表頭指針為空指針，則說(shuō)明該鏈表為空鏈表。

1.插入

假設(shè)要在線性表的兩個(gè)數(shù)據(jù)元素a和b之間插入一個(gè)數(shù)據(jù)元素x，p為指向結(jié)點(diǎn)a的指針。為了插入數(shù)據(jù)元素x，首先要生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)，s為指向新增節(jié)點(diǎn)的指針，然后使新增節(jié)點(diǎn)的指針域指向b(p->next)，結(jié)點(diǎn)a的指針域指向新增節(jié)點(diǎn)(s)。

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

2.建立線性鏈表

1)頭插法

建立線性鏈表應(yīng)從空表開(kāi)始，每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)結(jié)點(diǎn)，然后插在鏈表的頭結(jié)點(diǎn)與第一個(gè)結(jié)點(diǎn)之間。記頭結(jié)點(diǎn)為H，申請(qǐng)的結(jié)點(diǎn)為s，按照上述插入算法，操作步驟為：

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

再加上新建頭結(jié)點(diǎn)、讀入數(shù)據(jù)元素、申請(qǐng)結(jié)點(diǎn)等步驟，可編程如下：

LinkList *CreateLinkList_front()
{
    LinkList *H;/*H表示頭結(jié)點(diǎn)*/
    LinkList *s;
    char x;/*設(shè)數(shù)據(jù)元素的類型為char*/
    H = (LinkList *)malloc(sizeof(LinkList));/*為頭結(jié)點(diǎn)申請(qǐng)內(nèi)存空間*/
    H->next = NULL;
    scanf(" %c", &x);
    while (x!=flag)/*flag為結(jié)束創(chuàng)建過(guò)程的標(biāo)志，如'#'等*/
    {
        s = (LinkList *)malloc(sizeof(LinkList));
        s->data = x;
        s->next = H->next;
        H->next = s;
        scanf(" %c", &x);
    }
    return H;
}

因?yàn)槭窃阪湵淼念^部插入，讀入數(shù)據(jù)的順序和線性表中的邏輯順序是相反的。

2)尾插法

在表頭插入建立線性鏈表方法簡(jiǎn)單，但讀入數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，所以需加入一個(gè)指針用來(lái)始終指向鏈表中的尾結(jié)點(diǎn)，以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部。

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

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

但是這樣使得算法的時(shí)間復(fù)雜度比頭插法要高出了一個(gè)數(shù)量級(jí)，因?yàn)槊看卧谖膊坎迦霐?shù)據(jù)元素時(shí)，都要重新調(diào)用InsertLinkList()函數(shù)，使指針重新從表頭指針開(kāi)始指向尾結(jié)點(diǎn)。

因此我們可以使指針（記為p）一直指向鏈表中的尾結(jié)點(diǎn)，然后讓新結(jié)點(diǎn)（記為s）按照插入算法插入鏈表的尾部。只需修改上述代碼的while循環(huán)即可實(shí)現(xiàn)：

LinkList *CreateLinkList_rear()
{
    LinkList *H, *p, *s;
    DataType x;/*設(shè)DataType為數(shù)據(jù)元素的類型*/
    H = (LinkList *)malloc(sizeof(LinkList));
    H->next = NULL;
    scanf(&x);/*讀入數(shù)據(jù)元素的值*/
    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.刪除

假設(shè)鏈表中有a, b, c3個(gè)數(shù)據(jù)元素，要?jiǎng)h除數(shù)據(jù)元素a和數(shù)據(jù)元素c中間的數(shù)據(jù)元素b時(shí)，僅需修改數(shù)據(jù)元素a所在的結(jié)點(diǎn)的指針域。假設(shè)指針p指向數(shù)據(jù)元素a，用語(yǔ)句表示就是：

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

添加一個(gè)指針變量q，讓q指向數(shù)據(jù)元素b，當(dāng)改變數(shù)據(jù)元素a所在的結(jié)點(diǎn)的指針域后，即可釋放q的內(nèi)存，即釋放數(shù)據(jù)元素b所占的內(nèi)存。進(jìn)一步地，調(diào)用函數(shù)時(shí)傳入標(biāo)志變量i，可實(shí)現(xiàn)刪除第i個(gè)數(shù)據(jù)元素。

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

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

這是因?yàn)?，在鏈表根本沒(méi)有i-1個(gè)元素的情況下，循環(huán)條件為p && j<i-1的循環(huán)運(yùn)行結(jié)果為p指向尾結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)即p=NULL，而循環(huán)條件為p->next && j<i-1的循環(huán)運(yùn)行結(jié)果為p指向尾結(jié)點(diǎn)即p&ne;NULL。若將刪除算法的循環(huán)條件也改為p && j<i-1，在鏈表根本沒(méi)有i-1個(gè)元素的情況下，while循環(huán)后面的語(yǔ)句if (!(p->next))將會(huì)造成非法內(nèi)存訪問(wèn)，因?yàn)榇藭r(shí)p=NULL，我們無(wú)法訪問(wèn)空指針指向的內(nèi)容。

4.查找

查找結(jié)點(diǎn)使用的算法是線性查找法（順序查找法），即從鏈表的第一個(gè)結(jié)點(diǎn)開(kāi)始，順著指針鏈一個(gè)一個(gè)比較，相等則查找成功，返回結(jié)點(diǎn)位置；如果比較到最后也沒(méi)有相等的，則查找不成功，返回空。

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

若要返回值為x的結(jié)點(diǎn)在鏈表中的位序，則可使用一個(gè)標(biāo)記變量i，記錄結(jié)點(diǎn)的位序；若找不到則返回-1。修改程序如下：

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

5.求線性鏈表的表長(zhǎng)

設(shè)H是帶頭結(jié)點(diǎn)的線性鏈表（線性表的長(zhǎng)度不包括頭結(jié)點(diǎn)），求線性鏈表的表長(zhǎng)的操作與上述查找某結(jié)點(diǎn)在鏈表中的位序相似。

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

到此，關(guān)于“C語(yǔ)言線性表的線性鏈表是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！