大话数据结构(读书笔记)

数据结构

什么是数据结构

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

说白了就是数据的集合、但是集合里面的数据之间存在特地的关系(这翻译得好像没说一样)

数据结构的逻辑结构

是指数据元素之间的相互关系

• 集合结构：集合中的数据元素除了同属一个集合外、它们之间没有其他关系。

  

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

  

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

  

• 图形结构：图形结构的数据元素是多对多的关系

  

数据结构的物理结构

指数据的逻辑结构在计算机存储形式

• 顺序存储结构：是把数据元素存放在地址连续的存储单元里、其数据间的逻辑关系和物理关系是一致的
• 链式存储结构：是把数据元素存放在任意的存储单元、这组存储单元可以是连续的、也可以是不连续的

数据类型

数据类型指的是一组性质相同的值的集合以及定义在此集合上的一些操作的总称

数据类型可以分为两类

• 原子类型：是不可以再分解的基本类型、包括整型、浮点型、字符
• 结构类型：由若干个类型组合而成、是可以再分解的、比如整型数组是由若干个整型数据组成的

算法

什么是算法

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

算法的特性

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

• 算法具有零个或多个输入、算法至少有一个或多个输出、算法是一定需要输出的、不需要输出、要你这个算法干嘛
• 有穷性：指算法执行有限的步骤之后、自动结束而不会出现无限循环、并且每一个步骤在可接受的时间内完成。
• 确定性：算法的每一步都具有明确的含义、不会出现二义性。相同的输入只能有唯一的输出结果
• 可行性：算法的每一步都必须是可行的、也就是说、每一步都能够通过执行有限次数来完成

算法设计的要求

• 正确性
• 可读性
• 健壮性
• 时间效率高、存储量低

算法的时间复杂度

在进行算法分析时、语句总的执行次数 T(n) 是关于问题规模 n 的函数、进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。

算法的时间复杂度、也就是算法的时间量度、记作 T(n) = O(f(n))、他表示随问题规模 n 的增大、算法执行时间的增长率和 f(n) 的增长率相同。其中 f(n) 是问题规模 n 的某个函数。

使用大写 O() 来体现算法的时间复杂度记法。

一般情况下、随着 n 的增大、T(n) 增长最慢的算法称为最优算法

O(1) 常数阶、O(n)线性阶、O(n^2)平方阶、O(logn)对数阶

常见的时间复杂度

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

• 常数阶
• 对数阶
• 线性阶
• 平方阶
• 指数阶
• 阶乘阶

最坏情况与平均情况

最坏情况运行时间是一种保证、那就是运行时间将不会再坏了。这是一种最重要的需求、通常、除非特别制定、我们提到的运行时间都是最坏情况的运行时间

平均运行时间是所有情况中最油意义的、因为他是期望运行时间。

算法空间复杂度

算法的空间复杂度通过计算算法所需的存储空间实现、算法空间复杂度的计算公式记住:S(n)=O(f(n)) 。其中 n 为问题的规模，f(n)为语句关于n所存储空间的函数。

线性表

零个或多个数据元素的有限序列

首先 它是一个序列、也就是说元素之间是有顺序的、若元素存在多个、则第一个元素无前驱、最后一个元素无后继，其他每个元素都有且仅有一个前驱和一个后继。线性表强调的另一个点是有限。

线性表的顺序存储结构

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

优缺点

• 随机访问
• 无须为表示表中之间的逻辑关系而增加额外的存储空间
• 插入和删除元素需要移动大量的对象
• 当线性表长度变化比较大的时候、难以确定存储空间的大小
• 造成空间的碎片

线性表的链式存储结构

对单链表结构和顺序存储结构做对比

• 存储分配方式
  • 顺序存储结构是使用一段连续对存储单元一次存储线性表的数据元素的
  • 单链表采用链式存储结构、用一组任意的存储单元存放线性表的元素
• 查找
  • 顺序存储结构O(1)
  • 单链表O(n)
