线性表是具有n个的有限序列()的有限序列

来源：蜘蛛抓取(WebSpider) 时间：2018-09-12 10:52 标签： 线性表是具有n个的有限序列

百度题库旨在为考生提供高效的智能备考服务，全面覆盖中小学财会类、建筑工程、职业资格、医卫类、计算机类等领域。拥有优质丰富的学习资料和备考全阶段的高效服务，助您不断前行！

线性表：由n(n>=0)个具有相同类型的元素组成的优有限序列。除第一个元素外，每个元素有且只有一个直接前驱，除最后一个元素外，每个元素有且只有一个直接后继。

按存储结构可分为定长的顺序存储结构（即顺序表）和变长的现行存储结构（即链表）。

使用C语言描述线性表数据结构。

1、  特点：顺序表通过创建数组来建立，为线性表分配一块连续的存储空间，线性表中的数据元素顺序地存储在这些地址连续的空间中，即所谓的逻辑相邻，物理相邻。

2、设每个数据元素占用d个存储空间，第一个元素内存地址为Loc(a1)，则第i个数据元素的内存地址为Loc(ai)+d(i-1)

3、  定义一个线性表：

用数组实现顺序表的存储结构，由于在实际操作中，要进行删除、插入等相关操作，即顺序表的长度是可变的，因此数组的容量需设计得足够大，用data[MAXSIZE]表示，顺序表中的数据元素从data[0]开始存放，采用变量last来记录当前线性表中最后一个元素在数组中的位置。因此，当last=-1时，就是一个空表。

//顺序表定义，包括一个表示最后元素的位置的last，和类型为elemtype的数组

插入时，确保顺序表有空闲的存储空间（判满）；确保插入位置合法；插入完成后，有关数据元素后移，数组长度加1.

判断删除位置是否合法，删除位置i+1~n后移，数组长度减1.

由于顺序表是通过数组来建立存储结构，因此可通过下标值直接访问一个数据元素，其时间复杂度为O(1)。

从第一个数据元素开始，扫描顺序表，直至数据元素等于所要查找的值，返回数组下标。时间复杂度为O(n)。

方便随机访问表中的每一个元素；

不需要再为表示结点间的逻辑关系而增加额外的空间。

线性表（linear list） 是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

  • 线性表的相邻元素之间存在着序偶关系。a1是a2的前驱，ai+1 是ai的后继，a1没有前驱，an没有后继
  • n为线性表的长度 ，若n==0时，线性表为空表
  • 存储结构：1. 数序存储结构 2. 链式存储结构
缺点：插入和删除效率慢

在JAVA里面基本的顺序存储结构线性表是数组，ArrayList是基于它来完成对象的存储，来分析一下ArrayList(Android里面的)的源码

从初始化的过程可以很明显的看出来，就是对内部的一个`数组`对象`elementData `进行初始化。

add()的时候先判断当前数据容量是否足够，如果不足够那么扩容，扩容的值等于当前数组长度右移一位，也就是x2，然后添加到指定位置即可。 addAll()也是同样的方式，在这就不贴代码，可以自行查看一下源码。

remove过程就是得到对应的值的下标，然后将该下标之后的数据都向前移动一个坐标，最后一个赋值为null

set()直接将其赋值即可

get()就直接将数组里面值取出来即可。

从源码的角度我们更加的熟悉了顺序线性表的优缺点：查询很快，插入和删除效率慢。

特点:用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。 

优点：插入和删除效率高
 

 插入和删除只需改变next指向的地址即可，所以增删效率比较高。
 
 

 如上图那样，如果需要查找第9个元素，那么将要从第一个一直指向第九个，所以查找效率低。
 
 

 链式存储结构又包含循环链表、双向循环链表、单向循环链表等。 单向循环链表就是上图那样的,一个指针对应下一个指针，直到结束，就如上面的那张图所示。 循环链表 : 将单链表中终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相连的单链表称为单循环链表，简称循环链表
 
 

 双向循环链表: 双向循环链表是单向循环链表的每个结点中，再设置一个指向其前驱结点的指针域
 
 

 
 

 在LinkedList里面有一个Node类，这个类就是用来确定上一个指针prev和下一个指针next
 
 

 
 
 

 可以很直观的看出，add的时候，将new出一个新的Node对象newNode，然后把上一个Node对象last的next指向它，然后又将last重新赋值。当指定位置add的时候，就需要先找个这个位置的Node对象，然后更改next和prev即可。在指定下标插入的话那么将先判断这个下标是在前半段还是后半段，如果是前半段的话就从头开始next遍历查找，如果是后半部的就从尾prev遍历。add操作如下图所示
 
 

 
 

 和add差不多，找出相应的Node对象，然后重新对前后的Node重新进行指向即可。
 
 

 remove主要操作所下图所示
 
 

 
 

 判断这个下标是在前半段还是后半段，如果是前半段的话就从头开始next遍历查找，如果是后半部的就从尾prev遍历。
 
 

 
 

 先查找Node,然后重新赋值即可。
 
 
 

 水平有限，文中有什么不对或者有什么建议希望大家能够指出，谢谢！

我要回帖

更多关于 线性表是具有n个的有限序列 的文章

 

随机推荐