数据结构与算法(一):概述
数据结构学了有一年左右的时间了,但是一直没有详细地总结一下,现在回想起来,感觉有些内容忘记了。所以接下来一段时间我将重新归纳总结一下,算是温故而知新了。
一、数据结构
1、定义
数据结构是计算机存储、组织数据的方式。在现实世界中,不同数据元素之间不是独立的,而是存在特定关系的,我们将这些关系称为结构。同样在计算机中,数据元素也不是孤立、杂乱无序的,而是具有内在联系的数据集合。
数据元素之间存在的一种或多种特定关系,也就是数据的组织形式,叫数据结构。也可以说,数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。程序设计的实质就是数据结构和算法是设计,因此我们说程序设计 = 数据结构 + 算法。
2、数据结构的几个术语
-
数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。它不仅包括整型等数值类型,还包括字符、声音、图像等非数值类型。这些类型都具备两个特征:
- 可以输入计算机
- 能被计算机程序处理
-
数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。
-
数据项:一个数据元素可以由若干个数据项组成。数据项是A数据的不可分割的最小单位。。
-
数据对象:是性质相同的数据元素的集合,是数据的子集。
例如:一本书的书目信息为一个数据元素,而书目信息的每一项(如书名、作者名等)为一个数据项。
3、逻辑结构与物理结构
按照不同的角度,数据结构可分为逻辑结构和物理结构。其中逻辑结构是面向问题的,而物理结构是面向计算机的,它们的基本目标都是将数据及其逻辑关系存储到计算机内存中。
- 逻辑结构:是指数据对象中数据元素之间的相互关系。分为四种:集合结构、线性结构、树形结构和图形结构。
- 物理(存储)结构:是指数据的逻辑结构在计算机中的存储形式。数据的存储结构应正确反映数据元素之间的逻辑关系,这是关键。数据元素的存储结构可分为两种:顺序存储结构和链式存储结构。
- 顺序存储结构:把数据元素放在地址连续的存储单元中,数据间的逻辑关系和物理关系一致。如,数组。
- 链式存储结构:把数据元素放在任意的存储单元中,数据间使用指针关联。数据元素的存储关系不能反映其逻辑关系。如,链表。
同样的逻辑结构(线性、树形、图形、集合)既可以采用顺序存储结构也可以采用链式存储结构来存储数据和关系。存储结构的选择主要考虑算法的效率,算法的时间和空间哪个更好,具体选择哪种和需求有关,基本存储结构既可以单独使用,也可以组合使用。
二、抽象数据类型
数据类型是指一组性质相同的值的集合及定义在该集合上的一些操作的总称。而抽象是指抽象出事物具有的普遍性的本质,它是抽出问题的特征而忽略非本质的细节,是对具体事物的一个概括。抽象隐藏了繁杂的细节,只保留实现目标所必须的信息。因此抽象数据类型可以定义为:
抽象数据类型(Abstract Data Type,ADT)是指一个数学模型及定义在该模型上的一组操作,它是一种向用例隐藏内部表示的数据类型。
面向对象编程的特征之一就是使用数据类型的实现封装数据,以简化实现、隔离用例开发、实现模块化编程。抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。它将实际生活中的问题分解为多个规模小、能够独立开发和调试的小型模块,然后进行独立编程。这种方式将代码的影响限制在局部区域,改进了我们的软件质量,促进了代码复用。抽象数据类型抽象的层次越高,那么可复用性也越强。比如:java中的Object是对所有对象的抽象。
java中数据类型可以分为两类:
- 基本(原子)类型:不可以再分解的基本类型,包括int、short、long等
- 引用(结构)类型:由其他类型组合而成,可以再分解。如,String、数组等
注意:
- 对原子类型的操作不一定是原子操作,这点并发编程时应特别注意。如,在32位机上对long类型的操作就不是原子操作,因为其高32位和低32位是分别存储的。
- Java中所有的基本数据类型都有固定的存储范围和大小,其不受具体机器和操作系统的影响。
三、算法
算法(Algorithm)一词最早出现在波斯数学家al-Khwarizmi所写的《印度数字算术》中。欧几里得算法(求两个整数的最大公约数)被认为是史上第一个算法。
算法是解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
1、算法的基本特性
- 输入输出,算法具有零个或多个输入,至少有一个或多个输出。
- 有穷性,算法在执行有限步后能够自动结束,不会出现无限循环。
- 确定性,算法的每一步都具有确定的含义,不会出现二义性。
- 可行性,算法的每一步都能够通过执行有限次操作完成。
2、程序与算法的区别
程序(program)是软件开发人员根据用户需求开发的、用程序设计语言描述的适合计算机执行的指令(语句)序列。它包括「数据结构」、「算法」、「程序设计方法」和「编程语言」。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的有穷性,比如操作系统也是一种程序,它可以一直运行。
3、算法的设计要求
- 正确性,算法至少应该具有输入、输出和加工处理无歧义、能正确反映问题的需求、能够得到问题的正确答案。
- 可读性,便于阅读、理解和交流。
- 健壮性,输入不合法时,算法能够给出相应的处理,而不是产生错误的结果。
- 高效性,算法应该尽量满足高效率和低存储的需求。
四、算法的复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用: 时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。
1、时间复杂度
算法的时间复杂度反映了算法执行的时间长短,它是度量一个算法好坏的重要指标。
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
度量一个算法的时间复杂度通常有两种方式:
- 事后统计法
- 事前分析法(大O表示法)
算法的时间复杂度是由最深层嵌套语句的频度决定的。
大O表示法的推导:
- 用常数1取代运行时间中的所有加法常数
- 在修改后的运行次数函数中,只保留最高阶
- 将最高阶系数变为1
例1:
int i, j, temp;
for(i=0; i<n; i++) {for(j=i, j<n; j++) {temp++;}
}
语句执行的总次数:
其时间复杂度为O(n^2)。
例2:
for(i=1;i<=n;i=i*2){System.out.println(i);
}
执行的总次数满足:
所以它的时间复杂度为O(logn)
例3:分析冒泡排序算法的时间复杂度
//冒泡排序算法
public static void bubbleSort(int[] data) {if (data == null) {return;}int temp = 0;for (int i = data.length - 1; i > 0; --i){for (int j = 0; j < i; ++j){if (data[j + 1] < data[j]){temp = data[j];data[j] = data[j + 1];data[j + 1] = temp;}}}
}
算法分析:
常见时间复杂度大小关系:
算法的时间复杂度和两个因素有关:算法中的最大嵌套循环层数;最大嵌套循环结构中每次循环的次数。一般来说,具有多项式时间复杂度的算法是可以接受的;具有指数时间复杂度的算法,只有当n足够小时才可以使用。一般效率较好的算法要控制在O(N)或者O(log2 N)
2、空间复杂度
空间复杂度(Space Complexity)是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。其中,n为问题规模,f(n)为语句关于n所占存储空间的函数。
算法的空间复杂度分析方法和算法的时间复杂度分析方法基本相同。
例如:
int i, j, temp;
for(i=0; i<n; i++) {for(j=i, j<n; j++) {temp++;}
}
上方代码中,仅需为变量 i、j、temp分配空间即可,所以空间复杂度 S(n)=O(1)。
相关文章:

