顺序表（1）

1. 线性表我们在介绍顺序表之前应该先简单了解以下线性表是什么。简单来说线性表是一种逻辑结构是n个具有相同特性数据元素的有限序列。具有有限性有序性同类型三个特点。包括顺序表在内链表栈队列字符串通通都是线性表。线性表在逻辑上是线性结构但是在物理上不一定是连续的这是因为对于物理结构数据在计算机中实际存储方式有两种一种是顺序存储另一种是链式存储而链式存储是非连续的。2. 顺序表2.1 顺序表的概念顺序表是一段物理地址连续的存储单元依次存储数据元素的线性表的存储结构逻辑顺序与物理顺序一致通常基于数组实现。顺序表与数组的区别就像菜馆与米其林餐厅同样的菜品例如青菜小炒菜馆以简单方式炒完直接上菜而米其林餐厅通常会进行摆盘加一些秘制小料汁加一点小装饰再换个好听的名字。从普通饭变成了漂亮饭加上了许多的修饰顺序表就像米其林餐厅数组就像菜馆顺序表就是基于数组再添加了增删查改等功能2.2 顺序表分类2.2.1 静态顺序表简单来说静态顺序表就是通过结构体使用定长数组来存储元素代码形式如下typedef int SLDataType; #define N 7 //定长 typedef struct SeqList { SLDataType a[N]; //定长数组 int size; //数据个数 }SL;但是静态顺序表存在缺陷空间给少了不够用但是给多了又会造成空间浪费。打个比方假设我们在做淘宝电商每下一个订单都会存进一个定长数组中在平时订单量只有50-100个那么我们给定长数组设置150个长度就可以了但是如果某天官方突然发大额优惠卷订单量突然涨到500个那么我们150个长度的定长数组就不足与支持后面的客户下单这就是空间给少了不够用那么我们设置1000个长度换到平时又没有这么多订单就会造成空间浪费。放大一点看如果你是某个大公司的程序员双十一期间你现在正在休假但是上司突然需要你修改定长数组长度而电脑又不在你的身边就会导致大量客户没法下单造成客户流失影响到一大批营业额这样就坏菜了。2.2.2 动态顺序表动态顺序表就是可以实现按需申请功能的顺序表typedef int SLDataType; typedef struct SeqList { SLDataType* a; int size; //有效数据个数 int capacity; //空间容量 }SL;动态顺序表拥有可增容的效果通过数组实现支持容量动态调整当元素数量超过数组容量时会自动扩容结合了数组随机访问的优势和动态内存管理的灵活性。在下一篇博客我会介绍动态顺序表是如何实现的。