计算机二级公共基础知识辅导讲义第一章（3）

会计考友

　　1.3 线性表及其顺序存储结构
　　1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。
- G, P0 j  `0 U$ _# }1 [　　*：线性表是一种存储结构，它的存储方式：顺序和链式。
　　2、线性表的顺序存储结构具有两个基本特点：（1）线性表中所有元素所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
) U% s; _6 m/ p　　*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i个结点的存储地址。
　　3、顺序表的插入、删除运算（学吧学吧独家稿件）
2 Y; Q% B7 W/ s- Y0 y　　（1）顺序表的插入运算：在一般情况下，要在第i（1≤i≤n）个元素之前插入一个新元素时，首先要从最后一个（即第n个）元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。
1 V* M, D$ _" e4 a9 d  Q5 I5 R　　*：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。
+ \* y: P8 x1 u$ k$ b' Q" ]　　（2）顺序表的删除运算：在一般情况下，要删除第i（1≤i≤n）个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。
' x/ B+ i* ~5 |5 O7 F3 q+ g　　*：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动（n-1）/2个元素。插入、删除运算不方便。