第01章算法精.ppt

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

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

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

3、类型。(6)(6)数据的逻辑结构：数据的逻辑结构：数据元素之间的相互联系方式。数据元素之间的相互联系方式。(7)(7)数据的存储结构：数据的存储结构：数据元素在计算机中的存储方式。数据元素在计算机中的存储方式。(8)数据的操作：数据的操作：对一种数据类型的数据进行的某种处理。对一种数据类型的数据进行的某种处理。(9)数据的操作集合：数据的操作集合：对一种数据类型的数据进行的所有操对一种数据类型的数据进行的所有操作。作。第4页，本讲稿共30页数数据据的的逻逻辑辑结结构构线性结构：线性结构：除第一个和最后一个数据元素外，每个除第一个和最后一个数据元素外，每个数据元素只有一个前驱和一个后继数据元素。

4、数据元素只有一个前驱和一个后继数据元素。树结构：树结构：除根结点外，每个数据元素只有一个前驱除根结点外，每个数据元素只有一个前驱数据元素，可有个或若干个后继数据元素。数据元素，可有个或若干个后继数据元素。图结构：图结构：每个数据元素可有个或若干个前驱数据每个数据元素可有个或若干个前驱数据元素和个或若干个后继数据元素。元素和个或若干个后继数据元素。线性结构线性结构树结构树结构图结构图结构第5页，本讲稿共30页数数据据的的存存储储结结构构顺序存储结构顺序存储结构：把数据元素存储在一块连续地址空把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物间的内存中，其特点是逻辑上相邻的

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

6、关系表现在结点的链接关系上。第6页，本讲稿共30页数数据据的的操操作作从抽象角度从抽象角度，数据的操作主要讨论某种数据类型，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论；作一般和数据的逻辑结构一起讨论；在具体角度下在具体角度下，数据的操作主要讨论操作的具体，数据的操作主要讨论操作的具体实现算法。具体角度下的操作实现必须在数据的实现算法。具体角度下的操作实现必须在数据的存储结构确定后才能进行。存储结构确定后才能进行。C+语言实现具体操语言实现具体操 作的方法是把操作设计为相应类的成员函数。作的方法

7、是把操作设计为相应类的成员函数。数据结构课程主要讨论数据结构课程主要讨论表表、堆栈堆栈、队列队列、串串、数数组组、树树、二叉树二叉树、图图等典型的常用数据结构。在讨论这些等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。据操作三个方面进行分析讨论。第7页，本讲稿共30页1.2 1.2 抽象数据类型和软件构造方法抽象数据类型和软件构造方法类型类型是一组值的集合。是一组值的集合。数据类型数据类型是指一个类型和定义在这个类型上的操作集是指一个类型和定义在这个类型上的操作集合。合。抽象数据类型

8、抽象数据类型是指一个逻辑概念上的类型和这个类型是指一个逻辑概念上的类型和这个类型上的操作集合。上的操作集合。数据类型和抽象数据类型的不同之处仅仅在于数数据类型和抽象数据类型的不同之处仅仅在于数据类型指的是高级程序设计语言支持的基本数据类型，据类型指的是高级程序设计语言支持的基本数据类型，而抽象数据类型指的是在基本数据类型支持下用户新而抽象数据类型指的是在基本数据类型支持下用户新设计的数据类型。设计的数据类型。第8页，本讲稿共30页 抽象数据类型抽象数据类型使软件设计成为工业化流水线生产的使软件设计成为工业化流水线生产的一个中间环节。一个中间环节。一方面一方面，根据给出的抽象数据类型的功，根据给

9、出的抽象数据类型的功能定义，负责设计这些抽象数据类型的专门公司设计该能定义，负责设计这些抽象数据类型的专门公司设计该抽象数据类型的具体存储结构以及在具体存储结构下各抽象数据类型的具体存储结构以及在具体存储结构下各操作的具体实现算法；操作的具体实现算法；另一方面另一方面，利用已设计实现的，利用已设计实现的抽象数据类型模块，负责设计应用软件的专门公司可以抽象数据类型模块，负责设计应用软件的专门公司可以安全、快速、方便的完成该应用软件系统的设计。安全、快速、方便的完成该应用软件系统的设计。软件的设计采用软件的设计采用模块化模块化方法，抽象数据类型就是构方法，抽象数据类型就是构造大型软件的造大型软件的

10、最基本最基本模块。在模块。在C+语言中，语言中，类类就是确定就是确定了数据元素存储结构的抽象数据类型的具体实现。了数据元素存储结构的抽象数据类型的具体实现。第9页，本讲稿共30页1.3 算法及其时间复杂度算法及其时间复杂度算法算法是描述求解问题方法的操作步骤集合。是描述求解问题方法的操作步骤集合。的一个的一个有限长有限长操作序列。操作序列。描描述述算算法法的的语语言言形形式式1.文字形式文字形式:用中文或英文这样的文字来描述算用中文或英文这样的文字来描述算法。法。2.伪码形式伪码形式:用一种仿程序设计语言的语言来描用一种仿程序设计语言的语言来描述算法。述算法。3.程序设计语言形式程序设计语言形

