第01章算法PPT讲稿.ppt

《第01章算法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第01章算法PPT讲稿.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第01章算法第1页，共30页，编辑于2022年，星期日1.1 1.1 数据结构的基本概念数据结构的基本概念1.1.基本术语基本术语(1)(1)数据：数据：人们利用文字符号、数字符号以及其他规定的符号对现实世人们利用文字符号、数字符号以及其他规定的符号对现实世界的事物及其活动所做的抽象描述。界的事物及其活动所做的抽象描述。(2)(2)数据元素：数据元素：表示一个事物的一组数据。表示一个事物的一组数据。(3)(3)数据项：数据项：构成数据元素的数据。构成数据元素的数据。例如，学生信息可包括学生的学号、姓名、性别、年龄等数据。这例如，学生信息可包括学生的学号、姓名、性别、年龄等数据。这些数据构成学生

2、情况的描述的数据项；包括学号、姓名、性别、年些数据构成学生情况的描述的数据项；包括学号、姓名、性别、年龄等数据项的一组数据就构成学生信息的一个数据元素。龄等数据项的一组数据就构成学生信息的一个数据元素。第2页，共30页，编辑于2022年，星期日学生信息数据元素的表示方法是：学生信息数据元素的表示方法是：struct Studentlong number;char name10;char sex3;int age;第3页，共30页，编辑于2022年，星期日1.1.基本术语基本术语(续续)(4)(4)抽象数据元素：抽象数据元素：没有实际含义的数据元素。没有实际含义的数据元素。(5)(5)抽象数据类

3、型：抽象数据类型：没有确切定义的数据类型。没有确切定义的数据类型。(6)(6)数据的逻辑结构：数据的逻辑结构：数据元素之间的相互联系方式。数据元素之间的相互联系方式。(7)(7)数据的存储结构：数据的存储结构：数据元素在计算机中的存储方式。数据元素在计算机中的存储方式。(8)数据的操作：数据的操作：对一种数据类型的数据进行的某种处理。对一种数据类型的数据进行的某种处理。(9)数据的操作集合：数据的操作集合：对一种数据类型的数据进行的所有操作。对一种数据类型的数据进行的所有操作。第4页，共30页，编辑于2022年，星期日数数据据的的逻逻辑辑结结构构线性结构：线性结构：除第一个和最后一个数据元素外

4、，每个数除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。据元素只有一个前驱和一个后继数据元素。树结构：树结构：除根结点外，每个数据元素只有一个前驱数除根结点外，每个数据元素只有一个前驱数据元素，可有个或若干个后继数据元素。据元素，可有个或若干个后继数据元素。图结构：图结构：每个数据元素可有个或若干个前驱数据元素和每个数据元素可有个或若干个前驱数据元素和个或若干个后继数据元素。个或若干个后继数据元素。线性结构线性结构树结构树结构图结构图结构第5页，共30页，编辑于2022年，星期日数数据据的的存存储储结结构构顺序存储结构顺序存储结构：把数据元素存储在一块连续地址空间的把

5、数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。邻，数据间的逻辑关系表现在数据元素存储位置关系上。指针指针是指向物理存储单元地址的变量。由数据元素域和指是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。针域组成的一个结构体称为结点。链式存储结构链式存储结构：使用指针把相互直接关联的结点：使用指针把相互直接关联的结点(即直即直接前驱结点或直接后继结点接前驱结点或直接后继结点)链接起来，其特点是逻辑链接起来，其特点是逻辑上相邻的数据元素在物理上

6、不一定相邻，数据间的逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。关系表现在结点的链接关系上。第6页，共30页，编辑于2022年，星期日数数据据的的操操作作从抽象角度从抽象角度，数据的操作主要讨论某种数据类型数据应具，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论；逻辑结构一起讨论；在具体角度下在具体角度下，数据的操作主要讨论操作的具体实现，数据的操作主要讨论操作的具体实现算法。具体角度下的操作实现必须在数据的存储结算法。具体角度下的操作实现必须在数据的存储

7、结构确定后才能进行。构确定后才能进行。C+语言实现具体操语言实现具体操 作的方法是作的方法是把操作设计为相应类的成员函数。把操作设计为相应类的成员函数。数据结构课程主要讨论数据结构课程主要讨论表表、堆栈堆栈、队列队列、串串、数组数组、树树、二叉树二叉树、图图等典型的常用数据结构。在讨论这些典等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。据操作三个方面进行分析讨论。第7页，共30页，编辑于2022年，星期日1.2 1.2 抽象数据类型和软件构造方法抽象数据类型和软件构造方法类型类型是一

