大家好，欢迎来到IT知识分享网。

大话数据结构

1. 数据结构绪论

• 数据:是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。

• 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。
• 数据结构分为逻辑结构和物理结构,逻辑结构是面向问题的，而物理结构就是面向计算机的。目标是将数据及其逻辑关系存储到计算机的内存中。
  1. 逻辑结构:是指数据对象中数据元素之间的相互关系。有四种：集合结构、线性结构（数据元素是一对一）、树形结构（一对多）、图形结构（多对多）。
  2. 物理结构:是指数据的逻辑结构在计算机中的存储形式。分为顺序存储和链式存储。
     • 顺序存储结构:是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
     • 链式存储结构:是把数据元素存放在任意的存储单元里，这组存储单元可以是连 续的，也可以是不连续的。数据元素的存储关系并不能反映其逻辑关系。
• 数据类型:是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
• 抽象数据类型 (Abstract Data Type,ADT): 是指一个数学模型及定义在该模型上的一组操作。

2. 算法

• 算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。具有五个基本特性:输入、输出、有穷性、确定性和可行性。
• 算法效率的度量方法:事后统计方法、事前分析估算方法。
• 分析一个算法的时间复杂度
  1. 用常数 1 取代运行时间中的所有加法常数。
  2. 在修改后的运行次数中，只保留最高阶项 。
  3. 如果最高阶项存在且不是 1 ，则去除与这个项相乘的常数。 得到的结果就是大 O 阶。

3. 线性表

• 钱性表(List):零个或多个数据元素的有限序列。

  1. 线性表的顺序存储结构:用一段地址连续的存储单元依次存储线性表的触据元素。

     优点	缺点
     无须为表示表中元素之 间的逻辑关系而增加额外的存储空间	插入和删除操作需要移动大量元素
     可以快速地存取表中任一位置的元素	当线性表长度变化较大时，难以确定存储空间的容量
     	造成存储空间的”碎片”

  2. 线性表的链式存储结构：用一组任意的存储单元存放线性表的元素。

• 头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针；头指针具有标识作用，所以常 用头指针冠以链表的名字；无论锥表是否为空，头指针均不为空。头指针是链表由与必要元素。

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义(也可存储链表的长度)；有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了；头结点不一定是链表必须要素。

• 静态链表:用数组描述的链表叫静态链表，主要用于那些没有指针的语言实现链表，用游标实现。

• 循环链表，用尾指针查找开始结点和终端结点都很方便。

• 双向链表，是在单链袤的每个结点中，再设置一个指向其前驱结点的指针域。

4. 栈与队列

• 栈(stack)是限定仅在表尾进行捕入和删除操作的线性表。栈本身是线性表，所以同样有顺序存储(顺序栈)和链式存储(链栈)。
• 对于顺序存储的栈，两个栈可以共享空间，将两个栈的栈顶连通，两个栈将向中间靠拢。
• 栈的应用：递归、数学表达式求值（后缀表达式求值）、
• 队列(queue) 是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。同样也有顺序队列（采用循环队列）与链式队列。
• 栈与队列都是特殊的线性表，只不过对插入与删除进行了限制。

5. 串

• 串(string )是由零个或多个字符组成的有限序列，又名叫字符串。也可以顺序存储与链式存储。
• KMP模式匹配算法，把T串（目标串）各个位置的j 值的变化定义为一个数组next，next数组的值等于前缀最长公共子串长度加1，j=1时等于0（数组从1开始），其他情况等于1。
• KMP 算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势。主串下标不需要回溯，节约了时间。
• 改良的KMP算法，主要改进next，变成nextval。主要改进当前字符与之前字符相等的话就换成该位置对应的nextval。比next更近一步。具体的说，它是在计算出 next 值的同时，如果 a 位字符与它 next 值指向的 b位字符相等，则该 a 位的 nextval 就指向 b 位的 nextval 值，如果不等，则该a位的nextval值就是它自己a位的next的值。

6. 树

• 树用来表示一对多的逻辑关系。结点拥有的子树数称为结点的度(Degree)，树的度是树内各结点的度的最大值。
• 结点的子树的根称为该结点的孩子(Child) ，相应地，该结点称为孩子的双亲(Parent)。
• 同一个双亲的孩子之间直称兄弟 (Sibling)。
• 树中结点的最大层次称为树的深度 (Depth)或高度。

• 树的存储也可以用顺序存储结构(用下标表示逻辑关系)与链式存储结构或者两者结合，树的表示法包含：双亲表示法(节点加入双亲的关系)、孩子表示法、孩子兄弟表示法等等。
• 二叉树，二叉树( Binary Tree) 是 n(n>=O) 个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
• 特殊的二叉树，斜树（所有节点都只有一侧的子树）、满二叉树、完全二叉树。
  • 二叉搜索树：任何节点的键值一定大于左子树中的每一个节点键值，并小于等于右子树的每一个节点的键值。
  • 平衡二叉搜索树：在二叉搜索树基础上，保证没有任何一个节点过深。AVL—tree、RB-tree、AA-tree均可实现。
