每周学点大数据 | No.8基础数据结构之线性表

No.8期

基础数据结构之线性表

Mr. 王:为了以后的知识描述方便,这里简单介绍一下数据结构的概念。数据结构是一个广泛存在于计算机科学中的概念。曾经有一位计算机界的大师说:“数据结构+算法=程序”。随着计算机科学的发展,虽然现在这个理论被认为不够全面,但也足以说明数据结构的重要性。

小可:这么说,数据结构拥有和算法同样重要的地位了!那么数据结构究竟是什么呢?

Mr. 王:在客观世界中,信息是多种多样的,有数字、颜色、图形、文本、声音等。但是这些信息“本身”并不能直接存储在计算机中,而是要以数据的形式存储在计算机中。比如要描述一个颜色,就可以用显示器输出的红色、绿色、蓝色的值(RGB值)来表示;描述一张图片,就是用多个这样的RGB值或标识颜色的数据标签来记录的。不论何种类型的信息都要以数据的形式在计算机中进行表示。

不过,这些数据不能杂乱无章地存放在计算机中;否则,不仅损失了信息之间应有的逻辑关系,而且查找起来效率也比较低,所以我们就要试图去发现这些数据之间的一些相互关系,并且利用这些关系将数据组织成一种逻辑结构。这种结构就是数据结构,它研究的就是如何依照这些数据之间的逻辑关系将数据表示在计算机中。对于一组数据,我们不仅要关注它们的逻辑结构,也就是数据之间在逻辑上的相互关系,在实际使用时,还要关注它们的存储结构,也就是说,这些数据在内存(磁盘)中是如何存储的。这都是数据结构研究的范畴。

小可:既然有人说,程序等于数据结构加算法,那么数据结构和算法之间又有怎么样的关系呢?

Mr. 王:这是个很好的问题,计算机中的算法都要对数据进行处理,而既然要处理数据,就要涉及数据如何存储在计算机中,如何能够高效地访问和处理数据,这就需要用到数据结构,所以说算法离不开数据结构。而当我们需要使用、访问、添加、删除、修改存储在数据结构之中的数据时,也要依照数据结构的特点进行操作,而增加、删除、修改、查找这些操作本身就是一种算法,所以说数据结构也离不开算法。

小可:原来是这样,数据结构和算法之间的联系还真是紧密啊。

Mr. 王:下面我们就来介绍一下最基础的数据结构——线性表。

小可:线性表是不是就是这些数据一个挨着一个地线性存储的结构呢?

Mr. 王:是的,线性表是由相同类型的数据按照一定的顺序排成的序列。这是一种非常常见的基础数据结构,使用非常广泛。

小可:具体的线性表都有哪些呢?

Mr. 王:常见的线性表有链表、数组线性表、栈和队列。

小可:数组我知道! C语言和Java中就有,将同一类型的数据存储在连续的内存空间里,通过首地址和数组下标可以访问到数组中的每一个元素。嗯,数组果然是符合线性表的定义的。

Mr. 王:是的,数组就是一种典型的线性表。我们学过了算法分析,可以考虑一下,数组只要知道首地址和下标就可以找到一个元素,这意味着能够以O(1)的复杂度访问其中的每一个元素,从这个角度来看,数组也是具有其优势的。但是增加和删除其中的元素却比较麻烦,因为如果要在数组中间增加一个元素,需要将后面的元素全都向后移动一个位置,平均情况需要O(n)次移动数据,是非常耗时的。前面我们也讨论过,如果数组内容是无序存储的,查找其中某个特定的值就会比较困难,要逐个地去访问比较,需要O(n)的时间复杂度。从空间角度来讲,如果我们确定知道元素的数量,那么用数组会比较节省空间;但是对于那些不知道有多少个元素、需要频繁添加和删除的元素集合来说,就需要在定义数组时让它稍大一些,这就造成了空间浪费。

另外一种比较常见的线性结构是链表,它的构建是将元素一个一个地链接起来。访问链表时有一个首地址,我们可以通过这个首地址找到链表的第一个元素,这和数组是一样的;但和数组不一样的地方是,它的元素可能不连续地存储在空间中,而是每个元素的后面都带着一个地址,这个地址指向下一个元素的位置。我们想要逐个访问元素时,就要先找到第一个元素,通过第一个元素后面的地址找到第二个元素,然后再通过第二个元素后面的地址找到第三个元素,依此类推。

链表的例子

小可:那访问一个元素的时间复杂度就不是O(1)了,从平均情况来讲,访问一个元素的时间复杂度就是O(n)。

Mr. 王:很好,但是链表也并不是没有优点。链表的优点是,在一个特定的位置添加元素,并不需要移动任何元素的位置,只需要将其前面元素后面的地址指向新元素,再将新元素后面的地址指向前面元素原来的后面地址就可以了。删除也是一样,只需要将待删除元素前面元素的指针指向删除后面的元素,然后释放掉被删除元素的内存即可。

链表的插入操作

链表的删除操作

小可:这个时间复杂度是O(1)。

