-
数据结构——双向循环链表
目录
结构体的建立
- typedef int LTDatatype;
- typedef struct ListNode
- {
- struct ListNode* next;
- struct ListNode* prev;
- LTDatatype data;
- }LTNode;
初始化
- /*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
- LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
- LTNode* ListInit()
- {
- LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
- if (guard == NULL)
- {
- return NULL;
- }
- guard->next = guard;
- guard->prev = guard;
- return guard;
- }
创建节点
- LTNode* BuyNode(LTDatatype x)
- {
- LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
- if (guard == NULL)
- {
- return NULL;
- }
- guard->next = NULL;
- guard->data = x;
- guard->prev = NULL;
- return guard;
- }
头插节点
- void ListPushFront(LTNode* pphead, LTDatatype x)
- {
- LTNode* newnode = BuyNode(x);
- LTNode* next = pphead->next;
- newnode->next = next;
- next->prev = newnode;
- newnode->prev = pphead;
- pphead->next = newnode;
- }
尾插节点
- void ListPushBack(LTNode* pphead, LTDatatype x)
- {
- assert(pphead);//pphead不可能为空
- LTNode* newnode = BuyNode(x);
- LTNode* tail = pphead->prev;//先找到尾
- tail->next = newnode;//开始尾插
- newnode->prev = tail;
- newnode->next = pphead;
- pphead->prev =newnode;
- }//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead
头删节点
- void ListPopFront(LTNode* pphead)
- {
- LTNode* next = pphead->next;
- pphead->next = next->next;
- next->next->prev = pphead;
- free(next);
- }
尾删节点
- void ListPopBack(LTNode* pphead)
- {
- assert(pphead);
- assert(!ListEmpty(pphead));//判断是否为空
- LTNode* tail1 = pphead->prev;
- LTNode* tail2 = tail1->prev;
- free(tail1);
- tail1 = NULL;
- tail2->next = pphead;
- pphead->prev = tail2;
- }
- bool ListEmpty(LTNode* pphead)
- {
- assert(pphead);
- return pphead->next == pphead;//检测是否只剩头节点
- }
节点查找
- LTNode* ListFind(LTNode* pphead,LTDatatype x)
- {
- assert(pphead);
- size_t n = 0;
- LTNode* cur = pphead->next;
- while (cur != pphead)
- {
- if (cur->data == x)
- {
- return cur;
- }
- }
- }
节点前插入
- void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
- {
- assert(pos);
- LTNode* prev = pos->prev;
- LTNode* newnode = BuyNode(x);
- prev->next = newnode;
- newnode->prev = prev;
- newnode->next = pos;
- pos->prev = newnode;
- }
节点删除
- void ListErase(LTNode* pos)
- {
- assert(pos);
- LTNode* prev = pos->prev;
- LTNode* next = pos->next;
- prev->next = next;
- next->prev = prev;
- free(pos);
- pos = NULL;
- }
销毁链表
- void ListDestory(LTNode* pphead)//传一级，二级都可以
- {
- assert(pphead);
- //1.先释放带数字的节点，最后释放头哨兵
- LTNode* cur = pphead->next;
- while (cur != pphead)
- {
- LTNode* next = cur->next;
- free(cur);
- cur = next;
- }
- free(pphead);
- pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
- }
- //建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这里最后回到主函数把plist=NULL;即可
Dlist.h
- #pragma once
- #include
- #include
- #include
- #include
- #include
- typedef int LTDatatype;
- typedef struct ListNode
- {
- struct ListNode* next;
- struct ListNode* prev;
- LTDatatype data;
- }LTNode;
- /*void ListInit(LTNode**pphead);*///初始化，初始化要传指针，要建立一个哨兵节点，要实质上把plist改变
- LTNode* ListInit();//初始化,也可以不用二级，用一个返回值就行
- void ListPushBack(LTNode* pphead,LTDatatype x);//不需要传地址，因为再怎么改变都不会改变哨兵位的头，改的是哨兵位的指向
- void ListPushFront(LTNode* pphead, LTDatatype x);
- void ListPopBack(LTNode* pphead);
- void ListPrint(LTNode* pphead);
- void ListPopFront(LTNode* pphead);
- bool ListEmpty(LTNode* pphead);
- size_t ListSize(LTNode* pphead);
- LTNode* ListFind(LTNode* pphead, LTDatatype x);
- void ListInsert(LTNode* pos, LTDatatype x);
- void ListErase(LTNode* pos);
- void ListDestory(LTNode* pphead);
Dlist.c
- #define _CRT_SECURE_NO_WARNINGS
- #include"Dlist.h"
- LTNode* ListInit()
- {
- LTNode* guard= (LTNode*)malloc(sizeof(LTNode));
- if (guard == NULL)
- {
- return NULL;
- }
- guard->next = guard;
- guard->prev = guard;
- return guard;
- }
- LTNode* BuyNode(LTDatatype x)
- {
- LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
- if (guard == NULL)
- {
- return NULL;
- }
- guard->next = NULL;
- guard->data = x;
- guard->prev = NULL;
- return guard;
- }
- void ListPrint(LTNode* pphead)
- {
- assert(pphead);
- printf("guard<=>");
- LTNode* cur = pphead->next;
- while (cur!= pphead)
- {
- printf("%d<=>", cur->data);
- cur= cur->next;
- }
- printf("\n");
- }
- void ListPushBack(LTNode* pphead, LTDatatype x)
- {
- assert(pphead);//pphead不可能为空
- LTNode* newnode = BuyNode(x);
- LTNode* tail = pphead->prev;//先找到尾
- tail->next = newnode;//开始尾插
- newnode->prev = tail;
- newnode->next = pphead;
- pphead->prev =newnode;
- }//这种写法即使pphead是NULL，依然能插入，因为通过tail找到了pphead
- void ListPushFront(LTNode* pphead, LTDatatype x)
- {
- LTNode* newnode = BuyNode(x);
- LTNode* next = pphead->next;
- newnode->next = next;
- next->prev = newnode;
- newnode->prev = pphead;
- pphead->next = newnode;
- }
- void ListPopBack(LTNode* pphead)
- {
- assert(pphead);
- assert(!ListEmpty(pphead));//判断是否为空
- LTNode* tail1 = pphead->prev;
- LTNode* tail2 = tail1->prev;
- free(tail1);
- tail1 = NULL;
- tail2->next = pphead;
- pphead->prev = tail2;
- }
- bool ListEmpty(LTNode* pphead)
- {
- assert(pphead);
- return pphead->next == pphead;//检测是否只剩头节点
- }
- void ListPopFront(LTNode* pphead)
- {
- LTNode* next = pphead->next;
- pphead->next = next->next;
- next->next->prev = pphead;
- free(next);
- }
- size_t ListSize(LTNode* pphead)
- {
- size_t n = 0;
- LTNode* cur = pphead->next;
- while (cur != pphead)
- {
- ++n;
- cur = cur->next;
- }
- return n;
- }
- LTNode* ListFind(LTNode* pphead,LTDatatype x)
- {
- assert(pphead);
- size_t n = 0;
- LTNode* cur = pphead->next;
- while (cur != pphead)
- {
- if (cur->data == x)
- {
- return cur;
- }
- }
- }
- void ListInsert(LTNode* pos, LTDatatype x)//在pos之前插入,若在pphead前插入，实际会变成尾插
- {
- assert(pos);
- LTNode* prev = pos->prev;
- LTNode* newnode = BuyNode(x);
- prev->next = newnode;
- newnode->prev = prev;
- newnode->next = pos;
- pos->prev = newnode;
- }
- void ListErase(LTNode* pos)
- {
- assert(pos);
- LTNode* prev = pos->prev;
- LTNode* next = pos->next;
- prev->next = next;
- next->prev = prev;
- free(pos);
- pos = NULL;
- }
- void ListDestory(LTNode* pphead)//传一级，二级都可以
- {
- assert(pphead);
- //1.先释放带数字的节点，最后释放头哨兵
- LTNode* cur = pphead->next;
- while (cur != pphead)
- {
- LTNode* next = cur->next;
- free(cur);
- cur = next;
- }
- free(pphead);
- pphead = NULL;//如果传一级指针，这里的置空不起作用，若想起作用，要传二级指针
- }
- //建议：使用一级指针，然后让调用ListDestory的人置空，保持接口的一致性，这
顺序表和链表的区别
不同点 顺序表 链表 存储空间上 物理上一定连续 逻辑上连续，但物理上不一定
连续随机访问 支持O(1) 不支持：O(N) 任意位置插入或者删除
元素可能需要搬移元素，效率低
O(N)只需修改指针指向 插入 动态顺序表，空间不够时需要
扩容没有容量的概念 应用场景 元素高效存储+频繁访问 任意位置插入和删除频繁 缓存利用率 高 低 顺序表优点：1.尾插尾删的效率很高
2.可以随机访问（通过下标），链表需要遍历
3.和链表相比cpu高速缓存面中率很高
寄存器相当于锅 ，如有数组{1，2，3，4}，这四个元素是存在主存里面的，数据结构是在主存里面管理我们的数据，链表也一样（堆是一个虚拟的内存的划分）
越往上速度越快，成本更高 ，L1,L2,L3被称为CPU的高速缓存
代码编译好了就是指令，通过CPU去运行指令，CPU访问通过访问内存数据运行指令，
CPU执行指令，不会直接访问内存
1.先看数据在不在三级缓存，在（命中），就直接访问
2.不在（不命中），先加载到缓存，再访问
顺序表的缺点：1.头部和中部的插入删除效率低——O(N)
2.扩容（动态开辟空间）——性能消耗，有一定空间浪费
链表的优点：1.任意位置插入删除效率很高O(1)
2.按需申请释放（不存在空间浪费）
链表的缺点：1.不支持随机访问（现实中随机访问很重要）
-
相关阅读:
反射技巧让你的性能提升N倍
深度学习_6_实战_点集最优直线解_代码解析
数据结构（一）线性表（模板实现）
【洛谷】P5149 会议座位
导数差分近似公式总结
高可用架构，去中心化有多重要？
MySQL查询数据库响应时长的方法
VLAN笔记
系统架构设计师（第二版）学习笔记----层次式架构设计理论与实践
Typora使用教程
- 原文地址：https://blog.csdn.net/weixin_49449676/article/details/126146839
