日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

詳解C語言如何實現雙向帶頭循環鏈表_C 語言

作者：蔣靈瑜的流水賬 ? 更新時間： 2022-10-08 編程語言

一、雙向循環鏈表與順序表的區別

不同點 順序表 雙向帶頭循環鏈表
在內存中的存儲方式 連續存儲 不一定連續
隨機訪問 支持隨機訪問 不支持隨訪問
任意元素插入或刪除 尾插O(1)，其他O(N)，可能需要挪動元素 通過修改指針指向即可
應用場景 元素高效存儲、頻繁訪問 任意位置插入刪除頻繁
三級緩存命中率 高 低

寄存器的速度遠快于主存，所以需要三級緩存先將數據取出，寄存器讀取時將相鄰地址的數據進行讀取，所以順序表內存地址連續的特點使其三級緩存命中率高。

雙向帶頭循環鏈表雖然在鏈表中結構最復雜，但是解決了單鏈表找前一個節點需要遍歷、要判斷頭結點是否為空的缺點。

二、List.h

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int ListDateType;
typedef struct ListNode
{
    struct ListNode* next;
    struct ListNode* prev;
    ListDateType date;
}ListNode;
ListNode* ListInit();//初始化
void ListDestroy(ListNode* phead);//銷毀
void PrintList(ListNode* phead);//打印
bool ListEmpty(ListNode* phead);//判斷鏈表是否為空（只有頭節點）
 
void ListPushBack(ListNode* phead, ListDateType x);//尾插
void ListPopback(ListNode* phead);//尾刪
void ListPushFront(ListNode* phead, ListDateType x);//頭插
void ListPopFront(ListNode* phead);//頭刪
size_t ListSize(ListNode* phead);//有效節點個數
ListNode* ListFind(ListNode* phead, ListDateType x);//查找（可用于修改）
void ListInsert(ListNode* pos, ListDateType x);//pos位置插入
void ListErase(ListNode* pos);//刪除pos位置

結構體內包含指向下一個節點的指針next、指向上一個節點的指針prev和本節點存儲的數據date

三、List.c

1、帶頭雙向循環鏈表的初始化

ListNode* ListInit()//初始化，返回帶哨兵位的頭結點
{
    ListNode* guard = (ListNode*)malloc(sizeof(ListNode));
    if (guard == NULL)
    {
        perror("ListInit fail:\n");
        exit(-1);
    }
    guard->next = guard;
    guard->prev = guard;
    return guard;
}

malloc一個哨兵位的頭結點，并將其next和prev指針置空。

2、帶頭雙向循環鏈表的銷毀

void ListDestroy(ListNode* phead)//銷毀，傳一級指針調用方需要在外部將頭結點指針置空
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)//釋放非頭結點
    {
        ListNode* next = cur->next;
        free(cur);
        cur = next;
    }
    free(phead);//再釋放頭結點
}

為了保持接口的一致性，形參用一級指針，所以需要調用者在外部對頭指針置空。

先釋放非頭結點，再釋放頭結點。

3、帶頭雙向循環鏈表的打印

void PrintList(ListNode* phead)//打印
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d<=>", cur->date);
        cur = cur->next;
    }
    printf("\n");
}

從頭結點的next開始，遍歷打印

4、動態開辟一個節點

ListNode* BuyNode(ListDateType x)//動態開辟一個節點
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        perror("BuyNode:\n");
        exit(-1);
    }
    newnode->date = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

將值放入這個節點，并將兩個指針置空

5、帶頭雙向循環鏈表的判空

bool ListEmpty(ListNode* phead)//判斷鏈表是否只有頭節點
{
    assert(phead);
    return phead->next == phead;
}

只有哨兵位這一個頭結點即為空

6、帶頭雙向循環鏈表的尾插、尾刪

void ListPushBack(ListNode* phead, ListDateType x)//尾插
{
    assert(phead);
    ListNode* tail = phead->prev;
    ListNode* newnode = BuyNode(x);
    newnode->next = phead;
    newnode->prev = tail;
    tail->next = newnode;
    phead->prev = newnode;
}
void ListPopback(ListNode* phead)//尾刪
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* tail = phead->prev;
    ListNode* prev = tail->prev;
    free(tail);
    prev->next = phead;
    phead->prev = prev;
}

注意尾刪前需要判空

7、帶頭雙向循環鏈表的頭插、頭刪

void ListPushFront(ListNode* phead, ListDateType x)//頭插
{
    assert(phead);
    ListNode* cur = phead->next;
    ListNode* newnode = BuyNode(x);
    newnode->next = cur;
    newnode->prev = phead;
    cur->prev = newnode;
    phead->next = newnode;
}
void ListPopFront(ListNode* phead)//頭刪
{
    assert(phead);
    assert(!ListEmpty(phead));
    ListNode* cur = phead->next;
    ListNode* next = cur->next;
    free(cur);
    phead->next = next;
    next->prev = phead;
}

注意頭刪前需要判空

8、帶頭雙向循環鏈表的長度

size_t ListSize(ListNode* phead)//有效節點個數
{
    assert(phead);
    ListNode* cur = phead->next;
    size_t count = 0;
    while (cur != phead)
    {
        cur = cur->next;
        ++count;
    }
    return count;
}

循環計數即可，哨兵位不算

9、帶頭雙向循環鏈表的查找、任意位置插入、刪除

ListNode* ListFind(ListNode* phead, ListDateType x)//查找（可用于修改）
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur!=phead)
    {
        if (cur->date == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void ListInsert(ListNode* pos, ListDateType x)//pos位置之前插入
{
    assert(pos);
    ListNode* newnode = BuyNode(x);
    ListNode* prev = pos->prev;
    prev->next = newnode;
    newnode->prev = prev;
    newnode->next = pos;
    pos->prev = newnode;
}
void ListErase(ListNode* pos)//刪除pos位置
{
    assert(pos);
    ListNode* prev = pos->prev;
    ListNode* next = pos->next;
    free(pos);
    prev->next = next;
    next->prev = prev;
}

查找：遍歷鏈表，返回第一個date==x的節點指針，查找通常配合下面兩個接口使用

任意位置插入、刪除：使用pos位置進行插入刪除操作。

頭插、頭刪、尾插、尾刪接口可以復用上面三個接口

原文鏈接：https://blog.csdn.net/gfdxx/article/details/126287813

欄目分類
最近更新