数据结构：「顺序表基本操作」及其「时间复杂度分析」

C语言编程 06-01 188

前言：

而今你们对“c语言合并两个有序线性表”大约比较珍视，小伙伴们都想要了解一些“c语言合并两个有序线性表”的相关文章。那么小编在网摘上汇集了一些有关“c语言合并两个有序线性表””的相关文章，希望你们能喜欢，你们一起来了解一下吧！

顺序表定义1，前言

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。其最大的特点就是：元素的逻辑顺序与其物理顺序相同。

线性表的顺序存储结构中任一元素都可以随机存取，并且注意：线性表中元素的位序是从1 开始的，而数组中元素的下标是从0 开始的。假定线性表的元素类型为 EleType ，则线性表的顺序存储类型可以描述为：

2，动态实现

1，结构定义：

2，初始化顺序表：

3，增加动态数组的长度：

顺序表上的基本操作1，插入操作（Listsert(&L,i,e)

在表L 中的第i 个位置上插入指定元素e 。以下采用的是“静态分配的方式实现。

以下给出实现的主要代码部分，便于我们阅读理解：

插入操作的时间复杂度分析：

通过观察以上代码，我们分析时间复杂度时只需要关注最深层循环语句的执行次数与问题规模n 的关系。即语句“L.data[j]=L.data[j-1];” 即可：

（1）最好情况：新元素插入到表位，不需要移动元素，i=n+1，循环0次；最好的时间复杂度为O(1)

（2）最坏情况：新元素插入到表头，需要将原有的n 个元素全都向后移动，i =1，循环n 次；最坏的时间复杂度为O(n);

（3）平均情况：假设新元素插入到任何一个位置的概率相同，概率为P=1/(n+1)。i=1，循环n 次；i =2 时，循环n-1次；i =3 ，循环n-2 次 ..... i =n+1 时，循环0 次。平均循环次数 =np+(n-1)p+(n-2)p+.....+1.p= n/2。即得平均时间复杂度= O(n)

提示：如果以上的分析i 的值和循环次数n 的关系不是太清楚，要回想下开头提到的线性表中元素的位序是从1 开始的，而数组中元素的下标是从0 开始的。

2，删除操作（ListDelete(SqList &L,int i,int &e)）

删除顺序表L 中的第i （1<=i<=L.length)个位置的元素，用引用变量e 返回。若输入的i 不合法，则返回false ；否则，将被删元素赋给引用变量e ，并将第i+1 个元素及其后的所有元素一次往前移动一个位置，返回true 。

下面给出部分代码，辅助我们理解阅读：

删除操作的是时间复杂度分析：

通过观察以上代码，我们分析时间复杂度时只需要关注最深层循环语句的执行次数与问题规模n 的关系。即语句“L.data[j-1]=L.data[j];” 即可：

（1）最好情况：删除元素，不需要移动其他元素，i=n，循环0次；最好的时间复杂度为O(1)

（2）最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动。i=1，循环n-1次；最坏时间复杂度= O(n)

（3）平均情况：假设删除任何一个元素的概率相同，及p=1/n，i=1，循环n-1次；i=2，循环n-2 次..... i=n 时，循环0次，故平均循环次数=(n-1)p+(n-2)p+.....+1.p=(n-1)/2.则时间复杂度为O(n)

3，按位查找（GetElem(L,i)）

获取表L 中第i 个位置的元素的值。下面给出一段简单的代码示例：

由于顺序表的各个元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i 个元素，这也就是随机存取特性的体现。因此其时间复杂度可得为 O(1)。