数据结构:顺序表与链表

1. 线性表

2. 顺序表

2.1 概念与结构

概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储。

顺序表和数组的区别？

顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝

typedef int SLDataType;
#define N 7
//静态顺序表
typedef struct SLDataType {
	SLDataType arr[N];
	int slze;
}SL;

静态顺序表缺陷：空间给少了不够⽤，给多了造成空间浪费

 2.2.2 动态顺序表

typedef struct SeqList {
	SLDataType* arr;
	int slze;//有效个数
	int capacity;//容量大小
}SL;

2.2.3 动态顺序表实现

顺序表

3. 单链表

3.1  单链表概念与结构

概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。举个例子：淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。在链表⾥，每节“⻋厢”是什么样的呢？如图：

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变

量）。

图中指针变量 plist保存的是第⼀个结点的地址，我们称plist此时“指向”第⼀个结点，如果我们希望

plist“指向”第⼆个结点时，只需要修改plist保存的内容为0x0012FFA0。链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

3.1.2 链表的性质

1、链式机构在逻辑上是连续的，在物理结构上不⼀定连续

2、结点⼀般是从堆上申请的

3、从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

结合前⾯学到的结构体知识，我们可以给出每个结点对应的结构体代码：

假设当前保存的结点为整型：

struct SListNode
{
    int data; //结点数据
    struct SListNode* next; //指针变量⽤保存下⼀个结点的地址
};

当我们想要保存⼀个整型数据时，实际是向操作系统申请了⼀块内存，这个内存不仅要保存整型数

据，也需要保存下⼀个结点的地址（当下⼀个结点为空时保存的地址为空）。

当我们想要从第⼀个结点⾛到最后⼀个结点时，只需要在当前结点拿上下⼀个结点的地址就可以了。

3.1.3 链表的打印

给定的链表结构中，如何实现结点从头到尾的打印？

3.2 实现单链表

单链表

3.3 链表的分类

链表的结构⾮常多样，以下情况组合起来就有8种（2 x 2 x 2）链表结构：

链表说明：

虽然有这么多的链表的结构，但是我们实际中最常⽤还是两种结构： 单链表 和 双向带头循环链表

1. ⽆头单向⾮循环链表：结构简单，⼀般不会单独⽤来存数据。实际中更多是作为其他数据结构的⼦

结构，如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。

2. 带头双向循环链表：结构最复杂，⼀般⽤在单独存储数据。实际中使⽤的链表数据结构，都是带头

双向循环链表。另外这个结构虽然结构复杂，但是使⽤代码实现以后会发现结构会带来很多优势，实

现反⽽简单了，后⾯我们代码实现了就知道了。

4. 双向链表

4.1 概念与结构

注意：这⾥的“带头”跟前⾯我们说的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了同学们更好的理解就直接称为单链表的头结点。

4.2 实现双向链表

双向链表

5. 顺序表与链表的分析