数据结构导论-线性表

一、线性表的基本概念

线性表是由n(n>=0)个数据元素（节点）$a_{1}$, $a_{2}$, … $a_{n}$组成的有限序列。

1. 数据元素的个数n定义为表的长度，n=0时称为空表，记作（）或φ
2. 将非空的线性表（n>0）记作：L=($a_{1}$, $a_{2}$, … $a_{n}$), $a_{1}$称为起始结点，$a_{n}$称为终端结点，对任意一对相邻结点$a_{i}$和$a_{i+1}$(1<=i<n)，$a_{i}$称为$a_{i+1}$的直接前驱，$a_{i+1}$称为$a_{i}$的直接后继。
3. 数据元素$a_{i}$(1<=i<n)只是个抽象符号，其具体含义在不同情况下可以不同。

注意：线性表中只有一个起始节点，一个终端结点，起始结点没有直接前驱，有一个直接后继，终端结点有一个直接前驱，没有直接后继，除此二节点外，每个结点都有且只有一个直接前驱和一个直接后继。

2-14

二、线性表的顺序存储

三、线性表的链接存储

1. 单链表的类型定义

2. 线性表的基本运算在单链表上的实现

四、其他运算在单链表上的实现

1. 建表

2. 删除重复节点

五、其他链表

1. 循环链表

2. 双向循环链表

六、顺序实现与连接实现的比较

七、总结