Page 71 - 高中 信息技术 选择性必修1 数据与数据结构

 3.1 线性表

线性表：由n（n≥0）个数据元素a ，a ，…，a 组成的有限序列。该序列中所有数据
1
2
n
元素均具有相同的数据类型。其中，数据元素的个数n称为线性表的长度。
当n=0时，称为空表。
当n>0时，将非空的线性表记作：L=( a ，a ，…，a ，a ，a ，…，a )。
i-1
i
i+1
1
2
n
L为线性表名称；
a 为线性表的第一个数据元素，称为表头，a 为线性表的最后一个数据元素，称为
1
n
表尾；
a ，a ，…，a 都是a （2≤i≤n）的前趋，其中a 是a 的直接前趋；
1
i
i-1
2
i-1
i
a ，a ，…，a 都是a （1≤i≤n-1）的后继，其中a 是a 的直接后继。
i+1
i
i+1
广东教育出版社
n
i
i+2
对于线性表，常见的基本运算有：
（1）置空表setnull(L)，这是一个过程，其结果是将线性表L置为空表。
（2）求长度length(L)，这是一个函数，返回值为线性表L的长度。
（3）取得表中第i个元素get(L,i)，这是一个函数，当1≤i≤length(L)时，返回第i个数据
元素。
（4）取直接前趋prior(L,a )，这是一个函数，当2≤i≤length(L)时，返回a 的直接前趋
i
i
a 。
i-1
（5）取直接后继next(L,a )，这是一个函数，当1≤i≤length(L)-1时，返回a 的直接后继
i
i
a 。
i+1
（6）根据特定值查找线性表locate(L,x)，这是一个函数，若线性表中存在值为x的数据
元素a 时，则返回i值，即a 在线性表中的序号；若存在多个值为x的数据元素a 时，则i为其
i
i
i
序号最小的值；若不存在值为x的数据元素，则返回值零。
（7）插入数据元素insert(L,x,i)，这是一个过程，是将新数据元素x插入到数据元素a 之
i
前，因此当1≤i≤length(L)+1时有意义，运算的结果使长度为n的线性表变为长度为n+1的
线性表。
（8）删除操作delete(L,i)，这是一个过程，当1≤i≤length(L)时，将线性表L中第i个数
据元素删除，使长度为n的线性表变为长度为n-1的线性表。
以上这些数据的运算是定义在逻辑结构上的抽象运算，至于如何实现要待确定了数据
的存储结构之后再考虑。

3.1.2 线性表的应用

对事物进行信息化管理时，通常需要先根据管理目的或需求提取事物的相关属性，将
该属性下的信息借助表格进行存储、组织，以便后期使用。如第二章的表2-2呈现的超市

某年每月奶粉销量记录就是一个线性表，超市基于记录和查询奶粉每阶段销售情况的目

63 63

21X2204.indd 63 2019/9/26 13:53:15