软件设计师笔记-数据结构

数据结构

数据元素的集合及元素间的相互关系和构造方法。

线性表的存储结构

  • 顺序存储
  • 链式存储

单链表节点

typedef struct node { int data; struct node *link; 
}NODE, *LinkList; 

双向链表

每个节点有两个指针,分别指出直接前驱和直接后继。

循环链表

尾节点指针指向第一个节点。

静态链表

借助数组来描述线性表的链式存储结构。

  • 特点:后进先出
  • 初始化栈: InitStack(S)
  • 判栈空:StackEmpty(S)
  • 入栈:Push(S,x)
  • 出栈:Pop(S)
  • 读取栈顶元素:Top(S)-----顺序存储+链式存储

队列

  • 特点:先进先出,尾入头出
  • 初始化队列:InitQueue(Q)
  • 判队空:Empty(Q)
  • 入队:EnQueue(Q,x)
  • 出队:DeQueue(Q)
  • 读队头元素:FrontQue(Q)-----顺序存储+链式存储

仅由字符构成的有限序列,是取值范围受限的线性表。

数组

定长线性表在维数上的扩张,一般不做插入删除运算。

矩阵

  • 特殊矩阵:元素分布有一定的规律(对称矩阵、三角矩阵、对角矩阵)
  • 稀疏矩阵:非零元素远少于零元素且分布无规律,用三元组存储(行号,列号,值)

广义表

  • 表中有表
  • 表头:表中第一个元素
  • 表尾:表中除去表头剩下的部分

  • 递归的,元素之间有明显的层次关系。
  • 完全二叉树应采用顺序存储结构,一般二叉树则应采用链式存储结构
  • 二 叉 树 的 链 式 存 储 结 构:
    typedef struct BiTnode {int data; struct BiTnode *lchild, *rchild; }BiTnode, *BiTree; 
    

二叉树的遍历

  • 先序遍历(先访问根节点)
  • 中序遍历(第二访问根节点)
  • 后序遍历(最后访问根节点)
  • 层序遍历(利用队列、每次出同一层的节点时进他们的子节点层)

线索二叉树

加上线索(直接前驱和直接后继)的二叉树。

最优二叉树(哈夫曼树)

一类带权路径长度最短的树。

树的存储结构

  • 双亲表示法:顺序存储
  • 孩子表示:链式存储
  • 孩子兄弟表示:链式存储,两个指针分别为第一个孩子和下一个兄弟

一个节点的前驱节点和后继节点数目没有任何限制。

图的表示

  • G=(V,E);
  • V:顶点的集合;

边带权值的图。

图的相关概念

在这里插入图片描述

图的存储结构

  • 邻接矩阵表示法
  • 邻接链表表示法

图的遍历

  • 深度优先搜索
  • 广度优先搜索

生成树

极小连通子图,针对连通图。

最小生成树(权值和最小的生成树)算法

  • 普尼姆算法:在相邻边的基础上求最小,与边数无关,适于边稠密的网。
  • 克鲁斯科尔算法:在不构成环的基础上找最小边直至连通,与顶点数无关,适于边稀疏的网。

AOV 网

有向图中顶点表示活动,有向边表示活动间的优先关系。

拓扑排序

将 AOV 网中所有顶点按优先顺序排成一个线性序列的过程。

AOE 网

有向图中有向边表示活动,边上的权值表示该活动持续的时间。

关键路径

从源点到汇点的路径中长度最长的。

最短路径

从源点到其余各顶点的最短路径-----迪杰斯克拉算法。

平均查找长度

关键字和给定值进行过比较的记录个数的平均值。

静态查找方法

  • 顺序查找
  • 折半查找
  • 分块查找

动态查找

表结构本身在查找过程中是动态生成的。

二叉排序树

左子树上所有节点的值小于根节点的值,右子树上所有节点的值大于根节
点的值。

平衡二叉树(AVL 树)

左子树和右子树高度之差的绝对值不超过1 。

B_树(m 阶)

每个节点子树个数<=m,根节点子树个数=0 或>=2,其他节点子树个数=0
或>=m/2。

哈希表

  • 通过哈希函数(以记录的关键字为自变量)得到记录的存储地址
  • 定长按一定函数规律存放数据
  • 哈希地址+关键字

哈希表的重点

  • 构造哈希函数:直接定址法,数字分析法,平方取中法,折叠法,随机
    数法,除留余数法
    解决冲突:开放定址法,链地址法,再哈希法

