第第1 1章章 数据结构概述数据结构概述 数据结构研究的问题1.11.1 数据结构的有关概念1.21.2 算法与算法性能分析1.31.3 数据结构与算法描述工具简介1.41.49/24/20241本章主要内容本章主要内容 一、数据结构研究的问题一、数据结构研究的问题二、数据结构的概念及有关术语二、数据结构的概念及有关术语三、算法的概念、特点、及其性能分析方法三、算法的概念、特点、及其性能分析方法四、数据结构与算法的描述工具类四、数据结构与算法的描述工具类C语言简介语言简介9/24/202421.1 数据结构研究的问题 111 计算机解决实际问题的过程与步骤计算机解决实际问题的过程与步骤一、解题过程。一、解题过程。计算机解决问题的过程可以归结为五个世界、三级抽象和表示的过程。 五个世界分别是：现实世界、信息世界、概念世界、数据世界、机器世界。 三级抽象分别是：概念抽象、数据抽象、机器抽象。9/24/20243计算机解决实际问题的过程与步骤二、解题步骤二、解题步骤 用计算机解决实际问题一般需要经过8个步骤：1问题定义。分析问题，理解问题是什么？明确要求做什么？2、建立模型。将实际问题抽象，建立问题的数据模型。 3、定义数据。将数据模型确切定义出来。 4、寻找算法。探求数据模型的求解算法。5、编写代码。将算法表示成程序代码。6、调试运行。上机调试、查错、纠错，运行。7、分析结果。分析结果是否符合实际问题。8、总结改进。总结经验，加以改进提高。9/24/20244计算机解决实际问题的过程与步骤 上述上述8 8个步骤可能是循环的，如图所示：个步骤可能是循环的，如图所示：9/24/20245112 数据结构学科概念及其所研究的内容 数据结构是研究非数值计算的程序设计问数据结构是研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和题中计算机的操作对象以及它们之间的关系和操作专门的学科。操作专门的学科。 三个要点： 1、非数值计算问题、非数值计算问题2、数据之间的关系：逻辑关系、存储关系。、数据之间的关系：逻辑关系、存储关系。 3、数据的操作、数据的操作 ：操作定义与算法实现操作定义与算法实现9/24/20246113 数据结构的建模举例例例1 1、 集合结构数据模型集合结构数据模型例例2 2、线性结构数据模型、线性结构数据模型例例3 3、树结构数据模型、树结构数据模型例例4 4、图结构数据模型、图结构数据模型着重体会建模思想、掌握建模过程与方法着重体会建模思想、掌握建模过程与方法。返回首页返回首页9/24/2024712 数据结构的有关概念1 12 21 1 数据的有关概念数据的有关概念 1数据（Data）。表示信息的且能被计算机存储、处理的各种物理符号统称为数据。 2数据项（Data Item）。具有独立逻辑含义且不能再分解的数据称为数据项。 （最小单位） 3数据元素（Data Element）。数据元素是相关数据项的集合。 （基本单位） 4数据对象（Data Object）。具有相同性质的数据元素构成的集合称为数据类型。 9/24/20248122 数据结构的相关术语 1 1数据结构（数据结构（Data StructureData Structure） 数据结构数据结构 = = 数据元素集合数据元素集合 + + 一组关系集合。一组关系集合。 形式地表示形式地表示 ： Data_StructureData_Structure = ( D , R ) = ( D , R ) 2 2数据的逻辑结构（数据的逻辑结构（Logical StructureLogical Structure）集合结构：元素之间无关系。线性结构：元素之间存在1：1关系。树形结构：元素之间存在1：n关系。图状结构：元素之间存在m：n关系。 逻辑结构决定能定义那些操作。逻辑结构决定能定义那些操作。 9/24/20249数据结构的相关术语3 3四种物理结构（存储结构）四种物理结构（存储结构）顺序存储结构：用存储位置相邻表示逻辑关系。链接存储结构：用指针表示逻辑关系。索引存储结构：用“索引+顺序”方法存储数据。散列存储结构：用散列表存储数据。存储结构决定操作算法的实现及性能。存储结构决定操作算法的实现及性能。9/24/202410123 数据类型的概念1 1数据类型数据类型 数据类型数据类型 = = 数据值的集合数据值的集合 + + 一组操作一组操作2 2抽象数据类型抽象数据类型 抽象数据类型 = 数据结构 + 数据操作。抽象数据类型分为三种：原子类型：其值不能再分解成更简单的数据类型。静态聚合类型。其值由固定个数的数据项组成的复合数据类型。动态聚合类型。其值由个数可变的数据项组成的复合数据类型。 9/24/202411数据类型的概念抽象数据类型的描述格式抽象数据类型的描述格式ADT ADT 数据对象定义：数据对象定义： 数据关系定义：数据关系定义： 数据运算定义：数据运算定义： ADT ADT ；其中数据运算的定义格式为：其中数据运算的定义格式为： （ 参数表参数表 ） 初始条件描述初始条件描述 ； 操作结构描述操作结构描述 ； 9/24/202412数据类型的概念3 3多形数据类型多形数据类型其值的成份不确定的数据类型称为多形数据类型。它于抽象数据类型具有相同的抽象层次，不同的是，数据的关系和运算是确定的，但数据的结构是不确定的。 返回首页返回首页9/24/20241313 算法与算法性能分析1 13 31 1 算法概念及特点算法概念及特点1算法的概念对某个特定问题求解步骤的一种描述称为算法 。2算法的5个重要特征（1）有穷性。算法的步骤是有限的。（2）确定性。每个步骤的操作含义是唯一确定的。（3）可行性。每个步骤的操作机器能够实现。（4）输入性。有0或多个输入数据。（5）输出性。有1或多个输入数据。9/24/202414算法与算法性能分析3 3算法的描述方法算法的描述方法（1）自然语言描述。符合人的习惯（2）图形描述。直观、易懂。（3）类语言描述。方便、易实现（4）程序设计语言描述。 就是程序。9/24/202415132 算法的设计要求1、正确性。算法必须正确。2、易读性。算法易读、易懂、便于交流。3、健壮性。算法有稳定、容错、可靠、适应等性能。4、经济性。时间效率、空间效率高9/24/202416133 算法的性能分析 1 1算法性能的评价指标算法性能的评价指标（1）算法的时间复杂度。 一个算法执行所使用的时间称为该算法的时间复杂度。 用T=T（n）表示，n为问题的规模 。最坏时间复杂度：在最坏情况下执行算法在所花费的时间。最好时间复杂度：在最好情况下执行算法在所花费的时间。平均时间复杂度：在平均情况下执行算法在所花费的时间。 （2）算法的空间复杂度执行算法过程中所使用的额外存储空间的开销。不包括算法程序代码和所处理的数据本身所占用的空间部分， 记为S=S（n）单位为字节。 9/24/202417算法的性能分析2 2算法性能的评价方法算法性能的评价方法 （1 1） 精确计算法精确计算法 计算主要操作语句的执行次数。 （2 2）近似估计法）近似估计法 将时间和空间复杂度用O数量级表示： T（n）= O（f（n） ； S（n）= O（g（n）其中f（n）和g（n）是一个已知的函数（比较简单的），作为比较的尺度。 9/24/202418算法的性能分析通常使用的比较尺度有：通常使用的比较尺度有： O（1），称为常量级，算法的时间复杂度是一个常数。 O（n），称为线性级，时间复杂度是数据量n的线性函数。 O（n2），称为平方级，与n的二次多项式函数属于同一数量级。 O（n3），称为立方级，是n的三次多项式函数。 O（log2n），称为对数级，是n的对数函数 O（n log2n），是介于线性级和平方级之间一种数量级。 O（2n），称为指数级，时间复杂度与n的指数函数是同一个数量级。 O（n!），称为阶乘级， 与n的阶乘属于同一数量级。 返回首页返回首页9/24/20241914 数据结构与算法描述工具简介 1 14 41 1 符号常量定义符号常量定义# define TRUE 1# define FALSE 0# define OK 1# define ERORR 0# define OVERFLOW -1# define INFEASIBLR -21 14 42 2 数据存储结构定义数据存储结构定义用类型定义typedef描述。如：typedef int Bool ; typedef int Status ; 9/24/202420数据结构与算法描述工具简介1 14 43 3 运算符运算符算术运算符：+、*、/、%（取余）比较运算符：= = 、！=、=逻辑运算符：|（或）、&（与）、！（非） 1 14 44 4 函数函数 （1）自定义函数一般格式为：函数类型函数名（参数表） / 算法说明 局部变量说明 ； 语句序列 ； / 函数名 9/24/202421数据结构与算法描述工具简介（2 2）标准函数）标准函数 max ( 表达式1, 表达式2 , , 表达式m ) / 返回m个表达式的最大值 min ( 表达式1, 表达式2 , , 表达式m ) / 返回m个表达式的最小值 abs (表达式 ) / 返回表达式的绝对值 eof ( ) / 判断文件结束 elon ( ) / 判断行结束 bof ( ) / 判断文件开始9/24/202422数据结构与算法描述工具简介1 14 45 5 语句语句1计算赋值语句 变量名 = 表达式 ； / 单个变量赋值 变量名1 = 变量名2 = = 变量名n = 表达式 ； / 串联赋值 结构名 = 结构名 ； / 结构体变量整体赋值结构名 = 值1 , 值2, ,值m 数组名 = 表达式 ；/ 数组初始化 数组名low .high= 数组名 low .high ; / 数组整体赋值变量名 变量名; / 交换赋值 变量名 = 条件表达式？表达式1：表达式2 / 条件赋值9/24/202423数据结构与算法描述工具简介2I/O语句 scanf ( , &变量名1, &变量名2 , , &变量名k ) / 输入语句 printf ( , 表达式1, 表达式2 , , 表达式m ) / 输出语句 getchar ( ) ; / 字符输入 putchar ( ) ; / 字符输出9/24/2024243注释语句 / 注释内容 / 单行注释 /* 注释内容 */ / 多行注释 4条件选择语句 （1）单选择语句 if ( 条件表达式 ) 语句 S ; / S 可以是复合语句 语句序列; （2）双选择语句 if ( 条件表达式 ) 语句S1; else 语句S2 ; 9/24/202425格式一： 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 switch9/24/202426数据结构与算法描述工具简介5循环语句 （1）计数循环语句 for ( 循环变量 = 初值 ；循环变量= 终值 ；+/-循环变量+ /-) 语句序列 ; （2）当循环语句 while ( 条件表达式 ) 语句序列 ; （3）重复循环语句 do 语句序列 ; while ( 条件表达式 )9/24/202427数据结构与算法描述工具简介6其他控制语句 return ; / 返回语句 break ; / case或循环终止语句 exit ( 代码 ) ; / 异常结束语句 9/24/202428本章小结 1 1、数据结构的有关概念及术语。、数据结构的有关概念及术语。 数据、数据项、数据元素、数据对象、数据、数据项、数据元素、数据对象、 数据结构（数据结构（4 4种逻辑结构、种逻辑结构、4 4种存储）种存储） 、 数据类型、数据类型、ADTADT。2 2、算法的概念、特点、设计要求、算法的概念、特点、设计要求. .3 3、算法的评价指标与评价方法。、算法的评价指标与评价方法。4 4、数据结构与算法的描述工具类、数据结构与算法的描述工具类C C语言的基本知识。语言的基本知识。返回首页返回首页9/24/202429