数据结构
基本概念和术语
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。
数据结构中的4个概念:数据、数据对象、数据元素、数据项
数据:用户输入到计算机并且能够被计算机程序处理的一些符号，数据不仅仅包括整型、实型等数值类型，还包括字符及声音、图像、视频等非数值类型，对于从后端返回的整型,浮点型数据,可以直接进行数值计算. 对于字符串类型的数据,我们就需要进行非数值的处理. 而对于声音,图像,视频这样的数据,我们需要通过编码的手段将其变成二进制数据进行处理
数据对象：是性质相同的对象的集合（有点像数组，可不是面向对象的对象） eg:班级（一群学生，也就是一堆相同的数据元素）
数据元素：数据的基本单位，数据元素用于完整的描述一个对象 eg:学生 （数据项组合在一起就是一个完整的数据元素）
数据项：是组成元素的 eg:衣服啊，鞋啊，耳鼻喉啊（学生有的都可以是数据项）
逻辑结构与物理结构
逻辑结构
定义：是对数据之间关系的描述 (面向问题的)
任务：将基本概念模型图转换为与选用的数据模型相符合的逻辑结构
物理结构
定义：数据的物理（存储）结构 （面向计算机的）
任务：根据计算机系统的特点，为给定的数据模型确定合理的存储结构和存取方法
数据存储结构应该正确反映数据元素之间的逻辑关系, 如何存储数据元素之间的逻辑关系,是实现物理结构的重点
逻辑结构的分类
集合结构：数据之前只有一个关系就是在一个集合内，大家在一块待着，谁也不认识谁
线性结构：数据之间一对一关系，eg:数组，字符串，队列，栈，线性表
树形结构：数据之间一对多关系 eg:二叉树,B树,哈夫曼树,红黑树
图形结构：数据之间多对多关系 eg:邻近矩阵,邻接表.
存储结构的形式
顺序存储:是指把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的.
链式存储:是把数据元素放在任意的存储单元里,这组存储单元可以是连续的,也可以是不连续的. 数据元素的存储关系并不能反映逻辑关系,因此需要用一个指针存放数据元素的地址,这样通过地址就可以找到相关关联数据元素的位置.
算法
算法定义、特性、设计要求
算法定义：是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作（不是复杂的计算才叫算法）
算法特性：
- 输入输出
- 有穷性
- 确定性
- 可行性
算法设计要求：
- 正确性
- 可读性
- 健壮性
- 时间效率高和存储量低
做算法题的方法:
充分阅读题目.了解题目背后的关键意思;
分析题目,涉及到哪些数据结构,对问题进行分类. 到底属于链表问题, 栈思想问题, 字符串问题,二叉树问题,图相关问题,排序问题; 与你之前所接触过的算法题有没有类似,找到问题的解题思路
实现算法. 在算法的实现的过程,并不是一蹴而就, 肯定是需要不断的调试,修改的;
验证算法正确性
找到题源, 看其他的开发者对齐的解决思路.
找到题解建议之后, 对于其他优秀思路,分析它的优势,并且学习它的思路.并且写成其他解法的代码
算法题的解题能力来自于2点: 对于数据结构与算法核心问题是否夯实 + 是否有足够多且足够耐心的积累;
算法的评估
时间复杂度计算（推导大O阶方法）
用常数1取代运行时间中所有加法常数;
在修改后的运行次数函数中,只保留最高阶项;
如果在最高阶项存在且不是1,则去除与这个项相乘的常数;
空间复杂度 （在考量算法的空间复杂度,主要考虑算法执行时所需要的辅助空间）
程序空间计算因素:
-
寄存本身的指令
-
常数
-
变量
-
输入
-
对数据进行操作的辅助空间
eg: 数组逆序,将一维数组a中的n个数逆序存放在原数组中
网友评论