• 插入和删除
  • 顺序存储结构需要平均移动表长一半的元素、时间为O(n)
  • 单链表在找出某位置之后、插入和删除时间仅为O(1)
• 空间性能
  • 顺序存储结构、预分配、大了浪费、小了发生溢出
  • 单链表不需要预分配、元素个数不受限制

栈和队列

栈是限定仅在表尾进行插入和删除操作的线性表

队列是只允许在一端进行插入操作、而在另一端进行删除操作的线性表

栈

首先它是一个线性表、也就是说、栈元素具有线性关系、即前驱后继关系、只不过它是一种特殊的线性表而已。定义中说在线性表的表尾进行插入和删除的操作、这里的表尾是只栈顶、而不是栈底。

栈的应用-递归

直接或间接的调用函数自己本身。

递归出口：没过递归定义必须至少有一个条件、满足时递归不再进行，即不再引用自身而是返回值推出。

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

一种不需要括号的后缀表达法、我们也可以把它称为逆波兰。后缀表达式就是所有的符号都是在要运算数字的后面出现。

队列

线性表有顺序存储、栈是线性表、所以有这两种存储方式。同样队列作为一种特殊的线性表，也同样存在这两种存储方式。

循环队列

解决假溢出的办法就是后面满了、就再从头开始、也就是头尾相接的循环、我们把这种头尾相接的顺序存储结构称为循环队列。

串

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

KMP

KMP 模式匹配算法就是为了不必要的回溯不会发生

树

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

• 有且仅有一个特定的称为根的结点
• 当n>1时、其余节点可分为m(m>0)个互不相交的有限集 T1、T2、T3。其中每个集合本身又是一棵树、并且称为根的子树

结点分类

结点拥有的子树数称为结点的度。度为0度结点称为页结点或终端结点。度不为0的结点称为非终端结点。

除根结点外、分支结点也称为内部结点

树的度是树内部各结点的度的最大值

结点间关系

结点的子树称为该结点的孩子、相应地、该结点称为孩子的双亲。

树的其他概念

结点的层次、从根开始定义起、根为第一层、根的孩子喂第二层。

树中结点的最大层次称为树的深度

如果将树中结点的各子树看成从左至右是有次序的、不能互换的、则称该树为有序树、否则称为无序树。

森林是m棵互不相交的树的集合。

二叉树

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

二叉树的特点

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

特殊二叉树

• 斜树

  所有结点都只有左子树的二叉树叫做左斜树。所有结点只有右子树的二叉树叫右斜树。这两者统称为斜树

• 满二叉树

  在一棵二叉树中、如果所有分支结点都存在左子树和右子树、并且所有叶子都在同一层上、这样的二叉树称为满二叉树

• 完全二叉树

  对于一棵具有 n 个结点的二叉树按层序编号、如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中的位置完全、那么这棵二叉树称为完全二叉树。

  • 叶子结点只能出现在最下两层
  • 最下层的叶子一定集中在左部连续位置
  • 倒数第二层、如果有叶子结点、一定是在右部连续位置
  • 如果结点度为1、则该结点只有左子树、不存在只有右子树的情况
  • 同样结点数的二叉树、完全二叉树深度最少

二叉树性质

• 在二叉树的第i层上至多有2^(i-1)个结点
• 深度为k的二叉树至多有2^k - 1 个结点

遍历二叉树

二叉树的遍历是指从根结点出发、按照某种次序依次访问二叉树中所有结点、使得每个结点被访问一次且仅被访问一次。

• 前序遍历

  二叉树为空、则空操作返回、否则先访问根结点，然后前序遍历左子树、再前序遍历右子树。

• 中序遍历

  二叉树为空、则空操作返回、否则从根结点开始(注意并不是先访问根结点)、中序遍历根结点的左子树、然后访问根结点、最好中序遍历右子树

• 后序遍历

  二叉树为空、则空操作返回、否则从左到右先叶子后结点的方式遍历访问左右子树、最后访问根结点

• 层序遍历

  二叉树为空、则空操作返回、否则从树的第一层、也就是根结点开始访问、从上到下逐层遍历、在同一层中从左到右顺序对结点进行访问

