《数据结构与算法第一张清华大学出版社赵玉兰.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第一张清华大学出版社赵玉兰.ppt（92页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、刘咏梅内蒙古大学计算机学院315数据结构与算法数据结构与算法DATA STRUCTUREAND ARITHMETIC课程介绍课程介绍课程性质课程性质u计算机专业的课程分为计算机专业的课程分为公共基础课公共基础课专业基础课专业基础课专业方向课专业方向课专业选修课专业选修课u属于属于专业基础课专业基础课u考研的必考科目考研的必考科目计算机科学与技术学科联考专业基础综合共计算机科学与技术学科联考专业基础综合共150分，其分，其中中数据结构数据结构占占45分分课程介绍课程介绍u在教学计划中的地位：在教学计划中的地位：核心课程核心课程前导课程前导课程高等数学高等数学离散数学离散数学程序设计语言程序设计语
2、言后续课程后续课程操作系统操作系统编译编译数据库数据库课程介绍课程介绍教材及参考书教材及参考书u数据结构与算法数据结构与算法赵玉兰赵玉兰 等著，清华大学出版社等著，清华大学出版社u数据结构数据结构用面向对象方法与用面向对象方法与C+描述描述 殷人昆著，殷人昆著，清华大学出版社清华大学出版社u数据结构数据结构 严蔚敏、吴伟民著，严蔚敏、吴伟民著，清华大学出版社清华大学出版社u数据结构与算法分析数据结构与算法分析张铭、刘晓丹译，电子工业张铭、刘晓丹译，电子工业出版社出版社uComputer Algorithms Introduction to Design and Analysis Sara ba
3、se，高等教育出版社影印高等教育出版社影印uData Structures and Algorithms Alfred V.Ahou网上阅读材料网上阅读材料课程介绍课程介绍教学内容教学内容 第第3 3单元单元 常用数据处理技术常用数据处理技术数据结构的数据结构的基本概念基本概念算法的基本算法的基本概念概念第第1 1单单元元 基基本本概概念念线性表线性表树和二叉树树和二叉树图图特殊线性表特殊线性表广义线性表广义线性表 第第2 2单元单元 基本数据结构基本数据结构排序技术排序技术索引技术索引技术查找技术查找技术集合集合课程介绍课程介绍学习目标学习目标u知识方面知识方面掌握基本的数据结构掌握基本的数
4、据结构掌握数据结构的实现方法以及经典算法掌握数据结构的实现方法以及经典算法掌握初步的算法分析技术掌握初步的算法分析技术u能力方面能力方面培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力培养计算机思维能力培养计算机思维能力课程介绍课程介绍成绩组成成绩组成u总成绩平时成绩总成绩平时成绩30期末考试成绩期末考试成绩70u平时成绩包括作业成绩和上机成绩平时成绩包括作业成绩和上机成绩课程介绍课程介绍学习要求学习要求u重视课后习题重视课后习题u重视上机实验重视上机实验u最有害的行为最有害的行为抄袭他人作业抄袭他人作业拷贝他人程序拷贝他人程序第第1章章 概述概述1.1 数据结构的发展数据结构的发
5、展1.2 数据结构数据结构1.3 数据的逻辑结构数据的逻辑结构1.4 抽象数据类型抽象数据类型1.5 数据的存储结构数据的存储结构1.6 算法与算法分析算法与算法分析1.7 总结总结101.1 数据结构的发展数据结构的发展数据结构起源于程序设计，并随着程序设计的数据结构起源于程序设计，并随着程序设计的发展而发展发展而发展程序设计的实质是数据表示和数据处理程序设计的实质是数据表示和数据处理u数据表示：如何将数据从机外表示转化为机内表数据表示：如何将数据从机外表示转化为机内表示，存储在计算机（内存）中示，存储在计算机（内存）中u数据处理：如何处理机内表示的数据，实现问题数据处理：如何处理机内表示的
6、数据，实现问题求解或完成处理要求求解或完成处理要求 数据结构与算法数据结构与算法课程主要讨论数据表示和课程主要讨论数据表示和数据处理过程中的基本问题。数据处理过程中的基本问题。111.1 数据结构的发展数据结构的发展程序设计的发展阶段程序设计的发展阶段u无结构阶段无结构阶段应用领域：科学计算应用领域：科学计算处理的数据：数值型数据处理的数据：数值型数据数据之间的关系：数学方程或数学模型数据之间的关系：数学方程或数学模型例例l方程组求解方程组求解 l定积分定积分 在这一阶段，数据结构还未形成一门系统的学在这一阶段，数据结构还未形成一门系统的学科，而是零星地分布在程序设计、图论、集合、代科，而是零
7、星地分布在程序设计、图论、集合、代数、操作系统和编译原理等课程中。数、操作系统和编译原理等课程中。121.1 数据结构的发展数据结构的发展u结构化阶段结构化阶段 应用领域：科学计算与非数值性数据处理应用领域：科学计算与非数值性数据处理 处理的数据：数值型数据和非数值型数据处理的数据：数值型数据和非数值型数据70s80s90s70s80s 非数值问题猛增非数值问题猛增 数据之间的关系：产生了数据结构，提出了程序结构模数据之间的关系：产生了数据结构，提出了程序结构模块化，开始注意数据表示和操作的结构化块化，开始注意数据表示和操作的结构化数据结构算法程序数据结构算法程序 1968年，年，D.E.Kn
8、uth 所著的所著的计算机程序设计计算机程序设计技巧技巧第一卷第一卷基本算法基本算法，首次较系统地阐述了，首次较系统地阐述了数据的逻辑结构和存储结构以及定义在数据上的操数据的逻辑结构和存储结构以及定义在数据上的操作，开创了数据结构的课程体系。同年，作，开创了数据结构的课程体系。同年，数据结数据结构构作为一门独立的课程在计算机科学的学科课程作为一门独立的课程在计算机科学的学科课程中开始出现。中开始出现。131.1 数据结构的发展数据结构的发展u面向对象阶段面向对象阶段应用领域：更多地应用于非数值处理应用领域：更多地应用于非数值处理处理的数据：更多地处理非数值型数据处理的数据：更多地处理非数值型数
9、据数据之间的关系：数据结构发展到面向对象阶段数据之间的关系：数据结构发展到面向对象阶段（数据结构算法）程序（数据结构算法）程序类和数据结构之间的对应关系类和数据结构之间的对应关系类类属性属性方法方法数据结构数据结构数据之间的关系数据之间的关系基本操作基本操作对应对应141.1 数据结构的发展数据结构的发展数据结构的创始人数据结构的创始人D.E.Knuth1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁
10、起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖。此时，他年界的最高荣誉图灵奖。此时，他年仅仅36岁。岁。151.2 数据结构数据结构数据结构的研究对象数据结构的研究对象u用计算机求解问题的一般过程用计算机求解问题的一般过程具具体体问问题题建建立立模模型型设设计计算算法法编制编制计算机计算机程序程序问题分为两类问题分为两类数值问题数值问题非数值问题非数值问题161.2 数据结
11、构数据结构u数值问题数值问题建立的模型是数学方程建立的模型是数学方程问题求解的核心是数值计算问题求解的核心是数值计算例例l弹道计算弹道计算 l矩阵运算矩阵运算 M1M2M3Mnl方程组求解方程组求解 l定积分定积分数学方程数学方程171.2 数据结构数据结构u非数值问题非数值问题例例1 电话号码簿电话号码簿党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234
12、计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关党政机关 党委总机党委总机 4811122 宣传部宣传部 4811234 组织部组织部 4812345大专院校大专院校 内蒙古大学内蒙古大学 校务办公室校务办公室 4991234 计算机学院计算机学院 4992930 6845678是谁是谁的电话？的电话？太难太难找了！找了！181.2 数据结构数据结构l电话号码簿的结构：按照单位排列电话号码电话号码簿的结构：按照单位排列电话号码内蒙古党委内蒙古党委内
13、蒙古政府内蒙古政府党政机关党政机关理工学院理工学院计算机系计算机系网络中心网络中心计算中心计算中心计算机学院计算机学院内蒙古大学内蒙古大学内蒙古工业大学内蒙古工业大学大专院校大专院校医疗卫生医疗卫生交通运输交通运输呼和浩特市呼和浩特市电话号码簿电话号码簿191.2 数据结构数据结构l改变结构：按电话号码的大小排列改变结构：按电话号码的大小排列党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙
14、古大学 校务办公室 4991234 计算机学院 4992930 党政机关 党委总机 4811122 宣传部 4811234 组织部 4812345大专院校 内蒙古大学 校务办公室 4991234 计算机学院 4992930 110.匪警匪警 119火警火警120急救急救1234567.6845678.Tom6845678是老朋是老朋友友Tom的电话，的电话，太容易找了！太容易找了！201.2 数据结构数据结构例例2 学籍学籍管理问题管理问题表结构表结构 姓名姓名学号学号性别性别年龄年龄民族民族系系专业专业入学时间入学时间王小林王小林060631男男18汉族汉族计算机计算机计算机科学计算机科学2
15、006.9陈陈 红红060632女女20蒙族蒙族计算机计算机计算机应用计算机应用2006.9刘建平刘建平060633男男19回族回族计算机计算机电子商务电子商务2006.9.211.2 数据结构数据结构例例3 人机对弈问题人机对弈问题树结构树结构.221.2 数据结构数据结构例例4 教学计划编排问题教学计划编排问题图结构图结构C4,C5,C6数据库原理数据库原理C7C2,C4计算机原理计算机原理C6C3,C4数据结构数据结构C5C1,C2程序设计程序设计C4C1离散数学离散数学C3无无计算机导论计算机导论C2无无高等数学高等数学C1先修课先修课课程名称课程名称编号编号C1C2C3C4C6C5C
16、7231.2 数据结构数据结构总结总结l非数值问题建立的模型是诸如表、树、图之类的数非数值问题建立的模型是诸如表、树、图之类的数据结构，而不是数学方程据结构，而不是数学方程l非数值问题求解的核心是数据处理，而不是数值计非数值问题求解的核心是数据处理，而不是数值计算算 数据结构是一门研究非数值问题中计算机的数据结构是一门研究非数值问题中计算机的操作对象以及它们之间的关系和操作的学科。操作对象以及它们之间的关系和操作的学科。数据结构数据结构241.2 数据结构数据结构基本概念基本概念u数据（数据（Data）：是信息的载体，在计算机科学中）：是信息的载体，在计算机科学中指所有能输入到计算机中，并能被
17、计算机程序识指所有能输入到计算机中，并能被计算机程序识别和处理的符号集合。别和处理的符号集合。数值性数据数值性数据非数值性数据非数值性数据251.2 数据结构数据结构u数据元素数据元素（Data Element）（数据成员）：数据）（数据成员）：数据的基本单位。在计算机程序中常作为一个整体进的基本单位。在计算机程序中常作为一个整体进行考虑和处理。行考虑和处理。数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。u数据项（数据项（Data Item）：组成数据元素的不可分割）：组成数据元素的不可分割的最小单位。的最小单位。261.2 数据结构数据结构u数据对象（数据对象（Data O
18、bject）：数据的子集。具有相）：数据的子集。具有相同性质的数据元素的集合。同性质的数据元素的集合。整数数据对象，包括整数数据对象，包括 0,1,2,字母数据对象，包括字母数据对象，包括 A,B,Z,a,b,z学生数据对象学生数据对象271.2 数据结构数据结构u例例2 学籍管理问题学籍管理问题每一行是一个数据元素每一行是一个数据元素每一列是一个数据项每一列是一个数据项学生数据元素的集合是一个数据对象学生数据元素的集合是一个数据对象姓名姓名学号学号性别性别年龄年龄民族民族系系专业专业入学时间入学时间王小林王小林060631男男18汉族汉族计算机计算机计算机科学计算机科学2006.9陈陈 红红
19、060632女女20蒙族蒙族计算机计算机计算机应用计算机应用2006.9刘建平刘建平060633男男19回族回族计算机计算机电子商务电子商务2006.9.281.2 数据结构数据结构u数据类型（数据类型（Data Type）：指定一种数据对象的类）：指定一种数据对象的类型。定义为一个值的集合以及定义在该值集合上型。定义为一个值的集合以及定义在该值集合上的一组操作的总称。的一组操作的总称。C+语言的数据类型语言的数据类型基本类型基本类型结构类型结构类型整型整型实型实型字符型字符型枚举型枚举型指针型指针型数组型数组型结构型结构型共用体共用体类类291.2 数据结构数据结构u数据结构数据结构按照某种
20、按照某种逻辑关系逻辑关系组织起来的一批数据，按一定的组织起来的一批数据，按一定的存储存储方法方法把它存储在计算机中，并在这些数据上定义了一个把它存储在计算机中，并在这些数据上定义了一个运算的集合运算的集合。301.2 数据结构数据结构u数据结构研究的对象包括三个方面数据结构研究的对象包括三个方面数据的逻辑结构数据的逻辑结构l指数据元素之间的逻辑关系，即指数据元素之间的指数据元素之间的逻辑关系，即指数据元素之间的关联方式或邻接关系关联方式或邻接关系数据的存储结构数据的存储结构l指数据元素在计算机中的存储结构，如某个电话号指数据元素在计算机中的存储结构，如某个电话号码在号码本上的位置码在号码本上的
21、位置运算的集合运算的集合l定义在该结构上的一组操作，如输入定义在该结构上的一组操作，如输入/读取、检索读取、检索/查找、插入、删除、更新等查找、插入、删除、更新等311.3 数据的逻辑结构数据的逻辑结构预备知识预备知识偶对偶对u在数学中，用来表示两个事物之间所具有的固定在数学中，用来表示两个事物之间所具有的固定关系的方法，叫偶对关系的方法，叫偶对u分类分类无序偶对无序偶对l两个事物之间的关系没有次序之分两个事物之间的关系没有次序之分l表示：表示：(a,b)有序偶对有序偶对l两个事物之间的关系有次序之分两个事物之间的关系有次序之分l表示：表示：abab321.3 数据的逻辑结构数据的逻辑结构（直
22、接）前驱（直接）前驱（Previous）与（直接）后继（）与（直接）后继（Next）u如果有如果有，称，称 a 是是 b 的（直接）前驱，的（直接）前驱，b 是是 a的（直接）后继的（直接）后继笛卡儿积（笛卡儿积（Descartes Set）u给定两个集合给定两个集合 A 和和 B，如果有序偶对的第一个分，如果有序偶对的第一个分量是量是 A 的一个元素，第二个分量是的一个元素，第二个分量是 B 的一个元素，的一个元素，则所有这种有序偶对的集合称为集合则所有这种有序偶对的集合称为集合 A 和和 B 的笛的笛卡儿积卡儿积u记为：记为：AB|x A y B331.3 数据的逻辑结构数据的逻辑结构二元
23、关系（二元关系（Duality Relationship）uR 是集合是集合 A 上的二元关系：上的二元关系：RAA数据的逻辑结构数据的逻辑结构u由数据元素集及其逻辑关系组成，可形式地描述由数据元素集及其逻辑关系组成，可形式地描述为：为：Data_Structure=（D,R）其中：其中：D 是数据元素的有限集合；是数据元素的有限集合；R 是是 D 上的有上的有限关系集合。限关系集合。341.3 数据的逻辑结构数据的逻辑结构说明说明u从逻辑关系上描述数据，与数据的存储无关从逻辑关系上描述数据，与数据的存储无关u可以看作是从具体问题抽象出来的数据模型可以看作是从具体问题抽象出来的数据模型u面向问
24、题，面向用户面向问题，面向用户分类（根据数据元素间的不同特性）分类（根据数据元素间的不同特性）非线性非线性结构结构u线性结构线性结构u集合集合u树形结构树形结构u图或网状结构图或网状结构351.3 数据的逻辑结构数据的逻辑结构线性结构（线性结构（Linear Structure）uLS=(D,R)D=d1,d2,dn R=|i=1,2,3,n-1u例例4 DS=(D,R1)D=d1,d2,d3,d4,d5,d6 R1=,d1 d2 d3 d4 d5 d6 n仅有一个开始结点，仅有一个终仅有一个开始结点，仅有一个终端结点端结点n其它都是内部结点，且都有且仅其它都是内部结点，且都有且仅有一个直接前
25、驱、一个直接后继有一个直接前驱、一个直接后继361.3 数据的逻辑结构数据的逻辑结构集合集合u例例5 DS=(D,R2)D=d1,d2,d3,d4,d5,d6 R2=d1 D,d2 D,d3 D,d4 D,d5 D,d6 D结构中的数据元素只具有结构中的数据元素只具有“同同属于一个集合属于一个集合”的关系的关系d2d6d1d3d5d4371.3 数据的逻辑结构数据的逻辑结构树形结构树形结构u例例6 DS=(D,R3)D=d1,d2,d3,d4,d5,d6,d7 R3=,d4d1d2d3d5d6 d7 n有且仅有一个根结点有且仅有一个根结点n其它结点有且仅有一个其它结点有且仅有一个前驱结点前驱结
26、点n对于非根结点都存在从对于非根结点都存在从根到该结点的一条路径根到该结点的一条路径n结构中的数据元素存在结构中的数据元素存在一对多一对多的关系的关系381.3 数据的逻辑结构数据的逻辑结构图形或网状结构图形或网状结构u例例7 DS=(D,R4)D=d1,d2,d3,d4,d5 R4=,n结构中的数据元素存结构中的数据元素存在在多对多多对多的关系的关系d1d2d3d4d5391.4 抽象数据类型抽象数据类型抽象数据类型（抽象数据类型（Abstract Data Types，ADT）u面向对象技术核心概念面向对象技术核心概念u面向对象程序设计的基础（面向对象程序设计的基础（C+，Java，）u抽
27、象层次高，模块复用度高抽象层次高，模块复用度高 使用使用ADT有极大的优势有极大的优势401.4 抽象数据类型抽象数据类型u数据类型数据类型一个一个值的集合值的集合以及定义在该值集合上的以及定义在该值集合上的一组操作一组操作的总称的总称规定了该数据类型的取值范围和对这些数据所能采取的规定了该数据类型的取值范围和对这些数据所能采取的操作操作例，例，C+中的整型变量中的整型变量u抽象抽象抽出问题本质的特征而忽略非本质的细节，是对具体事抽出问题本质的特征而忽略非本质的细节，是对具体事物的一个概括物的一个概括隐藏了繁杂的细节，只保留实现目标所必需的信息隐藏了繁杂的细节，只保留实现目标所必需的信息例，地
28、图、驾驶汽车例，地图、驾驶汽车411.4 抽象数据类型抽象数据类型u抽象数据类型（抽象数据类型（Abstract Data Types，ADT）一个一个数学模型数学模型以及定义在以及定义在该模型该模型上的一组操作的总称上的一组操作的总称抽象数据类型与数据类型的区别抽象数据类型与数据类型的区别u数据类型仅局限于计算机（高级程序设计语言）数据类型仅局限于计算机（高级程序设计语言）中定义并实现了的数据类型中定义并实现了的数据类型u抽象数据类型还包括用户在设计软件系统时自己抽象数据类型还包括用户在设计软件系统时自己定义的数据类型定义的数据类型关键关键u使用它的人可以只关心它的逻辑特征，不需要了使用它的
29、人可以只关心它的逻辑特征，不需要了解它的存储方式解它的存储方式u定义它的人同样不必要关心它如何存储定义它的人同样不必要关心它如何存储421.4 抽象数据类型抽象数据类型ADT的描述的描述ADT ADT-name Data 数学模型或数据的逻辑结构数学模型或数据的逻辑结构 Operations /操作集操作集 Constrictor/构造操作，初始化构造操作，初始化 Initial values：用于初始化的值。：用于初始化的值。Process：初始化。：初始化。Operation1 Input：输入数据（参数）。：输入数据（参数）。Preconditions：执行本操作前系统必须处于的状态。：
30、执行本操作前系统必须处于的状态。Process：操作。：操作。Output：输出。：输出。Postconditions：执行本操作后系统所处状态。：执行本操作后系统所处状态。Operation2 Operationk/ADT-name431.4 抽象数据类型抽象数据类型例例8 自然数的抽象数据类型定义自然数的抽象数据类型定义ADT NaturalNumber Data：一个整数的有序子集合，它开始于一个整数的有序子集合，它开始于0，结束于机器，结束于机器 能表示的最大整数（能表示的最大整数（MaxInt）。）。Operations：对于所有的对于所有的 x,y NaturalNumber；Fa
31、lse,True Boolean，+、-、=、=等都等都 是可用的服务。是可用的服务。Zero()：NaturalNumber 返回自然数返回自然数0 IsZero(x):Boolean if(x=0)返回返回True else 返回返回False441.4 抽象数据类型抽象数据类型 Add(x,y):NaturalNumber if(x+y=MaxInt)返回返回 x+y else 返回返回MaxInt Subtract(x,y):NaturalNumber if(x y)返回返回 0 else 返回返回 x-y Equal(x,y):Boolean if(x=y)返回返回True else
32、 返回返回 False Successor(x):NaturalNumber if(x=MaxInt)返回返回 x else 返回返回 x+1 /NaturalNumber 451.5 数据的存储结构数据的存储结构数据的存储结构（数据的存储结构（Store Structure）u数据及其逻辑结构在计算机中的表示数据及其逻辑结构在计算机中的表示u面向计算机，面向具体实现面向计算机，面向具体实现u分类分类顺序存储结构（顺序存储结构（Sequential Store Structure）链式存储结构（链式存储结构（Linked Store Structure）461.5 数据的存储结构数据的存储结构
33、顺序存储结构顺序存储结构u例例9 LS=D,R D=a,b,c,d,e R=,abcde10241026102810301032存储空间连续存储空间连续保持了逻辑关系保持了逻辑关系数据元素的存储位置数据元素的存储位置a b c d e471.5 数据的存储结构数据的存储结构链式存储结构链式存储结构存储空间存储空间不不连续连续保持了逻辑关系保持了逻辑关系数数据据元元素素的的存存储储位位置置e 0 b 1040 a 1026d 1024 c 1034 102410261028103010321034103610381040abcde 不考虑具体地址，抽象为不考虑具体地址，抽象为数据元素数据元素 指
34、针指针结点（结点（node）：）：存储一个存储一个数据元素及附加信息的数据元素及附加信息的存储空间存储空间指针（指针（pointer）：）：存储地址存储地址 481.5 数据的存储结构数据的存储结构顺序存储结构的基本思想顺序存储结构的基本思想u用一组用一组连续连续的存储单元的存储单元依次依次存储数据元素存储数据元素u数据元素之间的逻辑关系是由元素的存储位置来数据元素之间的逻辑关系是由元素的存储位置来（隐式）表示的（隐式）表示的链式存储结构的基本思想链式存储结构的基本思想u用一组用一组任意任意的存储单元存储数据元素的存储单元存储数据元素u数据元素之间的逻辑关系是用指针来（显式）表数据元素之间的逻
35、辑关系是用指针来（显式）表示的示的491.5 数据的存储结构数据的存储结构数据的逻辑结构和存储结构是密切相关的两个方面数据的逻辑结构和存储结构是密切相关的两个方面u数据的逻辑结构是数据的机外表示，数据的存储数据的逻辑结构是数据的机外表示，数据的存储结构是数据的机内表示结构是数据的机内表示u一种数据的逻辑结构可以用多种存储结构来存储一种数据的逻辑结构可以用多种存储结构来存储u数据结构的基本操作是定义于逻辑结构，实现于数据结构的基本操作是定义于逻辑结构，实现于存储结构存储结构u采用不同的存储结构，其数据处理的效率往往是采用不同的存储结构，其数据处理的效率往往是不同的不同的501.6 算法与算法分析
36、算法与算法分析算法（算法（Algorithms）定义定义 u对具体问题的求解步骤，是指令的有限序列。对具体问题的求解步骤，是指令的有限序列。特性特性u有穷性有穷性一个算法必须在执行有限步骤后终止，且每一步都在有一个算法必须在执行有限步骤后终止，且每一步都在有限时间完成。限时间完成。u确定性确定性算法中的每条指令必须有确切的含义，无二义性。算法中的每条指令必须有确切的含义，无二义性。511.6 算法与算法分析算法与算法分析u可行性（有效性）可行性（有效性）算法中的所有操作都可以通过已经实现的基本操作执行算法中的所有操作都可以通过已经实现的基本操作执行有限次来实现。有限次来实现。u输入输入算法运行
37、过程中从外界给定的数据；算法运行过程中从外界给定的数据；一个算法有一个算法有0个或多个输入数据。个或多个输入数据。u输出输出对输入数据加工后的结果的输出；对输入数据加工后的结果的输出；一个算法至少有一个算法至少有1个输出数据。（必须有输出）个输出数据。（必须有输出）521.6 算法与算法分析算法与算法分析算法算法程序程序u程序是对一个算法使用某种程序设计语言的具体程序是对一个算法使用某种程序设计语言的具体实现，是对算法的精确描述，可在计算机上执行实现，是对算法的精确描述，可在计算机上执行u算法一定要满足有穷性而程序并不一定满足算法一定要满足有穷性而程序并不一定满足u程序设计的核心是算法设计程序
38、设计的核心是算法设计531.6 算法与算法分析算法与算法分析评价算法评价算法“好坏好坏”的几个标准的几个标准u算法的正确性算法的正确性u算法的效率算法的效率u占用空间量占用空间量u简单性和清晰性简单性和清晰性u最优性最优性541.6 算法与算法分析算法与算法分析算法的正确性算法的正确性u对任一合法的输入，算法结束后得到正确结果。对任一合法的输入，算法结束后得到正确结果。u体现在两个方面体现在两个方面求解问题的方法（算法）是正确的；求解问题的方法（算法）是正确的；对算法实现（程序）是正确的。对算法实现（程序）是正确的。u算法的正确性由问题领域的理论和定理保证和证算法的正确性由问题领域的理论和定理
39、保证和证明。如高斯迭代法，其正确性是由线性代数的理明。如高斯迭代法，其正确性是由线性代数的理论证明。论证明。u程序的正确性通过软件测试来判定，但测试无法程序的正确性通过软件测试来判定，但测试无法保证程序是绝对正确的。保证程序是绝对正确的。551.6 算法与算法分析算法与算法分析简单性（简单性（Simplicity）u简单的算法的优点简单的算法的优点易于验证正确性易于验证正确性易于实现（编写程序）易于实现（编写程序）易于调试、修改易于调试、修改u设计算法时，也需要权衡简单性和时间、空间复设计算法时，也需要权衡简单性和时间、空间复杂度之间的关系杂度之间的关系u通常方法越直接、越简单，算法的效率越低
40、通常方法越直接、越简单，算法的效率越低561.6 算法与算法分析算法与算法分析最优性（最优性（Optimality）u问题的下界（问题的下界（Lower Bounds）问题固有的复杂度，解决该问题至少要做的工作量问题固有的复杂度，解决该问题至少要做的工作量u算法的上界（算法的上界（Upper Bounds）算法工作量的上界算法工作量的上界u最优算法最优算法算法的上界问题的下界算法的上界问题的下界2m问问题题的的下下界界算算法法的的上上界界571.6 算法与算法分析算法与算法分析算法性能分析和度量算法性能分析和度量问题的提出问题的提出u计算机的所有应用问题，包括计算机自身的发展，计算机的所有应用
41、问题，包括计算机自身的发展，都是围绕着都是围绕着“时间时间速度速度”这一中心进行的。这一中心进行的。u算法的效率（算法的工作量）算法的效率（算法的工作量）指算法的执行时间指算法的执行时间效率越高，工作量越小，执行时间越短效率越高，工作量越小，执行时间越短u对给定的问题设计出多种算法时，如何选择其中对给定的问题设计出多种算法时，如何选择其中效率高的算法？效率高的算法？581.6 算法与算法分析算法与算法分析例例10 在三个整数中求最大者在三个整数中求最大者max(int a,int b,int c)if(ab)if(ac)return a;else return c;else if(bc)ret
42、urn b;else return c;/*/*无需额外存储空间，只需无需额外存储空间，只需两次比较两次比较*/max(int a3)int c,int i;c=a0;for(i=1;ic)c=ai;return c;/*/*需要两个额外的存储空间，需要两个额外的存储空间，两次比较，至少一次赋值两次比较，至少一次赋值*/591.6 算法与算法分析算法与算法分析度量算法效率的方法之一度量算法效率的方法之一事后测算事后测算u用源程序分别实现这些算法，然后输入适当的数用源程序分别实现这些算法，然后输入适当的数据运行，测算不同算法花费的时间。据运行，测算不同算法花费的时间。u缺点缺点编写多个程序并进行
43、测算，需要花费很多的时间和精力；编写多个程序并进行测算，需要花费很多的时间和精力；测试数据的选择可能对其中的某个算法有利；测试数据的选择可能对其中的某个算法有利；实验结果受运行环境、编译器、可用存储空间大小等的实验结果受运行环境、编译器、可用存储空间大小等的影响，有时容易掩盖算法本身的优劣；影响，有时容易掩盖算法本身的优劣；即使其中较好的那种算法也超出了你预算的开销。即使其中较好的那种算法也超出了你预算的开销。601.6 算法与算法分析算法与算法分析度量算法效率的方法之二度量算法效率的方法之二算法分析算法分析u算法分析：对一个算法执行时所消耗的两种计算算法分析：对一个算法执行时所消耗的两种计算
44、机资源（时间和空间）进行机资源（时间和空间）进行事前估算事前估算。u如何度量如何度量时间复杂度时间复杂度空间复杂度空间复杂度611.6 算法与算法分析算法与算法分析时间复杂度（时间复杂度（Time Complexity）u例例11for(int i=1;i=n;i+)for(int j=1;jn0，有，有|T(n)|c|f(n)|，则称，则称 T(n)在集合在集合 O(f(n)中。中。大大O表示法用于描述某一算法的上限，即当输入尺寸为表示法用于描述某一算法的上限，即当输入尺寸为n 时，一种算法所消耗的某种资源（通常是时间）的最时，一种算法所消耗的某种资源（通常是时间）的最大值。大值。定理：若定
45、理：若 A(n)=amnm+am-1nm-1+a1n+a0 是一个是一个m次次多多项项式，式，则则 A(n)=O(nm)。661.6 算法与算法分析算法与算法分析u时间复杂度分析举例时间复杂度分析举例x+;for(int i=1;i=n;i+)x+;for(int i=1;i=n;i+)for(int j=1;j=i-1;j+)x+;基本语句：基本语句：x+执行次数：执行次数：1时间复杂度时间复杂度 T(n)=1=O(1)基本语句：基本语句：x+执行次数：执行次数：n时间复杂度时间复杂度 T(n)=n=O(n)基本语句：基本语句：x+执行次数：执行次数：时间复杂度时间复杂度 T(n)=O(n2
46、)671.6 算法与算法分析算法与算法分析u应用规则应用规则加法规则加法规则 针对并列程序段针对并列程序段 T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)乘法规则乘法规则 针对嵌套程序段针对嵌套程序段 T(n,m)=T1(n)T2(m)=O(f(n)g(m)681.6 算法与算法分析算法与算法分析u例例12sum=0;for(i=1;i=n;i+)for(j=1;j=n;j+)sum+;for(k=1;k=n;k+)ak=k-1;的基本语句：的基本语句：sum=0 执行次数：执行次数：1 时间复杂度：时间复杂度：O(1)的基本语句：的基本语句：sum+执行次数：执行次数：
47、n2 时间复杂度：时间复杂度：O(n2)的基本语句：的基本语句：ak=k-1 执行次数：执行次数：n 时间复杂度：时间复杂度：O(n)则算法总的时间复杂度为则算法总的时间复杂度为 max(O(1),O(n2),O(n)=O(n2)691.6 算法与算法分析算法与算法分析u测试题测试题void example(float x ,int m,int n,int k)float sum ;for(int i=0;im;i+)/x 中各行数据累加中各行数据累加 sumi=0.0;for(int j=0;jn;j+)sumi+=xij;for(i=0;i m;i+)/打印各行数据和打印各行数据和 cou
48、t “Line”i “:”sum i endl;时间复杂度为时间复杂度为 O(max(mn,m)=O(mn)701.6 算法与算法分析算法与算法分析u增长率的对比增长率的对比c log2n n nlog2n n2 n3 2n 3n n!711.6 算法与算法分析算法与算法分析旧机器：旧机器：1小时可完成小时可完成10000个基本操作个基本操作新机器：执行速度是旧机器的新机器：执行速度是旧机器的10倍倍 T(n)：算法的时间复杂度：算法的时间复杂度n：旧机器一小时能完成的输入尺寸：旧机器一小时能完成的输入尺寸n：新机器一小时能完成的输入尺寸：新机器一小时能完成的输入尺寸增长率高的算法增长率高的算
49、法从机器升级中得从机器升级中得益较少！益较少！721.6 算法与算法分析算法与算法分析最好、最坏、平均情况下的时间复杂度最好、最坏、平均情况下的时间复杂度u对于某些算法，即使输入尺寸相同，如果输入数对于某些算法，即使输入尺寸相同，如果输入数据不同，其时间开销也不同据不同，其时间开销也不同u例例12 在一维整数数组在一维整数数组 An 中顺序查找与给定值中顺序查找与给定值k相等的元素（假设数组中有且仅有一个元素的值相等的元素（假设数组中有且仅有一个元素的值为为 k），算法见下页。），算法见下页。731.6 算法与算法分析算法与算法分析基本语句：元素比较基本语句：元素比较执行次数：取决于被查元素在
50、数组中的位置执行次数：取决于被查元素在数组中的位置l最好情况：数组中第一个元素就是最好情况：数组中第一个元素就是 k，算法只需比，算法只需比较较1次。次。l最坏情况最坏情况:数组中最后一个元素是数组中最后一个元素是 k，算法需要比，算法需要比较较 n 次。次。l平均情况：查找到数组一半时找到平均情况：查找到数组一半时找到 k，比较次数，比较次数 n/2 次。次。int Find(int A,int n,int k)for(int i=0;in;i+)if(Ai=k)break;return i;741.6 算法与算法分析算法与算法分析u说明说明最好情况发生概率太小，不能作为算法性能的代表。最好