《Chap1_算法与数据结构—C语言描述(第2版)张乃孝编课件》由会员分享，可在线阅读，更多相关《Chap1_算法与数据结构—C语言描述(第2版)张乃孝编课件（29页珍藏版）》请在金锄头文库上搜索。
1、算法与数据结构,计算机与电子信息工程系 万励QQ : 529566152Email: ,数据结构的地位,“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。,程序 = 数据结构 + 算法,课程目的,能够分析研究计算机加工的对象的特性，获得其逻辑结构，根据需求，选择合适存储结构及其相应的算法；学习一些常用的算法；复杂程序设计的训练过程，要求编写的程序结构清楚和正确易读；初步掌握算法的时间
2、分析和空间分析技术；,第一章 概论,问题和实例数据结构？抽象数据类型ADT类C描述算法和算法分析,问题和实例(1),当我们使用计算机来解决一个具体问题时，一般需要经过下列几个步骤： 问题 抽象 数据结构 算法 程序,问题和实例(2),快速送达疫苗 已知有临近的五个村子发生了疫情，我们要用汽车快速地将疫苗送达到5个村子。目标是寻找一条耗时最少的路线。,耗时矩阵,穷举法,贪心算法,数据结构,是一门研究非数值计算的程序设计问题中，计算机操作的对象以及它们之间的关系和操作的学科例子书目自动检索系统人机对奕问题 快速送达疫苗问题,例1 书目自动检索系统,书目文件,数据结构,例2 人机对奕问题,例3：问题
3、：快速送达疫苗 模型：图形结构,图形结构,数据结构,基本概念和术语,数据(Data)：客观事物在计算机中的符号表示，是能被计算机识别和处理的符号总称。(数值型、非数值型)数据元素(Data Element)：数据的基本单位，用于完整地描述一个对象;数据项(Data Object)：组成数据元素的有特定意义的最小单位 。数据对象(Data Object)：相同特性数据元素的集合，是数据的一个子集合。,数据结构：相互之间存在一种或多种特定关系的数据元素的集合。,基本概念和术语,基本概念和术语,形式定义：数据结构是一个二元组Data_Structure （D，R）,其中，D是数据元素的有限集，R是D
4、上关系的有限集。,数据结构主要关心的是下面三个方面 ：结构中各元素之间的逻辑关系线性结构：如图书馆的书目索引树形结构：如人机对奕问题图形结构：交通图2. 结构中各元素的存储方式(物理结构)3. 结构具有的行为特征(关系与操作),基本概念和术语,存储结构(物理结构)数据结构在计算机中的表示。顺序存储结构：借助元素在存储器中的相对位置表示数据元素之间的关系。链式存储结构：借助指示元素存储地址的指针（Pointer）表示数据元素之间的逻辑关系。,基本概念和术语,抽象数据类型,抽象数据类型:（Abstract Data Type）ADT:一个数学模型以及定义在该模型上的一组操作。ADT 抽象数据类型名
5、数据对象：数据对象定义数据关系：数据关系定义基本操作：基本操作定义ADT 抽象数据类型名,复数抽象数据类型ADT Complex数据对象：D = c1, c2 | c1, c2 R(R为实数集）数据关系：S = （ c1为实部，c2为虚部）基本操作：void Assign(*A, c1, c2）void Add(*A, B)void Minus(*A, B)void Multiply(*A, B)void Divide(*A, B).ADT Complex,复数抽象数据类型示例,typedef double ItemType;typedef structItemTyper ;ItemTypev
6、;Complex;/* 复数抽象数据类型 */void Assign(Complex *A, ItemType r, ItemType v); /* 赋值 */void Add(Complex *A, Complex B);/* A+B */void Minus(Complex *A, Complex B);/* A-B */void Multiply(Compex *A, Complex B);/* A*B */void Divide(Complex *A, Complex B);/* A/B */.,复数抽象数据类型的C语言实现,void Assign(Complex *A, ItemTy
7、pe real, ItemType virtual)A-r = real;A-v = virtual;/* Assign( ) */void Add(Complex *A, Complex B)A-r += B.r;A-v += B.v;/* Add( ) */,复数抽象数据类型的C语言实现,算法和算法分析,算法（Algorithm）：是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：,有穷性：执行有限步，每步有限的时间；确定性：相同的输入相同的输出；可行性：算法能实现输入:零个或多个输出:一个或多个,算法和算法分析,算法设计的要求：
8、正确性：可读性:健壮性:效率与低存贮量要求时间复杂度空间复杂度,算法效率,衡量算法效率的方法主要有两大类： 事后统计：利用计算机的时钟(与硬件有关)；事前分析估算：用高级语言编写的程序运行的时间主要取决于如下因素：算法；问题规模；使用语言：级别越高，效率越低；编译程序；机器；,时间复杂度,算法的运行工作量的大小就只依赖于问题的规模（通常用正整数n表示），或者说它是问题规模n的函数。记T(n)，称为该算法的时间复杂度算法主要由程序的控制结构（顺序，分支，循环）和原操作（必须的操作）构成，算法的时间主要取决于两者。,+x; s=0;语句频度为1，时间复杂度为O(1)。,时间复杂度,for(j=1;
9、j=n;+j)for(k=1;k=n;+k)+x;s+=x;语句频度为nn，时间复杂度为O(n2)。,时间复杂度,for(j=1;j=n;+j)for(k=1;k=j;+k)+x;s+=x;语句频度为近似于1/2*（n2），所以时间复杂度仍为O(n2)。,s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;时间复杂度为O(nlog2n),时间复杂度,例：矩阵加法：n x nfor( i = 0; i n; i+)for( j = 0; j n; j+)cij = aij + bij;语句的频度（Frequency Count ): 重复执行的次数：n*n;T( n )
10、 = O ( n 2)即：矩阵加法的运算量和问题的规模n的平方是同一个量级；,时间复杂度,k = 0;for( i = 0; i n; i+)for( j = 0; j = i; j+)aij = +k;执行次数：n*(n+1)/2,T( n ) = O ( n 2),算法的空间复杂度,算法的空间复杂度 算法的空间复杂度是指解决问题的算法在执行时所占用的存储空间。再具体一些，也就是我们编程序时，程序的存储空间、变量占用空间、系统堆栈的使用空间等等。也正由此，空间复杂度的度量分为两个部分：固定部分和可变部分。,for(k=1; k=n; k+) s=s+10; ,for(j=1; j=n; j+) for(k=1; k=n; k+) s=s+10; ,T(n)=O( n )n=1 执行1次;n=10 执行10次;n=100 执行100次;,for(i=1; i=n; i+) for(j=1; j=n; j+) for(k=1;k=n;k+) s=s+10; ,T(n)=O( n3 )n=1 执行1次;n=10 执行1000次;n=100 执行1000000次;,T(n)=O( n2 )n=1 执行1次;n=10 执行100次;n=100 执行10000次;,复杂度函数的增长率,1log2n n n log2n n2 n3 2n 10n,
