0


Python数据结构与算法(2.1)——线性表的基本概念

Python数据结构与算法(2.1)——线性表的基本概念

0. 学习目标

线性表是应用最为广泛的一种数据结构,如其名所示,是一种典型的线性结构。本节主要介绍线性表的有关概念和基本运算。
通过本节学习,应掌握以下内容:

  • 线性表的定义
  • 线性表的逻辑结构

1. 线性表的定义

线性表 (Linear List) 是最基础也是最常用的数据结构,是有

    n
   
   
    (
   
   
    n
   
   
    ≥
   
   
    0
   
   
    )
   
  
  
   n(n≥0)
  
 
n(n≥0) 个具有相同属性的数据元素组成的有限序列。序列中元素的个数 

 
  
   
    n
   
  
  
   n
  
 
n 称为线性表的长度,当 

 
  
   
    n
   
   
    =
   
   
    0
   
  
  
   n=0
  
 
n=0 时称为空表,即不含有任何元素。非空线性表L可以用以下形式表示:

 
  
   
    
     L
    
    
     =
    
    
     (
    
    
     
      a
     
     
      1
     
    
    
     ,
    
    
     
      a
     
     
      2
     
    
    
     ,
    
    
     …
    
    
     ,
    
    
     
      a
     
     
      i
     
    
    
     ,
    
    
     
      a
     
     
      
       i
      
      
       +
      
      
       1
      
     
    
    
     ,
    
    
     …
    
    
     ,
    
    
     
      a
     
     
      n
     
    
    
     )
    
   
   
    L=( a_1, a_2, …, a_i, a_{i+1}, …, a_n)
   
  
 L=(a1​,a2​,…,ai​,ai+1​,…,an​)

其中

     a
    
    
     i
    
   
   
    (
   
   
    1
   
   
    ≤
   
   
    i
   
   
    ≤
   
   
    n
   
   
    )
   
  
  
   a_i(1≤i≤n)
  
 
ai​(1≤i≤n) 表示 L 中的第 

 
  
   
    i
   
  
  
   i
  
 
i 个数据元素,下标 

 
  
   
    i
   
  
  
   i
  
 
i 为 

 
  
   
    
     a
    
    
     i
    
   
  
  
   a_i
  
 
ai​ 元素在线性表中的序号和位置。线性表中元素的顺序取决于添加顺序或移除顺序,某个元素被添加到线性表中后,它与前后元素的相对位置将保持不变。在线性表中,把 

 
  
   
    
     a
    
    
     i
    
   
   
    (
   
   
    2
   
   
    ≤
   
   
    i
   
   
    ≤
   
   
    n
   
   
    )
   
  
  
   a_i(2≤i≤n)
  
 
ai​(2≤i≤n) 的前一元素 

 
  
   
    
     a
    
    
     
      i
     
     
      −
     
     
      1
     
    
   
  
  
   a_{i-1}
  
 
ai−1​ 称为 

 
  
   
    
     a
    
    
     i
    
   
  
  
   a_i
  
 
ai​ 的直接前趋,后一元素 

 
  
   
    
     a
    
    
     
      i
     
     
      +
     
     
      1
     
    
   
  
  
   a_{i+1}
  
 
ai+1​ 称为 

 
  
   
    
     a
    
    
     i
    
   
  
  
   a_i
  
 
ai​ 的直接后继,第一个元素 

 
  
   
    
     a
    
    
     1
    
   
  
  
   a_1
  
 
a1​ 称为表头元素,最后一个元素 

 
  
   
    
     a
    
    
     n
    
   
  
  
   a_n
  
 
an​ 称为表尾元素。

非空线性表的逻辑结构可以用下图来表示:
非空线性表的逻辑结构
由上图所示,我们不难发现非空线性表的逻辑结构具有如下特征:

  • 线性表中的数据元素是按前后位置有序的,即第 i i i 个数据元素 a i a_i ai​ 在逻辑上是第 i + 1 i+1 i+1 个元素 a i + 1 a_{i+1} ai+1​ 的直接前趋,第 i + 1 i+1 i+1 个数据元素 a i + 1 a_{i+1} ai+1​ 在逻辑上是第 i i i 个数据元素 a i a_i ai​ 的直接后继。
  • 线性表中第一个数据元素 a 1 a_1 a1​ 有且仅有一个直接后继而没有直接前驱,最后一个数据元素 a n a_n an​ 有且仅有一个直接前驱而没有直接后继。其余每个数据元素 a i ( 1 < i < n ) a_i(1<i<n) ai​(1<i<n) 有且仅有一个直接前驱,并且有且仅有一个直接后继。
  • 线性表中数据元素的类型是相同的,表长的取值是一个有限数,最小为 0。

