程序员经验分享-hwhale

数据结构与算法——第一章绪论

2023-11-17

绪论

博主目前是一位大二学生，鉴于数据结构与算法是一门考试课，故记录以便学习

数据结构的研究对象

数据、数据元素、数据项
数据对象也是整张表
直观理解

  • 数据是信息的载体，是描述客观事物的数、 字符、以及所有能输入到计算机中，能被计算机程序识别和处理的符号的集合
  • 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素又称为元素、结点、记录
  • 数据项是数据结构中讨论的最小单位
  • 组合项：例如生日
  • 原子项：不可再分割的数据项如年、月、日
  • 数据对象：性质相同的数据元素的集合
  • 数据结构是数据元素之间抽象的相互关系，并不涉及数据元素的具体内容

数据结构的表示：

通常可以用一个二元组<D，R>来表示。或写成DS=<D，R>。
D是数据集合（数据对象），R是D中数据元素之间所存在的关系的有限集合。
数据结构（技术）就是根据各种不同的数据集合和数据元素之间的关系，研究如何表示、存储和操作（查找、插入、删除、修改、排序）这些数据的技术。

DS的第一个重要部分——逻辑结构

数据的逻辑结构—人为定义的，用户可以看到
数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；可以看作是从具体问题抽象出来的数据模型； 数据的逻辑结构与数据元素的相对（存储）位置无关。
分类：

  • 集合
  • 线性结构
  • 非线性结构
    • 树
    • 图

线性结构
关系r 是一种线性关系，或称为“前后关系”，有时也称为“大小关系”。关系 r 是有向的，且满足全序性和单索性等约束条件
e.g. linearity=(K,R)
K={1,2,3,4,5,6,7,8,9,10}
R={<5,1>,<1,3>,< 3,8>,<8,2>,<2,7>,<7,4>,<4,6>,<6,9>,<9,10>}
对应的图形：
⑤→①→③→⑧→②→⑦→④→⑥→⑨→⑩
<>表示有序（）表示无序

DS第二个重要部分——数据的存储结构-计算机如何存储（结点及结点关系）

  • 数据的存储结构是逻辑结构用计算机语言的实现；
  • 数据的存储结构依赖于计算机语言；
  • 计算机处理问题时是一条一条的，不能像人一样整体处理，根据存储结构找到下一条数据

基本存储映射方法：顺序（索引、散列）、非顺序（链接）

顺序存储表示：逻辑相邻则物理相邻
结点间的逻辑后继关系用存储单元的自然顺序关系来表达
在这里插入图片描述

链接存储表示：逻辑相邻未必物理相邻
利用指针，在结点的存储结构中附加指针字段称为链接法。
两个结点的逻辑后继关系用指针来表达
在这里插入图片描述

