c#中單鏈表有什么用

這篇文章主要介紹了c#中單鏈表有什么用，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

不帶頭節(jié)點(diǎn)鏈表

        單向鏈表是鏈表的一種。單向鏈表由一系列內(nèi)存不連續(xù)的節(jié)點(diǎn)組成，每個節(jié)點(diǎn)都包含指向值的域和指向下個節(jié)點(diǎn)的next指針。最后一個節(jié)點(diǎn)的next域?yàn)镹ULL值，代表鏈表結(jié)束。

        鏈表示意圖如下：

一，結(jié)構(gòu)體

1，結(jié)構(gòu)體定義：

struct LinkNode
{
    void *x; 
    struct LinkNode *next;
};

2，結(jié)構(gòu)體大小：

1）取結(jié)構(gòu)體大小方法：sizeof(struct LinkNode);在64位系統(tǒng)取出結(jié)構(gòu)體大小為：sizeof(struct LinkNode) = 16;

2）為什么是16字節(jié)：因?yàn)楸窘Y(jié)構(gòu)體包含的兩個指針成員x和next。指針是存放地址的，故在同一系統(tǒng)平臺下，指針變量取的sizeof大小都是一致。即對于指針變量的大小并不取決于指針類型，而取決于系統(tǒng)平臺。32位＝4字節(jié)，64位＝8字節(jié)。故有在64位系統(tǒng)中sizeof(void *) == sizeof(struct LinkNode *) == 8。在32位系統(tǒng)中，sizeof(void *) == sizeof(struct LinkNode *) == 4。

3）若假設(shè)節(jié)點(diǎn)ABCD是內(nèi)存連續(xù)的且A作為內(nèi)存其起始點(diǎn)，即A的地址為0x00，那么此時B，C，D的地址就依次為：0x10，0x20，0x30。且A的next指針指向的是節(jié)點(diǎn)B（A->next = &B）,依次類推，直到節(jié)點(diǎn)D的next存的是結(jié)束符NULL。

二，鏈表創(chuàng)建

1，鏈表創(chuàng)建一(使用一級指針)

    程序說明：

    1）程序調(diào)用方式szyu_link_create1("AA", "BB", NULL)，NULL用于正確終止for循環(huán)。

    2）創(chuàng)建新增節(jié)點(diǎn)node。

    3）如果鏈表為空，則先把新增節(jié)點(diǎn)(node)賦值給head,并讓last指向最新的head；如果鏈表不為空，則把尾節(jié)點(diǎn)的next指向最新節(jié)點(diǎn)，并重新賦值尾節(jié)點(diǎn)即可。

struct LinkNode
*szyu_link_create1(void *x, ...)
{
    struct LinkNode *head = NULL;
    struct LinkNode *last = head;

    va_list args;
    va_start(args, x);

    for ( ; x ; x = va_arg(args, void *) )
    {
        struct LinkNode *node = NULL;
        node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
        if ( node == NULL )
        {
            return head;
        }

        node->x = x;
        node->next = NULL;

        if ( head == NULL )
        {
            head = node;
            last = head;
        }
        else 
        {
            last->next = node;
            last = node;
        }
    }
    va_end(args);

    return head;
}

2，鏈表創(chuàng)建二(使用二級指針)

    程序說明：

    1）二級指針node存在如下成立等式：*node == head，**node = *head;

    2）for剛開始為*node(*node  = head)創(chuàng)建空間，既創(chuàng)建頭節(jié)點(diǎn)。

    3）為(*node)節(jié)點(diǎn)的x賦值，并讓指針node指向新節(jié)點(diǎn)的next，即賦值后*node即為前node的next域值。

    4）第二次for開始，為*node賦值就是給(*node)->next賦值。

    5）重復(fù)步驟3，4直到NULL傳入為止。

    6）最后一個節(jié)點(diǎn)把node指向next后并未對其進(jìn)行賦NULL值處理。故在for循環(huán)結(jié)束要為*node賦值NULL。代表鏈表結(jié)束。

