当前位置:首页 > 百科

线性表

线性表是最基本、最简单、也是最常用的一种数据结构来自

线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储),但是把最后一个数何则分交陈操据元素的尾指针指向了首位结点)

我们说"线性"和"非线性",只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。

在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的"线性表",可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。

线性表的逻辑结构简单,便于实现和操作。因此,线性表这种数据结构在实际应用中是广泛采用的一种数据结构。

  • 中文名 线性表
  • 外文名 linear list
  • 元素关系 一对一
  • 类别 一般线性表和受限线性表

定义

  线性表(linear list)属扬数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体来自含义在不同的情况下一般不同。

  在稍复杂的线性表中,一个数据元素可由多个数据项(item)组成,此种情况下常把数据元素称为记录(record),含有大量记录的线性表又称文件(file)

  线性表中的个数n定义为线性表的长度,n=0时称为空表。在非空表中每个数据元素都有一个确定的位置,如用ai表示数据元素,则i称为数据元素360百科ai在线性表中的位序。

  线性表的相邻元素之间存在着序偶关系。如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序较具革益否等掌素表,则表中ai-1领先于a举行盾延以民能段演背粮i,ai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱 。

特征

  1.集合中必存在唯一的一字学需步甚困精那个"第一元素"。

  2.集合中必存在唯一的一个 "最后元素" 。

  3.除最后一个元素之外,均有 唯一土属入倍仍激政课损的后继(后件)。

  4.除第一强试触敌台草技个元素之外,均有 端聚与管家些低衡顾持侵唯一的前驱(前件)。

基本操作

  1)MakeEmpty(L) 这是一个将L变为空表的方法

  2)Length(L) 返回表L的长度,即表中元素个数

  3)Get(L,i) 这是一个函数,函数值为L中位置i处的元素(1≤i≤n)

  4)Prior(L来自,i) 取i的前驱元素

  5)Next(L,i) 取i的后继元素

  6)Locate(L,x) 这是一个函数,函数值为元素x在怀统治L中的位置

  7)Insert(L,i,x)在表L的位置i处插入元素x,将原占据位置i的元素及岩决完象茶销应尽务取后面的元素都向后推一个位置

  8)Delete(L,p) 从表L中删除位置p处的元素

  9)IsEmpty(L) 如果表L为空表(长度为360百科0)则返回true,否则返回false

  10)Clear(L)清除所有元素

  11)Init(L此尽别宣践穿屋食)同第一个,初始化线性表为空

  12)Traverse(L)遍历输出所有元素

  13)Find(L,x)查找并返回元素

  14)Update(L规希弦织欢,x)修改元素

  15)Sort(L)对所有元素重新按给定的条件排序

  16) strs我观响兰优tr(string1,string2)用于字符数组的求string1中出现string2的首地址

存储结构

  线性表主要由顺序表示或链式表示。在实际应用中,常以栈、队列、字符串等特殊形式使用。

  顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序出州己重轻科映像(sequential mapping)。它以"物理位置相邻"来频欢实掉特念甲手间表示线性表中数据元素间的逻辑关系,可随机存取表中任一元素。

  链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。它的存储单元可以是连续的,也可以是不连续的。在表示数据元素之间的逻辑关系时,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置),这两部分信息组成数据元素的存储映像,称为结点(node)。它包括两个域;存储数据元素信息的域称为数据域;存储电理失真号父容局牛观着直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链 。

秋孙首具什身缺谈构特点

  1.均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。

  2.有序性:各数据元素在线性表中的位置只取决于它们的序号,数据元素之间的相对位置是线性的,即存在唯一的"第一个"和"最后一个"的数据元素,除了第一个和最后混律盐飞活装一个外,其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素(直接后继)。

线性表的推广

  时间有序表、排序表、和频率有序表都可以看海进用官造绿总探做是线性表的推广。如果按照结点到达结构的时间先新为后,作为确定结点之间关系的,这样一种线性结构称之为时间有序表。例如,在红灯前停下的一角创革粒情长串汽车,最先到达的为首结点,最后到达的为尾结点;在离开时最先到达的汽车将最先离开,最后到达的将最后离开。这些汽车构成理一个队列,实际上就是一个时间有序表。栈和队列都是时间有序表。频率有序表是按照结点的使用频率确定它们之间的相互关系的,而排序表是根据结点的关键字值来加以确定的去占以外含

声明:此文信息来源于网络,登载此文只为提供信息参考,并不用于任何商业目的。如有侵权,请及时联系我们:fendou3451@163.com
标签:

  • 关注微信
上一篇:分数乘除法
下一篇:新凤城

相关文章