数据结构与软件工程

《数据结构与软件工程》由会员分享，可在线阅读，更多相关《数据结构与软件工程（78页珍藏版）》请在金锄头文库上搜索。

1、数据结构与软件工程数据结构与软件工程信息科学与技术学院信息科学与技术学院郝矿荣郝矿荣E-mail:1数据结构与软件工程数据结构与软件工程教材及参考书目：教材及参考书目：数据结构（数据结构（C语言版）语言版）严蔚敏等编严蔚敏等编清华大学出版社清华大学出版社数据结构习题集（数据结构习题集（C语言版）语言版）严蔚敏等编严蔚敏等编清华大学出版社清华大学出版社数据结构数据结构C+语言描述语言描述刘卫东等译刘卫东等译清华大学出版社清华大学出版社2数据结构与软件工程数据结构与软件工程预备知识：预备知识：C语言语言程序设计的基本技术程序设计的基本技术离散数学离散数学概率论概率论3数据结构与软件工程数据结构与软

2、件工程计算机三级偏硬：计算机三级偏硬：计算机原理计算机原理60%数据结构数据结构30%Internet等等10%研究生入学考试的核心课程研究生入学考试的核心课程4数据结构与软件工程数据结构与软件工程“ “数据结构数据结构数据结构数据结构” ”所处的地所处的地所处的地所处的地位位位位5数据结构与软件工程数据结构与软件工程要求：要求：上课认真听课上课认真听课作业按时完成作业按时完成上机实习认真，按质按量完成上机实习认真，按质按量完成6数据结构与软件工程数据结构与软件工程第一章第一章 绪绪 论论 第六章第六章 树与二叉树树与二叉树第二章第二章 线性表线性表 第七章第七章 图图第三章第三章 栈和队列栈

3、和队列 第八章第八章 动态存储管理动态存储管理第四章第四章 串串 第九章第九章 查找查找第五章第五章 数组与广义表数组与广义表 第十章第十章 内部排序内部排序7第一章第一章 绪绪 论论目的：目的：n n了解数据结构的背景了解数据结构的背景n n掌握一些基本概念和术语掌握一些基本概念和术语n n掌握抽象数据类型的定义、表示与实现掌握抽象数据类型的定义、表示与实现n n描述算法的类描述算法的类C语言语言n n掌握算法分析的一些基本方法掌握算法分析的一些基本方法8第一章第一章 绪绪 论论重点：重点：n n有关数据结构的基本概念和术语有关数据结构的基本概念和术语n n掌掌握握抽抽象象数数据据类类型型A

4、DT的的定定义义、表表示示与与实现实现n n熟悉类熟悉类C语言的书写规范语言的书写规范n n理解算法五个要素的确切含义理解算法五个要素的确切含义n n掌掌握握估估算算时时间间复复杂杂度度的的方方法法，了了解解空空间间复杂度的度量方法复杂度的度量方法9第一章第一章 绪绪 论论难点：难点：n n抽象数据类型抽象数据类型ADT的表示与实现的表示与实现n n算法复杂度的分析方法算法复杂度的分析方法10第一章第一章 绪绪 论论1.1什么是数据结构什么是数据结构1.2基本概念和术语基本概念和术语1.3抽象数据类型的表示与实现抽象数据类型的表示与实现1.4算法和算法分析算法和算法分析1.4.1算法算法1.4

5、.2算法设计的要求算法设计的要求1.4.3算法效率的度量算法效率的度量1.4.4算法的存储空间的需求算法的存储空间的需求11一、数据结构形成和发展背景一、数据结构形成和发展背景n n计算机是一门研究用计算机进行信息表示和计算机是一门研究用计算机进行信息表示和处理的科学处理的科学n n两个问题：两个问题：1）信息的表示和组织：直接关系到处理信息）信息的表示和组织：直接关系到处理信息的程序的效率；的程序的效率；2）信息的处理：面向系统程序和应用程序的）信息的处理：面向系统程序和应用程序的大规模和复杂结构大规模和复杂结构1.1什么是数据结构什么是数据结构12一、数据结构形成和发展背景一、数据结构形成

6、和发展背景n n计算机的飞速发展及其应用范围的迅速扩展计算机的飞速发展及其应用范围的迅速扩展n n计算机处理的对象由纯粹的数值发展到字符、计算机处理的对象由纯粹的数值发展到字符、表格和图像等各种具有一定结构的数据表格和图像等各种具有一定结构的数据n n编制编制“好好”的程序要求分析待处理的对象以的程序要求分析待处理的对象以及各处理对象之间存在的关系及各处理对象之间存在的关系1.1什么是数据结构什么是数据结构13二、数据结构二、数据结构1、用计算机解决问题的步骤：具体问题、用计算机解决问题的步骤：具体问题建立建立数学模型数学模型设计算法设计算法编制程序编制程序测试和调测试和调整整最终答案最终答案

7、建立数学模型（关键）：分析问题、提取操建立数学模型（关键）：分析问题、提取操作对象、找出对象间关系，对此用数学语言作对象、找出对象间关系，对此用数学语言加以描述加以描述算法设计：利用建立的数学模型，根据具体算法设计：利用建立的数学模型，根据具体问题，设计出解决问题的方法问题，设计出解决问题的方法1.1什么是数据结构什么是数据结构14二、数据结构二、数据结构NiklausWirth：Algorithms+DataStructures=Programs程序设计程序设计:为计算机处理问题编制一组指为计算机处理问题编制一组指令集令集算法：处理问题的策略算法：处理问题的策略数据结构：问题的数学模型数据结

8、构：问题的数学模型1.1什么是数据结构什么是数据结构15二、数据结构二、数据结构从从数学模型数学模型上分：上分：数值问题（数学方程），如：数值问题（数学方程），如：桥梁结构的应力分析模型桥梁结构的应力分析模型线性方程组线性方程组人口增长模型人口增长模型微分方程微分方程全球天气预报全球天气预报环流模式方程环流模式方程非数值问题（集合、线性表、树、图等）非数值问题（集合、线性表、树、图等）无法用数学方程加以描述无法用数学方程加以描述1.1什么是数据结构什么是数据结构16二、数据结构二、数据结构非数值计算的程序设计问题非数值计算的程序设计问题非数值计算的程序设计问题非数值计算的程序设计问题例例例例1

9、:1:求一组求一组求一组求一组( (n n个个个个) )整数中的最大值整数中的最大值整数中的最大值整数中的最大值算法算法算法算法: :基本操作是基本操作是基本操作是基本操作是“ “比较两个数的大小比较两个数的大小比较两个数的大小比较两个数的大小” ”例例例例2 2：计算机对弈：计算机对弈：计算机对弈：计算机对弈算法：对弈的规则和策略算法：对弈的规则和策略算法：对弈的规则和策略算法：对弈的规则和策略例例例例3 3：协会会员注册系统：协会会员注册系统：协会会员注册系统：协会会员注册系统 算法：需要管理的项目？如何管理？用户界面？算法：需要管理的项目？如何管理？用户界面？算法：需要管理的项目？如何管

10、理？用户界面？算法：需要管理的项目？如何管理？用户界面？n n 模型：？模型：？模型：？模型：？1.1什么是数据结构什么是数据结构17二、数据结构二、数据结构2、数据结构主要关心的：、数据结构主要关心的：结构中各元素之间逻辑关系（结构中各元素之间逻辑关系（数学模型数学模型）线性结构：如图书馆的书目索引线性结构：如图书馆的书目索引树形结构：树形结构：见后面例子见后面例子图形结构：图形结构：见后面例子见后面例子结构中各元素的存储方式结构中各元素的存储方式结构具有的行为特征（结构具有的行为特征（其上的操作其上的操作）在计算机中的表示和实现在计算机中的表示和实现1.1什么是数据结构什么是数据结构18例

11、例例例1.1.电话号码查询系统电话号码查询系统电话号码查询系统电话号码查询系统设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了设有一个电话号码薄，它记录了N N个人的名字和其相个人的名字和其相个人的名字和其相个人的名字和其相应的电话号码，假定按如下形式安排：应的电话号码，假定按如下形式安排：应的电话号码，假定按如下形式安排：应的电话号码，假定按如下形式安排： ( (a a1 1,b,b1 1)(a)(a2 2,b,b2 2)(a)(an n, ,b bn n) )其中，其中，其中，其中，a ai i,b,bi i(i=1,2,n)(i=1,2,n)分别表示某

