数据结构第1章 线性表

2023-12-28 18:57:37

名人说:莫听穿林打叶声,何妨吟啸且徐行。—— 苏轼《定风波·莫听穿林打叶声》
本篇笔记整理:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊)

0、思维导图

在这里插入图片描述

线性表

线性表是由相同类型的数据元素构成的有序序列

特点:

  • 有序性:元素之间是有序排列的。
  • 元素类型相同:所有元素类型必须相同

线性表可以用数学公式表示为: L = ( a 1 , a 2 , . . . , a n ) L = (a_1, a_2, ..., a_n) L=(a1?,a2?,...,an?),其中 a i a_i ai? 是表中的第 i i i 个元素。
根据使用的存储结构不同,可以将线性表分为顺序表链表

1、顺序存储

1)顺序表

在这里插入图片描述
在顺序表中,数据元素存储在连续的存储单元中。顺序表的特点包括:

  • 连续存储:所有元素在内存中占据连续的位置。
  • 随机访问:可以直接通过索引快速访问任何一个元素。
  • 存储密度高:不需要额外的存储空间来存储节点间的关系。

顺序表的表示可以是: [ a 1 , a 2 , . . . , a n ] [a_1, a_2, ..., a_n] [a1?,a2?,...,an?],其中元素的物理存储顺序与逻辑顺序相同

2)顺序表的分类

顺序表分为静态顺序表和动态顺序表。

  • 静态顺序表:使用定长数组存储元素。(顺序表大小固定)
    特点:

    1. 固定大小:创建后最大容量固定。
    2. 连续存储:元素在内存中连续存储。
    3. 效率高:内存分配和管理相对简单,访问元素的时间复杂度为 (O(1))。
    4. 空间限制:不够灵活,一旦分配的空间不足或过多,都会产生问题:不足时无法添加更多的元素,过多时会造成内存浪费。
  • 动态顺序表:使用动态开辟的数组存储元素。(可以动态地调整顺序表的大小)
    特点:

    1. 动态扩容:当元素数量超过当前容量时,动态顺序表可以扩大其存储空间来容纳更多元素。
    2. 空间灵活:动态顺序表能更有效地利用内存,它能根据需要调整存储容量。
    3. 效率问题:普通操作(如访问特定元素)仍然保持 (O(1)) 的时间复杂度,但插入和删除操作(尤其是在表头或中间)可能由于动态扩容而导致额外的开销。

2、链式存储

链表 (Linked List)

在这里插入图片描述

链表也是线性表的一种实现方式,但其存储方式与顺序表不同。链表中的元素在内存中不一定连续存储每个元素节点通常包含两部分:一部分存储数据元素,另一部分存储指向下一个元素的指针(或引用)。

在这里插入图片描述

特点:

  • 非连续存储:元素可以分散在内存的任何地方,节点之间通过指针连接。
  • 动态大小:链表的大小可以在运行时动态变化,易于插入和删除操作。
  • 存储开销:每个元素节点需要额外存储指向下一个节点的指针,因此相比顺序表有更高的存储开销。

简单表示: a 1 → a 2 → . . . → a n a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_n a1?a2?...an?,其中每个箭头代表一个指向下一个节点的指针。

1)单链表

①概念

单链表 (Singly Linked List)

单链表是一种基础的数据结构,由一系列节点(Node)组成,每个节点包含两部分:一部分用于存储数据(数据域),另一部分用于存储指向下一个节点的指针(指针域)。

②特点

  1. 线性结构:单链表是一种线性结构,其中的元素(节点)按照序列排列。
  2. 动态大小:与数组不同,单链表的大小是动态的,可以在运行时添加或删除节点。
  3. 高效的插入和删除:在已知节点的情况下,单链表可以在 O ( 1 ) O(1) O(1) 时间复杂度内进行节点的插入和删除操作。
  4. 顺序访问:访问单链表中的元素需要从表头开始,按顺序遍历,因此访问任意位置的元素的时间复杂度为 O ( n ) O(n) O(n)
  5. 内存利用:每个节点只存储一个指向下一个节点的指针,相较于双链表,它节省了内存空间。

③节点结构
单链表的节点结构可以用以下 C 语言结构体表示:

typedef struct Node {
    int data; // 数据域
    struct Node* next; // 指针域,指向下一个节点
} Node;

在这里插入图片描述

单链表通常有一个头指针(head),指向链表的第一个节点。如果链表为空,则头指针为 NULL。单链表的简单表示如下:

head → a 1 → a 2 → . . . → a n → NULL \text{head} \rightarrow a_1 \rightarrow a_2 \rightarrow ... \rightarrow a_n \rightarrow \text{NULL} heada1?a2?...an?NULL

