0 数据结构与算法概述
2020-02-17 本文已影响0人
GoFuncChan
概述
在当今程序员的世界，算法已经成为衡量一名程序员水平高低的参照物。高深的程序员都会看重数据结构和算法的作用，水平越高，就越能理解算法的重要性。算法不仅仅是运算工具，它更是程序的“灵魂”。在现实项目开发过程中，很多实际问题需要精心设计的算法才能有效解决。对个人来讲，对算法的掌握也是区别于他人、保持竞争力的重要方面。
算法是计算机处理信息的本质，因为计算机程序本质上是一个算法，告诉计算机确切的步骤来执行一个指定的任务，如计算职工的薪水或打印学生的成绩单。一般地，当算法在处理信息时，数据会从输入设备读取，并写入输出设备，也可能保存起来供以后使用。
著名计算机科学家沃思提出了下面的公式：
数据结构+算法=程序
实际上，一个程序应当采用结构化程序设计方法进行程序设计，并且用某一种计算机语言来表示。因此，可以用下面的公式表示：
程序=算法+数据结构+程序设计方法+语言和环境
在上述公式的四个方面中，算法是“灵魂”，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法来解决“做什么”和“怎么做”的问题。
实际上程序中的操作语句就是算法的体现，所以说，不了解算法就谈不上程序设计。
数据是操作对象，对操作的描述即操作步骤，操作的目的是对数据进行加工处理得到期望的结果。
基本数据结构
事实上，在计算机中的数据物理机构只是无尽的0-1构成的内存空间，我们所说的程序数据结构，一般指数据逻辑结构，是为完成某种用途而设计的逻辑结构。
以下为基本的数据结构：
线性结构 （前驱:后继 1:1）
1.线性表
- 连续空间结构：字符串、数组
- 非连续空间结构：链表（单向、双向、环...）
2.栈（特殊线性表）：受限的线性表，一般用数组实现（也可以用链表实现，性能差不多），因为它只允许表头进入，表头弹出，顺序为先进后出；
- 顺序栈 —— 数组实现
- 链式栈—— 链表实现
3.队列（特殊线性表）：受限的线性表，一般由链表实现（也可以用数组实现，链表队列性能较高），因为它只允许表头进入表尾推出，顺序为先进先出；
- 顺序队列 —— 数组实现
- 链式队列 —— 链表实现
- 环形队列 —— 环形链表实现
广义表(Lists，又称列表)
广义表是一种非线性的数据结构。但如果广义表的每个元素都是原子,它就变成了线性表。
非线性结构
1.树 （前驱:后继 1:N）
- 分类
- 二叉树
- 二叉查找树
- 平衡查找树
- 赫夫曼树
- 红黑树
- B树
- B+树
- ...
- 实现结构：数组或链表
- 遍历方式：
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
2.图 （前驱:后继 M:N）
- 实现结构
- 邻接矩阵表示法——二维数组
- 邻接表表示法 —— 字典加数组
- 遍历方式
- 广度优先搜索
- 深度优先搜索
散列结构
- 哈希表:根据哈希算法
- 集合：一组无序、不能重复的元素构成，它是特殊的数组，常见实现形式也可以是哈希表。
基本算法
常用的基本算法分为排序算法，查找算法，分类算法，其他都是根据特定场景或算法思想而设计的算法，在基础篇中我们只讲排序，查找，分类等基本算法。
1.排序算法
- 交换类排序
- 冒泡排序
- 快速排序
- 选择类排序
- 直接选择排序
- 堆排序
- 插入类排序
- 直接插入排序
- 希尔排序
- 非比较类排序
- 计数排序
- 基数类排序
- 桶排序
- 基数排序
2.查找算法
- 顺序查找
- 分治类查找
- 二分查找
- 插值查找
- 斐波那契查找
- 树表查找
- 分块查找
- 哈希查找
3.分类算法
- k-近邻分类算法
- 决策树分类
- 贝叶斯分类
- 支持向量机
- 人工神经网络