8、组值的集合。是一组值的集合。数据类型数据类型是指一个类型和定义在这个类型上的操作集合。是指一个类型和定义在这个类型上的操作集合。抽象数据类型抽象数据类型是指一个逻辑概念上的类型和这个类型上的是指一个逻辑概念上的类型和这个类型上的操作集合。操作集合。数据类型和抽象数据类型的不同之处仅仅在于数据数据类型和抽象数据类型的不同之处仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，而类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新设计抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。的数据类型。第8页，共30页，编辑于2022年，星期日 抽象

9、数据类型抽象数据类型使软件设计成为工业化流水线生产的一使软件设计成为工业化流水线生产的一个中间环节。个中间环节。一方面一方面，根据给出的抽象数据类型的功能定，根据给出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该抽象数义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各操作的具据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；体实现算法；另一方面另一方面，利用已设计实现的抽象数据类型模，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以安全、快速、方便的完成该块，负责设计应用软件的专门公司可以安全、快速、方便

10、的完成该应用软件系统的设计。应用软件系统的设计。软件的设计采用软件的设计采用模块化模块化方法，抽象数据类型就是构造大型方法，抽象数据类型就是构造大型软件的软件的最基本最基本模块。在模块。在C+语言中，语言中，类类就是确定了数据元素就是确定了数据元素存储结构的抽象数据类型的具体实现。存储结构的抽象数据类型的具体实现。第9页，共30页，编辑于2022年，星期日1.3 算法及其时间复杂度算法及其时间复杂度算法算法是描述求解问题方法的操作步骤集合。是描述求解问题方法的操作步骤集合。的一个的一个有限长有限长操作序列。操作序列。描描述述算算法法的的语语言言形形式式1.文字形式文字形式:用中文或英文这样的文

11、字来描述算法。用中文或英文这样的文字来描述算法。2.伪码形式伪码形式:用一种仿程序设计语言的语言来描述算法。用一种仿程序设计语言的语言来描述算法。3.程序设计语言形式程序设计语言形式:用某种程序设计语言描述算法。其用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。算机能调用和运行。第10页，共30页，编辑于2022年，星期日 例例1-1:设计一个把存储在数组中的有设计一个把存储在数组中的有n个抽象数据元素个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为逆置的算法，即

12、要求逆置后的数组中数据元素序列为an-1,a1,a0,并要求原数组中的数据元素值不能被改变。并要求原数组中的数据元素值不能被改变。void Reverse(int n,DataType a,DataType b)int i;for(i=0;in;i+)bi=an-1-i;/把数组把数组a的元素逆置后赋给数组的元素逆置后赋给数组b第11页，共30页，编辑于2022年，星期日 例例1-2:设计一个把存储在数组中的有设计一个把存储在数组中的有n个抽象数据元素个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列为逆置的算法，即要求逆置后的数组中数据元素序列为an-1,a1,a

13、0,并要求原数组中的数据元素值被改变。并要求原数组中的数据元素值被改变。void Reverse(int n,DataType a)int i,m=n/2;DataType temp;for(i=0;im;i+)/进行进行m次调换次调换temp=ai;ai=an-1-i;an-1-i=temp;第12页，共30页，编辑于2022年，星期日算法满足以下性质算法满足以下性质:(1)输入性输入性(2)输出输出性性(3)有限性有限性(4)确定性确定性(5)可执行性可执行性算法设计满足以下目标算法设计满足以下目标:(1)正确性正确性(2)可读性可读性(3)健壮性健壮性(4)高时间效率高时间效率(5)高空

14、间效率高空间效率算法时间效率的度量算法时间效率的度量算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种的时间来度量。方法有两种:(1)事后统计方法事后统计方法(2)事前分析方法事前分析方法第13页，共30页，编辑于2022年，星期日程序运行消耗时间的有关因素程序运行消耗时间的有关因素:(1)书写算法的程序设计语言书写算法的程序设计语言 (2)编译产编译产生的机器语言代码质量生的机器语言代码质量 (3)机器执行指令的机器执行指令的速度速度 (4)问题的规模，即算法的时间问题的规模，即算法的时间效率与