12、人的名字和对应分别表示某人的名字和对应分别表示某人的名字和对应分别表示某人的名字和对应的电话号码的电话号码的电话号码的电话号码要求：设计算法，给定某人的名字，打印出此人的电要求：设计算法，给定某人的名字，打印出此人的电要求：设计算法，给定某人的名字，打印出此人的电要求：设计算法，给定某人的名字，打印出此人的电话号码；如果无此人，则报告无此人的标志话号码；如果无此人，则报告无此人的标志话号码；如果无此人，则报告无此人的标志话号码；如果无此人，则报告无此人的标志1.1什么是数据结构什么是数据结构19uu算法的设计，依赖于计算机如何存储人的名字和对应算法的设计，依赖于计算机如何存储人的名字和对应算法

13、的设计，依赖于计算机如何存储人的名字和对应算法的设计，依赖于计算机如何存储人的名字和对应 的电话号码，或者说依赖于名字和其电话号码的结构的电话号码，或者说依赖于名字和其电话号码的结构的电话号码，或者说依赖于名字和其电话号码的结构的电话号码，或者说依赖于名字和其电话号码的结构uu数据的结构，直接影响算法的选择和效率数据的结构，直接影响算法的选择和效率数据的结构，直接影响算法的选择和效率数据的结构，直接影响算法的选择和效率uu上述问题是一种数据结构问题。可将名字和对应的上述问题是一种数据结构问题。可将名字和对应的上述问题是一种数据结构问题。可将名字和对应的上述问题是一种数据结构问题。可将名字和对应

14、的 电话号码设计成：二维数组、表结构、向量电话号码设计成：二维数组、表结构、向量电话号码设计成：二维数组、表结构、向量电话号码设计成：二维数组、表结构、向量 1)1)假定名字和其电话号码逻辑上已安排成假定名字和其电话号码逻辑上已安排成假定名字和其电话号码逻辑上已安排成假定名字和其电话号码逻辑上已安排成N N元向量元向量元向量元向量 的形式，它的每个元素是一个数对的形式，它的每个元素是一个数对的形式，它的每个元素是一个数对的形式，它的每个元素是一个数对( (a ai i,b,bi i) )，1in1in 2)2)数据结构还要提供每种结构类型所定义的各种运数据结构还要提供每种结构类型所定义的各种运

15、数据结构还要提供每种结构类型所定义的各种运数据结构还要提供每种结构类型所定义的各种运 算的算法算的算法算的算法算的算法1.1什么是数据结构什么是数据结构20例例例例2.2.图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题图书馆的书目检索系统自动化问题（线性结构线性结构线性结构线性结构）l l图书馆的一本图书由图书馆的一本图书由图书馆的一本图书由图书馆的一本图书由书名书名书名书名、作者作者作者作者、出版社出版社出版社出版社等数据来等数据来等数据来等数据来描述，根据需要我们选择其中的若干项组成一个描述，根据需要我们选择其中的若干项组成一个描述，根据需要我们

16、选择其中的若干项组成一个描述，根据需要我们选择其中的若干项组成一个数数数数据元素据元素据元素据元素来对应一本书来对应一本书来对应一本书来对应一本书l l图书馆的编目表反映了书与书之间的关系，是图书馆的编目表反映了书与书之间的关系，是图书馆的编目表反映了书与书之间的关系，是图书馆的编目表反映了书与书之间的关系，是数据数据数据数据元素之间的结构元素之间的结构元素之间的结构元素之间的结构。当然我们还应注意到书是具体地。当然我们还应注意到书是具体地。当然我们还应注意到书是具体地。当然我们还应注意到书是具体地放在某个书架上的，它是编目表的放在某个书架上的，它是编目表的放在某个书架上的，它是编目表的放在某

17、个书架上的，它是编目表的物理实现物理实现物理实现物理实现l l图书馆从两方面管理图书：物理的藏书和逻辑的编图书馆从两方面管理图书：物理的藏书和逻辑的编图书馆从两方面管理图书：物理的藏书和逻辑的编图书馆从两方面管理图书：物理的藏书和逻辑的编目表。这就是图书馆的结构。和图书馆一样计算机目表。这就是图书馆的结构。和图书馆一样计算机目表。这就是图书馆的结构。和图书馆一样计算机目表。这就是图书馆的结构。和图书馆一样计算机管理数据，也有两个方面：即物理的存储和逻辑的管理数据，也有两个方面：即物理的存储和逻辑的管理数据，也有两个方面：即物理的存储和逻辑的管理数据，也有两个方面：即物理的存储和逻辑的关系关系关

18、系关系1.1什么是数据结构什么是数据结构211.1什么是数据结构什么是数据结构22例例例例3 3：学生选课系统模型：学生选课系统模型：学生选课系统模型：学生选课系统模型（图结构）图结构）图结构）图结构）1.1什么是数据结构什么是数据结构23例例例例3 3：学生选课系统模型：学生选课系统模型：学生选课系统模型：学生选课系统模型（图结构）图结构）图结构）图结构） 课程编号课程编号课程编号课程编号课课课课 程程程程 名名名名 学时学时学时学时 024002024002 程序设计基础程序设计基础程序设计基础程序设计基础 6464 024010024010 汇编语言汇编语言汇编语言汇编语言 4848 0

19、24016024016 计算机原理计算机原理计算机原理计算机原理 6464 024020024020 数据结构数据结构数据结构数据结构 6464 024021024021 微机技术微机技术微机技术微机技术 6464 024024024024 操作系统操作系统操作系统操作系统 4848 024026024026 数据库原理数据库原理数据库原理数据库原理 48481.1什么是数据结构什么是数据结构24例例例例3 3：学生选课系统模型：学生选课系统模型：学生选课系统模型：学生选课系统模型（图结构）（图结构）（图结构）（图结构）选课单包含如下信息选课单包含如下信息学学号号课程编号课程编号成成绩绩时时间

20、间 学生选课系统中实体构成的网状关系学生选课系统中实体构成的网状关系1.1什么是数据结构什么是数据结构25例例例例4 4：下棋问题：下棋问题：下棋问题：下棋问题1.1什么是数据结构什么是数据结构26例例例例5.5.多叉路口交通灯的管理（多叉路口交通灯的管理（多叉路口交通灯的管理（多叉路口交通灯的管理（图结构图结构图结构图结构）11112223344111.1什么是数据结构什么是数据结构27问题模型问题模型结构分析结构分析结构分析结构分析线性方程组线性方程组线性方程组线性方程组人口预报人口预报人口预报人口预报微分方程微分方程微分方程微分方程优化问题优化问题优化问题优化问题线性规划、非线性规划线性

21、规划、非线性规划线性规划、非线性规划线性规划、非线性规划震动问题震动问题震动问题震动问题矩阵分析；特征值、特征向量矩阵分析；特征值、特征向量矩阵分析；特征值、特征向量矩阵分析；特征值、特征向量信息管理信息管理信息管理信息管理二维数据表二维数据表二维数据表二维数据表下棋下棋下棋下棋树型结构树型结构树型结构树型结构城市路径城市路径城市路径城市路径图型结构图型结构图型结构图型结构DOSDOS目录目录目录目录树型结构树型结构树型结构树型结构家谱家谱家谱家谱树型结构树型结构树型结构树型结构排队排队排队排队队列（线性）队列（线性）队列（线性）队列（线性）1.1什么是数据结构什么是数据结构28数据的逻辑结构

22、按关系分为线性结构（关系是数据的逻辑结构按关系分为线性结构（关系是线性的）和非线性结构（关系是非线性的）线性的）和非线性结构（关系是非线性的）1.1什么是数据结构什么是数据结构29数据结构是一门研究非数值计算的程序设计数据结构是一门研究非数值计算的程序设计问题中问题中计算机的操作对象计算机的操作对象以及它们之间以及它们之间相互相互关系关系和操作等的学科和操作等的学科对这种结构定义相应的运算，而且确保经过对这种结构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结这些运算后所得到的新结构仍然是原来的结构类型构类型1.1什么是数据结构什么是数据结构301.2基本概念和术语基本概念和

