数据结构第一章

1、 数 据 结 构教材和教学参考资源教材和教学参考资源教材：教材：数据结构数据结构C语言描述语言描述 耿国华耿国华 高等教育出版社高等教育出版社参考教材参考教材 ：1.1.数据结构（数据结构（C C语言版）语言版） 严蔚敏严蔚敏 清华大学出版社清华大学出版社2.2.数据结构与算法数据结构与算法 许卓群编许卓群编 高等教育出版社（高等教育出版社（C+)C+)3.3.数据结构与算法数据结构与算法 齐德昱编齐德昱编 清华大学出版社清华大学出版社(C+)(C+)4.4.数据结构习题与解析数据结构习题与解析 李春葆编李春葆编 清华大学出版社清华大学出版社5.5.数据结构程序设计题典数据结构程序设计题典李春

2、葆等编李春葆等编 清华大学出版社清华大学出版社 6.6.算法与数据结构考研试题精析算法与数据结构考研试题精析 陈守礼等主编陈守礼等主编 机械工业出版社机械工业出版社7. 7. 网络资源网络资源(http:/ (http:/ 课程性质课程性质v数据结构是计算机专业的数据结构是计算机专业的专业基础课专业基础课 公共基础课、专业基础课、专业方向课、专业选修课公共基础课、专业基础课、专业方向课、专业选修课v在教学计划中的地位：在教学计划中的地位：核心、承上启下核心、承上启下 前导课：高等数学、离散数学、程序设计语言前导课：高等数学、离散数学、程序设计语言 后续课：数据库、操作系统、编译原理后续课：数据

3、库、操作系统、编译原理v属于武术中的属于武术中的“练功练功”科目科目 “练武不练功，到头一场空练武不练功，到头一场空”v考研科目，面试科目考研科目，面试科目学习目标学习目标 知识方面知识方面掌握基本的数据结构掌握基本的数据结构 工具箱工具箱复用、修改、重组复用、修改、重组掌握数据结构的实现方法以及经典算法掌握数据结构的实现方法以及经典算法 学习经典算法学习经典算法模仿模仿掌握初步的算法分析技术掌握初步的算法分析技术 评价算法、改进算法评价算法、改进算法学习目标学习目标 能力方面能力方面培养算法设计能力、程序设计能力培养算法设计能力、程序设计能力 算法算法程序的灵魂程序的灵魂 问题求解过程：问题

4、问题求解过程：问题想法想法算法算法程序程序 程序设计研究的层次：算法程序设计研究的层次：算法方法学方法学语言语言工具工具培养计算机思维能力培养计算机思维能力 计算机思维：逻辑思维和抽象思维计算机思维：逻辑思维和抽象思维 计算机求解问题的思路：计算机求解问题的思路： 问题问题形式化描述形式化描述自动化计算自动化计算学习要求学习要求v循序渐进，切忌心浮气躁循序渐进，切忌心浮气躁 提高课外学习的时间和内容提高课外学习的时间和内容 理解科学而不是背诵科学理解科学而不是背诵科学 会读书，会学习会读书，会学习 正确对待考试正确对待考试v作习题作习题v作实验作实验v听课笔记听课笔记 本本 课课 程程 教教

5、学学 内内 容容第一章第一章 绪论绪论第二章第二章 线性表线性表第三章第三章 栈和队列栈和队列第四章第四章 串串第五章第五章 数组和广义表数组和广义表第六章第六章 树和二叉树树和二叉树第七章第七章 图图第八章第八章 查找查找第九章第九章 内部排序内部排序 本本 课课 程程 内内 容容 结结 构构数数据据结结构构线线性性结结构构非非线线性性结结构构线性表线性表栈栈队列队列串串数组和广义表数组和广义表顺序表顺序表链表链表两种存两种存储结构储结构顺序存储顺序存储链式存储链式存储树树图图二叉树的存储二叉树的存储二叉树的遍历二叉树的遍历树和森林树和森林哈夫曼树及哈夫曼编码哈夫曼树及哈夫曼编码图的存储图的

6、存储图的遍历图的遍历最小生成树最小生成树拓扑排序和关键路径拓扑排序和关键路径最短路径最短路径查找查找排序排序静态静态动态动态哈希表哈希表内部内部外部外部 第一章第一章 绪绪 论论本章主要内容：本章主要内容：了解数据结构兴起与发展了解数据结构兴起与发展 数据结构的基本概念数据结构的基本概念算法的概念、分析和评价算法的概念、分析和评价学习重点及要求：学习重点及要求： 掌握数据结构的基本概念掌握数据结构的基本概念 掌握算法的概念及评价掌握算法的概念及评价本章难点本章难点: : 对数据结构的理解对数据结构的理解 算法时间复杂度的分析算法时间复杂度的分析1.1 数据结构的兴起和发展数据结构的兴起和发展1

7、.2 数据结构的研究对象数据结构的研究对象 1.3 数据结构的基本概念数据结构的基本概念1.4 算法和算法分析算法和算法分析 第一章第一章 绪绪 论论1938年出生，年出生，25岁毕业于加州理工岁毕业于加州理工学院数学系，博士毕业后留校任教，学院数学系，博士毕业后留校任教，28岁任副教授。岁任副教授。30岁时，加盟斯坦岁时，加盟斯坦福大学计算机系，任教授。从福大学计算机系，任教授。从31岁岁起，开始出版他的历史性经典巨著：起，开始出版他的历史性经典巨著：The Art of Computer Programming他计划共写他计划共写7卷，然而出版三卷之后，卷，然而出版三卷之后，已震惊世界，使

8、他获得计算机科学已震惊世界，使他获得计算机科学界的最高荣誉图灵奖，此时，他年界的最高荣誉图灵奖，此时，他年仅仅36岁。岁。数据结构的创始人数据结构的创始人克努思克努思http:/ 1.1 数据结构的兴起和发展数据结构的兴起和发展 数据结构随着程序设计的发展而发展数据结构随着程序设计的发展而发展 数据结构的发展并未终结数据结构的发展并未终结1. 无结构阶段无结构阶段2. 结构化阶段：数据结构算法程序结构化阶段：数据结构算法程序3. 面向对象阶段：面向对象阶段： （数据结构算法）程序（数据结构算法）程序1.1 数据结构的兴起和发展数据结构的兴起和发展 1.2 数据结构的研究对象数据结构的研究对象

9、计算机求解问题计算机求解问题: 问题问题 抽象出问题的模型抽象出问题的模型 求模型的解求模型的解 问题问题数值问题数值问题数学方程数学方程 非数值问题非数值问题数据结构数据结构例例1 学籍管理问题学籍管理问题表结构表结构学号学号姓名姓名性别性别出生日期出生日期政治面貌政治面貌0001王王 军军男男1983/09/02团员团员0002李李 明明男男1982/12/25党员党员0003汤晓影汤晓影女女1984/03/26团员团员完成什么功能完成什么功能?各表项之间是什么关系？各表项之间是什么关系？1.2 数据结构的研究对象数据结构的研究对象例例2 人机对弈问题人机对弈问题树结构树结构如何实现对弈如

10、何实现对弈?各格局之间是什么关系？各格局之间是什么关系？.1.2 数据结构的研究对象数据结构的研究对象例例3 教学计划编排问题教学计划编排问题图结构图结构C4, C5, C6数据库原理数据库原理C7C2, C4计算机原理计算机原理C6C3, C4数据结构数据结构C5C1, C2程序设计程序设计C4C1离散数学离散数学C3无无计算机导论计算机导论C2无无高等数学高等数学C1先修课先修课课程名称课程名称编号编号C1C2C3C4C6C5C7如何表示课程之间的先修关系？如何表示课程之间的先修关系？1.2 数据结构的研究对象数据结构的研究对象 数据结构是研究数据结构是研究非数值非数值问题中计问题中计算机

11、的算机的操作对象操作对象以及它们之间的以及它们之间的关系关系和和操作操作的学科。的学科。1.2 数据结构的研究对象数据结构的研究对象1.1.数据数据2.2.数据元素数据元素3.3.数据项数据项4.4.数据对象数据对象5.5.数据结构数据结构6.6.抽象数据类型抽象数据类型 1.3 1.3 数据结构的基本概念数据结构的基本概念1.1.数据数据 能被输入计算机且能被能被输入计算机且能被计算机处理计算机处理的一切的一切对象。是信息的载体，是客观事物的对象。是信息的载体，是客观事物的符号符号表示。表示。数据有两大类：数据有两大类：数值数据：整数、实数等数值数据：整数、实数等非数据数据：图形、图像、声音

12、、文字等非数据数据：图形、图像、声音、文字等数值计算数值计算非数值计算非数值计算1.3 1.3 数据结构的基本概念数据结构的基本概念2.2.数据元素数据元素 是是数据数据这个集合中的一个个体。这个集合中的一个个体。 是现实世界中某是现实世界中某独立实体独立实体的数据描述。的数据描述。在计算在计算机程序中通常作为一个机程序中通常作为一个整体整体进行考虑和处理。进行考虑和处理。数数据结构讨论的据结构讨论的基本单位基本单位，一般由若干，一般由若干数据项数据项组成。组成。有时称为有时称为结点结点、记录或表目。、记录或表目。1.3 1.3 数据结构的基本概念数据结构的基本概念3.3.数据项数据项 具有独

13、立意义的具有独立意义的最小数据单位最小数据单位，是对数据元素，是对数据元素 属性的描述属性的描述。 有时称有时称域或字段域或字段。 学学 号号 姓姓 名名 性性别别 籍籍 贯贯 出出生生年年月月 1 98131 刘刘激激扬扬 男男 北北 京京 1979.12 2 98164 衣衣春春生生 男男 青青 岛岛 1979.07 3 98165 卢卢声声凯凯 男男 天天 津津 1981.02 4 98182 袁袁秋秋慧慧 女女 广广 州州 1980.10 5 98224 洪洪 伟伟 男男 太太 原原 1981.01 6 98236 熊熊南南燕燕 女女 苏苏 州州 1980.03 7 98297 宫宫

14、力力 男男 北北 京京 1981.01 8 98310 蔡蔡晓晓莉莉 女女 昆昆 明明 1981.02 9 98318 陈陈 健健 男男 杭杭 州州 1979.12数据元素数据项1.3 1.3 数据结构的基本概念数据结构的基本概念 数据、数据元素、数据项之间是包含关系：数据、数据元素、数据项之间是包含关系： 数据项数据项 数据元素数据元素 数据。数据。 组成组成组成组成1.3 1.3 数据结构的基本概念数据结构的基本概念 数据元素数据元素是讨论数据结构时涉及的最小数据单位，是讨论数据结构时涉及的最小数据单位，其中的数据项一般不予考虑。其中的数据项一般不予考虑。 4.4.数据对象数据对象 具有具

15、有相同特征相同特征的数据元素的集合。数据的的数据元素的集合。数据的子集。子集。例如：例如： 数据集合数据集合D=0,1,A,B,Z 则：数据对象正整数则：数据对象正整数N=0,1, 数据对象字母数据对象字母C=A,B,Z 数据元素是数据的一个个体，数据元素是数据的一个个体，0,1,A,B 数据对象是数据的一个子集，数据对象是数据的一个子集，N，C1.3 1.3 数据结构的基本概念数据结构的基本概念5.5.数据结构数据结构 相互之间存在一种或多种特定相互之间存在一种或多种特定关系关系的数据元素的数据元素的集合的集合。1.3 1.3 数据结构的基本概念数据结构的基本概念数据的逻辑结构是从具体问题抽

16、象出来的数据的逻辑结构是从具体问题抽象出来的数据模型数据模型学籍管理问题中，表项之间的逻辑关系指的是什么？学籍管理问题中，表项之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？人机对弈问题中，格局之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？教学计划编排问题中，课程之间的逻辑关系指的是什么？1.3 1.3 数据结构的基本概念数据结构的基本概念按照视点的不同，数据结构分为按照视点的不同，数据结构分为逻辑结构逻辑结构和和存储结构存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。按照视点的不同，数据结构分为按

17、照视点的不同，数据结构分为逻辑结构逻辑结构和和存储结构存储结构。逻辑结构：指数据元素之间逻辑结构：指数据元素之间逻辑关系逻辑关系的整体。的整体。存储结构：又称为物理结构，是数据及其逻辑结构在存储结构：又称为物理结构，是数据及其逻辑结构在计算机计算机中的表示中的表示。存储结构实质上是内存分配，存储结构实质上是内存分配，在具体实现时，依赖于计算机语言。在具体实现时，依赖于计算机语言。1.3 1.3 数据结构的基本概念数据结构的基本概念1.3 1.3 数据结构的基本概念数据结构的基本概念 数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个

18、集合属于同一个集合” ；1.3 1.3 数据结构的基本概念数据结构的基本概念 数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系；1.3 1.3 数据结构的基本概念数据结构的基本概念 数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树

19、结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系； 数据结构从逻辑上分为四类：数据结构从逻辑上分为四类： 集合：数据元素之间就是集合：数据元素之间就是 “属于同一个集合属于同一个集合” ； 线性结构：数据元素之间线性结构：数据元素之间 存在着一对一的线性关系；存在着一对一的线性关系； 树结构：数据元素之间存在树结构：数据元素之间存在 着一对多的层次关系；着一对多的层次关系； 图结构：数据元素之间存在图结构：数据元素之间存在 着多对多的任意关系。着多对多的任意关系。1.3 1.3 数据结构的基本概念数据结构的基本概念batcateat起始地址起始地址例：（例

20、：（bat, cat, eat）1.3 1.3 数据结构的基本概念数据结构的基本概念 通常有两种存储结构：通常有两种存储结构：(1)(1)顺顺序存储结构序存储结构：用一组：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元素数据元素之间的逻辑关系由元素的的存储位置存储位置来表示。来表示。 通常有两种存储结构：通常有两种存储结构：(1)(1)顺序存储结构：用一组顺序存储结构：用一组连续连续的存储单元的存储单元依次依次存储数据元素，存储数据元素，数据元素之间的逻辑关系由元素数据元素之间的逻辑关系由元素的的存储位置存储位置来表示。来表示。(2) (2)

21、链接存储结构：用一组链接存储结构：用一组任意任意的存储单元存储数据元素，数据的存储单元存储数据元素，数据元素之间的逻辑关系用元素之间的逻辑关系用指针指针来表来表示示例：（例：（bat, cat, eat）0200020803000325 bat0200 cat0325 eat 1.3 1.3 数据结构的基本概念数据结构的基本概念 逻辑结构和存储结构之间的关系逻辑结构和存储结构之间的关系 数据的逻辑结构属于用户视图，是数据的逻辑结构属于用户视图，是面向问题面向问题的，反的，反映了数据内部的构成方式；数据的存储结构属于具映了数据内部的构成方式；数据的存储结构属于具体实现的视图，是体实现的视图，是面

22、向计算机面向计算机的。的。 一种数据的逻辑结构可以用多种存储结构来存储，一种数据的逻辑结构可以用多种存储结构来存储，而采用不同的存储结构，其数据处理的效率往往是而采用不同的存储结构，其数据处理的效率往往是不同的。不同的。 1.3 1.3 数据结构的基本概念数据结构的基本概念6.6.抽象数据类型抽象数据类型(1)(1)数据类型数据类型 数据类型是一个数据类型是一个值的集合值的集合和定义在这个值集上的一和定义在这个值集上的一组组操作操作的总称。的总称。 数据类型是数据类型是数据存储数据存储和和操作操作的的“封装封装” 。了解其了解其抽抽象特性象特性，如是什么类型，能进行什么操作即可。，如是什么类型

23、，能进行什么操作即可。 如：如：int、 float等等(2)(2)抽象抽象 抽出问题本质的特征而忽略非本质的细节，是对具抽出问题本质的特征而忽略非本质的细节，是对具体事物的一个概括。体事物的一个概括。 如：如： 地图、驾驶汽车地图、驾驶汽车1.3 1.3 数据结构的基本概念数据结构的基本概念(3)(3)抽象数据类型（抽象数据类型（ Abstract Data Type:ADT)Abstract Data Type:ADT) 一个一个数据结构数据结构以及定义在该结构上的以及定义在该结构上的一组操作一组操作的总的总称。称。 ADT的三个不同的视图：的三个不同的视图：ADTl逻辑结构逻辑结构l操作

