2011计算机等考二级公共基础知识讲义：第1章(3)

　　点击进入：2011计算机等考二级公共基础知识讲义汇总>>

　　1.3 线性表及其顺序存储结构

　　1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。

　　*：线性表是一种存储结构，它的存储方式：顺序和链式。

　　2、线性表的顺序存储结构具有两个基本特点：(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

　　*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i个结点的存储地址。

　　3、顺序表的插入、删除运算(学吧学吧独家稿件)

　　(1)顺序表的插入运算：在一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个(即第n个)元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。

　　*：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。

　　(2)顺序表的删除运算：在一般情况下，要删除第i(1≤i≤n)个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。

　　*：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动(n-1)/2个元素。插入、删除运算不方便。

　　相关推荐：

　　2011计算机等考二级公共基础知识要点汇总

　　2010年9月计算机等级考试成绩查询时间汇总

　　2011年上半年计算机等级考试报名时间汇总