Day01 绪论

---

背景：计算机加工处理的对象已经由纯粹的数值发挥到字符、表格、和图像等各种具有一定结构的数据，所以必须分析待处理的对象的特性以及各处理对象之间存在的关系。

---

1.1  什么是数据结构

计算机处理一个具体的问题的步骤：1、抽象数学模型   2、设计算法  3、编写程序  4、测试调整

简单来说：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据结构是介于数学、计算机硬件和计算机软件之间的一门核心课程。

---

1.2  基本概念和术语

数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

四类基本结构：集合、线性结构、树形结构、图状结构或网状结构

数据的物理结构、位、元素或节点、数据域

顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系：“一维数组”

链式存储结构：借助元素存储地址的指针表示数据元素之间的逻辑关系：“指针”

数据类型：一个值的集合和定义在这个值集上的一组操作的总称。

原子类型：属原子类型的变量是不可分解的。

结构类型：固定聚合类型、可变聚合类型

*****  多形数据类型：值的成分不确定的数据类型。

1.3  抽象数据类型的表示与实现

《数据结构》----严蔚敏    P9~P13

分配三个元素的存储空间：T = (ElemType * ) malloc (3 * sizeof(Elemtype));

1.4  算法与算法分析

1.4.1  算法

算法：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。具有以下5个重要特性：有穷性、确定性、可行性、输入、输出。

1.4.2  算法设计的要求

正确性： a.语法正确 b.几组正常数据可得到正确结果 c.精心选择的典型、苛刻而带有刁难性的几组输入数组可得到正确结果 d.对于一切合法数据都可得到正确结果。一般达到C即可称为合格。

可读性：便于人的阅读理解。

健壮性：输入数据非法时，进行报错，而不是产生莫名奇妙的结果。

效率与低存储量需求：效率指的是算法的执行时间，越短越好。存储量需求指算法执行过程中所需要的最大存储空间，越小越好。

1.4.3  算法效率的度量

时间复杂度：随问题规模n的增大，算法执行时间的增长率和 f(n)的增长率相同，称作算法的渐进时间复杂度。T(n) = O( f(n) )

1.4.4  算法效率的度量

空间复杂度