2011年计算机二级公共基础知识考点知识3

　　1.3.1线性表的基本概念 (P12—P13)

　　线性表是由n (n≥0)个数据元素a1，a2，…，an组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为。

　　(a1,a2,…,ai,…,an)

　　非空线性表有如下一些结构特征：

　　① 有且只有一个根结点a1，它无前件；

　　② 有且只有一个终结点an，它无后件；

　　③ 除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。

　　1.3.2线性表的顺序存储结构 (P13—P14)

　　在计算机中存放线性表，一种最简单的方法是顺序存储，也称为顺序分配。

　　线性表的顺序存储结构具有以下两个基本特点：

　　① 线性表中所有元素据所占的存储空间是连续的；

　　② 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

　　假设线性表中的第一个数据元素的存储地址为ADR(a1)，每一个数据元素占K个字节，则线性表中第i 个元素ai在计算机存储空间中的存储地址为

　　ADR(a1)=ADR(a1)+(i-1)K

　　1.3.3顺序表的插入运算 (P14—P15)

　　在平均情况下，要在线性表中插入一个新元素，需要移动表中一半的元素。因此，在线性表顺序存储的情况下，要插入一个新元素，其效率是很低的。

　　1.3.4顺序表的删除运算 (P15—P16)

　　在平均情况下，要在线性表中删除一个元素，需要移动表中表中一半的元素。因此，在线性表顺序存储的情况下，要删除一个元素，其效率也是很低的。

　　由线性表在存储结构下的插入与删除运算可以看出，线性表的顺序存储结构对于小线性表或者其中元素不常变动的线性表来说是合适的，因为顺序存储的结构比较简单。但这种顺序存储的方式对于元素经常需要变动的大线性表就不太合适了，因为插入删除的效率比较低。