简明易懂的算法及数据结构

算法及数据结构数据结构算法与数据结构算法是对一系列数据进行处理，得到最终结果。一系列数据的组织形式，对算法的设计和实现有着很大的影响。数据结构一系列数据的组织形式学习一些重要的、常见的数据结构数据结构的分类线性结构数据是一个接着一个，数据间只有0或1个前置和0或1个后续常见的数据结构包括：数组、线性表、栈和队列非线性结构数据间的关系比较多样，数据间可以有0或多个前置和0或多个后续常见的数据结构包括：树和图数据结构的操作数据结构的操作对数据结构中那一系列数据进行管理的行为根本的操作添加数据删除数据修改数据遍历所有数据查找指定数据的位置或节点对于不同的数据结构，还有和它们自身相关的一些操作数据结构的实现形式数据结构的实现方法主要有两种使用数组实现的数据结构，称为“顺序实现〞使用引用特性实现的数据结构，称为“链式实现〞“链式〞数据结构的两局部数据结构的实现一般分为两局部数据节点〔Node〕：用来存放信息，包括：实际的数据引用相关数据节点〔Node〕的变量节点管理〔Manager〕：用来管理所有的数据节点，维护它们之间的引用关系数据结构的操作在节点管理里面实现命名，假设数据结构的名称为XXX数据节点：XXXNode节点管理：XXX“链式〞数据结构的图示我们会采用图示的方式来描述数据结构直观，便于讨论沟通数据节点

Node实际数据引用变量节点间的引用关系已存在或新建准备删除“链式〞数据结构图示的例如“你”Next“们”Next“好”Next“你”Next“们”Next“好”Next你们好你好“链式〞数据结构图示的例如“祖父”父亲儿子“伯父”父亲儿子“父亲”父亲儿子“叔叔”父亲儿子“表兄”父亲儿子“你”父亲儿子族谱线性表线性结构线性结构是数据有次序集合的一类数据结构特点：必然存在唯一的一个“第一元素〞必然存在唯一的一个“最后元素〞除最后元素外，均有唯一的后续除第一元素外，均有唯一的前驱线性结构的分类根据实现手段区分使用数组实现——顺序线性结构使用引用实现——链式线性结构根据线性结构中元素的访问限制无任何限制——线性表有访问限制——栈和队列线性表的操作——元素操作添加：Add在线性表最后添加元素插入：Insert在线性表中间指定的位置添加元素移除：RemoveAt把线性表中指定位置的元素从线性表中移去注意：被移除的元素只是在线性表中不存在，但并不没有消失替换：Replace替换线性表中指定位置的元素清空线性表：Clear把线性表中所有元素清空线性表的操作——元素信息获取：GetByIndex获取线性表中指定位置的元素从前查找：IndexOf从线性表中第一元素开始，获取符合条件的元素所在的位置从后查找：LastIndexOf从线性表中最后元素开始，获取符合条件的元素所在的位置获取数量：Count获取线性表中所有元素的数量数据结构的元素遍历获取当前元素：GetCurrent获取当前所指向的元素移动到下一个元素：MoveNext移动到下一个元素返回值为bool，如果有下一个元素，返回true，否那么，返回false。重置：Reset重新指向第一个元素单向链表LinkNodeLink双向链表DoubleLinkNodeDoubleLink单向循环链表LinkNodeLink算法与穷举法什么是算法算法对特定问题求解步骤的一种描述计算机算法使用计算机指令实现算法所描述的步骤，令到计算机解决特定的问题计算机算法的描述形式自然语言描述算法框图描述伪代码描述类似于编程代码，但忽略编程语言中一些严格的语法规那么与细节目的在于描述算法计算机算法的特性输入性有些算法好似没有输入量，实际上是输入量已被嵌入到算法中输出性有些算法好似没有输出结果，实际上是算法中已经对外部产生影响确定性相同的输入，得到的输出也是相同的有穷性算法在有限步骤下结束，每个步骤在有限时间内完成可行性算法能够被现有的计算机技术实现算法的优劣依据同一个问题，可能存在多种算法判断算法优劣标准正确性可读性易于人的阅读和理解健壮性具备检查错误和对错误进行适当处理的能力效率运行时间——时间复杂度内存占用——空间复杂度什么是穷举法逐一尝试所有可能的解利用计算机的高速度和不知疲倦的特性通过判断是否与条件矛盾来确定其是否为问题的解什么情况下适用穷举法对问题求解毫无头绪的情况下问题是可以必须预先确定可能解的个数，或可能解的取值范围穷举法较为费时穷举法步骤确定可能解的取值范围遍历所有可能解根据条件，判断该可能解是否符合题目要求穷举法例子1问题：求整数数组A[0:N-1]中的最小值。穷举法思路：解的范围就是数组中的所有元素假设其中一个是最小值用其他所有元素与“最小值〞比较，如果更新小，那么更换最小值穷举法例子2问题：有N个硬币，其中一个是假币。所有真币的重量一样，而假币与真币重量不一样。现有一个精确天平，但没有砝码。利用该天平找出假币。用整型数组表示所有硬币的重量，显示假币的位置，并说明假币比真币重还是轻。穷举法思路：解的范围就是数组中的所有硬币进行两两比较如果硬币重量一样，那么都是真币如果硬币重量不一样，那么其中一个是硬币。此时需要和其他组别的硬币比较，判断哪个是真币。注意N为奇数的情况穷举法例子3问题：密码组合。密码由26个英文字母组成，大小写不区分。长度可以是1-4个字符。显示所有可能的密码组合。提示：26个英文字母可以放在一个字符数组里面多个字符的情况可以使用多重循环穷举法例子4问题：众数查找。在一个由假设干元素组成的数组中，出现次数最多的元素称为众数。如果有多个元素的出现次数一样，第一个出现的元素才是众数。寻找元素是整数类型的数组中的众数。穷举法例子5问题：求满足如下两个性质的最小自然数n：a) n的个位数是6；b)假设将n的个位数移到其余各位数字之前，所得的新数是n的4倍。提示：该数值为：153846穷举法例子6问题：Ａ、Ｂ、Ｃ、Ｄ、Ｅ五名学生有可能参加计算机竞赛，根据以下条件判断哪些人参加了竞赛：

