【数据结构与算法】数据结构初阶：详解顺序表和链表（一）

🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

前言：上篇文章我们介绍了复杂度的概念，我们通过一个个经典的例子，对时间复杂度和空间复杂度的概念进行了剖析，结合图像，让大家更加直观地理解知识点，我们对比了常见的复杂度，展示了各种各样的排序算法的复杂度表格，通过轮转数组这一道力扣题向大家展示了“算法思路有很多种”名不虚传，我们通过三种不同的思路（超出时间限制、通过、时间复杂度O(n)空间复杂度O(1)的情况下通过）详解了算法和复杂度的关系。

本篇文章，我们就要开始介绍顺序表和链表相关的知识点了，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们已经介绍完了第一部分：算法复杂度，从本文开始，我们就正式进入第二部分中的顺序表和链表部分内容的学习啦。

正文

一、线性表

线性表（Linear List）是指n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串……

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

由此可见线性表还可分为两种结构：线性结构和逻辑结构。

所谓逻辑结构就是人为想象出来的。

二、顺序表

（一）顺序表的概念

概念：顺序表是一段用物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。那么我们可不可以说，数组就是顺序表？或者说，顺序表就是数组？可以这么说吗？如果不能这么说，那么数组和顺序表又有什么区别呢？

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

换句话说，数据结构完成的就是顺序表的增删查改等接口函数的实现。

举个例子，数组和顺序表的关系可以拿苍蝇小馆和米其林五星级餐厅类比一下——

（二）顺序表的分类

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

1、静态顺序表

静态顺序表就是使用定长数组存储元素。

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

2、动态顺序表

动态顺序表就是按需申请空间存储进行存储。

（三）顺序表的结构

我们分别介绍静态顺序表和动态顺序表的结构——

（四）动态顺序表的实现

静态顺序表和动态顺序表，我们这里就实现一下动态顺序表，但并不是说静态顺序表就没有学习的必要了。这一点要明确。

我们要分成三个文件来实现，因为是顺序表，我们就取个名字叫"SeqList"，用三个文件实现一个功能我们在扫雷游戏那里就接触过了，我们简单分析一下三个文件各自的分工：

我们分别创建三个文件：SeqList.h头文件、SeqList.c文件、test.c测试文件——

下面我们会分别介绍三个文件的书写，每个小标题下面的第一个代码是动态顺序表的代码实现。在代码下面则是抽丝剥茧展开来的详解。

动态顺序表的实现（包含尾插）

（1）SeqList.h

#pragma once
#include<stdio.h>//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{SLDataType* arr;//存储数据int size;//有效数据个数int capacity;//空间大小
}SL;//typedef struct SeqList SL;void SLInit(SL s);

（2）SeqList.c

#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"
#include"stdio.h"
#include"test.c"
#include<stdlib.h>void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}//尾插
void SLPushBack(SL* ps, SLDataType x)
{//空间不够if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity);if (tmp == NULL);{perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->size++] = x;
}

（3）test.c

#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"void test01()
{SL sl;SLInit(&sl);//具备了一个空的顺序表SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);
}int main()
{test01();return 0;
}

（五）详解顺序表书写

这里涉及到了结构体的知识，我们学习数据结构要对结构体有足够的认识。

#pragema once#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增删查改等接口函数

这里.h文件的第一行我们看到的代码的作用，博主在C语言专栏的这篇文章里面介绍过——预处理深入详解：预定义符号、宏、命名约定、命令行定义、条件编译、头文件的包含

我给大家截过来看一下——

#pragma once

功能就是可以避免头文件被重复包含。

如果你不想这样定义，也可以写成这样，作用是等价的——

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增删查改等接口函数
#endif  //__TEST_H__

我们定义的时候要注意，为什么这里数据类型不用define来定义？类型我们一般用typedef来定义的，定义一个普通的常量，我们是用#define，比如这里我们定义N是一个常量100。

#define  N  100

我们这样定义的好处就是不需要再在代码中一个一个去修改了——

#pragema oncestruct SeqList
{int a[10];int size;
}

如果我们想顺序表存储的不是10，而是100，或者1000，我们一般这样定义：

#pragema once#define  N  100struct SeqList
{SQDataType a[N];int size;
}

a[ ]里面放N，当我们想改的时候，直接在定义里面把N改一下就可以了，不用在代码里面一个一个去改。像顺序表存储的数据类型，我们这样定义——

