《数据结构》C语言版 (清华严蔚敏考研版）第二章线性表知识梳理与总结

本文主要是介绍《数据结构》C语言版 (清华严蔚敏考研版）第二章线性表知识梳理与总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

个人主页：李仙桎

🔥 个人专栏：《数据结构与算法》

⛺️生活的理想，就是为了理想的生活!

Alt

⛺️前言：各位铁汁们好啊！！！，今天继续学习数据结构相关的内容，后续不断更新数据结构有关知识内容！！希望各位铁汁多多支持！这一章节主要是《数据结构》第二章线性表的内容。知识梳理与总结——重点掌握理解时间复杂都计算

1、线性表定义和相关术语⭐⭐

1.1、线性表

1.2、数组

2、顺序表的表示

2.1、静态顺序表

注意点：typedef 关键字——数据类型重命名

2.2、动态顺序表

2.3、顺序表的特点

3、顺序表的操作

3.1、插入一个数据元素

3.2、删除一个元素

3.3、查找元素——按位查找

3.4、查找元素——按值查找

4、单链表

4.1、单链表定义

4.1.1、不带头结点的单链表

4.1.2、带头结点的单链表

4.2、单链表操作

4.2.1、按位序插入

4.2.2、按位序删除

4.2.3、按位查找

4.2.4、按值查找

4.3、单链表的建立

4.3.1、头插法

4.3.2、尾插法

5、双链表

5.1、双链表的初始化

5.2、双链表的插入

5.3、双链表的删除

5.4、双链表的遍历

6、循环链表

6.1、循环单链表

6.2、循环双链表

6.3、循环双链表的插入

6.4、循环双链表的插入

7、静态链表

7.1、静态链表初始化

7.2、静态链表基本操作

1、线性表定义和相关术语⭐⭐

1.1、线性表

线性表是数据结构的一种，它是一组具有相同数据类型的数据元素的有限序列。在线性表中，除了第一个和最后一个数据元素之外，每个数据元素均只有一个直接前驱和一个直接后继。线性表的元素个数n（n≥0）定义为线性表的长度，当n=0时，称为空表。

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链表的形式存储

线性表的抽象数据类型定义

ADT List{数据对象:D={ai|aiEElemSet.i=1,2,…,n,n≥0}    //任意数据元素的集合数据关系:R={<ai-1, ai>| ai-1, ai ∈D,i=2,3,…,n }//除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作:InitList(&L )操作结果:构造一个空的线性表L;ListLength( L)初始条件:线性表L已存在;操作结果:返回L中的数据元素个数。GetElem( L,i,&e )初始条件:线性表L已存在，1≤i≦ListLength(L);操作结果:用e返回L中第i个数据元素的值;...
}ADT List

1.2、数组

提到顺序表，我们不得提一下数组，数组是程序设计中的一种基本数据结构，它是同一数据类型元素的集合，这些元素在内存中按照顺序排列，占据连续的内存空间。数组是静态的数据结构，它的大小在定义时就已确定，并且在整个生命周期中保持不变。数组可以是一维的，也可以是多维的（如二维数组、三维数组等）

数组特点：

静态结构：一旦定义，大小不可变。
连续的内存空间。
支持随机访问，即可以通过索引访问任意元素。
大小固定，一旦数组被声明，它的大小就被确定下来，不能动态地增加或减少元素。

2、顺序表的表示

2.1、静态顺序表

注意点：typedef 关键字——数据类型重命名

类型抽象：通过使用类型别名，可以将数据类型抽象化。这意味着如果将来需要改变数据类型（比如从 int 改为 float 或者某个结构体类型），只需修改 typedef 行的定义，而不用修改整个代码中的多个地方。这提高了代码的可维护性。我们展开讨论：

假设您在一个较大的项目中定义了一个数据类型别名 SLDataType 来代表 int，并在多个函数和数据结构中广泛使用了这个别名。现在，我们来看看如果需要更改这个数据类型，类型别名如何简化这个过程。

typedef int SLDataType; // 初始类型别名定义// 使用SLDataType的函数
void processElement(SLDataType element) {// ... 处理逻辑 ...
}// 使用SLDataType的数据结构
typedef struct {SLDataType array[10];int size;
} DataArray;

在这个初始代码中，SLDataType 被用于函数 processElement 和结构体 DataArray。

更改数据类型
现在，假设您决定将 SLDataType 从 int 更改为 float。这种情况下，您只需修改 typedef 行：

typedef float SLDataType; // 修改类型别名

由于 SLDataType 被用于整个项目中，这一改变会自动应用于所有使用了 SLDataType 的地方。这意味着您不需要逐个查找和替换每个 int 类型的实例。processElement 函数和 DataArray 结构体现在都会使用 float 而不是 int，而且不需要对它们的代码进行任何修改

静态顺序表使用过程

2.2、动态顺序表

增加动态数组的时候使用malloc申请一片连续的空间，但是在销毁的时候不会自动销毁，需要我们使用free手动销毁

2.3、顺序表的特点

3、顺序表的操作

3.1、插入一个数据元素

3.2、删除一个元素

3.3、查找元素——按位查找

3.4、查找元素——按值查找

4、单链表

4.1、单链表定义

链表是一种在计算机科学中常用的数据结构，用于存储元素的集合。它与顺序表相比，链表的元素不是在内存中连续存储的（逻辑上元素是来连续的的，但是物理地址上并不连续的）。链表由一系列节点组成，每个节点至少包含两个部分：一个是存储的数据，另一个是指向列表中下一个节点的指针（或引用）。通过这种方式，链表中的节点被串联起来

优点：不要求大片连续空间

缺点：不可以随机存取，要耗费一定空间存放指针

LinkList 和LNode *的使用看使用地方，主要目的是提高可读性

4.1.1、不带头结点的单链表

4.1.2、带头结点的单链表

带头节点的单链表，是指在单链表的最前端添加了一个额外的节点，这个节点被称为头节点（哨兵节点），但它一般不用于存储实际的数据（或者可以说存储的数据不被使用）。头节点的主要目的是为了简化链表操作的逻辑，避免在处理链表的开始位置时需要进行特殊的条件判断

4.2、单链表操作

4.2.1、按位序插入

带头结点——找到第i-1个元素，将新节点插入其后面

平均时间复杂度：O(n)

不带头结点（不存在第0个节点，因此i=1的时候需要特殊处理）——找到第i-1个元素，将新节点插入其后面！没有头节点的普通单链表中，如果链表为空，则链表的第一个节点（head pointer）直接为NULL，这使得插入和删除操作时，需要分别检查特定情况，如链表是否为空、是否在链表开始或结束位置进行操作等。