24、集合操作集合数据结构数据结构l存储结构存储结构l算法设计算法设计类类使用视图使用视图设计视图设计视图实现视图实现视图 成员变量成员变量 成员函数成员函数ADT的定义的定义 ADT的设计的设计 ADT的实现的实现1.3 1.3 数据结构的基本概念数据结构的基本概念定义格式：定义格式：ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象： 数据关系：数据关系： 基本操作：基本操作： （相当于声明若干函数（相当于声明若干函数) ) ADT ADT抽象数据类型名抽象数据类型名 抽象数据类型的描述抽象数据类型的描述抽象数据类型定义用三元组表示：抽象数据类型定义用三元组表示：（D D，S S，

25、P P），）， 其中，其中，D D是数据对象，是数据对象， S S是是D D上的关系集，上的关系集， P P是对是对D D的基本操作集。的基本操作集。1.3 1.3 数据结构的基本概念数据结构的基本概念 如：如：ADT ListADT List 数据对象：数据对象：D=aD=ai i|a|ai iElemSet, i=1,2,3,ElemSet, i=1,2,3,n,n0,n,n0 数据关系：数据关系：R1=aR1=|a|ai-1i-1,a,ai iD,i=2,D,i=2,nn 基本操作：基本操作： InitList(&L)InitList(&L)要点：要点： 操作结果：构造一

