数据结构第1章 绪论2

与其在计算机内部的表示和实现无关。 不论内部结构如何变化，都不会影响外部使用。
8
例：线性表这样的抽象数据类型。 • 数学模型：数据元素的集合； • 该集合内的元素的关系：除第一个和最后 一个外，每个元素有唯一的前趋和唯一的 后继； • 操作：插入一个元素、删除一个元素等。
9
抽象数据类型不仅仅局限于固有数据类型，也包括用 户自定义的数据类型。 ADT 按照其值的不同特性，分为4种类型：
第一章 绪 论
1.1 什么是数据结构
1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析
1
1.1 什么是数据结构
用计算机解决具体问题的步骤 ：
1. 抽象出一个数学模型； 2. 设计一个解此数学模型的算法； 3. 编程、测试、调整。 寻求数学模型：分析问题、提取操作的对象及其 数据结构是一门研究非数值计算的程序设计问题 对象之间的关系并进行描述。
1. 数据抽象：用ADT描述程序处理的实体时，强调 的是其本质的特征、其所能完成的功能以及它和外 部用户的接口（即外界使用它的方法）。 2. 数据封装：将实体的外部特性和其内部实现细节 分离，并且对外部用户隐藏其内部实现细节。 抽象数据类型的定义由一个值域和定义在该值域上 的一组操作组成。
11
抽象数据类型的描述方法
25
例:试说明下列算法过程是否是一个算法：
(1)开始
(2)n=0; (3)n=n+1； (4)重复(3)； (5)结束。
26
有穷性？ 不是一个算法！
二. 算法设计的原则
设计算法时，通常应考虑达到以下目标： 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求
27
1．正确性
⑴算法应当满足以特定的“规格说明”方式给出的 需求。 ⑵对算法是否“正确”的理解可以有以下四个层次： a．程序中不含语法错误； b．程序对于几组输入数据能够得出满足要求的 结果； √ c．程序对于精心选择的、典型、苛刻且带有刁难 性的几组输入数据能够得出满足要求的结果； d．程序对于一切合法的输入数据都能得出满足要 通常以第 c 层意义的正确性作为衡量标准。 求的结果；
•原 子 类 型：其值不可分解的类型；如：int •固定聚合类型：其值由确定数目的成分按某种结构组成；如： 复数； •可变聚合类型：其值由不固定数目的成分按某种结构组成； 如：学生基本情况，有序整数序列； •多形数据类型：其值的成分不确定的数据类型；（元素之间 的关系相同，基本操作也相同 ）
10
ADT 有两个重要特征:
1. 数据类型是一个“值”的集合和定义在此集 合上的“一组操作”的总称。
例：C++语言中的整型，其内涵为一定范围的自然数集合，及 定义在该集合上的加减乘除及取模等算术运算。
数据 类型
原子类型:整型、实型、字符型等 结构类型:数组、结构体
2. 数据类型也可以是看成一个数据结构和定义 在这个数据结构上一组操作的总称。
31
三. 算法效率的衡量方法和准则
1. 对一个算法要作出全面的分析衡量，可分 别使用两种方法：事后统计和事前分析
• 事后统计 缺点：1．必须执行程序 2．其它因素掩盖算法本质
32
•事前分析 和算法执行时间相关的因素： ⑴ 算法选用的策略
⑵ 问题的规模
⑶ 编写程序的语言 ⑷ 编译程序产生的机器代码的质量 ⑸ 计算机执行指令的速度
17
GetImag( Z, &ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。
Add( z1,z2, &sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的和值。
} ADT Complex 假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果即为用户需要的结果 z3 = z2 + z1
18
1.3 抽象数据类型的表示和实现
抽象数据类型需要通过固有数据类型(高级编程语言
中已实现的数据类型)来实现。
【例】利用C++语言实现的"复数"类型如下描述：
19
// -----存储结构的定义 typedef struct { float realpart； float imagpart； } complex； // -----基本操作的函数原型说明 void Assign( complex &Z, float realval, float imagval )； // 构造复数 Z,其实部和虚部分别被赋以参数 // realval 和 imagval 的值
2. 初始条件: 描述了操作执行之前数据结构和参数 应满足的条件，若不满足，则操作失败，并返回相应 出错信息。若初始条件为空，则省略之。 3. 操作结果: 说明了操作正常完成之后，数据结构的 变化状况和应返回的结果。
15
【例】抽象数据类型 复数 的定义：
ADT Complex { 数据对象： D＝{e1, e2｜e1,e2∈RealSet } 数据关系： R1＝{<e1, e2> | e1是复数的实数部分， | e2 是复数的虚数部分 }
21
// -----基本操作的实现 void add( complex z1, complex z2, complex &sum ) { // 以 sum 返回两个复数 z1, z2 的和
sum.realpart = z1.realpart + z2.realpart;
sum.imagpart = z1.imagpart + z2.imagpart; } { 其它省略…… }
中计算机的操作对象以及它们之间的关系和操作 的学科。
2
1.2 基本概念
一. 数据和数据结构
数据：
指所有能被输入到计算机中，且能被计算
机处理的符号的集合。
是计算机操作的对象的总称。
数据元素:
是数据结构中讨论的基本单位。 在计算机程序中作为一个“整体”进行考
虑。
3
数据项：
是数据结构中讨论的不可分割的最小单位。
29
4．高效率与低存储量需求 通常，效率指的是算法执行时间；存储量指的是算
法执行过程中所需的最大存储空间，两者都与问题
的规模有关。
30
• 算法与程序的区别
– 算法是解决问题的一种方法或一个过程，考虑 如何将输入转换成输出，一个问题可以有多个 算法。 – 程序是用某种程序设计语言对算法的具体实现。 • 主要区别：有穷性、正确性和描述方法 – 程序可以是无穷的，例如OS，算法是有穷的； – 程序可以是错误的，而算法必须是正确的； – 程序是用程序设计语言描述的，在机器上可以 执行，算法还可以用自然语言、框图、高级程 序语言等方式描述。
“O”的数学含义是，若存在两个常量 c 和 n0 ,当n≥n0 时， T(n)≤cf(n) 则记作 T(n)= O(f(n))
例：T(n)=(n+1)2 当n0=1,c=4时 n≥1时，(n+1)2≤4n2 则T(n)=O(n2) ——(渐近)时间复杂度
35
(渐近)时间复杂度 T(n)=2n+1 O(n) T(n)=2n2+2n+1 O(n2) m+1 ——频度 for(i=1;i≤m;i++) m*(n+1) for(j=1;j≤n;j++) m*n x++; T(n)=m+1 + m*(n+1) + m*n =2*m*n+2*m+1 T(n)=O(mn)
2．确定性: 对于每种情况下所应执行的操作，在算 法中都有确切的规定，使算法的执行者或阅读者都 能明确其含义及如何执行。并且在任何条件下，算 法都只有一条执行路径。
3．可行性: 算法中描述的操作都是可以通过已经实 现的基本运算执行有限次来实现。
24
4．有输入：零个或多个的输入。作为算法加工对象 的量值，通常体现为算法中的一组变量。有些输入 量需要在算法执行过程中输入，而有的算法表面上 可以没有输入，实际上已被嵌入算法之中。 5．有输出：一个或多个的输出。它是一组与“输 入”有确定关系的量值，是算法进行信息加工后得 到的结果，这种确定关系即为算法的功能。
抽象数据类型可用三元组表示:
ADT =（D，S，P）
其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。
12
数据结构的形式定义为:
数据结构是一个二元组 Data_Structures = (D, S) 其中: D 是数据元素的有限集， S 是 D上关系的有限集。
13
其中，数据对象和数据关系的 定义用伪码描述
与计算机 硬件、软 件有关
33
2.一个算法的“运行工作量”通常是随问题规模 的增长而增长，因此比较不同算法的优劣主要 应该以“问题规模增长的趋势”为准则。 3.算法中所有语句的频度之和记做T(n)。
4.假如，随着问题规模n的增长,算法执行时间的 重复执行 增长率和f(n)(算法中基本操作重复执行的次 的次数 数是问题规模n的某个函数f(n)）的增长率相 其重复执行次数和算法的执 同,则可记作： 行时间成正比的原操作 T(n)= O(f(n)) 34 称T(n)为算法的(渐近)时间复杂度
5
1.2 基本概念
二. 数据类型
在用高级程序语言编写的程序中，必须对程序中出现 的每个变量、常量或表达式，明确说明它们所属的数 据类型。 【例】C/C++语言中提供的基本数据类型有: 整 型 int 浮 点 型 float 双精度型 double
6
字符型 char
逻辑型 bool （ C++语言）
16