简单排序

  • 时间复杂度 O( n 2 n^2 n2),空间复杂度 O( 1 1 1))
  • 直接插入排序:插入第 i 个时,前 i-1 个已经排序好
  • 冒泡排序:相邻两个比较排序,每次循环确定一个极值
  • 简单选择排序:第 i个依次与后面每个元素比较排序,每次循环确定一个极值,不稳定

高端内部排序

  • 希尔排序:先将整个序列分割成若干序列分别进行直接插入排序,再对整个序列进行一次直接插入排序,不稳定
  • 快速排序:将整个记录分割成独立的两部分,两个指针分别指向对应部分的两端,往中间移动比较排序,递归,不稳定
  • 堆排序:建立初始堆输出并删除堆顶关键字,再建立新堆得到新的关键字依次输出,不稳定
  • 归并排序:将若干个有序序列合并为新的有序序列
  • 基数排序:按组成关键字的各个数位的值进行排序

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/4627.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

LangChain Ollama实战文献检索助手(一)环境配置和输入输出解析

挑选合适的模型 调用API需要花钱&#xff0c;因此在搭建阶段最佳的方法是利用Ollama部署本地CPU推理的轻量化大模型。大模型选择可以参照hugging face的榜单open-llm-leaderboard。 这里对我来说&#xff0c;要选择的模型需要满足 1.ollama上有的模型。 2.推理速度快&#xff…

在docker中搭建redis哨兵环境

文章目录 一、引言二、环境准备前提条件目录结构 三、配置文件1. 主节点配置文件 sentinel-master.conf2. 从节点配置文件3. 哨兵配置文件 sentinel.conf4. Docker Compose 文件 四、启动 Docker Compose五、验证哨兵机制1. 检查主节点状态2. 检查从节点状态3. 检查哨兵状态4. …

上线不出网机器

不出网机器介绍 上线不出网机器是我们常见的问题&#xff0c;如何在内网中实现不出网机器的上线呢&#xff0c;我们分为了如下的形式&#xff0c;根据之前所学的内容我们开始进行实验&#xff0c;常见的网络拓扑如下 情况分类 上线不出网机器一般是指B区域的电脑上线到CS工具或…

Modbus解析流程全面升级:体验全新核心与终极优化!

01 前言 本文章原文发表于我的微信公众号&#xff0c;请大家关注阅读&#xff0c;涉及的源代码等都在公众号&#xff0c;请搜索公众号&#xff1a; 智能家居NodeRed和HomeAssistant 即可关注。 02 全面改进的解析流程 前面发布过的Modbus解析流程在经过多个设备测试后发现存…

Python邮差:如何用代码精确投递商品快递费用的密信

目录 一、准备工作 二、编写API请求脚本 三、解析与处理快递费用数据 四、案例应用&#xff1a;模拟电商平台的快递费用计算 五、自动化邮件通知 六、总结 在电子商务的广阔天地里&#xff0c;精确计算并快速传递商品快递费用是一项至关重要的任务。作为Python邮差&#…

修改sql server 数据库的排序规则Chinese_PRC_CI_AS(字符集+排序)

文章目录 引言I 解决方案案例II 知识扩展排序规则SQL SERVER支持的所有排序规则引言 新增sql server 数据库实例的默认排序规则不支持中文存储,导致乱码 解决方案: 修改排序规则为Chinese_PRC_CI_AS 或者 Chinese_PRC_Stroke_CI_AS_WS或者Chinese_PRC_CI_AI_KS_WS 仅对新增…

七十页PPT展示智驾时代来临,国产汽车零部件厂商准备几何?

u 智能汽车车身架构主要可分为感知、决策控制、执行及通信四大板块&#xff0c;目前国产汽车零部件供应商在感知系统已取得较强的话语权&#xff0c;在决策控制系统、执行系统领域亦取得一定竞争力。 u 感知系统主要硬件包括激光雷达、毫米波雷达、摄像头等&#xff1b;其中&a…

Springboot 整合 Java DL4J 打造自然语言处理之智能写作助手

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/literature?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;…

moffee

https://github.com/BMPixel/moffee Moffee&#xff1a;一键将Markdown转换为专业PPT&#xff0c;支持多主题与实时预览 文章目录 1-安装1.1-环境1.2-编码 2-使用2.1-语法 moffee 演示让 Markdown 准备好演示为什么选择 moffee&#xff1f;展示用 Markdown 设置样式媒体布局 1-…

玩转「HF/魔搭/魔乐」平台

