数据结构 —— 数组、栈、队列、链表
编辑历史：
2018.7.3 小赖 文档初始化
数据结构是什么？
数据结构是在计算机为了组织数据的特定方式，目的是为了高效地使用数据。
数据结构提供不同的方式来存储数据，以便快速、动态地搜索、插入、移除、更新数据。列举一些常用的数据结构：
- 数组 （Array）
- 栈（Stacks）
- 队列（Queues）
- 链表（Linked Lists）
- 集合（Sets）
- 树（Trees）
- 图（Graphs）
- 哈希表（Hash Tables）
数据结构
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
- 集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
- 线性结构:数据结构中的元素存在一对一的相互关系；
- 树形结构:数据结构中的元素存在一对多的相互关系；
- 图形结构:数据结构中的元素存在多对多的相互关系。
概念介绍
数组
- 概念：数组是在内存中开辟一段连续的空间，并在此空间存放元素。
- 理解：就像是一层学生公寓，有20个房间，从01到50每个房间都有固定编号，通过编号就可以快速找到住房子的人。
- 特点：元素类型是固定的、长度是固定的、通过角标查询，查询快，增删慢。
- 时间复杂度：O(1）
- 空间复杂度：
图片示例：
15306884463884.jpg
图片解释：0，1... 代表的是角标。
栈
- 概念：栈是一种先入后出的线性结构，每次加入新的元素和拿走元素都在顶部操作。
- 理解：就像羽毛球盒，只有一个口，有顺序地进出，并且只能一端进与出，称为LIFO，先进后出或者后进先出，顾名思义就是先进去的就后出来，先进去的球会被后来的球不断的挤压，此举称之为压栈。
- 特点：1.遵循 后进先出（LIFO ）规则;2.有用于管理栈内内容的 push（add） 和 pop（remove） 方法;3.有一个 top 属性用于跟踪栈的大小以及当前栈顶位置。
- 时间复杂度：O(n）
- 空间复杂度：
图片示例：
15306897582599.jpg
链表
- 概念：链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
- 类型：单链表，双链表，有序链表
- 理解：有一条街，小明住在街中一角，他有小红的地址，然后小红也是住在这条街，她有小花的地址，同样小花也有别人的地址。某天我想找小红玩，但是我不知道她住哪里，我可以问小明，就知道小红住在哪里了。那么小明小红小花这些人之间的关系就组成一个链表。
- 特点：1.链表存储的数据在地址空间上可连续，可不连续;2.链表中的每一个节点都包括数据和指向下一个地址的指针;3.方便数据的增删。
- 时间复杂度：O(n）
示例图片：
15306901103088.jpg
15306900584335.jpg
-
单链表：就是小明只是右手握着小红的地址，他只有小红一个人的地址
-
双链表：就是小明左手握着小白的地址，右手握着小红的地址，他有两个人的地址
-
循环链表：就是小明握有小红的地址，小红握有小花的地址，而小花又握有小明的地址，这样就形成了一个循环
-
有序链表：以某个标准，给链表的元素排序，比如比较内容大小、比较哈希值等
队列
-
概念：队列是一种先入先出的逻辑结构，对元素的操作分别在对头和队尾，元素的插入在对尾，元素的删除在对头
-
理解：就像是一条水管，有两端，有顺序地进出，并且只能一端进另一端出，称为FIFO，先进先出，顾名思义就是先进去的就先出来，如果你要删除，只能从出口端，一个一个的顺序删除，同理，要增加，也只能通过入口端顺序地添加进去。
-
特点：先进先出。
示例图片
未完待续。
网友评论