数据结构概述

一、概述

1. 是计算机的一门基础学科

2. 研究数据在计算机中进行组织和存储,使我们可以高效的获取数据和修改数据

3. 分类

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

• 树型结构:二叉树、二分搜索树、AVL树、红黑树、堆、Tire、线段树、并查集...

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

二、基本概念

数据(Data):能输入并被计算机所处理的符号

数据元素(Data Element):是数据的基本单位

数据项(Data Item):是组成数据元素的有独立含义的,不可分割的最小单位

数据对象(Data Object):是性质相同的数据元素的集合,是数据的一个子集

数据结构+算法=程序

数据结构(Data Structure):是相互之间存在一种或多种特定关系的数据元素的集合

数据结构包括逻辑结构和存储结构两个层次

1.逻辑结构有两个要素

数据元素

关系:非线性结构(集合,树,图或网状(多对多)),线性结构(线性表、栈和队列、字符串、数组、广义表)

2.存储结构又称物理结构

顺序存储

链式存储

算法:一类问题所使用的解决方案,在不同方案中,时间复杂度和空间复杂度不同.好的算法就是在时间复杂度和空间复杂度找到平衡.

三、后期开发环境

IDEA,JDK8+

四、学习网站

labuladong(学习)

牛客网 (nowcoder.com)(刷题)

力扣 (LeetCode)(刷题)

JavaAPI(查询)

五、时间复杂度O(n)和空间复杂度

两者是衡量算法优劣的标准

时间复杂度:取最大的指数幂;忽略常数项;描述n趋于无穷的情况

空间复杂度:对算法运行过程中临时占用的空间大小