数据结构绪.ppt

《数据结构绪.ppt》由会员分享，可在线阅读，更多相关《数据结构绪.ppt（80页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据结构绪数据结构绪现在学习的是第1页，共80页2关于教材关于教材主教材主教材 管致锦，徐慧，陈德裕管致锦，徐慧，陈德裕管致锦，徐慧，陈德裕管致锦，徐慧，陈德裕.数据结构（数据结构（C C C C版）版）版）版）.清华大学清华大学清华大学清华大学出版社出版社出版社出版社实践教材实践教材 徐慧等徐慧等.数据结构实践教程数据结构实践教程数据结构实践教程数据结构实践教程.清华大学出版社清华大学出版社习题与学习辅导习题与学习辅导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导陈德裕等。数据结构习题与学习指导.清华大学出版社清华大学出版社现在学习的是第2页

2、，共80页3如何使用教材如何使用教材主教材主教材 基本原理、学习中心基本原理、学习中心实践教材实践教材 验证实验验证实验验证实验验证实验设计实验设计实验设计实验设计实验综合实验综合实验综合实验综合实验辅导教材辅导教材 知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析知识结构、学习要点、重点难点释疑、习题解析光盘光盘 验证实验源程序验证实验源程序现在学习的是第3页，共80页4第第 1 1 章章 绪论绪论现在学习的是第4页，共80页5本章目录本章目录1.1数据结构的相关概念数据结构的相关概念 1.2数据类型和抽象数据类型

3、数据类型和抽象数据类型 1.3算法与算法分析算法与算法分析 现在学习的是第5页，共80页61.1 1.1 基本概念基本概念1.1.数据结构历史沿革数据结构历史沿革2.2.数据结构研究范畴数据结构研究范畴3.3.数据结构基本概念数据结构基本概念4.4.基本的逻辑结构基本的逻辑结构5.5.基本的物理结构基本的物理结构现在学习的是第6页，共80页7 1968196819681968年美国人年美国人Donald E.KnuthDonald E.KnuthDonald E.KnuthDonald E.Knuth开创了数开创了数开创了数开创了数据结构的最初体系，他所著的据结构的最初体系，他所著的据结构的最

4、初体系，他所著的据结构的最初体系，他所著的计算机程计算机程序设计的艺术序设计的艺术第一卷第一卷基本算法基本算法是第是第是第是第一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。构及其操作的著作。构及其操作的著作。构及其操作的著作。19681968年，数据结构作为一门独立的课程在年，数据结构作为一门独立的课程在年，数据结构作为一门独立的课程在年，数据结构作为一门独立的课程在国外开始出现。国外开始出现。国外开始出现。国外开始出现。数据结构历史沿革数据结构历史沿革现在学习的是第7页

5、，共80页8数据结构的发展数据结构的发展 从从从从20202020世世世世纪纪纪纪6060年年年年代代代代末末末末到到到到7070年年年年代代代代初初初初，出出出出现现现现了了了了大大大大型型型型程程程程序序序序，软软软软件件件件也也也也相相相相对对对对独独独独立立立立，结结结结构构构构程程程程序序序序设设设设计计计计成成成成为为为为程程程程序序序序设设设设计计计计方方方方法法法法学学学学的的的的主主主主要要要要内内内内容容容容，人人人人们们们们越来越重视数据结构越来越重视数据结构越来越重视数据结构越来越重视数据结构从从7070年代中期到年代中期到年代中期到年代中期到80808080年代，各种

6、版本的数据结构著作相继出年代，各种版本的数据结构著作相继出年代，各种版本的数据结构著作相继出年代，各种版本的数据结构著作相继出现。目前，数据结构的发展并未终结，一方面，面向各专门现。目前，数据结构的发展并未终结，一方面，面向各专门现。目前，数据结构的发展并未终结，一方面，面向各专门现。目前，数据结构的发展并未终结，一方面，面向各专门领域中特殊问题的数据结构得到研究和发展，如多维图形数领域中特殊问题的数据结构得到研究和发展，如多维图形数领域中特殊问题的数据结构得到研究和发展，如多维图形数领域中特殊问题的数据结构得到研究和发展，如多维图形数据结构等；另一方面，从抽象数据类型和面向对象的观点来据结构

