http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学 Data Structure and Algorithm 《数据结构及其算法》 http://staff.ustc.edu. cn/~dongeliu/dsa.html 刘 东 信息学院6系 中国科学技术大学
第2章 数据结构导论 2.1 概念与术语 2.2 抽象数据类型 2.3 算法概述 2.4 算法分析 2019/4/22 数据结构及其算法 第2章 数据结构导论
数学模型：用数学语言描述客观事物的特性和事物 之间的关系 利用计算机解决具体问题的步骤 从具体问题抽象出数学模型 针对数学模型设计算法 将算法转化为程序 数学模型：用数学语言描述客观事物的特性和事物 之间的关系 对于数值计算问题，数学模型一般是方程 对于非数值计算问题，数学模型一般是表、树、图等结构 数值计算问题 如：最大公约数问题 输入：m,n 输出：p 数学模型：p = max{q|m%q==0 && n%q==0} 2019/4/22 数据结构及其算法 第2章 数据结构导论
非数值计算问题1：查找图书 输入：图书目录、查找关键字 输出：图书编号 数学模型：表（线性结构） 2019/4/22 数据结构及其算法 第2章 数据结构导论
非数值计算问题2：人机对弈 输入：当前棋盘格局 输出：最佳落子位置 数学模型：状态树（树形结构） 2019/4/22 数据结构及其算法 第2章 数据结构导论
非数值计算问题3：六度分隔 输入：人际关系 输出：最短路径 数学模型：社会网络（图状结构） 2019/4/22 数据结构及其算法 第2章 数据结构导论
非数值计算问题中的线性、树形、网状等数学模型 统称为数据结构 程序设计 = 数据结构 + 算法 2019/4/22 数据结构及其算法 第2章 数据结构导论
The Art of Computer Programming (TAOCP) “数据结构”学科开创者 Donald E. Knuth (高德纳) The Art of Computer Programming (TAOCP) 2019/4/22 数据结构及其算法 第2章 数据结构导论
2.1 概念与术语 数据(data)：是对客观事物的符号表示，所有能 输入到计算机中并被计算机程序处理的符号的总称 数据元素(data element)：数据的基本单位 数据项(data item)：数据的不可分割的最小单位 数据对象(data object)：性质相同的数据元素 的集合 数据结构(data structure)：相互之间存在一 种或多种特定关系的数据元素的集合 2019/4/22 数据结构及其算法 第2章 数据结构导论
典型的数据“结构” 集合 线性结构 树形结构 图状结构 2019/4/22 数据结构及其算法 第2章 数据结构导论
数据结构的形式定义：Data_Structure=(D,S) 例：复数数据结构 ComplexNumber = (D,S) D = {real,imag|real,imag为实数} S = {<real,imag>} 常用<>表示有序关系，()表示无序关系 real imag 2019/4/22 数据结构及其算法 第2章 数据结构导论
数据结构在计算机中的存储方式称为数据的物理结 构或存储结构 数学模型又称为数据的逻辑结构 数据元素存储为位串（元素element或结点node） 数据项存储为子位串（数据域data field） 典型的存储结构 顺序存储 链式存储 2019/4/22 数据结构及其算法 第2章 数据结构导论
2.2 抽象数据类型 数据类型(data type)：一个值的集合和定义在 这个值集上的一组操作的总称 原子类型：如int、float、char 结构类型：如数组、struct、class (C++) 抽象数据类型(abstract data type, ADT)： 一个数学模型以及定义在该模型上的一组操作 ADT=(D,S,P) P：对数据的操作（函数）的集合 封装(encapsulate)了一组操作 2019/4/22 数据结构及其算法 第2章 数据结构导论
复数ADT的定义 ADT ComplexNumber { 数据： D = {real,imag|real,imag为实数} S = {<real,imag>} 操作： // 构造一个复数 // c [out]: 复数，构造结果 // v1 [in]: 实数，作为复数实部 // v2 [in]: 实数，作为复数虚部 void InitComplexNumber(&c,v1,v2); // 复数相加 // c1 [in]: 复数，被加数 // c2 [in]: 复数，加数 // return : 复数，和 ComplexNumber PlusComplexNumber(c1,c2); …… } End ADT ComplexNumber 2019/4/22 数据结构及其算法 第2章 数据结构导论
复数ADT用C++语言实现 #include <stdio.h> struct ComplexNumber { double real, imag; void InitComplexNumber(double v1, double v2) { this->real = v1; this->imag = v2; } ComplexNumber PlusComplexNumber(ComplexNumber c2) { ComplexNumber res; res.real = this->real + c2.real; res.imag = this->imag + c2.imag; return res; }; int main() { ComplexNumber c1, c2; c1.InitComplexNumber(3, 2); c2.InitComplexNumber(2, -3); ComplexNumber res = c1.PlusComplexNumber(c2); printf("%g%+gi\n", res.real, res.imag); 2019/4/22 数据结构及其算法 第2章 数据结构导论
2.3 算法概述 问题(Problem) 算法(Algorithm) 程序(Program) 计算机求解的问题往往附加对计算资源的限制，如合理的 运行时间、内存占用等 算法(Algorithm) “一个算法，就是一个有穷规则的集合，其中之规则定义 了一个解决某一特定类型问题的运算序列” 一个问题可以有多种算法，但一个算法只能解决一种特定 类型的问题 正确性、具体性、确定性、有限性、可终止性 程序(Program) 一个算法使用某种程序设计语言的具体实现 一个算法可以有多个不同的程序实现，但有的程序不对应 于算法 2019/4/22 数据结构及其算法 第2章 数据结构导论
最大公约数问题 #include <stdio.h> int algo1(int m, int n) { for (int i = n; i >= 1; --i) { if (m % i == 0 && n % i == 0) return i; } int algo2(int m, int n) { int r = m % n; while (r) { m = n; n = r; r = m % n; return n; int main() { int m = 123456789, n = 87654321; printf("%d %d\n", algo1(m, n), algo2(m, n)); 2019/4/22 数据结构及其算法 第2章 数据结构导论
算法评价标准 正确性 可读性 健壮性 高效性 简洁性 2019/4/22 数据结构及其算法 第2章 数据结构导论
2.4 算法分析 算法设计的目标 算法效率分析 简便算法：容易理解、方便编码和调试 高效算法：运行时间短、占用空间少 时间复杂度：运行时间 空间复杂度：占用空间 2019/4/22 数据结构及其算法 第2章 数据结构导论
如何评价算法的时间复杂度？ 方法1：事后统计 方法2：事前估算 编程实现该算法，测算程序的运行时间 优点：最准确 缺点：需要先编写程序，运行时间依赖于硬件环境、程序 实现、输入数据等因素 方法2：事前估算 根据算法的步骤，估计算法的运行时间 优点：不需要编写程序，与硬件环境、程序实现无关，可 估算不同输入数据的不同情况 缺点：未必准确 2019/4/22 数据结构及其算法 第2章 数据结构导论
语句的频度(frequency count)：执行次数 算法的执行时间一般是问题规模的函数 “理想机器”模型 单个CPU、无限大内存 每个基本语句的执行时间都是1单位 例：矩阵乘法 语句的频度(frequency count)：执行次数 算法的执行时间一般是问题规模的函数 语句 执行次数 执行时间 1 2m+2 2 m(2p+2) 3 mp 4 mp(2n+2) 5 mnp 2mnp 合计 4mnp+5mp+4m+2 for (int i = 0; i < m; ++i) { for (int j = 0; j < p; ++j) { c[i][j] = 0.0; for (int k = 0; k < n; ++k) { c[i][j] += a[i][k] * b[k][j]; } 1 2 3 4 5 2019/4/22 数据结构及其算法 第2章 数据结构导论
采用事前估算法得到算法的运行时间一般表示为问 题规模n的某个数量级函数f(n)，称为算法的渐近 时间复杂度，记作T(n)=O(f(n)) 常用数量级函数： O(1) O(log2n) O(n) O(nlog2n) O(n2) O(nk) O(2n) O(n!) O(nn) 2019/4/22 数据结构及其算法 第2章 数据结构导论
循环语句只考虑循环体，多层循环只考虑最内层 利用O的加法和乘法规则 T(n)=O(n2) 例：分析算法的渐近时间复杂度 基本语句的时间是O(1) 循环语句只考虑循环体，多层循环只考虑最内层 利用O的加法和乘法规则 T(n)=O(n2) 1 2 3 4 int x = 0; for (int i = 2; i <= n; ++i) { for (int j = 2; j <= i - 1; ++j) { a[i][j] = x++; } 2019/4/22 数据结构及其算法 第2章 数据结构导论
算法的执行时间不仅取决于问题规模，还与具体输 入数据有关 最好、最坏、平均时间复杂度 例：冒泡排序 算法的执行时间不仅取决于问题规模，还与具体输 入数据有关 最好、最坏、平均时间复杂度 void BubbleSort(int *a, int n) { bool change = true; int t; for (int i=n-1; i>=1 && change; --i) { change = false; for (int j=0; j<i; ++j) { if (a[j] > a[j+1]) { change = true; t = a[j]; a[j] = a[j+1]; a[j+1] = t; } 最好情况： 数组恰好是正序的 O(n) 最坏情况： 数组恰好是逆序的 O(n2) 2019/4/22 数据结构及其算法 第2章 数据结构导论
采用事前估算法，一般表示为问题规模n的某个数 量级函数g(n)，记作S(n)=O(g(n)) 如何评价算法的空间复杂度？ 采用事前估算法，一般表示为问题规模n的某个数 量级函数g(n)，记作S(n)=O(g(n)) 一般不考虑输入、输出所占用的存储空间，只考虑 算法需要的额外存储空间 常见算法的空间复杂度都是O(1)，称为原地工作 void BubbleSort(int *a, int n) { bool change = true; int t; for (int i=n-1; i>=1 && change; --i) { change = false; for (int j=0; j<i; ++j) { if (a[j] > a[j+1]) { change = true; t = a[j]; a[j] = a[j+1]; a[j+1] = t; } 冒泡排序的额外存储是change,t,i,j 空间复杂度为O(1) 2019/4/22 数据结构及其算法 第2章 数据结构导论
本章复习提纲 数据结构的基本概念 算法 算法分析：时空复杂度 逻辑结构与存储结构 抽象数据类型 2019/4/22 数据结构及其算法 第2章 数据结构导论
作业 2.2 (△是指第一个语句) 2.2 求语句频度 2019/4/22 数据结构及其算法 第2章 数据结构导论