26、个空的线性表操作结果：构造一个空的线性表L L。 ListLength(L)ListLength(L) 初始条件：线性表初始条件：线性表L L已存在。已存在。 操作结果：返回操作结果：返回L L中数据元素个数中数据元素个数( (线性表的长度线性表的长度) ) ListInsert(&L,i,e) ListInsert(&L,i,e) 初始条件：线性表初始条件：线性表L L已存在，已存在，1iListLength(L)+11iListLength(L)+1 操作结果：在操作结果：在L L中第中第I I个位置之前插入新的数据元素个位置之前插入新的数据元素e e，L L的的 长度加长

27、度加1 1。 1.3 1.3 数据结构的基本概念数据结构的基本概念对数据结构设置的操作集合，实现各对数据结构设置的操作集合，实现各种应用对数据的各种访问种应用对数据的各种访问 总结总结(1)ADT(1)ADT可理解为对数据类型的进一步抽象可理解为对数据类型的进一步抽象(2)(2)数据类型和数据类型和ADTADT的区别：的区别： 数据类型数据类型指的是高级程序设计语言支持的基本数据类型指的是高级程序设计语言支持的基本数据类型 ADTADT指的是指的是自定义的数据类型自定义的数据类型(3)ADT=(3)ADT=数据结构数据结构 + + 一组一组基本操作基本操作 1.2 数据结构的基本概念数据结构的

