数据结构绪论课件

中山大学1学习学习的意义：的意义：n数据结构是计算机及相关专业中一门重要的专业基础课程。n数据的表示及数据的处理是用计算机来解决实际问题时，首要涉及的主要问题，而数据表示及数据处理正是数据结构课程的主要研究对象。n数据结构是后续专业课程（操作系统等）的基础，为软件方面的课程打下了厚实的知识基础，同时也提供了必要的技能训练。中山大学1学习的意义：数据结构是计算机及相关专业1中山大学2学习学习的要求：的要求：n在基础方面，要求学生掌握常用数据结构的基本概念及其不同的实现方法；n在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。中山大学2学习的要求：在基础方面，要求学生掌握常2中山大学3本课程讲述的主要内容本课程讲述的主要内容 本课程将分别讲述数据结构的基本概念、线性表、栈和队列、串和数组、树形结构、图结构、查找、排序和文件等内容。中山大学3本课程讲述的主要内容 本课程将分别讲3中山大学4学习本课程的基本方法学习本课程的基本方法n上课认真听讲；n仔细阅读教材中的大量例题，从而体会并最终掌握数据结构中的基本概念；n独立完成每个章节后面的练习题；n多上机实验多上机实验，用程序验证算法的正确性。在实践中体会构造性思维的方法，掌握数据组织与程序设计的技术。中山大学4学习本课程的基本方法上课认真听讲；4中山大学5第一章第一章 绪论绪论1.1 数据结构研究的主要内容数据结构研究的主要内容；1.2 基本概念基本概念；1.3 算法和算法的衡量；算法和算法的衡量；中山大学5第一章 绪论1.1 数据结构研究的主要内容；5中山大学6 n早期计算机应用的特点：数值计算的程序设计问题。结构应力分析计算：结构应力分析计算：线性代数方程组线性代数方程组 全球天气预报：全球天气预报：环流模式方程环流模式方程1.1数据结构研究的主要内容数据结构研究的主要内容中山大学6早期计算机应用的特点：数值计算的程序设计问题。1.6中山大学71.11.1数据结构研究的主要内容数据结构研究的主要内容n当今计算机应用的特点：1、所处理的数据量大且具有一定的关系；2、对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。中山大学71.1数据结构研究的主要内容当今计算机应用的特点：7中山大学8应用举例1学籍档案管理n假设一个学籍档案管理系统应包含如下表1-1所示的学生信息。中山大学8应用举例1学籍档案管理假设一个学籍档案管理系统8中山大学9应用举例1学籍档案管理n 特点：n每个学生的信息占据一行，所有学生的信息按学号顺序依次排列构成一张表格；n表中每个学生的信息依据学号的大小存在着一种前后关系，这就是我们所说的线性结构；n对它的操作通常是插入某个学生的信息，删除某个学生的信息，更新某个学生的信息，按条件检索某个学生的信息等等。中山大学9应用举例1学籍档案管理 特点：9中山大学10应用举例2制定教学计划n在制定教学计划时，需要考虑各门课程的开设顺序。有些课程需要先导课程，有些课程则不需要，而有些课程又是其他课程的先导课程。比如，计算机专业课程的开设情况如下表1-2所示：中山大学10应用举例2制定教学计划在制定教学计划时，需要10中山大学11应用举例2制定教学计划c1c9c4c2c12c10c11c5c3c6c7c8图图图图 1-2 1-2 计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系计算机专业必修课程开设先后关系中山大学11应用举例2制定教学计划c1c9c4c2c1211中山大学12应用举例2制定教学计划n特点：1、课程之间的先后关系用图结构描述；2、通过实施创建图结构，按要求将图 结构中的顶点进行线性排序。中山大学12应用举例2制定教学计划特点：12n 在八皇后问题中，处理过程不是根据某种确定的计算法则，而是利用试探和回溯的探索技术求解。为了求得合理布局，在计算机中要存储布局的当前状态。从最初的布局状态开始，一步步地进行试探，每试探一步形成一个新的状态，整个试探过程形成了一棵隐含的状态树。如图1.2所示（为了描述方便，将八皇后问题简化为四皇后问题）。回溯法求解过程实质上就是一个遍历状态树的过程。在这个问题中所出现的树也是一种数据结构，它可以应用在许多非数值计算的问题中。应用举例3八皇后问题 在八皇后问题中，处理过程不是根据某种确定的计算法则，而是13中山大学14结论结论n由以上三个例子可见，由以上三个例子可见，描述这类非数值计算问描述这类非数值计算问题的数学模型不是数学方程，而是表、图和题的数学模型不是数学方程，而是表、图和树之类的数据结构。树之类的数据结构。n因此从广义上讲，因此从广义上讲，数据结构描述现实世界实体数据结构描述现实世界实体的数学模型及其上的操作在计算机中的表示的数学模型及其上的操作在计算机中的表示和实现。和实现。n学习数据结构的目的学习数据结构的目的是为了了解计算机处理对是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象象的特性，将实际问题中所涉及的处理对象在计算机中在计算机中表示出来表示出来并对它们并对它们进行处理进行处理。与。与此同时，通过算法训练来提高学生的思维能此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。综合应用能力和专业素质的提高。中山大学14结论由以上三个例子可见，描述这类非数值计算问题的14中山大学151.2.1.2.基本概念基本概念一、数据和数据结构；一、数据和数据结构；二、数据类型；二、数据类型；三、抽象数据类型三、抽象数据类型ADT；中山大学151.2.基本概念一、数据和数据结构；15中山大学16一、数据和数据结构一、数据和数据结构1、数据的定义数据的定义:n定义一：数据是客观事物的符号表示。例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。中山大学16一、数据和数据结构1、数据的定义:例：张三的C语16中山大学17一、数据和数据结构一、数据和数据结构n定义二：能输入到计算机中并被计算机程序处理的符号的总称。例：图像、声音等。n总结总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。中山大学17一、数据和数据结构定义二：能输入到计算机中并被计17中山大学182、数据元素和数据项数据元素和数据项:n数据的数据的基本单位基本单位。在计算机程序中常作为一个。在计算机程序中常作为一个整体进行考虑和处理。整体进行考虑和处理。n有时一个有时一个数据元素数据元素可以由若干可以由若干数据项数据项(Data(Data Item)Item)组成。组成。n数据元素又称为元素、结点、记录。数据元素又称为元素、结点、记录。一、数据和数据结构一、数据和数据结构中山大学182、数据元素和数据项:一、数据和数据结构18中山大学19一、数据和数据结构一、数据和数据结构有两类数据元素有两类数据元素:n一类是不可分割的一类是不可分割的“原子原子”型数据元素，如整数型数据元素，如整数“3”“3”，字符，字符”N”N”等；等；n一类是由多个款项构成的数据元素，其中每个款一类是由多个款项构成的数据元素，其中每个款项称为项称为“数据项数据项”。例如描述一个学生的信息的。例如描述一个学生的信息的数据元素可由下列数据元素可由下列6 6个数据项组成。其中的出身个数据项组成。其中的出身日期又可以由三个数据项：日期又可以由三个数据项：年年、月月 和和 日日 组组成，则称成，则称 出身日期出身日期 为为 组合项组合项，而其它不可分，而其它不可分割的数据项为割的数据项为 原子项原子项。中山大学19一、数据和数据结构有两类数据元素:19中山大学20一、数据和数据结构一、数据和数据结构数据项数据项是具有是具有独立独立含义的含义的最小标识单位最小标识单位，数据元素，数据元素是数据项的集合。是数据项的集合。关键字：关键字：指的是能识别一个或多个数据元素的数据项。若指的是能识别一个或多个数据元素的数据项。若能起唯一识别作用，则称之为能起唯一识别作用，则称之为“主主”关键字，否则称之关键字，否则称之为为 次次 关键字。关键字。中山大学20一、数据和数据结构数据项是具有独立含义的最小标识20中山大学213、数据对象：具有相同性质的数据元素的集合。是数据的具有相同性质的数据元素的集合。是数据的一个一个子集。n整数数据对象：整数数据对象：N=0,N=0,1,1,2,2,n字母字符数据对象：字母字符数据对象：C=A,B,C,C=A,B,C,FF n一个班级的成绩表可以看作一个数据对象。一个班级的成绩表可以看作一个数据对象。一、数据和数据结构一、数据和数据结构中山大学213、数据对象：一、数据和数据结构21中山大学224、数据结构：、数据结构：若在特性相同的数据元素集合中的数据元素之间存在一种或多种特定的关系，则称该数据元素的集合为“数据结构”，换句话说，数据结构是带“结构”的数据元素的集合。“结构”即指数据元素之间存在的关系。一、数据和数据结构一、数据和数据结构中山大学224、数据结构：一、数据和数据结构22中山大学23例1:在2行3列的数组 a1,a2,a3,a4,a5,a6中6个元素 之间存在两个关系:a1,a3,a5 a1,a2,a3 a2,a4,a6 a4,a5,a6 行的次序关系:row=,列的次序关系:col=,一、数据和数据结构一、数据和数据结构中山大学23例1:在2行3列的数组 a1,a2,a3,23中山大学24例2:一维数组 a1,a2,a3,a4,a5,a6中存在次序关系:|i=1,2,3,4,5 不同的关系构成不同的结构，所以说数据结构是带有结构的数据元素的集合。一、数据和数据结构一、数据和数据结构中山大学24例2:一维数组 a1,a2,a3,a4,24中山大学25数据结构的形式定义为：数据结构是一个二元组，一个二元组，数据结构可描述为 Data_Structures=（D，S）有限个数据元有限个数据元素的集合素的集合有限个结点间有限个结点间关系的集合关系的集合一、数据和数据结构一、数据和数据结构其中，D是数据元素的有限数据元素的有限集，S是D D上关系的有限集。中山大学25数据结构的形式定义为：数据结构是一个二元组，数25中山大学26数据的逻辑结构数据的逻辑结构n 从逻辑关系上描述数据，与数据的存储无关；从逻辑关系上描述数据，与数据的存储无关；n 从具体问题抽象出来的数据模型；从具体问题抽象出来的数据模型；n 与数据元素本身的形式、内容无关；与数据元素本身的形式、内容无关；一、数据和数据结构一、数据和数据结构中山大学26数据的逻辑结构一、数据和数据结构26中山大学27数据的数据的逻辑结构逻辑结构可归结为以下四类可归结为以下四类:1.集合：元素间为松散的关系。结构中的数据元素除了同属于一种类型外，别无其它关系;一、数据和数据结构一、数据和数据结构中山大学27数据的逻辑结构可归结为以下四类:一、数据和数据27中山大学282.线性结构：结构中的数据元素之间为严格的一对一关系。86胡孝臣986110395刘忠赏9861107100张卓9861109成绩姓名学号一、数据和数据结构一、数据和数据结构中山大学282.线性结构：结构中的数据元素之间为严格的一对一28中山大学293.树形结构：结构中的数据元素之间为严格的一对多关系。一、数据和数据结构一、数据和数据结构中山大学293.树形结构：结构中的数据元素之间为严格的一对多29中山大学304.图状结构或网状结构：结构中的数据元素之间为多对多关系。一、数据和数据结构一、数据和数据结构中山大学304.图状结构或网状结构：结构中的数据元素之间为多30中山大学31数据的存储结构数据的存储结构u 数据结构在计算机中的表示。数据结构在计算机中的表示。u 数据的存储结构依赖于计算机语言。数据的存储结构依赖于计算机语言。顺序存储表示顺序存储表示 链接存储表示链接存储表示 索引存储表示索引存储表示 散列存储表示散列存储表示一、数据和数据结构一、数据和数据结构中山大学31数据的存储结构一、数据和数据结构31中山大学32数据的存储结构数据的存储结构 数据的逻辑结构在存储器中的数据的逻辑结构在存储器中的映象。映象。“数据元素数据元素”的映象的映象？“关系关系”的映象的映象？一、数据和数据结构一、数据和数据结构中山大学32数据的存储结构一、数据和数据结构32中山大学33数据元素的映象方法：数据元素的映象方法：用用二进制位二进制位（bit）的位串表示）的位串表示数据元素。数据元素。计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。位串。在逻辑描述中，把位串称为元素或结点结点。一、数据和数据结构一、数据和数据结构中山大学33数据元素的映象方法：用二进制位（bit）的位串表33中山大学34 当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。数据域。例：学生成绩表数据用C语言语言的结构体数组 classonestu50来存储：struct stu int stuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/char name20;int maths;int language;int c_language;classonestu50;一、数据和数据结构一、数据和数据结构中山大学34 当数据元素由若干数据项组成时，位串中34中山大学35“关系关系”的映象方法：的映象方法：（表示（表示 x,yx,y 的方法）的方法）顺序映象顺序映象：以相对的存储位置表示后继关系。：以相对的存储位置表示后继关系。例如例如:令令 y 的存储位置和的存储位置和 x 的存储位置之间差一个常量的存储位置之间差一个常量C。而而C是一个隐含值，是一个隐含值，整个存储结构中只含数据元素本整个存储结构中只含数据元素本身的信息。身的信息。一、数据和数据结构一、数据和数据结构cyx中山大学35“关系”的映象方法：一、数据和数据结构cyx35中山大学36链式映象：链式映象：以附加信息(指针)表示后继关系。以和x绑定在一起的附加信息（指针）表示后继关系，来指示y 的存储位置。一、数据和数据结构一、数据和数据结构yx中山大学36链式映象：以附加信息(指针)表示后继关系。一、数36中山大学37在不同的编程环境中，存储结构可有不同的描述方法，当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。一、数据和数据结构一、数据和数据结构中山大学37在不同的编程环境中，一、数据和数据结构37中山大学38二、二、数据类型数据类型n数据类型数据类型 定义：定义：一组性质相同的值集合以及定一组性质相同的值集合以及定义在这个值集合上的一组操作的总称义在这个值集合上的一组操作的总称。n数据类型中定义了两个集合，即该数据类型中定义了两个集合，即该 类类型的型的取值范围取值范围，该类型中可允许使用，该类型中可允许使用的的一组运算一组运算。中山大学38二、数据类型数据类型 38中山大学39n数数据据类类型型是是和和数数据据结结构构密密切切相相关关的的一一个个概概念念。它它最最早早出出现现在在高高级级程程序序设设计计语语言言中中，用以刻划程序中操作对象的特性。用以刻划程序中操作对象的特性。n高高级级语语言言中中的的数数据据类类型型就就是是已已经经实实现现的的数数据据结结构构的的实实例例。从从这这个个意意义义上上讲讲，数数据据类类型型是是高高级级语语言言中中允允许许的的变变量量种种类类，是是程程序序语语言言中中已已经经实实现现的的数数据据结结构构（即即程程序序中中允允许出现的数据形式）。许出现的数据形式）。n在在高高级级语语言言中中的的整整型型类类型型，则则它它可可能能的的取取值值范范围围是是-32768-32768到到+32767+32767之之间间，可可用用的的运运算算符符集集合合为为加加、减减、乘乘、除除、乘乘方方、取取模模（如（如C C语言中语言中+，-，*，/，%）。）。中山大学39数据类型是和数据结构密切相关的一个概念。它最早出39中山大学40二、二、数据类型数据类型在高级程序设计语言中，数据类型可分为两类：在高级程序设计语言中，数据类型可分为两类：数据类型封装了数据类型封装了数据存储数据存储与与操作操作的具体细节的具体细节 中山大学40二、数据类型在高级程序设计语言中，数据类型可分为40中山大学41三、三、抽象数据类型抽象数据类型n抽象数据类型(Abstract Data Type 简称ADT)定义了一个数据对象，数据对象间各元素间的结构关系，以及一组处理数据的操作。n抽象数据类型的最重要特点是：数据抽象信息隐藏。中山大学41三、抽象数据类型抽象数据类型(Abstract 41中山大学42三、三、抽象数据类型抽象数据类型n数据抽象：抽象的本质是抽取反映问题的本质点，忽视非本质的细节，从而使设计的数据结构更具有一般性，可以解决一类问题。n信息隐藏：对用户隐藏数据存储和操作实现的细节，使用者仅需了解操作或界面服务，通过使用界面服务来访问数据。中山大学42三、抽象数据类型数据抽象：42中山大学43三、三、抽象数据类型抽象数据类型nADT 包括定义和实现两方面，其中定义是独立独立于实现的。n定义：ADT定义该抽象数据类型需要包含哪些信息，并根据功能确定公共界面的服务，使用者可以使用公共界面中的服务对该抽象数据类型进行操作。n实现：ADT实现作为私有部分封装在其实现模块内，使用者不能看到，也不能直接操作该数据类型所存储的数据，只有通过界面中的服务来访问这些数据。中山大学43三、抽象数据类型ADT 包括定义和实现两方面，其43中山大学44三、三、抽象数据类型抽象数据类型抽象数据类型的描述抽象数据类型的描述n抽象数据类型可用（抽象数据类型可用（D D，S S，P P）三元组表示）三元组表示其其中中，D D是是数数据据对对象象，S S是是D D上上的的关关系系集集，P P是是对对D D的基本操作集。的基本操作集。ADT ADT 抽象数据类型名抽象数据类型名 数据对象：数据对象：数据对象的定义数据对象的定义 数据关系：数据关系：数据关系的定义数据关系的定义 基本操作：基本操作：基本操作的定义基本操作的定义 ADT ADT 抽象数据类型名抽象数据类型名中山大学44三、抽象数据类型抽象数据类型的描述44其中其中,数据对象、数据关系用伪码描述；基本操作定义格数据对象、数据关系用伪码描述；基本操作定义格式为：式为：基本操作名（参数表）基本操作名（参数表）初始条件：初始条件描述初始条件：初始条件描述操作结果：操作结果描述操作结果：操作结果描述n基基本本操操作作有有两两种种参参数数：赋赋值值参参数数只只为为操操作作提提供供输输入入值值；引引用用参参数数以以&打打头头，除除可可提提供供输输入入值值外外，还还将将返返回回操操作作结果。结果。n“初初始始条条件件”描描述述了了操操作作执执行行之之前前数数据据结结构构和和参参数数应应满满足足的的条条件件，若若不不满满足足，则则操操作作失失败败，并并返返回回相相应应出出错信息。错信息。n“操操作作结结果果”说说明明了了操操作作正正常常完完成成之之后后，数数据据结结构构的的变变化化状状况况和和应应返返回回的的结结果果。若若初初始始条条件件为为空空，则则省省略略之。之。其中,数据对象、数据关系用伪码描述；基本操作定义格45中山大学46例：抽象数据类型复数的数据结构定义如下：ADT Complex 数据对象：D=e1，e2|e1，e2属于实数集 数据关系：S|e1是复数的实数 部分，e2是复数的虚数部分 三、抽象数据类型三、抽象数据类型中山大学46例：抽象数据类型复数的数据结构定义如下：三、抽46中山大学47基本操作：基本操作：InitComplex（&Z，v1，v2）操作结果：构造复数Z，其实部和虚部分别被赋予参数v1，v2的值。DestroyComplex（&Z）操作结果：复数Z被销毁。GetReal（Z，&realPart）初始条件：复数Z已存在。操作结果：用realPart返回复数Z的实数部分值。三、抽象数据类型三、抽象数据类型中山大学47基本操作：三、抽象数据类型47中山大学48GetImage（Z，&ImagePart）：初始条件：复数Z已存在。操作结果：用RealPart返回复数Z的虚数部分值。Add（Z1，Z2，&Sum）：初始条件：Z1，Z2是复数。操作结果：用Sum返回两个复数Z1，Z2 的和值。ADT Complex三、抽象数据类型三、抽象数据类型中山大学48GetImage（Z，&ImagePart 48中山大学491.3 1.3 算法和算法的衡量算法和算法的衡量n定义：算法是为了解决某类问题而规定的一个有限长的操作序列。n计算机对数据的操作可以分为数值性和非数值性两种类型。在数值性操作中主要进行的是算术运算；而在非数值性操作中主要进行的是检索、排序、插入、删除等等。中山大学491.3 算法和算法的衡量定义：算法是为了解决某类49中山大学50一、算法的五个特性一、算法的五个特性1.1.有穷性：有穷性：对于任意一组合法的输入值，在执 行有穷步骤之后一定能结束，且算法中的每 个步骤都可在有限时间内完成；haha()/*only a joke,do nothing.*/main()printf(“请稍等.您将知道世界的未日.”);while(1)haha();中山大学50一、算法的五个特性1.有穷性：对于任意一组合法的50中山大学51一、算法的五个特性一、算法的五个特性2.2.确定性确定性：对于每种情况下所应执行的操作，在算法中都有确切的规定，使算法的阅读者 或执行者都能明确其含义及如何执行。并且 在任何条件下，算法只能有唯一的一条执行 路径，即对于相同的输入只能得出相同的输 出。中山大学51一、算法的五个特性2.确定性：对于每种情况下所应51中山大学52一、算法的五个特性一、算法的五个特性3.3.可行性：可行性：算法中描述的操作都必须足够基本，都可以通过已经实现的基本运算执行有限次来实现的.中山大学52一、算法的五个特性3.可行性：算法中描述的操作都52中山大学53一、算法的五个特性一、算法的五个特性4.有有输入：输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。中山大学53一、算法的五个特性4.有输入：作为算法加工对象的53中山大学54一、算法的五个特性一、算法的五个特性5.5.有有输出输出:它是一组与“输入”有确定关系的量值，有一个或多个输出，是算法进行信息加工后得到的结果，这种确定关系即为算法的功能。中山大学54一、算法的五个特性5.有输出:它是一组与“输入54中山大学55算法与程序的区别算法与程序的区别n算法是解决问题的一种方法或一个过程，考虑如何将输入转换成输出，一个问题可以有多种算法。n程序是用某种程序设计语言对算法的具体实现。n主要区别在：有穷性和描述方法 1、程序可以是无穷的，例如OS，算法是有穷的；2、程序是用程序设计语言描述，在机器上可以执行；算法还可以用框图、自然语言等方式描述。中山大学55算法与程序的区别算法是解决问题的一种方法或一个过55中山大学56二、算法设计的原则二、算法设计的原则设计算法时，通常应考虑达到以下目标：设计算法时，通常应考虑达到以下目标：1正确性正确性2.可读性可读性3健壮性健壮性4高效率与低存储量需求高效率与低存储量需求中山大学56二、算法设计的原则设计算法时，通常应考虑达到以下56中山大学57二、算法设计的原则二、算法设计的原则1.正确性：正确性：首先，算法应当满足以特定的首先，算法应当满足以特定的“规格说规格说明明”方式给出的需求。方式给出的需求。其次，对算法是否其次，对算法是否“正确正确”的理解可以的理解可以有以下四个层次：有以下四个层次：a a、程序不含语法错误；、程序不含语法错误；b b、程序对于几组输入数据能够得出满足、程序对于几组输入数据能够得出满足 规格说明要求的结果规格说明要求的结果 ；中山大学57二、算法设计的原则1.正确性：57中山大学58二、算法设计的原则二、算法设计的原则c c、程序对于精心选择的典型、苛刻而带有刁程序对于精心选择的典型、苛刻而带有刁 难性的几组输入数据能够得出满足规格说难性的几组输入数据能够得出满足规格说 明要求的结果明要求的结果。d d、程序对于一切合法的输入数据都能产生满、程序对于一切合法的输入数据都能产生满 足规格说明要求的结果。足规格说明要求的结果。中山大学58二、算法设计的原则c、程序对于精心选择的典型、苛58中山大学59中山大学5959中山大学60二、算法设计的原则二、算法设计的原则2.可读性：可读性：算法主要是为了人的阅读和交流，其算法主要是为了人的阅读和交流，其次才是为计算机执行。因此，算法应该易次才是为计算机执行。因此，算法应该易于人的理解；另一方面，晦涩难读的程序于人的理解；另一方面，晦涩难读的程序易于隐藏较多的错误而难以调试；易于隐藏较多的错误而难以调试；中山大学60二、算法设计的原则2.可读性：60中山大学61二、算法设计的原则二、算法设计的原则3.健壮性：健壮性：算法应具有算法应具有容错容错处理。当处理。当输入非法数据输入非法数据时时，算法应对其作出反应，而不是产生莫名，算法应对其作出反应，而不是产生莫名其妙的输出结果。并且，处理出错的方法不其妙的输出结果。并且，处理出错的方法不应是中断程序的执行，而应是返回一个表示应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层错误或错误性质的值，以便在更高的抽象层次上进行处理。次上进行处理。中山大学61二、算法设计的原则3.健壮性：61中山大学62二、算法设计的原则二、算法设计的原则4、高效率与低存储量需求：、高效率与低存储量需求：通常，效率指的是通常，效率指的是算法执行的时间算法执行的时间；对于解决同一问题的多个算法，执行时间对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行短的算法效率高。存储量需求指算法执行过程中过程中所需要的最大最大存储空间。一般，这。一般，这两者两者与问题的规模有关与问题的规模有关。中山大学62二、算法设计的原则4、高效率与低存储量需求：62二、算法设计的原则二、算法设计的原则中山大学63二、算法设计的原则中山大学6363设计实现算法过程步骤1.找出与求解有关的数据元素之间的关系2.确定在某一数据对象上所施加运算 3.考虑数据元素的存储表示 4.选择描述算法的语言5.设计实现求解的算法，并用程序语言加以描述。中山大学64设计实现算法过程步骤1.找出与求解有关的数据元素之间的关系64中山大学65 最简单的方法是使用自自然然语语言言。用自然语言来描述算法的优点是简单且便于人们对算法的阅读。缺点是不够严谨。可以使用程序流程图、N-S流程图等算法描述工具。其特点是描述过程简洁、明了。用以上两种方法描述的算法不能够直接在计算机上执行，若要将它转换成可执行的程序还有一个编程的问题。三、算法的描述三、算法的描述中山大学65 最简单的方法是使用自然语言。用自然语言来描述算65中山大学66 使用某种程序设计语言来描述算法，与具体的语言结合紧密，为具体程序设计语言量身定制，易于用所用的具体语言实现；但描述算法时需要考虑具体程序设计语言的要求(语法，类的定义、继承、扩展等)，不利于从整体上描述算法思想，所描述的算法可读性差，算法性能分析较困难，不同的语言，算法描述差异较大，缺乏通用性；三、算法的描述三、算法的描述中山大学66 使用某种程序设计语言来描述算法，与具体的语言结66中山大学67 为了解决理解与执行这两者之间的矛盾，人们常常使用一种称为伪码语言的描述方法来进行算法描述。伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节，因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。它虽然不能直接执行但很容易被转换成高级语言。三、算法的描述三、算法的描述中山大学67 为了解决理解与执行这两者之间的矛盾，人们常常使67中山大学68三、算法的描述三、算法的描述 “类C”描述语言是通过对C语言进行精心筛选保留的一个核心子集，并为了便于描述，又做了若干扩展修改，从而，增强了语言的描述功能。中山大学68三、算法的描述 “类C”描述语68中山大学69n#define TRUE 1n#define FALSE 0n#define OK 1n#define ERROR 0n#define OVERFLOW -1n数据结构的表示都用类型定义typedef的方式描述。数据元素被约定为ElemType 类型，用户需要根据具体情况，自行定义该数据类型。1.预定义常量及类型预定义常量及类型中山大学69#define TRUE 1 1.预69中山大学70 函数类型 函数名（函数参数表）语句序列；为了简化函数的书写，提高算法描述的清晰度，我们规定除函数参数表中的参数需要说明数据类型外，函数中使用的局部变量可以不做变量说明，必要时给出相应的注释即可。另外，在书写算法时，应该养成对重点语句段落添加注解的良好习惯。2.算法描述为以下的函数形式算法描述为以下的函数形式中山大学70 函数类型 函数名（函数参数表）2.70中山大学71n简单赋值 变量名=表达式；n串联赋值 变量名1=变量名2=.=变量名n=表达式；n成组赋值（变量名1，.，变量名n）=（表达式1，.，表达式n）；3.使用的赋值语句形式有使用的赋值语句形式有中山大学71简单赋值 变量名=表达式；3.使用的赋71中山大学72n结构赋值 结构名1=结构名2；结构名=（值1，值2，.，值n）；n条件赋值 变量名=条件表达式?表达式1：表达式2；n交换赋值 变量名1 变量名2；3.使用的赋值语句形式有使用的赋值语句形式有中山大学72结构赋值 结构名1=结构名2；3.使用72中山大学73n条件语句1 if（表达式）语句；n条件语句2 if（表达式）语句；else 语句；n开关语句1 switch（表达式）n case 值1：语句序列1；break；n case 值2：语句序列2；break；n.n case 值n：语句序列n；break；n default：语句序列n+1；n 4.使用的选择结构语句形式有使用的选择结构语句形式有中山大学73条件语句1 if（表达式）语句；4.使用73中山大学745.使用的循环结构语句形式有nfor循环语句循环语句 for（表达式1；循环条件表达式；表达式2）语句；nwhile循环语句循环语句 while（循环条件表达式）语句；n do-while循环语句循环语句 do 语句序列；while（循环条件表达式）；中山大学745.使用的循环结构语句形式有for循环语句 74中山大学756.使用的结束语句形式有n函数结束语句 return 表达式；return;ncase或循环结束语句 break;n异常结束语句 exit（异常代码）；中山大学756.使用的结束语句形式有函数结束语句 75中山大学767.使用的输入输出语句形式有n输入语句 scanf(格式串，变量名1，.，变量名n)；n输出语句 printf(格式串，表达式1，.，表达式n);n方括号（）中的内容是可以省略的部分。中山大学767.使用的输入输出语句形式有输入语句 sca76中山大学778.使用的扩展函数和注释格式n求最大值 max（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最大值。n求最小值 min（表达式1，.，表达式n）；这个函数返回参数表中n个表达式计算结果中的最小值。n单行注释 /文字序列中山大学778.使用的扩展函数和注释格式求最大值 max（77中山大学78四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则 n评价算法的标准：评价算法的标准：评价一个算法主要看这个算法所占用机器资源的多少，而这些资源中时间代价与空间代价是两个主要的方面，通常是以算法执行所需的机器时间和所占用的存储空间来判断一个算法的优劣。中山大学78四、算法效率的衡量方法和准则 评价算法的标准：78中山大学79四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则 n算法执行的时间是算法问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：1 1、事后统计法；、事后统计法；缺点：缺点：1 1、必须执行程序、必须执行程序 2 2、其它因素掩盖算法本质、其它因素掩盖算法本质 2 2、事前分析估算法；、事前分析估算法；中山大学79四、算法效率的衡量方法和准则 算法执行的时间是算79中山大学80四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则和算法执行时间相关的因素：和算法执行时间相关的因素：1、算法本身选用的策略；2 2、问题的规模、问题的规模（规模越大，消耗时间越多）；）；3、编写程序的语言（语言越高级，消耗时间越 多）；4、编译程序产生的机器代码质量；5、计算机执行指令的速度；中山大学80四、算法效率的衡量方法和准则和算法执行时间相关的80中山大学81四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则 n1、算法的执行时间：、算法的执行时间：一个算法的执行时间大致一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所执行时间是指该条语句的执行次数和执行一次所需时间的乘积。需时间的乘积。中山大学81四、算法效率的衡量方法和准则 1、算法的执行时间81中山大学82四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则 n分析：分析：由于语句的执行要由源程序经编译程序由于语句的执行要由源程序经编译程序翻译成目标代码、目标代码经装配再执行，语翻译成目标代码、目标代码经装配再执行，语句执行一次实际所需的具体时间是与机器的软、句执行一次实际所需的具体时间是与机器的软、硬件环境（机器速度、编译程序质量、输入数硬件环境（机器速度、编译程序质量、输入数据量等）密切相关，与算法设计的好坏无关，据量等）密切相关，与算法设计的好坏无关，所以，所谓的算法分析所以，所谓的算法分析不是针对实际执行时间不是针对实际执行时间的精确的算出算法执行具体时间的分析的精确的算出算法执行具体时间的分析，而是，而是针对算法中语句的针对算法中语句的执行次数执行次数做出做出估计估计，从中得，从中得到算法执行时间的信息。到算法执行时间的信息。中山大学82四、算法效率的衡量方法和准则 分析：由于语句的执82中山大学83四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则 n2、语句频度、语句频度：该语句在一个算法中重复执行的：该语句在一个算法中重复执行的次数。次数。中山大学83四、算法效率的衡量方法和准则 2、语句频度：该语83中山大学843 3、时间复杂度、时间复杂度:一个算法的时间复杂度是该算法的时间耗费，一个算法的时间复杂度是该算法的时间耗费，一般地说，时间复杂度是一般地说，时间复杂度是问题规模问题规模的函数的函数 T(n)T(n)。算法中语句重复执行次数的。算法中语句重复执行次数的数量级数量级就是就是时间复杂度时间复杂度。四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则中山大学843、时间复杂度:四、算法效率的衡量方法和准则84中山大学85时间复杂度的表示方法：时间复杂度的表示方法：T(n)=O(f(n)T(n)=O(f(n)f(n)表示基本操作基本操作重复执行的次数，是n的某个函数，随问题规模n的增大，算法执行时间的增长率和f(n)的增长率属于同一数量级；O表示f(n)和T(n)只相差一个常数倍。T（n)称做渐进时间复杂度，简称时间复杂度。一般情况下，随n的增大，T（n)的增长较慢的算法为最优的算法。四、算法效率的衡量方法和准则四、算法效率的衡量方法和准则中山大学85时间复杂度的表示方法：T(n)=O(f(n)85中山大学861 1、我我们们假假定定，每每条条语语句句一一次次执执行行的的时时间间都都是是相相同同的的，为为单单位位时时间间。这这样样我我们们对对时时间间的的分分析析就就可可以以独独立立于于软软硬硬件件系系统统。算算算算法法法法的的的的时时时时间间间间复复复复杂杂杂杂度是该算法中所有语句的执行频度之和度是该算法中所有语句的执行频度之和度是该算法中所有语句的执行频度之和度是该算法中所有语句的执行频度之和。算法时间复杂度分析算法时间复杂度分析中山大学861、我们假定，每条语句一次执行的时间都是相同的，86例：求两个方阵的乘积例：求两个方阵的乘积 CA*Bdefine n 自然数自然数MATRIXMLT(float Ann,float Bnn,float Cnn)int i,j,k;for(i=0;in;i+)/n+1 for(j=0;jn;j+)/n(n+1)Cij=0;/n*n for(k=0;kn;k+)/n*n*(n+1)Cij=Aik*Bkj /n*n*n 例：求两个方阵的乘积 CA*B87中山大学882、一一般般情情况况下下，对对步步进进循循环环语语句句只只考考虑虑循循环环体体语语句句的的执执行行次次数数，而而忽忽略略该该语语句句中中部部长长加加一一、终终值值判判别别、循循环环转转移移等等成成份份。因因此此，当当有有若若干干个个循循环环语语句句时时，算算法法的的时时间间复复杂杂度度是是由由嵌套层数最最多多的的循环语句中最内层语句的频度所决定的。算法时间复杂度分析算法时间复杂度分析中山大学882、一般情况下，对步进循环语句只考虑循环体语句的88例：例：x=0;y=0;for(k=1;k=n;k+)x+;for(i=1;i=n;i+)for(j=1;j1&change;-I)/将a中整数序列重新排列成自小至大有序的整数序列。change=false;for(j=0;jaj+1)aj aj+1;change=TURE /bubble-sort 基本操作：赋值操作；中山大学92算法时间复杂度分析例.对n个整数的序列进行冒泡排92中山大学93算法时间复杂度分析算法时间复杂度分析最好情况：0次;最坏情况：1+2+3+n-1=n(n-1)/2;平均时间复杂度为:O(n2);有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。中山大学93算法时间复杂度分析最好情况：0次;93中山大学94几种时间复杂度几种时间复杂度1.O(1):常数时间常数时间2.O(log2n)：对数时间：对数时间3.O(n)：线性时间：线性时间4.O(nlog2n)：线性对数时间：线性对数时间5.O(n2):平方时间平方时间6.O(n3):立方时间立方时间7.O(2n):指数时间指数时间中山大学94几种时间复杂度O(1):常数时间94中山大学95几种时间复杂度几种时间复杂度中山大学95几种时间复杂度95中山大学96五、算法的存储空间需求五、算法的存储空间需求 类似于算法的时间复杂度，空间复杂度可以类似于算法的时间复杂度，空间复杂度可以作为算法所需存储空间的量度。记作：作为算法所需存储空间的量度。记作：S(n)=O(g(n)表示随着问题规模表示随着问题规模n的增大，算法运行所需存的增大，算法运行所需存储量的增长率与储量的增长率与g(n)的增长率相同。的增长率相同。中山大学96五、算法的存储空间需求 类似于算法的时间复96中山大学97算法的存储量包括：算法的存储量包括：1.输入数据所占空间；2.程序本身所占空间；3.辅助变量所占空间；五、算法的存储空间需求五、算法的存储空间需求中山大学97算法的存储量包括：五、算法的存储空间需求97中山大学98 若输入数据所占空间只取决与问题本身，若输入数据所占空间只取决与问题本身，而与算法无关。则只需要分析除输入数据和而与算法无关。则只需要分析除输入数据和程序之外的辅助变量所占的额外空间。程序之外的辅助变量所占的额外空间。若所需额外空间若所需额外空间相相对于输入数据量来说对于输入数据量来说是常数是常数，则称此算法为，则称此算法为原地工作原地工作。若所需存储量若所需存储量依赖于特定的输入依赖于特定的输入，则通，则通常按常按最坏最坏情况考虑。情况考虑。五、算法的存储空间需求五、算法的存储空间需求中山大学98 若输入数据所占空间只取决与问题本身，而与算98中山大学991熟悉各名词、术语的含义，深刻理解 基本概念。2了解抽象数据类型的定义、表示和实 现方法。3理解算法的概念及5个要素的确切含 义。4掌握算法时间复杂度的估算方法。本章学习要点本章学习要点中山大学99 1熟悉各名词、术语的含义，深刻理解 本章学习99中山大学100中山大学100100逻辑结构和存储结构的区别n逻辑结构定义了数据元素之间的逻辑关系；n存储结构是逻辑结构在计算机中实现；n一种逻辑结构可以采用不同存储方式存储在计算机中，但都必须反映出要求的逻辑关系。中山大学101逻辑结构和存储结构的区别逻辑结构定义了数据元素之间的逻辑关系101中山大学102 1.1.简述如下概念：简述如下概念：n数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、抽象数据类型。本章习题本章习题中山大学102 1.简述如下概念：本章习题102中山大学103 2.定义抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。本章习题本章习题中山大学103 2.定义抽象数据类型“有理数”。基本操作103中山大学104(1)i=1;k=0;do k+=10*i;i+;while(i=n-1);(2)k=0;for(i=1;i=n;i+)for(j=i;j=n;j+)k+;本章习题本章习题 3.设n为正整数，利用大“O”记号，分析下列程序段的T(n)。中山大学104(1)i=1;k=0;do 104（3）for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;中山大学105本章习题本章习题（3）for(i=1;i=n;i+)中山大学105本章习105