23、术语n n数据：数据：数据：数据：数据是信息的载体，是描述客观事物的数、数据是信息的载体，是描述客观事物的数、数据是信息的载体，是描述客观事物的数、数据是信息的载体，是描述客观事物的数、字符以及所有能输入到计算机中，被计算机程序字符以及所有能输入到计算机中，被计算机程序字符以及所有能输入到计算机中，被计算机程序字符以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合识别和处理的符号的集合识别和处理的符号的集合识别和处理的符号的集合uu 数值性数据数值性数据数值性数据数值性数据 / /非数值性数据非数值性数据非数值性数据非数值性数据数数数数据据据据元元元元素素素素：数数数数据据据据基基基

24、基本本本本单单单单位位位位，通通通通常常常常作作作作为为为为一一一一个个个个整整整整体体体体来来来来考虑，如：考虑，如：考虑，如：考虑，如：“ “树树树树” ”中的一个棋盘格局；中的一个棋盘格局；中的一个棋盘格局；中的一个棋盘格局； 学学学学生生生生信信信信息息息息表表表表，一一一一个个个个数数数数据据据据元元元元素素素素（记记记记录录录录）含含含含若若若若干干干干个个个个数数数数据项等据项等据项等据项等数据项数据项数据项数据项是数据的不可分割的最小单位是数据的不可分割的最小单位是数据的不可分割的最小单位是数据的不可分割的最小单位311.2基本概念和术语基本概念和术语n n数据对象：数据对象：

25、数据对象：数据对象：数据的子集。具有相同性质的数据成数据的子集。具有相同性质的数据成数据的子集。具有相同性质的数据成数据的子集。具有相同性质的数据成员（数据元素）的集合。数据对象可以是有限的，员（数据元素）的集合。数据对象可以是有限的，员（数据元素）的集合。数据对象可以是有限的，员（数据元素）的集合。数据对象可以是有限的，也可以是无限的也可以是无限的也可以是无限的也可以是无限的uu 整数数据对象整数数据对象整数数据对象整数数据对象 : :N N =0,=0, 1,1, 2,2,uu英文字符类型的数据对象英文字符类型的数据对象英文字符类型的数据对象英文字符类型的数据对象:A A，B B，C C，

26、D D，E E，F F，uu 学生数据对象：数据表学生数据对象：数据表学生数据对象：数据表学生数据对象：数据表n n数据、数据元素和数据对象数据、数据元素和数据对象数据、数据元素和数据对象数据、数据元素和数据对象之间的关系：之间的关系：之间的关系：之间的关系：数据数据数据数据 数据元素数据元素数据元素数据元素 数据项数据项数据项数据项32集合集合集合集合元素间为松散的元素间为松散的元素间为松散的元素间为松散的关系关系关系关系线性结构线性结构线性结构线性结构元素间为严格的元素间为严格的元素间为严格的元素间为严格的一对一关系一对一关系一对一关系一对一关系树形结构树形结构树形结构树形结构元素间为严格

27、的元素间为严格的元素间为严格的元素间为严格的一对多关系一对多关系一对多关系一对多关系图状结构图状结构图状结构图状结构（或网状（或网状（或网状（或网状结构）结构）结构）结构）元素间为多对多元素间为多对多元素间为多对多元素间为多对多关系关系关系关系示例示例示例示例特征特征特征特征1.2基本概念和术语基本概念和术语331.2基本概念和术语基本概念和术语数据结构与数据对象之间的区别和联系？数据结构与数据对象之间的区别和联系？数据结构与数据对象之间的区别和联系？数据结构与数据对象之间的区别和联系？数据对象仅仅是数据元素的集合，不涉及这些元数据对象仅仅是数据元素的集合，不涉及这些元数据对象仅仅是数据元素的

28、集合，不涉及这些元数据对象仅仅是数据元素的集合，不涉及这些元素之间的关系素之间的关系素之间的关系素之间的关系描述数据结构不仅要描述数据对象，而且要描述描述数据结构不仅要描述数据对象，而且要描述描述数据结构不仅要描述数据对象，而且要描述描述数据结构不仅要描述数据对象，而且要描述元素彼此之间的关系元素彼此之间的关系元素彼此之间的关系元素彼此之间的关系341.2基本概念和术语基本概念和术语数据结构描述数据结构描述数据结构描述数据结构描述Data-Structure=(D,S)Data-Structure=(D,S)DD数据集；数据集；数据集；数据集；SS关系集关系集关系集关系集例：学科研究课题小组例

29、：学科研究课题小组例：学科研究课题小组例：学科研究课题小组Group=(P,R)Group=(P,R)其中：其中：其中：其中：P=T,GP=T,G1 1,G,G2 2,GGn n,S,S1111,S,S1212,S Snmnm R=R1,R2R=R1,R2R1=T,R1=|i=1,2,3|i=1,2,3R2=R2=|i=1,2,3,j=1,2|i=1,2,3,j=1,2351.2基本概念和术语基本概念和术语数据结构描述数据结构描述数据结构描述数据结构描述 例：复数的数据结构定义如下：例：复数的数据结构定义如下：例：复数的数据结构定义如下：例：复数的数据结构定义如下：Complex=(CComp

30、lex=(C，R)R) 其中：其中：其中：其中：C C是含两个实数的集合是含两个实数的集合是含两个实数的集合是含两个实数的集合C1C1，C2C2，分别分别分别分别表示复数的实部和虚部。表示复数的实部和虚部。表示复数的实部和虚部。表示复数的实部和虚部。R=PR=P，P P是定义在集合是定义在集合是定义在集合是定义在集合上的一种关系上的一种关系上的一种关系上的一种关系 C1C1，C2C2 361.2基本概念和术语基本概念和术语数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构逻辑结构逻辑结构逻辑结构逻辑结构：数据结构描述的元素间的逻辑：数据结构描述的元素间的逻辑：数据结构描述的元素间的逻辑：

31、数据结构描述的元素间的逻辑“关系关系关系关系”，独立于计算机，独立于计算机，独立于计算机，独立于计算机按集合的观点，数据的逻辑结构有两个按集合的观点，数据的逻辑结构有两个按集合的观点，数据的逻辑结构有两个按集合的观点，数据的逻辑结构有两个要素要素要素要素：一：一：一：一是数据元素，二是关系是数据元素，二是关系是数据元素，二是关系是数据元素，二是关系数据元素间的数据元素间的数据元素间的数据元素间的关系关系关系关系表示表示表示表示 1 1 1 1）顺序映象顺序映象顺序映象顺序映象：借助元素在存储器中的相对位置：借助元素在存储器中的相对位置：借助元素在存储器中的相对位置：借助元素在存储器中的相对位置

32、来表示数据元素之间的逻辑关系来表示数据元素之间的逻辑关系来表示数据元素之间的逻辑关系来表示数据元素之间的逻辑关系2 2）非顺序映象）非顺序映象）非顺序映象）非顺序映象 ：借助指示元素存储地址的指针：借助指示元素存储地址的指针：借助指示元素存储地址的指针：借助指示元素存储地址的指针表示数据元素之间的逻辑关系表示数据元素之间的逻辑关系表示数据元素之间的逻辑关系表示数据元素之间的逻辑关系371.2基本概念和术语基本概念和术语数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构顺顺顺顺序序序序映映映映象象象象：x x和和和和y y存存存存储储储储位位位位置置置置的的的的相相相相对对对对关关关关系系

33、系系表表表表示示示示有有有有序序序序对对对对 x,y最最最最简简简简单单单单的的的的方方方方法法法法就就就就是是是是使使使使y y和和和和x x的的的的存存存存储储储储位位位位置置置置之之之之间间间间差差差差一一一一个个个个常量常量常量常量C,C,例如：例如：例如：例如：( (a1,a2,a3)a1,a2,a3)381.2基本概念和术语基本概念和术语数据的逻辑结构数据的逻辑结构数据的逻辑结构数据的逻辑结构链链链链式式式式映映映映象象象象：x x和和和和y y的的的的存存存存储储储储位位位位置置置置随随随随意意意意，则则则则需需需需要要要要用用用用一一一一个个个个和和和和x x在在在在一一一一起

