当前位置：首页 > article >正文

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

article 2024/12/24 0:57:25

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

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