typedef int SLDataType;

我们这样定义有什么好处？很简单，比如我们上面的头文件里面定义了一个数据类型叫SLDATAType，现在在代码里面我们定义它是int类型，如果我要存的是char类型，我把这里改成char就行了，如果我要存的是double，我把这里改成double就可以了。

typedef char SLDataType;
typedef float SLDataType;
typedef double SLDataType;

是不是这个道理？这样我们就不需要考虑别的，直接在定义里面修改就可以了。这就是我们这样定义的好处。

定义完了，我们就要进行一下初始化。

初始化我们可以考虑用一个循环来初始化，也可以像下面这样用一个memset函数来初始化，memset函数是按字节对其进行初始化。

#pragema once#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}//增删查改等接口函数
void SeqListInit(struct SeqList sl);

我们C语言里面结构体不能直接写结构体名称，uu们是不是觉得这样太长了，我们可以简写：

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;struct SeqList
{SQDataType a[N];int size;
}
typedef struct SeqList SL;
void SeqListInit(struct SeqList sl);
//增删查改等接口函数
#endif  //__TEST_H__

当然我们还可以这样写（有很多书上包括很多老师是这样写的）：

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[N];int size;
}SL;
void SeqListInit(struct SeqList sl);
//增删查改等接口函数
#endif  //__TEST_H__

那我们就可以不写那么长一截了，直接写简写“SL”——

#ifdef __TEST_H__
#define __TEST_H__#define  N  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[N];int size;
}SL;
void SeqListInit(SL sl);
//增删查改等接口函数
#endif  //__TEST_H__

是不是简单多了？这里再提醒一下uu们，我们敲代码不要一股脑敲完了再测试，我们可以敲一个测试一个，代码如果很长，一股脑写完可能出问题了一时半会儿找不到bug，这是一个很好的代码书写习惯，是前辈们总结出来的经验教训，大家也应当学习一下这种书写方式。

写程序的时候，奋笔疾书、一顿操作，写完一运行几十个错误，再反复调试了一两个小时，再一运行，又报了几十个错误，自己都快崩溃了。

那我们写一个测试一个，有问题也只在这几行代码里面，方便我们查找，犯不上自己吓自己~

顺序表就是数组嘛，uu们可能觉得这个N还不好理解，我们可以在定义的时候写成这样——

#ifdef __TEST_H__
#define __TEST_H__#define  MAX_SIZE  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
void SeqListInit(SL s);
//增删查改等接口函数
#endif  //__TEST_H__

这样是不是更容易理解，我们一看便知，这是数组最大的大小。

#include"SeqList.h"void SeqListInit(SL s)
{memset(sl.a,0,sizeof(SQDataType)*MAX_SIZE);sl.size = 0;
//sl.a说明是按字节初始化
//初始化多少个字节呢？MAX_SIZE个
//每个有多大呢？sizeof(SQDataType)——SQDataType这个类型每一个的大小
}

这里我们就能更明显地感觉到我们定义数组大小为MAX_SIZE的好处了，我们想把数组大小改一下是不是只要在.h文件的定义这里改一下就把所有包含了.h文件的数组大小都改掉了？很方便。

定义数据类型和定义数组大小同理，本质上都是增强了程序可维护性（不用所有地方都去改）。

那我们现在开始写一点测试一点，我们程序要输入输出，包含一个头文件，我们不知道的话再查一下memset的头文件，<cstring>或者<string.h>这两个头文件是一样的——

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增强程序可维护性
#define  MAX_SIZE  100
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
void SeqListInit(SL s);
//增删查改等接口函数
#endif  //__TEST_H__

然后我们来到test.c文件，先写一个简单的——

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(SL s1);
//调接口进行初始化
}int main()
{return 0;
}

定义完了，我们先来试着跑一跑，调试的时候我们可以结合VS调试技巧中介绍过的技巧，F9打断点，按F5调试，运行到断点处。

所以这里我们就不能这么写，要把前面的改一改：

1、静态顺序表

我们C语言里面学过一个通讯录的东西，就是这个结构。定义一个宏就写死了。

（1）SeqList.h

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增强程序可维护性
#define  MAX_SIZE  10//100个、500个有点太大了，先来10个
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//头插
void SeqListPopBack(SL*ps);//头删
void SeqListPopFront(SL*ps);//尾删
#endif

