资源描述
1,算法与数据结构,李 睿,2020/7/8,2,1.1 问题求解分析 1.2 基本概念和术语 1.3 算法和算法分析 1.4 抽象数据类型的表示与定义,2020/7/8,3,例：魔方求解问题,一个魔方（magic square）就是一个由1到n2的整数构成的nn的矩阵，其中每行、每列以及两条对角线上的数字之和都相等。,2020/7/8,4,本方法: 15 8 1 24 17 16 14 7 5 23 22 20 13 6 4 3 21 19 12 10 9 2 25 18 11,2020/7/8,5,1、数据结构形式化结果为： int squareMAX_SIZE MAX_SIZE; 2、将上述的产生魔方的过程算法化，用简洁的描述方式描述产生魔方的过程，即就是算法描述,2020/7/8,6,1）square0(size-1)/2=1; /*把1放入第一行最中间的方格中 */ 2）for (count=2; count=size*size; count+) /*依次放入其后的数字*/ row=(i-10)? (size-1): ( i-1); /*i=0;j=(size-1)/2; 上方*/ column=(j-10)? (size-1): ( j-1); /*左方*/,2020/7/8,7,if (squarerowcolumn) /*如果方格已被填入数字，下方 */ i=(+i) % size; else i=row; j = column； squareij=count; ,2020/7/8,8,1现实问题的计算机化表示问题 2现实问题的处理过程程序化问题,2020/7/8,9,1.1 问题求解分析 1.2 基本概念和术语 1.3 算法和算法分析 1.4 抽象数据类型的表示与定义,2020/7/8,10,1.2 基本概念和术语,一、基本概念 二、结构的定义 三、数据结构的定义 四、数据结构的分类,2020/7/8,11,一. 基本概念 数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 是计算机操作的对象的总称 。是信息的载体。,2020/7/8,12,数据元素(Data Element):是数据（集合）中的一个“个体”,是组成数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 是数据结构中讨论的基本单位,2020/7/8,13,数据项：是数据结构中讨论的最小单位（不可分割）。数据元素可以是数据项的集合（组成数据元素的各个项）,2020/7/8,14,数据对象(Data Object)：是性质相同的数据元素的集合。是数据的一个子集。 例1、整数的数据对象。 例2、英文字符类型的数据对象。 数据对象可以是有限的，也可以是无限的。,2020/7/8,15,二. 结构的定义 结构（ Structure ）:数据元素之间的相互关系。 如指数据在逻辑上的关系，称为逻辑结构。 如指数据在物理上的关系，称为物理结构。,2020/7/8,16,三. 数据结构的定义 数据结构(Data Structure) 1. 描述性定义：是相互之间存在一种或多种特定关系的数据元素的集合。 2. 形式定义,2020/7/8,17,数据结构一般包括以下三方面内容： 1）数据元素之间的逻辑关系，也称数据的逻辑结构 2）数据元素及其关系在计算机存储器内的表示，称为数据的存储结构（Storage Structure） 3）数据的运算，即对数据施加的操作,2020/7/8,18,2020/7/8,19,四、 数据结构的分类 1. 从逻辑结构角度分 线性结构：线性表、栈、队列 非线性结构：树、图 2. 从物理结构角度分 存储结构：物理结构。,2020/7/8,20,四种不同的存储结构 1、顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。 2、链式存储结构：在每一个数据元素中增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。,2020/7/8,21,3、索引存储方法 该方法通常在存储结点信息的同时，还建立附加的索引表。 4. 散列存储方法 根据结点的关键字直接计算出该结点的存储地址。,2020/7/8,22,1.1 问题求解分析 1.2 基本概念和术语 1.3 算法和算法分析 1.4 抽象数据类型的表示与定义,2020/7/8,23,1.3 算法和算法分析 一、算法 二、算法分析,2020/7/8,24,一、算法 1、算法：是对特定问题求解步骤的一种描述。 算法是指令的有限序列，其中每一条指令表示一个或多个操作。 2、算法具有以下五个特性： （1）有穷性（2）确定性 （3）可行性（4）输入 (5)输出,2020/7/8,25,3、 算法设计的要求 评价一个好的算法有以下几个标准: (1)正确性(Correctness ) (2)可读性(Readability) (3)健状性(Robustness) (4)效率与存储量需求,2020/7/8,26,二、 算法分析,性能评价 对问题规模n与该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。,2020/7/8,27,语句频度：是指该语句一个算法中重复执行的次数。 例 for(i=1；i=n;+i) for(j=1;j=n;+j) cij=0; for(k=1;k=n;+k) cij+=aik*bkj; ,2020/7/8,28,1）算法的时间复杂度:,算法的时间度量记作 T(n)=O(f(n) 称作算法的渐近时间复杂度，简称时间复杂度。,2020/7/8,29,例、 +x;s=0; 例、for(i=1;i=n;+i) +x;s+=x; 例、for(i=1;i=n;+i) for(j=1;j=n;+j) +x;s+=x;,2020/7/8,30,例 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; ai，j=x; ,2020/7/8,31,例6：Void bubble-sort(int a，int n) for(i=n-1,change=TURE;i=1 change=TURE ,2020/7/8,32,以下六种计算算法时间的多项式是最常用的。其关系为： O(1)O(logn)O(n)O(nlogn) O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn),2020/7/8,33,有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大“O”记号表示。例如，设 T1(n)=1.39nlgn+100n+256 =1.39nlgn+O(n), T2(n)=2.0nlgn-2n =2.0nlgn+O(n),2020/7/8,34,3）、算法的空间复杂度 空间复杂度:算法所需存储空间的度量，记作: S(n)=O(f(n) 其中n为问题的规模(或大小),2020/7/8,35,例 以魔方为例来看一下实现魔方算法的评价。 空间复杂度上，存贮一个nn的魔方，只需要nn的整数存贮空间，即O（n2）。 时间复杂度上，操作的主要工作来自于两个for循环嵌套，所以时间复杂度是O（n2）。,2020/7/8,36,1.1 问题求解分析 1.2 基本概念和术语 1.3 算法和算法分析 1.4 抽象数据类型的表示与定义,2020/7/8,37,1、数据类型,数据类型 是一个 值的集合和定义在此集合上的 一组操作的总称。,2020/7/8,38,2. 抽象数据类型（Abstract Data Type简称ADT）,在数据结构中我们常用到抽象数据类型。ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。 ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT 抽象数据类型名,2020/7/8,39,作 业 1、简述下列术语：数据、数据元素、数据对象、数据结构、数据类型、逻辑结构、物理结构。 2、算法的时间复杂度仅与问题的规模相关吗?,2020/7/8,40,2、为下面两个程序段中的所有语句确定频数 (1) for(i=1; i=n ；i+) for(j=1; j=i； j+) for(k=1; k=j ；k+) x+; (2) i=1; while(i=n) x+; i+; ,
展开阅读全文