28、基本概念 用标准用标准C C语言表示和实现语言表示和实现ADTADT描述时，主要包括以下两描述时，主要包括以下两个方面个方面: : (1) (1) 通过结构体将通过结构体将intint、 floatfloat等固有类型组合到一起等固有类型组合到一起, , 构成一个结构类型构成一个结构类型, , 再用再用typedeftypedef为该类型或该类型指针为该类型或该类型指针重新起一个名字。重新起一个名字。 (2) (2) 用用C C语言函数实现各操作。语言函数实现各操作。 数据的操作：插入、删除、修改、检索、排序等数据的操作：插入、删除、修改、检索、排序等 数据的逻辑结构数据的逻辑结构 数据的存储

29、结构数据的存储结构 顺序存储顺序存储链式存储链式存储集合集合线性结构线性结构树结构树结构图结构图结构 非数值问题非数值问题 数数据据表表示示小结小结1.3 1.3 数据结构的基本概念数据结构的基本概念 n数据结构主要研究内容：数据结构主要研究内容： u数据的各种逻辑结构和存储结构，以及它们数据的各种逻辑结构和存储结构，以及它们之间的相应关系之间的相应关系u并对每种结构定义相应的各种运算并对每种结构定义相应的各种运算u设计出相应的算法设计出相应的算法u分析算法的效率分析算法的效率1.3 1.3 数据结构的基本概念数据结构的基本概念1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法二、算

