记得上数据结构时，用的书是清华大学出版社的那本数据结构，当时看我的一愣一愣的，枯燥乏味之极，现在回头再来理理数据结构，只对数据结构概念简单地介绍不做过深的研究（谁让我是用Java的呢）

1.什么是数据结构？

数据结构指的数据之间的相互关系，即数据的组织形式。
什么意思呢？就是说物以类聚，相同的数据元素的集合是数据结构。

2.顺序存储结构和链式存储结构

顺序存储结构：比如数组就是一个顺序存储结构，相邻的元素在一组连续的存储单元中。
缺点：插入、删除时速度慢，因为要移动节点。
链式存储结构：每个结点附加指针字段存放相邻节点存储地址。
缺点：空间利用率低，
优点：插入、删除速度快，因为不用移动节点 。

下面开始正式介绍各种数据结构：

3.线性表(list)

线性表是由n（n>=0）个节点组成的有限序列。
如（a1,a2,a3,a4,a5）
a1为起始节点，a5为终端节点，a1是a2的前驱节点，a3是a2的后继节点。
不含有任何节点的线性表为()
3.1 顺序线性表
在Java中ArrayList就是线性表的顺序存储结构。
3.2 单链表
链式存储的线性表
3.3循环单链表
最后一个节点指针指向头结点形成一个环叫做单链表
3.4双链表
在单链表的基础上每个指点增加一个指向前驱的指针域prior.

4栈(Stack)

栈是一种特殊的线性表，特点：FIFO。
允许进行插入删除的一端是栈顶，另一端是栈低。

5.队列(Queue)

队列是一种运算受限的线性表。
插入在表的一端进行，而删除只能在另一端进行，举个例子，很像食堂排队买饭，你要是想排队只能在最后排队，打好饭后从前面离开，脱离队伍。

6.串

就是java 中的string
串的模式匹配算法KMP、BF（看不懂），

7.数组

没有什么好说的，存储的连续内存单元中
7.1稀疏矩阵

8.递归

不断地调用本身。

9广义表

广义表是线性表的推广。

10.树

树是树形结构的简称。

10.1 二叉树

著名的二叉树
二叉树是一处特殊的树，每个节点最多只有2 个后继节点。
二叉树的遍历（看根节点的位置在哪里 ）：
先序遍历：根节点，左节点，右节点
中序遍历：左 、根、右
后序遍历：左、右、根

10.2哈夫曼树

特殊的二叉树，从根节点到叶子节点都带有权值，从中构造出带权路径最短的乘积的和叫做哈夫曼树。

11.图

图是一种非线性结构，比树形结构复杂的多。
图是一个非空节点的集合并且描述顶点之间的关系的组成
11.1 有向图：边有方向的，无向图：边无方向。
11.2图的遍历
广度优先和深度优先

查找

12.顺序查找

one by one

13.二分查找 （折半查找）

线性表中的元素必须递增或递减顺序排列
砍一半从中间查找 ，比较大小再砍一半
问：要是不是递增或者递减怎么办？

14分块查找

性能介于顺序查找和二分查找之间
分块查找是把线性表分成干块，每个块内的数据顺序不固定，但是块与块之间前一个块中的最大值比后一个块中的最小值 要小，还要一个索引表来，索引表中的每一个项对应一个块。举个例子，分块查找很像1-6年级分别找一个小朋友，每个小朋友都是这个年级学习最好的，但是再厉害也没有比他年级大的厉害。

15.二叉排序树

解决二分查找时频繁插入、删除额外的开销。
最坏的时间0（n）

16.二叉平衡树

提升二叉排序树的性能

排序

17插入排序

17.1 直接插入排序
将一个数插入到一个有序的序列中

17.2 希尔排序

也叫缩小增量排序，举个例子，比如10个数，第一次增量是5,0和5比较，1和6比较...
第二次增量变为2，第三次增量变为1

18选择排序

选择最小的数放在已排好的最后边，依次类推

18.1直接选择排序

18.2堆排序

堆是顺序存储的完全二叉树

19交换排序

以前丧尸教的

19.1冒泡排序

19.2快速排序

冒泡的改进，没看懂

19.3归并排序

有点像比赛，先是2个是一对排序，这一对和另外一对比较排序，他们四个又组成一对，一直到最后

19.4基数排序

算法

20.迭代法

不断用新值取代旧值
Fibonacci数列
1 1 2 3 5 8

21.穷举法

思想是不重复，不遗漏

22.递归法

23.回溯法

叫试探法更好理解法

24.分枝限界法

25.分治法

大问题变为小问题

26.动态规划法

与分治法类似，大问题变为小问题，小问题往往不是相互独立的

数据结构与算法差不多稍微提了一下。