算法与数据结构第 1 章 概论

1、算法与数据结构许亮2算法与数据结构w 课程名称：算法与数据结构课程名称：算法与数据结构w 先修课程：先修课程：C语言程序设计语言程序设计w 后续课程：微机原理及应用后续课程：微机原理及应用 单片机原理及应用单片机原理及应用w 教材：算法与数据结构教材：算法与数据结构-C语言描述语言描述 张乃孝编著张乃孝编著w 参考资料：参考资料： 1、数据结构（、数据结构（C语言版）语言版） 严蔚敏严蔚敏 吴伟民吴伟民 编著编著 2、数据结构题集（、数据结构题集（C语言版）语言版） 严蔚敏严蔚敏 吴伟民吴伟民 编著编著3、数据结构、数据结构 唐策善等编唐策善等编4、算法与数据结构、算法与数据结构 陈守孔等编陈

2、守孔等编w 教师：电子信息教研室教师：电子信息教研室 许亮许亮 3课程成绩的考核 平时（出勤、作业、上课）占平时（出勤、作业、上课）占50%； 期末考试占期末考试占50；4第1章 概论 本章目录w 1.1 从问题到程序从问题到程序n1.1.1 问题分析与抽象问题分析与抽象 n1.1.2 程序的设计与实现程序的设计与实现w 1.2 基本概念和术语基本概念和术语w 1.3 抽象数据类型抽象数据类型w 1.4 算法算法n1.4.1 算法算法n1.4.2 算法的设计算法的设计n1.4.3 算法的精化算法的精化n1.4.4 算法的分析算法的分析51.11.1从问题到程序从问题到程序w当我们使用计算机来解

3、决一个具体问题当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤：时，一般需要经过下列几个步骤： 实际实际问题提出问题提出 需求模型需求模型抽象抽象问题模型问题模型 数学模型数学模型 实现模型实现模型 程序程序 是使用程序设计语言精确描述的实现模型是使用程序设计语言精确描述的实现模型程序就是在程序就是在数据数据的某些特定的结构和表示的基础的某些特定的结构和表示的基础上对于上对于算法算法的描述。的描述。61.11.1从问题到程序从问题到程序w 计算机的用途：计算机的用途： 微分方程微分方程数值运算数值运算 数学模型数学模型 代数方程组等代数方程组等非数值运算：数据结构讨论的内非数值运

4、算：数据结构讨论的内容（应用更为广泛）容（应用更为广泛）71.11.1从问题到程序从问题到程序w为一个实际问题建立一个正确的求解程为一个实际问题建立一个正确的求解程序，通常可以分成以下四个阶段：序，通常可以分成以下四个阶段： 分析阶段：分析阶段：建立模型（需求或数学模型）建立模型（需求或数学模型）设计阶段：设计阶段：算法和数据结构的设计（实现模型）算法和数据结构的设计（实现模型）编码阶段：编码阶段：编写可执行程序编写可执行程序调试和维护调试和维护81.1.1问题分析与抽象信号灯问题AEDCB考虑一个多叉路口，其C，E为单行线，其余为双行线；任务：设计一个安全有效的交通信号灯的管理系统分析：1、

5、分为13组（可能的行驶方向），每次一组通行，最安全，但效率低。2、尽可能分组少，这样效率高。ABACADBABCBDDADBDCEDECEBEA91.1.1问题分析与抽象信号灯问题AEDCB抽象后：1、有连线代表有冲突，在不同组里。2、BA、DC、ED为右转，可以任何时许都通行，也可进行控制，看问题的复杂程度。ABACADBABCBDDADBDCEDECEBEAABACADBABCBDDADBDCEDECEBEA交叉路口行驶冲突的模型可行解最优解次优解101.1.2程序的设计与实现一、选择算法：1、穷举法2、贪心法ABACADBABCBDDADBDCEDECEBEA二、选择抽象数据类型三、算法

6、的描述四、数据结构的设计五、算法的精化与代码生成11例1.1 考生录取信息系统考号考号姓名姓名性别性别报考专业报考专业成绩成绩23004112300411李闽志李闽志男男计算机科学与技术计算机科学与技术65865810004721000472于惠芳于惠芳女女英语英语63263215063021506302刘刘 红红女女应用数学应用数学61761721059022105902宋大明宋大明男男英语英语60060009347850934785高大庆高大庆男男计算机科学与技术计算机科学与技术60160106008070600807何文丽何文丽女女英语英语61161108785290878529隋文涛隋

7、文涛男男应用数学应用数学61261216908341690834崔秀海崔秀海男男英语英语60260217106411710641于众群于众群女女计算机科学与技术计算机科学与技术61961919001621900162魏人民魏人民男男英语英语67167112考生录取信息系统w计算机计算机处理的对象处理的对象是表是表w元素间的关系元素间的关系是线性关系是线性关系w施加于对象上的施加于对象上的操作操作有查询、插入、有查询、插入、删除等删除等13例1.2 人机博弈 14国际象棋wDeep Blue: 2亿结点亿结点/秒，秒，60万种棋局，万种棋局，评价函数有评价函数有8000个参数；个参数；w计算机预

8、见计算机预见1015步步，心理学家认，心理学家认为，为，人类选手只能预测人类选手只能预测35步步；w棋局中期计算机往后看棋局中期计算机往后看75步步。15人机博弈w计算机计算机处理的对象处理的对象是树型结构是树型结构w元素间的关系元素间的关系是层次关系是层次关系w施加于对象上的施加于对象上的操作操作有查询、插有查询、插入、删除等入、删除等16例例1.3 1.3 哥尼斯堡七桥问题哥尼斯堡七桥问题 问题问题： 怎样才能够从某块陆地出发，经怎样才能够从某块陆地出发，经过每座桥一次且仅一次最后回到出发点。过每座桥一次且仅一次最后回到出发点。 B A D C 17哥尼斯堡七桥问题哥尼斯堡七桥问题 w计算

9、机计算机处理的对象处理的对象是图是图w元素间的关系元素间的关系是复杂的图形或网状关是复杂的图形或网状关系系w施加于对象上的施加于对象上的操作操作有查询、插入、有查询、插入、删除等删除等18数据结构研究的内容 由以上三个例子可见，描述这类由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构。因此，简单说来，数据结数据结构是一门研究构是一门研究非数值计算非数值计算的程序设计的程序设计问题中计算机的问题中计算机的操作对象操作对象以及它们之以及它们之间的间的关系关系

10、和和操作操作的学科。的学科。191.2基本概念和术语w 数据数据(Data)：客观事物在计算机中的符号客观事物在计算机中的符号表示，是表示，是能被计算机识别和处理的符号总能被计算机识别和处理的符号总称。称。w 数据元素数据元素(Data Element)：数据的数据的基本单基本单位位，用于完整地描述一个对象，用于完整地描述一个对象; (也称为：也称为：记录，元素，结点，顶点等）记录，元素，结点，顶点等）w 数据项数据项(Data Item)：组成数据元素的有特组成数据元素的有特定意义的定意义的最小的不可分割的单位最小的不可分割的单位 。201.2基本概念和术语w数据的三个层次数据的三个层次数据

11、数据数据元素数据元素 数据项数据项w数据对象数据对象(Data Object)：具有相同特具有相同特性的数据元素的性的数据元素的集合集合，是数据的一个，是数据的一个子集子集;211.2基本概念和术语w 数据结构数据结构：相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的数据元的数据元素的集合。素的集合。w 形式定义形式定义：数据结构是一个二元组数据结构是一个二元组Data_StructureData_Structure （D D，R R）, ,其中，其中，D是数据元素的有限集，是数据元素的有限集，R是是D上上关系关系的有限集。的有限集。例 复数的数据结构定义如下： Complex=

12、(C，R)其中：C是含两个实数的集合C1，C2，分别表示复数 的实部和虚部。 R=P，P是定义在集合上的一种关系C1，C2。221.2基本概念和术语w 数据结构数据结构：相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的数据元的数据元素的集合。素的集合。w 形式定义形式定义：数据结构是一个二元组数据结构是一个二元组Data_StructureData_Structure （D D，R R）, ,其中，其中，D是数据元素的有限集，是数据元素的有限集，R是是D上上关系关系的有限集。的有限集。w “关系关系”：描述的是数据元素之间的逻辑关系，因此又描述的是数据元素之间的逻辑关系，因此又称

13、为称为逻辑结构逻辑结构 。算法的设计取决于选定的逻辑结构。算法的设计取决于选定的逻辑结构。w 数据结构在计算机中的表示称为数据的数据结构在计算机中的表示称为数据的物理结构物理结构，又称，又称存储结构存储结构。算法的实现依赖于采用的存储结构。算法的实现依赖于采用的存储结构。23逻辑结构：数据元素之间的逻辑关系数据元素之间的逻辑关系w 数据的逻辑结构是本质，可以分为： 线性结构线性结构和和非线性结构，非线性结构，也可以分为也可以分为集合：集合：线性结构：线性结构：树形结构：树形结构：图状结构图状结构：（复杂结构）：（复杂结构）24存储结构：数据结构在计算机中的表示。数据结构在计算机中的表示。a0a

14、n-11000a1a210021004a0a2a3a1300020001000顺序存储结构顺序存储结构：借助元素在存储器中的相对位借助元素在存储器中的相对位置表示数据元素之间的关系。置表示数据元素之间的关系。链式存储结构链式存储结构：借助指示元素存储地址的指针（借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。表示数据元素之间的逻辑关系。25物理（存储）结构的分类w 物理（存储）结构的分类物理（存储）结构的分类顺序存储结构：顺序存储结构：它是把逻辑上相邻的节点存储在物理位置相信的存储它是把逻辑上相邻的节点存储在物理位置相信的存储单元里，节点的逻辑关系由存储单元的邻接关系来

15、体现。单元里，节点的逻辑关系由存储单元的邻接关系来体现。链式存储结构：链式存储结构：它不要求逻辑上相信的节点在物理位置上亦相邻，节它不要求逻辑上相信的节点在物理位置上亦相邻，节点之间的逻辑关系是由附加的指针字段表示的。点之间的逻辑关系是由附加的指针字段表示的。索引存储结构：索引存储结构：除建立存储节点信息外，还建立附加的索引表来标识除建立存储节点信息外，还建立附加的索引表来标识节点的地址。节点的地址。散列存储结构：散列存储结构：根据节点的关键字直接计算出该节点的存储地址。根据节点的关键字直接计算出该节点的存储地址。26 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检

16、索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结构图形结构数据结构的三个方面：数据结构的三个方面：271.3抽象数据类型w 抽象数据类型抽象数据类型:（Abstract Data Type）ADT:一一个数学模型个数学模型以及定义在该模型上的以及定义在该模型上的一组操作一组操作。 抽象数据类型的定义取决于它的一组抽象数据类型的定义取决于它的一组逻辑特逻辑特性性，而与其在计算机内部如何表示和实现无关。，而与其在计算机内部如何表示和实现无关。即不论其内部结构

17、如何变化，只要它的即不论其内部结构如何变化，只要它的数学特数学特性不变性不变，都不影响其外部的使用。，都不影响其外部的使用。281.3抽象数据类型w 抽象数据类型的定义：抽象数据类型的定义：ADT 抽象数据类型名抽象数据类型名 数据对象数据对象：数据对象定义：数据对象定义 数据关系数据关系：数据关系定义：数据关系定义 基本操作基本操作：基本操作定义：基本操作定义ADT 抽象数据类型名抽象数据类型名w 基本操作的定义格式为：基本操作的定义格式为：基本操作名（参数表）基本操作名（参数表） 初始条件初始条件：初始条件描述：初始条件描述 操作结果操作结果：操作结果描述：操作结果描述29u 算法与数据结

18、构关系密切算法与数据结构关系密切 选择的数据结构是否恰当直接影响算法的选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来效率；而数据结构的优劣由算法的执行来体现。体现。u N.Wirth Algorithms+Data Structures=Programs1.4算法301.4算法w 算法算法（Algorithm）：是对特定问题求解步骤的一是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：或多个操作。一个算法应该具有下列特性：有穷性有穷性：执行有限步，每步有限的时间

19、执行有限步，每步有限的时间。确定性确定性：每条指令有确切含义，相同输入只能得到相同输出。每条指令有确切含义，相同输入只能得到相同输出。可行性可行性：操作通过已实现的基本运算执行有限次来实现。：操作通过已实现的基本运算执行有限次来实现。输入输入：零个至多个零个至多个输入。输入。输出输出：一个至多个一个至多个输出。输出。1.4.1算法算法（Algorithm）311.4.2算法的设计w算法设计的方法：算法设计的方法：贪心法贪心法分治法分治法回溯法回溯法动态规划法动态规划法分枝界限法分枝界限法32w 算法设计的要求：算法设计的要求：l正确性正确性(correctness)： 1、不含语法错误 2、对

20、于几组输入数据能够得出满足规格说明要求的结果 3、对于精心选择的典型、苛刻而带有刁难性的数据能够得出满足规格说明要求的结果 4、对于一切合法的输入数据都能产生满足规格说明要求的结果l可读性可读性(readability)：人的阅读与交流l健壮性健壮性(robustness)：当输入非法数据时，算法能够适当的做出反应或进行处理，不会产生莫名其妙的结果l效率与低存储量：效率与低存储量：算法的执行时间和所需的最大存储空间1.4.2算法的设计33w 排序问题排序问题l初始条件：初始条件：n个待排序的数个待排序的数a0an-1l结果：排序后结果：排序后a0an-1从小到大排列从小到大排列 算法思想：直接

21、选择排序 1）从a中选出一个最大的整数放到一个空的数组a中，作为a中的第一个元素。 2）从a中剩下的元素中再选出最大的整数放到a中，接在前一个已放入元素的后面。 反复执行步骤2)，直到a中所有的整数都放到排好序的数组a中。1.4.3算法的精化34w 排序问题排序问题 第一步精化： 1）i从n-1直到i=2做（2）（3）步 2）j从0直到j=i-1做（3） 3）若ajaj+1则交换它们 4）算法结束Void sortIntArray(int a,int n) for(i=n-1;i0;-i) for(j=0;jaj) t=ak;ak=aj;aj=t; /sortIntArray1.4.3算法的精

22、化35w 排序问题排序问题 第二步精化： 1）置标记change=TRUE； 2）i从n-1直到i=2做（3）（6）步 3）change=FALSE； 4）j从0直到j=i-1做（5） 5）若ajaj+1则交换它们并置change=TRUE； 6）若change=FALSE则结束 7）算法结束1.4.3算法的精化36算法效率的度量（时间复杂度和空间复杂度）w 衡量算法效率的方法主要有两大类：衡量算法效率的方法主要有两大类： n事后统计：利用计算机的时钟；事后统计：利用计算机的时钟； (不可取不可取)n事前分析估算：用高级语言编写的程序运行的时事前分析估算：用高级语言编写的程序运行的时间主要取决

23、于如下因素：间主要取决于如下因素：l算法选用的策略；算法选用的策略；l问题规模；问题规模；l使用语言：级别越高，效率越低；使用语言：级别越高，效率越低；l编译程序；编译程序；l机器执行指令的速度；机器执行指令的速度；1.4.4算法的分析37时间复杂度w 算法的运行工作量的大小就只依赖于算法的运行工作量的大小就只依赖于问题的规模问题的规模（通常用正整数（通常用正整数n n表示），或者说它是表示），或者说它是问题规模问题规模n的函数的函数。记。记T(nT(n) )，称为该算法的称为该算法的时间复杂度时间复杂度w 算法主要由程序的算法主要由程序的控制结构控制结构（顺序，分支，循环）（顺序，分支，循环

24、）和和原操作原操作（必需的操作）构成，算法的时间主要（必需的操作）构成，算法的时间主要取决于两者。取决于两者。w 度量算法运行时间：度量算法运行时间： “原操作原操作”的的执行次数执行次数38+x; s=0;语句频度语句频度为1，时间复杂度为时间复杂度为O(1)O(1)。 时间复杂度-举例常量阶O(1)for(j=1;j=10000;+j)+x; s+=x;语句频度语句频度为为10000，时间复杂度为时间复杂度为O(1)O(1)。39时间复杂度-举例对数阶O(logn)s=0;for(j=1; j=n; j*=2)s+;语句频度语句频度为为log2n，所以时间复杂度为所以时间复杂度为O(log2n)。40时间复杂度-举例线性阶O(n)S=0;for(j=1;j=n;+j)s+;语句频度语句频度为为n n，所以所以时间复杂度为时间复杂度为O(nO(n) )。41时间复杂度-举例对数阶O(nlogn)s=0;for(j=