数据结构与算法(一):概述
数据结构学了有一年左右的时间了,但是一直没有详细地总结一下,现在回想起来,感觉有些内容忘记了。所以接下来一段时间我将重新归纳总结一下,算是温故而知新了。 一、数据结构 1、定义 数据结构是计算机存储、组织数据的方式。在…...
Spring3之Bean的属性详解
简介 Spring 中大量使用到 Bean 的注入来实现各个模块之间的依赖,本章将详细介绍 Bean 的主要属性 id 和 name 属性 每个 Bean 可以有一个 id 属性,并可以根据该 id 在 IoC 容器中查找该 Bean,该 id 属性值必须在IoC 容器中唯一 可以不指定…...

C语言之结构体内存的计算
结构体的内存 一.提出疑问 结构体占用的是一片连续的内存空间,大小是由成员变量的类型决定的。但并不是计算所有成员变量的类型大小之和那么简单。 先举一个实例: struct student {int age; //4个字节int telephone; //4个字节 }; int main() {struc…...

Java网络编程之UDP和TCP套接字
文章目录一. 网络编程概述二. UDP网络编程1. UDP套接字2. UDP客户端回显服务器程序2.1 UDP回显服务器2.2 UDP客户端2.3 UDP实现查词典的服务器三. TCP网络编程1. TCP套接字2. TCP客户端回显服务器程序2.1 TCP回显服务器2.2 TCP客户端2.3 解决服务器无法同时出力多个客户端的问题…...

Linux进程信号产生以及捕捉
一.什么是信号 生活中,有哪些信号相关的场景呢,比如:红绿灯,闹钟,转向灯等等 1.这里我们要知道,你为什么认识这些信号呢,记住了对应场景下的信号+后续是有”动作“要你执行的 2.我们…...
11. GLSL(OpenGL Shader Language)常用知识点汇总
1. 说明: 在使用OPenGL进行三维模型渲染时,需要使用到两个着色器对模型进行位置设置和颜色设置,分别为顶点着色器和片段着色器,这两个着色器是使用 GLSL 语法进行编写的。这篇文章总结了一些GLSL中的一些基本语法知识。 2. 基本…...

转发一张网络工程师考试的试卷2021.5.15
网络工程师考试 单选题 (30题,每题1分,共30分) 1. 你在一个网络中实现DHCP服务,配置一些计算机成为DHCP客户端,由于工作需要,一台系统为Windows 10 的客户端要把从DHCP服务器获得的地址释放&a…...

AMD发布23.2.1 新驱动 支持开年新作《魔咒之地》
如果说2023年有什么新作,《魔咒之地(Forspoken)》当属开年大作之一,1月25日才在steam平台发售。虽然开售后的表现似乎不如想象中优秀,加之价格相对昂贵,令不少玩家望而却步,但如果只是想尝鲜&am…...
开放平台如何做接口的签名和加解密?
目录安全性功能介绍实现流程开放平台依赖代码AES加解密工具类PlatformConfigRequestUtilsPlatformServiceCommonCodeZuulFilterHelperServerResponsePlatformContactRsaSignatureRsaUtilsStreamUtil开放平台-解密过滤器开放平台-加密过滤器调用方代码公共代码Get-DemoPost-Demo…...

Mr. Cappuccino的第40杯咖啡——Kubernetes之Pod生命周期
Kubernetes之Pod生命周期Pod生命周期官方文档Pod的状态初始化容器案例钩子函数Exec命令TCPSocketHTTPGet案例容器探测Exec命令TCPSocketHTTPGet探测时间重启策略Pod生命周期官方文档 Pod生命周期官方文档 Pod的状态 pending:挂起,apiserver创建了pod资…...

记一次OOM
1,问题描述: 新上了一版代码之后,上游服务请求我们服务失败,报错:“服务不可用”,发现注册中心上服务掉线,查询日志:发现oom:Java heap space,GC overhead limit exceeded。 容易…...

idea插件生成dao类service类controller类以及mapper.xml
idea插件生成dao类service类controller类以及mapper.xml 安装插件Easycode和MybatisX,不用自己写代码 1.Files——》Settings——》Plugins,分别搜索Easycode和MybatisX,点击下载。 2.新建一个springboot模板,选择的依赖如下 3.…...
DML 数据操作语言
概述 DML英文全称是Data Manipulation Language(数据操作语言),用来对数据库中表的数据记录进行增、删、改操作。 添加数据(INSERT)修改数据(UPDATE)删除数据(DELETE) 添加数据 1、给指定字段…...

PySpark实战一之入门
1、PySpark的编程模型 分三个模块: 数据输入:通过SparkContext对象,完成数据输入 数据处理计算:输入数据后得到RDD对象,对RDD对象的成员方法进行迭代计算 数据输出:最后通过RDD对象的成员方法࿰…...

【DockerCE】Docker-CE 23.0.1正式版发布
很意外啊!Docker社区版竟然直接从20.xx.xx版本,升级到23.xx.xx版本了。官网地址(For RHEL/CentOS 7.9):https://download.docker.com/linux/centos/7/x86_64/stable/Packages/23.0.1版本官方安装包如下:# l…...

vscode开发的Vue家用电器维修服务系统nodejs+mysql
主要功能包括管理员:首页、个人中心、用户管理、维修员管理、维修信息管理、维修申请管理、维修处理管理、家电类别管理、配件信息管理、配件领用管理、维修结果管理、家电维修知识管理、公告信息管理、留言板管理,用户:首页、个人中心、维修…...

PyQt5数据库开发1 4.2 配置SQL Server 2008 数据源(ODBC编程)
文章目录 配置SQL Server 2008 数据源(ODBC编程) 1. 了解要配置的数据源服务器名称,以及数据库和对应表 2. 打开控制面板,点击管理工具 3. 双击数据源 4. 选择“用户DSN”选项卡,点击“添加” 5. 选择SQL Serv…...

【JavaEE】多线程代码实例:单例模式与阻塞队列BlockingQueue
目录 单例模式: 什么是单例模式? 单例模式的实现方式: 饿汉模式: 懒汉模式: 基于并发编程对单例模式线程安全问题的讨论: 阻塞队列: 标准库中的阻塞队列: 自实现阻塞…...

算法思想 - 搜索算法
本文主要介绍算法中搜索算法的思想,主要包含BFS,DFS。搜索相关题目深度优先搜索和广度优先搜索广泛运用于树和图中,但是它们的应用远远不止如此。BFS广度优先搜索的搜索过程有点像一层一层地进行遍历,每层遍历都以上一层遍历的结果…...

C#底层库--日期扩展类(上周、本周、明年、前年等)
系列文章 C#底层库–记录日志帮助类 本文链接:https://blog.csdn.net/youcheng_ge/article/details/124187709 C#底层库–数据库访问帮助类(MySQL版) 本文链接:https://blog.csdn.net/youcheng_ge/article/details/126886379 …...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...

Python实现prophet 理论及参数优化
文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候,写过一篇简单实现,后期随着对该模型的深入研究,本次记录涉及到prophet 的公式以及参数调优,从公式可以更直观…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...

让AI看见世界:MCP协议与服务器的工作原理
让AI看见世界:MCP协议与服务器的工作原理 MCP(Model Context Protocol)是一种创新的通信协议,旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天,MCP正成为连接AI与现实世界的重要桥梁。…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...

基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...