数据结构与算法分析课件

数据结构与算法分析主讲教师主讲教师董洁董洁数据结构与算法分析主1第一章第一章绪论绪论知识点知识点2：基本概念和术语基本概念和术语第一章绪论知识点2：基本概念和术语2一、基本概念一、基本概念数据数据n数据数据(Data)：信息的符号表示。在计算机科学中是指所信息的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。有能输入到计算机中并被计算机程序处理的符号的总称。例如：文字处理程序处理的字符，数值分析程序处理的整数和实数，所有计算机程序加工的原料都称为数据，含义非常含义非常广泛广泛，可以是编码后的图像、声音等。一、基本概念数据数据(Data)：信息的符号表示。在计算3一、基本概念一、基本概念数据元素数据元素n数据元素数据元素(DataElement)：是数据的基本单位，是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。例如：通讯录中的每一条信息，人机对弈程序中的棋局，地图中的每一个城市，这些都是数据元素。一个数据元素可由若干个数据项（一个数据元素可由若干个数据项（DataItem）组成）组成。数据数据项是数据的不可分割的最小单位。项是数据的不可分割的最小单位。例如：书目中的每一项，如书名、作者名等，都是数据项。一、基本概念数据元素数据元素(DataElement)4图书信息表：图书信息表：数据、数据元素、数据项及其关系数据、数据元素、数据项及其关系数据元素数据元素数据项数据项数据数据图书信息表：数据、数据元素、数据项及其关系数据元素数据5一、基本概念一、基本概念数据对象数据对象n数据对象数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。例如：整数的数据对象是-3，-2，-1，0，1，2，3，；英文字符类型的数据对象是A，B，C，D，E，F，一、基本概念数据对象数据对象(DataObject)：6二、数据结构（重点二、数据结构（重点）数据结构数据结构(DataStructure)：是相互之间存在一种或多种特是相互之间存在一种或多种特定关系的数据元素的集合。定关系的数据元素的集合。主要指：主要指：n逻辑结构逻辑结构n物理结构物理结构本书采用本书采用抽象数据类型抽象数据类型来描述数据结构。来描述数据结构。进一步明确数据结构的研究内容：进一步明确数据结构的研究内容：二、数据结构（重点）数据结构(Data71、逻辑结构、逻辑结构基本结构基本结构逻辑结构逻辑结构：数据元素之间存在的关系数据元素之间存在的关系。有以下。有以下4类基本结类基本结构：构：集合集合：同属于一种类型。：同属于一种类型。线性结构线性结构：一对一。如线性表、栈、队列：一对一。如线性表、栈、队列树型结构树型结构：一对多。如树：一对多。如树图状结构或网状结构图状结构或网状结构：多对多。：多对多。1、逻辑结构基本结构逻辑结构：数据元8逻辑结构逻辑结构描述形式描述形式数据结构的形式定义为：数据结构是一个二元组：数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)D是数据元素的有限集，是数据元素的有限集，S是是D上关系的有限集上关系的有限集。如：已知逻辑结构linear=(D,R)其中：D=1,2,3,4,5R=,则其逻辑图为：12345逻辑结构描述形式数据结构的形式定义为：数9练习：练习：已知一个逻辑结构已知一个逻辑结构t=(D,R)其中：其中：D=a,b,c,e,f,g,hR=,判断其属于哪种类型的逻辑结构。判断其属于哪种类型的逻辑结构。abcefgh分析其逻辑图为：分析其逻辑图为：树型结构树型结构返回练习：已知一个逻辑结构t=(D,R)其中：abcef10物理结构物理结构定义与分类定义与分类物理结构物理结构：数据结构在计算机中的表示，又称为存储结构，数据结构在计算机中的表示，又称为存储结构，可根据在计算机中的不同表示法主要分为以下两种：可根据在计算机中的不同表示法主要分为以下两种：n顺序存储结构：顺序存储结构：借助元素在存储器中的相对位置来表示数据元借助元素在存储器中的相对位置来表示数据元素间的逻辑关系素间的逻辑关系顺序映象顺序映象n链式存储结构：链式存储结构：借助指示元素存储地址的指针表示数据元素间借助指示元素存储地址的指针表示数据元素间的逻辑关系的逻辑关系非顺序映象非顺序映象物理结构定义与分类物理结构：数据结构在11元素元素n n.元素元素i i.元素元素2 2元素元素1 11 2 i n存储序号存储序号存储内容存储内容相对位置表达逻辑顺序相对位置表达逻辑顺序顺序存储顺序存储返回元素n.元素i.元素2元素112121536元素元素2 21400元素元素1 11346元素元素3 3元素元素4 41345h存储地址存储地址 存储内容存储内容 指针指针 13451345 元素元素1 1 14001400 13461346 元素元素4 4 .14001400 元素元素2 2 15361536 .15361536 元素元素3 3 13461346 链式存储链式存储：额外增加指针域表示逻辑关系额外增加指针域表示逻辑关系h返回1536元素21400元素11346元素3元素4134513数据结构小结：数据结构小结：数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树形结构树形结构图形结构图形结构 n算法设计的选取取决于数据的逻辑结构，算算法设计的选取取决于数据的逻辑结构，算法的实现依赖于采用的存储结构法的实现依赖于采用的存储结构n数据的逻辑结构只是抽象反映数据元素的逻辑关系；数据的逻辑结构只是抽象反映数据元素的逻辑关系；n数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。数据的存储（物理）结构是数据的逻辑结构在计算机存储器中的实现。数据结构小结：数据的逻辑结构数据的存储结构数据的运算14三、数据类型和抽象数据类型三、数据类型和抽象数据类型定义定义：高级语言中指数据的取值范围及其上可进行的操作高级语言中指数据的取值范围及其上可进行的操作的总称。的总称。例如，例如，C语言中的整型，值集为某个区间上的整数，定语言中的整型，值集为某个区间上的整数，定义在其上的操作为加、减、乘、除取余数等算术运算。义在其上的操作为加、减、乘、除取余数等算术运算。数据类型可分为不可再分的数据类型可分为不可再分的原子类型原子类型和若干成分按照某种和若干成分按照某种结构组成的结构组成的结构类型结构类型。1、数据类型、数据类型三、数据类型和抽象数据类型定义：高级语言中指数据的取值范围及152、抽象数据类型、抽象数据类型抽象数据类型抽象数据类型：一个数学模型以及定义在该模型上的一组操作。：一个数学模型以及定义在该模型上的一组操作。本质：本质：该定义仅取决于逻辑特性，而与内部的表示无关。该定义仅取决于逻辑特性，而与内部的表示无关。实质是数据类型，但范畴更广实质是数据类型，但范畴更广，不再局限于已定义并实现的数据类型，不再局限于已定义并实现的数据类型，还包括自定义的数据类型。还包括自定义的数据类型。抽象数据类型 数学模型数学模型 定义在该模型上的一组操作定义在该模型上的一组操作数据的取值范围数据的取值范围+及其上可进行操作及其上可进行操作2、抽象数据类型抽象数据类型：一个数学模型以及定义16抽象数据类型表示方法：抽象数据类型表示方法：ADT抽象数据类型名抽象数据类型名数据对象数据对象：数据关系数据关系：基本操作基本操作：ADT抽象数据类型名抽象数据类型名其中：其中：数据对象数据对象和和关系关系的定义用伪代码，的定义用伪代码，基本操作基本操作的定义格式为：的定义格式为：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件：操作结果操作结果:抽象数据类型表示方法：ADT抽象数据类型17n基本操作有两种参数：基本操作有两种参数：赋值参数：提供输入值；赋值参数：提供输入值；引用参数：以引用参数：以&打头，打头，主要是返回操作结果主要是返回操作结果。n “初初始始条条件件”：执执行行本本操操作作时时数数据据结结构构和和参参数数应应满满足足的的条条件，若不满足，则操作失败，并返回相应出错信息。件，若不满足，则操作失败，并返回相应出错信息。初始条件为空时省略。初始条件为空时省略。n “操操作作结结果果”：操操作作完完成成后后，数数据据结结构构的的变变化化状状况况和和返返回回的结果。的结果。数据结构与算法分析课件18例：抽象数据类型三元组的定义：例：抽象数据类型三元组的定义：三元组是具有如下特性的数据元素：由三个相同类型的有序数三元组是具有如下特性的数据元素：由三个相同类型的有序数据项组成。据项组成。ADTTriplet数据对象：数据对象：D=e1，e2，e3|e1，e2，e3 ElemSet(定义了关系运算的某个集合定义了关系运算的某个集合)数据关系：数据关系：R=e1，e2，=0任意数据元素的集合数据关系R1=|ai-1,ai D,i=2,.,n除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(&L,i,e)ListDelete(&L,i,e)L为线性表，i为位置，e为数据元素。例：线性表抽象数据类型的表示例：线性表抽象数据类型的表示名称线性表数据对象D=ai|aiElemSet,i=123n1）数据类型数据类型数据类型数据类型指的是高级语言程序设计支持的基本数据类型；指的是高级语言程序设计支持的基本数据类型；指的是高级语言程序设计支持的基本数据类型；指的是高级语言程序设计支持的基本数据类型；n n2 2）ADTADT指的是自定义的数据类型；指的是自定义的数据类型；指的是自定义的数据类型；指的是自定义的数据类型；*本课程将要学习的本课程将要学习的本课程将要学习的本课程将要学习的ADTADT是是是是 线性表类型、栈类型、队列类型、数组类型、广义表类型、树类线性表类型、栈类型、队列类型、数组类型、广义表类型、树类线性表类型、栈类型、队列类型、数组类型、广义表类型、树类线性表类型、栈类型、队列类型、数组类型、广义表类型、树类型、图类型、查找表类型等。型、图类型、查找表类型等。型、图类型、查找表类型等。型、图类型、查找表类型等。数据类型与抽象数据类型数据类型与抽象数据类型(ADT)的区别的区别1）数据类型指的是高级语言程序设计支持的基本数据类型；数据类24