7、等；另一方面，从抽象数据类型和面向对象的观点来据结构等；另一方面，从抽象数据类型和面向对象的观点来据结构等；另一方面，从抽象数据类型和面向对象的观点来讨论数据结构已成为一种新的趋势，越来越被人们所重视。讨论数据结构已成为一种新的趋势，越来越被人们所重视。讨论数据结构已成为一种新的趋势，越来越被人们所重视。讨论数据结构已成为一种新的趋势，越来越被人们所重视。数据结构问题起源于程序设计数据结构问题起源于程序设计 现在学习的是第8页，共80页9 数据结构的发展并未终结数据结构的发展并未终结1.1.1.1.无结构阶段无结构阶段2.2.2.2.结构化阶段：数据结构算法程序结构化阶段：数据结构算法程序结构

8、化阶段：数据结构算法程序结构化阶段：数据结构算法程序3.3.面向对象阶段：面向对象阶段：面向对象阶段：面向对象阶段：（数据结构算法）程序（数据结构算法）程序（数据结构算法）程序（数据结构算法）程序数据结构的发展阶段数据结构的发展阶段现在学习的是第9页，共80页10数据结构研究对象数据结构研究对象计算机科学是对信息进行表示和处理的科学。计算机科学是对信息进行表示和处理的科学。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。计算机中表示和处理的信息以数据的形式体现。数据的表示和组织直接关系到计算机程序能否处理这些数据数据

9、的表示和组织直接关系到计算机程序能否处理这些数据数据的表示和组织直接关系到计算机程序能否处理这些数据数据的表示和组织直接关系到计算机程序能否处理这些数据以及处理的效率。以及处理的效率。以及处理的效率。以及处理的效率。设计高效率、高可靠性的程序需要设计高效率、高可靠性的程序需要：(1)(1)研究数据的特性、数据间的相互关系；研究数据的特性、数据间的相互关系；(2)(2)数据在计算机内部的存储表示。数据在计算机内部的存储表示。(3)(3)(3)(3)利用这些特性和关系设计出相应的算法和程序利用这些特性和关系设计出相应的算法和程序 数值计算数值计算数值计算数值计算非数值计算非数值计算现在学习的是第1

10、0页，共80页11 结构静力分析计算结构静力分析计算 -线性代数方程组线性代数方程组 -环流模式方程环流模式方程 (球面坐标系球面坐标系)全球天气预报全球天气预报 数值计算的程序设计问题数值计算的程序设计问题现在学习的是第11页，共80页12数据计算问题：百鸡问题数据计算问题：百鸡问题公元公元公元公元5 5世纪末，我国古代数据家张丘建在他所撰写的世纪末，我国古代数据家张丘建在他所撰写的算经算经算经算经中，提出了这样一个问题：中，提出了这样一个问题：“鸡翁一，值钱五；鸡翁一，值钱五；鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡鸡母一，值钱三；鸡雏三，值钱一。百钱买百鸡，问鸡翁、母、雏各几何？

11、即：翁、母、雏各几何？即：公鸡每只公鸡每只公鸡每只公鸡每只5 5元、母鸡每只元、母鸡每只3 3元、小鸡元、小鸡元、小鸡元、小鸡3 3 3 3只只只只1 1 1 1元，用元，用元，用元，用100100100100元钱买元钱买元钱买元钱买100100只鸡，求公鸡、母鸡、小鸡的只数。只鸡，求公鸡、母鸡、小鸡的只数。只鸡，求公鸡、母鸡、小鸡的只数。只鸡，求公鸡、母鸡、小鸡的只数。设设a a、b b、c c分别为公鸡、母鸡、小鸡的只数，则：分别为公鸡、母鸡、小鸡的只数，则：a+b+c=100a+b+c=100 5a+3b+c/3=100 5a+3b+c/3=100 c%3=0 c%3=0现在学习的是第1

12、2页，共80页13非数值计算问题：非数值计算问题：学籍管理问题学籍管理问题姓名姓名学号学号性性别别年年龄龄健康状况健康状况王好好王好好0721010107210101男男2020良好良好李平平李平平0721010207210102男男1919一般一般赵赵深深深深0721010307210103女女1818良好良好钱钱多多多多0721010407210104男男1919较较差差.现在学习的是第13页，共80页14 以上家庭成员关系之间构成了一个树状结构，结构以上家庭成员关系之间构成了一个树状结构，结构以上家庭成员关系之间构成了一个树状结构，结构以上家庭成员关系之间构成了一个树状结构，结构中的数据

