当前位置: 首页 > news >正文

数据结构期末复习总结(前章)

作者的话

作为一名计算机类的学生,我深知数据结构的重要性。在期末复习前,我希望通过这篇博客给大家一些复习建议。希望能帮助大家夯实数据结构的基础知识,并能够更好地掌握数据结构和算法的应用。

一、绪论

数据:信息的载体,所有能输入到计算机中,被计算机程序识别和处理的符号的集合

数据元素是数据的基本单位,数据项是数据的最小单位
数据结构 = {D, R}
D:数据元素
R:数据元素间的关系
数据结构是指数据元素之间的逻辑关系,即数据的逻辑结构,与数据的存储无关

数据对象是性质相同的数据元素的集合。
抽象数据类型:信息隐蔽,数据封装,使用与实现相分离
面向对象 = 对象+类+继承+通信

数据结构包括逻辑结构和存储结构两个层次

1.1数据的逻辑结构

逻辑结构包括:线性结构、非线性结构

  1. 线性结构:
  • 集合中存在唯一一个“第一个元素”
  • 集合中存在唯一一个“最后一个元素”
  • 除最后一个元素之外,其他数据元素均有唯一的“后继”
  • 除第一个元素之外,其他数据元素均有唯一的“前驱”
  1. 非线性结构:包括树形结构、图形结构
  2. 集合结构
  • 一对多

1.2数据的物理结构

物理结构包括:

  • 顺序存储方法、链式存储方法、索引存储方法、散列存储方法

数据在计算机内存中的表示

1.3算法的基本概念

算法分析是评估算法性能的过程,包括时间复杂度和空间复杂度。时间复杂度是指算法执行所需的时间,通常用大O表示法表示。空间复杂度是指算法执行所需的内存空间。

在这里插入图片描述

算法原地工作:空间复杂度为O(1)

算法是解决问题的有限运算序列 

算法的时间复杂度不仅与问题的规模有关,还与问题的其他因素有关。如某些 排序的算法,其执行时间与待排序记录的初始状态有关

算法的设计目标:

  • 正确性、可使用性、可读性、健壮性、效率

算法的特性:

  • 有穷性、确定性、输入、输出、可行性

二:线性表

2.1相关概念

存储密度越大.存储空间的利用率就越高。显然,顺序表的在储密度为1而链表的存储密
度小于1

顺序表存取元素效率高,链表插入和删除元素效率高

在顺序表中插入一个结点的时间复杂度都是 O(n 2 ),排序的时间复杂度为 O(n 2 ) 或 O(nlog2n)

三:栈和队列

栈(Stack)是一种基本的数据结构,它具有后进先出(Last-In-First-Out,LIFO)的特性。这意味着最后插入的元素最先被删除,而最先插入的元素最后被删除。

栈在递归调用函数调用表达式求值都有所应用
队列(Queue)是一种基于先进先出(FIFO,First-In-First-Out)原则的数据结构,类似于现实生活中的排队等候。队列只允许在一端插入元素,在另一端删除元素,插入操作在队尾进行,删除操作在队头进行。

用链接方式存储的队列,在进行删除运算时一般情况下只修改头指针,但是,当删除的是队列中最后一个元素时,队尾指 15 针也丢失了,因此需对队尾指针重新赋值。

 中序表达式转后序表达式

 技巧:加括号符号后撤 

四、串

 

KMP 算法

在这里插入图片描述

手工求解 next 数组,nextval数组

在这里插入图片描述

例题:求模式串的比较次数

2019 年 408 统考真题
设主串 T=“abaabaabcabaabc”,模式串 S=“abaabc”,采用 KMP 算法进行模式匹配,到匹配成功时为止,在 匹配过程中进行的单个字符间的比较次数是?

解答

在这里插入图片描述

五、数组、矩阵和广义表

1.对称矩阵在这里插入图片描述

公式

