数据结构简介
什么是数据结构?
- 计算机存储及组织数据的方式. 也可以理解为, 一些有特殊关系的数据
- 计算机以0和1的电信号来存储数据, 8个0/1为一个字节(bit), 1024个bit为1KB, 1024KB为1M 以此类推
常见数据结构
- 线性表(数组 链表 栈 队列)
- 树
- 图
逻辑结构
数据从逻辑上看, 可以分为下面几种结构:
-
集合结构
集合结构- 集合结构里面有很多元素, 但元素之间没有特殊的关系, 类似于NSSet NSMutableSet
-
线性结构
线性结构- 线性结构中的元素在逻辑上是有顺序的, 但在内存中的存放不一定是有序的,类似于NSArray, NSMutableArray等
-
树状结构
树状结构- 树状结构是一个或者多个节点的有限集合, A为根节点, 以为它最大, D是I和J的父节点, I,J为兄弟节点
-
图形结构
图形结构- 图形结构简称"图", 是一种相对复杂的数据结构, 任意两个节点之间在逻辑上都可以相互关联
存储结构
数据结构从逻辑上可以分为以上几种, 但是这些数据都要存放到内存中去, 那么内存中存放数据也有不一样的结构
-
顺序存放结构
顺序存放结构- 顺序存放结构中存储单元的内存地址是连续的, 要求逻辑上相邻的元素, 在物理地址上也是相邻的
- 优点是遍历、查找非常快
-
链式存储结构
链式存储结构- 链式存储结构中的元素在内存中的地址有可能是连续的, 也有可能是不连续的, 不要求逻辑上相邻的元素在物理地址上相邻
- 1中保存2的内存地址, 2中保存3...依次类推
- 优点是:相对于顺序存放结构更加灵活, 插入元素更加灵活
线性表
-
什么是线性表
- 线性表就是多个具有相同特性的元素(节点)组成的, 有限而且有序的集合(逻辑有序)
- 当线性表的节点个数为0时, 称之为空表
- 第一个元素称为首节点, 最后一个元素称为尾节点
- 如:某个线性表元素:a1 a2 ...a99, 那么 a1...a98都是a99的 前驱, a98是a99的 直接前驱 , a2...98都是a1的 后继, a2是a1的 直接后继
-
线性表的顺序存储结构
- 用一组地址连续的内存单元一次存放线性表的数据元素
-
线性表的链式存储结构
- 用一组任意的内存单元一次存放线性表的数据元素, 其物理地址可以是连续的, 也可以是不连续的
-
评判算法的优劣有两种标准:
-
时间复杂度
- 指算法执行代码(指令)的次数, 次数越多, 时间复杂度越高
-
空间复杂度
- 指内存的消耗, 主要是看堆空间的消耗
-
时间复杂度