struct LinkNode
*szyu_link_create2(void *x, ...)
{
    struct LinkNode *head  = NULL;
    struct LinkNode **node = &head;

    va_list args;
    va_start(args, x); 

    for ( ; x; x = va_arg(args, void *) )
    {   
        (*node) = (struct LinkNode *)malloc(sizeof(struct LinkNode));
        if ( (*node) == NULL )
        {   
            return head;
        }   

        (*node)->x = x;

        node = &(*node)->next;
    }   
    *node = NULL;
    va_end(args);

    return head;
}

3，一級指針和二級指針對比

    一級指針

    1）優(yōu)點(diǎn)：程序通俗易懂。

    2）缺點(diǎn)：插入頭節(jié)點(diǎn)和插入其他位置方式不同，代碼風(fēng)格不統(tǒng)一。

    二級指針

    1）優(yōu)點(diǎn)：無論插入什么位置，代碼風(fēng)格高度統(tǒng)一。代碼精簡。

    2）缺點(diǎn)：技巧性較高。

4，設(shè)計思路

    二級指針的使用場景就是“間接改變一級指針?biāo)赶虻膬?nèi)存地址”。而改變的一級指針指向的即為next指針。除頭節(jié)點(diǎn)外的所有節(jié)點(diǎn)新增地址都存在上一節(jié)點(diǎn)的next中，固有設(shè)計node指向next，為*node賦值時即為next賦值。

三，鏈表插入

1，鏈表插入一（使用一級指針）

    程序說明：

    1）key的判斷保證輸入位置不能小于1,并可以在鏈表最后面插入新節(jié)點(diǎn)。

    2）初始化新增節(jié)點(diǎn)。

    3）int cnt = 2;在key = 1時，是要重新插入第一個節(jié)點(diǎn)；key = 2 時插入的前一個節(jié)點(diǎn)即為第一節(jié)點(diǎn)。所以在key <= 2時是不需要進(jìn)行鏈表移動，故cnt ＝ 2開始執(zhí)行。

    4）由于不帶頭節(jié)點(diǎn)，故在插入時，插入在頭節(jié)點(diǎn)位置和后面位置需要區(qū)分考慮。

struct LinkNode
*szyu_link_insert1(struct LinkNode *head, void *x, int key)
{
    if ( head == NULL )
    {
        return head;
    }

    int len = szyu_link_length2(head);

    if ( key < 1 || key - 1 > len )
    {
        return head;
    }

    struct LinkNode *node = NULL;
    node = (struct LinkNode *)malloc(sizeof(struct LinkNode));
    if ( node == NULL )
    {
        return head;
    }

    node->x = x;
    node->next = NULL;

    struct LinkNode *list = head;
    
    int cnt = 2;
    for ( ; cnt < key; cnt++ )
    {
        list = list->next;
    }

    if ( key == 1 )
    {
        node->next = head;
        head = node;
    }
    else
    {
        node->next = list->next;
        list->next = node;
    }

    return head;
}

2，鏈表插入二（使用二級指針）

    程序說明：

    1）key - 1是保證在鏈表后面插入節(jié)點(diǎn)正常。

    2）由于使用二級指針故cnt初始化為1即可，無須單獨(dú)考慮插入頭節(jié)點(diǎn)情況。

struct LinkNode                                                                           
*szyu_link_insert2(struct LinkNode *head, void *x, int key)
{
    if ( head == NULL )
    {
        return head;
    }

    int len = szyu_link_length2(head);

    if ( key < 1 || key - 1 > len )
    {
        return head;
    }

    struct LinkNode **list = &head;

    int cnt = 1;

    while ( cnt < key )
    {
        list = &(*list)->next;
        cnt += 1;
    }
    struct LinkNode *remain = *list;

    *list = (struct LinkNode *)malloc(sizeof(struct LinkNode));
    if ( (*list) == NULL )
    {
        return head;
    }

    (*list)->x = x;
    (*list)->next = remain;

    return head;
}

