算法与数据结构.docxVIP

算法与数据结构 算法与数据结构的关系： 数据结构是算法的基础，没有数据结构就没有算法 数据结构 所有的数据结构，本质上都是图 线性 栈 举例：汉诺塔 后入先出(last in first out) 可用于深度优先 从某节点开始对图进行探索 该节点有无标记？ 有 将其栈出并记录 无 该节点有无非标记相邻节点？ 有 将该节点进行标记，并将其相邻节点(非标记过)栈入 无 将该节点标记并栈出，记录 队列 可用于广度优先 先将起始点放入队首，将该点排出并读取，之后将其子节点放入队列中，如此一直进行下去，直至队列为空 非线性 图 树(不含环的图) 二叉树 排序二叉树 特点 左边的节点大于其父节点，右边的则小于，或相反 分左右 平衡二叉树 任意两叶节点的深度相差不超过一 此树实现各种算法效率比较高 非树(含环的图) 有向图 表现形式 n阶方阵 与线性代数有关 n为图中的节点数 无向图 无向图本质上是两个方向必互通的有向图 表现形式 对称矩阵 探索方法 两种 bfs(广度优先) dfs(深度优先) 对树进行探索的时候也是如此 算法 查找 字符串查找 常用方法 Bruce算法 名称来源 Bruce意味着粗鲁的 策略 将要查找的模式串与母串从第一个字符开始比对 相同 刚刚子串不是最后一个字符 母串刚刚比较完最后一个字符 是 查找失败 否 继续下一个字符的比较 刚刚子串已比较完最后一个字符 字串开头的位置即为结果 不同 模式串头部移动到母串的下一个字符，重新比较 KMP算法 名称来源 三位提出者的名字的首字母 内容关键 对每个模式串内部进行分析，以使分析变为“跃进”式 过程 一、分析字串 得到一张表 内容 一、字串有多长，就有多少条目 二、每个条目后写有当该字符(键)比对出错时，该子串应调整到第(值)个。 来源 递归方法得出 当一个条目得出之后 该条目后一个字符若与前一个串的重合串的后一个字符相同 直接加一 若不同 把前一个串的重合串的内部进行递归，直至相同 定义 查找一个字符串从左到右第一次符合某种排列的串时(即模式串)，该字符串开头的位置 排序 定义 把系列可按某属性比较的数据按该属性排列 堆排序 堆的定义 特殊的树 冒泡排序 高德纳：冒泡排序美但无用 类似：递归 并非无用 用之有度 用在合适的地方 特点 优点：易理解，简单 缺点：效率低下，时间复杂度为o(n^2) 过程 一、输入要排序的n个数 二、循环(n-1)次 三、第i次循环时，从第一个数开始，到第n-i个数，将该数与其后一个数进行比较，如次序不对，进行交换。 代码 def maopao(a): for i in range(Len(a)-1): for j in range(Len(a)-i-1): if(a[j]a[j+1]): temp=a[j] a[j]=a[j+1] a[j+1]=temp 逆序数 来源 行列式定义 排序过程中 交换次数 奇数 负数 偶数 正数 例子：本就无需排列的数，交换零次 快速排序 本质 两数据交换时，不像冒泡排序一次相邻两个数交换，可以实现两个相邻很多格的数进行交换 先设定一个数然后把比该数大的放右边，比该数小的放左边，然后对该数左右两串数继续此操作，直至串的长度为零