总结：

问题的共性都无法用数学公式或方程来描述，是一些“非数值计算”的程序设计问题

描述非数值计算问题的数学模型不是数学方程，而是表、树、图之类的具有逻辑关系的数据

数据结构是一门研究非数值计算的程序设计中计算机的操作对象以及它们之间的关系和操作的学科

数据（Data）：是能输入计算机并且能被计算机处理的**各种符号的集合**

是信息的载体

是对客观事物符号化的表示

是能够被计算机识别、存储和加工

分类：

数值型数据（可以进行加减乘除取余等操作）：整数、实数

非数值型：文字、图像、图形、声音等

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

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

别名：元素、记录、结点、顶点

数据项（Data Item）：是构成数据元素的不可分割的最小单位

数据>数据元素>数据项

例：

学生表>个人记录>学号、姓名…

数据对象（Data Object）：是性质相同的数据元素的集合，是数据的一个子集

例如：

整数数据对象 N={0,-1,1,2,3,4…}

字母字符数据对象集合：{A,B,C… }

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

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

数据结构（Data Structure）：

数据结构包括三个方面的内容：

划分方式一：

线性结构：有且仅有一个开始和一个终端节点，并且中间节点之间存储位置是连续的。

例如（一对一）；线性表、栈、队列、串

非线性结构：一个结点可能有多个直接前趋和直接后继

例如（一对多、多对多）：树、图

划分方式二（四个基本逻辑结构）：

四种基本的存储结构：

数据类型的定义：

是一组性质相同的**值或集合以及定义与这个值集合上的一组操作**的总称。

通解：数据类型=值的集合+值集合上的一组操作

在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量，常量或表达式，明确说它们所属的数据类型。

举例C语言：

数据类型的作用：

抽象数据类型（Abstract Data Type ADT）：

定义：是指一个数学模型以及定义在此数学模型上的一组操作

抽象数据类型的形式定义：

可用（D、S、P）三元组表示：

抽象数据类型的定义格式：

对特定问题求解方法和步骤的一种描述，他是**指令的有限序列**。其中每个指令表示一个或多个操作。

概况：算法就是解**决问题的方法和步骤**

算法：

是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个额问题可以有多种算法。

程序：

是用某种程序设计语言对算法的具体实现。

二者之间的关系：

程序=数据结构+算法

有穷性：算法执行步骤是有范围的，且每一个都在有穷时间内完成。

确定性：算法中的每一条指令都是有确切含义的。

可行性：算法可以执行。

输入：算法有零个或多个输入。

输出：算法有一个或多个输出。

4个要求：

算法效率通过两个方面进行考虑：

根据算法在执行过程耗费的时间来度量。

两种度量方法：

通俗解释：

*算法运行时间=每条语句的执行次数（语句频度）该语句执行一次所需的时间

注意：我们可假设执行每条语句所需时间均为**单位时间，**此时：

算法的运行时间，只需要考虑算法中所有语句的执行次数即可。

for循环的次数等于 N+1次，（+1是不满足条件的最后一次）

为了便于笔记不同算法的时间效率，我们仅不叫它们的**数量级**

例如：

a=n的三次方，b=n的5次方

结果：a好，b不好

算法中基本语句重复执行的次数是问题规模N的某个函数f(n)，算法的时间记作：T(n)=O(f(n))

基本语句重复执行的次数解释：

问题规模n解释：

它表示随着n的增大，算法执行的时间的增长率和f（n）的增长相同，称：渐进时间复杂度

步骤：

1 找到语句频度最大的那条语句作为基本语句

2 计算基本语句的频度得到问题规模n的某个函数f(n)

3 取其数量级用符号O表示

理解：$ 2^4=log_216=4 $

$ 2^x=log_2N=x $

注意点：有的情况下，算法中基本操作重复执行的次数还随问题的数据解不同而不同

考虑算法时间复杂度的三个方面：

对于复杂的算法，可以将它分成几个容易估算的部分，然后利用大O加法法则和乘法法则，计算算法的时间复杂度：

当n取得很大后，指数时间算法和多项式时间算法在所需时间上非常悬殊

口令：常对幂指阶

记作：$ S(n)=O(f(n)) $

注意：其中n为问题的规模