30、法描述二、算法描述三、算法分析三、算法分析一、算法一、算法 算法算法是对特定问题是对特定问题求解步骤求解步骤的一种描述，的一种描述，是一个有限的指令集或指令的有限序列是一个有限的指令集或指令的有限序列。 1. 1. 算法（算法（AlgorithmAlgorithm）的定义）的定义1.4 1.4 算法和算法分析算法和算法分析2. 2. 算法的特性算法的特性 有限性有限性：有限步骤之内正常结束，：有限步骤之内正常结束， 不能形成无不能形成无穷循环。穷循环。 确定性确定性： 算法中的每一个步骤必须有确定含义，算法中的每一个步骤必须有确定含义， 无二义性。无二义性。 (3)(3)可行性可行性： 原则上

31、能精确进行，原则上能精确进行， 操作可通过已操作可通过已实现的基本运算执行有限次而完成。实现的基本运算执行有限次而完成。(4)(4)输入输入： 有多个或有多个或0 0个输入。个输入。 (5)(5)输出输出： 至少有一个或多个输出。至少有一个或多个输出。一、算法一、算法1.4 1.4 算法和算法分析算法和算法分析 算法是解决问题的一种方法或一个过程，考虑如何将算法是解决问题的一种方法或一个过程，考虑如何将输入转换输出，一个问题可以有多种算法。输入转换输出，一个问题可以有多种算法。 程序是用某种程序设计语言对算法的具体实现。程序是用某种程序设计语言对算法的具体实现。 主要区别体现在有穷性、正确性和

