计算机从解决数值计算问题到解决生活中的问题

现实生活中的问题涉及不同个体间的复杂联系

需要在计算机程序中描述生活中个体间的联系

数据结构主要研究非数值计算程序问题中的操作对象以及它们之间的关系而不是研究复杂的算法

数据结构

基本概念

数据：程序的操作对象，用于描述客观事物

数据的特点：

-可以输入到计算机

-可以被计算机程序处理

数据是一个抽象的概念，将其进行分类后得到程序设计语言中的类型。如：int，float，char等等

数据元素：组成数据的基本单位

数据项：一个数据元素由若干数据项组成

数据对象 – 性质相同的数据元素的集合

e.g.

struct _MyTeacher   //一种数据类型{
    	char	name[32];	char	tile[32];	int		age;	char	addr[128];};int main21(){
    	struct _MyTeacher t1; //数据元素    struct _MyTeacher tArray[30]; //数据对象	memset(&t1, 0, sizeof(t1));	strcpy(t1.name, "name"); //数据项	strcpy(t1.addr, "addr"); //数据项	strcpy(t1.tile, "addr"); //数据项	t1.age = 1;}

数据元素之间不是独立的，存在特定的关系，这些关系即结构

数据结构指数据对象中数据元素之间的关系

数据的逻辑结构

指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类

数据的物理结构

数据的运算

算法

基本概念

算法是特定问题求解步骤的描述

在计算机中表现为指令的有限序列

算法是独立存在的一种解决问题的方法和思想

对于算法而言，语言并不重要，重要的是思想

算法和数据结构区别

数据结构只是静态的描述了数据元素之间的关系

高效的程序需要在数据结构的基础上设计和选择算法

程序=数据结构+算法

总结：

算法是为了解决实际问题而设计的

数据结构是算法需要处理的问题载体

数据结构与算法相辅相成

算法特性

• 输入：算法具有0个或多个输入
• 输出：算法至少有1个或多个输出
• 有穷性：算法在有限的步骤之后会自动结束而不会无限循环
• 确定性：算法中的每一步都有确定的含义，不会出现二义性
• 可行性：算法的每一步都是可行的

算法效率的度量

• 事后统计法

  比较不同算法对同一组输入数据的运行处理时间
  缺陷
  • 为了获得不同算法的运行时间必须编写相应程序
  • 运行时间严重依赖硬件以及运行时的环境因素
  • 算法的测试数据的选取相当困难
  • 事后统计法虽然直观，但是实施困难且缺陷多

• 事前分析估算

  依据统计的方法对算法效率进行估算
  影响算法效率的主要因素
  • 算法采用的策略和方法
  • 问题的输入规模
  • 编译器所产生的代码
  • 计算机执行速度

• 大O表示法

  算法效率严重依赖于操作(Operation)数量
  在判断时首先关注操作数量的最高次项
  操作数量的估算可以作为时间复杂度的估算
  常见时间复杂度：
  
  关系
  

• 算法的空间复杂度

  算法的空间复杂度通过计算算法的存储空间实现
  S(n) = O(f(n))
  其中，n为问题规模，f(n))为在问题规模为nn时所占用存储空间的函数
  大O表示法同样适用于算法的空间复杂度
  当算法执行时所需要的空间是常数时，空间复杂度为O(1)

空间与时间的策略

• 多数情况下，算法执行时所用的时间更令人关注
• 如果有必要，可以通过增加空间复杂度来降低时间复杂度
• 同理，也可以通过增加时间复杂度来降低空间复杂度