数据结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

• 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
• 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。
• 数据项：数据项是数据不可分割的最小单位。
• 数据对象：是性质相同的数据元素的集合，是数据的子集。

逻辑结构

1. 集合结构：几何结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。

   
   
   集合结构

2. 线性结构：线性结构中的数据元素之间是一对一的关系。

   
   
   线性结构

3. 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。

   
   
   树形结构

4. 图形结构：图形结构的数据元素是多对多的关系。

   
   
   图形结构

在用示意图表示数据的逻辑结构时，要注意两点：

1. 将每一个数据元素看做一个节点，用圆圈表示；
2. 元素之间的逻辑关系用节点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示。

物理结构

物理结构是数据的逻辑结构在计算机中的存储形式，是针对计算机的。数据的存储结构用正确反映数据元素之间的逻辑关系，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。
　　数据元素的存储结构形式有两种：

1. 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

   
   
   顺序存储结构

2. 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以使连续的，可以是不连续的。数据源岁的存储关系并不能反应其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。

   
   
   链式存储结构

抽象数据类型

数据类型

是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
Ｃ语言中，按照取值不同，数据类型可以分为两类：

1. 原子类型：不可再分解的基本类型，包括整形、实型、字符型。
2. 结构类型：由若干个类型组合而成，是可以再分解的。

抽象数据类型

是指一个数学模型及定义在该模型上的一组操作。抽象的意义在于数据类型的数学抽象特性。（Point等）

算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

数据结构与算法关系

算法定义

算法特性

算法有五个基本的特性：输入、输出、有穷性、确定性和可行性。

1. 输入输出：算法具有零个或多个输入，至少有一个或多个输出。
2. 有穷性：算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。
3. 确定性：算法的每一步骤都具有确定的含义，不会出现二义性。
4. 可行性：算法的每一步必须都是可行的，也就是说，每一步都能够通过执行有限次数来完成。

算法设计的要求

1. 正确性：算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。但是算法的“正确”通常在用法上有很大的差别，大体分为一下四个层次：

• 算法程序没有语法错误；
• 算法程序对于合法的输入数据能够产生满足要求的输出结果；
• 算法程序对于非法的输入数据能够得出满足规格说明的结果；
• 算法程序对于精心选择的，甚至是刁难的测试数据都有满足要求的输出结果。

实际上，这也是程序员程序的健壮性的一个体现。你无法保证输入数据是完全按照给定的规则的，当输入有一点不合规则就导致崩溃的程序是不健壮的。
2.可读性：算法设计的另一目的是为了便于阅读、理解和交流。
这个就不用多说了，程序员写的程序，可读性高意味着易于理解、调试与修改，可读性差则经常会出现时间长了不知道自己写了什么的窘况。

3. 健壮性：当输入的数据不合法时，算法也能做出相应的处理，而不是产生异常或莫名其妙的结果。
4. 时间效率和存储量要求：设计的算法应尽量满足时间效率高和存储量低的需求。用最少的空间花最少的时间解决同样的问题。

算法效率的度量方法

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

函数的渐进增长

给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐进快于g(n)。
　　结论：判断一个算法好不好，只通过少量的数据是不能做出准确的判断的，通过对比算法的时间函数的渐进增长性，可以得出某个算法，随着n增大，它会越来越优于另一算法，或者越来越差与另一算法。这就是事前估算法的理论依据，通过算法时间复杂度来估算算法时间的效率。

算法的时间复杂度

• 大O阶来表示算法的时间复杂度
• 推导大O阶方法

• 常见的算法时间复杂度

  
  
  常见的时间复杂度

最坏情况与平均情况

算法空间复杂度

线性表

零个或多个元素的有限序列。
抽象数据类型定义：

线性表的顺序存储结构

线性表的顺序存储结构指的是用一段地址连续的存储单元依次存储线性表的数据元素。

• 顺序存储方式：存储空间的起始位置、线性表的最大容量、线性表的当前长度。
• 地址计算方法：首地址+单个存储单元长度*下标
• 插入与删除操作：具体步骤、时间复杂度

线性表的链式存储结构

• 单链表
• 静态链表
• 循环链表
• 双向链表

栈与队列

栈

栈是限定仅在表尾进行插入和删除操作的线性表。允许插入和删除的一段称为栈顶，另一端称为栈底，不含任何数据元素的栈称为空栈。（FILO）

栈的抽象数据类型

栈的顺序存储结构——入栈、出栈

两栈共享空间

栈的链式存储结构

栈的应用——递归

栈的应用——四则运算表达式求值

队列

队列是只允许在一端进行插入操作，在另一端进行删除操作的线性表。（FIFO）

队列的抽象数据类型

![Upload 9CAB1B6D-D3BF-456F-A624-96BDB101D5B9.png failed. Please try again.]

循环队列

队列的链式存储结构及其实现

串

串是由零个或多个字符组成的有限序列，又名字符串。

串的比较

串的抽象数据类型

串的存储结构

• 顺序
• 链式

朴素匹配算法——低效

KMP模式匹配算法

树

树是n个节点的有限集，在任意一颗非空树中，有且仅有一个根节点，当n>1时，其余节点可分为m(m>0)个互不相交的有限集T1,T2...，其中每一个集合本身又是一棵树，并称为根的子树。需要注意的还有两点：

1. n>0时根节点是唯一的，不可能存在多个根节点；
2. m>0时，子树的个数没有限制，但他们一定是互不相交的。

节点分类

树的节点包含一个数据元素及若干指向其子树的分支，节点拥有的子树数称为节点的毒。度为0的节点称为叶节点或终端节点；度不为0的节点称为非终端节点或分支节点。除根节点之外，分支节点也称为内部节点，树的度是树内各节点的度的最大值。

节点之间的关系

父子、兄弟、祖先。

其他相关概念

• 节点的层次、树的深度、高度。
• 有序树、无序树。
• 森林是m(m>0)棵互不相交的树的集合。

树的抽象数据类型

树的存储结构

• 双亲表示法
• 孩子表示法
• 孩子兄弟表示法

二叉树的定义

二叉树是n(n>0)个结点的有限集合，该集合或者为空集，或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和又子树的二叉树组成。二叉树特点如下：

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点；
• 左子树和右子树是有顺序的，次序不能颠倒；
• 即使一个结点只有一棵子树，也要区分是左右子树。

特殊二叉树

• 斜树
• 满二叉树
• 完全二叉树

二叉树的性质

• 在第i层上最多有2^(i-1)个结点
• 深度为k的二叉树至多有2^k-1个结点
• 任意一颗二叉树T，如果终端结点数为n0，度为2的结点树为n2，则n0=n2+1
• 具有n个结点的完全二叉树的深度为[log2(n) 向下取整]+1
• 如果对一棵有n个结点的完全二叉树的结点按层序编号，则有

1. 如果i=1，则结点i是二叉树的根，若i>1，则父节点是[i/2 向下取整]
2. 如果2i>n，则结点i无左孩子，否则其左孩子是结点2i
3. 如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1

二叉树的存储结构

• 顺序(一般只用于完全二叉树，否则浪费存储空间)
• 二叉链表

遍历二叉树

• 前序遍历
• 中序遍历
• 后序遍历
• 层序遍历

二叉树的建立

树、森林与二叉树的转换

二叉搜索树

查找、插入、删除节点算法

平衡二叉树

插入、删除节点算法

堆

最大堆、最小堆
哈弗曼树、哈夫曼编码

图