数据结构

数据结构的用途:
程序员的基本功、有效的管理数据对象、解决性能问题、面试加分项。

什么是数据结构?编程思想。
广义说法:数据结构 = 数据存储 + 算法
狭义说法:数据结构 = 数据存储

基本概念:
数据:描述客观事物的符号且计算机可以识别
数据对象:性质相同的数据元素集合
数据元素:数据元素有一定意义的最基本的单位、作为一个整体、也称作记录
数据项:组成数据的最小单位、不可在被分割

数据结构:相互之间存在一种或者多种特定关系的数据。数据结构和算法结合比较紧密。
数据之间的关系称之为结构,通常两种结构逻辑结构(通常反应数据元素之间的逻辑关系,谁排在谁之前、谁排在谁之后),存储结构(数据结构在计算机内存当中以一种什么样的形式保存)

存储结构

计算机内存相关知识:

内存的原理与构造:


地址:16进制表示地址。类似0x01,0x02,截图里面0不是很准确
指针:保存了内存地址的内存
引用:将一些复杂数据存入内存,将指针封装,变成引用。方便操作。
存储结构与内存管理:
存储结构:
顺序存储结构,典型代表数组(会开辟一段连续的内存,且数组中的元素一般都有一个前驱元素和后继元素,唯有数组头部元素没有前驱元素,末尾元素没有后继元素)。——好处数据个数是确定的就用顺序表
链表存储结构:每一个元素随机存储在内存中,链表中每一个元素都是分为两个部分:1.保存数据的部分,2.保存指针或引用的部分。在内存当中表示一个数据的时候,前一个部分保存存放的数据,后一个部分保存着后继元素的指针或者引用。——好处数据个数是不确定确定的就用链表、比较灵活

顺序存储结构、链表存储结构,逻辑结构都是线性的。

线性表的衍生结构(被限制操作的线性结构)
栈:有一个严格要求执行顺序,先进后出。LIFO(last in first out),用到的地方:浏览器前进后退功能

队列:可以两端进行操作,一端进一端出,且先进先出,后进后出。FIFO(first in first out),用到的地方:消息中间件。

串:接触最多的字符串(字符型的数组,所有的元素都是字符型),有一个起始位置和结束位置。避免没有终点,一直向后读取。操作与数组相似。但是有扩展批量操作,查找一串的字符

树:
基本概念:节点,边,路径。
节点:保存数据。
边:连接两个节点
路径:由一个树当中两个节点之间的多个边组成。从一个节点到另一个节点,只能有一条路径。(多条路径就是图)
树的特点:有一个根节点。最后一层为叶子节点
度:一个节点有子节点的数量
深度:
一个树没有任何节点,叫做空数
遍历:树上的所有节点,且不重复访问。
深度优先遍历:先序遍历、中序遍历、后序遍历
广度优先遍历:层序遍历

深度优先遍历-先序遍历
深度优先遍历-中序遍历 从整棵树的最左边的节点开始(蓝色)

深度优先遍历-后序遍历 最左边的叶子节点开始,后序先找到最左边的叶子节点,然后找父节点的另一个子节点,然后在找父节点

广度优先遍历

🌲的衍生结构:
二叉树:每个节点的子节点最多是2个
完全二叉树:从根往下数,除了最下层外都是全满(都有两个子节点),而最下层所有叶结点都向左边靠拢填满。
满二叉树:二叉树除了叶结点外所有节点都有两个子节点。

图:
顶点和边。边可以赋值、可以是长度也可以是别的,那么这个值称之为权
图分为有向图和无向图

无向图
有向图

图可以退化为树,图和树的区别,图不可以是空数据,树可以是一个空数。

索引存储结构

散列存储结构