数据结构顺序表的查找_数据结构 2.1顺序表

线性结构是数据结构中最基础、最简单的一种数据结构类型，其中最典型的就是线性表

线性表的定义

具有「相同特性」的数据元素的「有限序列」

相同特性	所有元素属于同一数据类型
有限	数据元素个数是有限的
序列	数据元素由逻辑序号唯一确定

❝

用逻辑序号来确定的特性使得线性表中可以有多个相同值的元素

❞

线性表中所含元素的个数叫做线性表的长度，用

n

表示(

n

≥ 0)

当

n

= 0时，表示线性表是一个空表，即表中不包含任何元素

线性表的逻辑表示

线性表的逻辑表示为：

表示第个元素为逻辑位序

线性表的基本运算

1. 初始化线性表：构造一个空的线性表

   l

2. 建立线性表
3. 销毁线性表：释放线性表

   l

   占用的内存空间
4. 判线性表是否为空表：若为空返回

   1

   ，不为空返回
5. 求线性表的长度：返回元素个数

   n

6. 输出线性表：当线性表

   l

   不为空时，顺序输出

   l

   的每一个元素
7. 求线性表

   l

   中指定位置的某个数据元素：用

   e

   返回

   l

   中第

   i

   个元素的值
8. 定位查找：返回

   l

   中第一个与

   e

   相等的逻辑位序
9. 插入一个数据元素：在

   l

   的第

   i

   个元素之前插入新的元素

   e

   ，

   l

   的长度

   +1

10. 删除数据元素：删除

    l

    的第

    i

    个元素，并用

    e

    返回其值，

    l

    的长度

    -1

线性表的顺序存储结构

把线性表中所有的元素按照顺序的方法进行存储。所有元素按逻辑顺序依次存储到存储器中「一片连续的存储空间」中

顺序表类型定义

顺序表运算的实现

初始化线性表

建立线性表

销毁线性表

判断是否为空表

求线性表的长度

当线性表不为空时，顺序显示L中各元素的值

求某个数据元素值

❝

getElem()

的时间复杂度为

O(1)

。体现了顺序表的「随机存取特性」

❞

按元素值查找

插入数据元素

在插入之前，已有的元素要给新来的元素腾出空间，后面的元素都要向表尾移动一位。最后表的长度

+1

在第二个位置插入元素5

• 当

  i = n+1

  时，元素移动次数为 ，最好时间复杂度为

  O(1)

• 当

  i = 1

  时，元素移动

  n

  次，最坏时间复杂度为

  O(n)

线性表中有

n+1

个可以插入元素的地方，在插入元素

ai

时，若为等概率情况，则

此时需要将

ai

到

an

的元素均向后移动一个位置，共移动

n-i+1

个元素

所以在长度为

n

的线性表中插入一个元素时所需移动元素的平均次数为

因为插入算法主要花的时间就在移动元素上，因此插入算法的平均时间复杂度为

O(n)

删除元素

用后面的元素覆盖被删除元素，同时都向表头移动。最后「表的长度-1」

删除第二个位置的元素

对于本算法来说，元素移动的次数也与表长

length

和删除元素的位置

i

有关：

• 当

  i = n

  时，移动次数为 ，最好时间复杂度为

  O(1)

• 当

  i = 1

  时，移动次数为

  n-1

  ，最坏时间复杂度为

  O(n)

在线性表

l

中共有

n

个可以删除元素的地方，在删除元素

ai

时，若为等概率情况，则

此时需要将

a(i+1)

和

an

的元素均前移一个位置，共移动

n-(i+1)+1

=

n-i

个元素

平均时间复杂度为

O(n)