帐号: 密码: Cookie:   注册| 忘记密码 
  您的位置: 【卓安特保-山东卓安联网报警服务中心】山东卓安联网报警服务中心 >> 安防资讯 >> 卓安安防 >> JAVA编程
 阅读文章

线性表

  文章作者:网络来源:网络转摘浏览次数:395字体:字体颜色
 阅读权限:游客身份花费会员币:0添加时间:2020/4/11 22:29:23提交会员:李漠
本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。
线性表是最基本、最简单、也是最常用的一种数据结构。线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。
线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的(注意,这句话只适用大部分线性表,而不是全部。比如,循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储,但是把最后一个数据元素的尾指针指向了首位结点)。
中文名:线性表
外文名:linear list
元素关系:一对一
类    别:一般线性表和受限线性表
优    点:逻辑结构简单,便于实现和操作
应用学科:计算机科学、测绘科学、通信工程

目录

  1. 1 简介
  2. 定义
  3. 分类
  4. 优点
  1. 2 特征
  2. 3 基本操作
  3. 4 存储结构
  1. 5 结构特点
  2. 6 线性表的推广

线性表简介

线性表定义

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。
在稍复杂的线性表中,一个数据元素可由多个数据项(item)组成,此种情况下常把数据元素称为记录(record),含有大量记录的线性表又称文件(file)
线性表中的个数n定义为线性表的长度,n=0时称为空表。在非空表中每个数据元素都有一个确定的位置,如用ai表示数据元素,则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用(a1,…,ai-1,ai,ai+1,…,an)表示一个顺序表,则表中ai-1领先于aiai领先于ai+1,称ai-1是ai的直接前驱元素,ai+1是ai的直接后继元素。当i=1,2,…,n-1时,ai有且仅有一个直接后继,当i=2,3,…,n时,ai有且仅有一个直接前驱 [1]  。

线性表分类

我们说“线性”和“非线性”,只在逻辑层次上讨论,而不考虑存储层次,所以双向链表和循环链表依旧是线性表。
在数据结构逻辑层次上细分,线性表可分为一般线性表和受限线性表。一般线性表也就是我们通常所说的“线性表”,可以自由的删除或添加结点。受限线性表主要包括栈和队列,受限表示对结点的操作受限制。

线性表优点

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

线性表特征

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为空表(长度为0)则返回true,否则返回false
10)Clear(L)清除所有元素
11)Init(L)同第一个,初始化线性表为空
12)Traverse(L)遍历输出所有元素
13)Find(L,x)查找并返回元素
14)Update(L,x)修改元素
15)Sort(L)对所有元素重新按给定的条件排序
16) strstr(string1,string2)用于字符数组的求string1中出现string2的首地址

线性表存储结构

编辑
线性表主要由顺序表示或链式表示。在实际应用中,常以栈、队列、字符串等特殊形式使用。
顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素,称为线性表的顺序存储结构或顺序映像(sequential mapping)。它以“物理位置相邻”来表示线性表中数据元素间的逻辑关系,可随机存取表中任一元素。
链式表示指的是用一组任意的存储单元存储线性表中的数据元素,称为线性表的链式存储结构。它的存储单元可以是连续的,也可以是不连续的。在表示数据元素之间的逻辑关系时,除了存储其本身的信息之外,还需存储一个指示其直接后继的信息(即直接后继的存储位置),这两部分信息组成数据元素的存储映像,称为结点(node)。它包括两个域;存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针或链 [1]  。

线性表结构特点

编辑
1.均匀性:虽然不同数据表的数据元素可以是各种各样的,但对于同一线性表的各数据元素必定具有相同的数据类型和长度。
2.有序性:各数据元素在线性表中的位置只取决于它们的序号,数据元素之前的相对位置是线性的,即存在唯一的“第一个“和“最后一个”的数据元素,除了第一个和最后一个外,其它元素前面均只有一个数据元素(直接前驱)和后面均只有一个数据元素(直接后继)。

线性表线性表的推广

编辑
时间有序表、排序表、和频率有序表都可以看做是线性表的推广。如果按照结点到达结构的时间先后,作为确定结点之间关系的,这样一种线性结构称之为时间有序表。例如,在红灯前停下的一长串汽车,最先到达的为首结点,最后到达的为尾结点;在离开时最先到达的汽车将最先离开,最后到达的将最后离开。这些汽车构成了一个队列,实际上就是一个时间有序表。栈和队列都是时间有序表。频率有序表是按照结点的使用频率确定它们之间的相互关系的,而排序表是根据结点的关键字值来加以确定的。 [2] 
·上篇文章:JAVA关键字
·下篇文章:Java中创建对象的5种方式
复制 】 【 打印
 相关文章
没有相关文章
特别声明:本站除部分特别声明禁止转载的专稿外的其他文章可以自由转载,但请务必注明出处和原始作者。文章版权归文章原始作者所有。对于被本站转载文章的个人和网站,我们表示深深的谢意。如果本站转载的文章有版权问题请联系我们,我们尽快予以更正,谢谢。
关于我们 | 业务范围 | 免责声明 | 联系我们 | 友情连接
版权所有 Copyright © 2007 【卓安特保-山东卓安联网报警服务中心】山东卓安联网报警服务中心 All Rights Reserved.
鲁ICP备11024361号-5    页面执行时间:19.53MS