在这里,每个箭头表示一个节点指向下一个节点的指针。由于单链表的节点只包含指向下一个节点的指针,因此它只能从头部开始按顺序遍历。

④单链表的常见类型

  • 循环

在这里插入图片描述

  • 不循环

    在这里插入图片描述

2)双链表

①双链表的概念理解

双链表 (Doubly Linked List)

双链表是链表的一种形式,在双链表中,每个节点不仅包含指向下一个节点的指针,还包含指向前一个节点的指针。这种结构使得双链表具有以下特点:

  1. 双向遍历:可以从表头到表尾,也可以从表尾到表头进行遍历。
  2. 插入和删除效率高:相比单链表,双链表可以更方便地进行节点的插入和删除,因为可以直接访问前驱和后继节点。
  3. 额外的内存开销:每个节点需要额外存储一个指向前驱节点的指针,因此相比单链表,双链表占用更多的内存空间。
  4. 更灵活的操作:由于可以直接访问任一节点的前驱和后继,双链表在某些操作上更加灵活,比如在双向遍历和逆序输出等场景中表现更优。

②双链表的节点结构

双链表的节点结构通常包含三个部分:数据域(存储数据)、前驱指针(指向前一个节点)和后继指针(指向下一个节点)。
在这里插入图片描述

③双链表的简单表示

a 1 ? a 2 ? . . . ? a n a_1 \leftrightarrows a_2 \leftrightarrows ... \leftrightarrows a_n a1??a2??...?an?

其中,每个双箭头 ? \leftrightarrows ? 表示节点间的双向连接。

④双链表的常见类型

  • 循环(双循环链表)

    在这里插入图片描述

  • 不循环(非循环双链表)

    在这里插入图片描述

3)头节点和首元节点

①头节点

1??头节点的位置
头节点一般位于第一个元素之前

2??头节点的特点
头节点的next指针域指向首元节点,数据域一般为空,或者存储的是链表的长度

注?:头节点不是链表必要要素,但头指针是链表的必要元素,无论链表是否为空,头指针均不为空,因为没有头指针,我们就没有办法知道链表的起始位置。

3??带头节点的作用与好处

  • 可以简化链表的插入和删除操作,不需要对第一个节点和最后一个节点进行特殊处理 。
  • 可以避免空链表的出现,因为头结点是链表的标志,只要链表存在,头结点就不为空。
  • 获取链表的长度方便,只需要遍历从头结点开始的所有结点即可 。
  • 可以实现一些特殊的功能,比如循环链表,只需要让头结点的指针域指向自己或者第一个结点即可。

②首元结点

  • 链表的第一个元素结点(有实在意义的结点)

3、顺序表 vs 链表

1)顺序表 胜

①针对情况

选择顺序存储结构存储元素的情况一般为:

  • 元素个数固定
  • 需频繁地随机访问任意位置的元素

②优缺点

1??优点

  • 存储密度高,每个元素只需要存储数据本身,不需要额外的指针域。
  • 存取速度快,可以通过下标直接访问任意位置的元素,时间复杂度为O(1)。

2??缺点

  • 存储空间不灵活,需要提前分配一块连续的空间,如果空间不够或者过多,都会造成空间浪费或者溢出。
  • 插入和删除操作复杂,需要移动大量的元素,时间复杂度为O(n)。

2)链表 胜

①针对情况

选择链式存储结构存储元素的情况一般为:

  • 元素个数是动态变化的

  • 需要频繁地在任意位置插入或删除元素

②优缺点

1??优点

  • 存储空间灵活,每个元素可以动态分配空间,不需要提前预留空间。
  • 插入和删除操作简单,只需要修改相邻元素的指针域,时间复杂度为O(1)。

2??缺点

  • 存储密度低,每个元素除了存储数据本身,还需要额外的指针域。
  • 存取速度慢,不能直接访问任意位置的元素,需要从头结点开始遍历链表,时间复杂度为O(n)。

3)表格对比

在这里插入图片描述

4、伪链表

一种类似于链表的数据结构,却不完全遵循标准链表的行为或实现方式。在标准链表中,每个元素(通常称为节点)包含数据和指向列表中下一个(有时是前一个)元素的引用。

每个元素由两部分组成:

  • 存储的数据
  • 下一个元素在数组中的索引。

这种结构使得元素间可以像链表一样链接,但实际上是通过数组索引来实现的

例如:静态链表

在这里插入图片描述

上述内容笔记部分图片来源网络,侵删。
Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder)
点赞加关注,收藏不迷路!本篇文章对你有帮助的话,还请多多点赞支持!

文章来源:https://blog.csdn.net/qq_51646682/article/details/135267638
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。