数据结构的基础概念

  1. 数据(Data) 数据是描客观事物的数值、字符已经能输入机器且能被处理的各种符号集合。

  2. 数据元素(Data Element) 数据元素是组成数据的基本单位，是组成数据集合的个体。

  • (ps:数据项（Record)：是有独立含义的最小单位)。 一个数据元素可由一个或多个数据项组成。
  1. 数据对象(Data Object) 是性质相同数据元素的集合，是数据的一个子集。
  2. 数据结构(Data Structure) 是相互之间存在一种或多种特定关系的数据元素集合。
  3. 数据类型(Data Type) 是一组性质相同的值集合已经定义在这个值集合上的一组操作的总称。 一般来说高级语言的数据类型分为 “原子类型”和“结构类型”
  4. 抽象数据类型(Abstract Data Type,ADT)
  • 定义了一个数据对象；
  • 定义结构对象中各元素间的结构关系以及；
  • 一组处理数据的操作。
  1. ps:ADT包括“定义”和“实现”俩方面，定义独立与实现。 如：表、队列、堆栈......就是抽象数据类型。 重点：抽象数据类型的重要特点是：数据抽象和信息隐蔽

数据结构的内容

数据元素吉间的相互关系：

  1. 逻辑结构：是指元素之间逻辑关系的描述。
  • //线性结构 （1）集合结构； （2）线性结构；
  • //非线性结构 （1）树状结构； （2）图状结构或者网状结构
  1. 存储结构(物理结构)：是逻辑结构在计算机中存储的映像、实现，包括数据元素的表示和关系的表示。 ps:逻辑结构和存储结构的关系： 存储结构是逻辑关系的映像和元素本身的映像； 逻辑结构是数据结构的抽象； 存储结构是数据结构的实现。 数据元素之间的关系有线性存储结构和非线性存储结构两种表示方法。
  2. 运算集合 数据结构：按某种逻辑关系组织起来的一批数据，按一定的映像方法把他们存放在计算机的存储器中，并在这些数据中定义一个运算的集合！

算法

  1. 定义：算法(Algorithm)是规则的有限集合，是为了解决特定问题而规定的一系列操作。
  2. 算法的特征： a.有限性； b.确定性：即指每个步骤必修有确定的含义； c.可行性； d.输入； e.输出。
  3. 算法设计要求 （1）算法的正确性； （2）可读性； （3）健壮性(鲁棒性):抗非法输入能力; （4）高效性和低存储性。

算法的描述

  1. 算法、语言、程序的关系 a.算法：描述数据对象之间的关系(包括逻辑关系、存储关系)； b.语言:描述算法的工具； c.程序：算法在计算机中的实现。
  2. 设计实现算法过程的步骤
  • a.建立(数据元素之间)结构关系;
  • b.确定在某一数据对象上施加的运算；
  • c.考虑数据元素的存储表示;
  • d.选择语言；
  • e.设计求解的算法并加以描述。

算法性能评价

  1. 性能评价 对 问题规模 和算法在运行时所占 时间 以及 空间 的评价。
  2. 问题规模 算法求解问题的输入量，一般用整数表示。
  3. 算法时间性能分析
    1. 算法耗费的时间 a.一个算法执行时间是指所有语句执行时间的总和； b.每条语句的执行时间=(该条语句执行次数)x(执行一句该语句所需要的实际时间)
    2. 语句频度：是指该语句在算法中重复执行的次数 一个算法的时间耗费：该算法中所有语句频度之和。
    3. 算法的时间复杂度：算法所需时间和问题规模的函数，记作T(n) 算法的时间复杂度T(n)时该算法的时间度量，记作：T(n)=O(f(n))
    4. 渐进时间复杂度 例如：f(n)=2n^3+3n^2+2n+1-->f(n)=n^3; 一般来说常用渐进时间 复杂度表示时间复杂度
    5. 常用算法时间复杂度 O(1)常数型 O(n)线性型 O(n^2)平方型 O(n^3)立方型 O(2^n)指数型 O(log2^n)对数型 O(nlog2^n)二维型 按时间复杂度由小到大递增排列: **log2^n < n < nlog2^n < n^2 < n^3 < 2^n **前三种可以实现，后三种理论上可以实现，但只限与n和小的时候。
  4. 算法的空间性能分析 (1) 算法耗费的空间：即分析该算法实现时所需的辅助空间(2) 算法的空间复杂度S(n)：也时问题规模n的函数，记作：S(n)=O(f(n)) 当没有用到辅助空间时为：S(n)=O(1)

面向对象与抽象数据类型

  1. 面向对象的概念 面向对象=对象+类+继承+通信
  • a.对象：是指应用问题中出现的各个实体、事件和规格说明等，她是由一组属性和在这组值上的一组服务构成的，其中属性值确定了对象的状态。
  • b.类：把具有相同属性和服务的对象归为一类，而把一个类中的每一个对象称为该类的一个实例。他们具有相同的服务。
  • d.继承：面向对象方法的最有特色的方面
  • e.各个类的对象间通过消息进行通信
  1. 面向对象程序设计的特点：封装性(Encapsulation)、继承性(Inheritance)、和多态性(Polymorphism)
  2. 基本操作：插入、删除、更新、查找、排序