《数据结构基础》PPT课件.ppt

《《数据结构基础》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构基础》PPT课件.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1算法与数据结构算法与数据结构李李 睿睿 算法与数据结构基础算法与数据结构基础2023/1/1921.1 1.1 问题求解分析问题求解分析1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 算法和算法分析算法和算法分析 1.4 1.4 抽象数据类型的表示与抽象数据类型的表示与定义定义 算法与数据结构基础算法与数据结构基础2023/1/193例：魔方求解问题例：魔方求解问题n一个魔方（一个魔方（magic squaremagic square）就是一个由就是一个由1 1到到n n2 2的整数构成的整数构成的的nnnn的矩阵，其中每行、的矩阵，其中每行、每列以及两条对角线上的数字每列以及两

2、条对角线上的数字之和都相等。之和都相等。算法与数据结构基础算法与数据结构基础2023/1/194本方法本方法: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 算法与数据结构基础算法与数据结构基础2023/1/1951 1、数据结构形式化结果为：、数据结构形式化结果为：nint squareMAX_SIZE MAX_SIZE;2 2、将上述的产生魔方的过程算法、将上述的产生魔方的过程算法化，用简洁的描述方式描述产生化，用简洁的描述方式描述产生魔方的过程，即就是魔方的过程，即就是算法描述算法描述 算法与数据结构基础

3、算法与数据结构基础2023/1/1961）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);/*左方左方*/算法与数据结构基础算法与数据结构基础2023/1/197if(squarerowcolumn)/*如果方格已被填入数字，下方如果方格已被填入数字，下方*/i=(+

4、i)%size;else i=row;j=column；squareij=count;算法与数据结构基础算法与数据结构基础2023/1/1981 1现实问题的计算机化表示问现实问题的计算机化表示问题题2 2现实问题的处理过程程序化现实问题的处理过程程序化问题问题 算法与数据结构基础算法与数据结构基础2023/1/1991.1 1.1 问题求解分析问题求解分析1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 算法和算法分析算法和算法分析1.4 1.4 抽象数据类型的表示与抽象数据类型的表示与定义定义 算法与数据结构基础算法与数据结构基础2023/1/19101.2 1.2 基本概念和术

5、语基本概念和术语一、基本概念一、基本概念二、结构的定义二、结构的定义三、数据结构的定义三、数据结构的定义四、数据结构的分类四、数据结构的分类 算法与数据结构基础算法与数据结构基础2023/1/1911一一.基本概念基本概念n数据数据(Data):(Data):是对信息的一种符是对信息的一种符号表示。在计算机科学中是指号表示。在计算机科学中是指所有能输入到计算机中并被计所有能输入到计算机中并被计算机程序处理的符号的总称算机程序处理的符号的总称 是是计算机操作的对象计算机操作的对象的总称的总称 。是是信息的载体信息的载体。算法与数据结构基础算法与数据结构基础2023/1/1912n数据元素数据元素

6、(Data Element):(Data Element):是是数据（集合）中的一个数据（集合）中的一个“个个体体”,是组成数据的是组成数据的基本单位基本单位,在计算机程序中通常作为一在计算机程序中通常作为一个整体进行考虑和处理。个整体进行考虑和处理。是数据结构中讨论的是数据结构中讨论的基本基本单位单位 算法与数据结构基础算法与数据结构基础2023/1/1913n 数据项数据项：是数据结构中讨论是数据结构中讨论的的最小最小单位（不可分割）。单位（不可分割）。数据元素可以是数据项的集数据元素可以是数据项的集合（组成数据元素的各个项）合（组成数据元素的各个项）算法与数据结构基础算法与数据结构基础2

7、023/1/1914n数据对象数据对象(Data Object)(Data Object)：是性质：是性质相同的数据元素的集合。是数据相同的数据元素的集合。是数据的一个的一个子集子集。例例1 1、整数的数据对象。、整数的数据对象。例例2 2、英文字符类型的数据对象。、英文字符类型的数据对象。数据对象可以是数据对象可以是有限有限的，也可以的，也可以是是无限无限的。的。算法与数据结构基础算法与数据结构基础2023/1/1915二二.结构的定义结构的定义结构（结构（Structure Structure）:数据元素之数据元素之间的相互关系。间的相互关系。如指数据在逻辑上的关系，称为如指数据在逻辑上的

