【数据结构(一)】初识数据结构
❣博主主页: 33的博客❣
▶文章专栏分类: Java从入门到精通◀
🚚我的代码仓库: 33的代码仓库🚚
🫵🫵🫵关注我带你学更多数据结构知识
目录
- 1.前言
- 2.集合架构
- 3.时间和空间复杂度
- 3.1算法效率
- 3.2时间复杂度
- 3.2.1大O的渐进表示
- 3.2.2常见时间复杂度举例
- 3.3空间复杂度
- 4.包装类
- 4.1基本数据和对应的包装类:
- 4.2装箱和拆箱
- 5.泛型
- 5.1引出范型
- 5.2语法
- 5.3泛型类的使用
- 5.4泛型是如何编译
- 5.5泛型的上界
- 5.6泛型方法
- 6.总结
1.前言
数据结构是计算机存储,组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合,从这篇文章开始,我们将一起进入数据结构的学习,那么该如何学好数据结构呢?博主的建议是多写代码,多思考,多画图!
本章重点
掌握数据结构基本知识主要包括集合框架,时间和空间复杂度,算法效率,大O渐进表示,包装类,泛型相关知识。
2.集合架构
Java 集合框架Java Collection Framework ,又被称为容器和其实现类classes 。
类和接口总览:
3.时间和空间复杂度
遇到一个算法,我们怎么衡量一个算法的好坏呢?
3.1算法效率
算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被称作空间复杂度。
3.2时间复杂度
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个数学函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度。
有些算法的时间复杂度存在最好、平均和最坏情况:
最坏情况:任意输入规模的最大运行次数(上界)当说时间复杂度一般值最坏情况下
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(下界)
3.2.1大O的渐进表示
在计算时间复杂度时,我们不需要计算精确的执行次数,只需要大概的次数,那么我们就剋用大O渐进表示法去掉那些对结果影响不大的项,简明表示执行的次数。
规则:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
3.2.2常见时间复杂度举例
例1
.
void func2(int N) {int count = 0;for (int k = 0; k < 2 * N ; k++) {count++; //时间复杂度2N}int M = 10;while ((M--) > 0) {count++; //时间复杂度10}System.out.println(count);}
时间复杂度2N+10 为O(N)
例2.
void func3(int N, int M) {int count = 0;for (int k = 0; k < M; k++) {count++; //时间复杂度M}for (int k = 0; k < N ; k++) {count++; //时间复杂度N}System.out.println(count);}
时间复杂度M+N为O(M+N)
例3.
// 计算func4的时间复杂度?
void func4(int N) {int count = 0;for (int k = 0; k < 100; k++) {count++; //时间复杂度100}System.out.println(count);}
时间复杂度100为O(1)
例4.
// 计算bubbleSort的时间复杂度?
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}}
假设array.length=N,那么第一次循环执行N-1次,第二次循坏执行N-2次,第三次循环执行N-3…最后一次为1,那么总次数就是(N-1)+(N-2)+(N-3)+…1,等差数列求和结果为(NN-N)/2那么时间复杂度为O(NN)。
例5.
int binarySearch(int[] array, int value) {int begin = 0;int end = array.length - 1;while (begin <= end) {int mid = begin + ((end-begin) / 2);if (array[mid] < value)begin = mid + 1;else if (array[mid] > value)end = mid - 1;elsereturn mid;}return -1;}
那么剩下1个数就需要时间复杂度O(log2^N)。
例6.
// 计算阶乘递归factorial的时间复杂度?
long factorial(int N) {return N < 2 ? N : factorial(N-1) * N;}
递归复杂度=递归次数*每次递归后执行的次数
时间复杂度=(N-1)*1=O(N)
例7.
int fibonacci(int N) {return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);}//2^n
3.3空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似,也使用大O渐进表示法。
例1.
void bubbleSort(int[] array) {for (int end = array.length; end > 0; end--) {boolean sorted = true;for (int i = 1; i < end; i++) {if (array[i - 1] > array[i]) {Swap(array, i - 1, i);sorted = false;}}if (sorted == true) {break;}}}//输出O(1)
例2.
int[] fibonacci(int n) {long[] fibArray = new long[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n ; i++) {fibArray[i] = fibArray[i - 1] + fibArray [i - 2];}return fibArray;}//O(N)
4.包装类
在Java中,由于基本类型不是继承自Object,为了在泛型代码中可以支持基本类型,Java给每个基本类型都对应了一个包装类型。
4.1基本数据和对应的包装类:
基本数据类型 | 包装类 |
---|---|
byte | Byte |
short | Short |
int | Integer |
long | Long |
float | Float |
double | Double |
char | Character |
boolean | Boolean |
4.2装箱和拆箱
Integer a = 10;//装箱
int b = 20;
Integer c=b;//基本类型转变为包装类型
Integer a = 10;
int c = a;//拆箱,包装类型转换为基本类型
例
public static void main(String[] args) {Integer a = 127;Integer b = 127;Integer c = 128;Integer d = 128;System.out.println(a == b);//trueSystem.out.println(c == d);//false}
为什么输出结果一个是T一个是F呢,我们来看看源码
通过源码我们知道,如果范围在【-128,127】那么就返回数组中的值,否则就new一个对象。127在范围内,那么直接返回cache[255]的值;128不在范围内,久new一个 对象。
5.泛型
泛型:就是适用于许多许多类型。从代码上讲,就是对类型实现了参数化。
5.1引出范型
实现一个类,类中包含一个数组成员,使得数组中可以存放任何类型的数据,也可以根据成员方法返回数组中某个下标的值?
class MyArray {public Object[] array = new Object[10];public Object getPos(int pos) {return this.array[pos];}public void setVal(int pos,Object val) {this.array[pos] = val;} }public class TestDemo {public static void main(String[] args) {MyArray myArray = new MyArray();myArray.setVal(0,10);myArray.setVal(1,"hello");//字符串也可以存放String ret = myArray.getPos(1);//编译报错//强行转化String ret =(String)myArray.getPos(1);System.out.println(ret);}}
但是我们发现,虽然任何类型的数据都可以存放,但是获得的时候报错,必须强制转换。但是,当代码很多的变量的时候,我们就不知道该变量是什么类型的,每次都要返回定义的时候去查看是什么类型,就比较繁琐。更多情况下,我们还是希望他只能够持有一种数据类型。而不是同时持有这么多类型。所以,泛型的主要目的:就是指定当前的容器,要持有什么类型的对象。让编译器去做检查。此时,就需要把类型,作为参数传递。需要什么类型,就传入什么类型。
5.2语法
class MyArray<T> {//添加< >表示这个类是泛型public T[] array = (T[])new Object[10];//这句代码是错误的,这样写只是为了不让编译器报错public T getPos(int pos) {return this.array[pos];}public void setVal(int pos,T val) {this.array[pos] = val;}}public class TestDemo {public static void main(String[] args) {MyArray<Integer> myArray = new MyArray<>();//传入<Integer>后,每次存储数据时会检查存入的数据是不是我传入的类型,获取数据的时候也不需要强制转化。myArray.setVal(0,10);myArray.setVal(1,12);int ret = myArray.getPos(1);System.out.println(ret);myArray.setVal(2,"bit");}}
5.3泛型类的使用
语法:
泛型类<参数类型> 变量名; //定义一个泛型类引用
MyArray<Integer> a;
new 泛型类<类型实参>(构造方法实参); // 示例化一个泛型类对象
MyArray<Integer> myArray = new MyArray<>();
5.4泛型是如何编译
在编译过程中将所有的T替换为object,这种机制称为擦除机制,在运行的时候并没有泛型的概念。
通过命令:javap -c 查看字节码文件,所有的T都是Object:
在编译的过程当中,将所有的T替换为Object这种机制,我们称为:擦除机制。
Java的泛型机制是在编译级别实现的。
实例化的时候不能实例化一个泛型数组。
T[] a=new T[5];//这样定义泛型是错误的,这个时候我们不知道到底定义的什么类型的数组
//以我们现在的知识,一般定义数组的时候,我们采取以下方式:
object[] a=new obje[5];
5.5泛型的上界
在定义泛型类时,有时需要对传入的类型变量做一定的约束,可以通过类型边界来约束。
语法
class 泛型类名称<类型形参 extends 类型边界> {...}
MyArray<Integer> l1; // 正常,因为 Integer 是 Number 的子类型
MyArray<String> l2; // 编译错误,因为 String 不是 Number 的子类型
5.6泛型方法
定义语法:
方法限定符 <类型形参列表> 返回值类型 方法名称(形参列表) { ... }
示例:
public class Util {//静态的泛型方法 需要在static后用<>声明泛型类型参数public static <E> void swap(E[] array, int i, int j) {E t = array[i];array[i] = array[j];array[j] = t;}}//使用Integer[] a = { ... };Util.swap(a, 0, 9);//使用类型推导Util.<Integer>swap(a, 0, 9);//不使用类型推导
6.总结
本篇介绍数据结构基本知识主要包括集合框架,时间和空间复杂度,算法效率,大O渐进表示,包装类,泛型相关知识,其中关于用泛型定义数组的内容,博主比并没有深入讲解,感兴趣的同学可以查看其他博主的内容。
下期预告:顺序表
相关文章:
【数据结构(一)】初识数据结构
❣博主主页: 33的博客❣ ▶文章专栏分类: Java从入门到精通◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵关注我带你学更多数据结构知识 目录 1.前言2.集合架构3.时间和空间复杂度3.1算法效率3.2时间复杂度3.2.1大O的渐进…...
前端三剑客 —— CSS (第六节)
目录 内容回顾: 弹性布局属性介绍 案例演示 商品案例 布局分析 登录案例 网格布局 内容回顾: 变量:定义变量使用 --名称:值; 使用变量: 属性名:var(--名称)&a…...
MyBatis 解决上篇的参数绑定问题以及XML方式交互
前言 上文:MyBatis 初识简单操作-CSDN博客 上篇文章我们谈到的Spring中如何使用注解对Mysql进行交互 但是我们发现我们返回出来的数据明显有问题 我们发现后面三个字段的信息明显没有展示出来 下面我们来谈谈解决方案 解决方案 这里的原因本质上是因为mysql中和对象中的字段属性…...
Rust语言之属性宏(Attribute Macro)derive
文章目录 Rust语言之属性宏(Attribute Macro)derive Rust语言之属性宏(Attribute Macro)derive 属性宏是一种基于属性的宏,用于修改、扩展或注解 Rust 代码。它们通常用于为函数、结构体、枚举、模块等添加元数据或自…...
[技术闲聊]我对电路设计的理解(六)-原理图封装
电路设计的直观体现就是完整的原理图,绘制电路图阶段的第一步,绘制原理图封装库。 封装库一共有两种,一种是原理图封装库,一种是PCB封装库,如下图所示。 原理图封装和PCB封装之间的唯一关联就是 引脚位号,…...
算法(滑动窗口四)
1.串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words ["ab","cd","ef"]ÿ…...
学习记录:bazel和cmake运行终端指令
Bazel和CMake都是用于构建软件项目的工具,但它们之间有一些重要的区别和特点: Bazel: Bazel是由Google开发的构建和测试工具,用于构建大规模的软件项目。它采用一种称为“基于规则”的构建系统,它利用构建规则和依赖关…...
蓝桥杯刷题--python-37-分解质因数
3491. 完全平方数 - AcWing题库 nint(input()) res1 i2 while i*i<n: if n%i0: t0 while n%i0: n//i t1 if t%2: res*i i1 if n>1: res*n print(res) 4658. 质因数个数 - AcWing题库…...
Delphi编写的图片查看器
UNIT Unit17;INTERFACEUSESWinapi.Windows, Winapi.Messages, System.SysUtils, System.Variants,System.Classes, Vcl.Graphics, Vcl.Controls, Vcl.Forms, Vcl.Dialogs,Vcl.StdCtrls, Vcl.ExtDlgs, Vcl.ExtCtrls, Vcl.Imaging.jpeg; //注意:要加入jpej 否侧浏览图…...
Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐
前言 最近在开发swing客户端时候碰到一个棘手的问题: Swing中的FlowLayout/WrapLayout在打横排列时候如何做到置顶对齐如果是vue或者react,一搜百度什么都出来了,swing的话,嗯。。。资料有点少而且大部分是stack overflow上面的…...
C# MES通信从入门到精通(8)——C#调用Webservice服务进行数据交互
前言 在上位机开发领域,使用webservice来访问客户的终端Mes系统是一项必备的技能,本文详细介绍了如何在c#中调用webservice服务,不仅介绍了使用添加服务引用直接调用webservice中的方法外还介绍了使用http的post方法调用webservice方法,过程详细且均为实战经验总结,对于初…...
day04-MQ
1.初识MQ 1.1.同步和异步通讯 微服务间通讯有同步和异步两种方式: 同步通讯:就像打电话,需要实时响应。异步通讯:就像发邮件,不需要马上回复。 两种方式各有优劣,打电话可以立即得到响应,但是你…...
神经网络汇聚层
文章目录 最大汇聚层平均汇聚层自适应平均池化层 最大汇聚层 汇聚窗口从输入张量的左上角开始,从左往右、从上往下的在输入张量内滑动。在汇聚窗口到达的每个位置,它计算该窗口中输入子张量的最大值或平均值。计算最大值或平均值是取决于使用了最大汇聚…...
2024.3.8力扣每日一题——找出美丽数组的最小和
2024.3.8 题目来源我的题解方法一 数学 题目来源 力扣每日一题;题序:2834 我的题解 方法一 数学 经过分析,在target之前,取小于等于target/2的正整数才能使得和最小,并且满足条件3。 时间复杂度:O(n) 空…...
单例模式以及线程安全问题
单例模式的概念 单例模式是指的是整个系统生命周期内,保证一个类只能产生一个实例对象 保证类的唯一性 。 通过一些编码上的技巧,使编译器可以自动发现咱们的代码中是否有多个实例,并且在尝试创建多个实例的时候,直接编译出错。 …...
车载电子电器架构 —— 软件下载
车载电子电器架构 —— 软件下载 我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 屏蔽力是信息过载时代一个人的特殊竞争力,任何消耗你的人和事,多看一眼都是你的不对。非必要不费力证明自己,无…...
阿里云弹性计算通用算力型u1实例性能评测,性价比高
阿里云服务器u1是通用算力型云服务器,CPU采用2.5 GHz主频的Intel(R) Xeon(R) Platinum处理器,ECS通用算力型u1云服务器不适用于游戏和高频交易等需要极致性能的应用场景及对业务性能一致性有强诉求的应用场景(比如业务HA场景主备机需要性能一致)…...
Jupyter IPython帮助文档及其魔法命令
1.IPython 的帮助文档 使用 help() 使用 ? 使用 ?? tab 自动补全 shift tab 查看参数和函数说明 2.运行外部 Python 文件 使用下面命令运行外部 Python 文件(默认是当前目录,也可以使用绝对路径) %run *.py …...
设计模式总结-面向对象设计原则
面向对象设计原则 面向对象设计原则简介单一职责原则单一职责原则定义单一职责原则分析单一职责原则实例 开闭原则开闭原则定义开闭原则分析开闭原则实例 里氏代换原则里氏代换原则定义里氏代换原则分析 依赖倒转原则依赖倒转原则定义依赖倒转原则分析依赖倒转原则实例 接口隔离…...
绿联 安装zfile,创建属于自己的网盘,支持直链分享
绿联 安装zfile,创建属于自己的网盘,支持直链分享 1、镜像 zhaojun1998/zfile:latest ZFile ZFile 是一个适用于个人的在线网盘(列目录)程序,可以将你各个存储类型的存储源,统一到一个网页中查看、预览、维护,再也不用…...
KnowLog:基于知识增强的日志预训练语言模型|顶会ICSE 2024论文
徐波 东华大学副教授 东华大学计算机学院信息技术系副系主任,复旦大学知识工场实验室副主任,智能运维方向负责人。入选“上海市青年科技英才扬帆计划”。研究成果发表在IJCAI、ICDE、ICSE、ISSRE、ICWS、CIKM、COLING等国际会议上,曾获中国数…...
前端:用Sass简化媒体查询
在进行媒体查询的编写的时候,我们可以利用scss与与编译器,通过include混入的方式对代码进行简化,从而大大提高了代码的可维护性,也减少了代码的编写量,废话不多说,直接上代码 // 定义设备数值 $breakpoints…...
如何快速写出漂亮的Button按钮呢?
你是否曾在浏览网页时,被那些色彩鲜艳、功能多样的按钮所吸引?无论是提交表单,还是触发一个动作,按钮都扮演着不可或缺的角色。今天聊聊网页设计中的 <button> 标签。 1. 基础语法 什么是 <button> 标签 <butto…...
美摄科技AI智能图像矫正解决方案
图像已经成为了企业传播信息、展示产品的重要媒介,在日常拍摄过程中,由于摄影技巧的限制和拍摄环境的复杂多变,许多企业面临着图像内容倾斜、构图效果不佳等挑战,这无疑给企业的形象展示和信息传递带来了不小的困扰。 美摄科技深…...
上位机图像处理和嵌入式模块部署(qmacvisual查找圆缺角)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing 163.com】 前面我们讲过识别,讲过标定,讲过测量,讲过匹配,但就是没有讨论过基于图像的产品检测。但事实上&…...
Python 之 Fastapi 框架学习
依赖安装 Fastapi 有版本要求,需要的 Python 版本至少是 Python 3.8(不要犟,按照版本要求来,我最先也是在我 Python3.6 上装的,果不其然跑不起来),幸好我 Win7 老古董能支持的 Python 最高版本…...
C++初阶:stack和queue使用及模拟实现
stack的介绍和使用 stack的介绍 堆栈 - C 参考 (cplusplus.com) 翻译 : 1. stack 是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。 2. stack 是作为容器适配器被实现的,容器…...
LINUX系统CFS调度模型实现思考和仿真
关于LINUX资源调度 计算机系统中,管理资源的方式一般有两种方法,分别是时间分割和空间分割,可以通过分割硬件的相似性,让软件以一致的逻辑执行,CPU运行特点是在时刻点A和时刻B运行机制是一样的,不同的只是…...
兑换码生成算法
兑换码生成算法 兑换码生成算法1.兑换码的需求2.算法分析2.重兑校验算法3.防刷校验算法 3.算法实现 兑换码生成算法 兑换码生成通常涉及在特定场景下为用户提供特定产品或服务的权益或礼品,典型的应用场景包括优惠券、礼品卡、会员权益等。 1.兑换码的需求 要求如…...
Vue框架介绍简介
Vue.js,通常简称为Vue,是一个用于构建用户界面的渐进式框架。它发布于2014年2月,由Evan You设计并开发。Vue被设计为可以自底向上逐层应用,这使得开发者可以根据项目的需求灵活地使用Vue。无论是构建简单的轻量级应用,…...
个人做购物商城网站会罚款吗/谷歌推广费用
IT-网站技术 泛域名 第一步:泛域名的解析 首先我要给大家讲一个故事:故事的内容是“泛域名”。从前啊,有个小朋友叫做“泛域名”,泛域名 是谁家的小孩呢?知道DOS 伯伯吗?唉~~对了&a…...
定制开发电商网站建设多少钱/手机百度高级搜索入口在哪里
目录 文章目录目录RSS 多队列网卡RSS 技术实现原理RSS FilterRSS HASH硬中断信号绑定ethtool 操作指令RSS 多队列网卡 在以往,一张 NIC 只具有一个 Rx Queue,对应一个 CPU Core 来进行收包处理。在多核时代,为了充分利用 Multi-CPU Cores&am…...
网站快速搜索/网站搜索引擎优化主要方法
http://blog.csdn.net/yangyk125/article/details/29216149 多媒体编程——摄像头录像预览 1、 新建MFC工程,选择对话框工程。 2、新建一个static控件。 3、修改ID,并且在OnInitDialog里面获取指针。 4、加一个成员函数,并且在OnInitDialog…...
鸡西市网站建设/源云推广
目录一. 复习事物隔离级别事物隔离级别中可能涉及到的几个问题版本链二. MVCC什么是当前读,快照读什么是ReadView不同隔离解绑下 ReadView 的生成规则MVCC下可见性判断流程1. 读取已提交隔离级别下执行示例2. 可重复读隔离级别下执行示例如何解决幻读为什么可重复读隔离级别下是…...
网页制作网站创建/浙江网站推广运营
Bessel函数介绍贝塞尔函数(Bessel functions)是数学上的一类特殊函数的总称。一般贝塞尔函数是下列常微分方程(一般称为贝塞尔方程)的标准解函数y(x):这类方程的解是无法用初等函数系统地表示的。贝塞尔函数的具体形式随上述方程中任意实数α变化而变化(相应地&…...
网站建设江西/如何建立免费个人网站
程序段:?1234567vector <int> vecInt;for (int i0;i<500;i){vecInt.push_back(i);}int j vecInt.capacity(); //j512i vecInt.size(); //i500?办法1 : 使用 clear ,清空元素,但不回收空间. ?123vecInt.clear();j vecInt.capacity(); //j5…...