模型下载 Hugging Face 下载到 GitHub CodeSpace CodeSpace创建环境&#xff1a; # 安装transformers pip install transformers4.38 pip install sentencepiece0.1.99 pip install einops0.8.0 pip install protobuf5.27.2 pip install accelerate0.33.0下载internlm2_5-7b…

运维高可用架构设计

一、硬件 1、服务器 2、网络架构 二、软件 1、基础组件 组件名称 高可用方式 最少节点数 负载均衡(Tenginx) corsyncpacemaker互为主备 多组集群通过DNS轮循实现一个大集群 2DNS主从集群2RabbitMQ原生HA镜像集群3Zookeeper原生分布式集群3Kafka原生分布式集群3ES原生分布式集…

DICOM标准:MR图像模块属性详解——磁共振成像(MR)在DICOM中的应用

目录 引言 磁共振成像&#xff08;MR&#xff09; 一、MR图像模块 二、MR图像属性描述 1、图像类型 (Image Type) 2、抽样每个象素 (Sampling per Pixel) 3、光度插值 (Photometric Interpretation) 4、位分配 (Bits Allocated) 结论 引言 数字成像和通信在医学&#xff08…

SpringBoot在线教育系统:多语言支持

5系统详细实现 5.1 普通管理员管理 管理员可以对普通管理员账号信息进行添加修改删除操作。具体界面的展示如图5.1所示。 图5.1 普通管理员管理界面 5.2 课程管理员管理 管理员可以对课程管理员进行添加修改删除操作。具体界面如图5.2所示。 图5.2 课程管理员管理界面 5.3 …

Cursor和GitHub Copilot之间的竞争

大家好&#xff0c;今天我们要聊聊一个在开发者圈子里引起热议的话题&#xff1a;GitHub Copilot和Cursor之间的竞争&#xff0c;以及Copilot最近宣布的新功能&#xff0c;这可能会改变我们对编程辅助工具的看法。 GitHub Copilot将支持来自Anthropic、Google和OpenAI的模型&am…

Python酷库之旅-第三方库Pandas(181)

目录 一、用法精讲 836、pandas.api.types.is_file_like函数 836-1、语法 836-2、参数 836-3、功能 836-4、返回值 836-5、说明 836-6、用法 836-6-1、数据准备 836-6-2、代码示例 836-6-3、结果输出 837、pandas.api.types.is_list_like函数 837-1、语法 837-2、…

软件测试必会:cookie、session和token的区别~

今天就来说说session、cookie、token这三者之间的关系&#xff01;最近这仨玩意搞得头有点大&#x1f923; 01、为什么会有它们三个 我们都知道 HTTP 协议是无状态的&#xff0c;所谓的无状态就是客户端每次想要与服务端通信&#xff0c;都必须重新与服务端链接&#xff0c;意…

Vue3+vite 加载优化

公司项目&#xff0c;技术栈&#xff1a;vue3viteelementPLusecharts。首屏加载有点慢&#xff0c;针对这个做了一些优化措施&#xff0c;记录一下。之前写过关于vue2版本的优化&#xff0c;有兴趣的可以了解下 定位问题 f12打开控制台&#xff0c;然后Network看下那些包占比大…

Nvidia突袭AI江湖!悄悄发布新模型,完爆OpenAI和Anthropic?

你以为Nvidia只会造芯片&#xff1f;太天真了&#xff01;这家GPU巨头刚刚在AI语言模型领域上演了一出惊天逆袭&#xff0c;让OpenAI和Anthropic都措手不及。 没有轰轰烈烈的发布会&#xff0c;没有铺天盖地的宣传&#xff0c;Nvidia就这么静悄悄地在Hugging Face平台上扔出了一…

【Unity Shader】Special Effects(十)Change 变换(UI)

源码:[点我获取源码] 索引 Change 变换思路分析变换进度噪声纹理闪烁闪烁时机闪烁颜色闪烁动画Change 变换 变换的效果为图像间的切换带来动感过程,使用动画播放器: 思路分析 首先,从原始图像变换到目标图像是一个从0到1的过程,这个过程我们命名为变换进度(0为完全显…

jQuery选择器

目录 一、基本选择器 1. 标签选择器&#xff08;元素选择器&#xff09; 2. ID 选择器 3. 类选择器 4. 通配符选择器 二、层次选择器 1. 后代选择器 2. 子选择器 3. 相邻兄弟选择器 4. 一般兄弟选择器 三、属性选择器 1. 简单属性选择器 2. 属性值等于选择器 3.属…