2
本章主要内容：
2.1 线性表的定义及运算
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.3.1 线性链表
2.3.2 循环链表
2.3.3 双向链表
2.4 一元多项式的表示及相加
3
2.1 线性表的定义及运算
线性表 (Linear List) ：由 n(n≧) 个数据元素 ( 结
点 )a
1
， a
2
…， a
n
组成的有限序列。其中数据元素的
个数 n 定义为表的长度。当 n=0 时称为空表，常常将
非空的线性表 (n>0) 记作： (a
1
， a
2
…， a
n
)
这里的数据元素 a
i
(1≦i≦n) 只是一个抽象的符号，其
具体含义在不同的情况下可以不同。
例 1 、 26 个英文字母组成的字母表
（ A ， B ， C …、 、 Z ）
例 2 、某校从 1978 年到 1983 年各种型号的计算机
拥有量的变化情况。
（ 6 ， 17 ， 28 ， 50 ， 92 ， 188 ）
4
例 3 、一副扑克的点数
（ 2 ， 3 ， 4 ，…， J ， Q ， K ， A ）
从以上例子可看出线性表的逻辑特征是：
在非空的线性表，有且仅有一个开始结点 a
1
，
它没有直接前趋，而仅有一个直接后继 a
2
；
有且仅有一个终端结点 a
n
，它没有直接后继，
而仅有一个直接前趋 a
n-1
；
其余的内部结点 a
i
(2≦i≦n-1) 都有且仅有一个
直接前趋 a
i-1
和一个直接后继 a
i+1
。
线性表是一种典型的线性结构。
5
2.1 线性表的定义及运算
各种运算简介：
1 ． Initiate(L) 初始化：构造一个空的线性表 L 。
2 ． Length(L) 求长度：对给定的线性表 L ，返回线性
表 L 的数据元素的个数。
3 ． Get(L,i) 存取：对给定的线性表 L ，返回第
i （ 0≤i≤Length(L)-1 ）个数据元素，否则返回 Null 。
4 ． Location(L,x) 查找定位：对给定的值 x ，若线性表
L 中存在一个元素 ai 与之相等，则返回该元素在线性
表中的位置的序号 i ，否则返回 Null （空）。
5 ． Insert(L,i,x) 插入：在给定的线性表 L 中，在第 i 个
元素之前插入数据元素 x 。线性表 L 长度加 1 。
