【软件设计师：数据结构】1.数据结构基础（一）

一 线性表

1.线性表定义

线性表是n个元素的有限序列，通常记为(a1，a2，…，an)。
特点：

• 存在惟一的表头和表尾。
• 除了表头外，表中的每一个元素均只有惟一的直接前驱。
• 除了表尾外，表中的每一个元素均只有惟一的直接后继。

2.线性表的存储结构

(1)顺序存储

是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。

• 优点：可以随机存取表中的元素

• 缺点：插入和删除操作需要移动大量的元素。

在线性表的顺序存储结构中，第i个元素ai的存储位置为：

LOC(ai)= LOC(a1)+(i-1)×L

其中LOC(a1)是表中第一个元素的存储位置，L是表中每个元素所占空间的大小。

(2)链式存储

链式存储是指用结点来存储数据元素，结点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。
结点空间只有在需要的时候才申请，无须