15、算法所处理的数据个数效率与算法所处理的数据个数n的函数关系。的函数关系。算法的时间效率算法的时间效率是算法所处理的数据个数是算法所处理的数据个数n的函数，算法的时间效的函数，算法的时间效率也称作算法的率也称作算法的时间复杂度。时间复杂度。定义定义:T(n)=O(f(n),当且仅当存在正常数当且仅当存在正常数c和和n0，对所有的对所有的n(n n0)满满足足T(n)cf(n)。第14页，共30页，编辑于2022年，星期日 例例1-3 设数组设数组a和和b在前边部分已赋值，求如下两个在前边部分已赋值，求如下两个n阶矩阵相阶矩阵相乘运算算法的时间复杂度。乘运算算法的时间复杂度。for(i=0;in;

16、i+)for(j=0;jn;j+)cij=0;/基本语句基本语句1for(k=0;kn;k+)cij=cij+aik*bkj;/基本语句基本语句2解解:设基本语句的执行次数为设基本语句的执行次数为f(n),有有f(n)=c1n2+c2n3,因因 T(n)=f(n)=c1n2+c2n3c n3,其中其中c1,c2,c均为常数，所以该算法的均为常数，所以该算法的时时间复杂度为间复杂度为T(n)=O(n3)第15页，共30页，编辑于2022年，星期日 例例1-4 设设n n为如下算法处理的数据个数，求如下算法的时间复杂度。为如下算法处理的数据个数，求如下算法的时间复杂度。for(i=1;i=n;i=

17、2*i)printf(“i=%d“,i);解解:设基本语句的执行次数为设基本语句的执行次数为f(n),有有2 2f f(n n)n,即有即有f(n)lb n。因因T(n)=f(n)lb n c lb n,所以该算法的时间复杂度为所以该算法的时间复杂度为T(n)=O(lb n)。例例1-5:下边的算法是用冒泡排序法对数字下边的算法是用冒泡排序法对数字a中的中的n个整数类型的数据元个整数类型的数据元素素(a0an-1)，从小到大进行排序，求该算法的时间复杂度。从小到大进行排序，求该算法的时间复杂度。第16页，共30页，编辑于2022年，星期日void BubbleSort(int a,int n)

18、int i,j,flag=1;int temp;for(i=1;in&flag=1;i+)flag=0;for(j=0;jaj+1)flag=1;temp=aj;aj=aj+1;aj+1=temp;第17页，共30页，编辑于2022年，星期日解解:设基本语句的执行次数为设基本语句的执行次数为f(n),最坏情况下有最坏情况下有 f(n)n+4*n2/2因因T(n)=f(n)n+2*n2 c*n2,其中其中c为常数，所以该算法的时间复杂度为常数，所以该算法的时间复杂度为为T(n)=O(n2)。算法的时间复杂度是衡量一个算法好坏的重要指标。一般算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，

19、具有来说，具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际使用可接受、可实际使用的算的算法法;具有具有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小时才可使用的算小时才可使用的算法。法。第18页，共30页，编辑于2022年，星期日 例例1-6 下面的算法是在一个有下面的算法是在一个有n个数据元素的数组个数据元素的数组a中删除第中删除第I个个位置的数组元素，要求当删除成功时数组元素个数减位置的数组元素，要求当删除成功时数组元素个数减1，求该，求该算法的时间复杂度。其中数组下标从算法的时间复杂度。其中数组下标从0至至n-1。int Delete(in

20、t a,int&n,int i)int j;if(i=n)return 0;/删除位置错误，失败返回删除位置错误，失败返回for(j=i+1;jn;j+)aj-1=aj;/顺次移位填补顺次移位填补n-;/数组元素个数减数组元素个数减1return 1;/删除成功返回删除成功返回第19页，共30页，编辑于2022年，星期日解解:假设删除任何位置上的数据元素都是等概率的假设删除任何位置上的数据元素都是等概率的,设设Pi为删除第为删除第i个个位置上数据元素的概率，则有位置上数据元素的概率，则有Pi=1/n，设，设E为删除数组元素的平为删除数组元素的平均次数，则有均次数，则有因因T(n)=E(n+1)

21、/2 c*n,其中其中c为常数，所以该算法的等概率平均时间为常数，所以该算法的等概率平均时间复杂度为复杂度为T(n)=O(n).第20页，共30页，编辑于2022年，星期日以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常用的。其关系为：系为：O(1)O(logn)O(n)O(nlogn)O(n O(1)O(logn)O(n)O(nlogn)O(n2 2)O(n)O(n3 3)指数时间的关系为：指数时间的关系为：O(2O(2n n)O(n!)O(n)O(n!)O(nn n)当当n n取得很大时，指数时间算法和多项式时间算取得很大时，指数时间算法和多项式时间算法在所需

22、时间上非常悬殊。因此，只要有人能将现法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。间算法，那就取得了一个伟大的成就。第21页，共30页，编辑于2022年，星期日计算机处理中的计算机处理中的“难难”的问题和不可解问题的问题和不可解问题现实世界中，大量非数值问题在求解时，首先要判定其是否可解。通过建立计算的数学模型（如图灵机、递归函数、-演算、Post系统等）精确区分哪些是可计算的，哪些是不可计算的。但是许多问题本身是不可判定的(如悖论问题、图灵机停机问题等)。只有是可判定、可计

23、算的问题，才能通过精确的算法描述进行求解。计算的过程就是执行算法的过程。可计算性的核心问题是将算法这一直观概念精确化，变为一个具有有限性、可执行性、确定性、终止性、有限个输入、1个或1个以上输出的具体算法。第22页，共30页，编辑于2022年，星期日1.多项式问题（P问题）如果一个问题的规模是n，按某种算法解决问题时用的计算次数是n的多项式，或者说计算的复杂度为O(log n)，O(n)，O(n2)，O(n3)或O(nk)（k为常数），则称该算法为多项式算法，而这类问题称为多项式(P)问题。以当今计算机的处理速度，对于一个有合理输入数量的多项式问题，计算机都能有效地予以解决。一个问题会有多种算

24、法，算法会有快、慢。例如教材中排序、查找部分，选择排序比冒泡排序快，对分查找比顺序查找快，等等。第23页，共30页，编辑于2022年，星期日2.非多项式问题（NP问题）有许多问题，当它们的规模变得越来越大时，不管你采用什么算法，求解它所用的时间都会长得惊人。就算是用当今的快速计算机，都无法在可容忍的时间内完成，这就是所谓非多项式（NP）问题。第24页，共30页，编辑于2022年，星期日若问题求解时所用算法的计算时间的阶等价于某种指数函数，或者说算法的复杂度为O(2n)，O(kn)（k为常数）或O(n!)，则称该算法为指数型算法，而这类问题就是非多项式（NP）问题。非多项式问题远比多项式问题难度

25、大，当问题规模增大时，用计算机处理需要数月甚至数年的时间才能得出问题结果。例如，梵塔问题、货郎担问题、因式分解问题、纵横字谜问题、图形着色问题、棋类博弈问题、可满足性问题等等都是所谓“难”的问题。第25页，共30页，编辑于2022年，星期日3.不可解问题 对这类问题，无法用计算机程序来解决。图灵是较早发现这类问题的人。例如，他提出了“停机问题”就是一个不可解问题。还有很多不可解问题。问问 题题不可解的问题不可解的问题非多项式问题非多项式问题多项式问题多项式问题可解的问题可解的问题第26页，共30页，编辑于2022年，星期日算法设计时需要注意算法设计时需要注意1.1.必须把问题形式化必须把问题形

26、式化;2.2.问题必须是可计算的，即一定要有算法问题必须是可计算的，即一定要有算法;3.3.要用计算机实现一个算法以解决某种问题，问题的复杂度要用计算机实现一个算法以解决某种问题，问题的复杂度必须是合理的，即要避免指数爆炸。必须是合理的，即要避免指数爆炸。算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际使用可接受、可实际使用的算法的算法;具有具有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小时才可使用的算法。小时才可使用的算法。第2

27、7页，共30页，编辑于2022年，星期日1.4 1.4 算法的书写规范算法的书写规范 算法应具有算法应具有可读性可读性，主要体现在算法的，主要体现在算法的符号命名符号命名和和书写格式书写格式上上。命名规范命名规范:(1)各种符号均以英语各种符号均以英语单词命名，所有命名应见名知意。单词命名，所有命名应见名知意。(2)变量名字母均小写，若单词多变量名字母均小写，若单词多于一个时，第二个单词首字母大写。于一个时，第二个单词首字母大写。(3)类名、方法名、常量变量名和文件名字母均小写，但所有单词的首字类名、方法名、常量变量名和文件名字母均小写，但所有单词的首字母大写。母大写。(4)使用适当的缩写形式

28、。使用适当的缩写形式。(5)函数中的类类型参数用单字母大写。函数中的类类型参数用单字母大写。第28页，共30页，编辑于2022年，星期日书写规范书写规范:(1)#include先包括系统先包括系统头文件，再包括自定义头文件。头文件，再包括自定义头文件。(2)变量就近定义，以便于阅读变量就近定义，以便于阅读和查找。和查找。(3)算法采用缩进格式书写。算法采用缩进格式书写。(4)当算法简单时当算法简单时,通常不分段通常不分段;当算法复杂时当算法复杂时,可分成若干段可分成若干段,每每段之间空一行。段之间空一行。(5)为增加算法的可读为增加算法的可读性，算法中应添加适当的注释语句。性，算法中应添加适当的注释语句。int Delete(int a,int&n,int i)int j;if(i=n)return 0;/删除位置错误，失败返回删除位置错误，失败返回for(j=i+1;jn;j+)aj-1=aj;/顺次移位填补顺次移位填补n-;/数组元素个数减数组元素个数减1return 1;/删除成功返回删除成功返回第29页，共30页，编辑于2022年，星期日作作 业业P25 1-3，1-7，1-11（5），1-12第30页，共30页，编辑于2022年，星期日