第第1章章 数据结构概述数据结构概述本章重点和难点：本章重点和难点：1 1、数据结构的基本概念、数据结构的基本概念2 2、什么是抽象数据类型、什么是抽象数据类型3 3、如何计算算法的时间复杂度、如何计算算法的时间复杂度1.1 为什么要学习数据结构为什么要学习数据结构1 1数据结构的发展变迁数据结构的发展变迁 数据结构在计算机科学与技术专业中是一门综合性的数据结构在计算机科学与技术专业中是一门综合性的专业基础课。在国外，数据结构作为一门独立的课程是从专业基础课。在国外，数据结构作为一门独立的课程是从1968 年才开始设立的。年才开始设立的。 1968年，美国的唐年，美国的唐欧欧克努特教授开创了数据结克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。储结构及其操作的著作。1.1 为什么要学习数据结构为什么要学习数据结构2 2数据结构的地位数据结构的地位 在我国，数据结构已经不仅仅是计算机专业的核心课在我国，数据结构已经不仅仅是计算机专业的核心课程，还是其他非计算机专业的主要选修课程之一。数据结程，还是其他非计算机专业的主要选修课程之一。数据结构的研究不仅涉及到计算机硬件的研究范围，而且与计算构的研究不仅涉及到计算机硬件的研究范围，而且与计算机软件的研究有着更密切的关系，无论是编译程序还是操机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。因此，作系统，都涉及到数据元素在存储器中的分配问题。因此，可以认为数据结构是介于数学、计算机硬件和计算机软件可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。三者之间的一门核心课程。1.1 为什么要学习数据结构为什么要学习数据结构 开发所有的计算机系统软件和应用软件都要用到各开发所有的计算机系统软件和应用软件都要用到各种类型的数据结构。因此，要想更好地运用计算机来解种类型的数据结构。因此，要想更好地运用计算机来解决实际问题，仅掌握几种计算机程序设计语言是难以应决实际问题，仅掌握几种计算机程序设计语言是难以应付众多复杂问题的。要想有效地使用计算机、充分发挥付众多复杂问题的。要想有效地使用计算机、充分发挥计算机的性能，还必须学习和掌握好数据结构方面的有计算机的性能，还必须学习和掌握好数据结构方面的有关知识。打好关知识。打好“数据结构数据结构”这门课程的扎实基础，对于这门课程的扎实基础，对于学习计算机专业的其他课程，如操作系统、编译原理、学习计算机专业的其他课程，如操作系统、编译原理、数据库管理系统、软件工程、人工智能等都是十分有益数据库管理系统、软件工程、人工智能等都是十分有益的。的。1.1 为什么要学习数据结构为什么要学习数据结构 在计算机发展的初期，人们使用计算机的目的主要是处理数值计算问题。 学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。与此同时，通过算法训练来提高学生的思维能力，通过程序设计的技能训练来促进学生的综合应用能力和专业素质的提高。 1.2 基本概念和术语基本概念和术语1 1数据（数据（datadata） 数据是描述客观事物的符号，能输入到计算机中并能数据是描述客观事物的符号，能输入到计算机中并能被计算机程序处理的符号集合。它是计算机程序加工的被计算机程序处理的符号集合。它是计算机程序加工的“原料原料”。例如，一个文字处理程序（如。例如，一个文字处理程序（如Microsoft word）的处理对象就是字符串，一个数值计算程序的处）的处理对象就是字符串，一个数值计算程序的处理对象就是整型和浮点型数据。因此，数据的含义非常理对象就是整型和浮点型数据。因此，数据的含义非常广泛，如整型、浮点型等数值类型及字符、声音、图像、广泛，如整型、浮点型等数值类型及字符、声音、图像、视频等非数值数据都属于数据范畴。视频等非数值数据都属于数据范畴。1.2 基本概念和术语基本概念和术语2 2数据元素（数据元素（data elementdata element） 数据元素是数据的基本单位，在计算机程序中通常作数据元素是数据的基本单位，在计算机程序中通常作为一个整体考虑和处理。一个数据元素可由若干个数据项为一个整体考虑和处理。一个数据元素可由若干个数据项（data item）组成，数据项是数据不可分割的最小单位。）组成，数据项是数据不可分割的最小单位。例如，一个学校的教职工基本情况表包括编号、姓名、性例如，一个学校的教职工基本情况表包括编号、姓名、性别、籍贯、所在院系、出生年月、职称等数据项。这里的别、籍贯、所在院系、出生年月、职称等数据项。这里的数据元素也称为记录。教职工基本情况如表数据元素也称为记录。教职工基本情况如表1.1所示。所示。1.2 基本概念和术语基本概念和术语表1.1 教职工基本情况表编 号姓 名性 别籍 贯所在院系出生年月职 称05002胡志刚男河南化工学院1970.10教授01156张琳女北京文学院1978.08副教授03527李燕女陕西信息学院1981.11讲师1.2 基本概念和术语基本概念和术语3 3数据对象（数据对象（data objectdata object） 数据对象是性质相同的数据元素的集合，是数据的一数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，正整数数据对象是集合个子集。例如，正整数数据对象是集合N=1，2，3，字母字符数据对象是集合，字母字符数据对象是集合C=A，B，C，。1.2 基本概念和术语基本概念和术语4 4数据结构（数据结构（data structuredata structure） 数据结构即数据的组织形式，它是数据元素之间存在数据结构即数据的组织形式，它是数据元素之间存在的一种或多种特定关系的数据元素集合。在现实世界中，的一种或多种特定关系的数据元素集合。在现实世界中，任何事物都是有内在联系的，而不是孤立存在的，同样在任何事物都是有内在联系的，而不是孤立存在的，同样在计算机中，数据元素不是孤立的、杂乱无序的，而是具有计算机中，数据元素不是孤立的、杂乱无序的，而是具有内在联系的数据集合。例如，表内在联系的数据集合。例如，表1.1的教职工基本情况表的教职工基本情况表是一种表结构，学校的组织机构是一种层次结构，城市之是一种表结构，学校的组织机构是一种层次结构，城市之间的交通路线属于图结构，如图间的交通路线属于图结构，如图1.1、图、图1.2所示所示。1.2 基本概念和术语基本概念和术语1.2 基本概念和术语基本概念和术语5 5数据类型（数据类型（data typedata type） 数据类型是用来刻画一组性质相同的数据及其上的操作。数据类型是按照值的不同进行划分的。 在C语言中，按照取值的不同，数据类型还可以分为两类：原子类型和结构类型。原子类型是不可以再分解的基本类型，包括整型、实型、字符型等。结构类型是由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干整型数据组成的，结构体类型的值也是由若干个类型范围的数据构成，它们的类型都是相同的。1.3 数据的逻辑结构与存储结构数据的逻辑结构与存储结构1.3.1 逻辑结构 数据元素之间存在数据元素之间存在4种结构类型：种结构类型： （1）集合。结构中的数据元素除了同属于一个集合外，数）集合。结构中的数据元素除了同属于一个集合外，数据元素之间没有其它关系。这就像我们数学中的自然数集合，据元素之间没有其它关系。这就像我们数学中的自然数集合，集合中的所有元素都属于该集合，除此之外，没有其它特性。集合中的所有元素都属于该集合，除此之外，没有其它特性。例如，数学中的正整数集合例如，数学中的正整数集合5，67，978，20，123，18，集合中数除了属于正整数外，元素之间没有其它关系，数，集合中数除了属于正整数外，元素之间没有其它关系，数据结构中的集合关系就类似于数学中的集合。集合表示如图据结构中的集合关系就类似于数学中的集合。集合表示如图1.3所示。所示。1.3 数据的逻辑结构与存储结构数据的逻辑结构与存储结构 （2）线性结构。结构中的数据元素之间是一对一的）线性结构。结构中的数据元素之间是一对一的关系。线性结构如图关系。线性结构如图1.4所示。数据元素之间有一种先后所示。数据元素之间有一种先后的次序关系，的次序关系，a,b,c是一个线性表，其中，是一个线性表，其中，a是是b的前驱，的前驱，b是是a的后继。的后继。 （3）树形结构。结构中的数据元素之间存在一种一）树形结构。结构中的数据元素之间存在一种一对多的层次关系，树形结构如图对多的层次关系，树形结构如图1.5所示。这就像学校的所示。这就像学校的组织结构图，学校下面是教学的院系、行政机构的部和组织结构图，学校下面是教学的院系、行政机构的部和处及一些研究所。处及一些研究所。1.3 数据的逻辑结构与存储结构数据的逻辑结构与存储结构 （4）图图结结构构。结结构构中中的的数数据据元元素素是是多多对对多多的的关关系系。图图1.6就就是是一一个个图图结结构构。城城市市之之间间的的交交通通路路线线图图就就是是多多对对多多的的关关系系，a，b，c，d，e，f，g是是7个个城城市市，城城市市a和和城城市市b、e、f都都存存在在一一条条直直达达路路线线，而而城城市市b也也和和a、c、f存存在在一一条条直达路线。直达路线。1.3 数据的逻辑结构与存储结构数据的逻辑结构与存储结构1.3.2 存储结构 存储结构存储结构也称为物理结构，物理结构，指的是数据的逻辑结构在计算机中存储形式。 数据元素的存储结构形式通常有两种：顺序存储结构和链式存储结构。采用顺序存储的字符串”abcdef”的存储结构如图1.7所示。链式存储是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的，数据元素的存储关系并不能反映其逻辑关系，因此需要借助指针来表示数据元素之间的逻辑关系。字符串”abcdef”的链式存储结构如图1.8所示。1.3 数据的逻辑结构与存储结构数据的逻辑结构与存储结构 数据的逻辑结构和物理结构是密切相关的，今后在学习数据结构的过程中，读者将会发现，任何一个算法的设计取决于选定的数据逻辑结构，而算法的实现依赖于所采用的存储结构。1.4 抽象数据类型及其描述抽象数据类型及其描述1.4.1 什么是抽象数据类型 抽象数据类型（抽象数据类型（abstract data type，简称，简称ADT）是描述具有某种逻辑关系的数学模型，并对在该）是描述具有某种逻辑关系的数学模型，并对在该数学模型上进行的一组操作。抽象数据类型描述的是一数学模型上进行的一组操作。抽象数据类型描述的是一组逻辑上的特性，与在计算机内部表示无关。计算机中组逻辑上的特性，与在计算机内部表示无关。计算机中的整数数据类型是一个抽象数据类型，不同的处理器可的整数数据类型是一个抽象数据类型，不同的处理器可能实现方法不同，但其逻辑特性相同，即加、减、乘、能实现方法不同，但其逻辑特性相同，即加、减、乘、除等运算是一致的。除等运算是一致的。1.4 抽象数据类型及其描述抽象数据类型及其描述 抽象数据类型不仅包括在计算机中已经定义了的抽象数据类型不仅包括在计算机中已经定义了的数据类型，例如整型、浮点型等，还包括用户自己定数据类型，例如整型、浮点型等，还包括用户自己定义的数据类型，例如结构体类型、类等。义的数据类型，例如结构体类型、类等。 一个抽象数据类型定义了一个数据对象、数据对一个抽象数据类型定义了一个数据对象、数据对象个数据元素之间的关系及对数据元素的操作。抽象象个数据元素之间的关系及对数据元素的操作。抽象数据类型通常是指用户定义，用来解决应用问题的数数据类型通常是指用户定义，用来解决应用问题的数据模型，包括数据的定义和操作。例如，据模型，包括数据的定义和操作。例如，C+的类就的类就是一个抽象数据类型，它包括用户类型的定义和在用是一个抽象数据类型，它包括用户类型的定义和在用户类型上的一组操作。户类型上的一组操作。1.4 抽象数据类型及其描述抽象数据类型及其描述 抽象数据类型体现了程序设计中的问题分解、抽象抽象数据类型体现了程序设计中的问题分解、抽象和信息隐藏特性。抽象数据类型把实际生活中的问题分和信息隐藏特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题，然后进行建立起一解为多个规模小且容易处理的问题，然后进行建立起一个计算机能处理的数据模型，并把每个功能模块的实现个计算机能处理的数据模型，并把每个功能模块的实现细节作为一个独立的单元，从而使具体实现过程隐藏起细节作为一个独立的单元，从而使具体实现过程隐藏起来。来。1.4 抽象数据类型及其描述抽象数据类型及其描述1.4.2 抽象数据类型的描述 本书把抽象数据类型分为两个部分来描述：数据对象本书把抽象数据类型分为两个部分来描述：数据对象集合和基本操作集合。其中，数据对象集合包括数据对象集合和基本操作集合。其中，数据对象集合包括数据对象的定义及数据对象中元素之间关系的描述，基本操作集合的定义及数据对象中元素之间关系的描述，基本操作集合是对数据对象的运算的描述。是对数据对象的运算的描述。数据对象和数据关系的定义可采用数学符号和自然语言描述，基本操作的定义格式为： 基本操作名（参数表）：初始条件和操作结果描述。 1.4 抽象数据类型及其描述抽象数据类型及其描述 例如，线性表的抽象数据类型描述如下：例如，线性表的抽象数据类型描述如下： 1数据集合数据集合 线性表的数据对象集合为线性表的数据对象集合为a1，a2，an，每个元素，每个元素的类型均为的类型均为DataType。其中，除了第一个元素。其中，除了第一个元素a1外，每一外，每一个元素有且只有一个直接前驱元素，除了最后一个元素个元素有且只有一个直接前驱元素，除了最后一个元素an外，外，每一个元素有且只有一个直接后继元素。数据元素之间的关每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。系是一对一的关系。1.4 抽象数据类型及其描述抽象数据类型及其描述2基本操作集合基本操作集合线性表的基本操作主要有：（1）InitList(&L)：初始化操作，建立一个空的线性表L。这就像是在日常生活中，一所院校为了方便管理，建立一个教职工基本情况表，准备登记教职工信息。（2）ListEmpty(L)：若线性表L为空，返回1，否则返回0。这就像是刚刚建立了教职工基本情况表，还没有登记教职工信息。（3）GetElem(L,i,&e)：返回线性表L的第i个位置元素值给e。这就像在教职工基本情况表中，根据给定序号查找某个教师信息。（4）LocateElem(L,e)：在线性表L中查找与给定值e相等的元素，如果查找成功返回该元素在表中的序号表示成功，否则，返回0表示失败。这就像在教职工基本情况表中，根据给定的姓名查找教师信息。（5）InsertList(&L,i,e)：在线性表L中的第i个位置插入新元素e。这就类似于经过招聘考试，引进了一名教师，这个教师信息被登记到教职工基本情况表中。1.4 抽象数据类型及其描述抽象数据类型及其描述 可能你会在大多数教材上看到线性表的抽象数据类型用以可能你会在大多数教材上看到线性表的抽象数据类型用以下方式描述：下方式描述： ADT List 数据对象：数据对象：D=ai|aiElemSet，i=1，2，n，n0 数据关系：数据关系：R=|ai-1，aiD，i=2，3，n1.4 抽象数据类型及其描述抽象数据类型及其描述 需需要要注注意意的的是是，在在基基本本操操作作的的描描述述过过程程中中，参参数数传传递递有有两两种种方方式式：一一种种是是数数值值传传递递，另另一一种种是是引引用用传传递递。前前者者仅仅仅仅是是将将数数值值传传递递给给形形参参，并并不不返返回回结结果果；后后者者其其实实是是把把实实参参的的地地址址传传递递给给形形参参，实实参参和和形形参参其其实实是是同同一一个个变变量量，被被调调用用函函数数通通过过修修改改该该变变量量的的值值返返回回给给调调用用函函数数，从从而而把把结结果果带带回回。在在描描述述算算法法时时，通通过过在在参参数数前前加加上上&，表表示示引引用用传传递递，如如果果参参数数前前没没有有&，表表示示是数值传递。是数值传递。1.5 算法算法1.5.1 数据结构与算法的关系 算法与数据结构关系密切。两者既有联系又有区别。算法与数据结构关系密切。两者既有联系又有区别。 数据结构与算法的联系可用一个公式描述：程序数据结构与算法的联系可用一个公式描述：程序=算法算法+数据结构。数据结构是算法实现的基础，算法总是要依赖数据结构。数据结构是算法实现的基础，算法总是要依赖于某种数据结构来实现的。算法的操作对象是数据结构。于某种数据结构来实现的。算法的操作对象是数据结构。1.5 算法算法 数数据据结结构构与与算算法法的的区区别别在在于于：数数据据结结构构关关注注的的是是数数据据的的逻逻辑辑结结构构、存存储储结结构构以以及及基基本本操操作作，而而算算法法更更多多的的是是关关注注如如何何在在数数据据结结构构的的基基础础上上解解决决实实际际问问题题。算算法法是是编编程程思思想想，数据结构则是这些思想的逻辑基础。数据结构则是这些思想的逻辑基础。1.5 算法算法1.5.1 什么是算法 算法算法(algorithm)是解决特定问题求解步骤的描述，在计算机中表是解决特定问题求解步骤的描述，在计算机中表现为有限的操作序列。操作序列包括了一组操作，每一个操作都完成现为有限的操作序列。操作序列包括了一组操作，每一个操作都完成特定的功能。例如，求特定的功能。例如，求n个数中最大者的问题，其算法描述如下：个数中最大者的问题，其算法描述如下： 1定义一个变量定义一个变量max和一个数组和一个数组a，分别用来存放最大数和数组，分别用来存放最大数和数组的元素，并假定第一个数最大，赋给的元素，并假定第一个数最大，赋给max，即：，即： max=a0;1.5 算法算法2依次把数组依次把数组a中其余的中其余的n-1个数与个数与max进行比较，遇进行比较，遇到较大的数时，将其赋给到较大的数时，将其赋给max。 for(i=1;in;i+) if(maxai) max=ai; 最后，最后，max中的数就是中的数就是n个数中的最大者。个数中的最大者。1.5 算法算法1.5.2 算法的五大特性算法具有以下5个特性。（1）有穷性有穷性。有穷性指的是算法在执行有限的步骤之后，自动结束而不会出现无限循环，并且每一个步骤在可接受的时间内完成。（2）确定性确定性。算法的每一步骤都具有确定的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，也就是相同的输入只能有一个唯一的输出结果。（3）可行性可行性。算法的每一步都必须是可行的，也就是说，每一步都能够通过执行有限次数完成。（4）输入输入。算法具有零个或多个输入。（5）输出输出。算法至少有一个或多个输出。输出的形式可以是打印输出也可以是返回一个或多个值。1.5.3 算法的描述 算法的描述方式有多种：自然语言、伪代码（或称为类算法的描述方式有多种：自然语言、伪代码（或称为类语言）、程序流程图及程序设计语言（如语言）、程序流程图及程序设计语言（如C语言）。语言）。 例如，判断正整数例如，判断正整数m是否为质数的算法可用以下几种方是否为质数的算法可用以下几种方式描述。式描述。1.5 算法算法1.5 算法算法1自然语言描述法自然语言描述法我们利用自然语言描述我们利用自然语言描述m是否为质数的算法如下：是否为质数的算法如下：（1）输入正整数）输入正整数m，令，令i=2；（2）如果）如果i=，则令，则令m对对i求余，将余数送入中间变量求余，将余数送入中间变量r；否则，输出否则，输出“m是质数是质数”，算法结束；，算法结束；（3）判断）判断r是否为零。如果为零，输出是否为零。如果为零，输出“m不是质数不是质数”，算，算法结束。如果法结束。如果r不为零，则令不为零，则令i增加增加1，转到步骤（，转到步骤（2）执）执行。行。1.5 算法算法 2程序流程图法程序流程图法 判断m是否为质数的程序流程图如图1.9所示。我们采用类C语言描述和C语言描述如下： 1.5 算法算法 3类语言法类语言法void IsPrime()/*判断m是否为质数*/scanf(m); /*输入正整数m*/for(i=2;i=sqrt(m);i+) r=m%i; /*求余数*/ if(r=0) /*如果m能被整除*/ printf(“m不是质数！”); break; printf(“m是质数！”);1.5 算法算法 4程序设计语言法程序设计语言法void IsPrime()/*判断m是否为质数*/ printf(“请输入一个正整数：”);scanf(“%d”,&m); /*输入正整数m*/for(i=2;i=sqrt(m);i+)r=m%i; /*求余数*/if(r=0) /*如果m能被整除*/printf(“m不是质数！n”); break; printf(“m是质数！n”);1.6.1 算法设计的四个目标 一个好的算法应该具备以下目标：一个好的算法应该具备以下目标： 1算法的正确性算法的正确性 算法的正确性（算法的正确性（correctness）是指算法至少应该包括对）是指算法至少应该包括对于输入、输出和加工处理无歧义性的描述，能正确反映问于输入、输出和加工处理无歧义性的描述，能正确反映问题的需求，且能够得到问题的正确答案。题的需求，且能够得到问题的正确答案。1.6 1.6 算法分析算法分析 通常算法的正确性应包括以下通常算法的正确性应包括以下4个层次：个层次：a.算法对应算法对应的程序没有语法错误；的程序没有语法错误；b.对于几组输入数据能得到满足规对于几组输入数据能得到满足规格要求的结果；格要求的结果；c.对于精心选择的典型的、苛刻的带有刁对于精心选择的典型的、苛刻的带有刁难性的几组输入数据能得到满足规格要求的结果；难性的几组输入数据能得到满足规格要求的结果；d.对于对于一切合法的输入都能得产生满足要求的结果。一切合法的输入都能得产生满足要求的结果。1.6 1.6 算法分析算法分析 2可读性可读性 算法主要是为了人们方便阅读和交流，其次才是计算机执行。可读性（可读性（readability）好有助于人们对算法的理解，晦涩难懂的程序往往隐含错误不易被发现，难以调试和修改。1.6 1.6 算法分析算法分析3健壮性（健壮性（robustness） 当输入数据不合法时，算法也能做出反应或进行处理，而不会产生异常或莫名其妙的输出结果。例如，求一元二次方程根ax2+bx+c=0的算法，需要考虑多种情况，先判断b2-4ac的正负，如果为正数，则该方程有两个不同的实根；如果为负，表明该方程无实根；如果为零，表明该方程只有一个实根；如果a=0，则该方程又变成了一元一次方程，此时若b=0，还要处理除数为零的情况。如果输入的a、b、c不是数值型，还要提示用户输入错误。1.6 1.6 算法分析算法分析4 4高效率和低存储量高效率和低存储量 效率指的是算法的执行时间。对于同一个问题如果有多个算法能够解决，执行时间短的算法效率高，执行时间长的效率低。存储量需求指算法在执行过程中需要的最大存储空间。效率与低存储量需求都与问题的规模有关，求100个人的平均分与求1000个人的平均分所花的执行时间和运行空间显然有一定差别。设计算法时应尽量选择高效率和低存储量需求的算法。1.6 1.6 算法分析算法分析1.6.2 算法效率评价 算法执行时间需通过依据该算法编制的程序在计算机上的算法执行时间需通过依据该算法编制的程序在计算机上的运行时所耗费的时间来度量，而度量一个算法在计算机上的执运行时所耗费的时间来度量，而度量一个算法在计算机上的执行时间通常有两种方法：行时间通常有两种方法： 1事后统计方法事后统计方法 这种方法有两个缺陷：一是必须依据算法事先编制好程这种方法有两个缺陷：一是必须依据算法事先编制好程序，这通常需要花费大量的时间与精力；二是时间的长短依赖序，这通常需要花费大量的时间与精力；二是时间的长短依赖计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。计算机硬件和软件等环境因素，有时会掩盖算法本身的优劣。 因此，人们常常采用事前分析估算的方法评价算法的好坏。因此，人们常常采用事前分析估算的方法评价算法的好坏。1.6 1.6 算法分析算法分析2事前分析估算方法事前分析估算方法 这主要在计算机程序编制前，对算法依据数学中的统计方法进行估算。这主要是因为算法的程序在计算机上的运行时间取决于以下因素： a算法采用的策略、方法； b编译产生的代码质量； c问题的规模； d书写的程序语言，对于同一个算法，语言级别越高，执行效率越低； e机器执行指令的速度。1.6 1.6 算法分析算法分析 例如，斐波那契数列的算法和语句的的频度如下。例如，斐波那契数列的算法和语句的的频度如下。 每一条语句的频度每一条语句的频度 f0=0; 1 f1=1; 1 printf(“%d,%d”,f0,f1); 1 for(i=2;i=n;i+) n fn=f0+f1; n-1printf(“,%d”,fn); n-1f0=f1; n-1f1=fn; n-1 每一条语句的右端是对应语句的频度（每一条语句的右端是对应语句的频度（frequency count），即语），即语句的执行次数。上面算法总的执行次数为句的执行次数。上面算法总的执行次数为T(n)=1+1+1+n+4(n-1)=5n-1。1.6 1.6 算法分析算法分析1.6.3 算法的时间复杂度 在进行算法分析时，语句总的执行次数T（n）是关于问题规模n的函数，进而分析T（n）随n的变化情况并确定T（n）的数量级。算法的时间复杂度，也就是算法的时间量度算法的时间量度，记作： T（n）=O(f（n）) 它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度（渐进时间复杂度（asymptotic time complexity），简称为时间复杂度时间复杂度。 1.6 1.6 算法分析算法分析 一般情况下，随n的增大，T（n）的增长较慢的算法为最优的算法。例如，在下列三段程序段中，给出原操作x=x+1的时间复杂度分析。 （1）x=x+1； （2）for（i=1；i=n；i+） x=x+1； （3）for（i=1；i=n；i+） for（j=1；j=n；j+） x=x+1； 1.6 1.6 算法分析算法分析 常用的时间复杂度所耗费的时间从小到大依次是：常用的时间复杂度所耗费的时间从小到大依次是： O(1)O(log2n)O(n)O(n2)O(n3) O(2n)O(n!) 。 一些常见函数的增长率如图一些常见函数的增长率如图1.10所示。所示。 1.6 1.6 算法分析算法分析1.6.4 算法的空间复杂度 空间复杂度空间复杂度（space complexity）作为为算法所需存储空间的量度，记作： S(n)=O(f(n) 其中，n为问题的规模，f(n)为语句关于n的所占存储空间的函数。 1.6 1.6 算法分析算法分析 谈谈关于如何学好数据结构的一些粗浅认识。 1明确数据结构的重要性，树立学好数据结构的信心。 2熟练掌握程序设计语言，变腐朽为神奇 3结合生活实际，变抽象为具体 4多思考，多上机实践1.7 学好数据结构的秘诀学好数据结构的秘诀