线性表

1、线性表的定义 线性表（List）：零个或多个数据元素的有限序列

第一个元素无前驱，最后一个元素无后继，其他元素都有且只有一个前驱和后继。然后，线性表强调是有限的，

线性表元素的个数n(n≥0)定义为线性表的长度，当n=0时，成为空表。

2、线性表的抽象数据类型

对于不同的应用，线性表的基本操作是不同的，上述操作是最基本的，对于实际问题中涉及的关于线性表的更复杂操作，完全可以用这些基本操作的组合来实现。

3、线性表的顺序存储结构

3.1顺序存储定义

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。 存储单元存储数据元素

3.2顺序存储结构的插入与删除 3.2.1

插入

删除1

删除2

3.2.2线性表顺序存储结构的优缺点 优点： ①无须为表示表中元素之间的逻辑关系而增加额外的存储空间 ②可以快速地存取表中任一位置的元素

缺点： ①插入和删除操作需要移动大量元素 ②当线性表长度变化较大时，难以确定存储空间的容量 ③造成存储空间的“碎片”

4、线性表的链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置 以前在顺序结构中，每个数据元素只需要存数据元素信息，现在链式结构中，除了要存储元素信息外，还要存储它的后继元素的存储地址。

头指针与头结点的异同

image.png

结点由存放数据元素的数据域以及存放后继结点地址的指针域组成。

单链表结构与顺序存储结构优缺点

image.png

结论：若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。

5、静态链表

C语言具有指针能力，使得它可以非常容易操作内存中的地址和数据，但有些语言没有指针，可以用数组代替。 我们让数组的元素都是由两个数据域组成，data 和cur。也就是说，数组的每一个下标都对应一个data和一个cur。数据域data,用来存放数据元素，也就是通常我们要处理的数据，而游标cur相当于单链表中国的nexe指针，存放该元素的后继在数组中的下标。 我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。

假设我们已经将数据存入静态链表，比如分别存放着“甲”、“乙”、“丁”、“戊”、“己”、“庚”等数据，则它将处于下图状态：

此时“甲”这里存有下一元素“乙”的游标2，“乙”则存有下一元素“丁”的下标3，而“庚”是最后一个有值元素，所以它的cur设置为0。而最后一个元素的cur则因“甲”是第一有值元素而存有它的下标为1.而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。