《第01章算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第01章算法精选PPT.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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,DataTyp
12、e a,DataType 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;
13、im;i+)/进行进行m次调换次调换temp=ai;ai=an-1-i;an-1-i=temp;第12页，此课件共30页哦算法满足以下性质算法满足以下性质:(1)输入性输入性(2)输出输出性性(3)有限性有限性(4)确定性确定性(5)可执行性可执行性算法设计满足以下目标算法设计满足以下目标:(1)正确性正确性(2)可读性可读性(3)健壮性健壮性(4)高时间效率高时间效率(5)高空间效率高空间效率算法时间效率的度量算法时间效率的度量算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗算法的执行时间需通过根据该算法编制的程序在计算机上运行时所消耗的时间来度量。方法有两种的时间来度量。方法
14、有两种:(1)事后统计方法事后统计方法(2)事前分析方法事前分析方法第13页，此课件共30页哦程序运行消耗时间的有关因素程序运行消耗时间的有关因素:(1)书写算法的程序设计语言书写算法的程序设计语言 (2)编译产生编译产生的机器语言代码质量的机器语言代码质量 (3)机器执行指令的速度机器执行指令的速度 (4)问题的规模，即算法的时间效率与算法所处理的数据个数问题的规模，即算法的时间效率与算法所处理的数据个数n的的函数关系。函数关系。算法的时间效率算法的时间效率是算法所处理的数据个数是算法所处理的数据个数n的函数，算法的时间效的函数，算法的时间效率也称作算法的率也称作算法的时间复杂度。时间复杂度
15、。定义定义:T(n)=O(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)
16、=f(n)=c1n2+c2n3c 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
17、n)。例例1-5:下边的算法是用冒泡排序法对数字下边的算法是用冒泡排序法对数字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),最坏情
18、况下有最坏情况下有 f(n)n+4*n2/2因因T(n)=f(n)n+2*n2 c*n2,其中其中c为常数，所以该算法的时间复为常数，所以该算法的时间复杂度为杂度为T(n)=O(n2)。算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有具有多项式时间复杂度多项式时间复杂度的算法，是的算法，是可接受、可实际使用可接受、可实际使用的算法的算法;具具有有指数时间复杂度指数时间复杂度的算法，是只有当的算法，是只有当n足够足够小时才可使用的算法。小时才可使用的算法。第18页，此课件共30页哦 例例1-6 下面的算法是在一个有下面的算法是在
19、一个有n个数据元素的数组个数据元素的数组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(n
21、logn)O(n2 2)O(n)O(n3 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(n
23、2)，O(n3)或O(nk)（k为常数），则称该算法为多项式算法，而这类问题称为多项式(P)问题。以当今计算机的处理速度，对于一个有合理输入数量的多项式问题，计算机都能有效地予以解决。一个问题会有多种算法，算法会有快、慢。例如教材中排序、查找部分，选择排序比冒泡排序快，对分查找比顺序查找快，等等。第23页，此课件共30页哦2.非多项式问题（NP问题）有许多问题，当它们的规模变得越来越大时，不管你采用什么算法，求解它所用的时间都会长得惊人。就算是用当今的快速计算机，都无法在可容忍的时间内完成，这就是所谓非多项式（NP）问题。第24页，此课件共30页哦若问题求解时所用算法的计算时间的阶等价于某种指
24、数函数，或者说算法的复杂度为O(2n)，O(kn)（k为常数）或O(n!)，则称该算法为指数型算法，而这类问题就是非多项式（NP）问题。非多项式问题远比多项式问题难度大，当问题规模增大时，用计算机处理需要数月甚至数年的时间才能得出问题结果。例如，梵塔问题、货郎担问题、因式分解问题、纵横字谜问题、图形着色问题、棋类博弈问题、可满足性问题等等都是所谓“难”的问题。第25页，此课件共30页哦3.不可解问题 对这类问题，无法用计算机程序来解决。图灵是较早发现这类问题的人。例如，他提出了“停机问题”就是一个不可解问题。还有很多不可解问题。问问 题题不可解的问题不可解的问题非多项式问题非多项式问题多项式问
25、题多项式问题可解的问题可解的问题第26页，此课件共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页哦