从今天开始正式开始学习数据结构与算法。
从今天开始正式开始学习数据结构与算法。从上面的框图也可以从整体上把握数据结构的关键知识点,不管是简单的顺序表还是栈,树等,学习的方法都是一样的他们的操作也都是无非都是些增删改查的操作,学习步骤就是先理解概念,然后理解每种结构的插入删除的方式,在转化为代码实现,之后我们就是先概念后代码,此过程也可以复习了之前的知识。
这节我们只讲一些相关的概念,毕竟数据结构比较抽象,防止我们在之后的学习中迷路,知道我们每一节在学什么,要掌握哪些重点,并且可以根据个人的情况,侧重的学习。
在学习之前,强烈推荐一本数据结构的书《大话数据结构》程杰著
一说到这门课,大多数人的第一反应就是比较抽象比较难懂,确实工作了这么长的时间依然还是没搞懂,但是它确实很重要。怎么重要?
你在工作中同样是实现一个功能,你的代码执行效率和操作方式就是比别人好,你不加薪谁加薪哈哈。
数据结构的起源,其实就是为了更好的处理现实问题。
那什么是数据?
数据就是我们做饭用的米。
官方套话:数据是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合(整型,实型,字符,声音,图片,视频等)
注:可输入到计算机,能被计算机程序处理的符号。
数据元素:组成数据的基本单位
数据项:一个元素可以由多个数据项组成
数据对象:性质相同的数据元素的集合,数据的子集(某种情况下可以理解为就是数据)
数据类型:对数据元素取值范围和运算的限定
数据结构:相互之间存在一种或多种特定关系的数据元素的集合。(分析对象的特征和各对象的关系)
数据结构研究计算机数据间关系,包括数据的逻辑结构和存储结构及其操作
数据结构可以分为逻辑结构(面向问题)和存储结构(面向计算机(内存))
逻辑结构
- 集合结构:数据元素除同属于一个集合外,他们之间没有任何关系(同级别)
- 线性结构:数据元素之间是一对一的关系
- 树形结构:数据元素之间存在一对多的层级关系
- 图形结构:数据元素是多对多的关系
形象的说明了数据结构中的重点逻辑结构(线性表(link list, queue,stack),树,图):
存储结构(数据的逻辑结构在计算机中的存储形式)
顺序存储结构:数据元素存放在地址连续的存储单元中,其数据间的逻辑关系和物理关系是 一致的。(数组就是这种存储结构,不易插入和添加数据)
链式存储结构:数据元素存放在任意的存储单元,存储单元可连续,可不连续。(通过指针进行寻找)例:银行的排号系统
索引存储:存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。(字典)
散列存储:按结点的关键字(key)直接计算出存储地址
数据运算关系
增,删,改,查
数据类型:
原子类型:基本类型(整型,实型,字符型)
结构类型:可再分解的类型(整型数组,结构体等)
抽象数据类型:
对已经有的数据类型进行的一个抽象(Abstract Data Type, ADT)
抽象类型的标准格式:
ADT 抽象数据类型名
DATA
数据元素之间的逻辑关系定义
Operation
操作1
初始条件
操作结果描述
。。。。。
endADT
上面我们说了一些关于数据结构的概念,那什么是算法。
算法就是解决特定问题求解步骤的描述。
同样的菜(数据),不同的烹饪方法,味道是不一样的。
数据结构与算法的关系,类似于搞基的关系。哈哈
程序 = 数据结构 + 算法
1.算法的五个基本特性:
输入,输出,有穷性,确定性和可行性。
2.算法设计的要求:
正确性,可读性,健壮性,时间效率高和存储量低
//下面说了很多,其实就是交给我们怎么判断一个程序的好坏,时间复杂度的估算要求我们掌握,虽然初学会感觉很没有必要,但为了更快速更高效(更胜一筹),还是要学习的。
3.算法效率的度量方法
1>事后统计法(做了解)
2>事前分析估算方法
程序在计算机运行中所消耗的时间
算法的设计
算法的输入规模
编译器对代码的优化
计算机执行指令的速度
4.如何使用事前分析估算方法?
1>函数的渐进增长
2>算法时间复杂度
3>常见的时间复杂度
4>时间复杂度最坏情况与平均情况
5>算法空间复杂度
时间复杂度的计算方法
根据语句频度,写出表达式
常数部分变为1
只保留最高阶项目,其余项舍去
如果最高阶段乘数不为1,表达式除与最高阶相乘的数
越平缓,效率越高。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)