数据结构与算法_大彤小忆的博客-程序员宝宝_结构与算法

技术标签: 算法  数据结构  

1. 数据结构

  数据结构(Data Structure)是计算机存储、组织数据的方式,是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

  数据结构主要研究非数值计算问题程序中的操作对象以及它们之间的关系,不是研究复杂的算法。

  数据结构中的基本概念

  • 数据: 程序的操作对象,用于描述客观事物。数据是能输入计算机且能被计算机处理的各种符号的集合,是信息的载体,是对客观事物符号化的表示,能够被计算机识别、存储和加工。数据是一个抽象的概念,将其进行分类后得到程序设计语言中的类型,如int、float、char等等。
  • 数据元素: 组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素由若干个数据项组成。
  • 数据项: 构成数据元素的不可分割的最小单位。
  • 数据对象: 性质相同的数据元素的集合(比如:数组、链表),是数据的一个子集。

  数据元素不是孤立存在的,它们之间存在着某种关系,数据元素相互之间的关系称为结构(Structure)。数据结构是指互相之间存在一种或多种特定关系的数据元素的集合;或者说,数据结构是带结构的数据元素的集合。

  一个数据结构的例子如下所示。

//声明一个结构体类型
struct _MyTeacher  //一种数据类型
{
    
	char name[32];
	char title[32];
	int age;
	char addr[128];
};

int main()
{
    
	struct _MyTeacher t1;  //数据元素
	struct _MyTeacher tArray[30];  //数据对象
	memset(&t1, 0, sizeof(t1));
	
	strcpy(t1.name, "name");  //数据项
	strcpy(t1.addr,"addr");  //数据项
	strcpy(t1.title, "addr");  //数据项
	t1.age = 1;
}

  数据结构包括以下三个方面的内容:
  数据元素之间的逻辑关系,称为逻辑结构。逻辑结构描述数据元素之间的逻辑关系,与数据的存储无关,独立于计算机,是从具体问题抽象出来的数学模型。
  数据元素及其关系在计算机内存中的表示(又称为映像),称为数据的物理结构或数据的存储结构。物理结构(存储结构)指数据元素及其关系在计算机存储器中的结构(存储方式),是数据结构在计算机中的表示。
  数据的运算和实现,即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

在这里插入图片描述
  逻辑结构与存储结构的关系

  1. 存储结构是逻辑关系的映像与元素本身的映像;
  2. 逻辑结构是数据结构的抽象,存储结构是数据结构的实现;
  3. 两者综合起来就建立了数据元素之间的结构关系。

  什么是数据结构?
  结构: 实体+关系
  数据结构: 按照逻辑关系组织起来的一批数据,按一定的存储方法把它存储在计算机中,在这些数据上定义了一个运算的集合。

2. 算法

  算法是对特定问题求解方法和步骤的一种描述,在计算机中表现为指令的有限序列,算法是独立存在的一种解决问题的方法和思想。

  算法是解决问题的一种方法或一个过程,考虑如何将输入转换成输出,一个问题可以有多种算法。对算法而言,语言并不重要,重要的是思想。

  算法的特性:

  • 输入: 算法具有0或多个输入;
  • 输出: 算法至少有1个或多个输出;
  • 有穷性: 算法在有限的步骤之后会自动结束而不会无限循环,并且每一个步骤都在有穷时间内完成。
  • 确定性: 算法中的每一步都有确定的含义,不会出现二义性,在任何条件下,只有唯一的一条执行路径,即相对于相同的输入只能得到相同的输出;
  • 可行性: 算法的每一步都是可行的,算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

  算法设计的要求:正确性、可读性、健壮性、高效性。

  算法效率的分析:可以从时间效率和空间效率两方面进行分析。时间效率指的是算法所耗费的时间;空间效率指的是算法执行过程中所耗费的存储空间,但有时时间效率和空间效率是矛盾的。
  算法时间效率的度量: 算法时间效率可以依据该算法编制的程序在计算机上执行所消耗的时间来度量。有以下三种方法:
    1. 事后统计法:主要通过设计好的测试程序和数据,利用计算机的计时器对不同算法编制的程序的运行时间进行比较,从而确定算法效率的高低。
     缺点: 1. 为了获得不同算法的运行时间必须编写相应程序;
         2. 运行时间严重依赖硬件以及运行时的环境因素;
         3. 算法的测试数据的选取相当困难。
     总结: 事后统计法虽然直观,但是实施困难且缺陷多。

    2. 事前分析估算:在计算机程序编写前,依据统计方法对算法所消耗资源进行估算。
     影响算法效率的主要因素: 1. 算法采用的效率和方法;
                  2. 问题的输入规模;
                  3. 编译器所产生的代码;
                  4. 计算机执行速度。

    3. 大O表示法:算法的时间复杂度通常用大O符号表述,定义为T[n] = O(f(n))。
     总结: 1. 只关注最高次项;
         2. 时间复杂度是指最坏时间复杂度;
         3. 只有常数项记作1。

  算法的空间复杂度并不是计算所有算法所占空间,而是使用辅助空间的大小。

3. 数据结构与算法的区别与联系

  数据结构与算法的区别与联系

  1. 数据结构只是静态的描述了元素之间的关系,高效的程序需要在数据结构的基础上设计和选择算法;
  2. 算法是为了解决实际问题而设计的;数据结构是算法需要处理的问题载体;
  3. 数据结构通过算法实现操作,算法根据数据结构设计程序;
  4. 程序=数据结构+算法,数据结构与算法相辅相成。
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/HUAI_BI_TONG/article/details/116211663

智能推荐

