1.1 线性表的定义和基本操作

1.1 线性表的定义和基本操作

1.1 线性表的定义和基本操作

　　线性表就是一串元素的有序排列，它是最基础的数据结构，应用非常广泛，能够进行初始化、查找、插入、删除、更新和遍历等多种操作。

1.1.1 线性表的逻辑定义与特征

　　线性表是一种典型的线性结构，由n(n≥0)个有序的数据元素（结点）组成。例如，从2001年到2010年的年份按顺序排列就是一个线性表（简称“年份线性表”）：
（2001，2002，2003，2004，2005，2006，2007，2008，2009，2010）
　　1．线性表的定义
　　线性表可定义为n个数据元素组成的序列：

（a₁，a₂，a₃，...，a_n）

　　① 数据元素的个数n为线性表长。如果n=0，即线性表中无数据元素，则称此线性表为空表。
　　② 每个数据元素在线性表中都有一个位置，线性表可以看成是由“位置＋数据元素”组成的集合，这个位置决定了各数据元素在线性表中的前驱元素和后继元素。定义a_i(1≤i≤n)为线性表中第i个位置上的元素，或者称为线性表的第i个元素。
　　线性表中数据元素的位置随着线性表插入（或删除）元素的操作而发生变化。当插入数据元素后，原线性表中插入位置及其之后的所有元素在新表中的位置都增加1。同理，当删除数据元素后，原线性表中删除位置之后的所有元素在新表中的位置都减少1。
　　③ 若线性表中存在两个相连的数据元素组成的序偶对<a_i-1，a_i>，则称a_i-1是a_i的直接前驱（元素），a_i是a_i-1的直接后继（元素）。
　　④ 数据元素a(1≤i≤n)只是一个抽象符号，它既可以是单数据项，也可以由多个数据项组成。例如，表1-1所示的学籍成绩花名册线性表就是一个多数据项元素线性表的例子，它的每个数据元素由学号、姓名、语文、数学、英语、总分和平均分7个数据项组成。

表1-1 学籍成绩花名册线性表示例

学    号	姓    名	语    文	数    学	英    语	总    分	平  均  分
1	张三	90	100	70	260	86.67
2	李四	80	80	65	225	75.00
3	王五	85	60	90	235	78.33
4	姚六	50	90	55	195	65.00
……	……	……	……	……	……	……

　　2．线性表的特征
　　线性表或者为空，或者具有如下特性：
　　① 有且仅有一个“头”数据元素。例如，年份线性表的“2001”。
　　② 有且仅有一个“尾”数据元素。例如，年份线性表的“2010”。
　　③ 除“头”数据元素外，线性表中的每个元素有且仅有一个直接前驱。例如，年份线性表中的“2009”的直接前驱是“2008”。
　　④ 除“尾”数据元素外，线性表中的每个元素有且仅有一个直接后继。例如，年份线性表中的“2007”的直接后继是“2008”。
　　3．特殊的线性表
　　特殊线性表有空表和长度为1的表。
　　① 空线性表。没有数据元素的线性表是空线性表，此时，线性表既没有头数据元素，也没有尾数据元素。
　　② 长度为1的线性表。线性表中只有一个数据元素，此元素既是该线性表的头数据元素，也是其尾数据元素，它没有前驱，也没有后继。

1.1 线性表的定义和基本操作