• 二叉树的顺序存储结构，由于定义的严格，数组的下标就能体现逻辑关系。如对于完全二叉树，i=1是根节点，2i是左孩子节点，2i+1是右孩子节点。二叉树的链式存储会更为方便。
• 二叉树的遍历，前序遍历（先左子树后右子树）、中序遍历（先中序遍历根节点的左子树，再根节点，最后中序遍历右子树）、后序遍历、图层遍历，一般采用递归实现。递归算法实现几乎一样，只是算法内部顺序不同，依次是前中后序。前三种遍历都是从根节点出发。

/*二叉树的前序遍历递归算法*/
void traverse(BitTree T)
{
    if(T==NULL)return;
    printf("%c",T->data);/*放在前面就是前序遍历，放在两递归中间就是中序，最后为后序遍历 */
    traverse(T->lchild);
    traverse(T->rchild);
} 

• 已知前序序列和中序序列可以唯一确定一颗二叉树，已知后序序列和中序序列也可以唯一确定一颗二叉树。
• 已知前序和后序遍历，是不能确定一棵二叉树的。
• 线索二叉树，由于对于一般有n个结点的二叉树，会有n+1个空指针，为充分利用空间，加上线索的二叉树即是线索二叉树。指向前驱和后继的指针称为线索。不过需要加入两个flag，判断指针是线索还是孩子结点。
• 线索二叉树的优点在于我们既可以从第一个结点起顺后继进行遍历，也可以从最后一个结点起顺前驱进行遍历。
• 通过设定一定的规则，可以将森林、树与二叉树进行相互转换。
• 哈夫曼树，带权路径长度WPL最小的二叉树称做赫夫曼树。
  1. 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称做路径长度，带权则乘上权值。
  2. 树的路径长度就是从树根到每一结点的路径长度之和，有权则乘上权值，称带权路径长度。
• 哈夫曼编码，目的是为了解决当年远距离通信(主要是电报)的数据传输的最优化问题。

7. 图

• 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G 表示一个图，V 是图G中顶点的集合，E是图G中边的集会。
• 无向边用小括号 “( )'” 表示，而有向边则是用尖括号”< >”表示
• 若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单圈。
• 在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
• 在有向图中，如果任意两个顶点之阅都存在方向互为相反的两条弧，则称该图为有向完全图。

• 与图的边或弧相关的数叫做权(Weight)，带权的图通常称为网(Network)。
• 以顶点v为头的弧的数自称为v的入度(InDegree)，记为ID(v); 以v为尾的弧的数目称为v的出度(OutDegree)，记为OD(v);顶点v的度为 TO(v)=ID(v)+OD(v)

• 无向图中的极大连通子图称为连通分量。在有向图中，若从VI到VJ和从VJ到VI都存在路径，则称图是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
• 图的存储结构
  1. 邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储圈中顶点信息，一个二维数组〈称为邻接矩阵)存储图中的边或弧的信息。可用普里姆算法遍历。
  2. 邻接表法，数组（顶点表）与链表（放邻接点）相结合的存储方法称为邻接表。适用于边数相对点数较小的图。对于有向图来说，邻接表是有缺陷的，关心了出度(邻接表)就必须遍历整个图才能知道入度（逆邻接表），反之亦然。
  3. 十字链表，一种有向图的存储方式。
  4. 邻接多重表，更关注边的操作。
  5. 边集数组，由两个一维数组构成，一个是存储顶点的信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标(begin)、终点下标(end)和权(weigbt) 组成。可用克鲁斯卡尔遍历。
• 图的遍历，从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
  1. 深度优先遍历DFS，其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次，类似树的前序遍历。深度优先更适合目标比较明确，以找到目标为主要目的的情况。
  2. 广度优先遍历BFS，类似树的层序遍历。两种遍历方式的时间复杂度是相同的。更适合在不断扩大遍历范围时找到相对最优解的情况。
• 最小生成树，我们把构造连通网的最小代价生成树称为最小生成树。
  1. 普里姆prim算法，以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树的。边数多效率好一些。
  2. 克鲁斯卡尔(Kruskal)算法，构建时要考虑是否会形成环路，主要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大的优势。
• 最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第 一个顶点是源点，最后一个顶点是终点。
  1. 迪杰斯特拉(Dijkstra)算法，是一个按路径长度递增的次序产生最短路径的算法。解决了从某个源点到其余各顶点的最短路径问题。时间复杂度O(\(n^2\))。
  2. 弗洛伊德(Floyd)算法，用于求所有顶点到所有顶点的的最短路径。二重循环始化加一个三重循环权值修正，就可以解决，代码十分简洁。
• 拓扑排序，是对一个有向图构造拓扑序列的过程。从AOV 网中选择一个人度为 0 的顶点输出，然后删去此顶点，井删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者 AOV 网中不存在入度为 0 的顶点为止。
• 关键路径，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动。

电子书pdf –《大话数据结构》 密码 0in1