软件技术基础课件-第3章 算法与数据结构(一)

软件技术基础,电子教案,第3章算法与数据结构,2,第3章内容摘要,3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序,软件技术基础电子教案,3,3.1数据结构概述,计算机=软件+硬件软件=程序+文档（软件工程的观点）程序=算法+数据结构（NiklausWirth，图灵奖获得者)程序设计:为计算机处理问题编制一组指令集算法:处理问题的策略数据结构:问题的数学模型,软件技术基础电子教案,4,数据结构=计算机程序设计技巧(Kunth，图灵奖获得者)熟悉C语言写出好的程序学习数据结构=编写高水平的程序数据结构：计算机类专业8大核心课程之一注：教育部计算机教指委认定的8大核心课程：计算机语言、数据结构、离散数学、计算机网络、计算机组成原理、操作系统、数据库、软件工程图灵奖：1966年设置，每年奖励1-2名杰出的计算机科学家，被誉为计算机领域的诺贝尔奖,软件技术基础电子教案,5,3.1.1什么是数据结构,早期的计算机主要用于数值计算现在的计算机更多地是用于非数值数据处理（字符、表格、图像）对非数值数据的处理：分析数据的逻辑特征抽象出合适的数学模型合理地存储到计算机设计出算法编写出程序,软件技术基础电子教案,6,首先要构造学生信息表，表3-1表达出学生数据的逻辑关系，它就是一个数学模型，这张表如何构造、在计算机内如何存储将直接影响查找算法的设计以及算法的效率,表3-1,例1学生信息查询系统,软件技术基础电子教案,7,学生信息表的特点,每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构，现实中这类关系的数据有很多。通常的操作插入某个学生的信息删除某个学生的信息更新某个学生的信息按条件查找某个学生的信息,软件技术基础电子教案,8,中国象棋、国际象棋的人机大战，核心技术是人编写的对弈程序。对弈步骤和过程可以用树型结构表达出来（数学模型）,例2人机对弈,图3-1井子棋对弈树,树形应用,软件技术基础电子教案,9,树型结构的特点所处理的数据之间具有层次关系，这是我们所说的树形结构,还有如：基因遗传关系等，它是一种非线性结构。对它的操作有：建立树形结构、存储树、访问树中的每个结点,软件技术基础电子教案,10,例3哥尼斯堡七桥问题,问题：怎样才能够从某块陆地出发，经过每座桥一次且仅一次最后回到出发点。,软件技术基础电子教案,11,图结构的特点,计算机处理的对象是图元素间的关系是复杂的图形或网状关系施加于对象上的操作有查询、插入、删除等现实中，这类关系的数据非常多。如：网络规划、交通、通讯规划等，这里典型的非线性关系。,软件技术基础电子教案,12,数据结构研究的内容,由以上三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树、图之类的数据结构。因此，简单说来，数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。此外，为了构造出好的数据结构及其实现，还需考虑数据结构及其实现的评价与选择。因此，数据结构的内容包括三个层次的五个“要素”，如下图所示：,软件技术基础电子教案,13,数据结构课程内容体系,软件技术基础电子教案,14,3.1.2基本概念和术语,数据是对客观事物的符号表示。在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合数据元素是数据集合中的一个实体，是计算机程序中加工处理的基本单位（记录、结构体）数据项组成数据元素的有特定意义的最小的不可分割的单位。,软件技术基础电子教案,15,3.1.2基本概念和术语,数据结构中讨论的最小单位是数据项;数据元素是数据项的集合例如：运动员（数据元素）其中出生日期中年月日是组合项单位。,软件技术基础电子教案,16,数据结构是相互之间存在一种或多种特定关系的数据元素的集合。数据结构的形式定义数据结构是一个二元组:Data_Structures=(D,R)其中:D是数据元素的有限集，R是D上关系的有限集。数据结构分为四大类:表:元素是线性关系(连接)图:元素间是非线性关系(连接)树:元素间是非线性关系，连接不得有回路文件:记录的序列,数据结构的定义,软件技术基础电子教案,17,数据结构的三要素数据的逻辑结构数据的存储结构对数据的操作（运算算法）,数据结构的定义,软件技术基础电子教案,18,数据结构的定义,逻辑结构数据结构中所说的“关系”实际上是指数据元素之间的逻辑关系，又称此为逻辑结构，可以分为：线性结构和非线性结构存储结构（物理结构）是指数据结构在存储器中的具体实现，包括顺序存储结构，链式存储结构，索引存储结构，散列存储结构。与孤立的数据元素表示形式不同，数据结构中的数据元素不但要表示其本身的实际内容，还要表示清楚数据元素之间的逻辑结构。数据运算对数据施加的操作。运算的定义依赖于逻辑结构，但运算的实现必依赖于存储结构（真正理解）,软件技术基础电子教案,19,第3章内容摘要,3.1数据结构概述3.2算法的描述和分析3.3线性表3.4树和二叉树3.5图3.6查找与排序3.7文件,软件技术基础电子教案,20,3.2算法的描述和分析,数据的运算是通过算法(Algorithm)。对实际问题选择一种好的数据结构，设计一个好的算法，是程序设计的本质。算法概念与特征算法描述算法设计的原则算法效率的衡量方法和准则算法的存储空间需求,软件技术基础电子教案,21,3.2.1算法概念与特征,算法（Algorithm）：算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特征：,有穷性：执行有限步，每步有限的时间。确定性：每条指令有确切含义，相同输入只能得到相同输出。可行性：操作通过已实现的基本运算执行有限次来实现。输入：0到多个输入。输出：1到多个输出。,软件技术基础电子教案,22,算法与数据结构,算法与数据结构关系密切选择的数据结构是否恰当直接影响算法的效率；而数据结构的优劣由算法的执行来体现。N.WirthAlgorithms+DataStructures=Programs,软件技术基础电子教案,23,3.2.2算法描述,算法可用多种方式描述：自然语言：易懂，灵活；不准确高级语言：准确，严格；死板伪码语言（类语言）：类C语言框图算法程序,软件技术基础电子教案,24,算法程序,算法是供人阅读的程序是让机器执行的算法用计算机语言实现时就是程序程序不具有算法的有穷性,软件技术基础电子教案,25,类C语言(1),类C语言由伪码和C语言组合，采用了C语言的核心部分，进行了扩充。数据结构的存储结构用类型定义（typedef）描述。数据元素的类型定义为ElemType,由用户在使用该数据类型时自行定义利用define定义布尔常量有:#defineTRUE1#defineFALSE0基本操作的算法用以下形式的函数描述：函数类型函数名（函数参数表）/算法说明语句序列/函数名参数表中的参数需要说明类型，算法中使用的辅助变量可以不用声明变量类型。,软件技术基础电子教案,26,类C语言（2）,赋值语句：简单赋值：变量名=表达式；串联赋值：变量名1=变量名2=变量名k=表达式；成组赋值：（变量名1，变量名k）=（表达式1，表达式k)；结构名=结构名；结构名=（值1，值k)；变量名=表达式；变量名起始下标.终止下标=变量名起始下标.终止下标；交换赋值：变量名变量名；条件赋值：变量名=条件表达式？表达式T：表达式,软件技术基础电子教案,27,类C语言（3）,条件语句if（表达式）语句；if（表达式）语句；else语句；分情形语句switch(表达式）case值1：语句序列1；break；case值n：语句序列n；break；default：语句序列n+1；break；,软件技术基础电子教案,28,类C语言（4）,for语句for（循环变量初值;条件;增量）语句；While语句dowhile语句while(表达式）dowhile(表达式）,软件技术基础电子教案,29,类C语言（5）,结束语句函数结束语句return(表达式)；或return;case结束语句break;异常结束语句exit();输入和输出语句输入语句scanf(变量1，变量2，变量n)输入语句printf(变量1，变量2，变量n),软件技术基础电子教案,30,类C语言（6）,注释多行注释/*注释内容*/单行注释/文字序列基本函数max（表达式1，.，表达式n），min,abs,floor,ceil,eof,eoln逻辑运算约定s=0;语句频度为1，时间复杂度为O(1)。,时间复杂度举例常量阶O(1),for(j=1;j=10000;+j)+x;s+=x;语句频度为10000，时间复杂度为O(1)。,软件技术基础电子教案,38,时间复杂度举例对数阶O(logn),s=0;for(j=1;j=n;j*=2)s+;语句频度为log2n，所以时间复杂度为O(log2n)。,软件技术基础电子教案,39,时间复杂度举例线性阶O(n),S=0;for(j=1;j=n;+j)s+;语句频度为n，所以时间复杂度为O(n)。,软件技术基础电子教案,40,时间复杂度举例对数阶O(nlogn),s=0;for(j=1;j=n;j*=2)for(k=1;k=n;+k)s+;时间复杂度为O(nlog2n),软件技术基础电子教案,41,时间复杂度举例平方阶O(n2),S=0;for(j=1;j=n;+j)for(k=1;k=n;+k)s+;语句频度为n2，所以时间复杂度为O(n2)。,s=0;for(j=1;j=n;j+)for(k=1;k=j;+k)s+;语句频度为n(n+1)/2，所以时间复杂度仍为O(n2)。,软件技术基础电子教案,42,时间复杂度举例立方阶O(n3),例：矩阵乘法：nxnfor(i=0;in;i+)/(n+1)for(j=0;jn;j+)/n(n+1)cij=0；/n2for(k=0;kn;j+)/n2(n+1)cij=cij+aik*bkj;/n3说明：各语句行后的数字是该语句重复执行的次数;本算法时间复杂度为O(n3),软件技术基础电子教案,43,算法的重要性,问题：公鸡每只五元，母鸡每只三元，小鸡三只一元，问百元买百鸡有几种买法？方案1：for(i=0;i=100;i+)for(j=0;j=100;j+)for(k=0;k=100;k+)if(i+j+k=100i=20;i+)for(j=0;j=34-i;j+)if(5*i+3*j+(100-i-j)/3=100)printf(“i=%d,j=%d,k=%d”,i,j,100-i-j);方案1内层循环超过100万次，在某机器上运行了50分钟；方案2的if语句执行525次，运行了2秒钟，相差1500倍。,软件技术基础电子教案,45,常见的时间复杂度及其关系,软件技术基础电子教案,46,1.下面程序段中带下划线的语句的执行次数的数量级是：【合肥工业大学1999三、1（2分）】i=1;while(in)i=i*2;,2.下面程序段中带下划线的语句的执行次数的数量级是()。【合肥工业大学2000三、1（2分）】i=1;while(in)for(j=0;jn;j+)x=x+1;i=i*2；,思考题,软件技术基础电子教案,47,voidbubble_sort(int-i)/bubble_sort,基本操作:赋值操作,最坏时间复杂度:O(n2),change=FALSE;/change为元素进行交换标志for(j=0;jaj+1)ajaj+1;change=TRUE;/一趟起泡,3.起泡排序,48,算法的空间复杂度定义为:,表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n)的增长率相同。,S(n)=O(g(n),3.2.5算法的存储空间需求,软件技术基础电子教案,49,算法的存储空间需求,算法的空间复杂度定义为:S(n)=O(g(n)表示随着问题规模n的增大，算法运行所需存储量的增长率与g(n