AI 助理
备案控制台
开发者社区 云计算 文章 正文

数据结构——双向循环链表

2022-12-09 126
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 笔记

结构体的建立

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<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
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的人置空，保持接口的一致性，这


顺序表和链表的区别

1.png

顺序表优点：1.尾插尾删的效率很高

                     2.可以随机访问（通过下标），链表需要遍历

                     3.和链表相比cpu高速缓存面中率很高

2.png3.png

寄存器相当于锅 ，如有数组{1，2，3，4}，这四个元素是存在主存里面的，数据结构是在主存里面管理我们的数据，链表也一样（堆是一个虚拟的内存的划分）


越往上速度越快，成本更高 ，L1,L2,L3被称为CPU的高速缓存


代码编译好了就是指令，通过CPU去运行指令，CPU访问通过访问内存数据运行指令，


CPU执行指令，不会直接访问内存


1.先看数据在不在三级缓存，在（命中），就直接访问


2.不在（不命中），先加载到缓存，再访问


顺序表的缺点：1.头部和中部的插入删除效率低——O(N)


                        2.扩容（动态开辟空间）——性能消耗，有一定空间浪费


链表的优点：1.任意位置插入删除效率很高O(1)


                     2.按需申请释放（不存在空间浪费）


链表的缺点：1.不支持随机访问（现实中随机访问很重要）


文章标签：
缓存
关键词：
数据结构链表
数据结构双向循环链表
jefcfxcg6xxjg
目录
相关文章
XIAZHI
|
1月前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
55 4
龙大吉
|
24天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
45 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
86 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
27 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
38 2
XIAZHI
|
1月前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
48 0
小强在此
|
2月前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
29 7
GuGuStudy
|
2月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密（附带练习唔）pro
GuGuStudy
28 3
java冯坚持
|
2月前
|
算法 Java
数据结构与算法学习五：双链表的增、删、改、查
双链表的增、删、改、查操作及其Java实现，并通过实例演示了双向链表的优势和应用。
java冯坚持
21 0
数据结构与算法学习五：双链表的增、删、改、查
努力学习的小廉
|
2月前
【数据结构】——双向链表详细理解和实现
【数据结构】——双向链表详细理解和实现
努力学习的小廉
37 2