图

图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为 G(V,E)。其中 G 表示一个图、V 是图G中顶点的集合、E是图G中边的集合。

深度优先遍历

也称为深度优先搜索、简称 DFS

它从图中某个顶点 v 出发、访问此顶点、然后从 v 的未被访问的邻接点出发深度优先遍历图、直至图中所有和 v 有路径相同的顶点都被访问到。

广度优先遍历

又称为广度优先搜索、简称 BFS

类似于树的层序遍历。

最小生成树

我们把构造连通网的最小代价生成树称为最小生成树。

• Prim 普里姆算法
• Kruskal 克鲁斯卡尔算法

最短路径

对于网图来说、最短路径、是指两顶点之间经过的边上权值之和最少的路径、并且我们称路径上的第一个顶点时源点、最后一个顶点是终点。

• Dijkstra 算法
• Flody 算法

查找

查找就是根据给定的某个值、在查找表中确定一个其关键字等于给定值的元素。

顺序查找

又叫线性查找、是最基本的查找技术、它的查找过程是：从表中的第一个记录开始、逐个进行记录关键字和给定值比较、若某个记录的关键字和给定值相等、则查找成功、找到所查找的记录、如果直到最后一个记录、其关键字和给定值比较都不等时、则代表表中没有所查找的记录。

有序表查找

折半查找

折半查找又称为二分查找、它的前提是线性表中的记录必须是关键码有序的、线性表必须采用顺序存储。折半查找的基本思想是：在有序表中、取中间记录作为比较对象、若给定值与中间记录的关键字相等、则查找成功、若给定值小于中间记录的关键字、则在中间记录的左半区继续查找、若给定值大于中间记录的关键字、则在中间记录的右半区继续查找。不断重复上诉过程、直到查找成功或者查找区域无记录。

插值查找

插值查找是根据要查找的关键字 key 与查找表中最大最小记录的关键字比较后的查找方法、其核心在于插值的计算公式 key-a[low] / a[high]-a[low]

斐波那契查找

线性索引查找

数据结构的最终目的是提高数据的处理速度、索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程。

索引按照结构可以分为线性索引、树形索引和多级索引。

所谓的线性索引就是将索引项集合组织为线性结构、也称为索引表。

线性索引可以分为稠密索引、分块索引、倒排索引。

稠密索引

稠密索引是指在线性索引中、将数据集中的每个记录对应一个索引项。

对于稠密索引这个索引表来说、索引项一定是按照关键码有序排列的

稠密索引的个数等于数据集记录的个数

分块索引

是把数据集的记录分成若干块、并且这些块需要满足两个条件

• 块内无序
• 块间有序

倒排索引

将单词或记录作为索引、将文档id作为记录、这样便可以方便地通过单词或记录查找到其所在的文档。

二叉查找树

• 若它的左子树不空、则左子树上所有结点的值均小于它的根结点的值
• 若它的右子树不空、则右子树上所有结点的值均大于它的根结点的值
• 它的左右子树也分别为二叉排序树

构造一棵二叉排序树的目的、并不是为了排序、而是为了提高查找和插入删除关键字的速度

平衡二叉树

平衡二叉树是一种二叉排序树、其中每个结点的左子树和右子树的高度差至多等于 1。

将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子。值只有-1、0、1

多路查找树

多路查找树其每一个结点的孩子数可以躲雨两个、且每个结点处可以存储多个元素。

B树

B 树是一种平衡的多路查找树

左侧灰色方块表示当前结点的元素个数。

B+树

哈希表

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系f、使得每个关键字 key 对应一个存储位置 f

解决哈希冲突

• 开放定址法
• 再散列函数法
• 链地址法
• 公共溢出区法

排序

• 交换排序

  • 冒泡排序
  • 快速排序

• 插入排序

  • 直接插入排序
  • 希尔排序

• 选择排序

  • 简单选择排序
  • 堆排序

• 归并排序

• 基数排序