a) Ａ参加时，Ｂ也参加；

b) Ｂ和Ｃ只有一个人参加；

c) Ｃ和Ｄ或者都参加，或者都不参加；

d) Ｄ和Ｅ中至少有一个人参加；

e) 如果Ｅ参加，那么Ａ和Ｄ也都参加。提示：参加的情况是：A=False,B=False,C=True,D=True,E=False滚雪球法什么是滚雪球法也称为迭代法——数学求解对一个的根底解，经过有限次的加工处理，令根底解变为最终解。什么情况下适用滚雪球法可以从问题中，确定一个根底解令根底解转变为最终解的一系列加工处理方法，可以重复进行加工处理方式是确定的加工处理的次数是确定的滚雪球法步骤确定一个根底解重复进行加工处理根据情况，选择适宜的加工处理的方法把〔加工后〕根底解作为加工处理方法的输入加工处理方法输出新的加工后根底解加工完成加工后的根底解就是最终解加工次数到达界限滚雪球例子1问题：猴子第一天摘下假设干桃子，当即吃下一半多一个。以后每天都吃前一天剩下的一半多一个。经过N天，只剩下1个桃子。问猴子第一天所摘桃子的数量。滚雪球法思路：根底解是怎样的加工的步骤如何滚雪球例子2问题：如果一对兔子每月里能生出一对小兔〔一雌一雄〕，而每对小兔在它们出生后的第三个月里，又能生出一对小兔。假定不发生死亡的情况下，由一对初生的小兔开始，n个月后会有多少对兔子？滚雪球法思路：根底解是怎样的加工的步骤如何递归法什么是递归法递归方法直接或间接调用自身相似问题结构相同但规模不一样的问题什么情况下适用递归法可以从题目中，把原问题转化为对相似问题的调用可以从题目中，找出能获取根底解的相似问题的规模递归法的两个过程递推：问题分解，直至能获取根底解回归：根底解构成最终解递归法步骤确定根底解获取的条件构造相似问题的算法输入——不同规模问题的输入量不一样对输入做相似的处理调用自身，设置新的输入对自身调用后的输出，做进一步加工输出调用算法，使用最大规模的输入量递归例子1问题：如果一对兔子每月里能生出一对小兔〔一雌一雄〕，而每对小兔在它们出生后的第三个月里，又能生出一对小兔。假定不发生死亡的情况下，由一对初生的小兔开始，n个月后会有多少对兔子？递归法思路：根底解是怎样的相似问题的处理：本月的数量=上月的数量+新出生的数量=上月的数量+上月三月大的数量+上月二月大的数量=上月的数量+(上上月三月大+上上月二月大〕的数量+上上月初生的数量=上月的数量+上上月的数量递归例子2问题：有三个柱子，柱A上有m个大小不一的盘子，并且小盘子在大盘子上面，现要求将盘子从A柱上，利用B柱，全部移到C柱。要求：小盘子在任何时候都必须在大盘子上面。〔汉诺塔问题〕递归法思路：根底解是怎样的相似问题的处理步骤分治法什么是分治法相似问题结构相同但规模不一样的问题对原问题分解为多个小规模问题小规模问题的解合并后得出最终解小规模问题可以递归求解什么情况下适用分治法可以从题目中，把原问题分解为多个相似问题的求解可以从题目中，找出能获取根底解的相似问题的规模分治法是对递归法的扩展递归法：原问题缩小为一个小规模问题分治法：原问题分解为多个小规模问题分治法步骤确定根底解获取的条件分解问题为多个小问题解决每个小问题，如果不能直接解决，那么进行递归求解合并所有小问题的解分治法例子1