一、数据结构

1. 什么是数据结构

 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成

2. 数据结构的分类

  传统上，我们把数据结构分为逻辑结构和物理结构
      
  (1). 逻辑结构:是指数据对象中数据元素之间的相互关系，也是我们今后最需要关注和讨论的问题。
       1.集合结构
       数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；

集合结构.jpg

       2.线性结构
       数据结构中的元素存在一对一的相互关系；

线性结构.jpg

       3.树形结构
       数据结构中的元素存在一对多的相互关系；

树形结构.jpg

       4.图形结构
       数据结构中的元素存在多对多的相互关系。

图形结构.jpg

 (2). 物理结构:指数据的逻辑结构在计算机存储空间的存放形式。
      1.顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。

顺序存储结构.jpg

      2.链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。

链式存储结构.jpg

3. 常用的数据结构

数据结构	优点	缺点
数组	插入块，如果知道下标，可以非常快的存取	删除和查找慢，大小固定
有序数组	比无序的数组查找快	删除和插入慢，大小固定
栈	提供后进先出的取存方法	取存其他项很慢
队列	提供先进先出的取存方法	取存其他项很慢
链表	插入快，删除快	查找慢
二叉树	查找，插入，删除都快(如果树保持平衡)	删除算法复杂
红-黑树	查找，是插入，删除都快。树总是平衡的	算法复杂
2-3-4树	查找，是插入，删除都快。树总是平衡的。类似的树对磁盘存储有用	算法复杂
哈希表	如果关键字已知存取几块。插入快	删除慢，如果不知道关键字则存取很慢，对存储空间使用不充分
堆	插入，删除快，对最大数据项的存取很快	对其他数据项存取慢
图	对现实世界建模	有些算法慢切复杂

数据结构.jpg

4. 数据结构的应用表现

   1. 对现实世界数据的存储
   2. 程序员的工具
   3. 对现实世界进行建模

二、算法

1. 什么是算法

      算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，
  算法代表着用系统的方法描述解决问题的策略机制。

2. 算法的特征

  一个算法应该具有以下五个重要的特征：
  
  有穷性（Finiteness）
  算法的有穷性是指算法必须能在执行有限个步骤之后终止；
  
  确切性 (Definiteness)
  算法的每一步骤必须有确切的定义；
  
  输入项 (Input)
  一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件；
  
  输出 (Output)
  一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
  
  可行 (Effectiveness)
  算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成（也称之为有效性）。

3. 算法设计的要求

  正确性
  算法的正确性是指算法至少应该具有输入、输出和加工处理无歧义性、能正确反映问题的需求、能够得到问题的正确答案。
  大体分为以下四个层次：
  算法程序没有语法错误。
  算法程序对于合法输入能够产生满足要求的输出。
  算法程序对于非法输入能够产生满足规格的说明。
  算法程序对于故意刁难的测试输入都有满足要求的输出结果。

  可读性
  算法设计另一目的是为了便于阅读、理解和交流。
  我么写代码的目的，一方面是为了让计算机执行，但还有一个重要的目的是为了便于他人阅读和自己日后阅读修改。
     
  健壮性
  当输入数据不合法时，算法也能做出相关处理，而不是产生异常、崩溃或莫名其妙的结果。
     
  时间效率高和存储量低
  生活中，每个男人都希望找一个贤惠的老婆，她们温柔又体贴，美丽又大方，还会做着一手的好菜。
  好算法就犹如好老婆，应该具备时间效率高和存储量低的特点。
  所以在设计算法的时候我们应该尽量思考这两方面的问题！

4. 算法的评价标准

     1. 时间复杂度
         就是常用的大O表示法，一般大O表示法是评判算法优劣的主要依据具体的描述可以查阅百度百科
     2. 空间复杂度
         在当前硬件设备便宜的当下，一般都会牺牲空间复杂度来换取时间