美文网首页简书新手程序员unity3D技术分享
数据结构笔记(四)——线性表

数据结构笔记(四)——线性表

作者: 泡泡不爱吃芹菜 | 来源:发表于2016-11-07 21:36 被阅读177次

前面说过,数据结构的类型大方向上来说分为线性结构非线性结构,下面要说的线性表就是线性结构的一种。
(复习一下,前面说过的线性结构有:线性表、栈、队列、字符串、数组和广义表)
上一行是课本上的原话,但是感觉这个在逻辑上有一些不清楚的地方,先忘掉上一行的东西吧,看完下面的再回来想想。

先来说一下线性表是什么。
线性表简单来说就是一个*有限个元素的序列 ***。
本来有一堆山楂,你拿个竹签,一个一个穿起来,就构成了线性表。
请记好,这里还有串“低配版”的只有山楂没有糖的糖葫芦,我们后面就用它来类比线性表。
——OOOOOOOOOOO————————(→.→ 我叫糖葫芦。。。)

线性表的性质

1.首先,这串糖葫芦的山楂的个数一定是可数的。
所以类比到线性表,线性表的元素一定是有限的。

2.然后,一般吃糖葫芦都是从开头第一个山楂开始吃,吃到最后一个山楂吃完。
类比到线性表,线性表有且只有一个开始节点、有且只有一个终端节点。

3.除了糖葫芦的第一个和最后一个山楂,其余的每个山楂都左边有一个山楂右边有一个山楂。
类比,线性表除了两端的元素节点,其他的每个元素都有且只有一个前驱节点和后继节点。

4.世界上没有两片完全相同的树叶,也没有两颗完全相同的山楂。对于这串糖葫芦,山楂的位置都是固定的,该是第几个就是第几个(假如你不吃或者不把山楂往前撸的话),只要通过位序就能找到对应的山楂的位置。

5.吃完了这串糖葫芦,就只剩一个空竹签了。类比地,把含有0个元素节点的线性表称为空表

6.当然,吃了半天糖葫芦,必须要知道的是,这串糖葫芦的每一个“元素”都是“山楂”,而不是其他什么果子。
类比线性表,线性表要求每一个数据元素的类型都是相同的,不能混进去什么奇怪的东西。

概括来说,线性表的三大特点就是:同一性(6)、有穷性(1)、有序性(2、3、4)。


说完了线性表的性质,可能就会有一些疑问:上面的糖葫芦模型是万能模型吗?(这个模型是不是完整模型?糖葫芦模型能不能代表所有线性表的特点?)

比如:我不想从第一个山楂开始吃,我从第二个开始吃可不可以?那对应的线性表的逻辑会不会乱掉?

答案是:虽然逻辑不会乱,你怎么吃那都是一串山楂;糖葫芦模型只是为了形象地表达一下线性表的最主要的特点,并不能解释所有的线性表的特点。后面还有别的线性表的内容呢,不能老吃糖葫芦呀多腻呀。。。
实际上线性表是有分类的(这个书上没说),按照操作方式,线性表一般分为一般线性表受限线性表两种。

有什么区别呢?

一般线性表

一般线性表就是前面的糖葫芦模型,你爱从哪里开始吃就从哪里开始,爱吃第几个就吃第几个。(对应的线性表例如数组)

受限线性表就不是糖葫芦了,而是桶装薯片(栈)和吸管(队列)。


(就酱婶的薯片,其实实物很小一罐的,但是这里看起来真的是好大一桶的样子)

这时候你只能先吃最上层的薯片,吃了上层才能拿下一层的,不能随便拿中间的第X层的那张薯片。

或者是吸管,你只能最先喝到最先进入吸管的那一部分,而不能直接就喝到吸管中段的那部分。
总而言之,这时候你的操作受限制了,不能再任性下去了,所以这样的线性表,称为受限线性表。


好,现在关于线性表的一些基础知识都过了一遍,现在让我们回到开头,我说“感觉逻辑怪怪的”这里。

课本上说的线性结构包含了:线性表、栈、队列、字符串、数组和广义表。似乎是把线性表和栈、队列、数组这些东西给平行表示了。
但是实际上,线性表与栈、队列和数组(或者也包括字符串)不是平行的。
线性表包括了栈、队列和数组、字符串

所以说,其实数据结构里的线性结构大多都是以线性表表示的。然后根据操作性质分别选用了“一般线性表”或者“受限线性表”,然后又根据不同的使用场景再一步细分为使用哪一种线性表(栈?队列?数组?串?)。

关于线性表的概念就到这里,后面的几期还会有薯片吸管糖葫芦等着我去吃。

新手上路,才疏学浅。如有错漏,多谢指教。

相关文章

  • 线性表

    最近在进行考研数据结构的二轮复习,想写一些比较重要的数据结构内容笔记,首先是线性表的学习笔记。 一、线性表的基本概...

  • 数据结构 -《大话数据结构》读书笔记(3)

    文章共分为三篇 第一篇:数据结构 -《大话数据结构》读书笔记(1) 一、数据结构绪论二、算法三、线性表 第二篇:数...

  • 数据结构 -《大话数据结构》读书笔记(2)

    文章共分为三篇 第一篇:数据结构 -《大话数据结构》读书笔记(1) 一、数据结构绪论二、算法三、线性表 第二篇:数...

  • 数据结构笔记(四)——线性表

    前面说过,数据结构的类型大方向上来说分为线性结构和非线性结构,下面要说的线性表就是线性结构的一种。(复习一下,前面...

  • 数据结构与算法学习-数组

    前言 这一篇笔记主要记录总结了线性表数据结构中的数组概念以及相关的算法。 名词解释 1. 线性表(Linear L...

  • 数据结构和算法一(线性表和单链表)

    一、前言 二、数据结构 三、线性表: 3、我们在来看顺序存储方式的特点 4、链式存储结构: 四、线性表(循环链表)...

  • 目录 - 数据结构

    总目录 数据结构 第01局:绪论 数据结构 第02局:线性表 上 数据结构 第03局:线性表 下 数据结构 第04...

  • iOS设计模式--迭代器

    学习迭代器之前,先看一种数据结构--线性表 线性表:线性表是最基本,最简单,也是最常用的一种数据结构。 线性表中数...

  • Java造轮子-数据结构-线性表

    数据结构-线性表 @(数据结构) 线性表是数据结构中的逻辑结构。可以存储在数组上,也可以存储在链表上。 顺序表(数...

  • 数据结构与算法(二)数组

    前言:本文是用来记录自己学习数据结构与算法的笔记,写的不对的地方欢迎指正。 数组定义 数组是一种线性表数据结构。它...

网友评论

    本文标题:数据结构笔记(四)——线性表

    本文链接:https://www.haomeiwen.com/subject/rhaouttx.html