34、起起起的的的的附附附附加加加加信信信信息息息息指指指指示示示示y y的的的的存存存存储储储储位位位位置置置置，这这这这个个个个附附附附加加加加信信信信息息息息和和和和x x绑绑绑绑定定定定在在在在一一一一起起起起，此此此此时时时时，两两两两者者者者合合合合在在在在一一一一起起起起作作作作为为为为x x的存储映象的存储映象的存储映象的存储映象 391.2基本概念和术语基本概念和术语数据的物理（存储）结构数据的物理（存储）结构数据的物理（存储）结构数据的物理（存储）结构物理结构物理结构物理结构物理结构：数据结构中数据元素间的关系在存储器：数据结构中数据元素间的关系在存储器：数据结构中数据元素间的关

35、系在存储器：数据结构中数据元素间的关系在存储器中的存储方法（表现和实现）中的存储方法（表现和实现）中的存储方法（表现和实现）中的存储方法（表现和实现）物理结构中的物理结构中的物理结构中的物理结构中的基本定义基本定义基本定义基本定义：1 1）位）位）位）位：二进制中的一位；信息表示的最小单位：二进制中的一位；信息表示的最小单位：二进制中的一位；信息表示的最小单位：二进制中的一位；信息表示的最小单位2 2）元素（结点）元素（结点）元素（结点）元素（结点）：由若干位组合起来形成的一个：由若干位组合起来形成的一个：由若干位组合起来形成的一个：由若干位组合起来形成的一个位串，可看成是数据元素在计算机中的

36、映象位串，可看成是数据元素在计算机中的映象位串，可看成是数据元素在计算机中的映象位串，可看成是数据元素在计算机中的映象3 3）数据域）数据域）数据域）数据域：当数据元素由若干数据项组成时，位：当数据元素由若干数据项组成时，位：当数据元素由若干数据项组成时，位：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串串中对应于各个数据项的子位串串中对应于各个数据项的子位串串中对应于各个数据项的子位串401.2基本概念和术语基本概念和术语按照物理结构的不同分为：按照物理结构的不同分为：按照物理结构的不同分为：按照物理结构的不同分为：1 1）顺序存储结构）顺序存储结构）顺序存储结构）顺序存储结构

37、：利用在存储器中的物理关系来表示：利用在存储器中的物理关系来表示：利用在存储器中的物理关系来表示：利用在存储器中的物理关系来表示逻辑关系。逻辑上相邻的数据元素存储在物理位置逻辑关系。逻辑上相邻的数据元素存储在物理位置逻辑关系。逻辑上相邻的数据元素存储在物理位置逻辑关系。逻辑上相邻的数据元素存储在物理位置上相毗邻的存储单元里，元素的关系由存储单元的上相毗邻的存储单元里，元素的关系由存储单元的上相毗邻的存储单元里，元素的关系由存储单元的上相毗邻的存储单元里，元素的关系由存储单元的邻接关系来体现邻接关系来体现邻接关系来体现邻接关系来体现2 2）链链链链式式式式存存存存储储储储结结结结构构构构：数数数

38、数据据据据元元元元素素素素可可可可以以以以在在在在计计计计算算算算机机机机内内内内任任任任意意意意位位位位置置置置上上上上存存存存放放放放（它它它它不不不不要要要要求求求求逻逻逻逻辑辑辑辑上上上上相相相相邻邻邻邻的的的的元元元元素素素素在在在在物物物物理理理理位位位位置置置置上上上上也也也也相相相相邻邻邻邻) )，用用用用在在在在存存存存储储储储器器器器中中中中附附附附加加加加指指指指针针针针的的的的方方方方式式式式来来来来表表表表示示示示逻逻逻逻辑辑辑辑关关关关系系系系。将将将将数数数数据据据据元元元元素素素素存存存存放放放放的的的的存存存存储储储储单单单单元元元元分分分分为为为为两两两两个

39、个个个部部部部分分分分，分别存放数据和指针，称为数据域和指针域分别存放数据和指针，称为数据域和指针域分别存放数据和指针，称为数据域和指针域分别存放数据和指针，称为数据域和指针域411.2基本概念和术语基本概念和术语数据的逻辑结构和数据的逻辑结构和数据的逻辑结构和数据的逻辑结构和物理结构的关系：物理结构的关系：物理结构的关系：物理结构的关系：逻辑结构逻辑结构逻辑结构逻辑结构只抽象地描述数据元素逻辑关系（简称只抽象地描述数据元素逻辑关系（简称只抽象地描述数据元素逻辑关系（简称只抽象地描述数据元素逻辑关系（简称数据结构）数据结构）数据结构）数据结构）物理结构物理结构物理结构物理结构是一个逻辑结构映像

40、到计算机中所得到是一个逻辑结构映像到计算机中所得到是一个逻辑结构映像到计算机中所得到是一个逻辑结构映像到计算机中所得到的存储表示的存储表示的存储表示的存储表示算法的设计算法的设计算法的设计算法的设计：取决于选定的：取决于选定的：取决于选定的：取决于选定的数据逻辑结构数据逻辑结构数据逻辑结构数据逻辑结构算法的实现算法的实现算法的实现算法的实现：依赖于采用的：依赖于采用的：依赖于采用的：依赖于采用的存储结构存储结构存储结构存储结构421.2基本概念和术语基本概念和术语数据类型数据类型数据类型数据类型 用以刻画（程序）操作对象的特性。用以刻画（程序）操作对象的特性。用以刻画（程序）操作对象的特性。用

41、以刻画（程序）操作对象的特性。一个值的集合（一个值的集合（一个值的集合（一个值的集合（整型变量整型变量整型变量整型变量）+ +该集合上定义的一该集合上定义的一该集合上定义的一该集合上定义的一组操作组操作组操作组操作( (不体现值间关系不体现值间关系不体现值间关系不体现值间关系) )（加、减等操作加、减等操作加、减等操作加、减等操作）类型明显或隐含地规定了：在程序执行期间变量或类型明显或隐含地规定了：在程序执行期间变量或类型明显或隐含地规定了：在程序执行期间变量或类型明显或隐含地规定了：在程序执行期间变量或表达式所有可能的取值范围以及在这些值上允许表达式所有可能的取值范围以及在这些值上允许表达式

42、所有可能的取值范围以及在这些值上允许表达式所有可能的取值范围以及在这些值上允许进行的操作进行的操作进行的操作进行的操作 431.2基本概念和术语基本概念和术语数据类型数据类型数据类型数据类型例例例例1.1.在在在在C C语言中语言中语言中语言中数据类型：基本类型和构造类型数据类型：基本类型和构造类型数据类型：基本类型和构造类型数据类型：基本类型和构造类型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型基本类型：整型、浮点型、字符型构造类型：数组、结构、联合、指针、枚举型、构造类型：数组、结构、联合、指针、枚举型、构造类型：数组、结构、联合、指针、枚举型

43、、构造类型：数组、结构、联合、指针、枚举型、自定义自定义自定义自定义例例例例2.2.在在在在FORTRANFORTRAN语言中语言中语言中语言中变量的数据类型有整型、实型、和复数型变量的数据类型有整型、实型、和复数型变量的数据类型有整型、实型、和复数型变量的数据类型有整型、实型、和复数型441.2基本概念和术语基本概念和术语数据类型数据类型数据类型数据类型按按按按“ “值值值值” ”的不同特性可分为：的不同特性可分为：的不同特性可分为：的不同特性可分为：1 1）非结构的原子类型：其值是不可分解的；）非结构的原子类型：其值是不可分解的；）非结构的原子类型：其值是不可分解的；）非结构的原子类型：其

44、值是不可分解的；2 2）结构类型：其值是由若干成分按某种结构组成）结构类型：其值是由若干成分按某种结构组成）结构类型：其值是由若干成分按某种结构组成）结构类型：其值是由若干成分按某种结构组成的，是可分解的；且它的成分可以是非结构的，的，是可分解的；且它的成分可以是非结构的，的，是可分解的；且它的成分可以是非结构的，的，是可分解的；且它的成分可以是非结构的，也可以是结构的。也可以是结构的。也可以是结构的。也可以是结构的。 451.2基本概念和术语基本概念和术语抽象数据类型：抽象数据类型：抽象数据类型：抽象数据类型： 数据结构数据结构数据结构数据结构+ +定义在此结构上的一组操作（和其在计定义在此

