数据结构与算法(一):数据结构

简单地总结一下常用的数据结构

Posted by Ted on February 1, 2015

前言

img

物理结构(存储结构):

  • 顺序存储
  • 链式存储

逻辑结构:

逻辑结构分为以下几种:

  • 集合结构 集合中任何两个数据元素之间都没有逻辑关系,组织形式松散.
  • 线性结构 线性结构中的 结点按逻辑关系依次排列形成一个“锁链”,其中有线性表(数组、链表),栈,队列,字符串。其中,栈、队列、字符串是特殊的线性表
  • 树形结构 树形结构具有分支、层次特性,其形态有点象自然界中的树.
  • 图状结构 图状结构中的结点按逻辑关系互相缠绕,任何两个结点都可以邻接

线性结构与非线性结构的区别:

  • 线性结构中的数据元素存在着”一对一”关系.
  • 相对于线性结构,非线性结构中的数据元素间存在”一对多”(树结构)或”多对多”(图结构)的关系.

线性结构的特点是:

  1. 只有一个首结点
  2. 只有一个尾结点
  3. 除首尾结点外, 其它结点称为内部结点
  4. 首结点只有后继结点,无前趋结点.
  5. 尾结点只有前趋结点,元后继结点.
  6. 内部结点有一个前趋结点,有一个后继结点.

一、线性结构

列表学习PDF

(一)、数组(Array)

数组是一种线性结构然后按顺序存储的数据结构,下标不同的n(n≥1)个相同数据类型的数据元素a0,a1,a2,…,an-1构成的占用一块地址连续的内存单元的有限集合

数组是将元素在内存中连续存放,由于每个元素占用内存相同,可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素,需要移动大量元素,在内存中空出一个元素的空间,然后将要增加的元素放在其中。同样的道理,如果想删除一个元素,同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据,很少或不插入和删除元素,就应该用数组。

img

(二)、链表(List)

链表:即是由节点(Node)组成的线性集合,每个节点可以利用指针指向其他节点。它是一种包含了多个节点的、能够用于表示序列的数据结构。

链表中的元素在内存中不是顺序存储的,而是通过存在元素中的指针联系到一起。比如:上一个元素有个指针指到下一个元素,以此类推,直到最后一个元素。如果要访问链表中一个元素,需要从第一个元素开始,一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了,只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

  • 单向链表: 链表中的节点仅指向下一个节点,并且最后一个节点指向空。
  • 双向链表: 其中每个节点具有两个指针 p、n,使得 p 指向先前节点并且 n 指向下一个节点;最后一个节点的 n 指针指向 null。
  • 循环链表:每个节点指向下一个节点并且最后一个节点指向第一个节点的链表。
  • 时间复杂度:
    • 索引: O(n)
    • 搜索: O(n)
    • 插入: O(1)
    • 移除: O(1)

(三)、栈

栈 (Stack)是限定仅在表尾进行插入和删除操作的特殊线性表,一种后进先出(last in first off,LIFO)的数据结构,栈属于一个逻辑概念,栈的实现可以用顺序(数组)也可以用链式(链表)。

我们把允许插入和删除的一端称为栈顶,另一端称为栈底,不含任何数据元素的栈称为空栈。

img

  • 索引: O(n)
  • 搜索: O(n)
  • 插入: O(1)
  • 移除: O(1)

应用场景

1、Navigationcontroller

Navigationcontroller就是一个栈结构,先push进来的ViewController被压在栈底,当pop时,会将后进的pop出去

2、OpenGL中的图形绘制

- (void)drawGreenCircle:(CGContextRef)ctxt {
    UIGraphicsPushContext(ctxt);
    [[UIColor greenColor] setFill];
    // draw my circle
    UIGraphicsPopContext();
}

在drawGreenCircle方法中,在设置填充颜色之前,我们Push保存了绘图上下文的信息,然后在设置当前操作的一些环境变量,绘制图形,绘制完成之后,我们Pop出之前保存的绘图上下文信息,从而不影响后面的绘图。

(四)、队列

