中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

單向鏈表c語言實現(xiàn)

  1. 定義(引用百度百科)
    單鏈表是一種鏈式存取的數(shù)據(jù)結(jié)構(gòu)，用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。鏈表中的數(shù)據(jù)是以結(jié)點來表示的，每個結(jié)點的構(gòu)成：元素(數(shù)據(jù)元素的映象) + 指針(指示后繼元素存儲位置)，元素就是存儲數(shù)據(jù)的存儲單元，指針就是連接每個結(jié)點的地址數(shù)據(jù)。
  2. 場景

在實際生產(chǎn)中，有可能在軟件啟動后，對一些數(shù)據(jù)進行多態(tài)擴容，比如，網(wǎng)卡收發(fā)包的時候，從協(xié)議棧上產(chǎn)生一個需求的包，需要暫時排隊，等網(wǎng)卡把數(shù)據(jù)發(fā)送出去后，在在隊列里處理，所以這種利用堆中分散的內(nèi)存，以結(jié)點為單位的數(shù)據(jù)結(jié)果是有一定的意義的。

創(chuàng)新互聯(lián)公司專注于企業(yè)全網(wǎng)整合營銷推廣、網(wǎng)站重做改版、豐城網(wǎng)站定制設(shè)計、自適應品牌網(wǎng)站建設(shè)、H5場景定制、商城網(wǎng)站制作、集團公司官網(wǎng)建設(shè)、外貿(mào)網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應式網(wǎng)頁設(shè)計等建站業(yè)務，價格優(yōu)惠性價比高，為豐城等各大城市提供網(wǎng)站開發(fā)制作服務。

  1. C語言實現(xiàn)，聊作記錄

鏈表的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)

typedef struct node
{
        int data;                                           //數(shù)據(jù)域
        struct node *next;                          //指針域
}NODE_t;

鏈表的創(chuàng)建

    NODE_t *CreatNodeList()
{
    NODE_t *head = NULL;

    head = (NODE_t *)malloc(sizeof(NODE_t));
    if(!head)
        exit(-1);
    head->next = NULL;

    return head;
}

鏈表的插入，頭插入，有個頭節(jié)點，方便遍歷，處理

int InsertNode(NODE_t *head,int data)
{
    NODE_t *cur = NULL;

    if(!head)
        exit(-1);

    cur = (NODE_t *)malloc(sizeof(NODE_t));
    if(!cur)
        exit(-1);

    cur->data = data;
    //cur 插入到 head 和 head->next 之間
    cur->next = head->next;
    head->next = cur;

    return 0;
}

結(jié)點的查找

NODE_t *findNode(NODE_t *head,int data)
{
    head = head->next;
    while(head)
    {
        if(head->data == data)
        {
            break;
        }
        head = head->next;
    }
    if(head == NULL)
    {
        printf("sorry,%d is not in the list\n",data);
    }

    return head;
}

結(jié)點的刪除

    int DeleteNodeOfList(NODE_t *head,NODE_t *pfind)
{
    // 首先找到這個需要刪除指針的前一個節(jié)點的指針
    // 因為pfind 的合法性在外面判斷，此處不再判斷
    while(head->next != pfind)
    {
        head = head->next;
    }

    head->next = pfind->next;
    free(pfind);
    pfind = NULL;

    return 0;
}

這里的刪除，假設(shè)結(jié)點數(shù)目很多，則會造成一個問題，單鏈表只能一個方向，則需要找到需要刪除的節(jié)點的前驅(qū)指針，則需要從頭開始遍歷，比較浪費資源，所以，這個地方存在優(yōu)化空間，就是，一旦擁有需要刪除的節(jié)點，則可以這么操作

  • 將需要刪除節(jié)點后驅(qū)結(jié)點的數(shù)據(jù)域數(shù)據(jù)拷貝至當前的刪除節(jié)點數(shù)據(jù)域
  • 刪除刪除節(jié)點的后驅(qū)指針

優(yōu)化版本如下：

// 優(yōu)化點： 不必每次都遍歷所有的節(jié)點，找到前驅(qū)節(jié)點
// 將這個需要刪除的節(jié)點的后驅(qū)節(jié)點的數(shù)據(jù)域拷貝過來，然后刪除這個后驅(qū)節(jié)點
int DeleteNodeOfList_Better(NODE_t *head,NODE_t *pfind)
{
    NODE_t *p = pfind->next;

    //最后一個節(jié)點，它其后沒有后驅(qū)節(jié)點，所以需要從頭遍歷，找到它的前置節(jié)點
    if(pfind->next == NULL)
    {
        while(head->next != pfind)
        {
            head = head->next;
        }

        head->next = pfind->next;
        free(pfind);
        pfind = NULL;
    }
    else //對于除最后一個節(jié)點的外的其他位置節(jié)點，則使用覆蓋后刪除后置節(jié)點的方式實現(xiàn)刪除
    {

        pfind->data = pfind->next->data;
        pfind->next = pfind->next->next;

        free(p);
        p = NULL;
    }

    return 0;
}

一旦找到結(jié)點的指針操作只是針對數(shù)據(jù)域的一個操作，比較便捷
結(jié)點的修改

int UpdateNode(NODE_t *head,int olddata,int newdata)
{
    NODE_t *p = findNode(head,olddata);
    if(p)
    {
        p->data = newdata;
    }

    return 0;
}

遍歷打印顯示

void showList(NODE_t *head)
{
    head = head->next;
    while(head)
    {
        printf("%d ==> ",head->data);
        head = head->next;
    }
    printf("end..\n");
}

鏈表的排序