13、元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。中的数据元素之间存在一对多的关系。构成家庭成员名的集合，构成家庭成员名的集合，如如 父亲，儿子，女儿，孙子，孙女父亲，儿子，女儿，孙子，孙女，这些数据有一个共，这些数据有一个共，这些数据有一个共，这些数据有一个共同特征，即他们都是家庭的成员名。同特征，即他们都是家庭的成员名。同特征，即他们都是家庭的成员名。同特征，即他们都是家庭的成员名。非数值计算问题：非数值计算问题：家庭成员的关系家庭成员的关系现在学习的是第14页，共80页15如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.

14、非数值计算问题：非数值计算问题：人机对弈问题人机对弈问题现在学习的是第15页，共80页16C C C C4 4 4 4,C,C,C,C5 5 5 5,C,C,C,C6 6 6 6数据库原理数据库原理数据库原理数据库原理C C C C7 7 7 7C C C C2 2 2 2,C C C C4 4 4 4计算机原理计算机原理计算机原理计算机原理C C C C6 6 6 6C C C C3 3 3 3,C,C,C,C4 4 4 4数据结构数据结构数据结构数据结构C C C C5 5 5 5C C C C1 1 1 1,C,C,C,C2 2 2 2程序设计程序设计程序设计程序设计C C C C4 4

15、 4 4C C C C1 1 1 1离散数学离散数学离散数学离散数学C C C C3 3 3 3无无无无计算机导论计算机导论计算机导论计算机导论C C C C2 2 2 2无无无无高等数学高等数学高等数学高等数学C C C C1 1 1 1先修课先修课先修课先修课课程名称课程名称课程名称课程名称编号编号编号编号C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？非数值计算问题：非数值计算问题：教学计划编排问题教学计划编排问题现在学习的是第16页，共80页17图 1-2 煤气管道的铺设示意图 以上煤气管道线之间构成了网状结构，结构中的数据元素之以上煤气管道线之间构

16、成了网状结构，结构中的数据元素之间存在多对多的关系。间存在多对多的关系。非数值计算问题：非数值计算问题：煤气管道的铺设煤气管道的铺设如下图需为城市的各小区之间铺设煤气管道，对如下图需为城市的各小区之间铺设煤气管道，对如下图需为城市的各小区之间铺设煤气管道，对如下图需为城市的各小区之间铺设煤气管道，对 n n 个小个小区只需铺设区只需铺设 n-1 n-1 n-1 n-1 条管线，由于地理环境等不同因素使各条条管线，由于地理环境等不同因素使各条条管线，由于地理环境等不同因素使各条条管线，由于地理环境等不同因素使各条管线所需投资不同管线所需投资不同管线所需投资不同管线所需投资不同(如图上所标识如图上

17、所标识如图上所标识如图上所标识)，如何使投资成本最低，如何使投资成本最低？现在学习的是第17页，共80页18非数值计算问题：非数值计算问题：多叉路口的交通灯设置多叉路口的交通灯设置有连线的节点用不同有连线的节点用不同的颜色标记的颜色标记,表示不表示不能同时通行能同时通行要求使用的颜色数尽要求使用的颜色数尽可能少可能少,以使减少等以使减少等待时间待时间这是图论中的四色这是图论中的四色问题问题现在学习的是第18页，共80页19计算机处理问题的一般过程计算机处理问题的一般过程 问题数学模型建模实现求精机外表示机外表示处理要求处理要求逻辑结构逻辑结构基本运算基本运算存储结构存储结构算法算法现在学习的是

18、第19页，共80页20数据结构研究范畴数据结构研究范畴(1)(1)建立数据模型建立数据模型逻辑结构逻辑结构(2)(2)计算机中的表示计算机中的表示物理物理/存储结构存储结构(3)(3)操作在计算机中的实现操作在计算机中的实现算法算法现在学习的是第20页，共80页21表表1-1 数据结构的核心技术是数据结构的核心技术是数据结构的核心技术是数据结构的核心技术是分解分解分解分解与与抽象抽象。通过分解可以划分出。通过分解可以划分出。通过分解可以划分出。通过分解可以划分出数据的三个层次；数据的三个层次；数据的三个层次；数据的三个层次；通过通过抽象抽象抽象抽象，舍弃数据元素的，舍弃数据元素的具体内容，就得

