第1章 数据结构概述.ppt

1、2020/7/13,1,第1章 数据结构概述,2020/7/13,2,本章主要内容,一、数据结构研究的问题 二、数据结构的概念及有关术语 三、算法的概念、特点、及其性能分析方法 四、数据结构与算法的描述工具类C语言简介,2020/7/13,3,1.1 数据结构研究的问题,111 计算机解决实际问题的过程与步骤 一、解题过程。 计算机解决问题的过程可以归结为五个世界、三级抽象和表示的过程。,五个世界分别是：现实世界、信息世界、概念世界、数据世界、机器世界。,三级抽象分别是：概念抽象、数据抽象、机器抽象。,2020/7/13,4,计算机解决实际问题的过程与步骤,二、解题步骤 用计算机解决实际问题一

2、般需要经过8个步骤：,1问题定义。分析问题，理解问题是什么？明确要求做什么？ 2、建立模型。将实际问题抽象，建立问题的数据模型。 3、定义数据。将数据模型确切定义出来。 4、寻找算法。探求数据模型的求解算法。 5、编写代码。将算法表示成程序代码。 6、调试运行。上机调试、查错、纠错，运行。 7、分析结果。分析结果是否符合实际问题。 8、总结改进。总结经验，加以改进提高。,2020/7/13,5,计算机解决实际问题的过程与步骤,上述8个步骤可能是循环的，如图所示：,2020/7/13,6,112 数据结构学科概念及其所研究的内容,数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之

3、间的关系和操作专门的学科。,三个要点： 1、非数值计算问题 2、数据之间的关系：逻辑关系、存储关系。 3、数据的操作 ：操作定义与算法实现,2020/7/13,7,113 数据结构的建模举例,例1、 集合结构数据模型 例2、线性结构数据模型 例3、树结构数据模型 例4、图结构数据模型 着重体会建模思想、掌握建模过程与方法。,返回首页,2020/7/13,8,12 数据结构的有关概念,121 数据的有关概念 1数据（Data）。表示信息的且能被计算机存储、处理的各种物理符号统称为数据。 2数据项（Data Item）。具有独立逻辑含义且不能再分解的数据称为数据项。 （最小单位） 3数据元素（Da

4、ta Element）。数据元素是相关数据项的集合。 （基本单位） 4数据对象（Data Object）。具有相同性质的数据元素构成的集合称为数据类型。,2020/7/13,9,122 数据结构的相关术语,1数据结构（Data Structure） 数据结构 = 数据元素集合 + 一组关系集合。 形式地表示 ： Data_Structure = ( D , R ) 2数据的逻辑结构（Logical Structure） 集合结构：元素之间无关系。 线性结构：元素之间存在1：1关系。 树形结构：元素之间存在1：n关系。 图状结构：元素之间存在m：n关系。 逻辑结构决定能定义那些操作。,2020/

5、7/13,10,数据结构的相关术语,3四种物理结构（存储结构） 顺序存储结构：用存储位置相邻表示逻辑关系。 链接存储结构：用指针表示逻辑关系。 索引存储结构：用“索引+顺序”方法存储数据。 散列存储结构：用散列表存储数据。 存储结构决定操作算法的实现及性能。,2020/7/13,11,123 数据类型的概念,1数据类型 数据类型 = 数据值的集合 + 一组操作 2抽象数据类型 抽象数据类型 = 数据结构 + 数据操作。 抽象数据类型分为三种： 原子类型：其值不能再分解成更简单的数据类型。 静态聚合类型。其值由固定个数的数据项组成的复合数据类型。 动态聚合类型。其值由个数可变的数据项组成的复合数

6、据类型。,2020/7/13,12,数据类型的概念,抽象数据类型的描述格式 ADT 数据对象定义： 数据关系定义： 数据运算定义： ADT ； 其中数据运算的定义格式为： （ 参数表 ） 初始条件描述 ； 操作结构描述 ； ,2020/7/13,13,数据类型的概念,3多形数据类型 其值的成份不确定的数据类型称为多形数据类型。 它于抽象数据类型具有相同的抽象层次，不同的是，数据的关系和运算是确定的，但数据的结构是不确定的。,返回首页,2020/7/13,14,13 算法与算法性能分析,131 算法概念及特点 1算法的概念 对某个特定问题求解步骤的一种描述称为算法 。 2算法的5个重要特征,（1

