系列文章目录
第一章 顺序表、链表
第二章 栈和队列
第三章 二叉树
第四章 八大排序
文章目录
前言
今天我们来学习顺序表和链表，顺序表、链表作为学习数据结构不可缺少的一部分知识，在数据结构中担当了重要角色。简单来说，顺序表和链表就是数据在内存中不同的存储方式，而学习数据结构就是学习管理内存的不同方式。下面让我们来一起认识一下顺序表和链表吧。
一、线性表
什么是线性表呢？实际上，顺序表和链表本质上都是线性表。线性表顾名思义，就是线性存储的。
线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。
在数据结构初阶中，我们学习的结构大多数都是线性表。常见的线性表：顺序表、链表、栈、队列、字符串。
今天我们就来学习其中的顺序表和链表：
二、顺序表
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般分为：
- 静态顺序表：使用定长数组存储元素
- 动态顺序表：使用动态开辟的空间存储元素
静态顺序表有很明显的缺陷：
- 大小固定----空间给小了不够用，空间给大了用不完。
在这里我们就不讲静态的顺序表，直接学习动态顺序表。关于静态顺序表我只给出它的结构，其接口的实现相比动态顺序表而言十分简单，我就不进行实现，感兴趣的同学可以在看完动态顺序表后自己实现静态顺序表。
静态顺序表结构
#define N 7
typedef int SLDataType;
typedef struct SeqList
{
SLDataType arr[N];
int size;
}SeqList
下面我们来看动态顺序表的结构，动态顺序表就是在静态顺序表之上的优化，其结构也十分简单。
typedef int SLDataType;
//顺序表
typedef struct SeqList
{
SLDataType* pa; //使用一个指针指向动态开辟的空间
int size; //存储元素的个数
int capacity; //给定一个变量用来检查空间是否满了
}SL;
2.1 接口实现
静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小。下面我们实现动态顺序表。
typedef int SLDataType;
//顺序表
typedef struct SeqList
{
SLDataType* pa;
int size;
int capacity;
}SL;
//初始化顺序表
void SLInit(SL* ps);
//销毁顺序表
void DestorySL(SL* ps);
// 增删查改
//打印
void SeqListPrint(SL* ps);
//头插尾插
void SeqListPushBack(SL* ps, SLDataType x);
void SeqListPushFront(SL* ps, SLDataType x);
//头删尾删
void SeqListPopFront(SL* ps);
void SeqListPopBack(SL* ps);
// 顺序表查找，返回下标
int SeqListFind(SL* ps, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SL* ps, int pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SL* ps, int pos);
这是我们要实现的关于动态顺序表的常用接口。
1.顺序表初始化
首先我们来看看顺序表的初始化
关于初始化我们有两个选择：
- 在初始化的时候不开辟空间
- 在初始化的时候开辟空间
这两个实现方式没有什么区别，在初始化的时候不开辟空间就需要我们在插入数据的时候进行处理，这里我们选择在初始化的时候开辟空间
void SLInit(SL* ps)
{
assert(ps); //assert断言，判断ps指针是否有效，可以不写
ps->size = 0;
ps->capacity = 4; //初始化的大小可以根据需要自己给定，一般建议不要给太大。
ps->pa = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity); //动态开辟空间
if (ps->pa == NULL) //这里对空间开辟失败进行处理
{
perror("malloc fail");
return;
}
memset(ps->pa, 0, sizeof(SLDataType) * ps->capacity); //初始化空间，这一步可以不写，因为我们在插入的时候就相当于初始化。
}
2.顺序表销毁
由于我们顺序表的空间是动态开辟的，所以要进行销毁，将空间返回给操作系统
void DestorySL(SL* ps)
{
assert(ps);
if (ps->capacity == 0) //防止重复释放
return;
free(ps->pa); //有malloc就有free
ps->size = 0;
ps->capacity = 0;
}
3.顺序表的头插尾插
接下来就要开始插入数据，插入数据时有两种方式：头插、尾插。我们先来实现尾插
//尾插
//当我们写尾插的时候就会发现一个问题，我们在不断插入数据的过程中，总有一次，空间会被放满数据，这时我们就需要进行扩容
void SeqListPushBack(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity) //判断空间是否满了
{
//扩容
ExpansionSL(ps);
}
ps->pa[ps->size] = x;
ps->size++;
}
当我们写尾插的时候就会发现一个问题，我们在不断插入数据的过程中，总有一次，空间会被放满数据，这时我们就需要进行扩容
void ExpansionSL(SL* ps)
{
//扩容时新开辟的空间大小一般是旧空间大小的2倍
SLDataType* tmp = (SLDataType*)realloc(ps->pa, sizeof(SLDataType) * ps->capacity * 2);
if (tmp == NULL)
{
perror("ExpansionSL fail");
}
ps->pa = tmp;
ps->capacity *= 2;
}
上面就是尾插的实现，代码其实非常简单，而头插的逻辑就相对复杂一点
我们要想进行头插就需要挪动数据，头插也需要扩容
//头插
void SeqListPushFront(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity)
{
//扩容
ExpansionSL(ps);
}
//挪动数据
for (int i = ps->size - 1; i >= 0; i--)
{
//从后向前挪动
ps->pa[i + 1] = ps->pa[i];
}
ps->pa[0] = x;
ps->size++;
}
4.顺序表的头删尾删
实现顺序表最重要的就是实现它的增删查改。我们有了头插、尾插，接下来就是头删、尾删。
头删这里比较复杂，需要向前覆盖数据，尾删就比较简单了。
//头删
void SeqListPopFront(SL* ps)
{
assert(ps);
if (ps->size == 0) //没有数据时就不要删除了
return;
//向前覆盖
for (int i = 1; i < ps->size; i++)
{
ps->pa[i - 1] = ps->pa[i];
}
ps->size--;
}
//尾删
void SeqListPopBack(SL* ps)
{
assert(ps);
if (ps->size == 0) //没有数据时就不要删除了
return;
ps->size--;
}
5.顺序表的查找
在顺序表中查找元素，找到了返回该元素所在位置（就是下标），找不到返回-1
查找的逻辑也很简单，遍历查找就可以。
int SeqListFind(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == 0) //当顺序表中没有数据的时候，一定找不到
return -1;
for (int i = 0; i < ps->size; i++)
{
if (ps->pa[i] == x)
return i;
}
return -1;
}
以上就是动态顺序表的一些基本接口，最后再学习两个常用的接口，我们动态顺序表的学习也就结束了。
6.顺序表的插入–随机位置
1.任意位置的插入
这个接口的代码逻辑就比较复杂了，我们需要判断该位置是否合法，并且也需要判断是否要扩容，当插入位置不在尾部的时候，我们要挪动插入位置之后的数据。
void SeqListInsert(SL* ps, int pos, SLDataType x)
{
//判断位置是否合法
//注：顺序表顾名思义就是顺序存储的，不可以跳着存储，所以我们要插入的位置只能在 ps->size 之前
if (pos > ps->size + 1)
{
printf("位置不合法\n");
return;
}
if (ps->size == ps->capacity)
{
ExpansionSL(ps);
}
pos = pos - 1; //这里的写法是因为普通人的起始数是从1开始的，而在代码中，下标是从0开始的。
for (int i = ps->size-1; i >= pos; i--)
{
ps->pa[i + 1] = ps->pa[i];
}
ps->pa[pos] = x;
ps->size++;
}
7.顺序表的删除–随机位置
2.任意位置的删除
删除的逻辑就没那么复杂，只需要从后向前覆盖到删除位置就可以，不论删除的位置在哪里，都没有任何问题。
void SeqListErase(SL* ps, int pos)
{
assert(ps);
if (ps->size == 0)
return;
pos = pos - 1;
for (int i = pos+1; i < ps->size; i++)
{
ps->pa[i-1] = ps->pa[i];
}
ps->size--;
}
以上就是动态顺序表的实现，可以看出来还是比较简单的。顺序表本质上就是一个数组，不同的就是顺序表被封装成了一个结构体，用来更好的管理数据（也就是更好的管理数组），只要明白了这一点，顺序表就相当简单。
最后列出我们的测试代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"
void SeqListTest1()
{
SL s;
SLInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPushBack(&s, 4);
SeqListPushBack(&s, 5);
SeqListPushBack(&s, 6);
SeqListPushFront(&s, 10);
SeqListPushFront(&s, 20);
SeqListPushFront(&s, 30);
SeqListPrint(&s);
SeqListPopFront(&s);
SeqListPopBack(&s);
SeqListPrint(&s);
DestorySL(&s);
}
void SeqListTest2()
{
SL s;
SLInit(&s);
SeqListPushBack(&s, 1);
SeqListPushBack(&s, 2);
SeqListPushBack(&s, 3);
SeqListPrint(&s);
int n=SeqListFind(&s, 1);
printf("%d\n", n);
SeqListInsert(&s, 1, 4);
SeqListPrint(&s);
SeqListErase(&s, 1);
SeqListPrint(&s);
DestorySL(&s);
}
int main()
{
SeqListTest1();
SeqListTest2();
return 0;
}
三、链表
学习完顺序表，下来就该我们的链表了。顺序表只是我们的开头小菜，链表才是我们的重头菜。
那这里就有一个问题，有了顺序表，为什么还要有链表呢？
我们来看一下关于顺序表的一些问题：
- 中间/头部的插入删除，时间复杂度为O(N)
- 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
- 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
那么如何解决这些问题呢，我们引入了链表。
链表在结构上比起顺序表较为复杂，但也没那么复杂，要理解链表其实很简单。
链表就是由一个个节点链接起来，所构成的一个链状结构。在逻辑上，是一个节点链着一个节点，在物理上（也就是实际存储在内存中的结构），是由一个指针指向下一个节点。
逻辑上是连续的，物理上不一定连续。
逻辑上
物理上
物理上是没有箭头的，只是为了方便我们看，所以加上了箭头。
我们再来看顺序表的问题，由于链表是由一个一个节点构成，所以就不存在浪费空间的问题，需要一个节点，就申请一个节点，进行链接。当然也就不需要增容。至于插入和删除的时间复杂度，好像也没什么问题。只需要修改指针的指向就可以。那么到底是不是这样呢？让我们来一起看看吧。
3.1 链表的分类
1.单向或者双向
2.带头或者不带头
3.循环或者非循环
这样下来一共有八种结构
- 单向带头循环
- 单向带头不循环
- 单向不带头循环
- 单向不带头不循环
- 双向带头循环
- 双向带头不循环
- 双向不带头循环
- 双向不带头不循环
虽然有这么多不同的结构，但我们只重点学习两种 — 单向不带头不循环（最简单的结构）和 双向带头循环（最复杂的结构）
3.2 单向不带头不循环链表
单向不带头不循环链表虽然结构最简单，但实际上代码实现却是最复杂的。因为结构简单，所以在实现上就会有许多问题，下面我们来看看单向不带头不循环链表的实现吧
typedef int SLDataType;
typedef struct SListNode
{
SLDataType data;
struct SListNode* next;
}SLTNode;
//打印单链表
void SListPrint(SLTNode* phead);
//单链表头插
void SListPushFront(SLTNode** pphead,SLDataType x);
//单链表尾插
void SListPushBack(SLTNode** pphead, SLDataType x);
//单链表头删
void SListPopFront(SLTNode** pphead);
//单链表尾删
void SListPopBack(SLTNode** pphead);
//单链表查找
SLTNode* SListFind(SLTNode* phead, SLDataType x);
//单链表插入,在pos位置前插入
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x);
//单链表插入,在pos位置后插入
void SListInsertAfter(SLTNode* pos, SLDataType x);
//单链表删除，删除pos位置
void SListErase(SLTNode** pphead, SLTNode* pos);
//单链表删除，删除pos后一位置
void SListEraseAfter(SLTNode* pos);
//销毁单链表
void SListDestory(SLTNode** pphead);
这是我们要实现的所有接口。
我们发现这个链表是不需要初始化，因为它一开始就没有数据，也不会开辟空间，只有当我们插入的时候，才会开辟一个节点，进行插入。
3.2.1 链表的打印
首先是为了能更好的观察链表，我们首先写一个链表的打印
链表的打印很简单，就是遍历这个链表。
void SListPrint(SLTNode* phead)
{
//当链表为空时，phead就为NULL，当链表不为空时，phead指向第一个节点，链表的最后一个节点指向空。
while (phead!=NULL)
{
printf("%d->", phead->data);
phead = phead->next;
}
printf("NULL\n");
}
3.2.2 链表的头插
链表的头插其实很简单，但这里会涉及到二级指针的问题。因为我们的链表是单向不带头不循环的链表，所以我们会有一个指针指向头结点。而我们头插的时候，是要改变这个指针的，改变一个一级指针，需要一级指针的地址，存放一级指针的地址，就需要二级指针。
这里还有一个问题就是，当我们第一次头插的时候，没有头结点，就直接让头指针（指向头结点的指针）指向该结点就可以，而之后我们再进行头插的时候，我们有了头结点，就需要注意了。
首先我们知道，链表是一个链式结构，由一个结点指向另一个结点，并且我们现在实现的是一个单向不带头不循环的链表。所以当我们修改一个结点的指向的时候，我们就会丢失该结点原本指向的一个结点
因此我们应该先让newnode指向node2，之后再让node1指向newnode。头插也是如此
//pphead存放的是一级指针的地址，*pphead找的这个一级指针
void SListPushFront(SLTNode** pphead, SLDataType x)
{
assert(pphead);
//申请节点
SLTNode* newnode = BuySListNode(x);
//判断链表是否为空
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//先让newnode指向头结点
newnode->next = *pphead;
//然后让头指针（指向头结点的指针）指向newnode
*pphead = newnode;
}
}
头插的时候，就需要申请一个节点，用来存放数据。因为后面的与插入相关的接口都需要申请节点，所以我们封装成一个函数。
SLTNode* BuySListNode(SLDataType x)
{
SLTNode* ptr = (SLTNode*)malloc(sizeof(SLTNode)*1);
if (ptr==NULL)
{
perror("BuySListNode fail:");
exit(-1);
}
ptr->data = x;
ptr->next = NULL;
return ptr;
}
3.2.3 链表的尾插
链表的尾插相比头插就简单一些，但也要注意一些细节。
跟头插一样，当链表为空时，直接让头指针指向头结点就可以。
当链表不为空时，首先我们要找到链表的尾（找尾是找到尾结点，不是找到空指针。尾结点指向空指针），然后插入到链表的尾部就可以
void SListPushBack(SLTNode** pphead, SLDataType x)
{
assert(pphead);
SLTNode* newnode = BuySListNode(x);
//链表为空直接插入
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//定义一个指针找尾
SLTNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
//链接起来
tail->next = newnode;
}
}
3.2.4 链表的头删
链表的删除最重要的一点就是，要记得释放结点，因为我们的结点是动态开辟出来的，不释放会造成内存泄漏。而释放结点就需要该结点的地址，一旦我们修改了指向该结点的那个指针，那么我们就不能找到该结点。
链表的头删要注意的是：
- 首先我们要有一个指针将头结点的位置存起来，然后修改头指针，让头指针指向头结点的下一结点，接着释放头结点。
- 注意链表为空时不能删除，要进行判断。
void SListPopFront(SLTNode** pphead)
{
assert(pphead);
//判断链表是否为空
assert(*pphead);
//cur指针指向头结点
SLTNode* cur = *pphead;
//改变头指针的指向
*pphead = (*pphead)->next;
//释放头结点
free(cur);
cur = NULL;
}
3.2.5 链表的尾删
链表的尾删要注意的是：要修改前一结点的指向。
链表的尾删有两种方式：
- 用tail找尾结点，用prev指针指向尾结点的前一结点，释放尾结点，修改prev（前一结点）的指向
- 用tail找尾结点的前一结点，释放tail->next，然后修改tail->next就可以
void SListPopBack(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
if ((*pphead)->next == NULL)
{
free((*pphead)->next);
*pphead = NULL;
}
else
{
//SLTNode* tail = *pphead;
//SLTNode* prev = tail;
//while (tail->next != NULL)
//{
// prev = tail;
// tail = tail->next;
//}
//free(tail);
//prev->next = NULL;
SLTNode* tail = *pphead;
while (tail->next->next != NULL)
{
//prev = tail;
tail = tail->next;
}
free(tail->next);
tail->next = NULL;
}
}
写到这里，其实我们已经发现，链表中最重要的就是要注意各个结点之间的联系，要删除一个结点，就要关注该结点的前一结点，以及该结点的下一结点的地址，插入一个结点也是同样的道理。
3.2.6 链表的查找
链表的查找没什么好说的，遍历链表，找到了返回该结点的地址，找不到返回NULL指针
SLTNode* SListFind(SLTNode* phead, SLDataType x)
{
assert(phead);
SLTNode* cur = phead;
while (cur != NULL)
{
if (cur->data == x)
return cur;
cur = cur->next;
}
return NULL;
}
3.2.7 链表的插入，在pos位置之前插入和在pos位置之后插入
1.在pos位置之前插入
这个插入要注意的就是，当pos位置是头结点的时候，就是头插，可以直接调用头插接口，而其他位置的插入代码逻辑和尾插差不多，尾插是找尾或者找尾的前一个，这个插入我们找pos结点的前一结点。
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
assert(pphead);
if (pos == *pphead)
{
SListPushFront(pphead, x);
return;
}
SLTNode* cur = *pphead;
SLTNode* newnode = BuySListNode(x);
//找pos的前一结点
while (cur->next != pos)
{
cur = cur->next;
}
newnode->next = cur->next;
cur->next = newnode;
}
2.在pos位置之后插入
这个插入写起来就相当简单，先让newnode指向pos结点的下一结点，然后修改pos结点的指向就可以。
void SListInsertAfter(SLTNode* pos, SLDataType x)
{
assert(pos);
SLTNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
3.2.8 链表的删除，删除pos位置的结点和删除pos后一位置的结点
1.删除pos位置的结点
当pos位置是头结点的时候，就是头删，调用头删接口即可
这个删除就是找pos位置的前一结点，让前一结点指向pos位置的下一结点，接着释放pos即可。
void SListErase(SLTNode** pphead, SLTNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
return;
}
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
pos = NULL;
}
2.删除pos后一位置的结点
用一指针tmp将pos后一位置的结点的地址存起来，然后改变pos的指向，接着释放tmp指针就可以。
void SListEraseAfter(SLTNode* pos)
{
assert(pos->next);
SLTNode* tmp = pos->next;
pos->next = tmp->next;
free(tmp);
tmp = NULL;
}
3.2.8 链表的销毁
最后就是我们链表的销毁，链表的销毁需要注意的是要释放每一个结点，而释放一个结点之后，我们就不能找到该结点之后的结点，所以我们需要先将该结点之后的结点的地址存起来，然后依次释放即可。
void SListDestory(SLTNode** pphead)
{
assert(pphead);
assert(*pphead);
SLTNode* cur = *pphead;
SLTNode* ptr = cur->next;
while (ptr != NULL)
{
free(cur);
cur = ptr;
ptr = cur->next;
}
free(cur); //注意最后也要释放最后一个结点
*pphead = NULL;
}
总结
以上就是我们顺序表和单向不带头不循环链表的实现，及一些细节讲解。关于链表还有一个结构比较复杂，但代码实现很简单的双向带头循环链表没有讲，我会在下一篇博客中讲解，其实理解了单向不带头不循环链表，双向带头循环链表的实现就相当简单。单向不带头不循环链表的实现为什么比较复杂，就是因为链表是由一个一个结点构成，而进行插入、删除某一个结点等操作时，需要我们关注该结点的前一结点指向是否正确，及新插入结点的指向是否正确，这就是我们单向不带头不循环链表实现起来复杂的地方。但是双向带头循环链表的结构在一定程度上就解决了大部分问题，大家可以思考一下，具体我会在下一篇博客中进行讲解，谢谢大家！