string字符串基本操作,去掉最后一个指定字符,灵活运用_小可乐-我一直在的博客-程序员宝宝_string去掉最后一个字符

本文章是本人在写项目时遇到的,对于大神来说不算什么,不喜勿喷,有好的方法可以留言,万分感谢通过lastIndexOf找到最后一个逗号的位置,然后通过substring去掉最后一个逗号定义一个需要去掉逗号的strString str = “123,233,323”;//定一个字符串1、通过lastIndexOf查找最后一个逗号返回 String 对象中子字符串最后出现的位置。strObj....

基于UML和ASP.NET实现三层B/S结构系统开发_reandy的博客-程序员宝宝

基于UML和ASP.NET实现三层B/S结构系统开发 2007-03-30 17:32 摘 要 进行良好的系统分析和设计是软件项目开发的关键,构架设计的合理与否往往决定了项目的成败。本文结合一个项目的开发,阐述了基于UML的系统建模过程和基于ASP.NET实现面向对象的三层结构应用系统的方法。 关键词 ASP.NET; 三层结构; UML建模; 系统开发架构设计是软件开发的基础,并往往决定一个项目

(2021总结篇)面向对象软件设计模式--(十六)行为型模式---遍历聚合对象中的元素--迭代器模式_zhangxiaoxiao9527的博客-程序员宝宝

迭代器模式迭代器模式的意图,解决的问题,什么时候使用1.迭代器模式1.1 文法1.2 句子1.3 语法树2.解释器模式中的角色3.解释器模式优缺点、使用场景优点:缺点:适用场景:迭代器模式的意图,解决的问题,什么时候使用在软件开发中,会遇到有些问题多次重复出现,而且有一定的相似性和规律性。如果将它们归纳成一种简单的语言,那么这些问题实例将是该语言的一些句子,这样就可以用“编译原理”中的解释器模式来实现了。虽然使用解释器模式的实例不是很多,但对于满足以上特点,且对运行效率要求不是很高的应用实例,如果用解

微信小程序 回到顶部 功能实现_奶派三叔的博客-程序员宝宝

一、前端代码<view class="top" bindtap="top"><image src="/static/icon/top.png" class="top_image"></image></view>在前端d

OpenVINO(1)-模型下载_多云的夏天的博客-程序员宝宝

1.模型名称查询2.下载模型3.把下载好的模型库复制到自己的工程中1.模型名称查询到文件夹下查询:C:\Program Files (x86)\Intel\openvino_2021.2.185\deployment_tools\open_model_zoo\models\intel2.下载模型cmd 到C:\Program Files (x86)\Intel\openvino_2021.2.185\deployment_tools\open_model_zoo\tools\downloa..

随便推点

Eddy'sAC难题_Staydesting的博客-程序员宝宝

Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来,然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较,他想使第一组中的最小ac数大于第二组中的最大ac数,但是这样的情况会有很多,聪明的你知道这样的情况有多少种吗?特别说明:为了问题的简化,我们这里假设摘录下的人数...

sqli-labs靶场5-6关(双查询注入)_chaosec的博客-程序员宝宝

知识点双查询注入的知识点原理:双注入查询需要联合着MYSQL的BUG报错来进行报错注入BUG:当在一个聚合函数,比如count函数后面如果使用分组语句就会把查询的一部分一错误形式显示出来;双查询在命令行中直观显示出来select count(*),concat((select user()),(floor(rand() * 2))) as a from information_schema.tables group by a;rand()函数 //随机函数floor(a)

Hololens第三人称视角Spectator View!_Eshine_Lee的博客-程序员宝宝_hololens第三方视角

首先分享一段TED Talk,这个是全球顶级的演讲,一般演讲跟IT男都没啥关系,比较内敛对吧,或者就没啥这方面细胞,乔布斯的演讲还不错,每次新品发布都挑逗观众G点,可惜人家不是IT男。能在TED Talk演讲,唯一的要求就是,你要够牛逼,要多牛逼?放到全世界你都是够牛逼就差不多了,然后再锻炼一下演讲技巧多排练几次就好。这个视频是微软的同事在介绍Hololens带来的梦想中的人与人之间的交互体验。

UVA - 11478 Halum(差分约束系统)_暗金色的博客-程序员宝宝

题目大意:有一种操作(u,c),表示所有以u为终点的边的权值减去c,所有以u为起点的边权值加上c 最后要求所有的边的权值非负且尽量大解题思路:最小且最大,二分,枚举边的最小权值,然后看是否符合 对于给出的所有有向线段(u,v,val) 所有对u和v的操作才会影响到这条边,对其他点的操作并不会影响到,所以可以将边分开出来讨论 假设对u的操作为d[u],对v的操作为d[v],那么这条边的权值就变

linux隐藏属性只读,Linux 文件隐藏属性 chattr, lsattr_weixin_39871378的博客-程序员宝宝

chattr:配置文件隐藏属性(注意:chattr命令只在Ext2/Ext3的文件系统上生效)语法:chattr [+-=][ASacdistu] 文件或目录名称参数:+ :添加某一个特殊参数,其他原本存在参数不动。- :移除某一个特殊参数,其他原本存在参数不动。= :配置后面接的参数A :当使用了A这个属性时,若你有存取此文件(或目录)时,他的存取时间atime 将 ...

图像处理和计算机视觉中的经典论文_Zmj115的博客-程序员宝宝

图像处理和计算机视觉中的经典论文[email protected]://blog.csdn.net/zouxy09    转自:http://www.cnblogs.com/moondark/archive/2012/04/20/2459594.html   感谢水木上同领域的同学分享,有了他的整理,让我很方便的获得了CV方面相关的经典论文,我也顺便整理一下,把p