学习数据结构和算法是比较枯燥的过程，很多定义需要理解记忆。一旦理解了这些概念，触类旁通，学习其他的东西时，是很有帮助并且很有意思的事。

数据简介

数据：是描述客观事物的符号,是计算机可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
数据的特征：
1、可以输入到计算机中
2、能被计算机程序处理。

数据元素：是组成数据的、并具有一定意义的基本单位，在计算机中通常作为整体处理。也被成为记录。
比如人类中，数据元素就是人。

数据项：一个数据元素可以由若干个数据项组成。
比如人这样的数据元素，由眼、耳、鼻、嘴、手、脚等数据项组成。是数据最小的不可分割的最小单元。

数据对象：是性质相同的数据元素的集合，是数据的子集。通常情况下，数据对象简称为数据。
NSString、int、double都为数据。但是NSString、int、double是不同的数据对象。

数据结构

结构：是各个组成部分相互搭配和排列的方式。
在现实世界中，不同数据元素之间不是独立的，而是存在特定的关系，这些关系成为结构。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
数据结构分为逻辑结构和物理结构。

逻辑结构：是指数据对象中数据元素之间的相互关系。
逻辑结构又分为以下四种：
1、集合结构：集合结构中的数据元素，除了他们属于同一个集合外，没有其他关系。
2、线性结构：线性结构中的数据元素之间是一对一的关系。
3、树形结构：树形结构中的数据元素存在一对多的关系。
4、图形结构：图形结构中的数据元素是多对多的关系。

物理结构：也叫存储结构，是指逻辑结构在计算机上存储的方式。
数据的存储结构应正确的反映数据元素之间的逻辑关系。
物理结构有两种存储方式：
1、顺序存储结构：是把数据元素存放在地址连续的内存单元中，其数据间的逻辑关系和物理关系是一致的。

2、链式存储结构：是把数据元素存放在任务的存储单元中，这组存储单元可以是连续的，也可以是不连续的。
数据元素在存储时，是有一个指针地址指向它，这样就可以通过这个地址找到这个数据元素。

数据类型

数据类型：是指一组性质相同的值的集合以及定义在此集合上的一些操作的总称。
类型就是用来说明变量或者表达式的取值范围和所能进行的操作。

数据类型的目的就是为了根据数据的类型开辟相应的内存空间来存储这个数据。
在C语言中，按照取值的不同，数据类型分为两类：
原子类型：不可再分的基本类型。包括整型、实型、字符型等。
结构类型：由若干个类型组合而成，是可以分解的。例如，整型数组是由若干个整型数据组成的。

抽象数据类型：是指一个数学模型以及定义在该模型上的一组操作。像point等都是抽象数据类型。
抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。
在高级语言中，为了便于开发或者表示某种计算方式，会出现很多的抽象数据类型。

算法定义

• 算法：算法是解决特性问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或者多个操作。
  算法的五个特性
  输入：算法具有零个或多个输入。
  输出：算法至少有一个输出。
  有穷性：算法在执行有限的步骤之后，会自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
  确定性：算法的每一个步骤都具有确定的含义，不会出现二义性。
  可行性：算法的每一个步骤都是可行的，也就是说，每一步都能够通过执行有限次数完成。

• 算法设计的要求
  1、正确性:算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求，能够得到问题的正确答案。

正确性提现在以下四个层次
1）算法程序无语法错误
2）对于输入的合法数据能输出正确的结果
3）对于非法的输出数据能够给出错误的结果
4）对于极限的测试数据能够给出正确的输出结果

2、可读性:代码便于阅读、理解以及交流。
3、健壮性：对于不合法的输入数据，能够给你相关处理，而不是崩溃或者异常的结果
4、时间效率高和存储量低

算法效率的度量方法

1、事后统计方法
通过设计好的测试程序和数据，利用计算机计时器对不同算法编制的程序的运行时间进行比较，从而确定算法效率的高低。
2、事前分析估算方法
在计算机程序编制前，依据统计方法对算法进行估算。

• 一个程序的运行时间，依赖于算法的好坏和问题的输入规模。也就是运行了多少次。

函数的渐近增长

函数的渐近增长：给定两个函数f(n)和g(n)，如果存在一个整型N，使得对于所有的n > N，f(n)总是比g(n)大，那么就说f(n)的增长渐近快于g(n)。

算法时间复杂度

在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n)=O(f(n))。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。其中f(n)是问题规模n的某个函数。

推导大O阶方法
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项相乘的常数。

线性表

