数据结构和算法-1-综述

之前有读过《Java数据结构和算法》，当时简单的写了一些笔记和实现的实例，现对其进行一个系统的整理，以作为分享和备忘。

本篇主要是一些简要的介绍和一些专业词汇的定义：

1. 什么是数据结构和算法

• 数据结构：对计算机内存/磁盘中数据的一种安排，数据结构包括数组，栈，二叉树，哈希表等待
• 算法：对这些结构中的数据进行各种处理，如查找，排序等

2. 可以解决哪些问题？

大体可以分为三类情况：

• 现实世界的数据存储
  如我们平时的手机电脑等电子产品中的保存的文件是如何进行存储的。使用什么结构，基于哪些算法可以更安全高效，更便于使用修改，查找等
• 程序员的工具
  如我们平时所说的堆栈，队列，经常使用的数组，java中提供的集合类，Arrays和Collections中提供的一些工具方法等
• 建模
  将现实中的问题映射成数据结构（比如之后要学到的图）或使用一些数据结构和算法进行组合分析等

3. 常用数据结构的优缺点

• 数组：
  优点：插入快，如果知道下标，可以非常快速的存取；
  缺点：查找慢，删除慢，大小固定
• 有序数组
  查找比无需数组快
  插入慢，删除慢，大小固定
• 栈
  提供后进先出方式的存取
  存取其他项很慢
• 队列
  提供先进先出方式的存取
  存取其他项很慢
• 链表
  插入快，删除快
  查找慢
• 二叉树
  插入，查找，删除都很快
  删除算法复杂
• 红黑树
  插入，查找，删除都很快，树总是平衡的
  算法复杂
• 234树
  插入，查找，删除都很快，树总是平衡的，
  算法复杂
• 哈希表
  插入快，如果关键字已知则存取极快
  删除慢，如果关键字未知则存取很慢，对存储空间使用不充分
• 堆
  插入，删除快，对最大数据项的存取快
  对其他数据项的存取慢
• 图
  对现实世界建模
  有些算法慢且复杂

以上除数组外，都可以被认为是抽象数据结构 ；
这些数据结构后面都会有单独的篇章去进行具体的讲解，现在不用去纠结它们是什么。

面向对象编程语言的产生的原因

• 是由于面向过程语言在处理大型的复杂问题时的力不从心
• 程序与现实世界缺乏对应关系（对现实世界建模的无能为力）
• 程序内部的结构出现了问题

抽象数据类型：

Abstract Data Type ，简称ADT，用于指定逻辑特性而不指定实现细节的数据结构 ，简单来说就是 着重于它做了什么，而忽略它是怎么做的。
例如，栈和队列都是属于ADT，用数组或者链表都可以实现栈和队列，拿栈来说，它的精髓在于后进先出，在于push，pop，以及如何使用它，而不是它的内在实现，用数组还是链表实现关键就在于，能否精确的预测栈或队列需要容纳的数据量，以及增删改查的时间复杂度（效率）的差别。

算法的时间复杂度(大O表示法)

• 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数。T(n)称为这一算法的“时间复杂度”。

这个定义来自百度百科，感觉并不容易看懂，不过并不重要，下面举几个例子就好了：

1. 交换i，j的时间复杂度是 O(1)

int i=1, j=2, temp;
temp=i;
i=j;
j=temp;

2. 单层for循环的时间复杂度是O(n)

int sum=0;
for(int i=0;i<n;i++){
  sum+=i;
}

3. 双重for循环的时间复杂度是O(n^2)

int sum=0;            （一次）
for(i=1;i<=n;i++)     （n次 ）
  for(j=1;j<=n;j++)   （n^2次 ）
    sum++；           （n^2次 ）
解：T(n)=2n^2+n+1 =O(n^2)

后面讲到其他数据结构和算法还会多次提及这个感念，例如下一篇的数组，线性查找(fori)的时间复杂度是O(n),而有序数组的二分查找的时间复杂度是O(logN)。