45、结构上的一组操作（和其在计定义在此结构上的一组操作（和其在计定义在此结构上的一组操作（和其在计算机上的表示和实现无关）。算机上的表示和实现无关）。算机上的表示和实现无关）。算机上的表示和实现无关）。 不再局限于前述各处理器中已定义并实现的数据不再局限于前述各处理器中已定义并实现的数据不再局限于前述各处理器中已定义并实现的数据不再局限于前述各处理器中已定义并实现的数据类型，还包括用户自定义的数据类型类型，还包括用户自定义的数据类型类型，还包括用户自定义的数据类型类型，还包括用户自定义的数据类型 按按按按“ “值值值值” ”的不同特性可分为：的不同特性可分为：的不同特性可分为：的不同特性可分为：1

46、 1）原子类型：其值是不可分解的；）原子类型：其值是不可分解的；）原子类型：其值是不可分解的；）原子类型：其值是不可分解的；2 2）固定聚合类型：其值由给定数目的成分按某种结）固定聚合类型：其值由给定数目的成分按某种结）固定聚合类型：其值由给定数目的成分按某种结）固定聚合类型：其值由给定数目的成分按某种结构组成；构组成；构组成；构组成；3 3）可变聚合类型：其值的成分的数目不确定。）可变聚合类型：其值的成分的数目不确定。）可变聚合类型：其值的成分的数目不确定。）可变聚合类型：其值的成分的数目不确定。461.2基本概念和术语基本概念和术语抽象数据类型抽象数据类型抽象数据类型抽象数据类型1 1）一

47、个含抽象数据类型的软件模块包含：定义、）一个含抽象数据类型的软件模块包含：定义、）一个含抽象数据类型的软件模块包含：定义、）一个含抽象数据类型的软件模块包含：定义、表示和实现表示和实现表示和实现表示和实现2 2）三元组表示（）三元组表示（）三元组表示（）三元组表示（D,S,PD,S,P）DD：数据对象，数据对象，数据对象，数据对象，S S：D D上的关系集，上的关系集，上的关系集，上的关系集，P P：D D上的基上的基上的基上的基本操作集本操作集本操作集本操作集 471.2基本概念和术语基本概念和术语抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：ADTADT抽象数据类

48、型名抽象数据类型名抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象：数据对象： 数据关系：数据关系：数据关系：数据关系： 基本操作：基本操作：基本操作：基本操作： ADTADT抽象数据类型名抽象数据类型名抽象数据类型名抽象数据类型名其中：其中：其中：其中：1 1）数据对象和数据关系的定义用伪码表示；）数据对象和数据关系的定义用伪码表示；）数据对象和数据关系的定义用伪码表示；）数据对象和数据关系的定义用伪码表示；481.2基本概念和术语基本概念和术语抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：2 2）基本操作的定义：）基本操作的定义：）基本操作的定义：）基本

49、操作的定义：基本操作名（参数表）基本操作名（参数表）基本操作名（参数表）基本操作名（参数表）初始条件：（初始条件描述）初始条件：（初始条件描述）初始条件：（初始条件描述）初始条件：（初始条件描述）操作结果：（操作结果描述）操作结果：（操作结果描述）操作结果：（操作结果描述）操作结果：（操作结果描述）基本操作有两种参数：基本操作有两种参数：基本操作有两种参数：基本操作有两种参数： 赋值参数：为操作提供输入值赋值参数：为操作提供输入值赋值参数：为操作提供输入值赋值参数：为操作提供输入值 引用参数：以引用参数：以引用参数：以引用参数：以&打头，除提供输入值外，还打头，除提供输入值外，还打头，除提供输

50、入值外，还打头，除提供输入值外，还将返回操作结果将返回操作结果将返回操作结果将返回操作结果491.2基本概念和术语基本概念和术语抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：抽象数据类型定义：2 2）基本操作的定义：）基本操作的定义：）基本操作的定义：）基本操作的定义： 初始条件：描述了操作执行之前数据结构和参初始条件：描述了操作执行之前数据结构和参初始条件：描述了操作执行之前数据结构和参初始条件：描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返数应满足的条件，若不满足，则操作失败，并返数应满足的条件，若不满足，则操作失败，并返数应满足的条件，若不满足，则操作失

51、败，并返回相应出错信息回相应出错信息回相应出错信息回相应出错信息 操作结果：说明了操作正常完成之后，数据结操作结果：说明了操作正常完成之后，数据结操作结果：说明了操作正常完成之后，数据结操作结果：说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，构的变化状况和应返回的结果。若初始条件为空，构的变化状况和应返回的结果。若初始条件为空，构的变化状况和应返回的结果。若初始条件为空，则省略之则省略之则省略之则省略之501.2基本概念和术语基本概念和术语抽象数据类型的两个特征抽象数据类型的两个特征抽象数据类型的两个特征抽象数据类型的两个特征: :数据抽象数据抽象数据抽象数据抽象

52、对对对对程程程程序序序序处处处处理理理理的的的的实实实实体体体体的的的的描描描描述述述述强强强强调调调调的的的的是是是是其其其其本本本本质质质质的的的的特特特特征征征征、其其其其所所所所能能能能完完完完成成成成的的的的功功功功能能能能以以以以及及及及它它它它和和和和外外外外部部部部用用用用户户户户的的的的接接接接口口口口( (即即即即外界使用它的方法外界使用它的方法外界使用它的方法外界使用它的方法) )数据封装数据封装数据封装数据封装将实体的外部特性和其内部实现细节分离，并且将实体的外部特性和其内部实现细节分离，并且将实体的外部特性和其内部实现细节分离，并且将实体的外部特性和其内部实现细节分离

53、，并且对外部养护隐藏其内部实现细节对外部养护隐藏其内部实现细节对外部养护隐藏其内部实现细节对外部养护隐藏其内部实现细节511.2基本概念和术语基本概念和术语抽象数据类型三元组的定义抽象数据类型三元组的定义抽象数据类型三元组的定义抽象数据类型三元组的定义: :（P9P9，例例例例1-61-6）ADTTripletADTTriplet数据对象：数据对象：数据对象：数据对象：D=e1,e2,e3|e1,e2,e3D=e1,e2,e3|e1,e2,e3 ElemSetElemSet数据关系：数据关系：数据关系：数据关系：R1=,R1=,基本操作：基本操作：基本操作：基本操作：InitTripletIn

54、itTriplet(&T)(&T)DestroyTripletDestroyTriplet(&T)(&T)Get(T,i,&e)Get(T,i,&e)Put(&T,i,e)Put(&T,i,e)ADTTripletADTTriplet521.3抽象数据类型的表示与实现抽象数据类型的表示与实现 可以通过固有数据类型表示和实现，即利用处理可以通过固有数据类型表示和实现，即利用处理可以通过固有数据类型表示和实现，即利用处理可以通过固有数据类型表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经器中已存在的数据类型来说明新的结构，用已经器中已存在的数据类型来说明新的结构，用已经器中已存在的

55、数据类型来说明新的结构，用已经实现的操作来组合新的操作实现的操作来组合新的操作实现的操作来组合新的操作实现的操作来组合新的操作 利用类利用类利用类利用类C C语言（语言（语言（语言（C C语言的一个核心子集）作为描语言的一个核心子集）作为描语言的一个核心子集）作为描语言的一个核心子集）作为描述工具述工具述工具述工具 类类类类C C语言描述语言描述语言描述语言描述：P10-13P10-13typedeftypedef数据类型定义数据类型定义数据类型定义数据类型定义ElemTypeElemType数据元素类型数据元素类型数据元素类型数据元素类型 StatusStatus函数结果状态的整数描述函数结

56、果状态的整数描述函数结果状态的整数描述函数结果状态的整数描述 与运算与运算与运算与运算&,&,或运算或运算或运算或运算| |53 类类类类C C语言描述语言描述语言描述语言描述：P10-13P10-13 内存的动态分配与释放内存的动态分配与释放内存的动态分配与释放内存的动态分配与释放指针变量指针变量指针变量指针变量=newnew数据类型数据类型数据类型数据类型deletedelete指针变量指针变量指针变量指针变量 基本操作的算法：函数描述基本操作的算法：函数描述基本操作的算法：函数描述基本操作的算法：函数描述 函数结果主要状态代码：函数结果主要状态代码：函数结果主要状态代码：函数结果主要状态

57、代码：TURE,OK=1TURE,OK=1FALSE,ERROR=0FALSE,ERROR=0OVERFLOW=-2OVERFLOW=-21.3抽象数据类型的表示与实现抽象数据类型的表示与实现54 类类类类C C语言描述语言描述语言描述语言描述：P10-13P10-13 几组特殊的赋值形式：交换赋值，数组赋值，条几组特殊的赋值形式：交换赋值，数组赋值，条几组特殊的赋值形式：交换赋值，数组赋值，条几组特殊的赋值形式：交换赋值，数组赋值，条件赋值件赋值件赋值件赋值 选择语句：条件语句，开关语句选择语句：条件语句，开关语句选择语句：条件语句，开关语句选择语句：条件语句，开关语句 循环语句：循环语句：

58、循环语句：循环语句：for,while,do-whilefor,while,do-while 输入和输出语句：输入和输出语句：输入和输出语句：输入和输出语句： 三种结束语句三种结束语句三种结束语句三种结束语句 return,break,exitreturn,break,exit 注释：注释：注释：注释： 基本函数：基本函数：基本函数：基本函数：max,min,abs,floor,ceil,max,min,abs,floor,ceil,eofeof, ,eolneoln1.3抽象数据类型的表示与实现抽象数据类型的表示与实现55 例例例例1-71-7抽象数据类型抽象数据类型抽象数据类型抽象数据类型

59、TripletTriplet的的的的表示和实现表示和实现表示和实现表示和实现（P11-13P11-13）基本操作的函数原型：基本操作的函数原型：基本操作的函数原型：基本操作的函数原型：StatusStatusInitTripletInitTriplet(Triplet&T,(Triplet&T,ElemTypeElemTypev1,v1,ElemTypeElemTypev2,v2,ElemTypeElemTypev3);v3);/操作结果：构造了三元组操作结果：构造了三元组操作结果：构造了三元组操作结果：构造了三元组T T，e1,e2e1,e2和和和和e3e3被赋以参数被赋以参数被赋以参数被赋

60、以参数v1,v2,v3v1,v2,v3的值的值的值的值StatusStatusDestroyTripletDestroyTriplet(Triplet&T)(Triplet&T)；/操作结果：三元组操作结果：三元组操作结果：三元组操作结果：三元组T T被销毁。被销毁。被销毁。被销毁。StatusGet(TripletT,StatusGet(TripletT,intinti,i,ElemTypeElemType&e);&e);/初始条件：三元组初始条件：三元组初始条件：三元组初始条件：三元组T T已存在，已存在，已存在，已存在，1 1 i i 3 3/操作结果：用操作结果：用操作结果：用操作结果

