线性表
零个或多个数据元素的有限序列
1. 面向何种问题？
在数据结构的第一篇基本理解里面有提到面向问题的逻辑结构，而线性表就是一个描述问题的逻辑结构
因此我们需要先弄清楚线性表描述的是什么样的问题
一年中的十二星座？马路边的一排整齐排列的单车？...
上面说的问题都对，通俗来说线性表就是一列相同性质的事物。
它有两个极为重要的特点，线性表描述的问题一定必须满足：
- 前驱后继的唯一性
！！线性表第一个元素没有前驱，最后一个元素没有后继，凡是中间元素必有且仅有一个前驱与一个后继。！！ - 有限性（无限的数列只存在数学概念中，所以这一特性只作为了解）
2. 线性表的抽象数据类型？
前面文章提到抽象数据类型实际上是一个数学模型，所谓数学模型可以理解成有共性，而线性表的共性就是前面所说的前驱后继关系。
- 这里先解决一个疑问：你说整型是一个数据类型，线性表是一个抽象数据类型，它们都是有相同的性质和一系列的操作，但是怎么理解线性表里面的数据元素是整型类型呢？
答：——所谓数据类型，无非是从某些个个体中抽象出了一堆的共性，首先，我把它们都是整数这一共性给抽象出来变成了整型数据类型，接着我们又把这些个体都是按照前驱后继的方式排列的共性再次抽象出来，就成了整型类型数据的线性表
| 类型 | 共性 | 操作 |
|---|---|---|
| 整型 | 都是整数 | 加减乘除... |
| 线性表 | 遵循前驱后继唯一和有限性 | 增删查改... |
| 整型线性表 | 都是整数且遵循前驱后继唯一且有限 | 加减乘除+增删查改 |
（理解可以按上面表格这么理解）
- 线性表抽象数据类型：
| Data | 与物理结构相关性 |
|---|---|
| 数据对象：D={ai|ai=ElemSet,i=1,2,..,n,n≥0} | 与存储物理结构无关 |
| 数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,...,n} | 与存储物理结构有关 |
| Operation | 与物理结构相关性 |
|---|---|
| InitList(*L)：初始化操作，建立一个空的线性表。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| ListEmpty(L)：判断线性表是否为空表。若为空表，返回true；否则，返回false。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| ClearList(*L)：将线性表清空。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| GetElem(L,i,*e)：将线性表L中的第i个位置的元素值，返回给e。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| LocateElem(L,e)：在线性表中L中查找与e相等的元素。若存在，返回元素序号；否则，返回0表示不存在。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| ListInsert(*L,i,e)：在线性表L中的第i个位置，插入新元素e。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
| ListDelete(L,i,e)：删除线性表中的第i个元素，并用e返回其值。 | 方法内实现过程与物理结构有关，而定义（传参、返回什么类型）与其无关 |
实际上会有很多更复杂的操作，但是都是可以通过组合上面的基本操作达到目的的！
这里很清楚的看到，方法定义（仅仅是种类，实现过程还是和物理结构有关的）是由线性表特性决定好的，和存储的物理结构无关，而Data中的数据关系则是要根据具体的物理结构具体去定义。
顺序存储结构
1. 理解
顺序存储的特点（也可能可以说是目的吧）：就是通过计算数据存储的地址，获取元素
（对比链式存储：通过一步步寻找找到数据存储的地址，获取元素）
不要小瞧计算两个字，它意味着
1.可以快速通过常数规模的计算量就找到存储地址
2.并不意味着数据必须按照连续存储的方法存储
怎么去理解？意思就是，即使是数组我也不需要连续存储，每一个数据隔一个存储单位放在硬盘里也行，隔两个存储单位也行，因为唯一不同的就是我计算地址的时候是：首地址+第i个*2 和 首地址+第i个*3 的区别
线性表顺序存储结构
1. 三个属性
线性表顺序存储结构有三个属性，它们是为了计算公式而存在的，有了这三个属性就能完全描述线性表的顺序存储结构：
-
存储空间起始位置（Data）
没有起始地址，计算数据存储地址从何谈起？ -
线性表的最大存储容量（MAXSIZE）
为什么需要定义最大长度？实际上是为了约束计算公式中的系数，否则的话，超出最大存储后，数据就不能按规律（例如说按照连续存储单元的规律）存储了，那么就无法通过计算来得到数据存储地址了 -
线性表当前长度（Length）
为了约束公式中的i，让它不要超过合理的上限，否则找不到真正存储的数据
2. 三个属性的java具体实现
详见https://www.jianshu.com/p/569ab283dfa0
网友评论