随笔-14  评论-142  文章-0  trackbacks-0
线性表 :
是 n(n>=0) 个相同特性数据元素的有序序列 .
  顺序存储结构和实现
线性表的顺序存储结构 , 可以随机存取 . 逻辑上相邻的两个元素 , 在物理存储上也是相邻的 . 顺序存储表示 :
( 见源代码 ) 基本操作在顺序表上的实现
( 见源代码 )
四大基本操作 :
(1)    构造一个空的线性表
( 简单 )
(2)    顺序表的插入算法 .
算法分析 :
时间主要耗费在移动元素上 , 与问题的规模 (N) 和你插入元素的具体位置有关 , 即插入元素位置越靠近 , 位序 1, 消耗的时间也就越多 . 设在位序 i 插入元素的概率位 pi=1/(n+1), 移动元素的个数为 ,(n-i+1):
      那么在长度为 n 的顺序表中 , 插入一个元素 , 所需移动元素的期望值为 :
      E = ∑ P i*(n-i+1)     (i=1,2,3,..,n+1)
       =n/2;
平均移动表中的一半元素 . 时间复杂度 O( n )
(3)    顺序表的删除算法 .
算法分析 :
同上 , E = ∑ q i*(n-i)     (i=1,2,3,..,n+1) qi=1/n
        =(n-1)/2;
时间复杂度为 O (n);
(4)    定位算法 .
算法分析 :
基本操作是进行两个元素之间的比较 , 假设存在该元素为 a i( 1 ≤ i ≤ n), 则比较的次数为 i, 否则为 n, 所以算法时间复杂度为 O(n); 顺序存储结构的性能小结 :
优点 :
(1)    可以随机存取 , 顺序表中的数据元素 .
(2)    存储空间连续 , 不必要增加额外的存储空间 . 比如如果你以链式结构存储 , 那么你就不得不增加一个指针域 .
缺点 :
(1) 插入和删除一个元素 , 需要移动大量元素 , 耗费时间 .
(2) 初始化顺序表的时候 , 要预先分配一个最大空间 . 有时候会使存储空间得不到充分利用 .
(3) 容量难以扩充 .
posted on 2006-06-15 17:25 liulang 阅读(1438) 评论(0)  编辑  收藏

只有注册用户登录后才能发表评论。


网站导航: