第1章 绪论 2019/4/16

课程信息 教师 联系方式 黄诚 Email：huangcheng@swpu.edu.cn Tel：13550301222 QQ：449557241 2019/4/16

课程信息 教材 参考 数据结构（C语言版），严蔚敏等编，清华大学出版社 算法与数据结构，傅清祥等，电子工业出版社，1998 算法导论（第2版），Cormen等，机械工业出版社，2006 计算机程序设计艺术（第3版）（Vol.1-3），D. E. Knuth，清华大学出版社，2002 2019/4/16

课程信息 目的：培养数据抽象能力 要求：获得算法及数据结构的基础知识和技能；进行复杂程序设计训练 帮助程序员（更有效地）组织数据、设计（高效的）算法、完成（高质量的）程序 要求：获得算法及数据结构的基础知识和技能；进行复杂程序设计训练 分析数据结构特性，为应用选择适当数据结构及相应算法，初步掌握算法时间分析和空间分析技术 完成的程序结构清楚、正确易读、符合规范 2019/4/16

课程信息 地位 计算机专业的核心课程之一 专业基础课 算法分析与设计、操作系统、软件工程、数据库概论、编译技术、计算机图形学、人机交互等专业基础课和专业课程的先行课程 语言编译要使用栈、散列表及语法树 操作系统中用队列、存储管理表及目录树等 数据库系统运用线性表，多链表及索引树等进行数据管理 人工智能领域，依求解问题性质的差异将涉及到各种不同的数据结构，如广义表，集合、搜索树及各种有向图等等 2019/4/16

数据结构在计算机科学中的地位 2019/4/16

课程信息 预备 计算机科学导论 C语言程序设计 离散结构1, 2 2019/4/16

数据结构学科背景 应用领域 处理对象 数值计算 非数值处理 数值、字符、表格、图象、动画、音/视频 etc. 工程、科学计算 2019/4/16

1.1 什么是数据结构 程序 = 数据结构+算法 例1 书目自动检索系统 书目卡片 线性表 登录号： 书名： 作者名： 分类号： 出版单位： 书目文件 登录号： 书名： 作者名： 分类号： 出版单位： 出版时间： 价格： 书目卡片 按书名 按作者名 按分类号 索引表 2019/4/16

树 例2 人机对奕问题 …….. …...

多叉路口交通灯管理问题 图 C E D A B AB AC AD BA BC BD DA DB DC EA EB EC ED 2019/4/16

数据结构（学科）定义 数据结构（学科） Donald E. Knuth 一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科 Donald E. Knuth 2019/4/16

1.2 基本概念和术语 数据（data) 数据元素（data element） 数据项（data item） 所有能输入计算机中的描述客观事物的符号 数据元素（data element） 数据的基本单位，也称节点（node）或记录（record）（如：一本书的书目） 数据项（data item） 有独立含义的数据最小单位，也称域(field)（如：书名） 数据对象(data object) 性质相同的数据元素的集合,数据的一个子集。 数据结构（data structure) 数据元素和数据元素关系的集合 2019/4/16

（数据）逻辑结构 抽象反映数据元素的逻辑关系 数据元素间关系：有四个基本类型 （集合）：数据元素间除“同属于一个集合”外，无其它关系 线性结构：一个对一个，如线性表、栈、队列 树形结构：一个对多个，如树 图状结构：多个对多个，如图 （数据）逻辑结构 抽象反映数据元素的逻辑关系 2019/4/16

（数据）物理结构 （数据）逻辑结构在计算机存储器中的实现 数据间关系在计算机存储器中的表示方法 顺序：用存储器中元素的相对位置表示元素间的逻辑关系 链式：用表示元素存储地址的指针表示元素间的逻辑关系 数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 2019/4/16

顺序存储 存储地址 存储内容 元素1 Lo 元素2 Lo+m …….. “一维数组” 元素i Lo+(i-1)*m …….. 元素n Lo+（n-1)*m 元素 i 的存储地址公式：Loc (i) = Lo+（i-1) * m 2019/4/16

存储地址 存储内容 分量1 Lo 分量2 Lo+ m0 …….. 顺序存储 “结构” 分量i …….. 分量n 2019/4/16

h “指针” h ∧ 存储地址 存储内容 指针 1345 元素1 1400 1346 元素4 ∧ ……. …….. 元素2 1536 元素3 链式存储 “指针” 1536 元素2 1400 元素1 1346 元素3 ∧ 元素4 1345 h 单链表 2019/4/16

建立/清除、插入/删除/修改、检索/排序、 etc. 线性表 栈、队列 线性结构 文件 逻辑结构 树形结构 非线性结构 数据结构 图形结构 顺序存储（数组） 数据间关系的存储 链式存储（指针） 数据运算 建立/清除、插入/删除/修改、检索/排序、 etc. 2019/4/16

1、数据类型 高级程序设计语言提供了实现所需数据结构的手段 在高级程序设计语言中，定义了多种数据类型，规定了数据取值范围及这类数据上允许进行的操作 C 语言 基本数据类型：int, char, float, double 等 构造数据类型：数组、结构、共用、枚举、指针等 自定义数据类型：typedef 2019/4/16

2、抽象数据类型(Abstract Data Type, ADT) 一个数学模型和在该模型上定义的操作的集合 高级程序设计语言提供了实现所需数据结构的手段 2、抽象数据类型(Abstract Data Type, ADT) 一个数学模型和在该模型上定义的操作的集合 C ++ 语言 (抽象)类：class 数据成员：可看成一个数据结构 成员方法：数据结构上的允许操作 2019/4/16

1.4 算法的描述和算法分析 算法（algorithm）：解决某一特定问题的具体步骤的描述，是指令的有限序列 算法特性： 有穷性：算法必须在有限时间内结束 确定性：只要输入不变，算法运行结果就确定不变 可行性：算法的每个步骤都能用 输入：0~n 个 输出：1~n 个 2019/4/16

算法与程序 算法的描述 程序不一定满足有穷性！操作系统 程序指令必须是机器可执行，算法指令无此限制 算法代表问题的解，程序是算法在计算机上的特定实现 程序是算法的程序设计语言描述形式 算法的描述 自然语言、流程图、程序设计语言、伪码语言 2019/4/16

算法的评价：什么是“好”的算法 正确性 (correctness) 时间效率与存储量 (complexity) 可读性 健壮性 算法执行结果能满足问题的（功能和性能）需求 时间效率与存储量 (complexity) 较高时间效率、有效使用存储空间 可读性 思路清晰、层次分明、简单明了、易读易懂 健壮性 输入出错时，能做适当反应 2019/4/16

④ 对于一切合法的输入均得到满足要求的结果 ⑤ 对于一切合法的输入算法均能在有限时间内结束 算法的“正确性” ① 不含语法错误 ② 对于几组输入数据能得到满足要求的结果 ③ 对精心选择苛刻并带有刁难的数据能得到满足要求的结果 ④ 对于一切合法的输入均得到满足要求的结果 ⑤ 对于一切合法的输入算法均能在有限时间内结束 2019/4/16

依据该算法编制的程序在计算机上执行所消耗的时间 执行时间的度量方法 算法效率（执行时间） 依据该算法编制的程序在计算机上执行所消耗的时间 执行时间的度量方法 1、事后统计 2、事前估计 2019/4/16

执行时间的度量方法 1、事后统计 与算法本身无关 用绝对时间单位衡量算法的时间效率不合适！ 利用计算机内记时功能，不同算法的程序可以用一组或多组相同的数据来区分其优劣； 特点：先写程序、再算时间 但是：影响程序运行时间的因素可以有 算法选用何种策略 问题规模 程序语言 编译程序产生的机器代码的质量 机器执行指令速度 与算法本身无关 用绝对时间单位衡量算法的时间效率不合适！ 2019/4/16

执行时间的度量方法 2、事前估计 包含在算法内 规模增大，算法执行时间增大 影响程序运行时间的因素 算法选用何种策略 问题规模 程序语言 编译程序产生的机器代码的质量 机器执行指令速度 包含在算法内 规模增大，算法执行时间增大 2019/4/16

算法中某条语句重复执行的次数：语句的频度 算法所有语句重复执行的次数是：算法的频度 语句/算法的频度是问题规模 n 的函数 f(n) 随着规模的增大，频度函数值增大，算法执行时间增大 举例：(a) x=x+1; s= 0 ; f(n) = 2 (b) for ( i=1 ; i <= n ; ++i ) { x=x+1; s =s+ x; } f(n) = 3n+1 2019/4/16

i 举例：(c) for ( i=1; i<=n ; ++i ) for( j=1 ; j <=n ; ++j ) { x=x+1 ; s = s + x; } f(n) = 3n2+4n+1 (d) for ( i=1; i<=n ; ++i ) for ( j=1 ; j <=n ; ++j ) { c[i][j] = 0; for ( k=1 ; k <= n; ++k ) c[i][j] += a[i][k] * b[k][j] ; } f(n) = 4n3+9n2+6n+1 i 2019/4/16

对算法执行时间贡献最大的语句：基本操作 算法中某条语句重复执行的次数：语句的频度 算法所有语句重复执行的次数是：算法的频度 语句/算法的频度是问题规模 n 的函数 f(n) 对算法执行时间贡献最大的语句：基本操作 基本操作的频度函数也是问题规模 n 的函数 举例：基本操作 x=x+1 (a) x=x+1; s= 0 ; f(n) = 1 (b) for ( i=1 ; i <= n ; ++i ) { x=x+1; s =s+ x; } f(n) = n 2019/4/16

i 基本操作？ 举例：基本操作 x=x+1 (c) for ( i=1; i<=n ; ++i ) for( j=1 ; j <=n ; ++j ) { x=x+1 ; s = s + x; } f(n) = n2 (d) for ( i=1; i<=n ; ++i ) for ( j=1 ; j <=n ; ++j ) { c[i][j] = 0; for ( k=1 ; k <= n; ++k ) c[i][j] += a[i][k] * b[k][j] ; } f(n) = n3 i 基本操作？ 2019/4/16

(渐近)时间复杂度：基本操作频度函数的化简形式 对算法执行时间贡献最大的语句：基本操作 基本操作的频度函数也是问题规模 n 的函数 算法执行时间的增长率与基本操作频度函数的增长率相同 时间复杂度：基本操作的频度函数 (渐近)时间复杂度：基本操作频度函数的化简形式 只留最高次项、去掉最高次项的常系数 记号：T(n)= O ( f(n) ) 随问题规模 n 的增大，算法执行时间 T(n) 的增长率和 f(n) 的增长率相同 2019/4/16

i 举例：(a) x = x + 1 ; f(n) = 1; T1(n) = O(f(n)) = O(1) 常量阶 (b) for ( i=1 ; i <= n ; ++i ) x = x+1; f(n) = n; T2(n) = O(f(n)) = O(n) 线性阶 (c) for ( i=1; i<=n ; ++i ) for( j=1 ; j <= n ; ++j ) x = x+1 ; f(n) = n2; T3(n) = O(f(n)) = O(n2) 平方阶 i 2019/4/16

举例：(d) for ( i=1; i<=n ; ++i ) for ( j=1 ; j <=n ; ++j ) { c[i][j] = 0; for ( k=1 ; k <= n; ++k ) c[i][j] += a[i][k] * b[k][j] ; } f(n) = n3; T4(n) = O(f(n)) = O(n3) 立方阶 2019/4/16

f(n) = log2n; T4(n) = O(f(n)) = O( lg n) 对数阶 举例： (e) i=n; while ( i >=1 ) { x = x + 1; i = i /2 ; } f(n) = log2n; T4(n) = O(f(n)) = O( lg n) 对数阶 2019/4/16

for ( j=1; j<=n; j++) x = x + 1; i = i /2 ; } 练习 (1) i=n; while ( i >=1 ) { for ( j=1; j<=n; j++) x = x + 1; i = i /2 ; } f(n) = nlog2n; T(n) = O(f(n)) = O(n lg n) 2019/4/16

f(n) = log2(log2n); T(n) = O(f(n)) = O( lg (lg n) ) 练习 (2) i=2; while ( i < n ) { i = i * i ; x = x + 1; } f(n) = log2(log2n); T(n) = O(f(n)) = O( lg (lg n) ) 2019/4/16

基本操作？ 举例： (f) long fact ( int n) { if ( n==0 ) || ( n ==1 ) return( 1 ); else return( n * fact( n – 1 ) ); } 乘法次数 f( n )= 1 当 n=0, n=1 1 + f( n – 1 ) 当 n > 1 基本操作？ f( n ) = 1+f( n – 1) f( n – 1) = 1 + f( n – 2) f( n – 2) = 1 + f( n – 3) … … f( 2 ) = 1 + f( 1 ) f( 1 ) = 1 f( n ) = 1 + 1 + 1 +……+1+1 f( n ) = n ∴ T( n ) = O( f( n ) ) = O( n ) 2019/4/16

(g) void bubble_sort ( int a[], int n) { int i, j, change; 举例： (g) void bubble_sort ( int a[], int n) { int i, j, change; for ( i = n-1; i>=1 && change; --i ) { change=FALSE; for ( j=0; j<i; ++j ) if ( a [j] > a [j+1] ) { t = a [j]; a [j] = a [j+1]; a [j+1] = t; change=TRUE; } Best 1 n-1 Worst 1 n-1 n(n-1)/2 Average ? O(n2) 基本操作？ O(n) O(n2) 2019/4/16

算法(时间) 效率的度量 (渐近)时间复杂度(函数)：T(n)= O ( f(n) ) 复杂度函数 客观度量算法的效率 函数增长趋势 方法：化简基本操作(语句)的频度函数 本质：随着问题规模的增长，算法执行时间的增长趋势 优点：与实现算法的平台、语言无关 － 用途： 复杂度函数 客观度量算法的效率 函数增长趋势 正确比较算法的优劣 2019/4/16

不同函数类型的增长趋势 程序运行时间比较 T (n) = O ( f(n) ) T(n) n 1000 2000 3000 5 10 15 1000 2000 3000 5 10 15 20 25 2n n3 100n 5n2 logn 2100 △n △ T(n) 2019/4/16

输入规模成倍增长时不同时间效率函数的变化趋势 10 20 30 40 50 60 .00001 .00002 .00003 .00004 .00005 .00006 second second second second second second .0001 .0004 .0009 .0016 .0025 .0036 .001 .008 .027 .064 .125 .216 .1 3.2 24.3 1.7 5.2 13.0 second second second minutes minutes minutes .001 1.0 17.9 12.7 35.7 366 second second minutes days years centuries .059 58 6.5 3855 2*108 1.3 *1013 second minutes years centuries centuries centuries n n2 n3 n5 2n 3n T(n) IBM 486 2019/4/16

计算机速度成倍增长时处理能力的增长趋势 n n2 n3 2n 3n 100n 10n 4.64n n+6.64 1000n 31.6n T(n) 当前速度 100 倍速度 1000 倍速度 n! n + 小常数 n + 极小常数 2019/4/16