数据结构与算法—顺序表和链表（1）

线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是⼀种在实际中⼴泛使⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串…线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

 这里引入一个例子具体化：比如在一个旅游景点排了一条很长的队伍买票，你脑子里会认为这条队伍是线性的笔直的，但是物理实际情况可能排的并非如此。

顺序表

概念与结构

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

但是顺序表和数组真的一样吗？又或者有什么关系？

其实他们的关系可以类比成两道一模一样的菜品，但是数组是在小餐馆的菜，而顺序表是星级饭馆里的菜，为什么这么说？

他们的底层菜一样都是西兰花相当于是数组，但是星级餐厅的菜品会有真多装饰品，这些装饰品就相当于图中的增加数据，删除数据这些额外功能等等。这就是他们的关系和区别。

分类

静态顺序表 和 动态顺序表

静态顺序表

使用定长的数组储存元素 缺陷：空间确定，容易造成不足或者浪费

动态顺序表

底层数组空间在不断的变化，能够根据需求来增大或者缩小，避免造成空间的短缺或者浪费

动态顺序表的实现

尾插法插入数据

头文件

实现文件

因为初始化会导致capacity的值为0，运用一个三目操作符进行判断，如果为0就给上4个空间， *2是建议最好以2的倍数增加开辟空间

拆解一下代码

在这里插入图片描述

因为realloc的 第二个参数是字节单位，返回类型是void*，所以capacity为0时给的四个空间是四个字节就是一个整数，所以容量大小需要乘保存在顺序表内的数据类型，所以也需要强转类型。

在这里插入图片描述

因为realloc可能会返回两种值，当申请空间成功会返回地址，失败后会返回NULL，将arr置为NULL，将所有数据清空，所以不能直接接受realloc的返回值，需要定义个临时的指针接受返回值

成功就让arr指向tmp的空间，capacity指向增加容量的空间newCapacity

测试文件

这就是一个动态顺序表的实现！