数据结构绪论-课件.ppt

数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社课程性质课程性质数据结构是计算机专业的专业基础课数据结构是计算机专业的专业基础课 公共基础课、专业基础课、专业方向课、专业选修课公共基础课、专业基础课、专业方向课、专业选修课在教学计划中的地位：核心、承上启下在教学计划中的地位：核心、承上启下 前导课：高等数学、离散数学、程序设计语言前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理后续课：数据库、操作系统、编译原理属于武术中的属于武术中的“练功练功”科目科目 “练武不练功，到头一场空练武不练功，到头一场空”考研：专业课必考考研：专业课必考数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社教学目标教学目标掌握基本的数据结构掌握基本的数据结构 工具箱工具箱复用、修改、重组复用、修改、重组培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 问题求解过程：问题问题求解过程：问题想法想法算法算法程序程序 程序设计研究的层次：算法程序设计研究的层次：算法方法学方法学语言语言工具工具培养算法分析能力培养算法分析能力 评价算法、改进算法评价算法、改进算法数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社学编程的境界学编程的境界学会写程序学会写程序 学会高效地写程序学会高效地写程序 学会写高效的程序学会写高效的程序 学会设计算法学会设计算法 学会设计有用的算法学会设计有用的算法 数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社学习要求学习要求循序渐进，切忌心浮气躁循序渐进，切忌心浮气躁 提高课外学习的时间和内容提高课外学习的时间和内容 理解科学而不是背诵科学理解科学而不是背诵科学读书读书 正确对待考试正确对待考试作习题作习题 华罗庚：华罗庚：“学数学不做习题等于入宝山而空返学数学不做习题等于入宝山而空返”作实验作实验 计算机学科是一门科学性与工程性并重的学科，计算机学科是一门科学性与工程性并重的学科，表现为理论和实践紧密结合的特征。表现为理论和实践紧密结合的特征。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社人：什么？明天要考高数？人：什么？明天要考高数？得道：什么？下节课要考高数？得道：什么？下节课要考高数？入仙：什么？刚才考的是高数？入仙：什么？刚才考的是高数？成佛：成佛：什么？昨天有考试？什么？昨天有考试？高级佛爷：高数？刚才考的不是英语？高级佛爷：高数？刚才考的不是英语？我寝室一哥们：高数是什么树？我寝室一哥们：高数是什么树？大学生大学生“混混”的最高境界的最高境界(考试版考试版)数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社主教材主教材王红梅王红梅,胡明胡明,王涛王涛.数据结构（数据结构（C+版）第版）第2版版.清华大学出版社清华大学出版社辅导及实验教材辅导及实验教材王红梅等王红梅等.数据结构（数据结构（C+版）学习辅导与实验指导（第版）学习辅导与实验指导（第2版）版）.清华大学出版社清华大学出版社参考教材参考教材1.严蔚敏严蔚敏.数据结构数据结构.清华大学出版社清华大学出版社.19972.张铭张铭.数据结构与算法数据结构与算法.高等教育出版社高等教育出版社.20083.曹宏庆译曹宏庆译.如何求解问题如何求解问题.中国水利水电出版社中国水利水电出版社.2003关于教材关于教材数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社成绩组成成绩组成平时成绩平时成绩 20：出勤作业报告：出勤作业报告实验成绩实验成绩 10：出勤程序报告：出勤程序报告期末考试成绩期末考试成绩 70数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社第第 1 章章 绪绪 论论数据结构在程序设计中的作用数据结构在程序设计中的作用 本书讨论的主要内容本书讨论的主要内容 数据结构的基本概念数据结构的基本概念算法及算法分析算法及算法分析本章的基本内容是：本章的基本内容是：数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1938年出生，年出生，25岁毕业于加州理工学岁毕业于加州理工学院数学系，博士毕业后留校任教，院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦福大岁时，加盟斯坦福大学计算机系，任教授。从学计算机系，任教授。从31岁起，开岁起，开始出版他的历史性经典巨著：始出版他的历史性经典巨著：The Art of Computer Programming，他计划共，他计划共写写7卷，然而出版三卷之后，已震惊卷，然而出版三卷之后，已震惊世界，使他获得计算机科学界的最高世界，使他获得计算机科学界的最高荣誉荣誉图灵奖，此时，他年仅图灵奖，此时，他年仅36岁。岁。数据结构的创始人数据结构的创始人数据结构的创始人数据结构的创始人克努思克努思克努思克努思数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.1 数据结构在程序设计中的作用数据结构在程序设计中的作用 程序设计的实质是什么程序设计的实质是什么?数据表示：数据表示：将数据存储在计算机（内存）中将数据存储在计算机（内存）中数据处理：数据处理：处理数据，设计方案（算法）处理数据，设计方案（算法）数据结构问题起源于程序设计数据结构问题起源于程序设计 数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.1 数据结构在程序设计中的作用数据结构在程序设计中的作用 利用计算机求解问题的一般过程利用计算机求解问题的一般过程?计算机不能分析问题并产生问题的解决方案，必须由人来分计算机不能分析问题并产生问题的解决方案，必须由人来分析问题，确定问题的解决方案，编写程序，然后让计算机执析问题，确定问题的解决方案，编写程序，然后让计算机执行程序最终获得问题的解。行程序最终获得问题的解。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.1 数据结构在程序设计中的作用数据结构在程序设计中的作用 例例1-1 手机电话号码查询问题手机电话号码查询问题将电话号码集合组织成线性结构和树结构，查找操作的效将电话号码集合组织成线性结构和树结构，查找操作的效率不同，当数据量较大时差别就更大。率不同，当数据量较大时差别就更大。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.2 本书讨论的主要内容本书讨论的主要内容p 计算机求解问题计算机求解问题:问题问题抽象出问题的模型抽象出问题的模型求模型的解求模型的解p 问题问题数值问题、非数值问题数值问题、非数值问题 数数 值值 问问 题题数学方程数学方程 非数值问题非数值问题数据结构数据结构数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-2 学籍管理问题学籍管理问题完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？1.2 本书讨论的主要内容本书讨论的主要内容数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-3 人人机对弈问题机对弈问题如何实现对弈如何实现对弈?各格局之间是什么关系？各格局之间是什么关系？1.2 本书讨论的主要内容本书讨论的主要内容数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-4 七巧板涂色问题七巧板涂色问题 如何表示区域之间的邻接关系？如何表示区域之间的邻接关系？1.2 本书讨论的主要内容本书讨论的主要内容数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社本书讨论本书讨论非数值问题非数值问题的数据组织和处理，主要内容如下：的数据组织和处理，主要内容如下：（1 1）数据的）数据的逻辑结构逻辑结构：线性表、树、图等数据结构，其核心：线性表、树、图等数据结构，其核心是如何组织待处理的数据以及数据之间的关系；是如何组织待处理的数据以及数据之间的关系；（2 2）数据的）数据的存储结构存储结构：如何将线性表、树、图等数据结构存：如何将线性表、树、图等数据结构存储到计算机的存储器中，其核心是如何有效地存储数据以及储到计算机的存储器中，其核心是如何有效地存储数据以及数据之间的逻辑关系；数据之间的逻辑关系；（3 3）算法算法：如何基于数据的某种存储结构实现插入、删除、：如何基于数据的某种存储结构实现插入、删除、查找等基本操作，其核心是如何有效地处理数据；查找等基本操作，其核心是如何有效地处理数据；（4 4）常用）常用数据处理技术数据处理技术：查找技术、排序技术、索引技术等。：查找技术、排序技术、索引技术等。1.2 本书讨论的主要内容本书讨论的主要内容数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.3 数据结构的基本概念数据结构的基本概念p 数据数据：所有能：所有能输入输入到计算机中并能被计算机程序到计算机中并能被计算机程序识别和处理识别和处理的符号集合。的符号集合。数值数据：整数、实数等数值数据：整数、实数等 非数值数据：图形、图象、声音、文字等非数值数据：图形、图象、声音、文字等 p 数据元素数据元素：数据的：数据的基本基本单位，在计算机程序中通常作为一个单位，在计算机程序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。p 数据项数据项：构成数据元素的不可分割的最小单位。：构成数据元素的不可分割的最小单位。数据结构的基本概念数据结构的基本概念学学 号号姓姓 名名性性 别别出生日期出生日期政治面貌政治面貌0001陆 宇男1986/09/02团员0002李 明男1985/12/25党员0003汤晓影女1986/03/26团员数据项数据项数据元素数据元素数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据、数据元素、数据项之间的关系数据、数据元素、数据项之间的关系包含关系：数据由数据元素组成，数据元素由数据项组成。包含关系：数据由数据元素组成，数据元素由数据项组成。数据元素数据元素是讨论数据结构时涉及的最小数据单位是讨论数据结构时涉及的最小数据单位，其中的，其中的数据项一般不予考虑。数据项一般不予考虑。1.3 数据结构的基本概念数据结构的基本概念数据数据 结构结构数据元素数据元素关系关系数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的的数据元素数据元素的集合。的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念关联方式或邻接关系关联方式或邻接关系关联方式或邻接关系关联方式或邻接关系数据的逻辑结构是从具体问题抽象出来的数据的逻辑结构是从具体问题抽象出来的数据模型数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据的逻辑结构在形式上可定义为一个二元组：数据的逻辑结构在形式上可定义为一个二元组：Data_Structure=(D,R)其中其中D是数据元素的有限集合，是数据元素的有限集合，R是是D上关系的集合。上关系的集合。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念Data_Structure=(D,R)其中其中D=A,B,C,D,E,F,GR=R1，R1=,数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构数据结构：相互之间存在一定：相互之间存在一定关系关系的数据元素的集合。的数据元素的集合。按照视点的不同，数据结构分为逻辑结构和存储结构。按照视点的不同，数据结构分为逻辑结构和存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构存储结构：又称为物理结构，是数据及其逻辑结构在在计算机计算机中的表示。中的表示。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念内存内存内存内存存储结构实质上是内存分配，在具体实现时依赖存储结构实质上是内存分配，在具体实现时依赖于计算机语言。于计算机语言。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社数据结构从逻辑上分为四类：数据结构从逻辑上分为四类：集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合”；线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系；图结构：数据元素之间存在图结构：数据元素之间存在 着多对多的任意关系。着多对多的任意关系。1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社通常有两种存储结构：通常有两种存储结构：1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。batcateat起始地址起始地址例：（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社通常有两种存储结构：通常有两种存储结构：1.顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元数据元素之间的逻辑关系由元素的素的存储位置存储位置来表示。来表示。2.链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据元素，数的存储单元存储数据元素，数据元素之间的逻辑关系用据元素之间的逻辑关系用指针指针来表示来表示。例：（例：（bat,cat,eat）1.3 数据结构的基本概念数据结构的基本概念数据结构的基本概念数据结构的基本概念0200020803000325 bat0200 cat0325 eat 数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，的，反映了数据内部的构成方式；数据的存储结构反映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是属于具体实现的视图，是面向计算机面向计算机的。的。一种数据的逻辑结构可以用多种存储结构来存一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效储，而采用不同的存储结构，其数据处理的效率往往是不同的。率往往是不同的。1.3 数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社抽象数据类型抽象数据类型1.数据类型数据类型（Data Type）：一组）：一组值值的集合以及定义的集合以及定义于这个值集上的一组于这个值集上的一组操作操作的总称。的总称。例如：例如：C+中的整型变量中的整型变量 2.抽象抽象（Abstract）:抽出问题本质的特征而忽略非本抽出问题本质的特征而忽略非本质的细节。质的细节。例如：例如：地图、驾驶汽车地图、驾驶汽车3.抽象数据类型抽象数据类型（Abstract Data Type，ADT）:一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总称。的总称。1.3 数据结构的基本概念数据结构的基本概念数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.3 数据结构的基本概念数据结构的基本概念抽象数据类型抽象数据类型在设计在设计ADTADT时，把时，把ADTADT的定义、设计和实现分开来。定义部分只的定义、设计和实现分开来。定义部分只包含数据的逻辑结构和所允许的操作集合，一方面，包含数据的逻辑结构和所允许的操作集合，一方面，ADTADT的使的使用者依据这些定义来使用用者依据这些定义来使用ADTADT，即通过操作集合对该，即通过操作集合对该ADTADT进行操进行操作；另一方面，作；另一方面，ADTADT的实现者依据这些定义来完成该的实现者依据这些定义来完成该ADTADT各种操各种操作的具体实现。作的具体实现。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社ADT 抽象数据类型名抽象数据类型名Data 数据元素之间逻辑关系的定义数据元素之间逻辑关系的定义Operation 操作操作1 前置条件前置条件：执行此操作前数据所必须的状态：执行此操作前数据所必须的状态 输输 入入：执行此操作所需要的输入：执行此操作所需要的输入 功功 能能：该操作将完成的功能：该操作将完成的功能 输输 出出：执行该操作后产生的输出：执行该操作后产生的输出 后置条件后置条件：执行该操作后数据的状态：执行该操作后数据的状态 操作操作2 操作操作n endADT 1.3 数据结构的基本概念数据结构的基本概念抽象数据类型抽象数据类型数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社1.3 1.3 数据结构的基本概念（小结）数据结构的基本概念（小结）数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社算法的相关概念算法的相关概念1.算算法法（Algorithm）:是是对对特特定定问问题题求求解解步步骤骤的的一种描述，是一种描述，是指令指令的的有限序列有限序列。2.算法的五大特性：算法的五大特性：输入输入：一个算法有零个或多个输入。：一个算法有零个或多个输入。输出输出：一个算法有一个或多个输出。：一个算法有一个或多个输出。有穷性有穷性：一个算法必须总是在执行有穷步之后结束，且：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。每一步都在有穷时间内完成。确定性确定性：算法中的每一条指令必须有确切的含义，对于：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。相同的输入只能得到相同的输出。可行性可行性：算法描述的操作可以通过已经实现的基本操作：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。执行有限次来实现。1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社mnr例：欧几里德算法例：欧几里德算法辗转相除法求两个自然数辗转相除法求两个自然数 m 和和 n 的最大公约数的最大公约数1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社算法的描述方法算法的描述方法自然语言自然语言 优点：容易理解优点：容易理解缺点：冗长、二义性缺点：冗长、二义性使用方法：粗线条描述算法思想使用方法：粗线条描述算法思想 注意事项：避免写成自然段注意事项：避免写成自然段1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社步骤步骤1：将：将m除以除以n得到余数得到余数r；步骤步骤2：若：若r等于等于0，则，则n为最大公约数，为最大公约数，算法结束；否则执行步骤算法结束；否则执行步骤3；步骤步骤3：将：将n的值放在的值放在m中，将中，将r的值放在的值放在n中，中，重新执行步骤重新执行步骤1；例：欧几里德算法例：欧几里德算法自然语言1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社优点：流程直观优点：流程直观 缺点：缺少严密性、灵活性缺点：缺少严密性、灵活性使用方法：描述简单算法使用方法：描述简单算法注意事项：注意抽象层次注意事项：注意抽象层次算法的描述方法算法的描述方法流程图流程图 1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社N开始输入m和n r=m%nr=0m=n；n=r 输出n结束Y流 程 图例：欧几里德算法例：欧几里德算法1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社优点：能由计算机执行优点：能由计算机执行 缺点：抽象性差，对语言要求高缺点：抽象性差，对语言要求高使用方法：算法需要验证使用方法：算法需要验证注意事项：将算法写成子函数注意事项：将算法写成子函数算法的描述方法算法的描述方法程序设计语言程序设计语言 1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社#include int CommonFactor(int m,int n)int r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;void main()coutCommonFactor(63,54)endl;程序设计语言例：欧几里德算法例：欧几里德算法1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社伪代码伪代码（Pseudocode）：介于自然语言和）：介于自然语言和程序设计语言之间的方法，它采用某一程序程序设计语言之间的方法，它采用某一程序设计语言的基本语法，操作指令可以结合自设计语言的基本语法，操作指令可以结合自然语言来设计。然语言来设计。优点：表达能力强，抽象性强，容易理解优点：表达能力强，抽象性强，容易理解使用方法：使用方法：7 2算法的描述方法算法的描述方法伪代码伪代码 1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社 1.r=m%n;2.循环直到循环直到 r 等于等于0 2.1 m=n;2.2 n=r;2.3 r=m%n;3.输出输出 n;伪 代 码上述伪代码再上述伪代码再具体具体一些，用一些，用C+的函数来描述。的函数来描述。例：欧几里德算法例：欧几里德算法1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社int CommonFactor(int m,int n)r=m%n;while(r!=0)m=n;n=r;r=m%n;return n;1.4 算法及算法分析算法及算法分析对对C+语言进行了如下简化：语言进行了如下简化：局部变量可以不声明；局部变量可以不声明；写出子函数即可，子函数不用写出子函数即可，子函数不用在主函数中调用，省略主函数；在主函数中调用，省略主函数；所有的包含函数（头函数所有的包含函数（头函数.h）可以省略；可以省略；交换两个变量的语句可以简写交换两个变量的语句可以简写为为ab。数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社算法分析算法分析度量算法效率的方法：度量算法效率的方法：事后统计事后统计：将算法实现，测算其时间和空间开销。：将算法实现，测算其时间和空间开销。缺点：缺点：编写程序实现算法将花费较多的时间和精力；编写程序实现算法将花费较多的时间和精力；所得实验结果依赖于计算机的软硬件等环境因素。所得实验结果依赖于计算机的软硬件等环境因素。事前分析事前分析：对算法所消耗资源的一种估算方法。：对算法所消耗资源的一种估算方法。1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社算法分析算法分析算算法法分分析析（Algorithm Analysis）：对对算算法法所所需需要要的的计计算机资源算机资源时间时间和和空间空间进行估算。进行估算。时间复杂性（时间复杂性（Time Complexity）空间复杂性（空间复杂性（Space Complexity）1.4 算法及算法分析算法及算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社算法的时间复杂度分析算法的时间复杂度分析1.4 算法及算法分析算法及算法分析算法分析算法分析算法的算法的执行时间执行时间每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间指令系统、编译的代码质量指令系统、编译的代码质量单位时间单位时间每条语句每条语句执行次数执行次数之和之和for(i=1;i=n;i+)for(j=1;j=n;j+)x+;基本语句基本语句的执行次数的执行次数数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社问题规模：问题规模：输入量的多少。输入量的多少。基基本本语语句句：是是执执行行次次数数与与整整个个算算法法的的执执行行次次数数成成正比的操作指令。正比的操作指令。for(i=1;i=n;i+)for(j=1;j=n;j+)x+;问题规模：n基本语句：x+1.4 算法及算法分析算法及算法分析算法分析算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有都有T(n)cf(n)，则称，则称T(n)=O(f(n)。n0问题规模问题规模n执执行行次次数数n0之之前前的的情情况况无无关关紧要紧要T(n)cf(n)v当当问题规模充分大问题规模充分大时在渐近意义下的阶。时在渐近意义下的阶。1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析大大O符号符号数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社定定理理：若若A(n)=amnm+am-1nm-1+a1n+a0是是一一个个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。忽略所有低次幂和最高次幂的系数。1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析大大O符号符号数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-5 +x;+x是基本语句，执行次数为是基本语句，执行次数为1，时间复杂度为，时间复杂度为O(1),称常量阶。称常量阶。例例1-6 for(i=1;i=n;+i)+x;时间复杂度为时间复杂度为O(n),称线性阶。称线性阶。例例1-7 for(i=1;i=n;+i)for(j=1;j=n;+j)+x;时间复杂度为时间复杂度为O(n2),称平方阶。称平方阶。1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-8 for(i=1;i=n;+i)for(j=1;j=i-1;+j)+x;执行次数为执行次数为n(n-1)/2，时间复杂度为，时间复杂度为O(n2),称平方阶。称平方阶。例例1-9 for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;时间复杂度为时间复杂度为O(n3),称立方阶。称立方阶。1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社例例1-10 for(i=1;i=n;i=2*i)+x;时间复杂度为时间复杂度为O(log2n),称对数阶。称对数阶。(1)(log2n)(n)(nlog2n)(n2)(n3)(2n)(n!)1.4 算法及算法分析算法及算法分析算法分析算法分析算法分析算法分析数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况例：在一维整型数组例：在一维整型数组A n 中顺序查找与给定值中顺序查找与给定值k相等的相等的元素（假设该数组中有且仅有一个元素值为元素（假设该数组中有且仅有一个元素值为k）。int Find(int A,int n)for(i=0;i n;i+)if(Ai=k)break;return i;1.4 算法及算法分析算法及算法分析基本语句的执行次数是否只和问题规模有关？基本语句的执行次数是否只和问题规模有关？数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社最好情况：出现概率较大时分析最好情况：出现概率较大时分析最差情况：实时系统最差情况：实时系统平均情况：已知输入数据是如何分布的，平均情况：已知输入数据是如何分布的，通常假设等概率分布通常假设等概率分布结论结论：如果问题规模相同，时间代价与输入数据有：如果问题规模相同，时间代价与输入数据有关，则需要分析最好情况、最坏情况、平均情况。关，则需要分析最好情况、最坏情况、平均情况。1.4 算法及算法分析算法及算法分析最好情况、最坏情况、平均情况最好情况、最坏情况、平均情况数据结构数据结构(C+版版)第第2版版清华大学出版社清华大学出版社本章小结本章小结知识结构图知识结构图绪绪绪绪 论论论论数据结构数据结构数据结构数据结构算算算算 法法法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系