数据结构:双向带头循环链表的增删查改

发布于:2024-12-20 ⋅ 阅读:(14) ⋅ 点赞:(0)

 先构建一个结构体,对其链表进行初始化,尾插,尾删,头插,头删,查找,修改,中间插入,删除等相关操作。

List.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
//创建一个结点
typedef struct SListNode
{
    //int data;
    LTDataType data;
    struct SListNode* next;//创建一个指针存下一个结点的地址
    struct SListNode* prev;
}LTNode;


//初始化
LTNode* ListInit();
//void ListInit(LTNode** phead);

LTNode* BuyListNode(LTDataType x);

//尾插
void ListPushBack(LTNode* phead, LTDataType x);

//尾删
void ListPopBack(LTNode* phead);

void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);

LTNode* ListFind(LTNode* phead, LTDataType x);//找到了就返回链表的指针

//在pos前面插入x
void ListInsert(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos);

void ListClear(LTNode* phead);

void ListDestory(LTNode** pphead);

void ListPrint(LTNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
LTNode* ListInit()
{
    //带哨兵位的头结点
    //不存储有效数字,啥都不存
    LTNode*  phead = (LTNode*)malloc(sizeof(LTNode));
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

//void ListInit(LTNode** pphead)
//{
//    //带哨兵位的头结点
//    //不存储有效数字,啥都不存
//    *pphead = BuyListNode(0);
//    (*pphead)->next = *pphead;
//    (*pphead)->prev = *pphead;
//}

LTNode* BuyListNode( LTDataType x)
{
    LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
    newnode->data = x;
    newnode->prev = NULL;
    newnode->next = NULL;
    return newnode;
}

void ListPushBack(LTNode* phead, LTDataType x)
{
    //assert(phead);
    //LTNode* tail = phead->prev;
    //LTNode* newnode = BuyListNode(x);
     phead   tail  newnode
    //tail->next = newnode;
    //newnode->next = phead;
    //phead->prev = newnode;
    ListInsert(phead,x );
}

//void ListPopBack(LTNode* phead)
//{
//    assert(phead);
//    assert(phead->next != phead);
//    LTNode* tail = phead->prev;
//    LTNode* tailPrev = tail->prev;
//    tailPrev->next = phead;
//    phead->prev = tailPrev;
//    //tailPrev->next = phead;             // 将尾节点的前一个节点的next指向头节点
//    //phead->prev = tailPrev;             // 将头节点的prev指向新的尾节点
//    free(tail);
//    tail = NULL;
//    //为什么不是phead->prev = tailPrev->next; 而是phead->prev = tailPrev,
//    // 应该是尾指向头才对啊
//    //在双向循环链表中,尾节点的 next 始终指向头节点 phead,而头节点的 prev 始终指向尾节点。
//    //因此,在删除尾节点时,关键是要确保头节点的 prev 被正确地更新为新的尾节点(即 tailPrev)。
//    //那么我们应该如何理解这两个不同的表达式呢?
//    //双向循环链表的结构:
//
//    //头节点 phead 的 next 指向第一个元素,prev 指向尾节点。
//    //尾节点的 prev 指向倒数第二个元素,next 指向头节点。
//    //在这种情况下,尾节点总是指向头节点,而头节点的 prev 始终指向尾节点。
//
//    //删除尾节点的操作:
//
//    //首先,获得尾节点 tail,并且获得尾节点的前驱节点 tailPrev。
//    //然后,我们需要做的是:
//    //将尾节点前驱节点 tailPrev 的 next 设置为 phead,
//    //即让 tailPrev 的 next 指向头节点,保持链表的循环结构。
//    //更新头节点 phead 的 prev 为 tailPrev,让 phead 的 prev 指向新的尾节点。
//    
//    //为什么不能是 phead->prev = tailPrev->next:
//    //tailPrev->next 是 尾节点的 next,它指向头节点 phead。
//    //如果你将 phead->prev 设置为 tailPrev->next,
//    //这就意味着 phead->prev 会被设置为 phead,从而破坏链表的双向连接关系。
//    //你应该将 phead->prev 设置为 tailPrev,让头节点的 prev 指向新的尾节点。
//}
//


void ListPopBack(LTNode* phead)
{
    //assert(phead);
    //assert(phead->next != phead);
    //LTNode* tail = phead->prev;
    //LTNode* tailPrev = tail->prev;
    //tailPrev->next = phead;
    //phead->prev = tailPrev;
    tailPrev->next = phead;             // 将尾节点的前一个节点的next指向头节点
    phead->prev = tailPrev;             // 将头节点的prev指向新的尾节点
    //free(tail);
    //tail = NULL;

    ListErase(phead->prev);
}

void ListPrint(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void ListPushFront(LTNode* phead, LTDataType x)
{
    /*assert(phead);
    LTNode* first = phead->next;
    LTNode* newnode = BuyListNode(x);

    phead->next = newnode;
    newnode->prev = phead;
    newnode->next = first;
    first->prev = newnode;*/
    ListInsert(phead->next, x);

}


void ListPopFront(LTNode* phead)
{
    /*assert(phead);
    assert(phead->next != phead);
    LTNode* first = phead->next;
    LTNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first);
    first = NULL;*/
    ListErase(phead->next);
}

LTNode* ListFind(LTNode* phead, LTDataType x)
{
    assert(phead);
    assert(phead->next != phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        if (cur->data == x)
        {
            return cur;;
        }
        cur = cur->next;
    }
    return NULL;
}


void ListInsert(LTNode* pos, LTDataType x)
{
    assert(pos);
    LTNode* newnode = BuyListNode(x);
    LTNode* posPrev = pos->prev;
    pos->prev = newnode;
    newnode->next = pos;
    posPrev->next = newnode;
    newnode->prev = posPrev;
}

void ListErase(LTNode* pos)
{
    assert(pos);

    LTNode* posPrev = pos->prev;
    LTNode* posNext = pos->next;
    posPrev->next = posNext;
    posNext->prev = posPrev;
    free(pos);
}

void ListClear(LTNode* phead)
{
    assert(phead);
    LTNode* cur = phead->next;
    while (cur != phead)
    {
        LTNode* next = cur->next;
        free(cur);
        cur = next;
    }
}

void ListDestory(LTNode** pphead)
{
    assert(*pphead);
    //销毁
    ListClear(*pphead);
    free(*pphead);
    *pphead = NULL;
}
test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "SList.h"
TestList()
{
    //LTNode* phead = NULL;
    //ListInit(&phead);
    LTNode* phead = ListInit();
    ListPushBack(phead, 1);
    ListPushBack(phead, 2);
    ListPushBack(phead, 3);
    ListPushBack(phead, 4);
    ListPrint(phead);

    ListPopBack(phead);
    ListPopBack(phead);
    ListPopBack(phead);
    ListPrint(phead);

    ListPushFront(phead, 1);
    ListPushFront(phead, 2);
    ListPushFront(phead, 3);
    ListPushFront(phead, 4);
    ListPrint(phead);

    ListPopFront(phead);
    //ListPopFront(phead);
    //ListPopFront(phead);
    
    ListPrint(phead);

    LTNode* pos = ListFind(phead, 3);
    pos->data = 300;
    ListInsert( pos, 30);
    ListPrint(phead);

    pos = ListFind(phead, 2);
    ListErase(pos);
    ListPrint(phead);
    ListDestory(&phead);
}

int main()
{
    TestList();
    return 0;
}

先尾插 1 2 3 4,然后尾删三个数,头插 4个数,头删两个数,找到3将其改成300,并在300前面插入30,最后删除2