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

前言

物理结构(存储结构)：

• 顺序存储
• 链式存储

逻辑结构：

逻辑结构分为以下几种：

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

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

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

线性结构的特点是：

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

一、线性结构

列表学习PDF

(一)、数组(Array)

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

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

(二)、链表(List)

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

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

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

(三)、栈

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

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

• 索引: 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)的结构，允许插入的一端称为队尾，允许删除的一端称为队头。队列的实现同样可以用顺序(数组)也可以用链式(链表)

• 索引: 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)个结点的有限集合，该集合或者为空集(称为空二叉树)，或者是一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

二叉树的特点：

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

二叉树的五种基本形态：

特殊二叉树

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

（二）、堆(Heap)

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

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

三、图(Graph)

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

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

四、哈希表

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

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

冲突解决

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