《数据结构》课件1第1章 绪论.ppt
《《数据结构》课件1第1章 绪论.ppt》由会员分享,可在线阅读,更多相关《《数据结构》课件1第1章 绪论.ppt(67页珍藏版)》请在文库网上搜索。
1、1.1 数据结构讨论的范畴数据结构讨论的范畴1.2 基本概念及术语基本概念及术语1.3 算法和算法的分析算法和算法的分析教教 学学 内内 容容要点:要点:1 1、数据结构的基本概念及有关术语、数据结构的基本概念及有关术语2 2、算法及算法的分析方法算法及算法的分析方法重点:重点:1 1、有关数据结构的名词和术语的含义;、有关数据结构的名词和术语的含义;2 2、语句频度和时间复杂度、空间复杂度的语句频度和时间复杂度、空间复杂度的估算。估算。难点:难点:时间复杂度的估算。时间复杂度的估算。Niklaus Wirth:(著名的瑞士科学家沃思教授)Algorithm+Data Structures=P
2、rograms (算算 法法 +数数 据据 结结 构构 =程程 序序)程程 序序:算算 法法:数据结构数据结构:为计算机处理问题而编制的一组指令集 求解问题的策略(是对数据运算的描述)问题的数学模型(存储结构和逻辑结构)1.11.1 数据结构讨论的范畴数据结构讨论的范畴求解问题的基本步骤求解问题的基本步骤1.1.确定求解问题的确定求解问题的数学模型数学模型 (逻辑结构逻辑结构);2.2.确定确定存储结构存储结构;3.3.设计设计算法算法;4.4.编程编程并测试结果。并测试结果。是在于解决两个主要问题:是在于解决两个主要问题:一一是是根据实际问题选择一种好的存储根据实际问题选择一种好的存储结构;
3、结构;二是二是设计一个好的算法,而设计一个好的算法,而好的算法在很大程度上取决于描述好的算法在很大程度上取决于描述实际问题的存储结构。实际问题的存储结构。程序设计的实质程序设计的实质1 1、数值计算的程序设计问题、数值计算的程序设计问题 很多数很多数值计算算问题的数学模型通常可用的数学模型通常可用一一组线性性或或非非线性性的代数方程的代数方程组或微分方程或微分方程组来描述。如来描述。如“鸡免同免同笼”“桥梁梁结构构设计”问题。但但大量大量非数非数值计算算问题的数学模型正是的数学模型正是本本门课程要程要讨论的数据的数据结构。构。求解问题举例求解问题举例2 2、非数值计算的程序设计问题、非数值计算
4、的程序设计问题【例一例一】求一组求一组(n(n个个)整数中的最大值整数中的最大值算法算法:?模型:模型:?基本操作是基本操作是“比较两个数的大小比较两个数的大小”但如果这些整数的值有可能达但如果这些整数的值有可能达到到1012,那么对,那么对32位的计算机来位的计算机来说,就存在一个如何表示的问说,就存在一个如何表示的问题。题。求解问题举例求解问题举例【例二例二】电话号码查询问题电话号码查询问题算法:算法:?模型:模型:?如何查询?如何查询?电话号码表电话号码表2 2、非数值计算的程序设计问题、非数值计算的程序设计问题求解问题举例求解问题举例【例三例三】煤气管道铺设问题煤气管道铺设问题算法:算
5、法:?模型:模型:?如何为城市的各小区之间铺如何为城市的各小区之间铺设煤气管道设煤气管道,使投资最小使投资最小?(对对 n 个小区只需铺设个小区只需铺设 n-1 条条管线管线)图的最小生成树图的最小生成树2 2、非数值计算的程序设计问题、非数值计算的程序设计问题求解问题举例求解问题举例方 面过程数据表示数据处理抽象逻辑结构基本运算实现存储结构算法评价 不同数据结构的比较和算法性能分析数据结构课程的内容体系数据结构课程的内容体系:简单地说简单地说,本课程本课程研究的内容包括以下三方面:研究的内容包括以下三方面:1.1.数据的逻辑结构数据的逻辑结构 2.2.数据的存储结构数据的存储结构/物理结构物
6、理结构 3.3.数据的运算数据的运算概括地说:概括地说:数据结构是一门讨论数据结构是一门讨论“描述描述现实世界实体的现实世界实体的数学模型数学模型(非数值非数值计算计算)及其上的操作(运算)及其上的操作(运算)在计在计算机中如何表示和实现算机中如何表示和实现”的学科。的学科。一、数据与数据结构一、数据与数据结构二、数据类型二、数据类型三、抽象数据类型三、抽象数据类型1.2 1.2 基本概念及术语基本概念及术语l所有能所有能被输入被输入到计算机中,且能被计算机到计算机中,且能被计算机处处理理的的符号的总称符号的总称。如:实数、整数、字符。如:实数、整数、字符(串)、图形、声音和视频等。(串)、图
7、形、声音和视频等。l对计算机而言,数据的含义极为广泛。如对计算机而言,数据的含义极为广泛。如指指纹纹、人体动作人体动作等都可以通过编码而归之于数等都可以通过编码而归之于数据的范畴。据的范畴。l是是计算机操作对象计算机操作对象的集合。的集合。数据数据(Data):(Data):一、数据与数据结构一、数据与数据结构l是是数据数据(集合)中的一个(集合)中的一个“个体个体个体个体”;l是数据结构中讨论的是数据结构中讨论的基本单位基本单位基本单位基本单位;l不同场合也叫不同场合也叫结点结点结点结点、顶顶顶顶点点点点、记录记录记录记录(。(。l数据元素有两种类型:数据元素有两种类型:“原子原子原子原子”
8、型和型和“构造构造构造构造”型型数据元素数据元素(Data Element):(Data Element):l是数据结构中讨论的是数据结构中讨论的最小最小最小最小单位单位;l构造型数据元素是由若干数据项组成。构造型数据元素是由若干数据项组成。数据项数据项(Data Item):(Data Item):数据对象(数据对象(Data ObjectData Object):是是性质相同的数据元素的性质相同的数据元素的集合。如整集合。如整数、实数和例数、实数和例1-21-2中的生产订单表。中的生产订单表。行:行:数据元素数据元素列:列:数据项数据项 请梳理一下:请梳理一下:数据、数数据、数据对象、数据
9、元素、数据项据对象、数据元素、数据项的概念及其之间的关系!的概念及其之间的关系!归纳总结归纳总结p数据数据=计算机操作对象计算机操作对象p数据对象数据对象=性质相同的数据元素的集合性质相同的数据元素的集合p数据元素数据元素=数据项数据项1+数据项数据项2+学号学号姓名姓名数学分析数学分析 普通物理普通物理高等代数高等代数20001200012000220002200032000320004200042000520005张三张三李四李四丁一丁一马二马二王五王五909080806767989856565656878767679090878789896767878767676868行:行:数据元素数
10、据元素列:列:数据项数据项数数据据数据对象数据对象 数据对象中的数据元素数据对象中的数据元素不会是孤立的不会是孤立的,而是彼此相关的而是彼此相关的,这种彼此之间的关系称为,这种彼此之间的关系称为“结构结构”。逻辑结构:逻辑结构:是指从具体问题抽象出来的数据模型,是是指从具体问题抽象出来的数据模型,是从从逻辑关系逻辑关系上描述数据,它与数据的存储无关,上描述数据,它与数据的存储无关,是独立于计算机的。如下表是一个数据结构:是独立于计算机的。如下表是一个数据结构:学号学号姓名姓名数学分析数学分析普通物理普通物理高等代数高等代数2000120002200032000420005张三张三李四李四丁一丁
11、一马二马二王五王五908067985656876790878967876768结点间的关系构成了这张学生成绩表的逻辑结构 或者说,或者说,逻辑结构是描述数据元素之间逻辑结构是描述数据元素之间的的逻辑关系逻辑关系。按按逻辑关系逻辑关系来分来分,数据结构数据结构可归结为以下四类四类:线性线性结构(1:1)树形树形结构(1:m)图状图状结构(m:n)集合集合结构(松散)非线性结构 数据结构(数据结构(Data StructureData Structure):是相互之间存在是相互之间存在一种一种或或多种关系多种关系的数的数据元素的集合。据元素的集合。例,在例,在2行行3列的二维数组列的二维数组a1,
12、a2,a3,a4,a5,a6中六个元素之间中六个元素之间存在两个关系存在两个关系:行的次序关系行的次序关系:列的次序关系列的次序关系:row=,col=,a1 a3 a5 a2 a4 a6 a1 a2 a3a4 a5 a6数据结构:数据结构:再例,在一维数组再例,在一维数组 a1,a2,a3,a4,a5,a6 的数据元素之间存在如下的的数据元素之间存在如下的次序关系次序关系:|i=1,2,3,4,5可见,不同的“关系”构成不同的“结构”数据结构:数据结构:数据结构的形式定义数据结构的形式定义为:数据结构数据结构是一个二元组 Data_Structures=(D,R)其中:D 是数据元素的有限集
13、数据元素的有限集,R是 D上关系的有限集关系的有限集。所以可用数据的逻辑结构图来形象表示由二元组所描述的结构也称为逻辑结构逻辑结构例例1 设有数据结构为:设有数据结构为:B=(D,R)D=k1,k2,k3,.k9 R=,画出其逻辑结构的图示,并确定相对于关系画出其逻辑结构的图示,并确定相对于关系R,哪些,哪些结点是开始结点,哪些是终端结点?结点是开始结点,哪些是终端结点?k2 k1 k4 k5 k3 k8 k6 k9 k7开始结点为开始结点为k1,k2(无前驱的结点)无前驱的结点)终端结点为终端结点为k6,k7(无后继的结点)无后继的结点)例例2 设有如图所示的逻辑图,给出它的数据结构。设有如
14、图所示的逻辑图,给出它的数据结构。k1 k2 k3 k6 k4 k8 k7 k5 k9 解:本题的结构如下:解:本题的结构如下:B=(D,R)D=k1,k2,k3,k9 R=,该结构是一个树形结构,其树根为该结构是一个树形结构,其树根为K1,叶子结点为,叶子结点为k2,k5,k7,k9.数据的存储结构存储结构 是逻辑结构在计算机中的表示,是逻辑结构在计算机中的表示,(即是(即是逻辑结构在存储器中的映象)映象)“数据元素数据元素”的映象的映象?“关系关系”的映象的映象?数据元素的映象方法:数据元素的映象方法:用二进制位用二进制位(bit)(bit)的位串表示数据元素的位串表示数据元素(321)1
15、0 =(501)8 =(101000001)2 A =(101)8 =(001000001)2关系的映象方法:关系的映象方法:(表示x,y的方法)1 1、顺序映象、顺序映象以相对的存储位置表示后继关系以相对的存储位置表示后继关系整个存储结构中只含数据元素本身的信息整个存储结构中只含数据元素本身的信息 x y顺序存储结构顺序存储结构(以逻辑位置关系与存储位置关系一致)(以逻辑位置关系与存储位置关系一致)链式(非线性)映象链式(非线性)映象以附加信息以附加信息(指针指针)表示后继关系表示后继关系需要用一个和 x附加在一起的指针来来指示 y 的存储位置y x链式存储结构链式存储结构数据的数据的存储结
16、构存储结构可用可用四种基本的存储方法四种基本的存储方法表示表示。1、顺序存储顺序存储 把逻辑上相邻的结点存储在物理上相邻的存储单元中。2、链接存储链接存储 对逻辑上相邻的元素不要求物理位置相邻,元素之间的逻辑关系是由附加的指针表示。3、索引存储索引存储 在存储结点信息的同时,建立附加索引表。4、散列存储散列存储 根据结点的关键字值直接计算出结点的存储地址。在不同的编程环境中,在不同的编程环境中,存储结构可有不同的描述方法。存储结构可有不同的描述方法。当用高级程序设计语言进行编程当用高级程序设计语言进行编程时,通常可用高级编程语言中提供的时,通常可用高级编程语言中提供的数据类型数据类型描述之描述
17、之。存储结构如何实现呢?存储结构如何实现呢?在用高级程序语言编写的程序中,必须对程序中出现的每个变量、常量或表达式,明确说明明确说明它们所属的数据类型数据类型。二、数据类型二、数据类型 其实数据类型反映三个方面的其实数据类型反映三个方面的内容:内容:存储结构,取值范围和能进存储结构,取值范围和能进行的操作行的操作。(Abstract Data Type 简称简称ADT)是指一个数学模型以是指一个数学模型以及定义在此数学模型上的及定义在此数学模型上的一组操作。一组操作。三、抽象数据类型三、抽象数据类型抽象数据类型的形式描述抽象数据类型的形式描述:ADT=(D,R,P)其中:其中:D 是数据对象;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 数据结构课件1第1章 绪论 课件