这里uu们如果有其他明明也是可以的，博主这里是跟cpp的STL库——标准库——的命名走的。这是一种比较规范的命名形式——

void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//头插
void SeqListPopBack(SL*ps);//头删
void SeqListPopFront(SL*ps);//尾删

当然这里还有其他的接口，我们还是老原则，写一个测试一个。

（2）SeqList.c（静态顺序表）

#include"SeqList.h"void SeqListInit(SL*p s)
{memset(ps->a,0,sizeof(SQDataType)*MAX_SIZE);ps->size = 0;
}
//头插  尾插  头删  尾删
void SeqListPushBack(SL*ps,SQDataType x);
{if(ps->size >= MAX_SIZE){printf("SeqList is Full\n");return;}ps->a[ps->size] = x;ps->size++;
}
//下面的大致也是上面这样，就不介绍了
void SeqListPushFront(SL*ps,SQDataType x);
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);

从这里我们可以看出静态顺序表结构不是一个好的顺序表，存储1001个，你定义MAX_SIZE为10000，是不是浪费了空间，静态顺序表存在的问题总结一下就是：

给少了不够用，给多了用不完浪费空间，不能很好地控制。

正因如此，我们选择更加灵活的动态顺序表，静态顺序表我们就介绍到这里。

（3）test.c

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);
//调接口进行初始化
}int main()
{TestSeqListl();return 0;
}

为什么要写指针呢，因为形参是实参的一份临时拷贝，形参和实参空间相互独立，我们要传地址，这样形参改变不会影响实参，传地址为什么可以影响呢？

2、动态顺序表

(1)尾插

（1）SeqList.h

#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增强程序可维护性
typedef int SQDataType;typedef struct SeqList
{SQDataType*a;int size;     //有效数据的个数int capacity;//容量
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPrint(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//头插
void SeqListPushFront(SL*ps,SQDataType x);//尾插
void SeqListPopBack(SL*ps);//头删
void SeqListPopFront(SL*ps);//尾删
#endif

（2）SeqList.c（动态顺序表）

#include"SeqList.h"void SeqListInit(SL*ps)
{
//粗暴一点，先置为空，再改成0，然后capacity也改为0ps->a = NULL;ps->size = 0;ps->capacity = 0;
//当然我们也可以直接malloc
}
//头插  尾插  头删  尾删
void SeqListPushBack(SL*ps,SQDataType x);
{//满了就要扩容if(ps->size == ps->capacity){//扩容一般扩两倍，一个一个太慢了，三倍又太多了，cpp标准库一般是扩两倍//我们有两种思路，一种是新开辟一个两倍的空间，然后把原来的内容复制过去，另一种是reallocint newcapacity = ps->capacity == 0 ? 4 : ps->capacity*2;//第一次给多少没什么讲究，给个10也可以，只是说一开始不要给太大，给太大就浪费了//动态管理，就是开始给小一点，不够了慢慢增加//最小给个1SQDataType* tmp = realloc(ps->a,ps->capacity*2*sizeof(SQDataType));//realloc有可能失败if(tmp == NULL){printf("realloc fail\n");exit(-1);}else{ps->a = tmp;//ps->capacity *= 2;//这里就不是乘两倍了，直接是等于newcapacityps->capacity = newcapacity;}}ps->a[ps->size] = x;ps->size++;  
}
void SeqListPushFront(SL*ps,SQDataType x);
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);void SeqListPrint(SL*ps)
{for(int i = 0;i < ps->size;++i){printf("%d ",ps->a[i]);}printf("\n");
}

（3）test.c

#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);SeqListPushBack(&sl,1);SeqListPushBack(&sl,2);SeqListPushBack(&sl,3);SeqListPushBack(&sl,4);SeqListPushBack(&sl,5);SeqListPushBack(&sl,6);SeqListPushBack(&sl,7);SeqListPushBack(&sl,8);SeqListPushBack(&sl,9);SeqListPushBack(&sl,10);SeqListPushBack(&sl,11);SeqListPrint(&sl);
}int main()
{TestSeqListl();return 0;
}

这种就是尾插，只要内存够，我们可以继续插。不会像静态顺序表那样，它不需要定义多少个，不够了就增容，可以一直尾插下去，这就是动态顺序表相较于静态顺序表的优越性。

那么uu们可能要问了，realloc不是在原来空间的基础上扩容吗？如果原来空间是0怎么办呢？