数据结构与算法之线性表

1. 线性表的定义

• 线性表L是n（n≥0）个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。
• 当n=0时称为空表，即不含有任何元素。
• 常常将非空的线性表L(n>0)记作：L=(a1，a2，…an)
• 其中ai-1为ai的直接前驱，ai＋1为ai的直接后继。a1为表头元素，an为表尾元素。

• 线性表（Linear list）是最简单且最常用的一种数据结构，其逻辑结构为线性结构。

• 线性表具有下列特点：

　　　　存在唯一的一个没有前驱的（头）数据元素；

　　　　 存在唯一的一个没有后继的（尾）数据元素；

　　　　每个数据元素(除表头元素)均有一个直接前驱；

　　　　每个数据元素(除表尾元素)均有一个直接后继；

　　　　表中数据元素的类型是相同的

2. 线性表的基本运算

数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。

（1）初始化线性表L：InitList(L)

（2）求线性表L的长度：GetLength(L)

（3）按序号取元素：GetNode（L，i）

（4）按值查找：LocateList（L，e）

（5）插入新元素：InsertList（L，i，e）

（6）在线性表中删除元素：DeleteList（L，i）

（7）把已有线性表置为空表：ClearList（L）

3. 线性表的实现

• 顺序表在具体实现时，一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素，在C语言中可用数组data[MaxLen]来存储数据元素，为保存线性表的长度需定义一个整型变量length。
• 线性表的第l，2，…，n个元素分别存放在此数组下标为0，1，…，length-1数组元素中，如下图所示

4. 线性表的顺序存储结构的特点

优点：顺序表中的任意数据元素的存储地址可由公式直接导出，因此顺序表可以“随机存取”其中的任意元素。

不足：

• 需预先分配相应的存储空间。预分配空间过小，存储空间不便于扩充；预分配空间过大，容易造成空间浪费。
• 插入与删除运算的效率很低，插入、删除操作时需移动大量数据。

数据结构与算法之线性表

原文：https://www.cnblogs.com/lisen10/p/10820719.html