2019-01-26 20:59:43 longgeqiaojie304 阅读数 97
  • 数据结构和算法视频教程

    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。

    87853 人正在学习 去看看 姜雪伟

数据结构概述

1、为什么要学习数据结构

(1)数据结构是所有计算机专业的同学必学的课程;

(2)数据结构研究的是数据如何在计算机中进行组织和存储的,使得我们可以高效的获取数据或者修改数据;

 

2、数据结构分类

(1)线性结构

       数组;栈;

 

       队列;链表;

 

       哈希表……

(2)树结构

       二叉树;二分搜索树;

 

       AVL;红黑树

      

       Treap;Splay;

 

       堆;Trie;

 

       线段树;K-D树;

 

       并查集;哈夫曼树……

 

(3)图结构

       邻接矩阵;邻接表;

我们需要根据不同的应用,灵活选择最合适的数据结构

 

3、计算机世界里,数据结构无处不在

(1)数据库场景

数据库底层是通过很多数据结构制作而成的,数据库主要目的就是用来存储数据的。

(2)操作系统场景

操作系统底层也是通过很多数据结构制作而成的。

系统栈:递归调用就需要借助系统栈空间。

堆:主要用于组建优先队列数据结构,通过比较优先队列优先级来进行多任务切换。

操作系统支持快速在多任务间切换

(3)文件压缩场景

简单的压缩算法可以使用哈夫曼树数据结构,但是下面文件格式并不是全部使用哈夫曼树数据结构。

(4)通讯录场景

通讯录产品:微软当时的一款使用链表数据结构来存储联系人,但是当联系人数量越来越大的时候,查询联系人是非常缓慢的。后来这个问题被微软一个实习生解决了,他使用了一种Trie-前缀树数据结构来解决的。不管你的通讯录数量有多大,查询联系人都是毫秒级别的。

(5)游戏场景

DFS:深度优先算法;

BFS:广度优先算法;

数据结构 + 算法 = 程序

4、常用数据结构学习

 

(1)面向面试数据结构

       数组;栈;队列;链表;二分搜索树;堆;

(2)面向竞赛数据结构

       线段树;Trie;并查集;

(3)世界性的计算机题库网站

       https://leetcode.com/

后面章节笔记主要内容:

  1. 递归;调试;简单的复杂度分析;
  2. 底层实现;创建自己的小型数据库;
  3. 数据结构的优化和比较;

 

如果感兴趣的童鞋,可以观看我下一篇博客:学习数据结构(和算法)到底有没有用?

 

 

 

2018-12-30 19:37:55 chengxu_kuangrexintu 阅读数 76
  • 数据结构和算法视频教程

    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。

    87853 人正在学习 去看看 姜雪伟

什么是数据结构

数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中元素之间的关系组成。

数据结构的分类

  1. 数据的存储结构
  2. 数据的逻辑结构

1.数据的存储结构

分类

①顺序存储结构
②链式存储结构

①顺序存储结构

顺序存储结构是把数据元素存放在地址连续的存储单元里,其数据间的逻辑关系和物理关系是一致的。数组就是顺序存储结构的典型代表。
在这里插入图片描述

②链式存储结构

在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).
在这里插入图片描述

两种方式的区别

  • 链表存储结构的内存地址不一定是连续的,但顺序存储结构的内存地址一定是连续的;
  • 链式存储适用于在较频繁地插入、删除、更新元素时,而顺序存储结构适用于频繁查询时使用。

2.数据的逻辑结构

分类

  1. 集合结构
  2. 线性结构
  3. 树形结构
  4. 图形结构

①集合结构

集合结构中的数据元素同属于一个集合,他们之间是并列关系,除此之外没有其他关系。
在这里插入图片描述

②线性结构

线性结构中的元素存在一对一的相互关系。
在这里插入图片描述

③树形结构

树形结构中的元素存在一对多的相互关系。
在这里插入图片描述

④图形结构

图形结构中的元素存在多对多的相互关系。
在这里插入图片描述

2019-09-27 14:54:34 zhanghuaichao 阅读数 96
  • 数据结构和算法视频教程

    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。

    87853 人正在学习 去看看 姜雪伟

 

最近在学习数据结构,有必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构

按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构

逻辑结构:是指数据对象中的数据元素之间的相互关系,主要分为以下四种结构

1.集合结构

集合结构中的数据元素处理同属于一个集合里,它们之间没有其他关系。各个数据元素是“平等”的,它们的共同属性是“同属于一个集合”。数据结构中的集合关系就类似于数学中的集合,满足集合的三个基本性质,确定性,互异性,无序性,而满足这个性质的应该只有C语言里的结构体满足这个条件,因为结构体里的数据无序,互异,确定。

 2.线性结构

