数据结构和算法的作用

定义

• 数据结构：数据结构是对计算机内存，有时候是磁盘中-数据的一种安排
• 数据结构的种类
  • 数组、链表、栈、二叉树、哈希表 etc
• 算法：算法是对这些数据结构中的数据进行各种各样的处理，如CRUD
• 数据结构由某个类进行封装，更泛化的讲，任何一个类都可称为数据结构，因为其中包含了数据的安排

掌握这些知识的好处

• 解决如何用计算机存储现实世界的数据
  • 如，如何用计算机表示一个 仓库货物清单，订单记录等
  • 简单来讲，可以用 List 存放 这些清单，List也是一种数据结构
  • 进而提炼出在此 数据结构中查找你想要信息即算法的问题
• 这些结构可以作为程序员日常工作的辅助工具
• 建模，提供对复杂问题的抽象建模
  • 最重要的数据结构是图

数据结构概述

注意：

查找：即针对特定元素进行搜索的过程

删除 有几种操作：

• 本身的删除操作，如链表前后指针的操作 VS 数组后面所有元素向前移动
• 删除特定位置对象的区别，如队头、栈顶等等，对其他数据操作则不同
• 对指定元素的删除，这样就加入了 查找的复杂度

数据结构	优点	缺点
数组	插入块，如果知道下标，存入/取出很快	查找/删除慢，因为查找要一一对比，删除要移动后续所有元素大小固定
有序数组	比无序数组查找快，可以用二分查找	插入比无序数组慢，删除比无序略快，可以用二分先找，但也要一一对比，大小固定
栈	提供后进先出方式的存取，对栈顶元素 取/删 很快	存取 除栈顶外的元素 慢
队列	提供先进先出方式的存取	存取除队头队尾元素外慢
链表	插入快、删除快	查找慢，一一对比
二叉树	查找、插入、删除都快	删除算法复杂
红黑树	查找、插入、删除都快	算法复杂
哈希表	如果关键字已知 则存、取极快，插入快	删除慢，若不知关键字则存取慢，空间利用不均匀
堆	插入、删除快，对最值存取快	其他数据项 存取慢
图	对现实世界的建模	算法复杂慢

算法

• insert
• select 某特定数据项
• remove 某特定数据项
• 遍历
• 排序
• 递归-

面向对象VS面向过程

• 即 行为与数据地位的问题
  • 数据与行为并列同等重要；
  • 还是 数据作为辅助单独存在方法里
• 面向过程：未重视数据，局部变量还可以，但全局变量，所有方法共同使用的数据就无能为力了

面向对象

• 对象
  • 关键思想：对象是方法和数据的共同存在
  • 与现实世界对象更好的映射
  • 全局变量 public、私有变量 private 的处理
• 类
  • 针对单一对象定义数据/行为，还是抽象提升一个层次
  • 除了单一的对象，有可能需要若干个对象同时处理
  • 类是针对一个或多个对象的说明、蓝图
  • 由类可以得到任意个具有相同数据、行为的对象