索引存储表示：为数据建立索引表
顺序存储法的一种推广，也使用整数编码来访问数据结点位置
在这里插入图片描述

  • 散列存储表示：根据数据的关键码用散列函数计算出该数据的存储地址(目前不太理解）
    索引方法的一种延伸和扩展
    利用一种称为散列函数(hash functions)的机制来进行索引值的计算，然后通过索引表求出结点的指针地址。散列函数是将字符串 s（ 或关键码）映射到非负整数 z 的一类函数 h: S -> Z ，对任意的 s∈ S，散列函数 h(s)=z，z∈ Z
    在这里插入图片描述
    这一部分的深入理解不要太急，先了解基础即可。

数据结构的发展概况

略

抽象数据型

abstract data types，ADT

抽象数据型的定义

抽象数据型是一个数学模型和在该模型上定义的操作集合的总称。

数据类型、数据结构和抽象数据型

一个变量的数据类型是该变量值的类型
抽象数据型是一个数学模型以及在该模型上定义的操作集合的总称
数据结构是抽象数据型中数学模型的表示

数据类型：一组性质相同的值的集合，以及定义于这个值集合上的一组操作的总称。
C语言中的数据类型
char int float double void *
字符型 整型 浮点型 双精度型 无值 地址

数据类型由基本数据类型或构造数据类型组成
构造数据类型由不同成分类型构成。
基本数据类型可以看作是计算机中已实现的数据结构。
数据类型就是数据结构，不过是从编程者的角度来使用。（不太理解）

多层次抽象技术

建议自底向上。
如文章->行->字

抽象数据型的优点

1.降低软件设计的复杂性
2.提高程序可读性和可维护性
3.降低程序复杂度
4.有利于基于软件构件的程序开发和程序重用（不太懂）

算法及其复杂度

算法是为解决某一特定问题而采取的具体有限的操作步骤。

算法与程序

算法是有穷性 ： 算法应在执行有穷步后结束。
程序可能持续运行，直到系统退出，例如操作系统wait函数。
算法是面向问题的。
程序是算法的具体语言实现。

算法的特性

  • 有穷性
  • 有n个输入（n可以=0）与输出（n>0）
  • 确定性：算法的每条指令是清晰、无歧义的。
  • 可行性

算法设计与算法分析是计算机科学的核心问题

在这里插入图片描述

  • 这里建议一一慢慢了解

算法的描述方法

  • 自然语言，易于理解但冗长有二义性。避免写成自然段

在这里插入图片描述

  • 流程图。流程直观，但缺少严密性，灵活性

在这里插入图片描述

  • 流程图的具体规范有时间再讨论
  • 程序设计语言。计算机可以直接执行，但可读性差，需要专业语言知识
    在这里插入图片描述
  • 伪代码（真正推荐使用）
    表达能力、抽象能力强，易于理解。
    课程老师推荐使用自然语言加C++
    在这里插入图片描述

算法的复杂度及其表示

计算算法效率的方法

  • 事后分析

  • 事前分析
    2.1 时间复杂度Time Complexity
    2.2空间复杂度Space Complexity

  • 如何表达一个算法的复杂性
    算法的执行时间，是基本（操作）语句重复执行的次数，它是问题规模的一个函数。我们把这个函数的渐近阶称为该算法的时间复杂度。
    问题规模：输入量的多少
    算法分析----大O符号
    定义： 若存在两个正的常数c和n0，对于任意n≥n0，都有T(n)≤c×f(n)，则称T(n)=O(f(n))
    在这里插入图片描述
    在这里插入图片描述
    很多算法使用的数据结构是静态的存储结构，即存储空间在算法执行过程中并不发生变化
    使用动态数据结构算法的存储空间是变化的，在算法运行过程中有时会有数量级的增大或缩小。对于这种情况，空间开销的分析和估计是十分必要的

  • 怎样计算一个算法的复杂性

时间复杂度分析的基本方法

在这里插入图片描述
算法分析：各种语句遵循的规则
(1)赋值语句或读/写语句: 运行时间通常取O(1)
(2)语句序列: 运行时间由加法规则确定
(3)分支语句：运行时间由条件测试（通常为O(1) ）加上分支中运行时间
最长的语句的运行时间
(4)循环语句: 运行时间是对输入数据重复执行n次循环体所耗时间的总和
每次重复所耗时间包括两部分：一是循环体本身的运行时间；二是计算循环参数、测试循环终止条件和跳回循环头所耗时间。后一部分通常为O(1)。 通常，将常数因子忽略不计，可以认为上述时间是循环重复次数n和m的乘积，其中m是n次执行循环体当中时间消耗最多的那一次的运行时间(乘法规则)当遇到多重循环时，要由内层循环向外层逐层分析。因此，当分析外层循环的运行时间是，内层循环的运行时间应该是已知的。此时，可以把内层循环看成是外层循环的循环体的一部分。
(5)函数调用语句: （不太懂，较难，会在第八章详细讲）
①若程序中只有非递归调用，则从没有函数调用的被调函数开始，计算所有这种函数的运行时间。然后考虑有函数调用的任意一个函数P，在P调用的全部函数的运行时间都计算完之后，即可开始计算P的运行时间。
②若程序中有递归调用，则令每个递归函数对应于一个未知的时间开销函数T(n)，其中n是该函数参数的大小，之后列出关于T的递归方程并求解之。
在这里插入图片描述
在这里插入图片描述
拓展
在这里插入图片描述

最坏、最好和平均情况分析

在进行算法增长率估计时，有些算法，即使问题规模相同，若输入数据不同，其时间复杂度也不同，由于算法实际执行的操作往往依赖于分支条件的走向，而输入数据的取值又影响这些分支走向，因此很多算法都无
法得出独立于输入数据的渐进估计

  • 针对这一情况，提出了最差情况估计、平均情况估计、最佳 情况估计等三种方法
    平均：
    随机情况下，数组的元素是无序的，既非升序也非降序
    计算平均情况的复杂度应该考虑算法的所有输入情况，确定针对每种输入情况算法所需的操作数目
    简单情况：每种输入出现的概率相同
    复杂情况：每种输入的出现概率并非相同，
    需要了解算法的实际输入在所有可能的输入集合中的分布状
    况
    对于时间开销，一般不注意算法的“最好估计” 。特别是处理应急事件，计算机系统必须在规定的响应时间内做完紧急事件处理。这时，最坏估计是唯一的选择
    对于多数算法而言，最坏情况和平均情况估计两者，它们的时间开销的公式虽然不同，但是往往只是常数因子大小的区别，或者常数项的大小区别。因此不会影响渐进分析的增长率函数估计

结论：一般而言计算最差情况即可

逐步求精的程序设计方法

如何求解问题

问题抽象成数学模型，
写成算法，
转化成计算机能执行的指令，
精细化，细致化，形式化。

算法的逐步求精

很是困难啊，日后精进吧

习题

  • 还不会

在这里插入图片描述

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

笔记

算法

数据结构

c

数据结构与算法——第一章绪论 的相关文章

  • 类型转换 sockaddr 结构

    我正在尝试学习网络编程 并在这个过程中学习C 我对结构感到困惑sockaddr这是一个通用地址 并且sockaddr in 我的书里是这么说的 因此 我们可以填写 sockaddr in 的字段 然后强制转换 a 指向 它指向 指向 soc

  • 将数据集导出到 EXCEL

    我使用以下代码将数据库表中的字段导出到 Excel 中 我想要做的是能够编写一条 SQL 语句从多个表中检索字段并将其导出到 Excel 中 这段代码只允许我导出一张表 另外 如何显示保存提示对话框 示例代码将不胜感激 非常感谢 prote

  • WPF MVVM将DataTable绑定到DataGrid不显示数据

    我有一个简单的控件 其中包含一个 DataGrid 其中 ItemsSource 绑定到 DataTable 当我填充 DataTable 时 我可以看到 DataGrid 中添加了行 但没有显示任何数据 我没有为此 DataGrid 使用

  • 如何以编程方式确定 C 中 int 数据的最大和最小限制？

    我正在尝试 K R 的练习 2 1 练习内容如下 编写一个程序来确定范围char short int and long变量 两者signed and unsigned 通过从标准标题打印适当的值并通过直接计算 如果计算它们会更困难 确定各种

  • C# - 如何将 IntPtr 缓冲区数据保存到文件（最快的方法）？

    我使用此代码将非托管代码中的 IntPtr 缓冲区中的字节保存到文件中 这是一个简单的回调函数 private void callback IntPtr buffer int length byte bytes new byte lengt

  • WIX 自动生成 GUID *？

    假设我生成产品 ID 为 的 WIX XML 文件 另外 对于每个组件 GUID 我都使用

  • 使用 C 创建立体声正弦波

    我正在尝试用 C 创建立体声正弦 WAV 并且可能有不同的 可能是空白的 左声道和右声道 使用此函数为每个通道生成一个音调 int16 t create tone float frequency float amplitude float

  • c#Registry to XML无效字符问题

    我在尝试从注册表创建 XML 文件时遇到问题 在我的笔记本电脑 W7 64b 上它工作正常 生成了 xml 文件 但在另一台计算机 Xp 32b 上抛出异常 System ArgumentException 十六进制值 0x00 是无效字符

  • popen2()在c中如何工作？

    我尝试使用管道 叉子和 dup 在我的程序中执行 md5sume 命令 我发现总和代码运行成功 但我无法理解某些代码行 这是我的代码 int infp outfp char buf 128 if popen2 md5sum infp out

  • C++ 克隆惯用语中协变返回类型的用处？

    通常的克隆习惯使用协变返回类型 struct Base virtual Base clone struct Derived public Base Derived clone 我读过一些内容 大意是协变返回类型是 C 后来添加的 较旧的编译

  • 发生错误。", ExceptionMessage: "提供的 'HttpContent' 实例无效

    尝试将文件添加到 http 休息调用时出现此错误 responseJson 消息 发生错误 ExceptionMessage 提供了无效的 HttpContent 实例 它确实 正在使用 多部分 参数名称 内容 异常类型 System Ar

  • 如何使用 Caliburn.Micro MVVM 将焦点设置到控件

    我有一个表单 我想在发生某些用户操作时将焦点设置到文本框 我知道 MVVM 的处理方式是绑定到 VM 属性 但是 TextBox 没有允许这种情况发生的属性 从虚拟机设置焦点的最佳方法是什么 我创建了一个 IResult 实现 可以很好地实

  • 允许 .NET WebApi 忽略 DOCTYPE 声明

    我正在尝试通过 WebApi 方法将 XML 反序列化为对象 我有以下课程 XmlRoot IsNullable false public class MyObject XmlElement Name public string Name

  • 如何使用包含的转换的排名来比较两个标准转换序列

    include

  • 无论表单上的焦点控件如何，如何捕获 Keys.F1？

    我使用了 KeyDown 事件和一些简单的代码 例如if e KeyCode Keys F1 捕获在表单上按下 F1 但如果表单上有一些文本框 或者表单上有一些带有 Dock Fill 的电子表格 则上面的代码将毫无用处并且不执行任何操作

  • 修改公共属性的访问修饰符是否是重大更改？

    如果我将公共属性的 setter 的访问修饰符从私有更改为公共 是否会导致引用它的其他程序集发生任何重大更改 UPDATE 这个问题是我 2012 年 1 月博客的主题 https ericlippert com 2012 01 09 ev

  • 更新插入 MongoDB 时如何防止出现“_t”字段？

    我有一个应用程序 它使用 MongoDB 的 C 驱动程序将 Upsert 插入 MongoDB 数据库 当我打电话给Update函数 我无法指定我要更新的类型 然后 t字段插入元素的类型 这是我用来更新插入的代码 collection U

  • 如何并排显示 4 个三角形图案

    我无法让 4 个不同的三角形图案并排出现 这是一个控制台应用程序 这正是我试图通过使用嵌套 for 循环来实现的目标

  • 当另一个进程使用 std::fstream 写入文件时从文件读取[重复]

    这个问题在这里已经有答案了 我需要从文件中逐行读取 它是由 std getline 完成的 另一个进程的问题是一直向其附加数据 然后我需要读取新行 例如 文件一开始包含10行 我的程序读取了10行 那么我的程序应该等待 过了一会儿 另一个进

  • C++20 范围太多 |运营商？

    我在这段代码中使用 g 10 2 有谁知道为什么我最后收到编译器错误std views reverse on results3 include

随机推荐

  • 边缘计算操作系统安装及测试实验报告

    边缘计算操作系统安装及测试 一 实验目的 二 实验环境 三 实验原理 1 系统组成部分 2 总体数据流程 四 实验步骤及结果 1 安装 Docker 和 Docker Compose 2 下载 EdgeX compose 文件 3 运行Ed

  • qt中clicked(bool checked)和toggled(bool checked)的区别

    先来看qt文档的解释 上面看出 共同点是 当点击按钮时 状态信号都会被发送 不同点 clicked this signal is not emitted if you call setDown setChecked or toggle to

  • 5年测试面试要20K，面试三个问题把我打发走了···

    都说金三银四 金九银十跳槽涨薪季 我是着急忙慌的准备简历 5年软件测试经验 可独立测试大型产品项目 熟悉项目测试流程 薪资要求 5年测试经验起码能要个20K吧 我加班肝了一页半简历 投出去一周 面试电话倒是不少 自信满满去面试 现场被问了这

  • Nmap源码分析（服务与版本扫描）

    Nmap源码分析 服务与版本扫描 2012年8月23日 在进行端口扫描后 Nmap可以进一步探测出运行在端口上的服务类型及应用程序的版本 目前Nmap可以识别几千种服务程序的签名 Signature 覆盖了180多种应用协议 比如 端口扫描

  • java写后端接口中mapper的一些操作

    文章目录 Mybatis Mapper的动态SQL语句问题 一 if 二 choose when otherwise 三 where 四 trim 元素来定制 where 元素的功能 五 set 动态地在行首插入 SET 关键字 六 for

  • PTA 7-4 统计学生平均成绩与及格人数 (15 分)

    本题要求编写程序 计算学生们的平均成绩 并统计及格 成绩不低于60分 的人数 题目保证输入与输出均在整型范围内 输入格式 输入在第一行中给出非负整数N 即学生人数 第二行给出N个非负整数 即这N位学生的成绩 其间以空格分隔 输出格式 按照以

  • C语言函数大全-- y 开头的函数

    y 开头的函数 1 yperror 1 1 函数说明 1 2 演示示例 2 yp match 2 1 函数说明 2 2 演示示例 3 y0 零阶第二类贝塞尔函数 3 1 函数说明 3 2 演示示例 3 3 运行结果 4 y1 一阶第二类贝塞

  • 在Vue中使用flex布局 echarts多图标不能自适应缩放问题

    前言 最近有个项目需要用到echarts绘制多个图表 需求是要支持大屏展示 还有需要支持不同比例的缩放和任意手动缩放 因此 深入学习了echarts和flex布局 虽然遇到很多问题 但都一一解决了收获良多 故此写下遇到的问题与坑 与之共勉

  • go 进阶 多路复用支持: 二. Accept/Read/Write

    目录 一 通过httpServer服务端引用Accept 二 Listener Accept 等待连接 三 Conn Read读数据 Conn Write写数据 四 gopark 阻塞 五 netpoll 唤醒等待队列中挂起的协程 什么时候

  • C#桌面应用程序打包

    使用微软的技术开发windows桌面应用程序是很快捷方便的 开发完之后肯定要打包安装才能发布 以前有做过但过长时间没有打包一下子还真有些遗忘 今天专门又重温了一些 干脆写下来算是加深些印象 以后需要时也好有个参考 感觉有很多技术上手都没有太

  • std::bind可以绑定成员变量

    include

  • java student类_java定义一个Student类，包含内容如下

    展开全部 public class Student 成员变量 学号 姓名 性别 班干部否 数学 语文 外语 成62616964757a686964616fe58685e5aeb931333337613166员方法 输入 总分 平均分 编程实

  • MeterSphere实践指南汇总，搬砖党

    闲来无事 整理了MeterSphere实践指南 我司用了MeterSphere一段时间 感觉挺好用 百度网盘下载链接 链接 https pan baidu com s 1s8sAuz31lgnvTRTLkWZuiQ pwd 98bg 提取码

  • 我的算法笔记（1）——冒泡排序

    我的算法笔记 1 冒泡排序 排序是指将一个无序序列按某个规则进行有序排列 而冒泡排序是排序算法中最基础的一种 现给出一个序列a 其中元素的个数为n 要求将他们按从小到大的顺序排序 冒泡排序的本质在于交换 即每次通过交换的方式把当前剩余元素的

  • BP神经网络阈值

    在基于神经网络的数据融合文章里 有改进权值和阈值 但是没有说清阈值到底是什么 神经网络是模仿大脑的神经元 当外界刺激达到一定的阈值时 神经元才会受到刺激 影响下一个神经元 简单来说 超过阈值 就会引起某一变化 不超过阈值 无论是多少 都不产

  • 【数据库实验】sql总结

    首先说明 以下大部分针对的是标准sql 目录 结构 关键词 关于模式 创建模式 删除模式 关于表 创建表 修改表 删除表 关于索引 建立索引 修改索引 删除索引 关于查询 几个点 指定列 全部列 经过计算的值 列的别名 方便查看 以及聚集函

  • 深度学习：将新闻报道按照不同话题性质进行分类

    深度学习的广泛运用之一就是对文本按照其内容进行分类 例如对新闻报道根据其性质进行划分是常见的应用领域 在本节 我们要把路透社自1986年以来的新闻数据按照46个不同话题进行划分 网络经过训练后 它能够分析一篇新闻稿 然后按照其报道内容 将其

  • Unity学习记录——模型与动画

    Unity学习记录 模型与动画 前言 本文是中山大学软件工程学院2020级3d游戏编程与设计的作业7 编程题 智能巡逻兵 1 学习参考 除去老师在课堂上讲的内容 本次作业代码与操作主要参考了 傅老師 Unity教學 DarkSouls複刻經

  • 使用QT绘制极坐标图表

    使用QT绘制极坐标图表 在数据可视化领域 极坐标图表是非常常见的一种图表类型 QT作为一个高效 易用的GUI框架 也提供了绘制极坐标图表的功能 下面我们就来看一下如何使用QT绘制极坐标图表 首先 我们需要创建一个QT项目 选择 QT Wid

  • 数据结构与算法——第一章绪论

    数据结构与算法 绪论 数据结构的研究对象 数据结构的表示 DS的第一个重要部分 逻辑结构 DS第二个重要部分 数据的存储结构 计算机如何存储 结点及结点关系 数据结构的发展概况 抽象数据型 抽象数据型的定义 数据类型 数据结构和抽象数据型

热门标签