线性表(List)

线性表的定义

1. 线性表由零个和多个数据元素组成的有限序列
2. 它是一个序列,也就是说元素之间是有先来后到的
3. 若元素存在多个,则第一个元素无前驱,而最后一个元素无后继,其他元素都有且只有一个前驱和后继
4. 线性表强调是有限的
5. 例子:线性表(a1..........ai-1,ai,ai+1,.....an) 其中ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素 所以线性表元素个数n(n>=0)定义为线性表的长度,当n=0时为空表

抽象数据类型(ADT)

1. 数据类型就是很多编程语言中的整型,浮点型,字符型,等等...
2. 抽象类型就是把数据类型和相关操作捆绑在一起
3. 描述抽象数据类型的标准格式: 伪代码

线性表的抽象数据类型

1. 线性表多的抽象数据类型定义

线性表的顺序存储结构

线性表从1开始,数组是从0开始

顺序存储结构代码

#define MAXSIZE 20
typedef int ElemType;
typedef static
{
    ElemType data[MAXSIZE];
    int length;
}SqList;

1. 顺序存储结构封装需要三个属性

   1. 存储空间的起始位置,数组data,它的存储位置就是线性表存储空间的存储空间的存储位置
   2. 线性表的最大存储容量:数组的长度MaxSize.
   3. 线性表的当前长度:length
   4. 数组多大的长度与线性表的当前长度需要区分一下:数组的长度是存放线性表的存储空间的总长度,一般初始化后不变,而线性表当前长度是线性表的个数,是会变化的

2. 地址计算方法

LOC(ai+1)=LOC(ai)+c

LOC(ai+1)=LOC(ai)+(i-1)c

3. 获取元素操作代码 GetElem 将线性表L中的第i个位置元素值返回,就相当于把数组第i-1下标的值返回即可

4. 插入操作 ListInsert(*L,i,e)

   在线性表L中的第i个位置插入新元素e

   插入算法思路:

   1. 如果插入位置不合理,抛出异常
   2. 如果线性表长度大于等于数组长度,则抛出异常或的动态增加数组容量;
   3. 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
   4. 将要插入元素填入位置i处;
   5. 线性表长+1

5. 删除操作ListDelete 删除算法的思路:
   1. 如果删除位置不合理,抛出异常;
   2. 取出删除元素;
   3. 从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
   4. 表长-1

线性表的顺序存储结构,在存,读数据时,不管是哪个位置,时间复杂度都是0(1)而在插入或删除时,时间复杂度都是O(n)

6. 线性表顺序存储结构优缺点 优点:

   1. 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
   2. 可以快速地存取表中任意位置的元素

   缺点:

   1. 插入和删除操作需要移动大量元素
   2. 当线性表长度变化比较大时,难以确定存储空间的容量
   3. 容易造成存储空间的"碎片"