int sortList(NODE_t *head)
{
    int i = 0,j = 0;
    int listlen = 0;
    int tmpData = 0;
    NODE_t *p = NULL;

    // 使用冒泡排序，不動指針域，比較數(shù)據(jù)域，使用臨時變量，將有大小之別的節(jié)點的數(shù)據(jù)域交換
    // 得到鏈表長度，方便冒泡
    listlen = ListNodeLen(head);

    // 指到首節(jié)點
    p = head->next;
    for(i = 0;i < listlen-1;i++)
    {
        // 每一輪從頭開始
        p = head->next;
        for(j = 0;j<listlen - i-1;j++)
        {
            // 將小值排在前面
            if(p->data > p->next->data)
            {
                tmpData = p->data;
                p->data = p->next->data;
                p->next->data = tmpData;
            }
            p = p->next;
        }
    }

    return 0;
}

這里只是demo，鏈表的數(shù)據(jù)域很小，所以這種排序方式可以，但是當數(shù)據(jù)域的很大時，直接使用這種排序，涉及到大量的搬運內(nèi)存，將會導致很大的資源消耗，所以這個地方是存在優(yōu)化的空間的，比如直接改變需要交換結(jié)點的指向關(guān)系
代碼如下

int sortList_better(NODE_t *head)
{
    // 當數(shù)據(jù)域很大的時候，搬遠數(shù)據(jù)很耗費資源，但是指針就4個字節(jié)，
    // 所以改變指針域的相互指向，就可解決問題
    // 思路如下：
    // 還是使用冒泡比較，當需要交換時，將兩個節(jié)點的指針域指向關(guān)系互換

    int i = 0,j = 0;
    int listlen = 0;
    NODE_t *p = NULL;
    NODE_t *q = NULL;
    NODE_t *tmp = NULL;
    listlen = ListNodeLen(head);

    for(i = 0;i <listlen -1;i++)
    {
        tmp = head;
        p = head->next;
        q = p->next;                    // q 永遠指向p結(jié)點的下一個結(jié)點
        for(j = 0;j <listlen-i-1;j++)
        {
            if(p->data > q->data)
            {
                //                NODE_t *tmp = prePointerOfNode(head,p);
//                現(xiàn)在有三個結(jié)點，prep p    q 他們分別代表的含義是

//                p 為當前結(jié)點
//                prep為p結(jié)點的前驅(qū)結(jié)點
//                q 為p結(jié)點的后續(xù)結(jié)點

//                現(xiàn)在需要將p 和 q的順序做對調(diào)，只需要改變其指向關(guān)系即可
//                1. 將prep 的下一個結(jié)點指向到q
//                2. 將p結(jié)點后續(xù)結(jié)點指向q的后續(xù)結(jié)點
//                3. 在第二步里已經(jīng)在q的后續(xù)結(jié)點的已經(jīng)找到，所以這個時候?qū)的后續(xù)結(jié)點指向p，
//                這樣子，就將p和q的順序?qū)φ{(diào)過了
                tmp->next = q;
                p->next = q->next;
                q->next = p;

//                因為p和q的順序已經(jīng)對調(diào)過了，為保證順序，將p和q的順序做一次對調(diào),
//                確保q是p的下一個結(jié)點
                /*
                    注意p和q都是臨時變量，所以，這個地方并非對結(jié)點的對調(diào)，只是臨時指針的對調(diào)，就是將q對于結(jié)點的指針放到p這個臨時變量里
                    ，原來p對應的結(jié)點指針放到q這個臨時變量中
                */
                NODE_t *t = NULL;
                t = p;
                p = q;
                q = t;
            }
//            向下走一個
            tmp = tmp->next;
            p = p->next;
            q = p->next;
        }
    }

    return 0;
}

鏈表的逆序

void ReverseList(NODE_t *head)
{
    //將頭指針和其他鏈表割裂，這樣子就是一個空鏈表 和一個無頭的鏈表
    // 然后將另一個鏈表的每個結(jié)點拆出來，然后使用頭插法插入到空鏈中，這樣子最后就實現(xiàn)了鏈表的逆向排序

    NODE_t *HeadNextNode = head->next;
    head->next = NULL; //分割鏈表，分成一個空鏈和一個鏈表

    // 將第二個鏈表的每一個結(jié)點分別插入到空鏈的頭部
    for(HeadNextNode;HeadNextNode !=NULL;HeadNextNode = HeadNextNode->next)
    {
        InsertNode(head,HeadNextNode->data);
    }
}

這個思路很好，不易出錯，如果貿(mào)然的從指向關(guān)系上入手，很容易把自己繞暈

鏈表的銷毀

void DestoryNodeList(NODE_t *head)
{
    NODE_t *p = NULL;

    while(head)
    {
        p = head->next;
        free(head);
        head = p;
    }
}

當前標題：單向鏈表c語言實現(xiàn)
URL網(wǎng)址：http://www.rwnh.cn/article24/pgssce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供標簽優(yōu)化、網(wǎng)頁設(shè)計公司、定制開發(fā)、網(wǎng)站營銷、網(wǎng)站設(shè)計公司、響應式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)

網(wǎng)站托管運營
东安县| 缙云县| 大新县| 周至县| 蒙阴县| 嘉义县| 天水市| 罗城| 鄂尔多斯市| 岳西县| 北宁市| 宜丰县| 双峰县| 吐鲁番市| 崇明县| 康定县| 深水埗区| 如皋市| 白河县| 惠安县| 定西市| 竹北市| 宜宾市| 江北区| 澜沧| 桐城市| 河间市| 台中县| 扎鲁特旗| 河源市| 肃宁县| 竹山县| 廉江市| 石景山区| 桑植县| 长沙县| 潼关县| 延津县| 保靖县| 阳西县| 福贡县|