队列(Queue)是只允许在一段进行插入操作,而在另一端进行删除操作的线性表,是一种先进先出 (fisrt in first out,FIFO)的结构,允许插入的一端称为队尾,允许删除的一端称为队头。队列的实现同样可以用顺序(数组)也可以用链式(链表)

img

  • 索引: O(n)
  • 搜索: O(n)
  • 插入: O(1)
  • 移除: O(1)

应用场景

GCD队列

(五)、字符串(String)

串是由另个或多个字符组成的有限序列,又名字符串,字符串通常采用顺序存储,但是字符串较长而没有那么大的连续空间时,可以把一个字符串分成多个小串,串与串之间采用链式存储

ASCII编码是由8位二进制数表示一个字符,总共可以表示256个字符

Unicode编码由16位的二进制表示一个字符,总共可以表示65万个多个字符,为了和ASCII码兼容,Unicode的前256个字符和ASCII码完全相同

二、树形结构

(一)、树(Tree)

树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中:

有且仅有一个特定的称为根(Root)的结点;

当n>1时,其余结点可分为m(m>0)个互不交互的有限集,其中每一个集合本身又是一颗树,并且称为根的字数。

二叉树

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者是一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点:

  • 每个结点最多有两棵子树。
  • 左子树和右子树是有顺序的,次序不能颠倒。
  • 即使树中某个结点只有一棵子树,也要区分是左子树还是右子树。

二叉树的五种基本形态:

img

特殊二叉树

  • 完全二叉树: 除最后一层外,每一层上的结点数均达到最大值;在最后一层上只缺少右边的若干结点。
  • 满二叉树: 树中的每个节点仅包含 0 或 2 个节点。
  • 完美二叉树(Perfect Binary Tree): 二叉树中的每个叶节点都拥有两个子节点,并且具有相同的高度。

(二)、堆(Heap)

堆是一种特殊的基于树的满足某些特性的数据结构,整个堆中的所有父子节点的键值都会满足相同的排序条件。堆更准确地可以分为最大堆与最小堆,在最大堆中,父节点的键值永远大于或者等于子节点的值,并且整个堆中的最大值存储于根节点;而最小堆中,父节点的键值永远小于或者等于其子节点的键值,并且整个堆中的最小值存储于根节点。

  • 访问: O(log(n))
  • 搜索: O(log(n))
  • 插入: O(log(n))
  • 移除: O(log(n))
  • 移除最大值 / 最小值: O(1)

img

三、图(Graph)

图是一种数据元素间为多对多关系的数据结构,加上一组基本操作构成的抽象数据类型。图是由顶点的有穷非空集合和顶点之间的集合组成,通常表示为:G(V,E),其中,G表示一个图,V是图中顶点的节后,E是图中边的集合.

  • 无向图(Undirected Graph): 无向图具有对称的邻接矩阵,因此如果存在某条从节点 u 到节点 v 的边,反之从 v 到 u 的边也存在。
  • 有向图(Directed Graph): 有向图的邻接矩阵是非对称的,即如果存在从 u 到 v 的边并不意味着一定存在从 v 到 u 的边。

img

四、哈希表

hash map 是一个存储键值间关系的数据结构。HashMap 通过哈希函数将键转化为桶或者槽中的下标,从而便于指定值的查找。HashMap是顺序结构及链表结构的组合

哈希用于将任意长度的数据映射到固定长度的数据。哈希函数的返回值被称为哈希值、哈希码或者哈希。如果不同的主键得到相同的哈希值,则发生了冲突。

img

冲突解决

  • 链地址法(Separate Chaining):在链地址法中,每个桶(bucket)是相互独立的,每一个索引对应一个元素列表。处理HashMap 的时间就是查找桶的时间(常量)与遍历列表元素的时间之和。
  • 开放地址法(Open Addressing):在开放地址方法中,当插入新值时,会判断该值对应的哈希桶是否存在,如果存在则根据某种算法依次选择下一个可能的位置,直到找到一个未被占用的地址。开放地址即某个元素的位置并不永远由其哈希值决定。

###