3，使用一級指針和二級指針優(yōu)缺點(diǎn)同鏈表創(chuàng)建

4，使用二級指針設(shè)計思路

    1）首先使二級指針list指向一級指針head。

    2）循環(huán)使用鏈表停留在插入位置的前一節(jié)點(diǎn)上。此時若不是頭節(jié)點(diǎn)位置，list指向的是插入位置前一節(jié)點(diǎn)的next，插入時，只需為*list賦值新節(jié)點(diǎn)地址即可。若是頭節(jié)點(diǎn)，則*list指向頭節(jié)點(diǎn)。

    3）無論是否為頭節(jié)點(diǎn)，把剩下鏈表賦值給remain（若插入為頭節(jié)點(diǎn)，此時remain保留的事整個鏈表；若插入在最后，則remain為NULL）。

    4）為*list賦值新節(jié)點(diǎn)地址。并把remain追加到*list節(jié)點(diǎn)后面即可。

四，鏈表節(jié)點(diǎn)刪除

1，鏈表節(jié)點(diǎn)刪除(一級指針)

     程序說明：

    1）如果頭節(jié)點(diǎn)為要刪除節(jié)點(diǎn)，只需要把head指向head->next即可。

    2）由于delete停留在要刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)，故只需要把delete->next賦值給remain，在free即可。

struct LinkNode
*szyu_link_delete1(struct LinkNode *head, void *x)
{
    if ( head == NULL )
    {
        return NULL;
    }

    struct LinkNode *delete = head;
    struct LinkNode *remain = NULL;
    if ( strcmp((char *)delete->x, (char *)x) == 0 )
    {
        remain = delete;
        head = delete->next;
    }
    else
    {
        while ( delete->next != NULL && strcmp((char *)delete->next->x, (char *)x) != 0)
        {
            delete = delete->next;                                                  
        }

        remain = delete->next;
        delete->next = delete->next->next;
    }

    free(remain);

    return head;
}

2，鏈表節(jié)點(diǎn)刪除(二級指針)

    程序說明

    1）若為頭節(jié)點(diǎn)時，*list = head，head = head->next即可，即為*list = (*list)->next。

    2）若不為頭節(jié)點(diǎn)，list是指向next的指針，此時*list即為下個節(jié)點(diǎn)，若要刪除下個節(jié)點(diǎn)，為*list重新賦值即可改變下個節(jié)點(diǎn)指向。

struct LinkNode
*szyu_link_delete2(struct LinkNode *head, void *x) 
{
    if ( head == NULL )
    {   
        return head;
    }   

    struct LinkNode **list = &head;
    while ( (*list) != NULL && strcmp((char *)(*list)->x, (char *)x) != 0 ) 
    {   
        list = &(*list)->next;
    }   

    struct LinkNode *remain = *list;

    (*list) = (*list)->next;

    free(remain);

    return head;
}

五，鏈表釋放

    程序說明：

    1）使用二級指針后的*head即為刪除節(jié)點(diǎn)。

void
szyu_link_free2(struct LinkNode **head)
{
    if ( *head == NULL || head == NULL )
    {
        return;
    }

    struct LinkNode *next = NULL;
    for ( ; *head; *head = next )
    {
        next = (*head)->next;
        free(*head);                                                                
    }
}

六，鏈表長度獲取

    程序說明：

    1）由于鏈表不帶頭節(jié)點(diǎn)，故直接賦值head鏈表。

int
szyu_link_length2(struct LinkNode *head)
{
    if ( head == NULL )
    {
        return 0;
    }

    struct LinkNode *pLen = head;
    int len = 0;
    for ( ; pLen != NULL; pLen = pLen->next )
    {
        len += 1;
    }

    return len;
}

七，鏈表打印

void
szyu_link_print1(struct LinkNode *head)
{
    if ( head == NULL )
    {
        return;
    }

    struct LinkNode *print = head;
    for ( ; print != NULL; print = print->next )
    {
        printf("%s ", (char *)print->x);
    }

    printf("\n");
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“c#中單鏈表有什么用”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!