数据结构学习笔记一

发表于 更新于 分类于

概述

这篇文章是我学习数据结构知识的笔记总结，示例以 java 8 语言实现。

定义

数据结构(data structure) 是计算机存储、组织数据的方式。 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构往往同高效的检索算法和索引技术有关，因此精心选择的数据接口可以带来更高的运行或存储效率。–来着百度百科。

相关概念

数据

描述客观事物的符号，是计算机可以操作的对象，是能被计算机识别，并输入改计算机处理的符号集合。 --来自《大话数据结构》

数据是研究数据结构的基础，将数据按一定方式进行组织就形成了数据结构。在 java 中的数据类型有整形、浮点型、字符串等，广义上来说还包括图片、声音、视频等。

数据元素

组成数据的、具有一定意义的基本单位，在计算机中通常作为整体处理。就是一条数据记录。

数据项

数据项是数据不可分割的最小单位，一个数据元素可以由多个数据项组成。如人有眼、耳、口、鼻这些数据项。

逻辑结构与物理结构

逻辑结构

分类依据是数据对象中数据元素之间的相互关系。

  • 集合结构：数据元素属于同一个集合，除此之外没有其他关系。类似于数学中的集合。如班级中的学生就是一个几个。
  • 线性结构：数据元素之间是一对一的关系。如链条一环扣一环。
  • 树形结构：元素之间存在一对多的层次关系。如族谱、管理层结构。
  • 图形结构：元素之间存在多对多的关系。如人脉关系网、铁路交通图。

物理结构

分类依据是数据的逻辑结构在计算机中的存储形式

  • 顺序存储结构：计算机开辟整块内存空间来顺序存储数据，如数组。优点是可以随机访问，缺点是容量固定不能扩展，添加、删除元素效率低。
  • 链式存储结构：存储空间可以不连续，每个数据元素中包含了下一个元素的地址信息，如链表。优点是添加、删除元素效率高，且容量不限制，缺点是不支持随机访问。

一些常见的数据结构

  • 线性结构: 数组、栈、队列、链表、哈希表

  • 树结构: 二叉树、二分查找树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树

  • 图结构: 邻接矩阵、邻接表

时间复杂度和空间复杂度

没有最好的数据结构，只有最适合的数据结构，通常情况下，数据结构与算法是息息相关的，数据结构在很大程度上决定了算法的实现方式。

时间复杂度

时间复杂度用来定性描述算法的运行时间，考察的是输入值大小趋近于无穷时的情况(称为渐进)，用大 O 符号表述。

推导方法：

  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中，只保留最高阶项。
  3. 如果最高阶项存在且不为1，则去除与这个项相乘的常数。

– 来自《大话数据结构》

常见的时间复杂度：

空间复杂度

空间复杂度用来度量一个算法运行过程中临时占用的存储空间大小，也是渐进考察的，是考虑输入值大小趋近于无穷的情况，用大 O 符号表示。

均摊时间复杂度与复杂度震荡

数组

概念：
数组(Array), 是由相同类型的元素(element)的集合所组成的结构，分配一块连续的内存来存储，利用元素的索引(index)可以计算出该元素对应的存储地址。
来自维基百科的解释。

数组最大的优点是查询快速，我们可以使用索引来访问数组中的元素，最好应用于索引有语义的情况，如用数组来存储学生成绩，数组索引为学生学号，这样要查询某个学生的成绩时就非常快速高效。

访问数组元素的时间复杂度为 O(1)，添加/删除数组元素的时间复杂度为 O(n)。

在 java 中定义数组时需要指定数组的容量和类型，不能动态添加，在某些编程语言中可以动态增加，不限类型，如 javascript。