Java教程

数据结构与算法学习笔记

本文主要是介绍数据结构与算法学习笔记,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是数据结构

数据结构的起源
1968年美国的高纳德教授开创了一门新的课程《基本算法》,开创了数据结构和算法的先河,确定了数据结构和算法的基本体系。
数据结构不是一门研究数据计算的学科,而是研究数据与数据之间关系的,是一门研究非数值计算的学科,专注于数据的关系及操作。
程序=数据结构+算法,它在计算机界的地位相当于E=MC^2在物理界的地位。
数据结构的基本概念
数据:所有能输入到计算机中的描述客观事物的符号。
数据项:有独立含义的数据的最小单位。描述事物的其中一项指标。
数据元素:数据的基本单位,也称节点或记录,用于描述一个完整的事物。
数据结构:数据元素+数据关系组成的集合
算法:
狭义:数据结构所具有的功能。
广义:解决问题的方法。
数据结构的三个方面
数据的逻辑结构
数据的存储结构
数据结构的运算
四种基本的逻辑结构
集合结构:数据元素之间除了同属于一个集体外,没有关系
线性结构:数据元素之间存在一对一关系(数组)。
数组、链表、功能受限的表(栈、队列)
树型结构:数据元素之间存在一对多关系。
普通树、二叉树、完全二叉树、满二叉树、有序二叉树
图型结构:元素之间存在多对多关系
邻接表、表的遍历(深度优先、广度优先)、最短路径

数据结构
数据结构分为数据和结构
1.什么是数据:但凡能够被计算机存储、识别、和计算的东西都叫数据(二进制)。硬盘中:mp3、jpg、doc、avi等文件就是数据。“巧妇难为无米之炊”,不管你再大或者再牛逼的计算机,没有“米”来下锅,它也是无用的。而这个“米”就是数据。也就是说这里的数据其实是一种符号,而这些符号必须能被输入到计算机中,或者说能被计算机程序处理。
2.结构 :就是数据和数据之间一种或多种的特定的关系。简单的来说就是关系,严格点来说是指各个组成部分相互搭配和排列的方式。在现实世界中,不同的数据元素之间不是独立的,而是存在特点的关系,我们将这些关系称为结构。
3.数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
它主要解决的问题:把零散的数据“整齐划一”方便后续的操作 。类似于现实生活中的垃圾分类,便于回收与处理。
数据结构的逻辑结构 :是指数据对象中数据元素之间的相互关系,它是抽象的,它主要分为一下四种:
3.1集合结构:结合结构中的数据元素除了同属于一个集合外,他们之间没有其他关系。也就是说各个元素都是平等的,他们之间没有其他关系,只不过他们的共同属性是属于同一个集合。有点像数学中的集合。
3.2 线性结构:线性结构中的数据元素之间是一对一的关系。像是一个链表,不管是1或9作为尾结点或者头结点。
3.3 树形结构:树形结构中的数据元素之间存在一种一对多的层次关系。想到了族谱,也是这种树形结构。
3.4 图形结构:图形结构的数据元素是多对多关系。比如数据库中表与表的对应关系,多对多时,查询起来sql语句就有点复杂了。
如下图:

在这里插入图片描述

4.数据结构的 物理结构:很多书中也叫它存储结构,不管叫什么,只要理解了也就一回事。他是具体的,存在计算机里的。
物理结构:它是指数据的逻辑结构在计算机中的存储形式。数据是数据元素的集合
① 顺序存储结构:开辟一组连续的空间存储数据–数组 地址本身是连续的,保证了数据之间的关系。这种结构很简单,说白了,就是排队占位,每个人都有特定的位置,不允许插队操作。
② 链式存储数据:开辟一组随机的空间存储数据–节点 ~不仅要存储数据,还要存储下一个节点的位置一保证数据之间的关系。把数据元素存放在任意的存储单元里,这组存储单元是连续的,也可以是不连续的。这跟银行的排队系统就很像了,每个人去了先领号,领完号后,只需等待银行叫号,你过来就行,而不管你在哪,你在干什么。

算法
1.算法:官方定义是解决特定问题求解步骤的描述,在计算机中表现为指令的有序序列,并且每条指令表示一个或多个操作。简单来说就是解决问题的步骤
如何评价一个算法的好坏:设计算法要提高程序运行的效率,这里效率大都指算法的运行时间
2.事后统计方法:在程序运行完后,对运行时间进行比较。缺陷:必须先编好程序,再运行,如果处理的数据大,花费时间长;依赖计算机软硬件;
3.事前分析估算方法:在程序编制前,统计方法对算法进行估计
在这里插入图片描述
它是衡量算法好与坏,执行时间快与慢的标准。

等差数列求和
int n = 100; //执行一次,
int sum = (n+1)*n/2; 执行一次
循环求解
int sum = 0;//执行一次,
int n = 100; //执行一次,
for(int i = 1;i<n;i++) { //执行n+1次,
sun+=i; //执行n次,
}
① 常数阶O(1) 第一个代码执行了两次,但是复杂度却为O(1) ;
② 线性阶O(n)/忽略常数,忽略N的系数/2n+3,随着N的增大,循环里面执行的次数越多,那么此算法的执行次数为2N+3次,但是是时间复杂度为O(n),因为随着N的不断增大,这个3就显得微不足道了,如果N达到足够大,这个系数2也显得微不足道,因为数量级是一样的,因此最后的时间复杂度为O(n)。
③ 对数阶O(logn):虽有循坏,虽也随着n的增大而增大,但是这种增大属于 加速度减小的加速运动
④ 平方阶O(n^2) 忽略常数,只保留幂高项,且忽略幂高项的系数

这篇关于数据结构与算法学习笔记的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!