等级考试公共基础考点分析之数据结构与算法(5)

文章作者 100test 发表时间 2007:03:10 16:45:55
来源 100Test.Com百考试题网

1.3 线性表及顺序存储结构
考点6 线性表的定义
　　线性表是n(n≥0)个元素构成的有限序列(a1，a2，…，an)。表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。即线性表是一个空表，或可以表示为
(a1，a2，…，an)
　　其中ai(i=1，2，…，n)是属于数据对象的元素，通常也称其为线性表中的一个结点。
　　其中，每个元素可以简单到是一个字母或是一个数据，也可能是比较复杂的由多个数据项组成的。在复杂的线性表中，由若干数据项组成的数据元素称为记录(record)，而由多个记录构成的线性表又称为文件(file)。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。非空线性表有如下一些结构特征：
(1)有且只有一个根结点a1，它无前件；
(2)有且只有一个终端结点an，它无后件；
(3)除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。线性表中结点的个数n称为线性表的长度。当n=0时称为空表。
考点7 线性表的顺序存储结构
　　线性表的顺序表指的是用一组地址连续的存储单元依次存储线性表的数据元素。
　　线性表的顺序存储结构具备如下两个基本特征：
　(l)线性表中的所有元素所占的存储空间是连续的；
(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
　　假设线性表的每个元素需要占用k个存储单元，并以所占的存储位置ADR(ai 1)和第i个数据元素的存储位置ADR(ai)之间满足下列关系：
　　ADR(ai 1)=ADR(ai) k
　　线性表第i个元素ai的存储位置为
　　ADR(ai)=ADR(a1) (i-1)×k
　　式中ADR(ai)是线性表的第一个数据元素a，的存储位置，通常称做线性表的起始位置或基址。
　　线性表的这种表示称做线性表的顺序存储结构或顺序映像，这种存储结构的线性表为顺序表。表中每一个元素的存储位置都和线性表的起始位置相差一个和数据元素在线性表中的位序成正比例的常数。如图1-4所示。由此只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。