32、描述方法：主要区别体现在有穷性、正确性和描述方法：(1)程序可以是无穷的，例如：程序可以是无穷的，例如：OS，算法是有穷的；，算法是有穷的；(2)程序可以是错误的，算法必须是正确的；程序可以是错误的，算法必须是正确的；(3)程序是用程序设计语言描述的，在机器上可以执行；程序是用程序设计语言描述的，在机器上可以执行； 算法可以用多种方式描述。算法可以用多种方式描述。3. 3. 算法与程序的区别算法与程序的区别 1.4 1.4 算法和算法分析算法和算法分析一、算法一、算法 欧几里德算法mnr例：求两个自然数例：求两个自然数 m 和和 n 的最大公的最大公约数。约数。 欧几里德算法欧几里德算法辗转相

33、除法辗转相除法1.4 1.4 算法和算法分析算法和算法分析二、算法的描述二、算法的描述自然语言自然语言流程图流程图程序设计语言程序设计语言伪代码伪代码1.4 1.4 算法和算法分析算法和算法分析 输入输入m 和和n； 求求m除以除以n的余数的余数r； 若若r等于等于0 0，则，则n为最大公约数，为最大公约数，算法结束；否则执行第算法结束；否则执行第步；步； 将将n的值放在的值放在m中，将中，将r的值放的值放在在n中；中； 重新执行第重新执行第步。步。例：欧几里德算法例：欧几里德算法自然语言1.4 1.4 算法和算法分析算法和算法分析N开始输入m和n r=m % nr=0m=n；n=r 输出n结

