数据结构学习笔记——线性表(上)

线性表:零个或多个数据元素的有限序列。

线性表的定义

线性表,从名字上可以感觉到,是具有像线一样的性质的表

官方定义: 线性表(List):零个或多个数据元素的有限序列

注意;

  • 首先它是一个序列。也就是说,元素之间是有序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素有且只有一个前驱和后继。
  • 线性表强调有限,元素个数是有限的。

其结构如下图:

线性表元素的个数n(n≥0)定义为线性表的长度,当n=0时,称为空表。在非空表中的每个元素都有一个确定的位置,如a1是第一个元素,an是最后一个元素,ai是第i各元素,i称为数据元素ai在线性表中的位序。

在较复杂的线性表中,一个元素可以由若干个数据项组成。

线性表的顺序存储结构

1、顺序存储定义

线性表的顺序存储结构,指的是用一段地址连续的存储单元依次存储线性表的数据元素。

这里强调两点:

  1. 地址连续
  2. 与线性表顺序一致

如图:

2、顺序存储方式

通俗地讲,线性表的顺序存储结构,就是在内存中找块地儿,通过占位的形式,把一定的内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地。

可以用一个一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置,接着把线性表相邻的元素存储在数组中相邻的位置。

我们发现描述存储结构三个重要的属性:

  • 存储空间的起始位置;
  • 线性表的最大存储容量;
  • 线性表的当前长度。

3、数组长度与线性表长度区别

  • 数组长度:定义数组时,已经开辟了固定大小的空间,一般不变;
  • 线性表长度:线性表中数据元素的个数,随着插入和删除的操作,这个量是变化的。

所以:线性表长度≤数组长度

4、地址计算方法

线性表的第i各元素存储在数组下标为i-1的位置,如下图:

这个图也体现了数组长度和线性表长度的关系。用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行插入和删除操作,因此分配的数组长度空间应该大于等于当前线性表的长度。

存储器中的每个存储单元都有自己的编号,这个编号叫做地址。

顺序结构的插入删除

1、获得元素操作

对于线性表的顺序存储结构来说,我们要实现getElem操作,即将线性表L中的第i个元素值返回,直接将数组第i-1下标的的值返回即可。

如果已知第一个元素的地址,和每个元素所占内存大小,即可算出第i个元素的内存地址,时间复杂度为O(1)。

2、插入操作

插入算法思路:

  • 如果插入位置不合理,抛出异常;
  • 如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
  • 从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
  • 将要插入的元素填入位置i处;
  • 表长加1。

3、删除操作

删除算法思路:

  • 如果删除位置不合理,抛出异常;
  • 取出删除元素;
  • 从删除位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
  • 表长减1。

4、操作整理

  • 读取、存入数据: O(1)
  • 插入、删除数据: O(n)

总的来说,线性表的顺序存储结构:读取快,增删慢

5、优缺点

优点

  • 无须为表示表中元素之间的逻辑关系而增加额外的存储空间;
  • 可以快速地存取表中任意一个位置的元素;

缺点

  • 插入和删除操作需要移动大量的元素;(最大缺点)
  • 当线性表长度变化较大时,难以确定存储空间的容量;
  • 容易造成存储空间的“碎片”。

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

LintCode 子数组之和题目分析代码

给定一个整数数组,找到和为零的子数组。你的代码应该返回满足要求的子数组的起始位置和结束位置

632
来自专栏Java后端技术栈

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

1232
来自专栏JAVA高级架构

Java HashMap 遍历方式性能探讨

关于HashMap的实现这里就不展开了,具体可以参考 JDK7与JDK8中HashMap的实现 JDK8之前,可以使用keySet或者entrySet来遍历Ha...

43112
来自专栏Jack的Android之旅

疯狂java笔记之线性表

从数据的逻辑结构来分,数据元素之间存在的关联关系被称为数据的逻辑结构。归纳起来,应用程序中的数据大致哟如下四种基本的逻辑结构。

1092
来自专栏Android开发小工

Java集合解惑

本文取自工匠若水的qq群里的Java基础题目,把里面有关Java集合放在一起。 全文github地址

1262
来自专栏Android机动车

数据结构学习笔记——线性表(下)

了解过线性表的链式存储结构以后,有人就想出来用数组来代替指针,来描述单链表。看看他们是怎么做到的。

491
来自专栏工科狗和生物喵

【计算机本科补全计划】Java学习笔记(九) Java日期时间

### 1、 Java 日期时间 java.util 包提供了 Date 类来封装当前的日期和时间。 Date 类提供两个构造函数来实例化 Date 对象。第一...

942
来自专栏令仔很忙

集合详解(三)----Map的两种遍历方式

Map是以键值对(key-value)的方式来存取值的,那么该怎么把Map中的值取出来的,有两种方式,往下看。先定义一个Map,向里面存放一些数据。

802
来自专栏开发之途

Java集合框架源码解析之LinkedHashMap

1243
来自专栏好好学java的技术栈

”365算法每日学计划”:02打卡-线性表(赠书活动第①期预告)

1323

扫码关注云+社区

领取腾讯云代金券