线性表在现实世界的非常常见,例如:26个英文字母表——(a, b, c, …, z),可以视为一个线性表,其中每个字母是一个数据元素;植物进化的演化过程也可以用线性表的形式表示——(藻类植物, 裸蕨类植物, 蕨类植物, 裸子植物, 被子植物);在复杂的线性表中,一个数据元素可以由若干个数据项组成,一个学生基本信息表可以视为一个线性表,其中每个学生的所有相关信息组成一个数据元素(也可以称为记录,record),每个数据元素包含学号、姓名、性别、年龄、班级、联系方式等数据项。
由上述示例可以看出,在现实世界的不同的情况下,线性表的数据元素的具体内容虽不相同,但是都反映了数据元素之间的相对位置是线性的逻辑结构特性。

2. 线性表的操作

数据结构的操作是定义在逻辑结构层次上的,而操作的具体实现则是建立在存储结构上的。因此下面定义的线性表的基本操作作为逻辑结构的一部分,给出了这些操作的功能是“做什么”,至于“如何做”则依赖于选定什么样的存储结构。
顺序表的主要操作包括:

  • 初始化线性表:构造空的线性表
  • 计数:返回列表中的元素数
  • 按序号取元素:读取线性表指定位置的元素
  • 按值查找:在列表中查找指定的数据元素
  • 插入:在列表中插入一个元素
  • 删除元素:从列表中删除并返回指定的位置元素

3. 抽象数据类型线性表定义

综上所述,抽象数据类型线性表的定义如下:

ADT List:
 数据对象:

     D
    
    
     =
    
    
     
      
       a
      
      
       i
      
     
     
      ∣
     
     
      
       a
      
      
       i
      
     
     
      ∈
     
     
      D
     
     
      a
     
     
      t
     
     
      a
     
     
      T
     
     
      y
     
     
      p
     
     
      e
     
     
      ,
     
     
      i
     
     
      =
     
     
      1
     
     
      ,
     
     
      2
     
     
      ,
     
     
      .
     
     
      .
     
     
      .
     
     
      ,
     
     
      n
     
     
      ,
     
     
      n
     
     
      ≥
     
     
      0
     
    
   
   
    D={a_i|a_i∈DataType, i=1,2,...,n,n\geq0}
   
  
 D=ai​∣ai​∈DataType,i=1,2,...,n,n≥0

 数据关系:

     R
    
    
     =
    
    
     
      <
     
     
      
       a
      
      
       i
      
     
     
      ,
     
     
      
       a
      
      
       
        i
       
       
        +
       
       
        1
       
      
     
     
      >
     
     
      ∣
     
     
      
       a
      
      
       i
      
     
     
      ,
     
     
      
       a
      
      
       
        i
       
       
        +
       
       
        1
       
      
     
     
      ∈
     
     
      D
     
     
      ,
     
     
      i
     
     
      =
     
     
      1
     
     
      ,
     
     
      2
     
     
      ,
     
     
      .
     
     
      .
     
     
      .
     
     
      ,
     
     
      n
     
     
      −
     
     
      1
     
    
   
   
    R={<a_{i},a_{i+1}>|a_i,a_{i+1}∈D,i=1,2,...,n-1}
   
  
 R=<ai​,ai+1​>∣ai​,ai+1​∈D,i=1,2,...,n−1

 基本操作:
  1. itit(): 初始化线性表
   将线性表 L 置为空表
  2. len(): 求取并返回线性表所含元素的个数 n
   若线性表为空,则返回整数0
  3. getitem(i): 读取线性表 L 中第 i 个数据元素
   其中 1 ≤ i ≤ len(L)
  4. locate(x): 在线性表 L 中查找值为 x 的数据元素
   若查找成功则返回第一个值为 x 的元素的序号;否则,返回一特殊值(例如-1),表示查找失败
  5. insert(i, x): 在线性表 L 第 i 个位置上插入值为 x 的新元素
   其中 1 ≤ i ≤ len(L)+1,插入后表长增 1;原序号为 i, i+1, …, n 的数据元素的序号变为 i+1, i+2, …, n+1
  6. delitem(i): 在线性表 L 中删除序号为 i 的数据元素
   其中 1 ≤ i ≤ len(L),删除后表长减 1;原序号为 i+1, i+2, …, n 的元素变为序号 i, i+1, …, n-1

以上只给出了定义在线性表逻辑结构上的最基本运算,在实际应用中可借助于这些基本运算构造出更为复杂的运算。


本文转载自: https://blog.csdn.net/LOVEmy134611/article/details/121192629
版权归原作者 盼小辉丶 所有, 如有侵权,请联系我们删除。

“Python数据结构与算法(2.1)&mdash;&mdash;线性表的基本概念”的评论:

还没有评论