数据结构_基础
2015-09-08 本文已影响131人
arkulo
当数据从数据库中读取出来后，在内存中除了数组还可以如何操作数据？？？？因为数组只能一个个的循环！！
单位换算
1 bit = 0/1 二进制数据
1 byte = 8 bit
1 字母 = 1 byte = 8 bit
1 汉字 = 2 byte = 16 bit
1G = 1024M(兆字节) = 1024*1024KB(千字节) = 1024*1024*1024B(字节) = 1024*1024*8bit（比特）
基本概念和术语
数据
反映客观事物的信息的集合，是信息的载体，能够被计算机识别、存储和加工处理
数据元素
集合中的个体，数据的基本单位，一个数据元素可以有多个数据项组成（字段、域、属性）
数据项
是具有独立含义的最小数据单位
数据结构
数据元素之间的逻辑关系
存储结构
数据元素及其关系在计算机存储器内的表示（大多数情况下都指内存）
算法
数据的运算，即对数据施加的操作
身份证数据管理
数据元素：每一个身份证信息是一个数据元素
数据项：姓名、性别、身份证号和相片
数据结构：
- 逻辑结构：线性表
- 物理结构：数组（顺序存储）
- 算法：增加、删除、查找
数据的逻辑结构
特征
- 从逻辑关系上描述数据，与数据的存储无关
- 从具体问题抽象出来的数据模型
- 与数据元素本身的形式、内容无关
逻辑结构分类
集合结构
数据元素间无任何关系
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/1.png
线性结构
元素之间的关系是1:1的
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/2.png
- 有且只有一个初始节点
- 最多有一个前驱，最多有一个后继（也可以没有）
- 插入或删除一个节点后仍满足前两条
例如：线性表
非线性结构
元素之间的关系是1:n的
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/3.png
- 一个节点可以多个直接后继（除叶子节点外），但只有一个直接前驱（除根节点外）
例如：一般树、二叉树、森林
图状结构
元素之间的关系是n:n的
https://raw.githubusercontent.com/arkulo56/thought/master/images/datastruct/4.png
- 一个节点可以有多个直接后继，也可以有多个直接前驱
数据结构的研究对象
- 非数值数据之间的结构关系
- 运算操作以插入、删除、查找、更改、排序为主
存储结构
数据结构在内存中的存储结构
原理
简单的线性的数据结构直接用顺序和链式存储就可以搞定，例如：队列，栈、二叉树
复杂的数据结构则需要顺序和链式复合才能存储，例如：树（度大于2）、图（采用邻接矩阵等）
顺序存储
- 位置即关系，节省空间
- 查询快，插入删除慢
- 内存碎片（内部碎片）
链式存储
- 数据元素要包含关系，空间开销大
- 插入删除快，查询则需遍历链表
- 没有碎片
注：头节点可以不包含数据，也可以包含链表的长度。其有助于删除第一个元素，或者在第一个元素前插入数据
注：头指针是指向头节点的指针，无论链表是否为空，都存在头指针
循环链表就是尾节点的next指向头节点，这样可以循环遍历