8、关系，称为逻辑结构逻辑结构。如指数据在物理上的关系，称为如指数据在物理上的关系，称为物理结构物理结构。算法与数据结构基础算法与数据结构基础2023/1/1916三三.数据结构的定义数据结构的定义数据结构数据结构(Data Structure)(Data Structure)1.1.描述性描述性定义：是相互之间存在定义：是相互之间存在一种或多种特定关系的数据元一种或多种特定关系的数据元素的集合。素的集合。2.2.形式形式定义定义 算法与数据结构基础算法与数据结构基础2023/1/1917数据结构一般包括以下三方面内容：数据结构一般包括以下三方面内容：1 1）数据元素之间的逻辑关系）数据元素之间的

9、逻辑关系，也称数也称数据的逻辑结构据的逻辑结构2 2）数据元素及其关系在计算机存储器）数据元素及其关系在计算机存储器内的表示内的表示，称为数据的存储结构称为数据的存储结构（Storage StructureStorage Structure）3 3）数据的运算）数据的运算，即对数据施加的操作即对数据施加的操作 算法与数据结构基础算法与数据结构基础2023/1/1918存储存储数据数据结构结构逻辑逻辑运算运算 算法与数据结构基础算法与数据结构基础2023/1/1919四、四、数据结构的分类数据结构的分类1.1.从逻辑结构角度分从逻辑结构角度分 线性结构线性结构：线性表、栈、队列：线性表、栈、队列

10、 非线性结构非线性结构：树、图：树、图2.2.从物理结构角度分从物理结构角度分n存储结构存储结构：物理结构物理结构。算法与数据结构基础算法与数据结构基础2023/1/1920n四种不同的存储结构四种不同的存储结构1 1、顺序存储结构、顺序存储结构:用数据元素在用数据元素在存储器存储器中的相对位置中的相对位置来表示数据元素之间的逻辑来表示数据元素之间的逻辑关系。关系。2 2、链式存储结构：、链式存储结构：在每一个数据元素在每一个数据元素中增加一个存放地址的指针，用此中增加一个存放地址的指针，用此指针指针来来表示数据元素之间的逻辑关系。表示数据元素之间的逻辑关系。算法与数据结构基础算法与数据结构基

11、础2023/1/19213 3、索引存储方法、索引存储方法n该方法通常在存储结点信息的同时，该方法通常在存储结点信息的同时，还建立附加的索引表还建立附加的索引表。4.4.散列存储方法散列存储方法n根据结点的关键字直接计算出该结点根据结点的关键字直接计算出该结点的存储地址。的存储地址。算法与数据结构基础算法与数据结构基础2023/1/19221.1 1.1 问题求解分析问题求解分析1.2 1.2 基本概念和术语基本概念和术语1.31.3 算法和算法分析算法和算法分析 1.4 1.4 抽象数据类型的表示与抽象数据类型的表示与定义定义 算法与数据结构基础算法与数据结构基础2023/1/19231.3

12、 1.3 算法和算法分析算法和算法分析一、算法一、算法二、算法分析二、算法分析 算法与数据结构基础算法与数据结构基础2023/1/1924一、算法一、算法1 1、算法、算法：是对特定问题求解步骤：是对特定问题求解步骤的一种描述。的一种描述。算法是指令的有限算法是指令的有限序列，其中每一条指令表示一个序列，其中每一条指令表示一个或多个操作。或多个操作。2 2、算法具有以下、算法具有以下五个特性五个特性：（1 1）有穷性（）有穷性（2 2）确定性）确定性（3 3）可行性）可行性（4 4）输入）输入 (5)(5)输出输出 算法与数据结构基础算法与数据结构基础2023/1/19253 3、算法设计的要

13、求算法设计的要求n评价一个好的算法有以下几个评价一个好的算法有以下几个标准标准:(1)(1)正确性正确性(Correctness)(Correctness)(2)(2)可读性可读性(Readability)(Readability)(3)(3)健状性健状性(Robustness)(Robustness)(4)(4)效率与存储量需求效率与存储量需求 算法与数据结构基础算法与数据结构基础2023/1/1926二、二、算法分析算法分析性能评价性能评价n对问题规模对问题规模n n与该算法在运行时与该算法在运行时所占的空间所占的空间S S与所耗费的时间与所耗费的时间T T给给出一个出一个数量关系数量关系

