2024-09-26 11:18:04
浏览数 (3)
特点：
- 结构：指向前一结点指针 数据 指向后一结点指针
- 由于循环，尾结点的下一结点next指向头结点（哨兵结点）
- 空的双向链表只有自循环的哨兵结点（头结点）
模拟实现双向链表
LIST.h
代码语言：javascript
复制#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
代码语言：javascript
复制#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;
}
