5)取数据元素 ListGet(L,i,x) int ListGet(Seqlist L, int i, DataType*x) {if(i<0‖i>L.size-1) printf("参数i合法!n"); return 0 else *x=Llisti; return 1
（5）取数据元素ListGet(L, i, x) int ListGet(SeqListL, int i, DataType *x) { if(i < 0 || i > L.size-1) { printf("参数i不合法!\n"); return 0; } else { *x = L.list[i]; return 1; } }
3顺序表操作的效率分析 时间效率分析: 算法时间主要耗在移动元素的操作上,因此计算时间复 杂度的基本操作(最深层语句频度) T(n)=O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置 若 L-SIze,则根本无需移动(特别快); 若≠=0,则表中元素全部要后移(特别慢); 应当考虑在各种位置插入(共n+1种可能)的平均移动次 数才合理
3.顺序表操作的效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时间复 杂度的基本操作(最深层语句频度) T(n)= O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i. 若i=size，则根本无需移动（特别快）； 若i=0，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次 数才合理
设P是在第诠个存储位置插入一个数据元素的概率,顺序 表中的数据元素个数为n当在顺序表的任何位置上插入数 据元素的概率相等时,有P=1(n+1),则 插入时的平均移动次数为: n(n+1)2÷ (n+1)=n/2≈O(n) ∑P(m-1)=-;(n-) n+ 同理可证:顺序表删除一元素的时间效率为: T(n)=(n-1)/2≈O(m) En=∑q(n-)=∑(n-) i=0 0
设Pi是在第i个存储位置插入一个数据元素的概率，顺序 表中的数据元素个数为n,当在顺序表的任何位置上插入数 据元素的概率相等时，有Pi=1/(n+1),则 插入时的平均移动次数为: n(n+1)/2÷ （n+1）＝n/2≈O(n) 同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 ≈O(n) 0 0 1 ( ) ( ) 1 2 n n is i i i n E p n i n i = = n = − = − = + 1 1 0 0 1 1 ( ) ( ) 2 n n dl i i i n E q n i n i n − − = = − = − = − =
顺序表中的其余操作都和数据元素个数n无关,因此,在 顺序表中插入和删除一个数据元素的时间复杂度为O(m),其余 操作的时间复杂度都为O(1) 主要优点是算法简单,空间单元利用率高 主 要 优〈主要缺点是需要预先确定数据元素的最大 缺个数,插入和删除时需要移动较多的数据 点 元素
顺序表中的其余操作都和数据元素个数n无关，因此，在 顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余 操作的时间复杂度都为O(1) 主要优点是算法简单，空间单元利用率高； 主要缺点是需要预先确定数据元素的最大 个数，插入和删除时需要移动较多的数据 元素。 主 要 优 缺 点
4顺序表应用举例 例:编程实现如下任务:建立一个线性表,首先依次输 入数据元素1,2,3,…,10,然后删除数据元素5,最 后依次显示当前线性表中的数据元素。要求采用顺序表实 现,假设该顺序表的数据元素个数在最坏情况下不会超过 100个
4.顺序表应用举例 例：编程实现如下任务:建立一个线性表，首先依次输 入数据元素1，2，3，…，10，然后删除数据元素5，最 后依次显示当前线性表中的数据元素。要求采用顺序表实 现，假设该顺序表的数据元素个数在最坏情况下不会超过 100个