当前位置 首页 > 考研资讯 正文

1.1 线性表的定义和基本操作

1.1 线性表的定义和基本操作

1.1 线性表的定义和基本操作

  线性表就是一串元素的有序排列,它是最基础的数据结构,应用非常广泛,能够进行初始化、查找、插入、删除、更新和遍历等多种操作。

1.1.1 线性表的逻辑定义与特征

  线性表是一种典型的线性结构,由n(n≥0)个有序的数据元素(结点)组成。例如,从2001年到2010年的年份按顺序排列就是一个线性表(简称“年份线性表”):
(2001,2002,2003,2004,2005,2006,2007,2008,2009,2010)
  1.线性表的定义
  线性表可定义为n个数据元素组成的序列:

(a1,a2,a3,...,an

  ① 数据元素的个数n为线性表长。如果n=0,即线性表中无数据元素,则称此线性表为空表。
  ② 每个数据元素在线性表中都有一个位置,线性表可以看成是由“位置+数据元素”组成的集合,这个位置决定了各数据元素在线性表中的前驱元素和后继元素。定义ai(1≤i≤n)为线性表中第i个位置上的元素,或者称为线性表的第i个元素。
  线性表中数据元素的位置随着线性表插入(或删除)元素的操作而发生变化。当插入数据元素后,原线性表中插入位置及其之后的所有元素在新表中的位置都增加1。同理,当删除数据元素后,原线性表中删除位置之后的所有元素在新表中的位置都减少1。
  ③ 若线性表中存在两个相连的数据元素组成的序偶对<ai-1,ai>,则称ai-1是ai的直接前驱(元素),ai是ai-1的直接后继(元素)。
  ④ 数据元素a(1≤i≤n)只是一个抽象符号,它既可以是单数据项,也可以由多个数据项组成。例如,表1-1所示的学籍成绩花名册线性表就是一个多数据项元素线性表的例子,它的每个数据元素由学号、姓名、语文、数学、英语、总分和平均分7个数据项组成。

表1-1 学籍成绩花名册线性表示例

学    号 姓    名 语    文 数    学 英    语 总    分 平  均  分
1 张三 90 100 70 260 86.67
2 李四 80 80 65 225 75.00
3 王五 85 60 90 235 78.33
4 姚六 50 90 55 195 65.00
…… …… …… …… …… …… ……

  2.线性表的特征
  线性表或者为空,或者具有如下特性:
  ① 有且仅有一个“头”数据元素。例如,年份线性表的“2001”。
  ② 有且仅有一个“尾”数据元素。例如,年份线性表的“2010”。
  ③ 除“头”数据元素外,线性表中的每个元素有且仅有一个直接前驱。例如,年份线性表中的“2009”的直接前驱是“2008”。
  ④ 除“尾”数据元素外,线性表中的每个元素有且仅有一个直接后继。例如,年份线性表中的“2007”的直接后继是“2008”。
  3.特殊的线性表
  特殊线性表有空表和长度为1的表。
  ① 空线性表。没有数据元素的线性表是空线性表,此时,线性表既没有头数据元素,也没有尾数据元素。
  ② 长度为1的线性表。线性表中只有一个数据元素,此元素既是该线性表的头数据元素,也是其尾数据元素,它没有前驱,也没有后继。

1.1 线性表的定义和基本操作

本文来自网络,不代表大媒体立场,转载请注明出处。
留言与评论(共有 0 条评论)
   
验证码:
© Copyright Powered by 考研网. 京ICP备18012533号 .
联系我们

联系我们

0000-123456789

在线咨询: QQ交谈

邮箱: email@123456.com

工作时间:周一至周五,9:00-17:30,节假日休息

关注微信
微信扫一扫关注我们

微信扫一扫关注我们

关注微博
返回顶部