讲数据结构概述.ppt

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

1、讲数据结构概述1现在学习的是第1页，共41页第第1 1讲讲 数据结构概述数据结构概述1.1 1.1 数据结构的基本概念与术语数据结构的基本概念与术语1.2 1.2 数据类型和抽象数据类型数据类型和抽象数据类型1.3 1.3 算法和算法分析算法和算法分析2现在学习的是第2页，共41页 l1.1 1.1 数据结构的基本概念与术语数据结构的基本概念与术语 一、为什么要学习数据结构？一、为什么要学习数据结构？l电子计算机的主要用途：电子计算机的主要用途：l早期早期：主要用于数值计算。l 后来：后来：l 处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。3现在学习的是第3页，共41

2、页l非数值计算的程序设计问题非数值计算的程序设计问题 o算法算法+数据结构数据结构=程序设计程序设计o算法即处理问题的策略，而数据结构即为问题的数学模型。o寻求数学模型的实质寻求数学模型的实质o提取操作的对象提取操作的对象o找出这些操作对象之间含有的关系找出这些操作对象之间含有的关系o用数学模型加以描述用数学模型加以描述4现在学习的是第4页，共41页l非数值计算的程序设计问题非数值计算的程序设计问题 例例1:1:求一组求一组(n(n个个)整数中的最大值整数中的最大值算法算法:基本操作是基本操作是“比较两个数的大小比较两个数的大小”模型：线性表模型：线性表 581379025现在学习的是第5页，

3、共41页例例2 2：计算机对弈：计算机对弈算法：对弈的规则和策略算法：对弈的规则和策略模型：树模型：树 6现在学习的是第6页，共41页例例3 3 田径赛的时间安排问题：田径赛的时间安排问题：设有六个比赛项目，规定每个选手至多可参加三个设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛日程表，使得在尽可能短的时间内完成比赛。算法算法:染色染色模型模型:无向图无向图7现在学习的是第7页，共41页（1）用顶点代表比赛项目，设用如下六个不同用顶点代表比赛项目，设用如下六个不同的代

4、号代表不同的项目的代号代表不同的项目：跳高跳高 跳远跳远 标枪标枪 铅球铅球 100米米 200米米 A B C D E F（2）不能同时进行比赛的项目之间连上一条边。不能同时进行比赛的项目之间连上一条边。某选手比赛的项目必定有边相连（不能同时比赛）某选手比赛的项目必定有边相连（不能同时比赛）（3）对图上的每个顶点染一种颜色，并且要求对图上的每个顶点染一种颜色，并且要求有线相连的两个顶点不能具有相同颜色，而有线相连的两个顶点不能具有相同颜色，而总的颜色种类应尽可能地少。总的颜色种类应尽可能地少。同色可以同时比赛同色可以同时比赛l-田径赛的时间安排问题解法田径赛的时间安排问题解法8现在学习的是第

5、8页，共41页姓名项目1项目2项目3丁一 A B E马二 C D 张三 C E F李四 D F A王五 B FAEBFDC比赛时间比赛项目1A，C2B，D3E4Fl只需安排四个单位时间进行比赛（无向图无向图）9现在学习的是第9页，共41页数据结构是一门研究数据结构是一门研究非数值计算非数值计算的的程序设计问题中计算机的程序设计问题中计算机的操作对象操作对象以以及它们之间的及它们之间的关系和操作关系和操作等的学科等的学科l数据结构的定义数据结构的定义(从研究对象来看从研究对象来看):10现在学习的是第10页，共41页&数据结构课程数据结构课程所处的地位：所处的地位：介于数学、计算机介于数学、计算

6、机硬件和计算机软件硬件和计算机软件三者之间的一门核三者之间的一门核心课程。心课程。11现在学习的是第11页，共41页二、数据结构的基本概念与术语二、数据结构的基本概念与术语1、数据数据(Data):(Data):描述客观事物的存在计算机中的并可为计算机处理的符号的描述客观事物的存在计算机中的并可为计算机处理的符号的总称，是计算机程序加工的总称，是计算机程序加工的”原料原料”。（分两类：数值型数据数值型数据和非数值型数据非数值型数据）2、数据元素数据元素(Data Element):(Data Element):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处是数据的基本单位，在计算

7、机程序中通常作为一个整体进行考虑和处理。理。或称：或称：元素、结点、顶点、记录元素、结点、顶点、记录 对于文件，每个记录就是它的数据元素对于文件，每个记录就是它的数据元素对于数组，每个数组元素就是对于数组，每个数组元素就是数据元素数据元素对于字符串，字符就是数据元素对于字符串，字符就是数据元素 12现在学习的是第12页，共41页3 3、数据项数据项(Data Item)(Data Item)：是具有独立意义的不可分割的最小数据单位。是具有独立意义的不可分割的最小数据单位。一个数据数据元素元素可由若干个数据项数据项组成。数据元素:运动员数据项:姓名 俱乐部名称 出生日期 参加日期 职务 业绩数据

8、元素与数据项的例子：数据元素与数据项的例子：13现在学习的是第13页，共41页4 4、数据对象数据对象(Data Object)(Data Object)：具有相同性质的数据元素的集合。是数据的一个子集具有相同性质的数据元素的集合。是数据的一个子集。整数数据对象：N0，1，2.，字母字符数据对象：C=A,B,Z学生成绩数据对象:Cj=(101,jane,80),(102,jack,90),(103,jerry,75)数据对象的例子：数据对象的例子：14现在学习的是第14页，共41页5、逻辑结构逻辑结构 客观事物中数据元素之间的关系，与计算机无关客观事物中数据元素之间的关系，与计算机无关 分两大

9、类：线性结构分两大类：线性结构 集合集合 非线性结构非线性结构 树型结构树型结构 图型结构（网状结构）图型结构（网状结构）（1 1）集合集合：结构中的数据元素除了同属于一种类型外，别无其它关系。结构中的数据元素除了同属于一种类型外，别无其它关系。（2 2）线性结构线性结构：结构中的数据元素之间存在一对一的关系。：结构中的数据元素之间存在一对一的关系。（3 3）树型结构树型结构：结构中的数据元素之间存在一对多的关系。：结构中的数据元素之间存在一对多的关系。（4 4）图型结构图型结构：结构中的数据元素之间存在多对多的关系。：结构中的数据元素之间存在多对多的关系。15现在学习的是第15页，共41页

10、（a）集合结构 （b）线性结构 （c）树型结构（d）图型结构四类基本结构的示意图四类基本结构的示意图16现在学习的是第16页，共41页数据的逻辑结构二元组表示：数据的逻辑结构二元组表示：B=(KB=(K，R)R)其中：K：数据元素的有限集合（数据对象）R：K上的关系的有限集合，用表示.ai称为直接前驱或弧尾,aj称为直接后继或弧头.图示为:aiaj弧aiaj边有向关系无向关系17现在学习的是第17页，共41页l数据结构二元组表示法示例：数据结构二元组表示法示例：例如，有例如，有5个人，分别记为个人，分别记为a,b,c,d,e,其中其中a是是b的父的父亲，亲，b是是c的父亲，的父亲，c是是d的父

11、亲的父亲,d是是e的父亲，如果只讨论的父亲，如果只讨论他们之间所存在的父子关系，则可以用下面的二元组形他们之间所存在的父子关系，则可以用下面的二元组形式化地予以表达式化地予以表达:B=（K，R）其中：其中：K=a,b,c,d,e R=r r=,18现在学习的是第18页，共41页 说明：a是b的直接前驱，b是a的直接后继a是开始结点，e为终端结点，b、c、d为内部结点 abcde线性逻辑结构线性逻辑结构 用图形方式表示如下：用图形方式表示如下：19现在学习的是第19页，共41页6、存储结构存储结构（物理结构）（物理结构）数据结构在计算机中的表示数据结构在计算机中的表示(或称映象）称为数据或称映象

12、）称为数据的存储结构，与计算机密切相关。的存储结构，与计算机密切相关。四种基本的存储结构：四种基本的存储结构：l （1）顺序存储结构：顺序存储结构：用数据元素在存储器中的用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。相对位置来表示数据元素之间的逻辑关系。l （2）链式存储结构：链式存储结构：在每一个数据元素中增在每一个数据元素中增加一个存放地址的指针（加一个存放地址的指针（），用此指针来表示数），用此指针来表示数据元素之间的逻辑关系。据元素之间的逻辑关系。l （3）索引存储结构）索引存储结构l （4）散列存储结构）散列存储结构20现在学习的是第20页，共41页数据结构：数据结构：

13、B=（K，R）其中其中K=k1,k2,k3,k4,k5,k6,k7,k8,k9 R=r r=,这是一个线性结构，它的顺序存储方式如图所示这是一个线性结构，它的顺序存储方式如图所示:顺序存储结构示例：顺序存储结构示例：21现在学习的是第21页，共41页k1k2k3k6k5k4k7k8k9存储地址存储地址 M M100110021003100410051006100710081009特点：逻辑上相特点：逻辑上相邻的元素物理位邻的元素物理位置上也相邻置上也相邻22现在学习的是第22页，共41页数据结构：数据结构：B=（K，R）其中其中 K=k1,k2,k3,k4,k5 R=r r=,这是一个线性结构

14、，它的链式存储如图所示。这是一个线性结构，它的链式存储如图所示。链式存储结构示例：链式存储结构示例：23现在学习的是第23页，共41页100010011002100310041005100610071008存储地址存储地址 info nextk41006k21007k11003k5 k31005特点特点:逻辑上相邻逻辑上相邻物理上不一定相邻。物理上不一定相邻。24现在学习的是第24页，共41页 7、数据的运算集合数据的运算集合注意：注意：数据的运算是定义在数据的逻辑结构之上的，而运算的具数据的运算是定义在数据的逻辑结构之上的，而运算的具体实现就依赖于数据的存储结构。体实现就依赖于数据的存储结构

15、。数据的运算集合要视情况而定，一般而言，数据的运算包括插入、数据的运算集合要视情况而定，一般而言，数据的运算包括插入、删除、检索、输出、排序等。删除、检索、输出、排序等。插入：在一个结构中增加一个新的结点。删除：在一个结构删除一个结点。检索：在一个结构中查找满足条件的结点。输出：将一个结构中所有结点的值打印、输出。排序：将一个结构中所有结点按某种顺序重新排列。25现在学习的是第25页，共41页 8、数据结构定义的术语描述数据结构定义的术语描述 按一定的逻辑结构组成的一批数据（或称带结构的数据元素的集合），使用某种存储结构将这批数据存储于计算机中，并在这些数据上定义了一个运算集合。注：注：同一种

16、逻辑结构可采用不同的存储方法（以上四种之一或组同一种逻辑结构可采用不同的存储方法（以上四种之一或组合），这主要考虑的是运算方便及算法的时空要求。合），这主要考虑的是运算方便及算法的时空要求。26现在学习的是第26页，共41页 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 运算运算：检索、排序、插入、删除、修改等：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队列队列树型结构树型结构图型结构图型结构数据结构研究的三个方面：数据结构研究的三个方面：散列存储散列存储索引存储索引存储串及数组串及数组27现在学习

17、的是第27页，共41页l1.2 1.2 数据类型和抽象数据类型数据类型和抽象数据类型 l数据的抽象经历了三个发展阶段：从无类型的二进制数到基本数据类型的产生从无类型的二进制数到基本数据类型的产生 从基本数据类型到用户自定义类型的产生从基本数据类型到用户自定义类型的产生 从用户自定义类型到抽象数据类型的出现从用户自定义类型到抽象数据类型的出现 28现在学习的是第28页，共41页l1.2 1.2 数据类型和抽象数据类型数据类型和抽象数据类型 1 1、数据类型数据类型(DataType)(DataType)数据对象和在该集合上的一组操作。数据对象和在该集合上的一组操作。（如C中的int型，它的值是-

18、MAXINT,MAXINT区间上的整数，操作为：加、减、乘、除、取余等运算）l 原子数据类型 C语言中基本类型：整型、实型、字符型等l 结构数据类型 C语言中数组和结构类型等29现在学习的是第29页，共41页2 2、抽象数据类型抽象数据类型（Abstract Data Types Abstract Data Types）uu由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的由用户定义，用以表示应用问题的数据模型数据模型uu由由基本的数据类型基本的数据类型基本的数据类型基本的数据类型组成组成组成组成,并包括并包括并包括并包括一组相关的运算一组相关的运算uu

19、信息隐蔽信息隐蔽和和和和数据封装数据封装，使用与实现相分离，使用与实现相分离，使用与实现相分离，使用与实现相分离u对一个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定这些函数的参数性质。30现在学习的是第30页，共41页抽象数据类型描述的一般形式如下：抽象数据类型描述的一般形式如下：ADT 抽象数据类型名称抽象数据类型名称 数据对象：数据对象：数据关系：数据关系：操作集合：操作集合：操作名操作名1：操作名操作名n：ADT抽象数据类型名称抽象数据类型名称 31现在学习的是第31页，共41页练习：练习：指出下列二元组表示法的数据结构是属于何种逻指出下列二元组表示法的

20、数据结构是属于何种逻辑结构。辑结构。（1 1）B=(K,R)B=(K,R)K=K=a,b,c,d,e,f a,b,c,d,e,f R=,R=,（2 2）B=(K,R)B=(K,R)K=d K=di i|1i5|1i5 R=d R=,i,ij32现在学习的是第32页，共41页1.3 1.3 算法和算法分析算法和算法分析一、算法的概念和描述：一、算法的概念和描述：1 1、什么是算法？、什么是算法？求解问题的方法和步骤。求解问题的方法和步骤。2 2、算法的特性、算法的特性（1）有穷性）有穷性（2）确定性）确定性（3）可行性）可行性（4）输入（有或没有）输入（有或没有）（5）输出（一定有）输出（一定有

21、）33现在学习的是第33页，共41页3 3、判断算法好坏的标准、判断算法好坏的标准(1)正确性正确性(2)可读性可读性(3)健壮性健壮性(4)时空效率时空效率 时间效率时间效率 空间效率空间效率4 4、算法的描述、算法的描述程序流程图程序流程图伪代码伪代码 自然语言自然语言(中文中文)类高级语言类高级语言 （如：（如：abab）程序语言程序语言5 5、算法的实现、算法的实现 本课程采用本课程采用C C语言语言34现在学习的是第34页，共41页二、算法的效率二、算法的效率算法随问题的规模变大时效率变化情况。算法随问题的规模变大时效率变化情况。一个算法效率的评价主要从一个算法效率的评价主要从时间复

22、杂度时间复杂度和和空间复杂度空间复杂度来考虑。来考虑。1 1、时间复杂度（、时间复杂度（着重评价着重评价）计算算法中主要语句执行的次数计算算法中主要语句执行的次数语句频度语句频度时间复杂度时间复杂度T(n)当问题规模当问题规模n时，算法执行时间增长率。时，算法执行时间增长率。用大用大“O”表示法。记作表示法。记作T(n)=O(f(n)（f(n)：为语句频度之和的最：为语句频度之和的最高次项的数量级阶）高次项的数量级阶）问题规模问题规模n 算法求解问题的输入量算法求解问题的输入量（或初始数据量）。（或初始数据量）。35现在学习的是第35页，共41页例：分析以下程序段的时间复杂度例：分析以下程序段

23、的时间复杂度（1）A、B两数交换两数交换 C=A;A=B;B=C；时间复杂度：时间复杂度：T(n)=1+1+1=O(1)常量阶常量阶l频度是：1l频度是：1l频度是：136现在学习的是第36页，共41页（2）二重循环for(i=1;i=n;i+)for(j=1;j=i;j+)x=x+1;时间复杂度：T(n)=1+2+3+n=平方阶平方阶l频度是：1+2+3+n37现在学习的是第37页，共41页（3）for(i=1;in;i+)y=y+1;for(j=0;j=(2*n);j+)x+;l频度是：n-1频度是：时间复杂度：T(n)=38现在学习的是第38页，共41页（4）i=1;while(i=n)

24、i=i*2 对数阶对数阶l频度是：1l频度是：f(n)l则有：即：取最大值：l时间复杂度为：39现在学习的是第39页，共41页 常量阶常量阶 O(1)l对数阶对数阶 O(log2n)l线性阶线性阶 O(n)l线性对数阶线性对数阶 O(nlog2n)l平方阶平方阶 O(n2)l立方阶立方阶 O(n3)llk次方阶次方阶 O(nk)l指数阶指数阶 O(2n)l常见时间复杂度按数量级递增排列常见时间复杂度按数量级递增排列l递增递增40现在学习的是第40页，共41页图图1 各种数量级的时间复杂度各种数量级的时间复杂度T(n)曲线的比较曲线的比较 图1 是不同数量级时间复杂度的特性曲线41现在学习的是第41页，共41页