线性表：零个或者多个数据元素的有限序列。
线性表元素的个数n(n>=0)定义为线性表的长度，当n=0时，成为空表。
线性表的顺序存储结构：指的是用一段地址连续的存储单元依次存储线性表的数据元素。
结点：结点包括数据域和指针域。这两部分信息组成数据元素a的存储映像。
为了表示每个数据元素a与其直接后继数据元素a+1之间的逻辑关系，对数据元素a来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息，这个存储数据元素的域称为数据域，把存储直接后继位置的域称为指针域。
指针域中存储的信息称为指针或者链。
链表中第一个结点的存储位置叫做头指针。
单链表：采用链式存储结构，用一组任意的存储单元存放线性表的元素。
在单链表中，第一个结点前附设一个结点，叫做头结点。存储线性表的长度等信息。
单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
顺序存储结构：用一段连续的内存单元依次线性表的数据元素。
顺序存储结构需要预先分配存储单元，分大了，空间浪费，分小了容易发生上溢。
双向链表:是在单链表的每个结点上，在设置一个指向其前驱结点的指针域。

栈

栈：是限定仅在表尾进行插入和删除操作的线性表。
允许插入和删除的一端称为栈顶，另一端称为栈底。不含任何数据元素的栈称为空栈。
栈的原则：先进后出原则（LIFO:Last In First Out）。
栈的插入操作，叫做进栈，也叫压栈、入栈。
栈的删除操作，叫做出栈，也叫弹栈。

栈的应用

递归函数：把一个直接调用自己或者通过一系列的调用语句间接地调用自己的函数，就是递归函数。（斐波那契数列算法）
对于每一层递归，函数的局部变量、参数值以及返回地址都被压入栈中。在退回阶段，位于栈顶的局部变量、参数值和返回地址被弹出，用于返回调用层次中执行代码的其余部分，也就是恢复调用的状态。

队列

队列：是只允许在一端进行插入操作，而在另外一端进行删除操作的线性表。
队列原则：先进先出原则（FIFO:First In First Out）

斐波那契数列算法

说如果兔子在出生两个月后，基友繁殖能力，一对兔子每个月能生出一对小兔子来。假如所有兔子都不死，那么40个月后可以繁殖多少对兔子？

int Fbi(int i){
    if (i < 2) {
        return i == 0 ? 0 : 1;
    }
    return Fbi(i-1) + Fbi(i-2);
}
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        int i;
        for (i=0; i<40; i++) {
            printf("%d\n",Fbi(i));
        }
    }
    return 0;
}

串

串：串是由零个或者多个字符组成的有限序列，又名叫做字符串。
串的存储结构包括顺序存储结构和链式存储结构。

树

树：树（Tree）是n（n>=0）个结点的有限集。
n=0时称为空树。
在任意一颗非空树中：
（1）有且仅有一个特定的称为根（Root）的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、T3、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

结点拥有的子树数称为结点的度（Degree）。度为0的结点称为叶节点（Leaf）或者终端结点；度不为0的结点称为非终端节点或者分支结点。除根节点之外，分支结点也被称为内部结点。树的度是树内各节点的度的最大值。

结点的层次（Level）是从根定义起，根为第一层，根的孩子为第二层。树中结点的最大层次称为树的深度或者高度。

树和线性结构的区别

线性结构：第一个数据元素无前驱。最后一个数据元素无后继。中间元素有一个前驱和一个后继。
树结构：根结点无双亲，是唯一的。叶结点没有孩子，可以有多个。中间结点有一个双亲或者多个孩子。

二叉树：是n（n>=0）个结点的有限集合，，该集合或者为空集（空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。
二叉树特点：
（1）每个结点最多有两棵子树。
（2）左子树和右子树是有顺序的，不能任意颠倒。
（3）即使树中某结点只有一棵子树，也要区分是左子树还是右子树。
二叉树的性质：
（1）在二叉树的第i层上至多有2^(i-1)个结点（i>=1）;
（2）深度为k的二叉树至多有2^k-1个结点（k>=1）；
（3）对任何一课二叉树T，如果其终端结点树为n0，度为2的结点数为n2,则n0=n2+1；
（4）具有n个结点的完全二叉树的深度为[log2^n]+1
（5）如果对一棵有n个结点的完全二叉树（其深度为[log2^{n]+1）的结点按层序编号（从第1层到第[log2}n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：
1、如果i=1，则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结点[i/2];
2、如果2i>n，则结点i无左子树（结点i为叶子结点）；否则其左子树是结点2i；
3、如果2i+1>n，则结点i无右子树；否则其右子树是结点2i+1。

二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问依次且仅被访问一次。
遍历方法
1、前序遍历：若二叉树为空，则空操作返回。否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。
2、中序遍历：若二叉树为空，则空操作返回。否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。
3、后序遍历：若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式访问左右子树，最后访问根结点。
4、层序遍历：若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上到下逐层访问，在同一层中，按从左到右的顺序对结点逐个访问。

参考书籍：
《大话数据结构》--程杰著 清华大学出版社