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

数据结构顺序表和链表

article 2024/12/22 5:28:26

1.线性表

线性表是n个具有相同特性的数据元素的有限序列，线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表，链表，栈，队列，字符串
线性表在逻辑上是线性结构的，也就是说连续的一条直线我，但是在物理结构上并不一定是连续的，线性表在物理上存储是我，通常以数组和链式结构的形式存储
在这里插入图片描述

2.顺序表

2.1概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储，在数组上完成数据的增删查改
顺序表一般可以分为：
1.静态顺序表：使用定长数组存储元素
在这里插入图片描述

2.动态顺序表：使用动态开辟的数组存储
在这里插入图片描述

2.2接口实现

静态顺序表只适用于确定知道需要存多少数据的场景，静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用，所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小

动态顺序表实现

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟的数组
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;
// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x); 
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

2.3数组相关的题

1.原地移除数组中所有的元素val,要求时间复杂度为O（N），空间复杂度为O（1）
2.删除排序数组中的重复项
3.合并两个有序数组

2.4顺序表的问题及思考

问题：
1.中间/头部的插入删除，时间复杂度为O（N）
解决：

  • 使用链表结构（针对中间/头部操作频繁的情况）：链表是一种动态数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针（单链表）或者同时包含指向前一个节点和下一个节点的指针（双链表）。在链表中进行中间或头部的插入删除操作时，只需要修改相关节点的指针，时间复杂度为O(1)。
  • 使用索引结构辅助（针对仍需使用数组且中间/头部操作有优化空间的情况）：如果使用数组来存储数据，可以额外维护一个索引结构。例如，对于中间插入操作，可以使用二叉搜索树或者跳表等数据结构来记录元素在数组中的位置信息。当需要在中间插入元素时，通过索引结构快速定位到插入位置，然后进行插入操作。虽然插入数组元素本身仍然可能需要移动后续元素，但通过索引结构可以减少查找插入位置的时间。

2.增容需要申请新空间，拷贝数据，释放旧空间，会有不小的消耗
解决：

  • 预分配策略优化：不再简单地按照固定倍数（如2倍）进行增容，而是根据数据的增长趋势进行预分配。可以通过分析历史数据的插入模式，例如，如果发现数据是缓慢增长的，可以采用较小的增量进行预分配。如果数据增长是阶段性爆发式的，可以在爆发增长前进行较大幅度的预分配。
  • 内存池技术：建立一个内存池，预先申请一块较大的内存空间。当需要增容时，从内存池中获取已经申请好的内存块，而不是每次都向操作系统重新申请。这样可以减少申请和释放内存的开销。

3.增容一般是呈2倍增长，势必会有一定的空间浪费，例如当前容量为100，满了以后增容到200，在插入5个数据，后面没有数据插入了，那么就浪费了95个数据空间
解决：

  • 动态调整增容策略：根据实际使用情况动态调整增容的比例。例如，可以设置一个阈值，当剩余空间低于这个阈值时才进行增容，并且增容的幅度可以根据剩余空间和历史插入数据的速度等因素来确定。
  • 使用紧凑型数据结构（在合适的场景下）：有些数据结构可以在一定程度上避免空间浪费。例如，对于稀疏矩阵，可以使用压缩存储的方式，如三元组顺序表或者十字链表等，而不是使用普通的二维数组来存储，这样可以大大减少空间浪费。

3.链表

3.1链表的概念及结构

概念：链表是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的
在这里插入图片描述
现实中 数据结构中
在这里插入图片描述

3.2链表的分类

实际中链表的结构非常多样，以下情况组合起来就有八种链表结构
1.单向或者双向
在这里插入图片描述
2.带头或者不带头
在这里插入图片描述
3.循环或者非循环
在这里插入图片描述
虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：
在这里插入图片描述

1.无头单向非循环链表：结构简单，一般不会单独用来存数据，实际中更多是作为其他数据结构的子结构，如哈希桶，图的链接表等，另外这种结构在笔试面试中很多
2.带头双向循环链表，结构最复杂，一般用在单独存储数据，实际中使用的链表数据结构，都会是带头双向循环链表，另外这个结构复杂，但是使用代码实现以后会发现会带来很多优势，实现反而简单

3.3链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

3.4链表题

1.删除链表中等于给定值v的所有节点
2.反转一个单链表
3.给定一个带头节点head的非空单链表，返回链表的中间节点，如果有两个中间节点，则返回第二个中间节点
4.将两个有序链表合并为一个新的有序链表并返回，新链表是通过拼接给定的两个链表的所有节点组成
5.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的节点排在大于或等于x的节点之前
6.链表的回文结构
7.输入两个链表，找出它们的第一个公共节点
在这里插入图片描述
8.给定一个链表，判断链表中是否有环

思路：快慢指针，慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环，则一定会在环中相遇，否则快指针率先走到链表末尾
拓展

  • 为什么快指针每次走两步，慢指针走一步可以
    假设链表带环，两个指针最后都会进入环，快指针先进入，慢指针后进入，慢指针进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度，此时，两个指针每移动一次我，之间距离缩小一步，不会出现每次刚好套圈的情况，因此，在慢指针走到一圈，快指针肯定可以追上慢指针，即相遇
  • 快指针三步，4步，n步可以吗
    在这里插入图片描述

9.给定一个链表，返回链表开始入环的第一个节点，如果链表无环，则返回NULL

结论：让一个指针从链表开始位置遍历链表，同时让一个指针从判环时相遇点的位置开始绕环运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇，证明

证明:
在这里插入图片描述

10.给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点,要求返回这个链表的深度拷贝。

11.其他，LeecodeOJ+牛客OJ

3.5双向链表的实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* next;
 struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);

4.顺序表和链表的区别

在这里插入图片描述

备注：缓存利用率参考存储体系结构以及局部原理性
在这里插入图片描述
与程序员相关的CPU缓存知识


http://www.kler.cn/a/446068.html

相关文章：

  • 基于层次化设计方法，设计一个16位二进制全加器
  • 不会心理描写，神态描写怎么办？
  • 二八(vue2-04)、scoped、data函数、父子通信、props校验、非父子通信(EventBus、provideinject)、v-model进阶
  • 机器学习中做时间序列模型考虑把时间作为特征分析
  • 关于如何做技术文档
  • MySQL 的事务与锁机制详解
  • 【21天学习AI底层概念】day8 什么是类意识？
  • Linux 下的 GPT 和 MBR 分区表详解
  • Qt Quick：CheckBox 复选框
  • 无人机+自组网+飞手：低空集群飞行技术详解
  • Angular学习路线图
  • skyler实战渗透笔记—Kioptrix-1
  • 【算法】栈
  • 配置TypeScript：tsconfig.json详解
  • Ubuntu上如何部署Nginx？
  • 中国人工智能学会技术白皮书
  • FPGA设计-使用 lspci 和 setpci 调试xilinx的PCIe 问题
  • 【libuv】Fargo信令1：client发connect消息给到server
  • 利用DnslogSqlinj工具DNSlog注入
  • 指令-v-for的key
  • 《 OpenCV 环境搭建》
  • 笔记本电脑需要一直插着电源吗？电脑一直充电的利弊介绍
  • 亚矩阵云手机
  • 使用ioredis在Node.js中操作Redis数据结构的详细指南
  • [数据结构] LRU Cache | ListMap 实现
  • JAVA队列每次添加需要新实例才能独立更新