34、束Y流 程 图例：欧几里德算法例：欧几里德算法1.4 1.4 算法和算法分析算法和算法分析#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 1.4 算法和算法分析算法和算法分析 1. r = m % n; 2. 循环直到循环直到 r 等于等于0 2.1 m = n; 2.2 n = r; 2.3 r = m % n; 3.

35、输出输出 n ;伪 代 码例：欧几里德算法例：欧几里德算法1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析设计算法时，通常应考虑达到以下目标：设计算法时，通常应考虑达到以下目标：1.1.正确性正确性2.2.可读性可读性3.3.健壮性健壮性4.4.高效率与低存储量的需求高效率与低存储量的需求1.4 1.4 算法和算法分析算法和算法分析例：八枚硬币中有一枚重，现有一个天秤例：八枚硬币中有一枚重，现有一个天秤 怎样选出？怎样选出？方法一：方法一：1-2、3-4、5-6、7-8最好秤最好秤1 1次，最坏秤次，最坏秤4 4次次方法二：方法二：8/2、4/2、2/23 3次一定能选出次

36、一定能选出方法三：方法三：6/2，若平：，若平：2/2 否则：否则：2/22 2次一定能选出次一定能选出1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析 算法分析算法分析：对算法所需要的计算机资源：对算法所需要的计算机资源时间时间和和空间空间进行估算。进行估算。 时间复杂性（时间复杂性（Time Complexity） 空间复杂性（空间复杂性（Space Complexity）三、算法分析三、算法分析1.4 1.4 算法和算法分析算法和算法分析 算法分析的目：算法分析的目：改进算法改进算法提高算法的时间效提高算法的时间效率和空间效率。率和空间效率。 度量算法效率的方法：度量

37、算法效率的方法：事后统计事后统计：将算法实现，测算其时间和空间开销。：将算法实现，测算其时间和空间开销。 事前分析事前分析：对算法所消耗资源的一种估算方法。：对算法所消耗资源的一种估算方法。1.1.算法的时间复杂度算法的时间复杂度算法的算法的执行时间执行时间每条语句执行时间之和每条语句执行时间之和执行次数执行次数执行一次的时间执行一次的时间指令系统、编译的代码质量指令系统、编译的代码质量单位时间单位时间每条语句每条语句执行次数执行次数之和之和基本语句基本语句的执行次数的执行次数1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析基本语句：基本语句：是执行次数与是执行次数与整个算