19、到逻辑结构。具体内容，就得到逻辑结构。通过通过通过通过分解分解将处理要求划分成将处理要求划分成将处理要求划分成将处理要求划分成各种功能各种功能各种功能各种功能通过通过抽象抽象抽象抽象舍弃实现细节，就舍弃实现细节，就得到运算的定义。得到运算的定义。方面方面层层次次数据表示数据表示 数据数据处处理理抽象抽象逻辑结逻辑结构构基本运算基本运算实现实现物理物理结结构构算法算法评评价价不同数据不同数据结结构的比构的比较较及算法分析及算法分析数据结构课程内容体系数据结构课程内容体系数据结构的内容包括三个层次的数据结构的内容包括三个层次的五个五个“要素要素”，如表，如表，如表，如表1-11-1所示。所示。所示

20、。所示。现在学习的是第21页，共80页22数据结构地位数据结构地位现在学习的是第22页，共80页23有关概念和术语有关概念和术语数据数据：所有能：所有能输入输入输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和处识别和处理理的符号集合。的符号集合。数值数据数值数据数值数据数值数据：整数、实数等：整数、实数等：整数、实数等：整数、实数等 非数值数据非数值数据非数值数据非数值数据：图形、图象、声音、文字等：图形、图象、声音、文字等 数据元素数据元素数据元素数据元素：数据的：数据的：数据的：数据的基本基本基本基本单位，在计算机程序中通常作为一个单位，在计算机程序中通常作为一个单位，在

21、计算机程序中通常作为一个单位，在计算机程序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。数据项数据项数据项数据项：构成数据元素的不可分割的最小单位。：构成数据元素的不可分割的最小单位。关键字：关键字：是指能识别一个或多个数据元素的数据项。若能是指能识别一个或多个数据元素的数据项。若能起唯一识别的作用，则称之为起唯一识别的作用，则称之为 主主 关键字，否则称之为关键字，否则称之为关键字，否则称之为关键字，否则称之为 次次 关键字。关键字。数据对象数据对象数据对象数据对象：具有相同：具有相同性质性质性质性质的数据元素的集合。的数据元素的集合。现在学习的是第23页，共80页24数据、数据元素

22、、数据项之间的关系数据、数据元素、数据项之间的关系包含关系包含关系：数据是由数据元素组成，数据元素是由：数据是由数据元素组成，数据元素是由数据项组成。数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数据单位，是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。其中的数据项一般不予考虑。姓名姓名学号学号性别性别班号班号出生日期出生日期入学成绩入学成绩年年月月日日现在学习的是第24页，共80页25数据结构数据结构数据结构数据结构：相互之间存在一定：相互之间存在一定：相互之间存在一定：相互之间存在一定关系关系关系关系的数据元素的集合。按照视的数据元素的集合。按照视的数据元素的集合。按

23、照视的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。点的不同，数据结构分为逻辑结构和存储结构。点的不同，数据结构分为逻辑结构和存储结构。点的不同，数据结构分为逻辑结构和存储结构。逻辑结构逻辑结构：指数据元素之间：指数据元素之间：指数据元素之间：指数据元素之间逻辑关系逻辑关系的整体。的整体。的整体。的整体。关联方式或邻接关系关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据模型数据的逻辑结构是从具体问题抽象出来的数据模型数据结构数据结构存储结构存储结构：又称为：又称为物理结构物理结构物理结构物理结构，是数据及其逻辑结构在，是数据及其逻辑结构在，是数据及其逻辑结构在，是数

24、据及其逻辑结构在计计算机算机中的表示。中的表示。实质上是内存分配，实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。现在学习的是第25页，共80页26典型逻辑结构典型逻辑结构2.线性表：数据元素之间存在着数据元素之间存在着一对一的线性关系；一对一的线性关系；3.树：数据元素之间存在数据元素之间存在着一对多的层次关系着一对多的层次关系ABCDEFGHIJMKL4.图：数据元素之间存在数据元素之间存在 着多对多的任意关系。着多对多的任意关系。BACDFE1.集合：数据元素之间就是数据元素之间就是 “属于同一个集合属于同一个集合”现在学习的是第26页，共80页27数据

