【13003数据结构与算法】第一章 绪论知识点

却尘

第一章 绪论

1. 数    据：指所有能输入计算机并被计算机程序处理的符号的集合，如文档，声音，视频等。

数据元素：构成数据的基本单位，逻辑上相关的、具有物理意义的若干数据项构成一个数据元素。

数 据 项：数据元素还可以细分为数据项，数据项是数据的最小不可分单位。

2. 数据结构：数据元素之间的相互关系构成结构，带有结构特性的数据元素集合构成数据结构，又可分为逻辑结构和存储结构。

逻辑结构：从逻辑上描述数据，表明数据元素之间的关系。

存储结构：指数据元素在计算机中的表示及存储方式

3.  基本的数据结构

集合、线性结构、图结构、树结构

4. 常用的存储方法

1）顺序存储方法：逻辑和物理位置都相邻，如一维数组保存线性结构中的数据元素。

2）链式存储方法：逻辑相邻，物理位置不一定相邻，通常用指针指示数据间的逻辑关系。

3）索引存储方法：由索引项组成，指示数据元素的物理位置，可加快查找。

4）散列存储方法：根据数据元素的关键字，计算出物理存储位置

5. 抽象数据类型

除了程序设计语言中提供的基本类型外，还可以定义抽象意义下的类型，并为该类型定义一组相关的操作。这样定义的数据类型称为抽象数据类型（ADT：Abstract Data Type）

抽象数据类型的定义包括类型的名字及对各个操作的刻画（没有实现）。规定操作的名字、操作执行的前提条件、输入和输出，每个操作通常表示为一个函数或是方法

6. 算法特性（助记：输入有确(鹊)行）

输入：有0或多个输入值

输出：有1或多个输出值

有穷性：一个算法必须在执行有穷步骤之后结束

确定性：算法的每一个步骤必须是有确切含义的

可行性：算法中要做的运算都是相当基本的、能够精确进行的

7. 问题规模：计算机中最重要的资源之一是CPU，显然，花费的时间与处理的数据个数有很大的关系，这个数据个数称为问题规模，也称问题大小。执行算法花费的时间表示为问题规模的一个函数。

8. 时间复杂度 （大O表示法）【应用】

一个算法的时间效率可以用问题规模及关键的处理步骤的多少来定义；

将算法的运行效率表示为问题规模n的一个解析式，对于规模为n的问题，解析式计算的值，应该是算法处理的步骤数，将关于n的这个解析式称为增长函数，表示为T(n)；

对于一个具体的算法，其增长函数是一个近似的表达式。

9. 空间复杂度

算法在运行过程中临时占用的空间大小。

算法代码占用的空间、算法中初始数据占用的存储空间，都不包含在内。

10. 算法设计策略

1）递推法：直接求解，利用问题本身所具有的一种递推关系进行求解。（斐波那契数列）

斐波那契数列:第3项起，每个数值都是前两个数值之和。前10项为：1,1, 2,3, 5,8, 13,21, 34,55。

2）迭代法：直接求解，建立迭代关系式，即根据前一个值推出下一个值的公式。（最大公约数）

3）递归法：是函数自己调用自己来解决问题。（阶层的递归实现）

4）贪心法：通过每一步选择局部最优解来达到整体最优解的算法。（构造哈夫曼树、最小生成树）

5）分治法：①将问题划分成子问题②求解小问题③小问题解的合并（快速排序、归并排序）

6）动态规划法：将问题的整体按时间或空间的特征分成若干个前后衔接的阶段，把多阶段决策问题表示为前后有关的一系列单阶段决策问题，然后逐个求解，从而求出整个问题的最优决策。（最大子序列和）