线性结构中的数据元素之间存在一对一的关系,满足这个关系的有  线性表(数组,vector,链表),队列,栈,串

下面具体解释下原因:先看定义

线性表:零个或者是多个数据元素的有限序列。

下面对其定义进行下充分的解读,首先它是一个序列,也就是说元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且之后一个前驱和后继。然后线性表强调是有限的,当元素个数为零个时称为空表。

所以线性表的元素之间是满足一对一的关系的

栈:栈(stack)是限定仅在表尾进行插入和删除操作的线性表,是一种特殊的线性表,所以属于线性结构

队列:队列(queue)是只允许在一端进行插入操作,而在另外一端进行删除操作的线性表,是一种特殊的线性表,所以属于线性结构

串:串(string)是由零个或者多个字符组成的有限序列。

看定义我们就能清楚的看到,串是特殊的线性表,只是把定义中的数据元素换成了特定的字符元素,所以串也是属于线性结构

一般情况下,把栈,队列,串,分为一组叫受限线性表。

3.树形结构

树形结构中的数据元素之间存在一种一对多的层次关系,一般分为一般树和二叉树,满足这个关系的有 set,map

4.图形结构

图形结构的数据元素是多对多的关系,一般分为有向图和无向图,

最后可以画一个思维导图进行下总结

2019-11-30 23:28:05 weixin_42528266 阅读数 7
  • 数据结构和算法视频教程

    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。

    87853 人正在学习 去看看 姜雪伟
2.1 数据结构有什么用?

当你用着java里面的容器类很爽的时候,你有没有想过,怎么ArrayList就像一个无限扩充的数组,也好像链表之类 的。好用吗?好用,这就是数据结构的用处,只不过你在不知不觉中使用了。

现实世界的存储,我们使用的工具和建模。每种数据结构有自己的优点和缺点,想想如果Google的数据用的是数 组的存储,我们还能方便地查询到所需要的数据吗?而算法,在这么多的数据中如何做到最快的插入,查找,删 除,也是在追求更快。

我们java是面向对象的语言,就好似自动档轿车,C语言好似手动档吉普。数据结构呢?是变速箱的工作原理。你 完全可以不知道变速箱怎样工作,就把自动档的车子从 A点 开到 B点,而且未必就比懂得的人慢。写程序这件事, 和开车一样,经验可以起到很大作用,但如果你不知道底层是怎么工作的,就永远只能开车,既不会修车,也不能 造车。当然了,数据结构内容比较多,细细的学起来也是相对费功夫的,不可能达到一蹴而就。我们将常见的数据 结构:堆栈、队列、数组、链表和红黑树 这几种给大家介绍一下,作为数据结构的入门,了解一下它们的特点即可。

在这里插入图片描述

2.2 常见的数据结构

数据存储的常用结构有:栈、队列、数组、链表和红黑树。我们分别来了解一下:

  • 栈:stack,又称堆栈,它是运算受限的线性表,其限制是仅允许在标的一端进行插入和删除操作,不允许在其 他任何位置进行添加、查找、删除等操作。

简单的说:采用该结构的集合,对元素的存取有如下的特点

  • 先进后出(即,存进去的元素,要在后它后面的元素依次取出后,才能取出该元素)。例如,子弹压进弹 夹,先压进去的子弹在下面,后压进去的子弹在上面,当开枪时,先弹出上面的子弹,然后才能弹出下面的子弹。
  • 栈的入口、出口的都是栈的顶端位置。
    在这里插入图片描述

这里两个名词需要注意:

  • 压栈:就是存元素。即,把元素存储到栈的顶端位置,栈中已有元素依次向栈底方向移动一个位置。
  • 弹栈:就是取元素。即,把栈的顶端位置元素取出,栈中已有元素依次向栈顶方向移动一个位置。

队列

  • 队列:queue,简称队,它同堆栈一样,也是一种运算受限的线性表,其限制是仅允许在表的一端进行插入, 而在表的另一端进行删除。

简单的说,采用该结构的集合,对元素的存取有如下的特点:

  • 先进先出(即,存进去的元素,要在后它前面的元素依次取出后,才能取出该元素)。例如,小火车过山 洞,车头先进去,车尾后进去;车头先出来,车尾后出来。

  • 队列的入口、出口各占一侧。例如,下图中的左侧为入口,右侧为出口。

在这里插入图片描述

数组

  • 数组:Array,是有序的元素序列,数组是在内存中开辟一段连续的空间,并在此空间存放元素。就像是一排出 租屋,有100个房间,从001到100每个房间都有固定编号,通过编号就可以快速找到租房子的人。

简单的说,采用该结构的集合,对元素的存取有如下的特点:

  • 查找元素快:通过索引,可以快速访问指定位置的元素

