# algorithm **Repository Path**: souls/algorithm ## Basic Information - **Project Name**: algorithm - **Description**: 算法、数据结构 - **Primary Language**: Java - **License**: Not specified - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2019-10-31 - **Last Updated**: 2022-09-18 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # algorithm Souls Alex ## 介绍 算法 ( java、php、c ) ## 说明 一个有穷规则的集合，起规则确定一个解决某一特定类型问题的操作序列。 ## 特性 1. 输入-算法有零个或多个输入数据； 2. 输出-算法有一个或多个输出数据，与输入数据有某种特定的关系； 3. 有穷性-算法必须在执行有穷步之后结束； 4. 确定性-算法的每个步骤必须含义明确无二义性； 5. 可行性-算法的每步操作必须是基本的，它们原则上都能够精确的进行，做有穷次就可以完成。 ## 使用说明 > 算法建立在数据结构之上，对数据结构的操作需要算法来描述； * 线性表有遍历、插入、删除、查找、排序等操作 * 树有遍历、插入、删除、查找、排序等操作 > 算法设计依赖数据的逻辑结构，算法实现依赖数据的存储结构 * 线性表的插入和删除操作，采用顺序存储结构，由于数据元素都是相邻存储的，所以添、删必须移动一些元素； * 链式存储结构，插入或删除一个元素，只需要改变相关结点的链接关系，无需移动元素。 > 综合性能最佳 * 数据操作所花费的时间短 * 占用存储空间少 * 不频繁增删的，可采用顺序存储结构；否则采用链式存储结构 ## 设计目标 1. 正确性：确切的满足应用问题的需求，这是基本 2. 健壮性：即使输入数据不合适，算法也能做出适当的处理，不会不可控 3. 高效时间效率：执行时间越短，执行效率越高 4. 高空间效率：执行占用空间越少，空间效率越高 5. 可读性：有利于人们的理解 ## 补充知识点 > 素数、质数、合数 * 质数又称素数。一个大于1的自然数，除了1和自身外，不能被其他自然数整除的数;否则称为合数. * 定理： 1. 在一个大于1的数a和它的2倍这间（即区间(a,2a]中）必存在至少一个素数 2. 存在任意长度的素数等差数列 3. 一个偶数可以写成两个合数之和，其中每一个合数都最多只有9个质因数 4. 一个偶数必定可以写成一个质数加上一个合成数，其中合数的因子个数有上界 5. 一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 （1 + 5） 6. 一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 （1 + 2） * 判断思路，对正整数n,如果用2到sqrt(根)之间的所有整数去除，均无法整除，则n为质数;质数大于等于2 不能被它本身和1以外的数整除 * 总结： 1不是质数，大于2，能被2整除也是不是质数，去掉偶数后，从 3 到 x-1, 每次加 2(只需到 sqrt(x) 即可以) ```$xslt public static boolean isPrime(int n){ if (n <= 3) { return n > 1; } for(int i=2;i<=Math.sqrt(n);i++){ if(n%i == 0) return false; } return true; } ``` > 等差数列 ? ## 算法分析 > 时间效率 * 顺序(O(n))： 1 < log2n < n < nlog2n < n*n > 空间效率 * S(n) ## 线性表 * 具有线性关系的一种线性结构。基本操作如：插入、删除、查找、替换。 * 可以采用顺序存储和链式存储结构表示。 * 顺序存储->约瑟夫(Josephus)环问题(Josephus.java) ## 栈和队列 * 特殊的线性表 * 若插入和删除操作只允许在线性表的一端进行，则为栈,特点，后进先出。(Last In First Out) * 若插入和删除操作分别在线性的两端进行，则为队列，特点，先进先出。（First In First Out） > 栈实现 * 顺序栈类 * 链式栈 * 判断括号匹配的算法 > 队列及实现 * 是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。 * 入队(enqueue),出队(dequeue),队尾(rear),队头(front) * 顺序循环队列 * 链式队列 * 求解素数的问题 ## 串 * 串有两种存储结构：顺序(依次)和链式(单字符链表和块名链表) * 串抽象 * 字符串常量类String,字符串变量类StringBuffer,都采用顺序存储 * 模式匹配分为朴素的模式匹配Brute-Force算法和无回溯的模式匹配KMP算法 * Brute-Force:依次与主字符串匹配，直到完全匹配则完成 * KMP：分解模式串的方式（有多个相同的前缀和后缀时）,在BF基础上增加位移 ## 数组和广义表 * 数组是一种数据结构，元素具有相同的数据类型。 * 线性表，顺序存储 * 压缩存储原则：多个重复元素只存储一份；不存储零元素。 * 对称矩阵、三角矩阵、稀疏矩阵压缩存储 * 广义表，是复杂的数据结构，它是线性表的扩展，能够表示树结构和图结构。 * 广义表，应用在文本处理，人工智能和计算机图形学等领域有着广泛的应用 ## 树和二叉树 > 树 * 树是数据元素（结点）之间具有层次关系的非线性结构 * 大多数使用链式存储结构和递归算法 > 二叉树 (binary tree) * 是n(n>=0)个结点组成的有限集合 *　分为左子树和右子树，也是递归定义的 * 基本形态： 1. 空二叉树 2. 只有一个结点的二叉树 3. 由根结占为、非空的左子树和右子树组成的二叉树 4. 由根结点、空的左子树和非空的右子树组成的二叉树 5. 由根结点、非空的左子树和空的右子树组成的二叉树 * 主要采用链式存储,顺序存储仅适用于完成二叉树和满二叉树，还有一种静态链表 * 满二叉树,结点数 = n=2^k-1,k表示深度（层数） * 完全二叉树，若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边 > 二叉树的三种次序遍历 * 先根次序，访问根结点，遍历左子树，遍历右子树； * 中根次序，遍历左子树，访问根结点，遍历右子树； * 后根次序，遍历左子树，遍历右子树，访问根结点； > 线索二叉树 * 对一棵二叉树进行遍历操作，所访问的结点构成一个线性序列，（该结点的前驱结点和后继结点） * 线索二叉树利用空链存储结点在某种遍历次序下的前驱和后续关系。即原有非空的链保持不变，仍然指向该结点的左右孩子结点; * 使空的left链指向前驱结点，空的right链指向后继结点。 * 指向前驱和后继结点的链称为线索。 * 对二叉树以某种次序进行遍历并加上线索的过程称为线索化。 > 哈夫曼编码与哈夫曼树 * 哈夫曼编码（Huffman code）是数据压缩技术中的一种无损压缩方法 * 哈夫曼编码实现步骤如下： 1. 统计原始数据中各信源符号出现的频率，按频率高低的次序排列 2. 将两个最小的频率相加，作为新的信源符号的频率 3. 重复上两步，直到和为1，在每次合并信源符号时，将合并的信源符号分别同赋0或1 4. 寻找从频率为1处到每一信源符号的路径，记录下路径上的1和0，保证信源由最短的编码组成，实现压缩 > 树的表示 * 树的存储有多种，如：孩子链表，孩子兄弟链表等 * 森林也可以转为一颗二叉树存储，转化过程如下： 1. 将每棵树转为二叉树 2. 有根的兄弟链将若干棵二叉树 * 树的遍历主要由先根遍历和后根遍历 * 树的先根遍历算法如下： 1. 访问根结点 2. 按照从左到右的次序先根遍历根的每一棵子树 * 树的后根遍历算法如下： 1. 按照从左到右的次序后根遍历根的每一棵子树 2. 访问根结点 > 相关实现 * 输出二叉树指定结点的所有祖先结点(Ancestors类中实现) * 建立二叉链表表示的完全二叉树(CompleteBinaryTree) * 哈夫曼树 ## 图（graph） * 图是一种数据元素之间具有多对多关系的非线性数据结构 * 每个元素可有多个前驱元素和多个后继元素，任意两个元素都可以相邻 * 刻画离散结构的一种有力工具 > 基本概念 * 图是由顶点（vertex）集合及顶点间的关系集合组成的一种数据结构 * 顶点之间的关系称为边（edge） * 一个图G记为G=(V,E),V是顶点A的有限集合，E是边的有限集合 * 无向图(undirected graph) * 有向图(directed graph) * 完全图(complete graph) * 带权图（wighted graph）：图中的边具有权值（weight），在不同的应用中，权值有不同的含义 * 邻接顶点(adjacent vertex) * 顶点的度(degree):指与顶点A关联的边数，记为deg（A）. * 悬挂点（pendant node）：度为1的顶点 * 入度：在有向图中，以A为终点的边数称为A的入度（indeg(A）) * 出度：以A为起点的边数称为出度（outdeg(A）) * 终端顶点：出度为0的顶点 * 顶点的度是入度和出度之和。deg(A) = indeg(A)+outdeg(A) * 子图 * 路径 * 连通性 * 邻接矩阵（adjacency matrix）：表示图中各顶点这间邻接关系的矩阵 * 邻接表（adjacency list）:采用单链表存储与一个顶点相关联的多条边信息。由顶点表和边表组成【未实现】 * 图的遍历->图的深度优先搜索遍历，图的广度优先搜索遍历【未实现】 * 树：连通的无回路的无向图，简称树(tree) * 树叶：树中的悬挂点(leaf) * 分支点:树的其他顶点（branched node） * 森林:各连通分量均为树的图称为森林(forest) * 最小生成树【未实现】(Prim算法、Kruskal算法) * 最短路径【未实现】(Dijkstra算法) ## 查找 （Search） *　如何有效的组织数据，如何根据数据结构的特点快速、高效的茆以检索结果是核心问题 ### 基于线性查找 * 主要有顺序查找、折半查找和分块查找，适用于线性表、有序顺序表和索引顺序表三种结构。 > 顺序查找(sequential search) * 从表的端，依次将每个元素的关键字与给定值进行比较。又称线性查找（linear search） * 用于数据量小的线性表 > 折半查找（binary search） * 对于已排序的顺序表,使查找范围缩小一半，从而提高了查找效率，也称二分查找 * 用于数据量小的线性表 > 基于索引顺序表的分块查找 * 对数据量较大的顺序表，建立索引（index）是一种有效的分治策略 * 以空间换时间 * 字典公提供查找操作，不提供插入和删除操作 * 字典的所有元素预先全部排序以节省查找时间；同时建立多级索引和完全索引，以空间换时间的措施，得到更高的效率 * 完全索引：如果索引表保存所有元素的索引信息，效率（O1） * 多索引结构：完全索引数据量较大，可以基础上，再做一级索引 * 分块查找：基于索引表的查找算法（blocking search）.步骤如下： ``` 1. 查找索引表，获得给定值的索引信息，确定在哪一块中，缩小查找范围 2. 在一块中，根据给定的值进行查找操作，获取结果 ``` ### 树结构的查找 > 二叉排序树(binary sort tree)及查找 * 每个结点都有一个作为查找依据的关键字，所有结点的关键字互不相同 * 基一个结点的左子树不空，则左子树上所有结点的关键字均小于这个结点的关键字；若一个结点的右子树不空，则右子树上所有结点的关键字均大于这个结点的关键字。 * 每个结点的左子树、右子树也分别为二叉排序树 ```text 对二叉排序树按中根次序遍历，得到按升序排列的关键字。 二叉排序树的操作主要有查找、插入和删除。 ``` * 在一棵二叉排序树中，查找值为value的结点，算法描述如下： ```text 1. 从根结点开始，设P指向根结点； 2. 将value与P结点的关键字比较，相等则成功； 若小，则p在左子树中找； 若大，则在右子树中找。 3. 重复执行上一步，直到成功或是p为空。为空则不成功 ``` * 插入和删除操作主要是查询操作,效率主要由查找决定 * 提高二叉树查找效率的办法是尽量降低二叉排序树的高度 ### 平衡二叉树(balanced binary tree),即AVL树 > 定义 * 具有下列性质的二叉排序树： ```text 1. 它的左子树和右子树都是平衡二叉树 2. 左子树和右子树的高度之差的绝对值不超过1 ``` * 平衡因子(balance factor):一个结点其右子树与左子树的高度之差。 * 插入或删除一个结点可能破坏二叉树的平衡性，因此插入或删除都需要调整二叉树，使之保持平衡 ### 散列(hash) * 散列是一种按关键字编址的存储和检索方法 * 散列函数:在数据元素的关键字和该元素的存储位置之间建立一种对应关系，将这种关系称之为hash function. * 散列表：由散列函数决定元素存储位置的存储结构称为hash table. * 散列地址：i=hash(key),其中，i就是该元素在散列表中的春出位置，因此hash(key)也称为散列地址。 ### 排序(sorting) * 是对数据序列中的元素按照指定关键字的某种次序进行重新排列的过程 * 直接插入排序 * 折半插入排序 * 希尔排序（shell sort）,又称缩小增量排序。思路：分组的直接插入排序,该算法不稳定 * 冒泡排序(bubble sort),比较相邻两个元素的关键字值 * 快速排序(quick sort),在数据数据列中选择一个值作为基准，将小的放在前端，大的放后端，在对子穿进行同样方式的排序。 * 直接选择排序(straight select sort),每次都选出最大或最下的元素放入最大或最小位置。顺序表或单/双链表实现 * 堆排序(heap sort),是完全二叉树的应用，充分利用完全二叉树的特性进行选择排序。根节点最小就是最小堆，否则最大 * 归并排序（merge sort），将两个已排序的子序列合并，形成一个有序数据序列，又称两路归并排序。第一次2个比较，第二次4个比较 > 思路 * 将非有序数据整理为有序的数据，再用折半法查找指定元素 ## 资料 1. 数据结构（Java版）第二版 电子工业出版社 （叶核亚、陈本林）