38、法的执行次整个算法的执行次数成数成 正比的操作指令。正比的操作指令。问题规模：问题规模：输入量的多少。输入量的多少。for (i=1; i=n; i+) for (j=1; j=n; j+) x+;问题规模：n基本语句：x+三、算法分析三、算法分析1.4 1.4 算法和算法分析算法和算法分析void MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) Cij = 0; for ( int k = 0; k 时，把时间复杂度的数量级（阶）时，把时间复杂

39、度的数量级（阶）称为算法的称为算法的渐进时间复杂度渐进时间复杂度 T(n) = O(f(n)1.4 1.4 算法和算法分析算法和算法分析2.2.大大O表示表示 定义定义 若存在两个正的常数若存在两个正的常数c和和n0，对于任意，对于任意nn0，都有，都有T( (n)cf( (n) )，则称，则称T( (n) )=O( (f( (n)n0问题规模问题规模n执执行行次次数数n0之前的之前的情况无关情况无关紧要紧要T( (n) )cf f(n nv当问题规模充分大时在渐近意义下的阶当问题规模充分大时在渐近意义下的阶1.4 1.4 算法和算法分析算法和算法分析 定理：若定理：若A(n)=amnm+am

40、-1nm-1+a1n+a0是一个是一个m次多项式，则次多项式，则A(n)=O(nm)。说明：在计算算法时间复杂度时，可以忽略所有说明：在计算算法时间复杂度时，可以忽略所有低次幂和最高次幂的系数。低次幂和最高次幂的系数。1.4 1.4 算法和算法分析算法和算法分析 用大用大O表示评估算法的复杂性，得到的只是表示评估算法的复杂性，得到的只是当当规模充分大规模充分大时的一个时的一个上界，上界，这个上界的这个上界的阶越低阶越低，则评估就则评估就越精确越精确，结果就越有价值。，结果就越有价值。f(n) = 2n3 + 2n2 + 2n +1T(n)=O(f(n)=O(n3) 常见时间复杂度常见时间复杂度

41、（按数量级递增排列）（按数量级递增排列） (1)、log2n) 、 n)、nlog2n)、 n2)、n3 )、 O 2n )、 3n)1.4 1.4 算法和算法分析算法和算法分析三、算法分析三、算法分析n例：设有两个算法在同一机器上运行，其执行例：设有两个算法在同一机器上运行，其执行时间分别为时间分别为 100n2 和和 2n，问：要使前者快于，问：要使前者快于后者，后者，n 至少要取多大？至少要取多大？ 解答：解答： 问题是找出满足问题是找出满足 100n2 2n = 8192 n = 14时，时，100n2 = 19600 2n = 16384 n = 15时，时，100n2 = 2250

42、0 2n = 32764 取取 n = 15 满足要求。满足要求。1.4 1.4 算法和算法分析算法和算法分析 n算法在运行过程中附加的辅助存储空间，与算法有关算法在运行过程中附加的辅助存储空间，与算法有关 空间复杂度是对算法执行过程需要的辅助空空间复杂度是对算法执行过程需要的辅助空间进行度量，是问题规模的函数，间进行度量，是问题规模的函数，表示为：表示为： S(n)=O(g(n)1.4 1.4 算法和算法分析算法和算法分析3.3.空间复杂度空间复杂度三、算法分析三、算法分析本本 章章 小小 结结 数据组织的三个层次：数据、数据元素和数据项数据组织的三个层次：数据、数据元素和数据项 数据结构主

43、要研究的三方面内容：数据结构主要研究的三方面内容： （1）数据的逻辑结构）数据的逻辑结构 （线性结构和非线结构）（线性结构和非线结构） （2）数据的存储结构）数据的存储结构 （顺序方式、链式方式、（顺序方式、链式方式、索引方式和散列方式索引方式和散列方式） （3）对数据实施的基本运算）对数据实施的基本运算: 算法算法算法分析：时间性能算法分析：时间性能时间复杂度时间复杂度 空间性能空间性能空间复杂度空间复杂度绪绪 论论数据结构数据结构算算 法法基基本本概概念念逻逻辑辑结结构构存存储储结结构构数据数据数据元素数据元素数据对象数据对象ADT逻辑结构逻辑结构数据结构数据结构的分类的分类存储结构存储结构常用存储常用存储方法方法基基本本概概念念算算法法分分析析算法算法算法特性算法特性评价算法评价算法描述算法描述算法问题规模问题规模基本语句基本语句时间复杂度时间复杂度大大O记号记号关关 系系习习 题题1.( )1.( )是数据的最小单位，（是数据的最小单位，（ ）是讨论数）是讨论数据结构时涉及的最小数据单位（基本单位）。据结构时涉及的最小数据单位（基本单位）。2.2.顺序存储结构中数据元素之间的逻辑关系由（顺序存储结构中数据元素之间的逻辑关系由（ ) )表表示的，链式存储结构中的数