企业官网建设流程全解析

1. 线性表的基本概念

1.1 线性表的定义

我们平常都是使用L来表示线性表，这里引进了一个新的概念------位序，我们要区分位序和下标之间的区别，下标是从0开始的，但是位序是从1开始的，很多书籍都将的位序，大家不要搞混了。

线性表的表头没有前驱，表尾没有后继，这与我们之前的顺序储存很相似。

1.2 线性表的两种实现方式

线性表使用顺序存储的方式就是顺序表，使用链式存储的方式就是链表（下一节内容）。

我们来回顾一下顺序存储和链式存储。

2. C++引用补充

我们完全可以使用C来实现数据结构的内容为什么我们还要适当引用C++的内容来实现代码呢？

其目的就是为了能减少指针的使用，简化程序。

这里我们需要注意一下，我们既然要使用C++的语法内容，文件名就不能使用XXX.c命名了，我们要将后缀改成cpp，因为C++完全兼容C。

2.1 引用的基本概念

引用不是定义一个新的变量，而是给现存的变量起一个别名，编译器不会为引用变量开辟空间。

重点就是这个&符号

这四个变量指向的都是同一块空间，其实就是为a取了3个别名。

2.2 引用的特性

引用在定义的时候，必须指出引用的对象。

2.3 引用的做参数

引用传参不用像传址那样使用指针来接受，相当于传过去的是实参的别名，而且引用传参无需开辟空间，传址则需要开辟指针空间。

3. 顺序表

3.1 动态顺序表和静态顺序表

3.1.1 静态顺序表

静态顺序表就是用固定大小的静态数组来存储数据。优点是实现简单，缺点是适用场景局限，只适 用于确定知道自己最多存放多少数据的场景，否则空间申请少了不够用，申请多了浪费。

这其中就包含了我们C中学习的结构体以及typedef和define，如果不熟悉的话现在可以去复习一下前面的知识。

3.1.2 动态顺序表

动态顺序表就是用一个堆上动态申请的数组来存储数据，如果空间不够了可以做扩容处理。优点适 用场景多，不确定自己要存放多少数据的场景也很适合，缺点是实现相对复杂⼀些。后续我们主要 实现动态顺序表，因为动态顺序表可以掌握，静态顺序表就是手拿把掐。

3.2 动态顺序表实现

为什么不讲静态顺序表呢？

静态顺序表我们使用的不多，而且静态顺序表难度不大，都是根据我们之前的知识，我们讲完动态顺序表之后静态顺序表也就会了。

我们先对顺序表实现的接口函数定义进行介绍。

这些函数命名我们都是放在头文件中，后续我们再源文件中要使用直接使用include引用即可。

这些函数的实现我们都是直接放到一个.cpp文件中，.h文件只放声明。

看到这里你们可以自己去试试能不能将这些函数进行自主实现。

3.2.1 初始化

顺序表的初始化，就要使用到我们C语言中学到的动态内存管理的相关知识。

调用malloc函数开辟空间，只要传入的时指针就一定要使用断言assert，我们这里的调用结构体的方式就是我们之前讲过的结构体的间接调用，因为我们得到的是指向结构体变量的指针。

但是我们可以不使用结构体指针来访问，我们可以使用前面说过的引用来调用，如果我们是使用引用的方式来调用的话，我们引用结构体成员就可以使用ps.arr的方式来直接调用结构体成员。

但是要注意，这里不能使用assert断言，这里的ps是结构体引用，引用不可能为空，使用断言的话会报错。

3.2.2 销毁

即使是要销毁的，我们也要先断言一下；释放动态数组指针的空间，并设置为NULL，将其他的设置为0。

3.2.3 删除元素

这里我们就还要断言一个，我们要确定i一定是再数组指针内的，我们必须再删除之前要先将要删除的元素存起，方便后续的返回。

我们后续会有一个贪吃蛇的小项目，我们要先掌握下面的头删和尾删以及头插尾插。

3.2.3.1 头删

这里我们是要删除元素所以我们不需要考虑空间不够的情况，但是我们后续将插入的时候就要考虑空间不够的情况了。

我们再删除的过程中，直接使用元素覆盖即可，头删用第二个元素进行覆盖，尾删直接删除即可。

3.2.3.2 尾删

直接有效元素-1即可

3.2.4 插入元素

我们先写一个用于判断是否需要扩容的函数:

这里我们判断不够后，扩容一般是扩容当前容量的2倍，以此内推，到后面我们的扩容次数会越来越少，这里我们使用了static，来限制函数的使用范围。

3.2.4.1 头插

因为我们要再头部腾出一块空间，所以我们应该要从最后一个元素开始向后移动，如果我们是从第一个元素开始向后移动的话，会导致第二个被第一个元素覆盖。

3.2.4.2 尾插

尾插我们也需要判断是否扩容，插入直接插入到末尾即可。