精华内容
下载资源
问答
  • 常见的数据结构

    2018-06-25 10:24:35
    今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)OC语言的基本数据类型有:整型int,浮点型float,字符型char等等 那么,究竟什么是...

    常见的数据结构

    上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~
     
    首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)O
    C语言的基本数据类型有:整型int,浮点型float,字符型char等等
     
    那么,究竟什么是数据结构呢?
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
    大部分数据结构的实现都需要借助C语言中的指针和结构体类型
     
    下面,进入今天的重点啦O(∩_∩)O几种常见的数据结构
    (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的有:数组、栈、队列和线性表
    (2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆
    (3)图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系
     
    下面分别对这几种数据结构做一个简单介绍:
    1、线性数据结构:典型的有:数组、栈、队列和线性表
    (1)数组和链表
    a、数组:存放着一组相同类型的数据,需要预先指定数组的长度,有一维数组、二维数组、多维数组等
    b、链表:链表是C语言中一种应用广泛的结构,它采用动态分配内存的形式实现,用一组任意的存储单元存放数据元素链表的,一般为每个元素增设指针域,用来指向后继元素
    c、数组和链表的区别:
    从逻辑结构来看:数组必须事先定义固定的长度,不能适应数据动态地增减的情况;链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项(数组中插入、删除数据项时,需要移动其它数据项)
    从内存存储来看:(静态)数组从栈中分配空间(用NEW创建的在堆中), 对于程序员方便快速,但是自由度小;链表从堆中分配空间, 自由度大但是申请管理比较麻烦
    从访问方式来看:数组在内存中是连续存储的,因此,可以利用下标索引进行随机访问;链表是链式存储结构,在访问元素的时候只能通过线性的方式由前到后顺序访问,所以访问效率比数组要低
     
    (2)栈、队列和线性表:可采用顺序存储和链式存储的方法进行存储
    顺序存储:借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系
    链式存储:借助表示数据元素存储地址的指针表示元素之间的逻辑关系
    a、栈:只允许在序列末端进行操作,栈的操作只能在栈顶进行,一般栈又被称为后进先出或先进后出的线性结构
       顺序栈:采用顺序存储结构的栈称为顺序栈,即需要用一片地址连续的空间来存储栈的元素,顺序栈的类型定义如下:
      
       链栈:采用链式存储结构的栈称为链栈:
        
     
    b、队列:只允许在序列两端进行操作,一般队列也被称为先进先出的线性结构
       循环队列:采用顺序存储结构的队列,需要按队列可能的最大长度分配存储空空,其类型定义如下:
      
      链队列:采用链式存储结构的队列称为链队列,一般需要设置头尾指针只是链表的头尾结点:
      
     
    c、线性表:允许在序列任意位置进行操作,线性表的操作位置不受限制,线性表的操作十分灵活,常用操作包括在任意位置插入和删除,以及查询和修改任意位置的元素
      顺序表:采用顺序存储结构表示的线性表称为顺序表,用一组地址连续的存储单元一次存放线性表的数据元素,即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系,为了避免移动元素,一般在顺序表的接口定义中只考虑在表尾插入和删除元素,如此实现的顺序表也可称为栈表:
     
     线性表:一般包括单链表、双向链表、循环链表和双向循环链表
     单链表:
      
     双向链表:
       
     线性表两种存储结构的比较:
     顺序表:
     优点:在顺序表中,逻辑中相邻的两个元素在物理位置上也相邻,查找比较方便,存取任一元素的时间复杂度都为O(1)
     缺点:不适合在任意位置插入、删除元素,因为需要移动元素,平均时间复杂度为O(n)
     链表:
     优点:在链接的任意位置插入或删除元素只需修改相应指针,不需要移动元素;按需动态分配,不需要按最大需求预先分配一块连续空空
     缺点:查找不方便,查找某一元素需要从头指针出发沿指针域查找,因此平均时间复杂度为O(n)
     
    2、树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆
    (1)二叉树:二叉树是一种递归数据结构,是含有n(n>=0)个结点的有限集合,二叉树具有以下特点:
    二叉树可以是空树;二叉树的每个结点都恰好有两棵子树,其中一个或两个可能为空;二叉树中每个结点的左、右子树的位置不能颠倒,若改变两者的位置,就成为另一棵二叉树
     
    (2)完全二叉树:从根起,自上而下,自左而右,给满二叉树的每个结点从1到n连续编号,如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,则称为完全二叉树
    a、采用顺序存储结构:用一维数组存储完全二叉树,结点的编号对于与结点的下标(如根为1,则根的左孩子为2*i=2*1=2,右孩子为2*i+1=2*1+1=2)
       
    b、采用链式存储结构:
    二叉链表:
     
    三叉链表:它的结点比二叉链表多一个指针域parent,用于执行结点的双亲,便于查找双亲结点
     
    两种存储结构比较:对于完全二叉树,采用顺序存储结构既能节省空间,又可利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系,但采用顺序存储结构存储一般二叉树容易造成空间浪费,链式结构可以克服这个缺点
     
    (3)二叉查找树:二叉查找树又称二叉排序树,或者是一课空二叉树,或者是具有如下特征的二叉树:
    a、若它的左子树不空,则左子树上所有结点的值均小于根结点的值
    b、若它的右子树不空,则右子树上所有结点的值均大于根结点的值
    c、它的左、右子树也分别是二叉查找树
     
    (4)平衡二叉树:平衡二叉查找树简称平衡二叉树,平衡二叉树或者是棵空树,或者是具有下列性质的二叉查找树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差的绝对值不超过1
     
    平衡二叉树的失衡及调整主要可归纳为下列四种情况:LL型、RR型、LR型、RL型
     
    (5)树:树是含有n(n>=0)个结点的有限集合,在任意一棵非空树种:
    a、有且仅有一个特定的称为根的结点
    b、当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树,并且T1,T2,...,Tm称为根的子树
     
    (6)堆:堆是具有以下特性的完全二叉树,其所有非叶子结点均不大于(或不小于)其左右孩子结点。若堆中所有非叶子结点均不大于其左右孩子结点,则称为小顶堆(小根堆),若堆中所有非叶子结点均不小于其左右孩子结点,则称为大顶堆(大根堆)
     

     
    (7)并查集:并查集是指由一组不相交子集所构成的集合,记作:S={S1,S2,S3,...,Sn}
    (8)B树
     
    3、图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系,可分为有向图和无向图
    展开全文
  • Redis的常用数据结构类型:string,list,set,sortedSet,hash一.sting的类型string类型是redis最常见的数据结构类型,存储的值为字符串。1.1String相关命令set key value :设置一个key,值为value,类型为String...

    Redis的数据结构类型,指的是redis的值的value类型;

    Redis的常用数据结构类型:string,list,set,sortedSet,hash

    一.sting的类型

    string类型是redis最常见的数据结构类型,存储的值为字符串。

    1.1String相关命令

    set key value :设置一个key,值为value,类型为String类型;如果这个key已经存在,则更新这个key的值。

    返回值

    1表示成功

    0表示失败

    setnx key vale:如果这个key不存在,则设置一个key,值为value;如果key存在,则不做更新。

    返回值

    1表示成功

    0表示失败

    get key:获取对应的value值;如果key不存在,则返回nil。

    incr key:将key中存储的数字值增一,然后返回。如果这个key不存在,那么key的值会先被初始化为0,然后再执行INCR操作。如果这个key对应的value值,不能表示数字,则会返回一个错误。

    incrby key increment:将key增加指定步长。

    decr key:将key中储存的数字值减一,然后返回。如果这个key不存在,那么key的值会先被初始化为0,然后再执行INCR操作。如果这个key对应的value值,不能表示数字,则会返回一个错误。

    decrby key decrement:将key减少对应的步长值。

    append key value:如果key已经存在,则将value追加到这个key原先的value值的末尾。如果这个key不存在,则执行set操作。

    Redis的key是单线程模式,这意味着一瞬间只有一个线程能够持有这个key,所以,可以使用redis解决部分涉及线程安全的业务。

    二.List类型

    1.特点

    (1)基于Linked List实现

    (2)元素是字符串类型

    (3)列表头尾增删快,中间增删慢,增删元素是常态

    (4)元素可以实现重现

    (5)最多包含2^32-1元素

    2.List类型相关命令

    lpush key value [value ...]:将一个或多个value插入到列表key的表头(即从左边插入);如果有多个value值,那么各个value值按从左到右的顺序依次插入表头;如果key不存在,一个空列表会被创建并执行LPUSH操作,当key存在但不是列表类型时,返回一个错误。

    rpush key value [value...]:尾部添加(从右向左),操作同上。

    llen key :返回key对应list长度,key不存在返回0,如果key对应类型不是list返回错误。

    lindex key index:index元素在list列表的下角标,从0开始;lindex是从左到右取元素。

    lrange key start stop:获取指定区间的所有元素;下角标从0开始,0表示第一个元素,1表示第二个,以此类推;-1表示最后一个元素,-2表示倒数第二个元素,以此类推。

    lpop key :移除并返回列表中的第一个元素。

    rpop key:移除并返回列表中的最后一个元素。

    三.Hash类型(散列)

    1.特点

    (1)由Field和之关联的value组成map键值对

    (2)field和value是字符串类型;

    (3)一个hash中最多包含2^32-1键值对。

    2.Hash相关命令

    hset key field value:设置hash field为指定值,如果key不存在,则先创建,如果field已经存在那么将更新这个field的值。

    hget key field:获取指定的hash field

    hmget key filed1...fieldN:获取全部指定的hash field

    hmset key filed1 value1 ... filedN valueN:同时设置hash的多个field

    hexists key field:测试指定field是否存在

    hdel key field:删除指定的hash field

    hlen key:返回指定hash的field数量

    hkeys key:返回hash的所有field

    hvals key:返回hash的所有value

    hgetall:返回hash的所有filed和value

    四:Set相关命令

    1.特点

    (1)无序的,去重的;

    (2)元素是字符串类型;

    (3)最多包含2^32-1元素。

    2.Set相关命令

    sadd key member [member  ...](无序不重复):将一个或多个 member 元素加入到集合key 当中,已经存在于集合的 member 元素将被忽略。假如 key 不存在,则创建一个只包含 member 元素作成员的集合。当 key 不是集合类型时,返回一个错误。

    smembers key:返回集合 key 中的所有成员。不存在的 key 被视为空集合。

    spop key:移除并返回集合中的一个随机元素。被移除的随机元素。当key不存在或key是空集时,返回nil。

    scard key:返回集合key的基数(集合中元素的数量)。集合的基数。当key不存在时,返回0。

    交集、并集、差集sinter sunion sdiff

    sinter key [key ...]:返回一个集合的全部成员,该集合是所有给定集合的交集。不存在的 key 被视为空集。

    sunion key [key ...]:返回一个集合的全部成员,该集合是所有给定集合的并集。不存在的 key 被视为空集。

    sdiff key [key ...]:返回一个集合的全部成员,该集合是所有给定集合之间的差集。不存在的 key 被视为空集。

    展开全文
  • 面试中常见的数据结构

    万次阅读 2018-07-26 10:08:20
    上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~   首先,先来回顾下C语言中常见的...

    上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~

     

    首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)O

    C语言的基本数据类型有:整型int,浮点型float,字符型char等等

     

    那么,究竟什么是数据结构呢?

    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合

    大部分数据结构的实现都需要借助C语言中的指针和结构体类型

     

    下面,进入今天的重点啦O(∩_∩)O几种常见的数据结构

    (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的有:数组、栈、队列和线性表

    (2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆

    (3)图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系

     

    下面分别对这几种数据结构做一个简单介绍:

    1、线性数据结构:典型的有:数组、栈、队列和线性表

    (1)数组和链表

    a、数组:存放着一组相同类型的数据,需要预先指定数组的长度,有一维数组、二维数组、多维数组等

    b、链表:链表是C语言中一种应用广泛的结构,它采用动态分配内存的形式实现,用一组任意的存储单元存放数据元素链表的,一般为每个元素增设指针域,用来指向后继元素

    c、数组和链表的区别:

    从逻辑结构来看:数组必须事先定义固定的长度,不能适应数据动态地增减的情况;链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项(数组中插入、删除数据项时,需要移动其它数据项)

    从内存存储来看:(静态)数组从栈中分配空间(用NEW创建的在堆中), 对于程序员方便快速,但是自由度小;链表从堆中分配空间, 自由度大但是申请管理比较麻烦

    从访问方式来看:数组在内存中是连续存储的,因此,可以利用下标索引进行随机访问;链表是链式存储结构,在访问元素的时候只能通过线性的方式由前到后顺序访问,所以访问效率比数组要低

    数组的优点:随机访问性强、查找速度快
    数组的缺点:插入和删除效率低、可能浪费内存、内存空间要求高,必须有足够的连续内存空间。数组大小固定,不能动态拓展
    链表的优点:插入删除速度快、内存利用率高,不会浪费内存、大小没有固定,拓展很灵活。
    链表的缺点:不能随机查找,必须从第一个开始遍历,查找效率低
    -    数组    链表
    读取    O(1)    O(n)
    插入    O(n)    O(1)
    删除    O(n)    O(1)

    (2)栈、队列和线性表:可采用顺序存储和链式存储的方法进行存储

    顺序存储:借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系

    链式存储:借助表示数据元素存储地址的指针表示元素之间的逻辑关系

    a、栈:只允许在序列末端进行操作,栈的操作只能在栈顶进行,一般栈又被称为后进先出或先进后出的线性结构

       顺序栈:采用顺序存储结构的栈称为顺序栈,即需要用一片地址连续的空间来存储栈的元素,顺序栈的类型定义如下:

      

       链栈:采用链式存储结构的栈称为链栈:

        

     

    b、队列:只允许在序列两端进行操作,一般队列也被称为先进先出的线性结构

       循环队列:采用顺序存储结构的队列,需要按队列可能的最大长度分配存储空空,其类型定义如下:

      

      链队列:采用链式存储结构的队列称为链队列,一般需要设置头尾指针只是链表的头尾结点:

      

     

    c、线性表:允许在序列任意位置进行操作,线性表的操作位置不受限制,线性表的操作十分灵活,常用操作包括在任意位置插入和删除,以及查询和修改任意位置的元素

     

      顺序表:采用顺序存储结构表示的线性表称为顺序表,用一组地址连续的存储单元一次存放线性表的数据元素,即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系,为了避免移动元素,一般在顺序表的接口定义中只考虑在表尾插入和删除元素,如此实现的顺序表也可称为栈表:

     

     

     

     线性表:一般包括单链表、双向链表、循环链表和双向循环链表

     单链表:

      

     

     双向链表:

     

       

     线性表两种存储结构的比较:

     顺序表:

     优点:在顺序表中,逻辑中相邻的两个元素在物理位置上也相邻,查找比较方便,存取任一元素的时间复杂度都为O(1)

     缺点:不适合在任意位置插入、删除元素,因为需要移动元素,平均时间复杂度为O(n)

     链表:

     优点:在链接的任意位置插入或删除元素只需修改相应指针,不需要移动元素;按需动态分配,不需要按最大需求预先分配一块连续空空

     缺点:查找不方便,查找某一元素需要从头指针出发沿指针域查找,因此平均时间复杂度为O(n)

     

    2、树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆

    (1)二叉树:二叉树是一种递归数据结构,是含有n(n>=0)个结点的有限集合,二叉树具有以下特点:

    二叉树可以是空树;二叉树的每个结点都恰好有两棵子树,其中一个或两个可能为空;二叉树中每个结点的左、右子树的位置不能颠倒,若改变两者的位置,就成为另一棵二叉树

     

    (2)完全二叉树:从根起,自上而下,自左而右,给满二叉树的每个结点从1到n连续编号,如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,则称为完全二叉树

    a、采用顺序存储结构:用一维数组存储完全二叉树,结点的编号对于与结点的下标(如根为1,则根的左孩子为2*i=2*1=2,右孩子为2*i+1=2*1+1=2)

       

     

    b、采用链式存储结构:

    二叉链表:

     

     

    三叉链表:它的结点比二叉链表多一个指针域parent,用于执行结点的双亲,便于查找双亲结点

     

     

    两种存储结构比较:对于完全二叉树,采用顺序存储结构既能节省空间,又可利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系,但采用顺序存储结构存储一般二叉树容易造成空间浪费,链式结构可以克服这个缺点

     

    (3)二叉查找树:二叉查找树又称二叉排序树,或者是一课空二叉树,或者是具有如下特征的二叉树:

    a、若它的左子树不空,则左子树上所有结点的值均小于根结点的值

    b、若它的右子树不空,则右子树上所有结点的值均大于根结点的值

    c、它的左、右子树也分别是二叉查找树

     

    (4)平衡二叉树:平衡二叉查找树简称平衡二叉树,平衡二叉树或者是棵空树,或者是具有下列性质的二叉查找树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差的绝对值不超过1

     

     

    平衡二叉树的失衡及调整主要可归纳为下列四种情况:LL型、RR型、LR型、RL型

     

    (5)树:树是含有n(n>=0)个结点的有限集合,在任意一棵非空树种:
    a、有且仅有一个特定的称为根的结点

    b、当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树,并且T1,T2,...,Tm称为根的子树

     

    (6)堆:堆是具有以下特性的完全二叉树,其所有非叶子结点均不大于(或不小于)其左右孩子结点。若堆中所有非叶子结点均不大于其左右孩子结点,则称为小顶堆(小根堆),若堆中所有非叶子结点均不小于其左右孩子结点,则称为大顶堆(大根堆)

     

     

     

    (7)并查集:并查集是指由一组不相交子集所构成的集合,记作:S={S1,S2,S3,...,Sn}

    (8)B树

     

    3、图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系,可分为有向图和无向图

    展开全文
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本...
    上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~
     
    首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)O
    C语言的基本数据类型有:整型int,浮点型float,字符型char等等
     
    那么,究竟什么是数据结构呢?
    数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合
    大部分数据结构的实现都需要借助C语言中的指针和结构体类型
     
    下面,进入今天的重点啦O(∩_∩)O几种常见的数据结构
    (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,是最常用的一类数据结构,典型的有:数组、栈、队列和线性表
    (2)树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆
    (3)图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系
     
    下面分别对这几种数据结构做一个简单介绍:
    1、线性数据结构:典型的有:数组、栈、队列和线性表
    (1)数组和链表
    a、数组:存放着一组相同类型的数据,需要预先指定数组的长度,有一维数组、二维数组、多维数组等
    b、链表:链表是C语言中一种应用广泛的结构,它采用动态分配内存的形式实现,用一组任意的存储单元存放数据元素链表的,一般为每个元素增设指针域,用来指向后继元素
    c、数组和链表的区别:
    从逻辑结构来看:数组必须事先定义固定的长度,不能适应数据动态地增减的情况;链表动态地进行存储分配,可以适应数据动态地增减的情况,且可以方便地插入、删除数据项(数组中插入、删除数据项时,需要移动其它数据项)
    从内存存储来看:(静态)数组从栈中分配空间(用NEW创建的在堆中), 对于程序员方便快速,但是自由度小;链表从堆中分配空间, 自由度大但是申请管理比较麻烦
    从访问方式来看:数组在内存中是连续存储的,因此,可以利用下标索引进行随机访问;链表是链式存储结构,在访问元素的时候只能通过线性的方式由前到后顺序访问,所以访问效率比数组要低
     
    (2)栈、队列和线性表:可采用顺序存储和链式存储的方法进行存储
    顺序存储:借助数据元素在存储空间中的相对位置来表示元素之间的逻辑关系
    链式存储:借助表示数据元素存储地址的指针表示元素之间的逻辑关系
    a、栈:只允许在序列末端进行操作,栈的操作只能在栈顶进行,一般栈又被称为后进先出或先进后出的线性结构
       顺序栈:采用顺序存储结构的栈称为顺序栈,即需要用一片地址连续的空间来存储栈的元素,顺序栈的类型定义如下:
      
       链栈:采用链式存储结构的栈称为链栈:
        
     
    b、队列:只允许在序列两端进行操作,一般队列也被称为先进先出的线性结构
       循环队列:采用顺序存储结构的队列,需要按队列可能的最大长度分配存储空空,其类型定义如下:
      
      链队列:采用链式存储结构的队列称为链队列,一般需要设置头尾指针只是链表的头尾结点:
      
     
    c、线性表:允许在序列任意位置进行操作,线性表的操作位置不受限制,线性表的操作十分灵活,常用操作包括在任意位置插入和删除,以及查询和修改任意位置的元素
      顺序表:采用顺序存储结构表示的线性表称为顺序表,用一组地址连续的存储单元一次存放线性表的数据元素,即以存储位置相邻表示位序相继的两个元素之间的前驱和后继关系,为了避免移动元素,一般在顺序表的接口定义中只考虑在表尾插入和删除元素,如此实现的顺序表也可称为栈表:
     
     线性表:一般包括单链表、双向链表、循环链表和双向循环链表
     单链表:
      
     双向链表:
       
     线性表两种存储结构的比较:
     顺序表:
     优点:在顺序表中,逻辑中相邻的两个元素在物理位置上也相邻,查找比较方便,存取任一元素的时间复杂度都为O(1)
     缺点:不适合在任意位置插入、删除元素,因为需要移动元素,平均时间复杂度为O(n)
     链表:
     优点:在链接的任意位置插入或删除元素只需修改相应指针,不需要移动元素;按需动态分配,不需要按最大需求预先分配一块连续空空
     缺点:查找不方便,查找某一元素需要从头指针出发沿指针域查找,因此平均时间复杂度为O(n)
     
    2、树形结构:结点间具有层次关系,每一层的一个结点能且只能和上一层的一个结点相关,但同时可以和下一层的多个结点相关,称为“一对多”关系,常见类型有:树、堆
    (1)二叉树:二叉树是一种递归数据结构,是含有n(n>=0)个结点的有限集合,二叉树具有以下特点:
    二叉树可以是空树;二叉树的每个结点都恰好有两棵子树,其中一个或两个可能为空;二叉树中每个结点的左、右子树的位置不能颠倒,若改变两者的位置,就成为另一棵二叉树
     
    (2)完全二叉树:从根起,自上而下,自左而右,给满二叉树的每个结点从1到n连续编号,如果每个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,则称为完全二叉树
    a、采用顺序存储结构:用一维数组存储完全二叉树,结点的编号对于与结点的下标(如根为1,则根的左孩子为2*i=2*1=2,右孩子为2*i+1=2*1+1=2)
       
    b、采用链式存储结构:
    二叉链表:
     
    三叉链表:它的结点比二叉链表多一个指针域parent,用于执行结点的双亲,便于查找双亲结点
     
    两种存储结构比较:对于完全二叉树,采用顺序存储结构既能节省空间,又可利用数组元素的下标值确定结点在二叉树中的位置及结点之间的关系,但采用顺序存储结构存储一般二叉树容易造成空间浪费,链式结构可以克服这个缺点
     
    (3)二叉查找树:二叉查找树又称二叉排序树,或者是一课空二叉树,或者是具有如下特征的二叉树:
    a、若它的左子树不空,则左子树上所有结点的值均小于根结点的值
    b、若它的右子树不空,则右子树上所有结点的值均大于根结点的值
    c、它的左、右子树也分别是二叉查找树
     
    (4)平衡二叉树:平衡二叉查找树简称平衡二叉树,平衡二叉树或者是棵空树,或者是具有下列性质的二叉查找树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差的绝对值不超过1
     
    平衡二叉树的失衡及调整主要可归纳为下列四种情况:LL型、RR型、LR型、RL型
     
    (5)树:树是含有n(n>=0)个结点的有限集合,在任意一棵非空树种:
    a、有且仅有一个特定的称为根的结点
    b、当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,...,Tm,其中每一个集合本身又是一棵树,并且T1,T2,...,Tm称为根的子树
     
    (6)堆:堆是具有以下特性的完全二叉树,其所有非叶子结点均不大于(或不小于)其左右孩子结点。若堆中所有非叶子结点均不大于其左右孩子结点,则称为小顶堆(小根堆),若堆中所有非叶子结点均不小于其左右孩子结点,则称为大顶堆(大根堆)
     
     
    (7)并查集:并查集是指由一组不相交子集所构成的集合,记作:S={S1,S2,S3,...,Sn}
    (8)B树
     
    3、图形结构:在图形结构中,允许多个结点之间相关,称为“多对多”关系,可分为有向图和无向图

    转载于:https://www.cnblogs.com/qccadmin/p/10085749.html

    展开全文
  • 1.列表Python有6个序列的内置类型,但最常见的是列表和元组。...列表的数据项不需要具有相同的类型。创建一个列表,只要把逗号分隔的不同的数据项使用方括号括起来即可。如下list = [‘aaa‘,‘...
  • ① 集合 集合中任何两个数据元素之间都没有逻辑关系,组织形式松散. ② 线性结构 线性结构中的 结点...集合:结构的数据元素之间除了同属于一种类型外,别无其它关系 线性结构结构的数据元素之间存在一对一的...
  • 今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)OC语言的基本数据类型有:整型int,浮点型float,字符型char等等添加描述那么,究竟...
  • 上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据...
  • 今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)OC语言的基本数据类型有:整型int,浮点型float,字符型char等等添加描述那么,究竟...
  • 西门子S7-200(CPU 224)S7-200西门子公司推出一种小型PLC,它优点(1)结构紧凑,占用空间小。(2)拓展型良好,可以接称重模块,数字量、模拟量输入输出模块等等,使用起来非常方便。(3)价格低廉但是除此之外,...
  • 这 8 种数据结构有什么区别呢? ①、数组 优点: ... 链表一种递归的数据结构,它或者为空(null),或者指向一个结点(node)的引用,该节点还有一个元素和一个指向另一条链表的引用。 ...
  • 以下将会介绍常见的数据结构。 如果嫌麻烦,那就可以跳过,以后再慢慢学习,日后再回过头看总结也行 数组(Array): 1、数组存储在连续的内存上 2、数组的元素类型必须相同 3、数组可以直接通过下标访问 4、查找与...
  • 简单来说 redis 就是一个数据库,不过与传统数据库不同的 redis 的数据是存在内存中的,所以读写速度非常快,因此 redis 被广泛应用于缓存方向。另外,redis 也经常用来做分布式锁。redis 提供了多种数据类型来...
  • 最近看到es6中set与map,然后去了解了一下为什么es6中要新增这么两种数据结构,了解过之后我看的很懵逼,就想着从0开始整理一下几种常见的数据类型及其特点.首先我们来了解下什么是数据结构数据结构是计算机存储、...
  • 列表(List)Python语言中最通用的序列数据结构之一。列表一个没有固定长度的,用来表示任意类型对象的位置相关的有序集合。列表的数据项不需要具有相同的类型,常用的列表操作主要包括:索引、连接、乘法和切片...
  • Queue什么是队列队列是数据结构中比较重要的一种类型,它支持 FIFO,尾部添加、头部删除(先进队列的元素先出队列),跟我们生活中的排队类似。队列的种类单队列(单队列就是常见的队列, 每次添加元素时,都添加到...
  • redis 数据结构常见命令

    千次阅读 2019-07-05 23:36:53
    现在开始将探究Redis5种数据结构,我们会解释每种数据结构是什么,包含了什么有效方法(Method),以及你能用这些数据结构处理哪些类型的特性和数据。 目前为止,我们所知道Redis构成仅包括命令、关键字和...
  • 2.常见的数据结构1.数组2.栈3.队列4.链表5.树6.堆7.哈希表8.图2.1 数组数组可以在内存中连续存储多个元素的结构,数组的元素通过数组下标进行访问,下标从0开始。数组优点:读取快,因为读取数据用的索引,只要...
  • 在关系数据库中,索引一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。更通俗的说,数据库索引的...
  • 本文结构如下: 什么是基本数据类型 什么是包装类 两者的区别以及使用...因此为方便基本类型的数据计算,java创造了八种基本数据类型:整型byte, short, int, long, 浮点型double, float, 字符型char, 布尔型bo...
  • 在计算机程序设计中, 图也一种非常常见的数据结构. 但是, 图论其实一个非常大的话题, 我们通过本章的学习来认识一下关于图的一些内容以及图的抽象数据类型. 一. 图的概念 我们先来认识一下什么是图, 另外图中...
  • 在关系数据库中,索引一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构,它某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。更通俗的说,数据库索引的...
  • 队列有次序的数据集合,其特征: 新数据项的添加总发生在一端,通常称为“尾rear端” 现存数据的一处总发生在另一端,通常称为“首front端” 当数据项加入队列时,首先出现在队尾,随着队首数据项的移除,它...
  • C语言中的数据结构

    2018-03-18 21:33:10
    那么,究竟什么是数据结构呢?...下面,进入今天的重点啦O(∩_∩)O几种常见的数据结构 (1)线性数据结构:元素之间一般存在元素之间存在一对一关系,最常用的一类数据结构,典型的有:数组、栈、队列和线性表
  • 导语Lua底层数据结构的内存动态分配,一般...由于lua一个跨平台的脚本语言,会根据平台位数(16bitbit)、平台类型(linuxwindows)、语言标准(C89C99)、以及编译参数等开启预编译选项,导致基本数据结构的字长和类型...
  • 结构数据是一种提供网页相关信息标准化方法。它有助于像 Google 这样搜索引擎更好地了解你内容。 但是,它对你有什么好处,你要如何实施它呢? 让我们开始吧! 结构数据如何帮助你...富结果常见类型是
  • 常用数据结构2. 什么是链表、队列、栈3. 什么是树(平衡二叉树、二叉排序树、B树、B+树、R树、红黑树) 1. 常用数据结构 1). 数组:顺序存储,随机访问。 链表:链表存储,顺序访问。 2). 栈:分为栈顶和栈底,遵循...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,058
精华内容 423
关键字:

常见的数据结构的类型是什么

数据结构 订阅