61、：用e e返回返回返回返回T T的第的第的第的第i i元的值元的值元的值元的值。1.3抽象数据类型的表示与实现抽象数据类型的表示与实现56 例例例例1-71-7抽象数据类型抽象数据类型抽象数据类型抽象数据类型TripletTriplet的的的的表示和实现表示和实现表示和实现表示和实现（P11-13P11-13）基本操作的实现：基本操作的实现：基本操作的实现：基本操作的实现：StatusStatusInitTripletInitTriplet(Triplet&T,(Triplet&T,ElemTypeElemTypev1,v1,ElemTypeElemTypev2,v2,ElemTypeElem

62、Typev3)v3)/构造三元组构造三元组构造三元组构造三元组T T，依此置依此置依此置依此置T T的三个的三个的三个的三个元素的初值为元素的初值为元素的初值为元素的初值为v1,v2,v3v1,v2,v3T=(T=(ElemTypeElemType*)malloc(3*)malloc(3*sizeofsizeof( (ElemTypeElemType););if(!T)exit(OVERFLOW);if(!T)exit(OVERFLOW);T0=v1;T1=v2;T2=v3;T0=v1;T1=v2;T2=v3;returnOK;returnOK;1.3抽象数据类型的表示与实现抽象数据类型的表示

63、与实现57 例例例例1-71-7抽象数据类型抽象数据类型抽象数据类型抽象数据类型TripletTriplet的的的的表示和实现表示和实现表示和实现表示和实现（P11-13P11-13）基本操作的实现：基本操作的实现：基本操作的实现：基本操作的实现：StatusStatusDestroyTripletDestroyTriplet(Triplet&T)(Triplet&T)/销毁三元组销毁三元组销毁三元组销毁三元组T Tfree(T);T=null;returnOK;free(T);T=null;returnOK;StatusGet(TripletT,StatusGet(TripletT,inti

64、nti,i,ElemTypeElemType&e)&e)/1/1 ii 3,3,用用用用e e返回返回返回返回T T的第的第的第的第i i元的值元的值元的值元的值。 if(i3)returnERROR;if(i3)returnERROR;e=Ti-1;returnOK;e=Ti-1;returnOK;1.3抽象数据类型的表示与实现抽象数据类型的表示与实现58例：复数抽象数据类型示例例：复数抽象数据类型示例例：复数抽象数据类型示例例：复数抽象数据类型示例ADTComplexADTComplex 数据对象：数据对象：数据对象：数据对象：D=c1,c2|c1,c2D=c1,c2|c1,c2 R(RR

65、(R为实数集）为实数集）为实数集）为实数集） 数据关系：数据关系：数据关系：数据关系：S=S=（c1c1为实部，为实部，为实部，为实部，c2c2为虚部）为虚部）为虚部）为虚部） 基本操作：基本操作：基本操作：基本操作：voidAssign(&A,c1,c2voidAssign(&A,c1,c2）voidAdd(&A,B)voidAdd(&A,B)voidMinus(&A,B)voidMinus(&A,B)voidMultiply(&A,B)voidMultiply(&A,B)voidDivide(&A,B)voidDivide(&A,B). .ADTComplexADTComplex1.3抽象

66、数据类型的表示与实现抽象数据类型的表示与实现591.4算法和算法分析算法和算法分析 算法算法算法算法：对特定问题求解步骤的一种描述，它是指：对特定问题求解步骤的一种描述，它是指：对特定问题求解步骤的一种描述，它是指：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个令的有限序列，其中每一条指令表示一个或多个令的有限序列，其中每一条指令表示一个或多个令的有限序列，其中每一条指令表示一个或多个操作操作操作操作 算法的算法的算法的算法的五个重要特性五个重要特性五个重要特性五个重要特性：1 1）有穷性）有穷性）有穷性）有穷性：一个算法必须总是在执行有穷步之：一个算法必须总是

67、在执行有穷步之：一个算法必须总是在执行有穷步之：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成后结束，且每一步都在有穷时间内完成后结束，且每一步都在有穷时间内完成后结束，且每一步都在有穷时间内完成2 2）确定性）确定性）确定性）确定性：算法中每一条指令必须有确切的含：算法中每一条指令必须有确切的含：算法中每一条指令必须有确切的含：算法中每一条指令必须有确切的含义，不存在二义性。且算法只有一个入口和一个义，不存在二义性。且算法只有一个入口和一个义，不存在二义性。且算法只有一个入口和一个义，不存在二义性。且算法只有一个入口和一个出口出口出口出口601.4算法和算法分析算法和算法分

68、析 算法的算法的算法的算法的五个重要特性五个重要特性五个重要特性五个重要特性： 3 3）可行性）可行性）可行性）可行性：一个算法是可行的。即算法描述的：一个算法是可行的。即算法描述的：一个算法是可行的。即算法描述的：一个算法是可行的。即算法描述的操作都是可以通过已经实现的基本运算执行有限操作都是可以通过已经实现的基本运算执行有限操作都是可以通过已经实现的基本运算执行有限操作都是可以通过已经实现的基本运算执行有限次来实现的次来实现的次来实现的次来实现的4 4）输入）输入）输入）输入：一个算法有零个或多个输入，这些输：一个算法有零个或多个输入，这些输：一个算法有零个或多个输入，这些输：一个算法有零

69、个或多个输入，这些输入取自于某个特定的对象集合入取自于某个特定的对象集合入取自于某个特定的对象集合入取自于某个特定的对象集合5 5）输出）输出）输出）输出：一个算法有一个或多个输出，这些输：一个算法有一个或多个输出，这些输：一个算法有一个或多个输出，这些输：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量出是同输入有着某些特定关系的量出是同输入有着某些特定关系的量出是同输入有着某些特定关系的量611.4算法和算法分析算法和算法分析 算法设计的要求算法设计的要求算法设计的要求算法设计的要求：1 1）正确性）正确性）正确性）正确性：算法应满足具体问题的需求：算法应满足具体问题的需求：

70、算法应满足具体问题的需求：算法应满足具体问题的需求a a）程序不含语法错误；程序不含语法错误；程序不含语法错误；程序不含语法错误；b b）程序对于一般输入数程序对于一般输入数程序对于一般输入数程序对于一般输入数据的正确性；据的正确性；据的正确性；据的正确性；c c）程序对于苛刻、刁难输入数据程序对于苛刻、刁难输入数据程序对于苛刻、刁难输入数据程序对于苛刻、刁难输入数据的正确性；的正确性；的正确性；的正确性；d d）程序对于一切合法输入数据的正程序对于一切合法输入数据的正程序对于一切合法输入数据的正程序对于一切合法输入数据的正确性确性确性确性2 2）可读性）可读性）可读性）可读性：算法应该好读。

71、以有利于人对程序：算法应该好读。以有利于人对程序：算法应该好读。以有利于人对程序：算法应该好读。以有利于人对程序的理解的理解的理解的理解3 3）健壮性）健壮性）健壮性）健壮性：算法应具有容错处理。当输入非法：算法应具有容错处理。当输入非法：算法应具有容错处理。当输入非法：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产年莫名数据时，算法应对其作出反应，而不是产年莫名数据时，算法应对其作出反应，而不是产年莫名数据时，算法应对其作出反应，而不是产年莫名其妙的输出结果其妙的输出结果其妙的输出结果其妙的输出结果621.4算法和算法分析算法和算法分析 算法设计的要求算法设计的要求算法设

72、计的要求算法设计的要求：4 4）效率与低存储量需求）效率与低存储量需求）效率与低存储量需求）效率与低存储量需求效率效率效率效率：算法执行时间：算法执行时间：算法执行时间：算法执行时间存储量需求存储量需求存储量需求存储量需求：算法执行过程中所需要的最大存：算法执行过程中所需要的最大存：算法执行过程中所需要的最大存：算法执行过程中所需要的最大存储空间储空间储空间储空间 一般，这两者与问题的规模有关一般，这两者与问题的规模有关一般，这两者与问题的规模有关一般，这两者与问题的规模有关631.4算法和算法分析算法和算法分析 算法效率的度量算法效率的度量算法效率的度量算法效率的度量 算法执行时间的度量方法

73、算法执行时间的度量方法算法执行时间的度量方法算法执行时间的度量方法：1 1）事后统计的方法：）事后统计的方法：）事后统计的方法：）事后统计的方法：收集此算法的执行时间和实际收集此算法的执行时间和实际收集此算法的执行时间和实际收集此算法的执行时间和实际占用空间的统计资料占用空间的统计资料占用空间的统计资料占用空间的统计资料缺陷：缺陷：缺陷：缺陷：a a）必须先运行依据算法编制的程序；必须先运行依据算法编制的程序；必须先运行依据算法编制的程序；必须先运行依据算法编制的程序；b b）依赖于计算机的硬件、软件等环境因素依赖于计算机的硬件、软件等环境因素依赖于计算机的硬件、软件等环境因素依赖于计算机的硬

74、件、软件等环境因素2 2）事前分析估算的方法）事前分析估算的方法）事前分析估算的方法）事前分析估算的方法：求出该算法的一个时间界：求出该算法的一个时间界：求出该算法的一个时间界：求出该算法的一个时间界限函数限函数限函数限函数 算法运行所消耗的时间取决于：算法运行所消耗的时间取决于：算法运行所消耗的时间取决于：算法运行所消耗的时间取决于：a a）依据的算法选依据的算法选依据的算法选依据的算法选用何种策略；用何种策略；用何种策略；用何种策略；b b）问题的规模；问题的规模；问题的规模；问题的规模；c c）书写程序的语言；书写程序的语言；书写程序的语言；书写程序的语言；d d）编译程序所产生的机器代

75、码的质量；编译程序所产生的机器代码的质量；编译程序所产生的机器代码的质量；编译程序所产生的机器代码的质量；e e）机器执机器执机器执机器执行指令的速度行指令的速度行指令的速度行指令的速度641.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量1 1）原操作）原操作）原操作）原操作：基本操作基本操作基本操作基本操作2 2）算法的时间度量）算法的时间度量）算法的时间度量）算法的时间度量：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数3 3）算法的渐近时间复杂度）算法的渐近时间复杂度）算法的渐近时间复杂度）算法的渐近时间

76、复杂度：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数是问题规模是问题规模是问题规模是问题规模n n的某个函数的某个函数的某个函数的某个函数f f( (n n) )T T( (n n)=O()=O(f f( (n n) )4 4）频度频度频度频度：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数：原操作重复执行的次数5 5）在在在在难难难难以以以以精精精精确确确确计计计计算算算算基基基基本本本本操操操操作作作作执执执执行行行行次次次次数数数数的的的的情情情情况况况况下下下下，只只只只需求出它关于需求出它关于需求出它关于需求出它关于n n的

77、的的的增长率或阶增长率或阶增长率或阶增长率或阶即可即可即可即可6 6）当当当当基基基基本本本本操操操操作作作作执执执执行行行行次次次次数数数数随随随随问问问问题题题题的的的的输输输输入入入入数数数数据据据据集集集集变变变变化化化化时时时时，计算计算计算计算平均时间复杂度或最坏情况下的上界平均时间复杂度或最坏情况下的上界平均时间复杂度或最坏情况下的上界平均时间复杂度或最坏情况下的上界651.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量 常用的计算规则常用的计算规则常用的计算规则常用的计算规则：1 1）加法准则）加法准则）加法准则）加法准则 T T( (

78、n n)=)=T T1 1( (n n)+)+T T2 2( (n n)=)=O O( (f f1 1( (n n)+)+O O( (f f2 2( (n n)=O O(max(max(f f1 1( (n n),),f f2 2( (n n)2 2）乘法准则乘法准则乘法准则乘法准则 T T( (n n)=)=T T1 1( (n n)T T2 2( (n n)=)=O O( (f f1 1( (n n)O O( (f f2 2( (n n) )=O O( (f f1 1( (n n)f f2 2( (n n) )常见的时间复杂度常见的时间复杂度常见的时间复杂度常见的时间复杂度： 1 1）O(

79、1)O(1)常量阶常量阶常量阶常量阶2 2）O(n)O(n)线性阶线性阶线性阶线性阶 3 3）O(nO(n2 2)平方阶平方阶平方阶平方阶4 4）O(nO(n3 3)立方阶立方阶立方阶立方阶 5 5）O(logn)O(logn)对数阶对数阶对数阶对数阶6 6）O(2O(2n n)指数阶指数阶指数阶指数阶661.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量六种常用计算算法时间的多项式的关系为：六种常用计算算法时间的多项式的关系为：六种常用计算算法时间的多项式的关系为：六种常用计算算法时间的多项式的关系为：O(1)O(O(1)O(lognlogn)O(n

80、)O()O(n)O(nlognnlogn)O(n)O(n2 2)O(n)O(n3 3) )指数时间的关系为：指数时间的关系为：指数时间的关系为：指数时间的关系为：O(2O(2n n)O(n!)O()O(n!)O(n nn n) ) 当当当当n n取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，若能将现有指数时在所需时间上非常悬殊。因此，若能将现有指数时在所需时间上非常悬殊。因此，若能将现有指数时在所需时间上非常悬殊。因此，若能将现有指数时间算法中的任何一个

81、算法化简为多项式时间算法，间算法中的任何一个算法化简为多项式时间算法，间算法中的任何一个算法化简为多项式时间算法，间算法中的任何一个算法化简为多项式时间算法，那就取得了一个那就取得了一个那就取得了一个那就取得了一个伟大的成就伟大的成就伟大的成就伟大的成就671.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量例例例例1.+1.+x;s=0;x;s=0;将将将将x x自增看成是基本操作，则语句频度为，即时间自增看成是基本操作，则语句频度为，即时间自增看成是基本操作，则语句频度为，即时间自增看成是基本操作，则语句频度为，即时间复杂度为复杂度为复杂度为复杂度为

82、(1)(1)如果将如果将如果将如果将s=0s=0也看成是基本操作，则语句频度为，其也看成是基本操作，则语句频度为，其也看成是基本操作，则语句频度为，其也看成是基本操作，则语句频度为，其时间复杂度仍为时间复杂度仍为时间复杂度仍为时间复杂度仍为(1)(1)，即，即，即，即常量阶常量阶常量阶常量阶例例例例2.2.for(i=1;i=n;+i)for(i=1;i=n;+i)+x;s+=x;+x;s+=x; 语句频度为：语句频度为：语句频度为：语句频度为：2 2n n其时间复杂度为：其时间复杂度为：其时间复杂度为：其时间复杂度为：O(n)O(n) 即时间复杂度为即时间复杂度为即时间复杂度为即时间复杂度为

83、线性阶线性阶线性阶线性阶681.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量计算累加和程序程序步数计算工作表格计算累加和程序程序步数计算工作表格691.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量例例例例3.3.for(i=1;i=n;+i)for(i=1;i=n;+i)for(j=1;j=n;+j)for(j=1;j=n;+j)+x;s+=x;+x;s+=x; 语句频度为：语句频度为：语句频度为：语句频度为：2 2n n2 2 其时间复杂度为：其时间复杂度为：其时间复杂度为：其时间复杂度为：O(nO(n2

84、 2) ) 即时间复杂度为即时间复杂度为即时间复杂度为即时间复杂度为平方阶平方阶平方阶平方阶。701.4算法和算法分析算法和算法分析 算法的时间度量算法的时间度量算法的时间度量算法的时间度量例例例例4.4.两个两个两个两个N*NN*N矩阵相乘的算法矩阵相乘的算法矩阵相乘的算法矩阵相乘的算法for(i=1;i=n;+i)for(i=1;i=n;+i)for(j=1;j=n;+j)for(j=1;j=n;+j) cij=0;cij=0;for(k=1;k=n;+k)for(k=1;k1&change;-i)for(i=n-1;i1&change;-i)change=FALSE;change=FAL

85、SE;for(j=0;ji;j+)for(j=0;jaj+1)if(ajaj+1)swap(&aj,&aj+1);swap(&aj,&aj+1); 最好情况：最好情况：0 0次次 最坏情况：最坏情况： 1+2+3+1+2+3+n-1n-1 =n(n-1)/2 =n(n-1)/2 平均时间复杂度为平均时间复杂度为: : O(nO(n2 2) )731.4算法和算法分析算法和算法分析 算法的存储空间需求算法的存储空间需求算法的存储空间需求算法的存储空间需求1 1）空间复杂度）空间复杂度）空间复杂度）空间复杂度：所需存储空间是问题规模所需存储空间是问题规模所需存储空间是问题规模所需存储空间是问题规模

86、n n的某个的某个的某个的某个函数函数函数函数f f( (n n) )S S( (n n)=O()=O(f f( (n n) )2 2）算法执行过程中所需的最大空间算法执行过程中所需的最大空间算法执行过程中所需的最大空间算法执行过程中所需的最大空间 估算方法估算方法估算方法估算方法：输入数据所占空间：输入数据所占空间：输入数据所占空间：输入数据所占空间+ + + +程序所占空间程序所占空间程序所占空间程序所占空间+ + + + 辅助变量所占空间辅助变量所占空间辅助变量所占空间辅助变量所占空间3 3) ) ) )在在在在难以精确计算所需存储空间的情况下，只需求难以精确计算所需存储空间的情况下，只

87、需求难以精确计算所需存储空间的情况下，只需求难以精确计算所需存储空间的情况下，只需求出它关于出它关于出它关于出它关于n n的的的的增长率或阶增长率或阶增长率或阶增长率或阶即可即可即可即可4 4）当当当当所所所所需需需需存存存存储储储储空空空空间间间间随随随随问问问问题题题题的的的的输输输输入入入入数数数数据据据据集集集集变变变变化化化化时时时时，计算计算计算计算平均空间复杂度或最坏情况下的上界平均空间复杂度或最坏情况下的上界平均空间复杂度或最坏情况下的上界平均空间复杂度或最坏情况下的上界74小小结结n n有关数据结构的基本概念和术语有关数据结构的基本概念和术语n n抽象数据类型抽象数据类型AD

88、T的表示与实现的表示与实现n n类类C语言的书写规范语言的书写规范n n算法五个要素的确切含义算法五个要素的确切含义n n估估算算时时间间复复杂杂度度的的方方法法，了了解解空空间间复复杂杂度的度量方法度的度量方法75作作业业1.1.解释下列术语解释下列术语解释下列术语解释下列术语 数数数数据据据据、数数数数据据据据元元元元素素素素、数数数数据据据据对对对对象象象象、数数数数据据据据类类类类型型型型、抽抽抽抽象象象象数数数数据据据据类类类类型型型型、原原原原子子子子数数数数据据据据类类类类型型型型、结结结结构构构构数数数数据据据据类类类类型型型型、逻逻逻逻辑辑辑辑结结结结构构构构、存存存存储储储

89、储结结结结构构构构、数数数数据据据据结结结结构构构构、顺顺顺顺序序序序存存存存储储储储结结结结构构构构、链链链链式式式式存存存存储储储储结结结结构、算法构、算法构、算法构、算法2.2. 设设设设有有有有数数数数据据据据逻逻逻逻辑辑辑辑结结结结构构构构为为为为Data-structure=(D,R),Data-structure=(D,R),其其其其中中中中D Ddd1 1,d,d2 2,d,d3 3,d,d4 4,d,d5 5,d,d6 6, R=r,R=r, r=dr=, d,d,d,d,d,试试试试画画画画出出出出其逻辑结构图。其逻辑结构图。其逻辑结构图。其逻辑结构图。76作作业业3.3.

90、 数数数数据据据据类类类类型型型型和和和和抽抽抽抽象象象象数数数数据据据据类类类类型型型型是是是是如如如如何何何何定定定定义义义义的的的的，二二二二者者者者有有有有何何何何相相相相同同同同和和和和不不不不同同同同之之之之处处处处？抽抽抽抽象象象象数数数数据据据据类类类类型型型型的的的的主主主主要要要要特特特特点点点点是是是是什什什什么？使用抽象数据类型的主要好处是什么？么？使用抽象数据类型的主要好处是什么？么？使用抽象数据类型的主要好处是什么？么？使用抽象数据类型的主要好处是什么？4.4.按照阶由低到高的顺序排列下列时间复杂度：按照阶由低到高的顺序排列下列时间复杂度：按照阶由低到高的顺序排列下

91、列时间复杂度：按照阶由低到高的顺序排列下列时间复杂度：5.5. 试试试试编编编编写写写写算算算算法法法法，对对对对连连连连续续续续输输输输入入入入的的的的n n个个个个整整整整数数数数，找找找找出出出出其其其其中中中中最大值和最小值（规定输入数在整数允许范围内）。最大值和最小值（规定输入数在整数允许范围内）。最大值和最小值（规定输入数在整数允许范围内）。最大值和最小值（规定输入数在整数允许范围内）。77作作业业6.6.具有具有具有具有100100个分量的向量，求其点乘个分量的向量，求其点乘个分量的向量，求其点乘个分量的向量，求其点乘7.7. 有有有有若若若若干干干干学学学学生生生生（设设设设有有有有3 3个个个个学学学学生生生生）的的的的成成成成绩绩绩绩（设设设设每每每每个个个个学学学学生生生生有有有有4 4门门门门课课课课程程程程），编编编编程程程程找找找找出出出出其其其其中中中中有有有有不不不不及及及及格格格格课课课课程程程程的的的的学学学学生，输出他们的全部课程的成绩。生，输出他们的全部课程的成绩。生，输出他们的全部课程的成绩。生，输出他们的全部课程的成绩。78