精华内容
下载资源
问答
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据...

    本文目录:

    数据结构分类

    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
    常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示:
    这里写图片描述
    每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。

    1、数组

    数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。

    int[] data = new int[100];data[0]  = 1;
    

    优点:
    1、按照索引查询元素速度快
    2、按照索引遍历数组方便

    缺点:
    1、数组的大小固定后就无法扩容了
    2、数组只能存储一种类型的数据
    3、添加,删除的操作慢,因为要移动其他的元素。

    适用场景:
    频繁查询,对存储空间要求不大,很少增加和删除的情况。

    2、栈

    栈是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出,或者说是后进先出,从栈顶放入元素的操作叫入栈,取出元素叫出栈。
    这里写图片描述
    栈的结构就像一个集装箱,越先放进去的东西越晚才能拿出来,所以,栈常应用于实现递归功能方面的场景,例如斐波那契数列。

    3、队列

    队列与栈一样,也是一种线性表,不同的是,队列可以在一端添加元素,在另一端取出元素,也就是:先进先出。从一端放入元素的操作称为入队,取出元素为出队,示例图如下:
    这里写图片描述
    使用场景:因为队列先进先出的特点,在多线程阻塞队列管理中非常适用。

    4、链表

    链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,每个元素包含两个结点,一个是存储元素的数据域 (内存空间),另一个是指向下一个结点地址的指针域。根据指针的指向,链表能形成不同的结构,例如单链表,双向链表,循环链表等。
    这里写图片描述
    链表的优点:
    链表是很常用的一种数据结构,不需要初始化容量,可以任意加减元素;
    添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可,所以添加,删除很快;

    缺点:
    因为含有大量的指针域,占用空间较大;
    查找元素需要遍历链表来查找,非常耗时。

    适用场景:
    数据量较小,需要频繁增加,删除操作的场景

    5、树

    是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

    • 每个节点有零个或多个子节点;
    • 没有父节点的节点称为根节点;
    • 每一个非根节点有且只有一个父节点;
    • 除了根节点外,每个子节点可以分为多个不相交的子树;

    在日常的应用中,我们讨论和用的更多的是树的其中一种结构,就是二叉树
    这里写图片描述
    二叉树是树的特殊一种,具有如下特点:

    1、每个结点最多有两颗子树,结点的度最大为2。
    2、左子树和右子树是有顺序的,次序不能颠倒。
    3、即使某结点只有一个子树,也要区分左右子树。

    二叉树是一种比较有用的折中方案,它添加,删除元素都很快,并且在查找方面也有很多的算法优化,所以,二叉树既有链表的好处,也有数组的好处,是两者的优化方案,在处理大批量的动态数据方面非常有用。

    扩展:
    二叉树有很多扩展的数据结构,包括平衡二叉树、红黑树、B+树等,这些数据结构二叉树的基础上衍生了很多的功能,在实际应用中广泛用到,例如mysql的数据库索引结构用的就是B+树,还有HashMap的底层源码中用到了红黑树。这些二叉树的功能强大,但算法上比较复杂,想学习的话还是需要花时间去深入的。

    6、散列表

    散列表,也叫哈希表,是根据关键码和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。

    记录的存储位置=f(key)

    这里的对应关系 f 成为散列函数,又称为哈希 (hash函数),而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

    哈希表在应用中也是比较常见的,就如Java中有些集合类就是借鉴了哈希原理构造的,例如HashMap,HashTable等,利用hash表的优势,对于集合的查找元素时非常方便的,然而,因为哈希表是基于数组衍生的数据结构,在添加删除元素方面是比较慢的,所以很多时候需要用到一种数组链表来做,也就是拉链法。拉链法是数组结合链表的一种结构,较早前的hashMap底层的存储就是采用这种结构,直到jdk1.8之后才换成了数组加红黑树的结构,其示例图如下:
    这里写图片描述
    从图中可以看出,左边很明显是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

    哈希表的应用场景很多,当然也有很多问题要考虑,比如哈希冲突的问题,如果处理的不好会浪费大量的时间,导致应用崩溃。

    7、堆

    堆是一种比较特殊的数据结构,可以被看做一棵树的数组对象,具有以下的性质:

    • 堆中某个节点的值总是不大于或不小于其父节点的值;

    • 堆总是一棵完全二叉树。

    将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

    堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。
    (ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2),满足前者的表达式的成为小顶堆,满足后者表达式的为大顶堆,这两者的结构图可以用完全二叉树排列出来,示例图如下:
    这里写图片描述
    因为堆有序的特点,一般用来做数组中的排序,称为堆排序。

    8、图

    图是由结点的有穷集合V和边的集合E组成。其中,为了与树形结构加以区别,在图结构中常常将结点称为顶点,边是顶点的有序偶对,若两个顶点之间存在一条边,就表示这两个顶点具有相邻关系。

    按照顶点指向的方向可分为无向图和有向图:
    这里写图片描述
    这里写图片描述
    图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构,这里不做展开,读者有兴趣可以自己学习深入。

    展开全文
  • 【数据结构与算法】常见数据结构及基本操作

    万次阅读 多人点赞 2019-06-16 21:42:44
    数据结构与算法常见概念2.数据逻辑结构2.1线性结构2.2树形结构2.3图形结构2.4集合结构3.排序算法冒泡排序简单选择排序直接插入排序希尔排序堆排序归并排序快速排序4.查找算法顺序表查找有序表查找线性索引查找二叉...


    总结《大话数据结构》和《C++Primer》,文后附《大话数据结构》和《C++Primer》第五版下载链接,本文相关代码均由C++编写。

    1.数据结构与算法常见概念:

    数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。
    数据元素:是组成数据的,有一定意义的基本单位,在计算机中通常作为整体处理,也被称为记录。
    数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
    数据结构的逻辑结构:数据对象中数据元素之间的相互关系,分为线性结构、树形结构、图形结构以及集合结构。
    数据结构的物理结构:数据的逻辑结构在计算机中的存储形式,分为顺序存储和链式存储(不连续存储)。

    算法:解决特定问题求解步骤的描述,在计算机中表现为指令的有限序列,并且每条指令表示一个或多个操作。
    算法五个基本特性:输入、输出、有穷性、确定性和可行性。
    算法时间复杂度O(n):常数阶、线性阶、平方阶、对数阶、立方阶、nlogn阶、指数阶。
    耗时排序:O(1)<O(logn)<O(n)<O(nlgn)<O(x2x^{2})<O(x3x^{3})<O(2n2^{n})<O(n!)<O(nnn^{n})

    2.数据结构:

    2.1线性结构:

    基本概念

    线性结构:数据元素之间是一对一的关系。
    在这里插入图片描述
    线性表:零个或多个数据元素的有限序列。
    区分数组长度与线性表的长度
            数组长度是指存放线性表的存储空间的长度,存储分配后这个值是不变的。
            线性表的长度是线性表中数据元素的个数,随着线性表的插入与删除,这个值是在变换的。
    在这里插入图片描述线性表的顺序存储:用一段连续的存储单元依次存储线性表的数据元素。(通常使用一维数组实现顺序存储结构)
    线性表的链式存储:除了存储本身的信息之外,还需存储一个指示后继的信息。
    顺序存储的插入步骤:
            a.线性表长度大于等于数组长度,抛出异常
            b.插入位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.从最后一个元素开始向前变量,将它们都向后移动一位
            d.将要插入的元素填入指定位置
            e.表长加一
    顺序存储的删除步骤:
            a.线性表是否为空
            b.删除位置不合适,抛出异常(判断插入位置与0和最大值的大小)
            c.取出删除元素
            d.从删除元素的位置遍历到最后一个元素位置,将它们前移一位
            e.表长减一
    链式存储的插入与删除在链表中介绍
    顺序存储和链式存储使用场景:如果频繁使用查找,很少进行插入和删除,易采用顺序存储。如果需要频繁插入和删除,易采用链式存储。

    数组

    数组及基本操作

    字符串

    字符串及基本操作

    队列

    队列及基本操作

    栈及基本操作

    链表

    链表及基本操作

    2.2树形结构

    基本概念

    树形结构:数据元素之间存在一对多的层次关系
    在这里插入图片描述
    :结点拥有的子树数
    叶结点/终端结点:度为0的结点
    树的度:树内各结点的度的最大值
    在这里插入图片描述
    结点间关系图
    在这里插入图片描述
    树的深度/高度:树中结点的最大层次
    在这里插入图片描述
    二叉树:是N(N>=0)个结点的有限集合,该集合或为空集(空二叉树),或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
    在这里插入图片描述
    满二叉树:所有分支结点都存在左子树和右子树,并且所有非叶子节点都在同一层上
    在这里插入图片描述
    完全二叉树:对一棵具有n个结点的二叉树按层序编号,如果编号i(1<= i <= n)的结点与同样深度的满二叉树中的编号i 的结点在二叉树的位置完全相同,则这棵二叉树称为完全二叉树
    在这里插入图片描述
    二叉树的特点

    1. 每个结点最多只有两颗子树
    2. 左右子树是有顺序的
    3. 即使某结点只有一颗子树,也要区分是右子树还是左子树

    二叉树的性质

    1. 在二叉树的第i层上至多有2i12^{i-1}个结点(i>=1)
    2. 深度为k的二叉树至多有2k2^{k}-1个结点(k>=1)
    3. 对任何一棵二叉树T,如果其终端结点数为n0n_{0},此二叉树至多有2k2^{k}-1个结点
    4. 具有n个结点的完全二叉树的深度为[log2log_{2}n]+1([x]表示不大于x的最大整数)
    5. n个结点的完全二叉树按层序编号(参考上图),对任意一个结点i有:
      a. 如果i=1,则i是二叉树的根,如果i>1,其双亲是[i/2]
      b. 如果2i>n,则结点i无左孩子
      c. 如果2i+1>n,则结点i无右孩子(否则其右孩子为2i+1)

    二叉树的递归遍历

    二叉树的遍历(递归)

    二叉树的非递归遍历

    未完待续……

    2.3图形结构

    图形结构:数据元素的多对多的关系
    在这里插入图片描述

    2.4集合结构

    集合结构:数据元素除了同属于一个集合外,它们之间没有其他关系。
    在这里插入图片描述

    3.资源链接

    《大话数据结构》+《C++Primer》PDF百度云盘链接
    提取码:6a7b

    展开全文
  • 数据结构算法常见面试考题

    万次阅读 多人点赞 2018-11-08 09:29:44
    数据结构上几种树集中的讨论一下: 1.AVLtree 定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)...

    (1) 红黑树的了解(平衡树,二叉搜索树),使用场景

    把数据结构上几种树集中的讨论一下:

    1.AVLtree

    定义:最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一,所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

    节点的平衡因子是它的左子树的高度减去它的右子树的高度(有时相反)。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的,并需要重新平衡这个树。平衡因子可以直接存储在每个节点中,或从可能存储在节点中的子树高度计算出来。
    一般我们所看见的都是排序平衡二叉树。

    AVLtree使用场景:AVL树适合用于插入删除次数比较少,但查找多的情况。插入删除导致很多的旋转,旋转是非常耗时的。AVL 在linux内核的vm area中使用。

    2.二叉搜索树

    二叉搜索树也是一种树,适用与一般二叉树的全部操作,但二叉搜索树能够实现数据的快速查找。

    二叉搜索树满足的条件:

    1.非空左子树的所有键值小于其根节点的键值
    2.非空右子树的所有键值大于其根节点的键值
    3.左右子树都是二叉搜索树

    二叉搜索树的应用场景:如果是没有退化称为链表的二叉树,查找效率就是lgn,效率不错,但是一旦退换称为链表了,要么使用平衡二叉树,或者之后的RB树,因为链表就是线性的查找效率。

    3.红黑树的定义

    红黑树是一种二叉查找树,但在每个结点上增加了一个存储位表示结点的颜色,可以是RED或者BLACK。通过对任何一条从根到叶子的路径上各个着色方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,因而是接近平衡的。

    当二叉查找树的高度较低时,这些操作执行的比较快,但是当树的高度较高时,这些操作的性能可能不比用链表好。红黑树(red-black tree)是一种平衡的二叉查找树,它能保证在最坏情况下,基本的动态操作集合运行时间为O(lgn)。

    红黑树必须要满足的五条性质:

    性质一:节点是红色或者是黑色; 在树里面的节点不是红色的就是黑色的,没有其他颜色,要不怎么叫红黑树呢,是吧。

    性质二:根节点是黑色; 根节点总是黑色的。它不能为红。

    性质三:每个叶节点(NIL或空节点)是黑色;

    性质四:每个红色节点的两个子节点都是黑色的(也就是说不存在两个连续的红色节点); 就是连续的两个节点不能是连续的红色,连续的两个节点的意思就是父节点与子节点不能是连续的红色。

    性质五:从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。从根节点到每一个NIL节点的路径中,都包含了相同数量的黑色节点。

    红黑树的应用场景:红黑树是一种不是非常严格的平衡二叉树,没有AVLtree那么严格的平衡要求,所以它的平均查找,增添删除效率都还不错。广泛用在C++的STL中。如map和set都是用红黑树实现的。

    4.B树定义

    B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树(查找路径不只两个),不属于二叉搜索树的范畴,因为它不止两路,存在多路。

    B树满足的条件:

    (1)树种的每个节点最多拥有m个子节点且m>=2,空树除外(注:m阶代表一个树节点最多有多少个查找路径,m阶=m路,当m=2则是2叉树,m=3则是3叉);
    (2)除根节点外每个节点的关键字数量大于等于ceil(m/2)-1个小于等于m-1个,非根节点关键字数必须>=2;(注:ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2)
    (3)所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子
    (4)如果一个非叶节点有N个子节点,则该节点的关键字数等于N-1;
    (5)所有节点关键字是按递增次序排列,并遵循左小右大原则;

    B树的应用场景:构造一个多阶的B类树,然后在尽量多的在结点上存储相关的信息,保证层数尽量的少,以便后面我们可以更快的找到信息,磁盘的I/O操作也少一些,而且B类树是平衡树,每个结点到叶子结点的高度都是相同,这也保证了每个查询是稳定的。

    5.B+树

    B+树是B树的一个升级版,B+树是B树的变种树,有n棵子树的节点中含有n个关键字,每个关键字不保存数据,只用来索引,数据都保存在叶子节点。是为文件系统而生的。

    相对于B树来说B+树更充分的利用了节点的空间,让查询速度更加稳定,其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定;我们先看看两者的区别

    (1)B+跟B树不同,B+树的非叶子节点不保存关键字记录的指针,这样使得B+树每个节点所能保存的关键字大大增加;
    (2)B+树叶子节点保存了父节点的所有关键字和关键字记录的指针,每个叶子节点的关键字从小到大链接;
    (3)B+树的根节点关键字数量和其子节点个数相等;
    (4)B+的非叶子节点只进行数据索引,不会存实际的关键字记录的指针,所有数据地址必须要到叶子节点才能获取到,所以每次数据查询的次数都一样;

    特点:
    在B树的基础上每个节点存储的关键字数更多,树的层级更少所以查询数据更快,所有指关键字指针都存在叶子节点,所以每次查找的次数都相同所以查询速度更稳定;

    应用场景: 用在磁盘文件组织 数据索引和数据库索引。

    6.Trie树(字典树)

    trie,又称前缀树,是一种有序树,用于保存关联数组,其中的键通常是字符串。与二叉查找树不同,键不是直接保存在节点中,而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。一般情况下,不是所有的节点都有对应的值,只有叶子节点和部分内部节点所对应的键才有相关的值。

    在图示中,键标注在节点中,值标注在节点之下。每一个完整的英文单词对应一个特定的整数。Trie 可以看作是一个确定有限状态自动机,尽管边上的符号一般是隐含在分支的顺序中的。
    键不需要被显式地保存在节点中。图示中标注出完整的单词,只是为了演示 trie 的原理。

    trie树的优点:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。缺点:Trie树是一种比较简单的数据结构.理解起来比较简单,正所谓简单的东西也得付出代价.故Trie树也有它的缺点,Trie树的内存消耗非常大.

    其基本性质可以归纳为:

    1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
    2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
    3. 每个节点的所有子节点包含的字符都不相同。

    典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。字典树与字典很相似,当你要查一个单词是不是在字典树中,首先看单词的第一个字母是不是在字典的第一层,如果不在,说明字典树里没有该单词,如果在就在该字母的孩子节点里找是不是有单词的第二个字母,没有说明没有该单词,有的话用同样的方法继续查找.字典树不仅可以用来储存字母,也可以储存数字等其它数据。

    (2) 红黑树在STL上的应用

    STL中set、multiset、map、multimap底层是红黑树实现的,而unordered_map、unordered_set 底层是哈希表实现的。

    multiset、multimap: 插入相同的key的时候,我们将后插入的key放在相等的key的右边,之后不管怎么进行插入或删除操作,后加入的key始终被认为比之前的大。

    (3) 了解并查集吗?(低频)

    什么是合并查找问题呢?

    顾名思义,就是既有合并又有查找操作的问题。举个例子,有一群人,他们之间有若干好友关系。如果两个人有直接或者间接好友关系,那么我们就说他们在同一个朋友圈中,这里解释下,如果Alice是Bob好友的好友,或者好友的好友的好友等等,即通过若干好友可以认识,那么我们说Alice和Bob是间接好友。随着时间的变化,这群人中有可能会有新的朋友关系,这时候我们会对当中某些人是否在同一朋友圈进行询问。这就是一个典型的合并-查找操作问题,既包含了合并操作,又包含了查找操作。

    并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将属于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。

    并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。

    并查集也是使用树形结构实现。不过,不是二叉树。每个元素对应一个节点,每个组对应一棵树。在并查集中,哪个节点是哪个节点的父亲以及树的形状等信息无需多加关注,整体组成一个树形结构才是重要的。类似森林

    (4) 贪心算法和动态规划的区别

    贪心算法:局部最优,划分的每个子问题都最优,得到全局最优,但是不能保证是全局最优解,所以对于贪心算法来说,解是从上到下的,一步一步最优,直到最后。

    动态规划:将问题分解成重复的子问题,每次都寻找左右子问题解中最优的解,一步步得到全局的最优解.重复的子问题可以通过记录的方式,避免多次计算。所以对于动态规划来说,解是从小到上,从底层所有可能性中找到最优解,再一步步向上。

    分治法:和动态规划类似,将大问题分解成小问题,但是这些小问题是独立的,没有重复的问题。独立问题取得解,再合并成大问题的解。

    例子:比如钱币分为1元3元4元,要拿6元钱,贪心的话,先拿4,再拿两个1,一共3张钱;实际最优却是两张3元就够了。

    (5) 判断一个链表是否有环,如何找到这个环的起点

    给定一个单链表,只给出头指针h:
    1、如何判断是否存在环?
    2、如何知道环的长度?
    3、如何找出环的连接点在哪里?
    4、带环链表的长度是多少?

    解法:
    1、对于问题1,使用追赶的方法,设定两个指针slow、fast,从头指针开始,每次分别前进1步、2步。如存在环,则两者相遇;如不存在环,fast遇到NULL退出。
    2、对于问题2,记录下问题1的碰撞点p,slow、fast从该点开始,再次碰撞所走过的操作数就是环的长度s。
    3、问题3:有定理:碰撞点p到连接点的距离=头指针到连接点的距离,因此,分别从碰撞点、头指针开始走,相遇的那个点就是连接点。(证明在后面附注)
    4、问题3中已经求出连接点距离头指针的长度,加上问题2中求出的环的长度,二者之和就是带环单链表的长度
    http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html

    (6) 实现一个strcpy函数(或者memcpy),如果内存可能重叠呢

    ——大家一般认为名不见经传strcpy函数实现不是很难,流行的strcpy函数写法是:

      1. char *my_strcpy(char *dst,const char *src)  
      2. {  
      3.     assert(dst != NULL);  
      4.     assert(src != NULL);  
      5.     char *ret = dst;  
      6.     while((* dst++ = * src++) != '\0')   
      7.         ;  
      8.     return ret;  
      9. }  
    

    如果注意到:
    1,检查指针有效性;
    2,返回目的指针des;
    3,源字符串的末尾 ‘\0’ 需要拷贝。

    内存重叠

    内存重叠:拷贝的目的地址在源地址范围内。所谓内存重叠就是拷贝的目的地址和源地址有重叠。
    在函数strcpy和函数memcpy都没有对内存重叠做处理的,使用这两个函数的时候只有程序员自己保证源地址和目标地址不重叠,或者使用memmove函数进行内存拷贝。
    memmove函数对内存重叠做了处理。
    strcpy的正确实现应为:

      1. char *my_strcpy(char *dst,const char *src)  
      2. {  
      3.     assert(dst != NULL);  
      4.     assert(src != NULL);  
      5.     char *ret = dst;  
      6.     memmove(dst,src,strlen(src)+1);  
      7.     return ret;  
      8. }  
    

    memmove函数实现时考虑到了内存重叠的情况,可以完成指定大小的内存拷贝

    (7) 快排存在的问题,如何优化

    快排的时间复杂度

    时间复杂度最快平均是O(nlogn),最慢的时候是O(n2);辅助空间也是O(logn);最开始学快排时最疑惑的就是这个东西不知道怎么得来的,一种是通过数学运算可以的出来,还有一种是通过递归树来理解就容易多了

    这张图片别人博客那里弄过来的,所谓时间复杂度最理想的就是取到中位数情况,那么递归树就是一个完全二叉树,那么树的深度也就是最低为Logn,这个时候每一次又需要n次比较,所以时间复杂度nlogn,当快排为顺序或者逆序时,这个数为一个斜二叉树,深度为n,同样每次需要n次比较,那那么最坏需要n2的时间

    优化:

    1.当整个序列有序时退出算法;
    2.当序列长度很小时(根据经验是大概小于 8),应该使用常数更小的算法,比如插入排序等;
    3.随机选取分割位置;
    4.当分割位置不理想时,考虑是否重新选取分割位置;
    5.分割成两个序列时,只对其中一个递归进去,另一个序列仍可以在这一函数内继续划分,可以显著减小栈的大小(尾递归):
    6.将单向扫描改成双向扫描,可以减少划分过程中的交换次数

    优化1:当待排序序列的长度分割到一定大小后,使用插入排序
    原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排

    优化2:在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割

    优化3:优化递归操作
    快排函数在函数尾部有两次递归操作,我们可以对其使用尾递归优化

    优点:如果待排序的序列划分极端不平衡,递归的深度将趋近于n,而栈的大小是很有限的,每次递归调用都会耗费一定的栈空间,函数的参数越多,每次递归耗费的空间也越多。优化后,可以缩减堆栈深度,由原来的O(n)缩减为O(logn),将会提高性能。

    (8) Top K问题(可以采取的方法有哪些,各自优点?)

    1.将输入内容(假设用数组存放)进行完全排序,从中选出排在前K的元素即为所求。有了这个思路,我们可以选择相应的排序算法进行处理,目前来看快速排序,堆排序和归并排序都能达到O(nlogn)的时间复杂度。

    2.对输入内容进行部分排序,即只对前K大的元素进行排序(这K个元素即为所求)。此时我们可以选择冒泡排序或选择排序进行处理,即每次冒泡(选择)都能找到所求的一个元素。这类策略的时间复杂度是O(Kn)。

    3.对输入内容不进行排序,显而易见,这种策略将会有更好的性能开销。我们此时可以选择两种策略进行处理:

    用一个桶来装前k个数,桶里面可以按照最小堆来维护
    a)利用最小堆维护一个大小为K的数组,目前该小根堆中的元素是排名前K的数,其中根是最小的数。此后,每次从原数组中取一个元素与根进行比较,如大于根的元素,则将根元素替换并进行堆调整(下沉),即保证小根堆中的元素仍然是排名前K的数,且根元素仍然最小;否则不予处理,取下一个数组元素继续该过程。该算法的时间复杂度是O(nlogK),一般来说企业中都采用该策略处理top-K问题,因为该算法不需要一次将原数组中的内容全部加载到内存中,而这正是海量数据处理必然会面临的一个关卡。

    b)利用快速排序的分划函数找到分划位置K,则其前面的内容即为所求。该算法是一种非常有效的处理方式,时间复杂度是O(n)(证明可以参考算法导论书籍)。对于能一次加载到内存中的数组,该策略非常优秀。

    (9) Bitmap的使用,存储和插入方法

    BitMap从字面的意思

    很多人认为是位图,其实准确的来说,翻译成基于位的映射。
    在所有具有性能优化的数据结构中,大家使用最多的就是hash表,是的,在具有定位查找上具有O(1)的常量时间,多么的简洁优美。但是数据量大了,内存就不够了。
    当然也可以使用类似外排序来解决问题的,由于要走IO所以时间上又不行。
    所谓的Bit-map就是用一个bit位来标记某个元素对应的Value, 而Key即是该元素。由于采用了Bit为单位来存储数据,因此在存储空间方面,可以大大节省。
    其实如果你知道计数排序的话(算法导论中有一节讲过),你就会发现这个和计数排序很像。

    bitmap应用

       1)可进行数据的快速查找,判重,删除,一般来说数据范围是int的10倍以下。
       2)去重数据而达到压缩数据
    

    还可以用于爬虫系统中url去重、解决全组合问题。

    BitMap应用:排序示例

    假设我们要对0-7内的5个元素(4,7,2,5,3)排序(这里假设这些元素没有重复)。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数,我们就只需要8个Bit(1Bytes),首先我们开辟1Byte的空间,将这些空间的所有Bit位都置为0(如下图:)

    然后遍历这5个元素,首先第一个元素是4,那么就把4对应的位置为1(可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况,这里默认为Big-ending。不过计算机一般是小端存储的,如intel。小端的话就是将倒数第5位置1),因为是从零开始的,所以要把第五位置为一(如下图):

    然后再处理第二个元素7,将第八位置为1,,接着再处理第三个元素,一直到最后处理完所有的元素,将相应的位置为1,这时候的内存的Bit位的状态如下:

    然后我们现在遍历一遍Bit区域,将该位是一的位的编号输出(2,3,4,5,7),这样就达到了排序的目的。

    bitmap排序复杂度分析

    Bitmap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。
    bitmap排序的时间复杂度不是O(N)的,而是取决于待排序数组中的最大值MAX,在实际应用上关系也不大,比如我开10个线程去读byte数组,那么复杂度为:O(Max/10)。也就是要是读取的,可以用多线程的方式去读取。时间复杂度方面也是O(Max/n),其中Max为byte[]数组的大小,n为线程大小。
    空间复杂度应该就是O(Max/8)bytes吧

    BitMap算法流程

    假设需要排序或者查找的最大数MAX=10000000(lz:这里MAX应该是最大的数而不是int数据的总数!),那么我们需要申请内存空间的大小为int a[1 + MAX/32]。
    其中:a[0]在内存中占32为可以对应十进制数0-31,依次类推:
    bitmap表为:
    a[0]--------->0-31
    a[1]--------->32-63
    a[2]--------->64-95
    a[3]--------->96-127

    我们要把一个整数N映射到Bit-Map中去,首先要确定把这个N Mapping到哪一个数组元素中去,即确定映射元素的index。我们用int类型的数组作为map的元素,这样我们就知道了一个元素能够表示的数字个数(这里是32)。于是N/32就可以知道我们需要映射的key了。所以余下来的那个N%32就是要映射到的位数。

    1.求十进制数对应在数组a中的下标:

    先由十进制数n转换为与32的余可转化为对应在数组a中的下标。
    如十进制数0-31,都应该对应在a[0]中,比如n=24,那么 n/32=0,则24对应在数组a中的下标为0。又比如n=60,那么n/32=1,则60对应在数组a中的下标为1,同理可以计算0-N在数组a中的下标。
    i = N>>K % 结果就是N/(2^K)
    Note: map的范围是[0, 原数组最大的数对应的2的整次方数-1]。

    2.求十进制数对应数组元素a[i]在0-31中的位m:

    十进制数0-31就对应0-31,而32-63则对应也是0-31,即给定一个数n可以通过模32求得对应0-31中的数。
    m = n & ((1 << K) - 1) %结果就是n%(2^K)

    3.利用移位0-31使得对应第m个bit位为1

    如a[i]的第m位置1:a[i] = a[i] | (1<<m)
    如:将当前4对应的bit位置1的话,只需要1左移4位与B[0] | 即可。

    Note:

    1 p+(i/8)|(0×01<<(i%8))这样也可以?
    2 同理将int型变量a的第k位清0,即a=a&~(1<<k)

    BitMap算法评价

    优点:
    1. 运算效率高,不进行比较和移位;
    2. 占用内存少,比如最大的数MAX=10000000;只需占用内存为MAX/8=1250000Byte=1.25M。
    3.
    缺点:
    1. 所有的数据不能重复,即不可对重复的数据进行排序。(少量重复数据查找还是可以的,用2-bitmap)。
    2. 当数据类似(1,1000,10万)只有3个数据的时候,用bitmap时间复杂度和空间复杂度相当大,只有当数据比较密集时才有优势。
    http://blog.csdn.net/pipisorry/article/details/62443757

    (10) 字典树的理解以及在统计上的应用

    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

    就是在海量数据中找出某一个数,比如2亿QQ号中查找出某一个特定的QQ号。。

    (11) N个骰子出现和为m的概率

    典型的可以用动态规划的思想来完成

    1.现在变量有:骰子个数,点数和。当有k个骰子,点数和为n时,出现次数记为f(k,n)。那与k-1个骰子阶段之间的关系是怎样的?

    2.当我有k-1个骰子时,再增加一个骰子,这个骰子的点数只可能为1、2、3、4、5或6。那k个骰子得到点数和为n的情况有:
    (k-1,n-1):第k个骰子投了点数1
    (k-1,n-2):第k个骰子投了点数2
    (k-1,n-3):第k个骰子投了点数3

    (k-1,n-6):第k个骰子投了点数6
    在k-1个骰子的基础上,再增加一个骰子出现点数和为n的结果只有这6种情况!
    所以:f(k,n)=f(k-1,n-1)+f(k-1,n-2)+f(k-1,n-3)+f(k-1,n-4)+f(k-1,n-5)+f(k-1,n-6)

    3.有1个骰子,f(1,1)=f(1,2)=f(1,3)=f(1,4)=f(1,5)=f(1,6)=1。
    用递归就可以解决这个问题:

    用迭代来完成

    (19) 海量数据问题(可参考左神的书)

    目前关于海量数据想到的解决办法:
    1.bitmap
    2.桶排序,外部排序,将需要排序的放到外存上,不用全部放到内存上

    (20) 一致性哈希

    说明

    http://www.zsythink.net/archives/1182

    优点

    1.当后端是缓存服务器时,经常使用一致性哈希算法来进行负载均衡。使用一致性哈希的好处在于,增减集群的缓存服务器时,只有少量的缓存会失效,回源量较小。
    2.尽量减少数据丢失问题,减少移动数据的风险

    展开全文
  • 数据结构-JS实现集合

    千次阅读 2021-03-08 17:20:16
    文章目录一、什么是集合?1.1 集合常见方法 一、什么是集合? 1.1 集合常见方法

    一、什么是集合?

    在这里插入图片描述

    1.1 集合的常见方法

    在这里插入图片描述

    1.2 常见方法的实现

    function Set() {
      // 属性
      this.items = {}
    
      // 方法
      // 1.add 向集合添加一个新的项
      Set.prototype.add = function (value) {
        // 判断当前集合中是否已经包含了该元素
        if (this.has(value)) return false
    
        // 将元素添加到集合中
        this.items[value] = value
        return true
      }
    
      // 2.has 判断值是否在集合中
      Set.prototype.has = function (value) {
        // 判断某个对象是否含有指定的属性
        return this.items.hasOwnProperty(value)
      }
    
      // 3.remove(remove) 删除指定的元素
      Set.prototype.remove = function (value) {
        // 1.判断是否包含要删除的元素
        if(!this.has(value)) return false
    
        // 2.将元素从属性中删除
        delete this.items[value]
        return true
      }
    
      // 4.clear 清空
      Set.prototype.clear = function (){
        this.items = {}
      }
    
      // 5.size方法 获取集合中的元素个数
      Set.prototype.size = function (){
        return Object.keys(this.items).length 
      }
      
      // 6.values 获取集合中所有的值
      Set.prototype.values = function (){
        return Object.keys(this.items)
      }
    }
    

    测试代码:

    // 测试
    let set = new Set()
    
    // 1.测试add
    console.log(set.add('a'));
    console.log(set.add('a'));
    console.log(set.add('b'));
    console.log(set.add('c'));
    
    // 2.测试 values
    console.log(set.values());
    
    // 3.测试 remove
    console.log(set.remove('c'));
    console.log(set.remove('c'));
    
    // 4.测试size
    console.log(set.size());
    
    // 5.测试 has
    console.log(set.has('a'));
    
    // 6.测试 clear
    console.log(set.values())
    console.log(set.clear());
    console.log(set.values())
    

    测试结果:

    在这里插入图片描述

    二、集合间的操作

    2.1 集合间的常见操作

    在这里插入图片描述

    2.2 并集 返回一个包含两个集合所有元素的集合

    // 1.并集
    Set.prototype.union = function (otherSet) {
      // this:集合对象A
      // otherSet:集合对象B
      // 1.创建一个新的集合
      let unionSet = new Set()
    
      // 2.将A集合中所有元素添加到新集合中
      let values = this.values()
      for (let i = 0; i < values.length; i++) {
        unionSet.add(values[i])
      }
    
      // 3.取出B集合中的元素,判断是否需要加入到新集合
      values = otherSet.values()
      for (let i = 0; i < values.length; i++) {
        unionSet.add(values[i])
      }
      return unionSet
    }
    

    测试代码:

    // 1.创建两个集合,并且添加元素
    let setA = new Set()
    setA.add('a')
    setA.add('b')
    setA.add('c')
    
    let setB = new Set()
    setB.add('aa')
    setB.add('bb')
    setB.add('c')
    // 1.求两个集合的并集
    console.log('求并集:=》', setA.union(setB));
    

    测试结果:
    在这里插入图片描述

    2.3 交集 集合A中的元素同时存在于集合B中

    // 2.交集
    Set.prototype.intersection = function (otherSet) {
      // this:集合A
      // otherSet:集合B
      // 1.先创建一个新的集合
      let intersectionSet = new Set()
    
      // 2.从A中取出一个个元素,判断是否同时存在于集合B,是则存放入新集合
      let values = this.values()
      for (let i = 0; i < values.length; i++) {
        let item = values[i]
        if (otherSet.has(item)) {
          intersectionSet.add(item)
        }
      }
      return intersectionSet
    }
    

    测试代码:

    // 1.创建两个集合,并且添加元素
    let setA = new Set()
    setA.add('a')
    setA.add('b')
    setA.add('c')
    
    let setB = new Set()
    setB.add('aa')
    setB.add('bb')
    setB.add('c')
    // 2.求交集
    console.log('求交集:=》',setA.intersection(setB));
    

    测试结果:
    在这里插入图片描述

    2.4 差集 存在于A中,不存在于B中

    Set.prototype.difference = function (otherSet) {
      // this:集合A
      // otherSet:集合B
      // 1.创建一个新的集合
      let differenceSet = new Set()
    
      // 2.取出A中的一个个元素,判断是否存在于B中,不存在,则添加到新集合中
      let values = this.values()
      for (let i = 0; i < values.length; i++) {
        let item = values[i]
        if (!otherSet.has(item)) {
          differenceSet.add(item)
        }
      }
      return differenceSet
    }
    

    测试代码:

    // 1.创建两个集合,并且添加元素
    let setA = new Set()
    setA.add('a')
    setA.add('b')
    setA.add('c')
    
    let setB = new Set()
    setB.add('aa')
    setB.add('bb')
    setB.add('c')
    
    // 3.求差集
    console.log('求差集:=》', setA.difference(setB));
    

    测试结果:
    在这里插入图片描述

    3.2 子集 A中的每一个元素都存在于B

    // 4.子集
    Set.prototype.subset = function (otherSet) {
      // 遍历集合A中的所有元素,如果都存在于B中,则返回true,
      // 只要有不存在于B中的,则放回false
      let values = this.values()
      for (let i = 0; i < values.length; i++) {
        let item = values[i]
        if (!otherSet.has(item)) {
          return false
        }
        return true
      }
    }
    

    测试代码:

    // 1.创建两个集合,并且添加元素
    let setA = new Set()
    setA.add('a')
    setA.add('b')
    setA.add('c')
    
    let setB = new Set()
    setB.add('aa')
    setB.add('bb')
    setB.add('c')
    
    let setC = new Set()
    setC.add('a')
    setC.add('b')
    setC.add('c')
    setC.add('d')
    
    // 4.子集
    console.log('求子集:=》', setA.subset(setB));  // A是不是B的子集
    console.log('求子集:=》', setA.subset(setC));  // A是不是C的子集
    

    测试结果:
    在这里插入图片描述

    展开全文
  • List集合的概述及特点:  元素有序,并且每一个元素都存在一个索引.元素可以重复。 List集合特有的功能:  void add(int index,E element): 在指定索引处添加元素  E remove(int index):移除指定索引处的元素 ...
  • 最近在学习数据结构必要对自己这两天的学习做一个总结,今天就来总结下,数据结构的逻辑结构 按照分类标准的不同,我们把数据结构分为逻辑机构和存储结构,今天主要讲解逻辑结构 逻辑结构:是指数据对象中的...
  • 常见数据结构与算法整理总结(上)

    万次阅读 多人点赞 2018-08-06 18:23:14
    数据结构是以某种形式将数据...为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,需要的...
  • 图解!24张图彻底弄懂九大常见数据结构

    万次阅读 多人点赞 2020-05-24 22:23:36
    数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的...
  • java数据结构了解与集合学习

    千次阅读 2020-08-04 20:36:23
    学习集合前需要了解数据结构基础。 数据结构 数据结构是指逻辑意义上的数据组织方式及其相应的处理方式。 逻辑意义:数据结构的抽象表达非常丰富,而实际物理存储方式相对单一。比如:二叉树结构,在物理上可能也...
  • 集合中常用数据结构总结

    千次阅读 2019-04-28 20:17:49
    常见的和集合相关的数据结构有: 数组, 栈, 队列,链表,哈希表, 二叉树 下面简单总结一下个数据结构特点: 1. 数组 ArrayList(public class ArrayList extends AbstractList implements List, RandomAccess, ...
  • python中的set是指一系列无序元素的集合,其中的元素都是相异的,常见的操作包括集合的并集,交集和补集等操作。 1、set的创建 格式 set_name = {value1, value2, ...} 创建空的集合 set_name = set() 注意:...
  • 常见数据结构

    万次阅读 2018-02-05 15:01:50
    2.数组中的所有元素必须是相同类型或类型的衍生(同质数据结构) 3.元素可以通过下标直接访问   二 LinkedList(链表) 链表:线性表的一种,最基本,最简单,也是最常用的数据结构 特征: 1.元素之间的关系是一对一的...
  • 常见数据结构与算法整理总结

    千次阅读 多人点赞 2018-01-10 14:03:30
    数据结构是以某种形式将数据...为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,需要的可以
  • 集合的底层数据结构原理决定了集合的一些特性,在这里对这几种数据结构特点简答介绍下,这几种数据结构也是最常见数据结构
  • 本节对常见数据结构做一个预览,我们的目的是快速了解他们,对于它们涉及到的复杂的数据结构和算法,在这里并不全部展开,留在后期详述。 1.数组 数组是我们要学习的第一个线性结构(Linear structure),所谓线性...
  • 常见数据结构简介

    千次阅读 2019-03-25 00:26:57
    数据结构是指一种或者多种关系的数据元素的集合或者该数据集合之间的关系组成。 常见数据结构有数组,队列,堆,栈,树,图,散列表,链表等。 一,线性结构 1)数组 数组是可以在内存中存储多个元素的结构,其在...
  • 底层数据结构是数组,查询快,增删慢 线程不安全,效率高 Vector 底层数据结构是数组,查询快,增删慢 线程安全,效率低 LinkedList 底层数据结构是链表,查询慢,增删快 线程不安全,效率高 ...
  • 数组、链表等常用数据结构集合浅解(java)

    万次阅读 多人点赞 2017-04-21 20:23:38
    数组、链表等常用数据结构集合浅解(java)脑子转了一圈,巴拉巴拉的写了一大堆,本来今天步行者打骑士的比赛在上半场已经花了,步行者领先20多分,然而詹姆斯一个大大大号三双强行把比分拉回来还赢了比赛,留下36...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • 数据是基础,算法是灵魂 本文出自门心叼龙的博客,属于原创类容,转载请注明出处。... 源码下载地址:... 初级篇:Java数据结构与算法初级篇之数组、集合和散列表 中级篇:Java数据结...
  • 在ES6里已经引入了集合数据结构概念——Set类。 分类:常见空集,并集,交集,差集。 应用场景:1)数据去重;2)用于存储一些独一无二的数据。 js实现一个集合 集合的特性类似于JavaScript数据类型里的...
  • Swift中的集合数据结构

    千次阅读 2015-09-15 08:27:54
    假设你一个需要处理许多数据的应用。你会把收据放在哪儿?...在那种情况下,你将会需要一种基本的集合数据结构。幸运的是,这篇教程就是关于那个主题的。下面是这篇教程的构成: 你将会复习什么是数据
  • 常见数据结构 单链表结构和顺序存储结构的区别 线性链表 数组和链表的区别 判断疫个链表是否环,如何找到这个环 单链表和双链表的区别 头指针和头结点的区别 简述KMP算法 栈和队列的区别 栈和队列的相同之处和...
  • 常见数据结构及其特征

    千次阅读 2017-03-23 15:39:21
    常见数据结构有stack、heap、list、linkedlist、doubly-linked-list、queue、array(vector)等
  • python面试题——python常见数据结构

    千次阅读 2018-10-13 10:31:20
    python面试题——python常见数据结构 文章开始把我喜欢的这句话送个大家:这个世界上还有什么比自己写的代码运行在一亿人的电脑上更酷的事情吗,如果那就是让这个数字再扩大十倍 Python中常见的数据结构可以统称...
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据...
  • 常见数据结构与python实现

    千次阅读 2020-04-21 12:16:05
    python重要的数据结构list 可以实现线性表,队列,栈等。 1. 线性表 顺序表 size = 10 array = [0 for i in range(size)] 链表 class ListNode: def __init__(self,x): self.val = x self.next = None node = ...
  • 数据结构:是指相互之间存在一种或多种特定关系的数据元素的集合用计算机存储、组织数据的方式。数据结构分别为逻辑结构、(存储)物理结构和数据的运算三个部分。 为什么要学数据结构? 首先,因为数据结构作为...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 251,267
精华内容 100,506
关键字:

常见的数据结构有集合

数据结构 订阅