11、式:用某种程序设计语言描述用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。句键入计算机，计算机能调用和运行。第10页，本讲稿共30页 例例1-1:设计一个把存储在数组中的有设计一个把存储在数组中的有n个抽象数据元素个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列逆置的算法，即要求逆置后的数组中数据元素序列为为an-1,a1,a0,并要求原数组中的数据元素值不能被改变。并要求原数组中的数据元素值不能被改变。void Reverse(int n,DataType a,DataT

12、ype b)int i;for(i=0;in;i+)bi=an-1-i;/把数组把数组a的元素逆置后赋给数组的元素逆置后赋给数组b第11页，本讲稿共30页 例例1-2:设计一个把存储在数组中的有设计一个把存储在数组中的有n个抽象数据元素个抽象数据元素a0,a1,an-1逆置的算法，即要求逆置后的数组中数据元素序列逆置的算法，即要求逆置后的数组中数据元素序列为为an-1,a1,a0,并要求原数组中的数据元素值被改变。并要求原数组中的数据元素值被改变。void Reverse(int n,DataType a)int i,m=n/2;DataType temp;for(i=0;im;i+)/进行进

13、行m次调换次调换temp=ai;ai=an-1-i;an-1-i=temp;第12页，本讲稿共30页算法满足以下性质算法满足以下性质:(1)输入性输入性(2)输出性输出性(3)有限性有限性(4)确定性确定性(5)可执行性可执行性算法设计满足以下目标算法设计满足以下目标:(1)正确性正确性(2)可读性可读性(3)健壮性健壮性(4)高时间效率高时间效率(5)高空高空间效率间效率算法时间效率的度量算法时间效率的度量算法的执行时间需通过根据该算法编制的程序在计算机上运算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种行时所消耗的时间来度量。方法有两种:(1)事后统计

14、方法事后统计方法(2)事前分析方法事前分析方法第13页，本讲稿共30页程序运行消耗时间的有关因素程序运行消耗时间的有关因素:(1)书写算法的程序设计语言书写算法的程序设计语言 (2)编译产生的机器语言代码质量编译产生的机器语言代码质量 (3)机器执行指令的速度机器执行指令的速度 (4)问题的规模，即算法的时间效率与算法所处理的数据个问题的规模，即算法的时间效率与算法所处理的数据个数数n的函数关系。的函数关系。算法的时间效率算法的时间效率是算法所处理的数据个数是算法所处理的数据个数n的函数，算法的函数，算法的时间效率也称作算法的的时间效率也称作算法的时间复杂度。时间复杂度。定义定义:T(n)=O