在这里插入图片描述

  • 增删元素慢
    指定索引位置增加元素:需要创建一个新数组,将指定新元素存储在指定索引位置,再把原数组元素根 据索引,复制到新数组对应索引的位置。如下图
    在这里插入图片描述
  • 指定索引位置删除元素:需要创建一个新数组,把原数组元素根据索引,复制到新数组对应索引的位 置,原数组中指定索引位置元素不复制到新数组中。如下图

在这里插入图片描述

链表

  • 链表:linked list,由一系列结点node(链表中每一个元素称为结点)组成,结点可以在运行时i动态生成。每 个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。我们常说的 链表结构有单向链表与双向链表,那么这里给大家介绍的是单向链表。

在这里插入图片描述

简单的说,采用该结构的集合,对元素的存取有如下的特点:

  • 多个结点之间,通过地址进行连接。例如,多个人手拉手,每个人使用自己的右手拉住下个人的左手,依次 类推,这样多个人就连在一起了。
    在这里插入图片描述

  • 查找元素慢:想查找某个元素,需要通过连接的节点,依次向后查找指定元素

增删元素快:

  • 增加元素:只需要修改连接下个元素的地址即可。
    在这里插入图片描述

  • 删除元素:只需要修改连接下个元素的地址即可。
    在这里插入图片描述

红黑树

  • 二叉树:binary tree ,是每个结点不超过2的有序树(tree) 。

简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。

二叉树是每个节点最多有两个子树的树结构。顶上的叫根结点,两边被称作“左子树”和“右子树”。如图:
在这里插入图片描述
我们要说的是二叉树的一种比较有意思的叫做红黑树,红黑树本身就是一颗二叉查找树,将节点插入后,该树仍然 是一颗二叉查找树。也就意味着,树的键值仍然是有序的。

红黑树的约束:

  1. 节点可以是红色的或者黑色的
  2. 根节点是黑色的
  3. 叶子节点(特指空节点)是黑色的
  4. 每个红色节点的子节点都是黑色的
  5. 任何一个节点到其每一个叶子节点的所有路径上黑色节点数相同

红黑树的特点:
速度特别快,趋近平衡树,查找叶子元素最少和最多次数不多于二倍

2019-07-14 17:27:52 qq_38198467 阅读数 100
  • 数据结构和算法视频教程

    数据结构、算法视频培训课程,该教程主要是介绍在游戏开发中经常使用的数据结构,例如数组,链表,栈,队列,二叉树,递归等重要知识点讲解以及将它们里灵活的运用到算法里面。

    87853 人正在学习 去看看 姜雪伟

三要素:

数据的逻辑结构:

可以理解为我们看到的程序的样子,比如程序先后做了哪些操作,一个数组里面按照什么样的规律存放了哪些数据等。这是比较直观的。

 常用结构:

  • 集合:只是存在一个相同的空间内,没有其他关系
  • 线性结构:数据之间有一对一的关系,比如排队
  • 树形结构:数据之间是一对多的关系,比如家谱
  • 图状结构或网状结构:数据之间存在多对多的关系,比如老师和学生

===========================================================================

数据的存储结构(物理结构):

相对于逻辑结构来讲,程序的存储结构是对计算机而言的,也就是计算机是怎么将程序存储的,它使用了什么样的结构来存储我们的程序,这个是我们所无法直观看出来的。

存储结构也叫物理结构,这个和计算机语言是有关系的,它就是计算机语言对逻辑结构实现后的东西,比如java、c++、C语言,他们实现的存储结构是各不一样的。

一般主要的有:

顺序存储、表示数据在计算机磁盘上的存储顺序都是相邻的

链式存储、物理位置不一定是相邻的,但是元素之间是有对象具体的位置信息的,通过这个位置信息就可以确定元素的位置

索引存储、这个东西嘛,就是类似于目录,比如数据库加了索引后查找数据更加快捷了,就是这个道理

散列存储、通过关键字和一定的计算方法计算后得出来的元素的具体位置信息,想想数据的加密,是不是有散列密码?

================================================================================

数据的运算:

运算其实就是我们平时所接触到的+-*/(加减乘除),就是数据之间的代数运算或者更加复杂的计算方法

实际上数据的运算包括了运算的定义和实现

比如说,我现在要计算一个班上数学成绩的平均值,那么这个目的该怎么实现?把数学成绩加起来除以总人数是不是就是我们对应的定义,这个东西就是我们上面说到的逻辑结构,而我们定好这个计算框架之后就要交给计算机来运算了,但是它具体是怎么运算的其实我们不知道,这个实现的过程其实就是数据的物理结构。

 

数据结构

阅读数 104

数据结构的分类

阅读数 126

Javascript数据结构

阅读数 255

没有更多推荐了,返回首页