25、结构的形式定义数据结构的形式定义 Data_Structure Data_Structure（D D，R R）（1-11-1）D D是数据元素的有限集，是数据元素的有限集，R R是是D D上关系的有限集。上关系的有限集。D=D=父亲，儿子，女儿，孙子，孙女父亲，儿子，女儿，孙子，孙女父亲，儿子，女儿，孙子，孙女父亲，儿子，女儿，孙子，孙女 R=R=R=R=（父亲（父亲,儿子）儿子）,（父亲（父亲（父亲（父亲,女儿）女儿）,（儿子（儿子,孙子），孙子），孙子），孙子），(儿子儿子儿子儿子,孙女）孙女）例例1.21.21.21.2中家庭成员数据结构可以中家庭成员数据结构可以中家庭成员数据结构可以中

26、家庭成员数据结构可以表示成：表示成：表示成：表示成：F=(D,R)F=(D,R)F=(D,R)F=(D,R)现在学习的是第27页，共80页28 数组的形式定义数组的形式定义例：一维数组，A6=a1,a2,a3,a4,a5,a6R=|i=1,2,3,4,5D=a1,a2,a3,a4,a5,a6a1a1a2a2a3a3a4a4a5a5a6a6例：二维数组D=a1,a2,a3,a4,a5,a6 R=row,col row=,col=,现在学习的是第28页，共80页29存储结构存储结构数据结构在计算机中的表示（又称映像）称为数据的数据结构在计算机中的表示（又称映像）称为数据的数据结构在计算机中的表示（

27、又称映像）称为数据的数据结构在计算机中的表示（又称映像）称为数据的物理结构物理结构物理结构物理结构，或称或称或称或称存储结构存储结构存储结构存储结构。它所研究的是数据结构在计算机中的实现。它所研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。方法，包括数据结构中元素的表示及元素间关系的表示。1.1.顺序存储顺序存储2.2.链式存储链式存储3.3.散列存储散列存储4.4.索引存储索引存储现在学习的是第29页，共80页30顺序存储方法顺序存储方法顺序存储方法：顺序存储方法：把逻辑上相邻的元素存储在物理位置相邻的把逻辑上相邻的元素存储在物理位置相邻的把逻辑上相邻的元素

28、存储在物理位置相邻的把逻辑上相邻的元素存储在物理位置相邻的存储单元中。顺序存储结构是一种最基本的存储表示方法，通存储单元中。顺序存储结构是一种最基本的存储表示方法，通存储单元中。顺序存储结构是一种最基本的存储表示方法，通存储单元中。顺序存储结构是一种最基本的存储表示方法，通常借助于程序设计语言中的数组来实现。常借助于程序设计语言中的数组来实现。常借助于程序设计语言中的数组来实现。常借助于程序设计语言中的数组来实现。现在学习的是第30页，共80页31链式存储方法链式存储方法链式存储方法：链式存储方法：链式存储方法：链式存储方法：对逻辑上相邻的元素不要求其物理位置相邻，对逻辑上相邻的元素不要求其物

29、理位置相邻，对逻辑上相邻的元素不要求其物理位置相邻，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针字段来表示。链式存储结构元素间的逻辑关系通过附设的指针字段来表示。链式存储结构元素间的逻辑关系通过附设的指针字段来表示。链式存储结构元素间的逻辑关系通过附设的指针字段来表示。链式存储结构通常借助于程序设计语言中的指针类型来实现。通常借助于程序设计语言中的指针类型来实现。通常借助于程序设计语言中的指针类型来实现。通常借助于程序设计语言中的指针类型来实现。现在学习的是第31页，共80页32其它存储方法其它存储方法根据关键字根据关键字根据关键字根据关键字keykeyH(key)H

30、(key)H(key)H(key)，来确定存储地址，来确定存储地址，来确定存储地址，来确定存储地址散列存储散列存储索引存储索引存储a4a4a4a4a3a3a3a3a2a2a1a1a1a1现在学习的是第32页，共80页33逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，的，反映了数据内部的构成方式；数据的存储结构属反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是于具体实现的视图，是面向计算机面向计算机的。的。一种一种数据的逻辑结构可以用数据的逻辑结构可以用多种多种存储结构来存储，存储结构来存储

31、，而采用而采用不同不同的存储结构，其数据处理的效率往往是的存储结构，其数据处理的效率往往是不同不同的。的。现在学习的是第33页，共80页341.2 1.2 数据类型数据类型1.1.数据类型数据类型2.2.抽象数据类型抽象数据类型现在学习的是第34页，共80页35数据类型数据类型数据类型（数据类型（Data TypeData Type）:是一个值的集合和定义在这个是一个值的集合和定义在这个值集上的一组操作的总称。值集上的一组操作的总称。在高级程序设计语言中，数据类型可分为两类在高级程序设计语言中，数据类型可分为两类在高级程序设计语言中，数据类型可分为两类在高级程序设计语言中，数据类型可分为两类：

32、原子类型原子类型原子类型原子类型和和结构类型结构类型结构类型结构类型。原子类型原子类型原子类型原子类型 ：原子类型的值是不可分解的。如整型、字：原子类型的值是不可分解的。如整型、字符型、浮点型、双精度型等符型、浮点型、双精度型等 结构类型结构类型结构类型结构类型：结构类型的值是可分解的，如数组：结构类型的值是可分解的，如数组 、指针、指针、结构等。结构等。现在学习的是第35页，共80页36整型整型 intint浮点型浮点型 floatfloat字符型字符型 charchar逻辑型逻辑型 boolbool双精度型双精度型 doubledouble实型实型C C 语言中提供的基本数据类型语言中提供

33、的基本数据类型现在学习的是第36页，共80页37typedef struct int y;/年号 Year int m;/月号 Month int d;/日号 Day DateType;/日期类型定义定义“日期日期”为:定义定义“学生学生”为:typedef struct char id8;/学号 char name16;/姓名 char sex;/性别M/F:男/女 DateType bdate;/出生日期 Student;/学生类型结构类型结构类型现在学习的是第37页，共80页38抽象数据类型抽象数据类型1.1.数据类型数据类型（Data TypeData TypeData TypeDat

34、a Type）：一组）：一组）：一组）：一组值值值值的集合以及定义于这个的集合以及定义于这个的集合以及定义于这个的集合以及定义于这个值集上的一组值集上的一组值集上的一组值集上的一组操作操作操作操作的总称。的总称。的总称。的总称。例如：例如：例如：例如：C+C+C+C+中的整型变量中的整型变量 2.2.2.2.抽象抽象（AbstractAbstract）:抽出问题本质的特征而忽略非本质的抽出问题本质的特征而忽略非本质的抽出问题本质的特征而忽略非本质的抽出问题本质的特征而忽略非本质的细节。细节。细节。细节。例如：例如：例如：例如：地图、驾驶汽车地图、驾驶汽车地图、驾驶汽车地图、驾驶汽车3.3.3.

35、3.抽象数据类型抽象数据类型抽象数据类型抽象数据类型（Abstract Data TypeAbstract Data TypeAbstract Data TypeAbstract Data Type，ADTADT）:一个一个一个一个数据结数据结构构以及定义在该结构上的以及定义在该结构上的一组操作一组操作一组操作一组操作的总称。的总称。的总称。的总称。现在学习的是第38页，共80页39ADTADT是对数据类型的进一步抽象是对数据类型的进一步抽象 ADT逻辑结构逻辑结构操作集合操作集合数据结构数据结构存储结构存储结构算法设计算法设计类类成员变量成员变量成员函数成员函数a.使用视图使用视图 b.设计

36、视图设计视图 c.实现视图实现视图 ADT的定义的定义 ADT的设计的设计 ADT的实现的实现ADTADT的不同视图的不同视图现在学习的是第39页，共80页40抽象数据类型可用抽象数据类型可用（D D，S S，P P）三元组表示三元组表示其中，其中，D D 是数据对象，是数据对象，S S 是是 D D 上的关系集，上的关系集，P P 是对是对 D D 的基本操作集。的基本操作集。抽象数据类型的形式化描述抽象数据类型的形式化描述现在学习的是第40页，共80页41ADTADT描述描述ADT ADT 抽象数据类型名抽象数据类型名抽象数据类型名抽象数据类型名 数据对象数据对象：数据对象的定义数据对象的

37、定义 数据关系数据关系：数据关系的定义数据关系的定义 基本操作基本操作基本操作基本操作：基本操作的定义基本操作的定义 ADT ADT 抽象数据类型名抽象数据类型名抽象数据类型名抽象数据类型名基本操作的定义格式为：基本操作的定义格式为：基本操作名基本操作名基本操作名基本操作名(参数表）参数表）参数表）参数表）前置条件：前置条件：前置条件：前置条件：执行此操作前数据所必须的状态执行此操作前数据所必须的状态执行此操作前数据所必须的状态执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入执行此操作所需要的输入执行此操作所需要的输入执行此操作所需要的输入 功功 能能：该操作将完成的功能该操作

38、将完成的功能该操作将完成的功能该操作将完成的功能 输输 出出：执行该操作后产生的输出执行该操作后产生的输出执行该操作后产生的输出执行该操作后产生的输出 后置条件后置条件后置条件后置条件：执行该操作后数据的状态执行该操作后数据的状态操操作作说说明明现在学习的是第41页，共80页42抽象数据类型复数的定义抽象数据类型复数的定义ADT Complex 数据对象数据对象：D De1,e2e1,e2RealSet 数据关系数据关系：R R|e1|e1是复数的实数部分是复数的实数部分是复数的实数部分是复数的实数部分,e2 e2 是复数的虚数部分是复数的虚数部分是复数的虚数部分是复数的虚数部分 基本操作：基

39、本操作：InitComplex(&Z,v1,v2)前置条件前置条件：无：无：无：无 输输 入入：两个实数：两个实数：两个实数：两个实数V1V1、V2V2 功功功功 能能能能 ：用实部为：用实部为：用实部为：用实部为V1V1、虚部为、虚部为V2，构造复数，构造复数Z Z 输输 出：出：无无 后置条件：后置条件：复数复数Z，其实部、虚部分别为：，其实部、虚部分别为：，其实部、虚部分别为：，其实部、虚部分别为：V1、V2 .ADT Complex 现在学习的是第42页，共80页43复数的复数的ADTADT定义举例定义举例DestroyComplex(&Z)DestroyComplex(&Z)前置条件

40、：前置条件：Z Z Z Z存在存在存在存在 输输 入：复数入：复数Z Z Z Z 功功 能能 ：销毁：销毁Z Z Z Z 输输 出：无出：无 后置条件：后置条件：Z Z Z Z不存在不存在 GetReal(Z,&realPart)GetReal(Z,&realPart)GetReal(Z,&realPart)GetReal(Z,&realPart)GetImag(Z,&ImagPart)GetImag(Z,&ImagPart)GetImag(Z,&ImagPart)GetImag(Z,&ImagPart)Add(z1,z2,&sum)Add(z1,z2,&sum)现在学习的是第43页，共80页

41、44C+C+实现的复数类型实现的复数类型Class complex private:float realpart;float imagpart;public:complex(float real,float imag)/构造函数 complex();/析构函数 float GetReal();/返回复数的实部 float GetImag();/返回复数的虚部 .现在学习的是第44页，共80页451.3 1.3 算法和算法分析算法和算法分析1.1.算法算法2.2.算法描述算法描述3.3.算法分析算法分析现在学习的是第45页，共80页46算算 法法算法（算法（算法（算法（AlgorithmAlgo

42、rithmAlgorithmAlgorithm）：）：是对特定问题求解步骤的一种是对特定问题求解步骤的一种描述，是指令的有限序列。其中每一条指令表示描述，是指令的有限序列。其中每一条指令表示一个或多个操作。一个或多个操作。例：求整型数组元素中的最大值例：求整型数组元素中的最大值求解思路求解思路求解思路求解思路：采用类似采用类似采用类似采用类似“打擂打擂打擂打擂”的方法的方法Step 1Step 1Step 1Step 1：设擂主。最初把数组首元素：设擂主。最初把数组首元素：设擂主。最初把数组首元素：设擂主。最初把数组首元素A0A0A0A0设为擂主，设为擂主，即即即即A0A0最小数，以最小数，以

43、minminminmin表示，表示，min=A0min=A0min=A0min=A0；Step 2Step 2Step 2Step 2：从次元素：从次元素A1A1A1A1直至直至直至直至An-1An-1An-1An-1依次与依次与依次与依次与minmin相比，如相比，如 果比果比minmin小，则该数组元素为新擂主，小，则该数组元素为新擂主，Step 3Step 3Step 3Step 3：输出最小数：输出最小数min min 操作步骤：操作步骤：操作步骤：操作步骤：现在学习的是第46页，共80页47算法特性算法特性1.1.有穷性有穷性。一个算法必须在有穷步之后结束，即必须在有一个算法必须在有

44、穷步之后结束，即必须在有一个算法必须在有穷步之后结束，即必须在有一个算法必须在有穷步之后结束，即必须在有限时间内完成。限时间内完成。限时间内完成。限时间内完成。2.2.2.2.确定性确定性确定性确定性。算法的每一步必须有确切的定义，无二义性。算法的每一步必须有确切的定义，无二义性。算法的每一步必须有确切的定义，无二义性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着相同的输入仅有唯一的一条路径。算法的执行对应着相同的输入仅有唯一的一条路径。算法的执行对应着相同的输入仅有唯一的一条路径。算法的执行对应着相同的输入仅有唯一的一条路径。3.3.可行性可行性。算法中的每一步都可以通过已经实现

45、的基本算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。运算的有限次执行得以实现。4.4.4.4.输入输入输入输入。一个算法具有零个或多个输入，这些输入取自一个算法具有零个或多个输入，这些输入取自特特 定的数据对象集合。定的数据对象集合。5.5.5.5.输出输出输出输出。一个算法具有一个或多个输出，这些输出同输一个算法具有一个或多个输出，这些输出同输入入 之间存在某种特定的关系。之间存在某种特定的关系。现在学习的是第47页，共80页48算法与程序算法与程序算法的含义与程序十分相似，但又有区别。算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性一个程序不一定满足有穷性一

46、个程序不一定满足有穷性一个程序不一定满足有穷性。例如，操作系统，只要整个。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个处理，它仍处于动态等待中。因此，操作系统不是一个算法。算法。程序中的指令必须是机器可执行的，而算法中的指令则程序中的指令必须是机器可执行的，而算法中的指令则无此限制无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定算法代表了对问题的解，而程序则是算法在计算机上的特定算法代表了对问题的解，而程序则是算法在计算机上的特定算法代表了对问题的解，而程序

47、则是算法在计算机上的特定的实现的实现的实现的实现。一个算法若用程序设计语言来描述，则它就是一个程序。一个算法若用程序设计语言来描述，则它就是一个程序。一个算法若用程序设计语言来描述，则它就是一个程序。一个算法若用程序设计语言来描述，则它就是一个程序。现在学习的是第48页，共80页49算法设计要求算法设计要求正确性正确性。算法的执行结果应当满足预先规定的功算法的执行结果应当满足预先规定的功能和性能要求。能和性能要求。可读性可读性。一个算法应当思路清晰、层次分明、一个算法应当思路清晰、层次分明、简单明了、易读易懂。简单明了、易读易懂。健壮性健壮性。当输入不合法数据时，应能作适当处理，当输入不合法数

48、据时，应能作适当处理，不至于引起严重后果。不至于引起严重后果。高效性高效性。有较高的时间效率并能有效使用存储。有较高的时间效率并能有效使用存储空间。空间。现在学习的是第49页，共80页50算法描述 自然语言 流程图 程序设计语言 类程序设计语言 伪代码现在学习的是第50页，共80页51mnr例：求两个自然数例：求两个自然数 mm 和和 n n 的最的最大公约数大公约数欧几里德算法欧几里德算法辗转相除法辗转相除法现在学习的是第51页，共80页52 输入输入m 和和n；求求m除以除以n的余数的余数r；若若r等等于于0 0，则则n为为最最大大公公约约数数，算算法法结结束束；否则执行第否则执行第步；步

49、；将将n的值放在的值放在m中，将中，将r的值放在的值放在n中；中；重新执行第重新执行第步。步。欧几里德算法：欧几里德算法：自然语言描述描述现在学习的是第52页，共80页53优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段自然语言描述的特点自然语言描述的特点现在学习的是第53页，共80页54N开始输入m和n r=m%nr=0m=n；n=r 输出n结束Y欧几里德算法：流程图欧几里德算法：流程图现在学习的是第54页，共80页55优点：流程直观优点：流程直观 缺点：缺少严密性、灵活

50、性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次流程图描述的特点流程图描述的特点现在学习的是第55页，共80页56#include void main()coutCommonFactor(63,54)endl;欧几里德算法：程序设计语言欧几里德算法：程序设计语言int CommonFactor(int m,int n)int CommonFactor(int m,int n)int r=m%n;int r=m%n;int r=m%n;int r=m%n;while(r!=0)while(r!=0)while(r!=0)while