vfp 第1章 数据结构与.pdf

第1章 数据结构与算法 1.1 算法 • 1.1.1 算法的基本概念 • 算法是对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。 • 1、算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得 到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义， 不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能 在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法 拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法 可能无效。 • 2、算法的基本要素 • (1)算法中对数据的运算和操作：每个算法实际上是按解题 要求从环境能进行的所有操作中选择合适的操作所组成的 一组指令序列。 • (2)算法的控制结构：一个算法的功能不仅仅取决于所选用 的操作，而且还与各操作之间的执行顺序有关。算法中各 操作之间的执行顺序称为算法的控制结构。 • 3、算法设计的基本方法 • 列举法 • 归纳法 • 递推 • 递归 • 减半递推技术 • 回溯法 • 4、算法设计的要求 通常一个好的算法应达到如下目标： (l)正确性(correctness) (2)可读性(readability) (3)健壮性(robustness) (4)效率与低存储量需求 1.1.2 算法的复杂度 • 1、算法的时间复杂度 • 算法的时间复杂度，是指执行算法所需要的计算工作量。 • 一个特定算法“运行工作量”的大小，只依赖于问题的规 模(通常用整数n表示)，它是问题的规模函数。即 算法的工作量=f(n) • 2、算法的空间复杂度 • 算法的空间复杂度是指执行这个算法所需要的内存空 间。 • 在许多实际问题中，为了减少算法所占的存储空间， 通常采用压缩存储技术，以便尽量减少不必要的额外空间。 1.2 数据结构 • 1.2.1 数据结构的定义 数据结构(datastructure)是指相互之间存在一种 或多种特定关系的数据元素的集合，即数据的组织形式。 • 1.2.2 数据结构的图形表示 • 1.2.3 线性结构与非线性结构 1.3 线性表及顺序存储结构 • 1.3.1 线性表的定义 • 线性表是n(n≥0)个元素构成的有限序列(a1，a2，…，an)。表中 的每一个数据元素，除了第一个外，有且只有一个前件，除了最 后一个外，有且只有一个后件。即线性表是一个空表，或可以表 示为 (a1，a2，…，an) • 其中ai(i=1，2，…，n)是属于数据对象的元素，通常也称其 为线性表中的一个结点。 • 1.3.2 线性表的顺序存储结构 线性表的顺序表指的是用一组地址连续的存储单元 依次存储线性表的数据元素。 线性表的顺序存储结构具备如下两个基本特征： (l)线性表中的所有元素所占的存储空间是连续的； (2)线性表中各数据元素在存储空间中是按逻辑顺序依次 存放的。 • 1.3.3 顺序表的插入运算 • 线性表的插入运算是指在表的第i(1≤i≤n+l)个位置上， 插入一个新结点x，使长度为n的线性表 (a1，…，ai-1，ai，…，an) 变成长度为n+1的线性表 (a1，…，ai-1，x，ai，…，an) • 1.3.4 顺序表的删除运算 • 线性表的删除运算是指将表的第i(1≤i≤n)个结点删除， 使长度为n的线性表： (a1，…，ai-1，ai，ai+1，…，an) 变成长度为n-l的线性表 (a1，…，ai-1，ai+1，…，an) 1.4栈和队列 • 1.4.1 栈及其基本运算 • 1、什么是栈 • 栈实际也是线性表，只不过