7、）有穷性。算法的步骤是有限的。 （2）确定性。每个步骤的操作含义是唯一确定的。 （3）可行性。每个步骤的操作机器能够实现。 （4）输入性。有0或多个输入数据。 （5）输出性。有1或多个输入数据。,2020/7/13,15,算法与算法性能分析,3算法的描述方法 （1）自然语言描述。符合人的习惯 （2）图形描述。直观、易懂。 （3）类语言描述。方便、易实现 （4）程序设计语言描述。 就是程序。,2020/7/13,16,132 算法的设计要求,1、正确性。算法必须正确。 2、易读性。算法易读、易懂、便于交流。 3、健壮性。算法有稳定、容错、可靠、适应等性能。 4、经济性。时间效率、空间效率高,20

8、20/7/13,17,133 算法的性能分析,1算法性能的评价指标 （1）算法的时间复杂度。 一个算法执行所使用的时间称为该算法的时间复杂度。 用T=T（n）表示，n为问题的规模 。 最坏时间复杂度：在最坏情况下执行算法在所花费的时间。 最好时间复杂度：在最好情况下执行算法在所花费的时间。 平均时间复杂度：在平均情况下执行算法在所花费的时间。 （2）算法的空间复杂度 执行算法过程中所使用的额外存储空间的开销。 不包括算法程序代码和所处理的数据本身所占用的空间部分， 记为S=S（n）单位为字节。,2020/7/13,18,算法的性能分析,2算法性能的评价方法 （1） 精确计算法 计算主要操作语句

9、的执行次数。,（2）近似估计法 将时间和空间复杂度用O数量级表示： T（n）= O（f（n） ； S（n）= O（g（n） 其中f（n）和g（n）是一个已知的函数（比较简单的）， 作为比较的尺度。,2020/7/13,19,算法的性能分析,通常使用的比较尺度有： O（1），称为常量级，算法的时间复杂度是一个常数。 O（n），称为线性级，时间复杂度是数据量n的线性函数。 O（n2），称为平方级，与n的二次多项式函数属于同一数量级。 O（n3），称为立方级，是n的三次多项式函数。 O（log2n），称为对数级，是n的对数函数 O（n log2n），是介于线性级和平方级之间一种数量级。 O（2n），

10、称为指数级，时间复杂度与n的指数函数是同一个数量级。 O（n!），称为阶乘级， 与n的阶乘属于同一数量级。,返回首页,2020/7/13,20,14 数据结构与算法描述工具简介,141 符号常量定义 # define TRUE 1 # define FALSE 0 # define OK 1 # define ERORR 0 # define OVERFLOW -1 # define INFEASIBLR -2 142 数据存储结构定义 用类型定义typedef描述。如： typedef int Bool ; typedef int Status ;,2020/7/13,21,数据结构与算法描

11、述工具简介,143 运算符 算术运算符：+、*、/、%（取余） 比较运算符：= = 、！=、= 逻辑运算符：|（或）、 / 数组整体赋值 变量名 变量名; / 交换赋值 变量名 = 条件表达式？表达式1：表达式2 / 条件赋值,2020/7/13,24,数据结构与算法描述工具简介,2I/O语句 scanf ( , / 字符输出,2020/7/13,25,3注释语句 / 注释内容 / 单行注释 /* 注释内容 */ / 多行注释 4条件选择语句 （1）单选择语句 if ( 条件表达式 ) 语句 S ; / S 可以是复合语句 语句序列; （2）双选择语句 if ( 条件表达式 ) 语句S1; e

12、lse 语句S2 ;,2020/7/13,26,格式一： switch ( 表达式 ) case ：语句序列1 ; break ; case ：语句序列2 ; break ; ; case ：语句序列n ; break ; default ：语句序列n+1 ; / end switch,数据结构与算法描述工具简介,（5）多选择语句（开关语句）,格式二： switch case ：语句序列1 ; break ; case ：语句序列2 ; break ; ; case ：语句序列n; break ; default ：语句序列n+1 ; / end switch,2020/7/13,27,数据结构与算法描述工具简介,5循环语句 （1）计数循环语句 for ( 循环变量 = 初值 ；循环变量= 终值 ；+/-循环变量+ /-) 语句序列 ; （2）当循环语句 while ( 条件表达式 ) 语句序列 ; （3）重复循环语句 do 语句序列 ; while ( 条件表达式 ),2020/7/13,28,数据结构与算法描述工具简介,6其他控制语句 return