15、(f(n),当且仅当存在正常数当且仅当存在正常数c和和n0，对所有的对所有的n(n n0)满足满足T(n)cf(n)。第14页，本讲稿共30页 例例1-3 设数组设数组a和和b在前边部分已赋值，求如下两个在前边部分已赋值，求如下两个n阶阶矩阵相乘运算算法的时间复杂度。矩阵相乘运算算法的时间复杂度。for(i=0;in;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+c2

16、n3c n3,其中其中c1,c2,c均为常数，所以该均为常数，所以该算法的算法的时间复杂度为时间复杂度为T(n)=O(n3)第15页，本讲稿共30页 例例1-4 设设n n为如下算法处理的数据个数，求如下算法的时为如下算法处理的数据个数，求如下算法的时间复杂度。间复杂度。for(i=1;i=n;i=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:下边的算法

17、是用冒泡排序法对数字下边的算法是用冒泡排序法对数字a中的中的n个整数类型个整数类型的数据元素的数据元素(a0an-1)，从小到大进行排序，求该算法从小到大进行排序，求该算法的时间复杂度。的时间复杂度。第16页，本讲稿共30页void BubbleSort(int a,int n)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页解解:设基本语句的执行次数为设基本语句的执行次数为f(n),最坏情况下有最坏情况下有 f(n)n+

18、4*n2/2因因T(n)=f(n)n+2*n2 c*n2,其中其中c为常数，所以该算法的时为常数，所以该算法的时间复杂度为间复杂度为T(n)=O(n2)。算法的时间复杂度是衡量一个算法好坏的重要指标。一算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有般来说，具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际可接受、可实际使用使用的算法的算法;具有具有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小小时才可使用的算法。时才可使用的算法。第18页，本讲稿共30页 例例1-6 下面的算法是在一个有下面的算法是在一个有n个数据元素的数组个数据元素

19、的数组a中删中删除第除第I个位置的数组元素，要求当删除成功时数组元素个数个位置的数组元素，要求当删除成功时数组元素个数减减1，求该算法的时间复杂度。其中数组下标从，求该算法的时间复杂度。其中数组下标从0至至n-1。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;/删除成功返回删除成功返回第19页，本讲稿共30页解解:假设删除任何位置上的数据元素都是等概率的假设删除任何

20、位置上的数据元素都是等概率的,设设Pi为删为删除第除第i个位置上数据元素的概率，则有个位置上数据元素的概率，则有Pi=1/n，设，设E为删除数为删除数组元素的平均次数，则有组元素的平均次数，则有因因T(n)=E(n+1)/2 c*n,其中其中c为常数，所以该算法的等概率为常数，所以该算法的等概率平均时间复杂度为平均时间复杂度为T(n)=O(n).第20页，本讲稿共30页以下六种计算算法时间的多项式是最常用的。其关以下六种计算算法时间的多项式是最常用的。其关系为：系为：O(1)O(logn)O(n)O(nlogn)O(n O(1)O(logn)O(n)O(nlogn)O(n2 2)O(n)O(n

21、3 3)指数时间的关系为：指数时间的关系为：O(2O(2n n)O(n!)O(n)O(n!)O(nn n)当当n n取得很大时，指数时间算法和多项式时间算取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。式时间算法，那就取得了一个伟大的成就。第21页，本讲稿共30页计算机处理中的计算机处理中的“难难”的问题和不可解问题的问题和不可解问题现实世界中，大量非数值问题在求解时，首先要判定其是否可解。通过建立计

22、算的数学模型（如图灵机、递归函数、-演算、Post系统等）精确区分哪些是可计算的，哪些是不可计算的。但是许多问题本身是不可判定的(如悖论问题、图灵机停机问题等)。只有是可判定、可计算的问题，才能通过精确的算法描述进行求解。计算的过程就是执行算法的过程。可计算性的核心问题是将算法这一直观概念精确化，变为一个具有有限性、可执行性、确定性、终止性、有限个输入、1个或1个以上输出的具体算法。第22页，本讲稿共30页1.多项式问题（P问题）如果一个问题的规模是n，按某种算法解决问题时用的计算次数是n的多项式，或者说计算的复杂度为O(log n)，O(n)，O(n2)，O(n3)或O(nk)（k为常数），

23、则称该算法为多项式算法，而这类问题称为多项式(P)问题。以当今计算机的处理速度，对于一个有合理输入数量的多项式问题，计算机都能有效地予以解决。一个问题会有多种算法，算法会有快、慢。例如教材中排序、查找部分，选择排序比冒泡排序快，对分查找比顺序查找快，等等。第23页，本讲稿共30页2.非多项式问题（NP问题）有许多问题，当它们的规模变得越来越大时，不管你采用什么算法，求解它所用的时间都会长得惊人。就算是用当今的快速计算机，都无法在可容忍的时间内完成，这就是所谓非多项式（NP）问题。第24页，本讲稿共30页若问题求解时所用算法的计算时间的阶等价于某种指数函数，或者说算法的复杂度为O(2n)，O(k

24、n)（k为常数）或O(n!)，则称该算法为指数型算法，而这类问题就是非多项式（NP）问题。非多项式问题远比多项式问题难度大，当问题规模增大时，用计算机处理需要数月甚至数年的时间才能得出问题结果。例如，梵塔问题、货郎担问题、因式分解问题、纵横字谜问题、图形着色问题、棋类博弈问题、可满足性问题等等都是所谓“难”的问题。第25页，本讲稿共30页3.不可解问题 对这类问题，无法用计算机程序来解决。图灵是较早发现这类问题的人。例如，他提出了“停机问题”就是一个不可解问题。还有很多不可解问题。问问 题题不可解的问题不可解的问题非多项式问题非多项式问题多项式问题多项式问题可解的问题可解的问题第26页，本讲稿

25、共30页算法设计时需要注意算法设计时需要注意1.1.必须把问题形式化必须把问题形式化;2.2.问题必须是可计算的，即一定要有算法问题必须是可计算的，即一定要有算法;3.3.要用计算机实现一个算法以解决某种问题，问题的要用计算机实现一个算法以解决某种问题，问题的复杂度必须是合理的，即要避免指数爆炸。复杂度必须是合理的，即要避免指数爆炸。算法的时间复杂度是衡量一个算法好坏的重要指标。一算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有般来说，具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际可接受、可实际使用使用的算法的算法;具有具有指数时间复杂度指数时间复杂度的算法

26、，是只有当的算法，是只有当n足够足够小小时才可使用的算法。时才可使用的算法。第27页，本讲稿共30页1.4 1.4 算法的书写规范算法的书写规范 算法应具有算法应具有可读性可读性，主要体现在算法的，主要体现在算法的符号命名符号命名和和书书写格式上写格式上。命名规范命名规范:(1)各种符号均以英语单词命名，所有命名应见名知意。各种符号均以英语单词命名，所有命名应见名知意。(2)变量名字母均小写，若单词多于一个时，第二个单词首字变量名字母均小写，若单词多于一个时，第二个单词首字母大写。母大写。(3)类名、方法名、常量变量名和文件名字母均小写，但所有类名、方法名、常量变量名和文件名字母均小写，但所有

27、单词的首字母大写。单词的首字母大写。(4)使用适当的缩写形式。使用适当的缩写形式。(5)函数中的类类型参数用单字母大写。函数中的类类型参数用单字母大写。第28页，本讲稿共30页书写规范书写规范:(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页作作 业业P25 1-3，1-7，1-11（5），1-12第30页，本讲稿共30页