一、什么是数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。

1、最常用的、最基础的数据结构

Tips ：后面会详细学习记录每一种数据结构，这里只做概念的解释

数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树

• (1)数组

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。
数组可以说是最基本的数据结构，在各种编程语言中都有对应。

一个数组可以分解为多个数组元素，按照数据元素的类型，
数组可以分为整型数组、字符型数组、浮点型数组、指针数组和结构数组等。

数组还可以有一维、二维以及多维等表现形式。

• (2)链表

链表是一种数据元素按照链式存储结构进行存储的数据结构，
这种存储结构具有在物理上存在非连续的特点。

链表由一系列数据结点构成，每个数据结点包括数据域和指针域两部分。

其中，指针域保存了数据结构中下一个元素存放的地址。
链表结构中数据元素的逻辑顺序是通过链表中的指针链接次序来实现的。

• (3)栈

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

栈按照后进先出的原则来存储数据，也就是说，先插入的数据将被压入栈底，
最后插入的数据在栈顶，读出数据时，从栈顶开始逐个读出。

栈在汇编语言程序中，经常用于重要数据的现场保护。

栈中没有数据时，称为空栈。

• (4)队列

队列和栈类似，也是一种特殊的线性表。
和栈不同的是，队列只允许在表的一端进行插入操作，而在另一端进行删除操作。
一般来说，进行插入操作的一端称为队尾，进行删除操作的一端称为队头。

队列中没有元素时，称为空队列。

• (5)散列表

散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，
那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

• (6)二叉树

二叉树是每个结点最多有两个子树的树结构。
树是典型的非线性结构，它是包括，2个结点的有穷集合K。
在树结构中，有且仅有一个根结点，该结点没有前驱结点。
在树结构中的其他结点都有且仅有一个前驱结点，而且可以有两个后继结点，m≥0。

• (7)堆

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。
堆的特点是根结点的值是所有结点中最小的或者最大的，并且根结点的两个子树也是一个堆结构。

• (8)跳表

增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。

跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。

跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。

跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。

• (9)图

图是另一种非线性数据结构。在图结构中，数据结点一般称为顶点，而边是顶点的有序偶对。
如果两个顶点之间存在一条边，那么就表示这两个顶点具有相邻关系。

• (10)字典树

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。

典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），
所以经常被搜索引擎系统用于文本词频统计。

它的优点是：
利用字符串的公共前缀来减少查询时间，
最大限度地减少无谓的字符串比较，查询效率比哈希树高。

二、什么是算法

定义：为解决一个问题而采取的方法和步骤，就称为“算法”。

特征：一个算法应该具有以下五个重要的特征

• 有穷性（Finiteness）

算法的有穷性是指算法必须能在执行有限个步骤之后终止。

• 确切性(Definiteness)

算法的每一步骤必须有确切的定义。

• 输入项(Input)

一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。

• 输出项(Output)

一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。

• 可行性(Effectiveness)

算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

1、最常用的算法

递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法

• (1)递归

程序调用自身的编程技巧称为递归。
递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

• (2)排序

排序算法，即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。

常见的排序算法：插入排序、冒泡排序、选择排序、快速排序、归并排序

• (3)二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。
但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

• (4)搜索

搜索算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，
从而求出问题的解的一种方法。
现阶段一般有枚举算法、深度优先搜索、广度优先搜索、A*算法、
回溯算法、蒙特卡洛树搜索、散列函数等算法。

• (5)哈希算法

安全散列算法（英语：Secure Hash Algorithm，缩写为SHA）是一个密码散列函数家族，
是FIPS所认证的安全散列算法。
能计算出一个数字消息所对应到的，长度固定的字符串（又称消息摘要）的算法。
且若输入的消息不同，它们对应到不同字符串的机率很高。

• (6)贪心算法

贪心算法是一种对某些求最优解问题的更简单、更迅速的设计技术。
它采用自顶向下,以迭代的方法做出相继的贪心选择,
每做一次贪心选择就将所求问题简化为一个规模更小的子问题, 
通过每一步贪心选择,可得到问题的一个最优解，虽然每一步上都要保证能获得局部最优解，
但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。

• (7)分治算法

[分治法]是把一个复杂的问题分成两个或更多的相同或相似的子问题，
再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

• (8)回溯算法

回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。
但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，
这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个[状态]的点称为“回溯点”。

• (9)动态规划

[动态规划]是一种在数学和[计算机科学]中使用的，用于求解包含重叠子问题的最优化问题的方法。
其基本思想是，将原问题分解为相似的子问题，在求解的过程中通过子问题的解求出原问题的解。

动态规划的思想是多种算法的基础，被广泛应用于计算机科学和工程领域。

• (10)字符串匹配算法

字符串匹配问题就是在一个大的字符串T中搜索某个字符串P的所有出现位置。
其中，T称为文本，P称为模式，T和P都定义在同一个字母表∑上

三、什么是算法复杂度

算法复杂度----数据结构和算法学习的精髓
算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括时间资源和内存资源。应用于数学和计算机导论。

四、数据结构和算法简单总结

1、数据结构是指一组数据的存储结构
2、算法就是操作数据的方法
3、数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构之上

学习数据结构和算法中。。。算是给自己立的flag，知识总结。