k=\left\{\begin{array}{ll} \frac{i(i-1)}{2}+j-1 & i \geqslant j \\ \frac{j(j-1)}{2}+i-1 & i<j \end{array}\right.

2.上/下三角矩阵 

同对称矩阵

3.稀疏矩阵在这里插入图片描述

对于一个稀疏矩阵的三元组表示,我们可以用以下公式计算其所需的字符数(假设每个索引和值都需要占用2个字节):

字符数 = 6 * 非零元素个数
其中,6表示每个三元组需要占用6个字符(2个字符用于表示每个索引,2个字符用于表示值,另外再加上2个字符用于分隔三元组)。

4.广义表 

  • 长度:广义表中最上层元素的个数
  • 深度:表中括号的最大层数
  • 表头:第一个元素
  • 表尾:除表头之外的所有元素组成的表

表头为非空广义表的第一个元素,可以是一个单原子,也可以是一个子表, ((a,b,c,d))的表头为一个子表(a,b,c,d);表尾为除去表头之外,由其余元素构成的表,表为一定 是个广义表,((a,b,c,d))的表尾为空表( )。

广义表的深度是指广义表中展开后所含括号的层数,广义表的长度是指广义表 中所含元素的个数。

相关文章:

数据结构期末复习总结(前章)

作者的话 作为一名计算机类的学生&#xff0c;我深知数据结构的重要性。在期末复习前&#xff0c;我希望通过这篇博客给大家一些复习建议。希望能帮助大家夯实数据结构的基础知识&#xff0c;并能够更好地掌握数据结构和算法的应用。 一、绪论 数据&#xff1a;信息的载体&am…...

设计环形队列

文章目录1.思路分析1.1队列空满分析1.2出队分析2.循环队列设计1.思路分析 1.1队列空满分析 首先我们假设一个长度为4的环形队列 队头front 队尾rear 当队列为空时 frontrear 当队列满时 frontrear 所以我们无法判断队列是满的或者空的 因此我们多加入一个空间使队列长度为5&am…...

面向对象之-接口鉴权

1 需求 1.1 需求背景 为了保证接口调用的安全性&#xff0c;我们希望设计实现一个接口调用鉴权功能&#xff0c;只有经过认证之后的系统才能调用我们的接口&#xff0c;没有认证过的系统调用我们的接口会被拒绝。 2 需求分析 2.1 基础分析 对于如何做鉴权这样一个问题&…...

Python 多进程多线程线程池进程池协程

目录 一、线程与进程很简单的介绍 1.1 线程与进程的区别 二、多进程Process 2.1 多进程与多线程的区别 2.2 多进程为啥要使用队列 2.3 控制进程运行顺序 2.3.1 join &#xff0c; 2.3.1 daemon 守护进程 2.4 进程id 2.5 进程 存活状态is_alive() 2.5 实现自定义多…...

【自然语言处理】基于句子嵌入的文本摘要算法实现

基于句子嵌入的文本摘要算法实现人们在理解了文本的含义后&#xff0c;很容易用自己的话对文本进行总结。但在数据过多、缺乏人力和时间的情况下&#xff0c;自动文本摘要则显得至关重要。一般使用自动文本摘要的原因包括&#xff1a; 减少阅读时间根据摘要&#xff0c;选择自…...

fiddler抓包

一、工具介绍Fiddler是一个通过代理的方式来进行抓包工具&#xff0c;运行时会在本地建立一个代理服务&#xff0c;默认地址&#xff1a;127.0.0.1:8888。Fiddler开启之后&#xff0c;配置本机代理&#xff0c;再打开IE浏览器&#xff0c;IE的PROXY会自动变成127.0.0.1:8888&am…...

【Linux】网络套接字编程

前言 在掌握一定的网络基础&#xff0c;我们便可以先从代码入手&#xff0c;利用UDP协议/TCP协议进行编写套接字程序&#xff0c;明白网络中服务器端与客户端之间如何进行连接并且通信的。 目录 一、了解源目的IP、端口、网络字节序、套接字 端口号&#xff1a; 套接字&…...

break与continue关键字

1.概述 不知道大家有没有这样一种感受哈&#xff0c;有的时候容易混淆break语句和continue语句的用法&#xff0c;总是模棱两可&#xff0c;不敢确定自己是否使用正确了。正好&#xff0c;我们本篇的重点就是break和continue关键字的用法。 2.使用场景 Java中为啥会诞生break…...

kafka使用入门案例与踩坑记录

每次用到kafka时都会出现各种奇怪的问题&#xff0c;综合实践&#xff0c;下面汇总下主要操作步骤&#xff1a; Docker镜像形式启动 zookeeper启动 docker run -d --name zookeeper -p 2181:2181 -t wurstmeister/zookeeperkafka启动 docker run --name kafka01 -p 9092:909…...

系统启动太慢,调优后我直呼Nice

问题背景最近在负责一个订单系统的业务研发&#xff0c;本来不是件困难的事。但是服务的启动时间很慢&#xff0c;慢的令人发指。单次启动的时间约在10多分钟左右&#xff0c;基本一次迭代、开发&#xff0c;大部分的时间都花在了启动项目上。忍无可忍的我&#xff0c;终于决定…...

java知识点

文章目录异常写法JVM加载反射访问private调用方法动态代理注解元数据&#xff1a;TargetRetention元注解泛型编写泛型擦拭法局限通配符无限定通配符(<?>)集合重写方法和实现类IO流字节与字符转换同步和异步可以设置编码的类Print*类Files时间与日期时区一种二种三种异常…...

文件的打开关闭和顺序读写

目录 一、文件的打开与关闭 &#xff08;一&#xff09;文件指针 &#xff08;二&#xff09; 文件的打开和关闭 二、文件的顺序读写 &#xff08;一&#xff09;fputc 1. 介绍 2. 举例 &#xff08;二&#xff09;fgetc 1. 介绍 2. 举例1 3. 举例2 &#xff08;三&…...

(十八)操作系统-进程互斥的软件实现方法

文章目录一、知识总览二、单标志法三、双标志先检查法四、双标志后检查法五、Peterson算法六、总结一、知识总览 二、单标志法 算法思想&#xff1a;两个进程在访问临界区后&#xff0c;会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进…...

2023年三月份图形化一级打卡试题

活动时间 从2023年3月1日至3月21日&#xff0c;每天一道编程题。 本次打卡的规则如下&#xff1a; 小朋友每天利用10~15分钟做一道编程题&#xff0c;遇到问题就来群内讨论&#xff0c;我来给大家答疑。 小朋友做完题目后&#xff0c;截图到朋友圈打卡并把打卡的截图发到活动群…...

linux 防火墙管理-firewalld

什么是Firewalld 当前很多linux系统中都默认使用 firewalld&#xff08;Dynamic Firewall Manager of Linux systems&#xff0c;Linux系统的动态防火墙管理器&#xff09;服务作为防火墙配置管理工具。 “firewalld”是firewall daemon。它提供了一个动态管理的防火墙&#x…...

2023年最新大厂开发面试题(滴滴,华为,京东,腾讯,头条)

2023年最新大厂开发面试题&#xff01;&#xff01;&#xff01; 滴滴篇 B树、B-树的区别? 数据库隔离级别&#xff0c;幻读和不可重复读的区别&#xff1f; 有 hell, well, hello, world 等字符串组&#xff0c;现在问能否拼接成 helloworld&#xff0c;代码实现。 快排算…...

2023年三月份图形化三级打卡试题

活动时间 从2023年3月1日至3月21日&#xff0c;每天一道编程题。 本次打卡的规则如下&#xff1a; 小朋友每天利用10~15分钟做一道编程题&#xff0c;遇到问题就来群内讨论&#xff0c;我来给大家答疑。 小朋友做完题目后&#xff0c;截图到朋友圈打卡并把打卡的截图发到活动群…...

蓝桥杯算法模板

模拟散列表拉链法import java.io.*; import java.util.*; public class a1 {static int n;static int N100003;static int[] hnew int[N];static int[] enew int[N];static int[] nenew int[N]; static int idx; static void insert(int x){int k(x%NN)%N;e[idx]x;ne[idx]h[k];…...

python之并发编程

一、并发编程之多进程 1.multiprocessing模块介绍 python中的多线程无法利用多核优势&#xff0c;如果想要充分地使用多核CPU的资源&#xff08;os.cpu_count()查看&#xff09;&#xff0c;在python中大部分情况需要使用多进程。Python提供了multiprocessing。 multiprocess…...

Vue.js自定义事件的使用(实现父子之间的通信)

vue v-model修饰符&#xff1a;.lazy、.number、.trim $attrs数据的透传&#xff0c;在组件&#xff08;这个是写在App.vue中&#xff09;,数据就透传到student组件中&#xff0c;在template中可以直接使用{{$attrs.students}}获取数据 通过defineProps定义的属性在attrs中就…...

调用支付宝接口响应40004 SYSTEM_ERROR问题排查

在对接支付宝API的时候&#xff0c;遇到了一些问题&#xff0c;记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...