自学内容网 自学内容网
自学内容网 > 正文

【c语言数据结构】超详细！模拟实现双向链表(初始化、销毁、头删、尾删、头插、尾插、指定位置插入与删除、查找数据、判断链表是否为空)

🕗 发布于 2024-09-25 18:06 数据结构  c语言  链表  

特点：

  • 结构：指向前一结点指针+数据+指向后一结点指针
  • 由于循环，尾结点的下一结点next指向头结点（哨兵结点）
  • 空的双向链表只有自循环的哨兵结点（头结点） 

模拟实现双向链表

LIST.h

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

//定义双向链表结构
typedef int LTDataType;//链表数据类型
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;

//初始化
void LTInit(LTNode** pphead);
LTNode* LTInit2();

//销毁    链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead);
void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL

//打印链表
void LTPrint(LTNode* phead);

//尾插数据
//第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//我们通过传递的一级指针来找到头结点，就可以找到之后的节点了

//那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x);

//头插数据
void LTPushFront(LTNode* phead, LTDataType x);

//尾删数据
void LTPopBack(LTNode* phead);

//头删数据
void LTPopFront(LTNode* phead);

//判断链表是否为空
bool LTEmpty(LTNode* phead);

//查找数据
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);

//删除指定位置的节点
void LTIErase(LTNode* pos);

LIST.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"LIST.h"

//创建结点
LTNode* buyNode(LTDataType x) {
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode*));
if (newnode == NULL) {
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;//初步实现双头自循环的空链表
return newnode;
}
//初始化1 传参初始化
void LTInit(LTNode** pphead) {
//创建一个哨兵结点（头结点）
*pphead = buyNode(-1);
}
//初始化2 返回值初始化
LTNode* LTInit2() {
LTNode* phead = buyNode(-1);
return phead;
}


//销毁    链表的销毁是整个都销毁的
void LTDesTory(LTNode** pphead) {
//哨兵位不能先销毁！
assert(pphead && *pphead);
LTNode* pcur = (*pphead)->next;//从哨兵位的下一结点开始遍历销毁

while (pcur != (*pphead)) {
LTNode* Next = pcur->next;//创建pcur下一结点，方便遍历销毁
free(pcur);
pcur = Next;
}
//跳出循环，说明哨兵位之后的全销毁了
//现在释放销毁哨兵位
free(*pphead);
*pphead = pcur = NULL;
}

//初次错误示范！！
void LTDesToryError(LTNode** pphead) {
LTNode* pcur = (*pphead)->next;
LTNode* Next = pcur->next;

while (pcur!=*pphead) {
free(pcur);
pcur = Next;
Next = Next->next;
}
pcur = Next = NULL;
}


//void LTDesTory2(LTNode* phead);//传一级我们需要手动将plist置为NULL

//打印链表
void LTPrint(LTNode* phead) {
LTNode* pcur = phead->next;//记住第一个结点！！是哨兵位下一个结点！
while (pcur != phead) {
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}

//尾插数据
//第一个参数传一级还是二级，，要看pphead指向的节点会不会发生改变
//如果发生改变，那么pphead的改变要影响实参，传二级
//如果不发生改变，pphead不会影响实参，传一级
//我们通过传递的一级指针来找到头结点，就可以找到之后的节点了

//那么我们在插入新节点的时候，受到影响的节点有之前的尾节点和哨兵位以及新节点
void LTPushBack(LTNode* phead, LTDataType x) {
assert(phead);
//哨兵位 phead 新结点 newnode 尾结点pcur(phead->prev)
LTNode* pcur = phead->prev;
LTNode* newnode = buyNode(x);

//newnode的指针修改，prev指向上个尾节点，next指向哨兵位
newnode->prev = pcur;
newnode->next = phead;

//原先的尾节点next指针->哨兵位，现在next->newnode
//哨兵位的prev原本->尾节点,现在让prev->newnode
pcur->next = newnode;
phead->prev = newnode;
}

//头插数据
void LTPushFront(LTNode* phead, LTDataType x) {
assert(phead);
//哨兵位phead 新结点newnode 第一个结点 pcur(phead->next)
LTNode* newnode = buyNode(x);
LTNode* pcur = phead->next;

//插入newnode，prev指向哨兵位，next指向pcur
newnode->prev = phead;
newnode->next = pcur;

//哨兵位的next，原头结点的prev，分别指向newnode
phead->next = newnode;
pcur->prev = newnode;
}
//————————ERROR！！注意！！！删除要检查链表是否为空！！——————————
//判断链表是否为空
bool LTEmpty(LTNode* phead) {
assert(phead);
//error!!! return phead == NULL;不是判断哨兵位phead！！第一个结点是哨兵位下一结点！phead->next!
return phead->next == phead;//如果哨兵位next指向自己，说明是自循环的只有哨兵位的空链表！
}//链表为空，返回true
//尾删数据
void LTPopBack(LTNode* phead) {
assert(phead);//哨兵位不得为空
assert(!LTEmpty(phead));//链表不得为空
//哨兵位phead 尾结点 del(phead->prev) 尾结点前一结点 del->prev
LTNode* del = phead->next;

//删除尾结点 哨兵位的prev指向del->prev, 尾结点的前一结点的next->哨兵位
del->prev->next = phead;//注意这俩行代码不可调换！
phead->prev = del->prev;//先改了头结点的指向 del也会跟着改！


//删除完之后释放del
free(del);
del = NULL;
}

//头删数据
void LTPopFront(LTNode* phead) {
assert(phead);
assert(!LTEmpty(phead));

//哨兵位phead 要删除的第一个结点del(phead->next) 新的第一结点del->next
LTNode* del = phead->next;

//删除结点 哨兵位的next指向新第一结点 新的第一结点的prev指向哨兵位
del->next->prev = phead;
phead->next = del->next;


//释放del
free(del);
del = NULL;
}


//查找数据
//遍历链表，直至再次遇到哨兵位（找一圈了没找到就是没有）
LTNode* LTFind(LTNode* phead, LTDataType x) {
LTNode* pcur = phead->next;//记住从第一个结点！不是phead！

while (pcur != phead) {
//找到了
if (pcur->data == x) {
return pcur;
}
pcur = pcur->next;
}
//遍历循环找了一圈，没找到
return NULL;
}
//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x) {
//创建一个新结点
LTNode* newnode = buyNode(x);

//pos newnode pos->next
//先安newnode
newnode->next = pos->next;
newnode->prev = pos;

//先连接pos后面的，再连pos
pos->next->prev = newnode;
pos->next = newnode;
}

//删除指定位置的节点
void LTIErase(LTNode* pos) {
assert(pos);//传过来的位置不为空

/*
pos前面的节点pos->prev
pos后面的节点pos->next

删除pos影响这两个节点

pos前面指针的节点的next指针->Pos后面的节点
pos后面的节点的prev指针就->pos前面的节点*/

//pos->prev pos pos->next
pos->prev->next = pos->next;
pos->next->prev = pos->prev;

free(pos);
pos = NULL;
}

 我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=3bmyejsi48e88


原文地址：https://blog.csdn.net/2301_80038570/article/details/142469755

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024