C++實現帶頭雙向迴圈連結串列的範例詳解

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

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;
}

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

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

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

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

void ListPushBack(ListNode* phead, ListDataType 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;
}

void ListPushFront(ListNode* phead, ListDataType 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;
}

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

ListNode* ListFind(ListNode* phead, ListDataType x)//查詢（可用於修改）
{
    assert(phead);
    ListNode* cur = phead->next;
    while (cur!=phead)
    {
        if (cur->data == x)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
void ListInsert(ListNode* pos, ListDataType 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;
}