14、的评价。的评价。算法与数据结构基础算法与数据结构基础2023/1/1927语句频度语句频度：是指该语句一个算法中重复执是指该语句一个算法中重复执行的次数。行的次数。例例for(i=1；i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;算法与数据结构基础算法与数据结构基础2023/1/19281 1）算法的时间复杂度）算法的时间复杂度:算法的时间度量记作算法的时间度量记作 T(n)=O(f(n)T(n)=O(f(n)称作算法的称作算法的渐近时间复杂度，渐近时间复杂度，简称简称时间复杂度时间复杂度。算法与数据结构基础算法与数据结构基础2

15、023/1/1929例、例、+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;算法与数据结构基础算法与数据结构基础2023/1/1930例例for(i=2;i=n;+i)for(j=2;j=1&change;-i)change=false;for(j=0;jaj+1)aj aj+1;change=TURE 算法与数据结构基础算法与数据结构基础2023/1/1932 以下六种计算算法时间的多以下六种计算算法时间的多项式是最常用的。其关系为：项式是最常用的。其关系为：O(1)O(logn)O(n)

16、O(nlogn)O(n2)O(n3)指数时间的关系为：指数时间的关系为：O(2n)O(n!)O(nn)算法与数据结构基础算法与数据结构基础2023/1/1933n有时为了比较两个同数量级算法的优有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低劣，须突出主项的常数因子，而将低次项用大次项用大“O”O”记号表示。例如，设记号表示。例如，设 T1(n)=1.39nlgn+100n+256T1(n)=1.39nlgn+100n+256 =1.39nlgn+O(n),=1.39nlgn+O(n),T2(n)=2.0nlgn-2n T2(n)=2.0nlgn-2n =2.0nlgn+O(n

17、)=2.0nlgn+O(n)算法与数据结构基础算法与数据结构基础2023/1/19343 3）、算法的空间复杂度）、算法的空间复杂度空间复杂度空间复杂度:算法所需存储空算法所需存储空间的度量，记作间的度量，记作:S(n)=O(f(n)其中其中n n为问题的规模为问题的规模(或大小或大小)算法与数据结构基础算法与数据结构基础2023/1/1935例例 以魔方为例来看一下实现魔方算法以魔方为例来看一下实现魔方算法的评价。的评价。n空间复杂度上，存贮一个空间复杂度上，存贮一个n n的魔方，的魔方，只需要只需要n n的整数存贮空间，即的整数存贮空间，即O（n2）。）。n时间复杂度上，操作的主要工作来自

18、时间复杂度上，操作的主要工作来自于两个于两个for循环嵌套，所以时间复杂循环嵌套，所以时间复杂度是度是O（n2）。）。算法与数据结构基础算法与数据结构基础2023/1/19361.1 1.1 问题求解分析问题求解分析1.2 1.2 基本概念和术语基本概念和术语1.3 1.3 算法和算法分析算法和算法分析 1.4 1.4 抽象数据类型的表示与抽象数据类型的表示与定义定义 算法与数据结构基础算法与数据结构基础2023/1/19371、数据类型、数据类型数据类型数据类型 是一个是一个 值的集合值的集合和和定义在此集合上的定义在此集合上的 一组操作一组操作的总称。的总称。算法与数据结构基础算法与数据结

19、构基础2023/1/19382.抽象数据类型（抽象数据类型（Abstract Data Type简称简称ADT）在数据结构中我们常用到抽象数据类型。ADT是指抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。ADT 抽象数据类型名抽象数据类型名数据对象：数据对象：数据关系：数据关系：基本操作：基本操作：ADT 抽象数据类型名抽象数据类型名 算法与数据结构基础算法与数据结构基础2023/1/1939作作 业业1 1、简述下列术语：数据、数据元素、简述下列术语：数据、数据元素、数据对象、数据结构、数据类型、数据对象、数据结构、数据类型、逻辑结构、物理结构。逻辑结构、物理结构。2 2、算法的时间复杂度仅与问题的规、算法的时间复杂度仅与问题的规模相关吗模相关吗?算法与数据结构基础算法与数据结构基础2023/1/19402、为下面两个程序段中的所有语句确定频数、为下面两个程序段中的所有语句确定频数 (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+;