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

会计考友

1.3 线性表及其顺序存储结构　　1、线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。线性表是由n(n≥0)个数据元素组成的一个有限序列，表中的每一个数据元素，除了第一个外，有且只有一个前件，除了最后一个外，有且只有一个后件。线性表中数据元素的个数称为线性表的长度。线性表可以为空表。
　　*：线性表是一种存储结构，它的存储方式：顺序和链式。
7 w4 h) {" C% ]. V( @9 D　　2、线性表的顺序存储结构具有两个基本特点：(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。
2 Z) C6 C- w5 j3 N$ l* M5 m* d/ Z　　*：由此可以看出，在线性表的顺序存储结构中，其前后件两个元素在存储空间中是紧邻的，且前件元素一定存储在后件元素的前面，可以通过计算机直接确定第i个结点的存储地址。
　　3、顺序表的插入、删除运算(学吧学吧独家稿件)
8 I* D' ]; W4 s: ~) d　　(1)顺序表的插入运算：在一般情况下，要在第i(1≤i≤n)个元素之前插入一个新元素时，首先要从最后一个(即第n个)元素开始，直到第i个元素之间共n-i+1个元素依次向后移动一个位置，移动结束后，第i个位置就被空出，然后将新元素插入到第i项。插入结束后，线性表的长度就增加了1。
( V" V0 G9 l9 c　　*：顺性表的插入运算时需要移动元素，在等概率情况下，平均需要移动n/2个元素。
/ o, T0 a2 i, y　　(2)顺序表的删除运算：在一般情况下，要删除第i(1≤i≤n)个元素时，则要从第i+1个元素开始，直到第n个元素之间共n-i个元素依次向前移动一个位置。删除结束后，线性表的长度就减小了1。
3 D" h+ A2 p! N" k　　*：进行顺性表的删除运算时也需要移动元素，在等概率情况下，平均需要移动(n-1)/2个元素。插入、删除运算不方便。