线性表的基本概念
零个或多个数据元素的有限序列。
前驱、后继。
除首个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继。
线性表有限，线性表元素的个数为线性表的长度，n=0时为空表。
有两种物理结构：顺序存储结构、链式存储结构。
线性表的抽象数据类型
ADT 线性表（List）
Data
线性表的数据对象集合为{a1,a2,……an}，每个元素的类型均为DataType。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
Operation
InitList(*L): 初始化操作，建立一个空的线性表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): 删除线性表L中第i个位置元素，并用e返回其值。
ListLength(L): 返回线性表L的元素个数。
endADT
线性表的顺序存储结构（随机存储结构）
线性表的顺序存储结构，指的是一段地址连续的存储单元依次存储线性表的数据元素。
一般用数组的形式实现线性表。
三个属性：
- 存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。
- 线性表的最大存储容量：数组长度MaxSize。
- 线性表的当前长度：length。
数组的长度为线性表的最大长度，也就是最大存储空间，线性表的长度小于等于数组长度。
存储位置计算
LOC(ai)=LOC(a1)+(i-1)*c
c的含义是数据元素占用的存储单元。
各种操作的时间复杂度
- 插入或删除的时间复杂度为 O(n)
- 查询的时间复杂度为 O(1)
优缺点
优点
- 无须为表示表中元素之间的逻辑关系而增加额外的存储空间。
- 可以快速地存取表中任一位置的元素。
缺点
- 插入和删除操作需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的容量
- 造成存储空间的“碎片”
获取元素算法思路
1. 如果获取位置不合法，则抛出异常；
2. 若i在范围内，返回数组下标为i-1的值。
插入操作算法思路
1. 如果插入位置不合理，抛出异常；
2. 如果线性表长度大于等于数组长度，则抛出异常或者动态增加容量；
3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置；
4. 将要插入元素放入位置i处；
5. 线性表长度加一。
删除操作算法思路
1. 如果删除位置不合理，抛出异常；
2. 取出删除元素；
3. 从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置；
4. 线性表长度减一。
网友评论