雙向循環(huán)鏈表詳解及C語言簡單實(shí)現(xiàn)-創(chuàng)新互聯(lián)

概念

鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。而雙向鏈表顧名思義通過指針域向前查找或者向后查找，且頭結(jié)點(diǎn)與尾節(jié)點(diǎn)直接相連構(gòu)成環(huán)。

創(chuàng)新互聯(lián)于2013年開始，是專業(yè)互聯(lián)網(wǎng)技術(shù)服務(wù)公司，擁有項(xiàng)目成都網(wǎng)站制作、成都做網(wǎng)站網(wǎng)站策劃，項(xiàng)目實(shí)施與項(xiàng)目整合能力。我們以讓每一個夢想脫穎而出為使命，1280元孟村做網(wǎng)站,已為上家服務(wù),為孟村各地企業(yè)和個人服務(wù),聯(lián)系電話:18982081108數(shù)據(jù)結(jié)構(gòu)

#ifndef DLIST_H
#define DLIST_H

// 數(shù)據(jù)類型，可根據(jù)需要自行定義
#define Item int 

// 鏈表節(jié)點(diǎn)信息 
typedef struct DLNode
{Item item;
    struct DLNode *prev;
    struct DLNode *next;
} DLNode;

typedef struct DList
{int size;
    DLNode *head;
} DList;

// Interfaces 
void InitDList(DList *dlist);
void InsertDlist(DList *dlist);
DLNode *searchDlist(Dlist *dlist);
void DeleteDlist(DList *dlist, const Item data);
void ShowDlist(const DList *dlist);
void freeDList(DList *dlist); 

#endif //DLIST_H

接口源代碼

#include#include#include#include

// 初始化雙向鏈表，帶頭結(jié)點(diǎn)
void InitDList(DList *dlist)
{dlist->head = (DLNode *)malloc(sizeof(DLNode));
    if (dlist->head == NULL)
        return;

    dlist->size = 0;
    dlist->head->item = -1;
    dlist->head->prev = dlist->head;
    dlist->head->next = dlist->head;
}

// 鏈表項(xiàng)數(shù)
int DListcounts(DList *dlist)
{assert(dlist);
    return dlist->size;
}

// 插入數(shù)據(jù) 1）將數(shù)據(jù)封裝成節(jié)點(diǎn)    2）插入鏈表尾
void InsertDList(DList *dlist, const Item data)
{assert(dlist != NULL);
    DLNode *newnode = (DLNode *)malloc(sizeof(DLNode));
    if(newnode == NULL)
    {printf("out of memory !!\n");
        exit(1);
    }

    newnode->item = data;

    newnode->prev = dlist->head->prev;
    newnode->next = dlist->head;
    dlist->head->prev->next = newnode;
    dlist->head->prev = newnode;
    dlist->size++;
}

// 在循環(huán)鏈表中查找指定數(shù)據(jù)的節(jié)點(diǎn)
DLNode *searchDList(DList *dlist, const Item data)
{int i;
    assert(dlist != NULL);
    if(dlist->size == 0)
    {printf("the dlist is empty, do not find element:%d\n", data);
        return NULL;
    }

    DLNode *cur = dlist->head->next;
    for (i = 0; i< dlist->size; i++)
    {if(cur->item == data)
        {printf("find it ^_^!!!\n");
            return cur;
        }
        cur = cur->next;
    }

    if( i == dlist->size)
    {printf("unlucky, the element:%d is not exist in dlsit\n");
        return NULL;
    }
}

// 在雙向循環(huán)鏈表中獲取指定數(shù)據(jù)的節(jié)點(diǎn)，并返回
void deleteDList(DList *dlist, const Item data)
{DLNode *node = searchDList(dlist, data);
    if(node == NULL)
    {printf("the delete element is not exist in dlist!!\n");
        return;
    }

    node->prev->next = node->next; 
    node->next->prev = node->prev;
    dlist->size--;
    free(node);
    printf("delete it successfully!!\n");
    return ;
}


// 釋放構(gòu)建鏈表所申請的堆內(nèi)存
void freeDList(DList *dlist)
{DLNode *cur =NULL, *next = NULL;
    for (cur = dlist->head->next; cur != dlist->head; cur = next)
    {next = cur->next;       // 獲取下一個節(jié)點(diǎn)
        free(cur);          // 釋放節(jié)點(diǎn)
    }

    free(dlist->head);
    dlist->head = NULL;
}

測試結(jié)果

// 主函數(shù)，對上述各接口調(diào)用
int main()
{DList list;
    DLNode *node;
    InitDList(&list);
    InsertDList(&list, 1);
    InsertDList(&list, 2);
    showDList(&list);
    node = searchDList(&list, 3);

    int counts1 = DListcounts(&list);
    printf("the counts of dlist is %d\n", counts1);

    deleteDList(&list, 1);

    int counts2 = DListcounts(&list);
    printf("the counts of dlist is %d\n", counts2);
    showDList(&list);
    freeDList(&list);
    return 0;
}

[postgres@test dlist_test]$ ./Dlist
1       2
unlucky, the element:3 is not exist in dlsit
the counts of dlist is 2
find it ^_^!!!
delete it successfully!!
the counts of dlist is 1
2

LeetCode 試題

class Solution {public:
    Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;
        Node* cur = head;
        // 1. 復(fù)制各節(jié)點(diǎn)，并構(gòu)建拼接鏈表
        while(cur != nullptr) {Node* tmp = new Node(cur->val);
            tmp->next = cur->next;
            cur->next = tmp;
            cur = tmp->next;
        }
        // 2. 構(gòu)建各新節(jié)點(diǎn)的 random 指向
        cur = head;
        while(cur != nullptr) {if(cur->random != nullptr)
                cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        // 3. 拆分兩鏈表
        cur = head->next;
        Node* pre = head, *res = head->next;
        while(cur->next != nullptr) {pre->next = pre->next->next;
            cur->next = cur->next->next;
            pre = pre->next;
            cur = cur->next;
        }
        pre->next = nullptr; // 單獨(dú)處理原鏈表尾節(jié)點(diǎn)
        return res;      // 返回新鏈表頭節(jié)點(diǎn)
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

本文標(biāo)題：雙向循環(huán)鏈表詳解及C語言簡單實(shí)現(xiàn)-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://bm7419.com/article24/hecce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供域名注冊、品牌網(wǎng)站制作、網(wǎng)站營銷、用戶體驗(yàn)、網(wǎng)站制作、外貿(mào)建站

廣告

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