Mr. 王:这说明链表适合用于那些需要频繁进行添加、删除的元素集合。另外,从空间角度来讲,链表的长度相对比较灵活,它不像数组,即使那个位置是空的,也要占用预先申请的内存空间;而链表每有一个元素,就占用一个元素和它后面地址的存储空间,相对于元素数量变化幅度比较大的元素集合来说,链表的存储更加节省空间。

小可:嗯,果然是互补的两种结构,要根据实际情况选择适合的结构来存储。

Mr. 王:这里还有两种非常重要的线性结构要介绍,这两种结构非常简单,但却是很多算法的基础和组成部分,它们就是栈和队列。

小可:那什么是栈和队列呢?

Mr. 王:栈和队列都是特殊的线性表,不论用数组还是链表来实现它们都是可以的。但是它们除了是线性表以外,还有自己的特殊性质。其实栈和队列这两种结构在生活中都可以见到。

先说队列吧。平时我们在各种公共场所进行排队时,如果将每一个人都看作一个元素的话,那么组成的就是一个队列。队列的特点就是,每一个新加入的元素,都要放在整个队列的最后面;而当一个元素要离开队列时,总是从队列的最前端离开。这就是说,先进入队列的元素先离开队列,后进入队列的元素后离开队列,总结起来就是FIFO策略(先进先出策略)。队列的常见操作有入队列(enqueue、push,让一个元素进入队列)、取队首(front,获得队列最前端元素的值)和出队列(dequeue,让队首的元素离开队列)等,这些算法都非常简单。

小可:嗯,队列还是很直观的。那什么是栈呢?

Mr. 王:栈的特点和队列正好相反。用生活中的例子来说,就像是一个书箱子,箱子只有一个朝上的开口,我们可以把书从上面放进箱子,但是想要取书时,也只能从箱子的顶端取走,不能直接从箱子的中间和底部取书。所以,先进入箱子的书就会最后离开箱子。栈只有一个访问端,元素的出入都只能通过这一个端,这样我们也可以分析出,先进入栈的元素会被放在栈的最底端,也就是说,它会最后离开栈。总结起来就是LIFO策略(后进先出策略)。对栈的常见操作有入栈(push,将一个新元素放在栈顶的位置)、出栈(pop,将栈顶的元素弹出栈,露出下一个元素作为栈顶)和取栈顶元素(top,获得栈顶元素的值)。

栈的示意图

小可:嗯,我懂了。可是栈在计算机中有什么用呢?

Mr. 王:看起来队列在生活中似乎更加常见一些,但在计算机中,栈的应用却是非常广泛的,我们可以通过一个非常经典的例子来介绍计算机是如何利用栈这个结构的。

内容来源:灯塔大数据

原文发布于微信公众号 - 灯塔大数据(DTbigdata)

原文发表时间:2016-10-05

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏向治洪

Scala入门笔记

Scala入门 Scala简介 ps:在最新的薪资调查中,Scala程序员的工资是平均最高的Scala工资。 Scala是一门多范式的编程语言,一种类似ja...

2147
来自专栏有趣的Python和你

函数讲解

963
来自专栏AzMark

Python列表与元组

1363
来自专栏Crossin的编程教室

【Python 第55课】 正则表达式(1)

今天来挖个新坑,讲讲正则表达式。 什么是正则表达式?在回答这个问题之前,先来看看为什么要有正则表达式。 在编程处理文本的过程中,经常会需要按照某种规则去查找一些...

2767
来自专栏大史住在大前端

javascript基础修炼(2)——What's this(上)

this是javascript关键字之一,是javascript能够实现面向对象编程的核心概念。用得好能让代码优雅高端,风骚飘逸,用不好也绝对是坑人坑己利器。我...

861
来自专栏向治洪

Scala入门

Scala入门 Scala简介 ps:在最新的薪资调查中,Scala程序员的工资是平均最高的Scala工资。 Scala是一门多范式的编程语言,一种类似java...

1997
来自专栏Phoenix的Android之旅

重构 - 完全不用 if-else 可能吗?

上次那篇重构-为什么 if-else 不是好代码 说到代码中的 if-else会随着代码量的增加,在迭代的过程中变的越来越难以维护, 然后用工厂模式的思路可以把...

852
来自专栏程序员互动联盟

【编程基础】main函数,你知道多少?

近期学习时对这个问题产生了迷惑,看到了这篇文章,感觉挺好。 在C/C++的学习过程中,一个很常见的问题就是void main和int main有什么区别呢?本文...

3578
来自专栏青玉伏案

PHP精选数组函数

编程怎么能少的了数组呢,以下是学习PHP时常用的数组处理函数。在编程中要遵循一个原则就是DRY(Don`t Repeat Yourself)原则,PHP中有大...

2258
来自专栏Java呓语

工厂方法模式(延迟到子类来选择实现)

1、工厂方法模式理念介绍 2、它与简单方法模式的区别 3、推荐使用工厂方法的场景 4、在Android 源码中的应用

774

扫码关注云+社区

领取腾讯云代金券