数据结构简明教程（第3版）课件 第1章 概论

数据结构简明教程（第3版）高等学校数据结构课程系列教材1/105数据结构教材介绍第1章概论1.1数据结构概述1.2算法和算法分析1.3数据结构程序设计第1章概论2/1051.1数据结构概述1.1.1什么是数据结构计算机数据运算的一般过程：

数据是信息的载体，能够被计算机识别、存储和加工处理，数据包括文字、表格、图像等。

信息是数据的内涵，即数据所表达的意义。1.1数据结构概述3/105数据的基本单位是数据元素（有时称为结点、记录等），通常把数据元素作为一个整体进行处理。例如，一个班的学生数据包括张三、李四等数据元素。

一个学生数据张三，男，101班李四，计科系，北京……数据元素1.1数据结构概述4/105

数据对象是具有相同类型的数据元素的集合，因为所有数据元素类型相同时处理起来更加方便，所以在数据结构中除特别指定外数据通常都是数据对象。一个学生数据对象张三，男，101班李四，男，102班……相同类型的数据元素姓名性别班号1.1数据结构概述5/105

有时一个数据元素可以由若干个数据项（也可称为字段、域、属性）组成。

数据项是具有独立意义的不可分割的最小标识单位。

例如在1～100的整数数据中，10就是一个数据元素；又比如在一个学生表中，一个学生记录可称为一个数据元素，而这个元素中的某一字段（如姓名）就是一个数据项。一个学生数据对象张三，男，101班李四，男，102班……相同类型的数据元素姓名性别班号1.1数据结构概述6/105

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。这些数据元素不是孤立存在的，而是有着某种关系，这种关系构成了某种结构。在数据结构中主要讨论数据元素之间的相邻关系数据结构=数据+结构数据结构可以看成是带结构的数据元素的集合1.1数据结构概述7/105逻辑结构：数据元素之间的逻辑关系的整体。它是数据结构在用户面前呈现的形式。存储结构：数据元素及其关系在计算机存储器中的存储方式，也称为数据的物理结构。运算：施加在该数据上的操作。数据结构包括如下几个方面：1.1数据结构概述8/1051.1数据结构概述数据结构的视角：逻辑结构+运算定义存储结构运算实现用户视角程序员视角数据结构9/105例如一个学生成绩表Score，它由多个学生成绩记录（即数据元素）组成，每个元素又包括多个数据项，其中学号数据项是关键字，即学号唯一标识一个学生记录。现求计算所有学生的平均分。逻辑结构表示学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功901.1数据结构概述10/105

Score的数据运算是求所有学生的平均分。

为了实现这个功能，先要设计对应的存储结构，即把Score表存放到计算机内存中，然后设计出实现求平均分的算法。数据运算的描述数据运算的实现1.1数据结构概述11/105数据元素之间的逻辑关系的整体称为数据的逻辑结构，这里的逻辑关系主要指数据元素之间的相邻关系。

根据数据元素之间逻辑关系的不同特性，分为下列4类基本结构。1.1.2逻辑结构集合：包含的所有数据元素同属于一个集合（最松散的关系）。线性结构：包含的数据元素之间存在一对一的关系。树形结构：包含的数据元素之间存在一对多的关系。图形结构：包含的数据元素之间存在多对多的关系。也称为网状结构。1.1数据结构概述12/105数据的逻辑结构可以采用多种方式描述，二元组是一种既常用也十分通用的数据逻辑结构表示方式。二元组表示如下：S=(D，R)D={di

|1≤i≤n}R={rj

|1≤j≤m}D是数据元素的有限集合，即D是由有限个数据元素（简称为元素）所构成的集合。R是D上的关系的有限集合，即R是由有限个关系rj（1≤j≤m）所构成的集合。rj是指从D→D的关系。1.1数据结构概述13/105每个关系rj用序偶集合来表示。一个序偶表示两个元素的关系。用尖括号表示有向关系，如<a,b>表示存在元素a到b的关系。用圆括号表示无向关系，如（a,b）表示既存在元素a到b的关系，又存在元素b到a的关系。

S=(D，R)D={di

|1≤i≤n}R={rj

|1≤j≤m}1.1数据结构概述ab<a,b>ab(a,b)14/105设rj是一个D到D的关系，rj∈R。若元素d，d'∈D，且<d,d'>∈rj，则称d'是d的后继元素，d是d'的前驱元素，这时d和d'是相邻的元素（都是相对rj而言的）。如果不存在一个d'使<d,d'>∈rj，则称d为rj的终端元素。如果不存在一个d'使<d',d>∈rj，则称d为rj的开始元素。如果d既不是终端元素也不是开始元素，则称d是内部元素。1.1数据结构概述abcda是b的前驱b是a的后继a为开始元素d为终端元素b、c为内部元素15/105学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90学生成绩表Score开始元素:没有前驱元素终端元素:没有后继元素其他所有元素都只有一个前驱元素和一个后继元素这个表的逻辑结构为线性结构。1.1数据结构概述16/105实际上，Score表完整地描述了该数据的逻辑结构，也可以用二元组表示其逻辑结构如下（用学号表示相应的元素）：Score=(D，R)D={201201，201202，201204，201205，201206}R={r} //只有一个逻辑关系r={<201201,201205>，201205,201206>，<201206,201202>，<201202,201204>}学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90学生成绩表Score1.1数据结构概述17/105【例1.1】设数据的逻辑结构如下：B1=(D,R)D={1,2,3,4,5,6,7,8,9}R={r}r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}试画出对应的逻辑结构图，并指出哪些是开始结点，哪些是终端结点，说明是何种数据结构。1.1数据结构概述18/105解：画出B1对应的逻辑结构图。123467958B1=(D,R)D={1,2,3,4,5,6,7,8,9}R={r}r={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>,<4,7>,<5,8>,<7,9>}1.1数据结构概述19/1051是开始结点。2、6、8、9是终端结点。除开始结点外，每个结点有唯一的前驱结点。除终端结点外，每个结点有一个或多个后继结点。123467958一种树形结构1.1数据结构概述20/105【例1.2】设数据的逻辑结构如下：B2=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}试画出对应的逻辑结构图，说明是何种数据结构。1.1数据结构概述21/105214356解：画出B2对应的逻辑结构图。B2=(D,R)D={1,2,3,4,5,6}R={r}r={<1,2>,<2,4>,<1,3>,<3,4>,<3,5>,<3,6>,<5,6>}1.1数据结构概述22/105每个结点都零个或多个前驱结点，每个结点都零个或多个后继结点214356一种图形结构1.1数据结构概述23/1051.1.3存储结构数据逻辑结构在计算机中的存储表示称为数据的存储结构，也称为物理结构。

通常情况下，同一种逻辑结构可以设计多种存储结构，在不同的存储结构中，实现同一种运算的算法可能不同。

逻辑结构存储结构映射1.1数据结构概述24/105逻辑结构、存储结构和运算三者之间的关系：运算的定义逻辑结构存储结构映射运算的实现将逻辑结构映射为存储结构时，存储逻辑结构中的：所有元素。元素之间的关系。1.1数据结构概述25/105主要的几种存储结构。顺序存储结构采用一组连续的存储单元存放所有的数据元素。逻辑上相邻的元素的存储单元也相邻。也就是说，元素之间的逻辑关系由存储单元地址间的关系隐含表示，即顺序存储结构将数据的逻辑结构直接映射到存储结构。1．顺序存储结构1.1数据结构概述26/105顺序存储结构可实现对各数据元素的随机存取。即顺序存储结构具有随机存取特性。随机存取是指给定某元素的逻辑序号i，能在常量时间内查找到对应的元素值。1.1数据结构概述27/105假设每个元素占用30个字节，且从100号单元开始由低地址向高地址方向存储。地址学号姓名分数100201201王实85130201205李斌82160201206刘英92190201202张山78220201204陈功90学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90Score对应的顺序存储结构所有元素的存储地址是连续的通过存储关系直接反映逻辑关系特点1.1数据结构概述28/1052．链式存储结构链式存储结构中每个结点单独存储，无需占用一整块存储空间。但为了表示结点之间的关系，给每个结点附加指针字段，用于存放相邻结点的存储地址。1.1数据结构概述29/105学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90Score对应的链式存储结构地址学号姓名分数下一个结点地址┆100201201王实85520┆230201204陈功90∧┆310201206刘英92450┆450201202张山78230┆520201205李斌82310┆1.1数据结构概述30/105每个结点存放一个学生成绩记录。每个结点附加一个“下一个结点地址”即后继指针域，用于存放后继结点的首地址。head作为第一个结点的地址来标识整个链式存储结构。head201201王实85201205李斌82201206刘英92201202张山78201204陈功90∧更形象的图示所有结点的地址不一定连续。一个结点的所有成员占用一片连续空间增加指针域来表示元素之间的逻辑关系特点1.1数据结构概述31/1053．索引存储结构索引存储结构=数据表

+索引表。索引表中的每一项称为索引项，索引项的一般形式为：

（关键字，对应地址）其中“对应地址”为该关键字的记录在数据表中的存储地址。索引表中所有关键字有序排列（如递增）。1.1数据结构概述32/1051.1数据结构概述地址学号姓名分数100201201王实85130201205李斌82160201206刘英92190201202张山78220201204陈功90数据表索引表地址关键字对应地址300201201100310201202190320201204220330201205130340201206160Score的索引存储结构在进行关键字（如学号）查找时：先在索引表中快速查找（因为索引表中按关键字有序排列，可以采用二分查找）到相应的关键字。然后通过对应地址在数据表中找到该记录的数据。33/105索引存储结构特点：通过索引表按关键字查找速度快增加索引表

存储空间较大1.1数据结构概述34/1054．哈希（散列）存储结构哈希存储结构=哈希函数+解决冲突方法。哈希函数H(key)将关键字为key的元素存放在该地址。查找关键字为key的元素时，先计算H(key)，由该值和解决冲突方法来确定其存储地址。1.1数据结构概述35/105key201201201205201206201202201204H(key)04513学号姓名分数201201王实85201205李斌82201206刘英92201202张山78201204陈功90哈希表长度m=6（存储单元的地址为0～5）记录个数n=5哈希函数：H(学号)=学号-2012011.1数据结构概述36/105Score哈希存储结构地址学号姓名分数0201201王实851201202张山7823201204陈功904201205李斌825201206刘英92key201201201205201206201202201204H(key)04513特点按关键字查找速度快需要解决冲突1.1数据结构概述37/1051.1.4数据运算数据运算就是施加于数据的操作。

这种将运算定义和运算实现相互分离的做法具体软件工程的思想，更加便于软件开发。运算定义（或运算描述）：确定运算的功能，是抽象的。运算实现：在存储结构上确定对应运算实现算法，是具体的。1.1数据结构概述38/1051.1.5数据结构、数据类型和抽象数据类型

数据结构是指带结构的数据元素的集合，包括数据逻辑结构、存储结构和数据运算。

1、数据结构1.1数据结构概述39/105

数据类型是高级程序设计语言中的一个基本概念，用于指定变量数据的存储方式。数据类型是一组性质相同的值的集合和定义在此集合上的一组操作的总称。shortint-32768～32767+-*/%…2、数据类型1.1数据结构概述40/105C/C++语言中常用的数据类型（1）C/C++语言的基本数据类型int型：

可以有3个修饰符：short（短整数）、long（长整数）和unsigned（无符号整数）float型double型char型1.1数据结构概述41/105

数据类型用于定义变量，如有定义语句：intn=10;在执行该语句时系统自动为变量n分配一个固定长度（如4个字节）的内存空间。10n程序员通过变量名n对这个内存空间进行存取操作!当超出作用范围时系统自动释放其内存空间，所以称之为自动变量。1.1数据结构概述42/105（2）C/C++语言的指针类型C/C++语言允许直接对存放变量的地址进行操作。例如：inti=2;int*p=&i;2ip&ii的存储地址1.1数据结构概述43/105可以使用malloc()函数为一个指针变量分配一片连续的空间（称为动态空间分配）。char*p;p=(char*)malloc(10*sizeof(char));

//动态分配10个连续的字符空间strcpy(p,"China"); //将"China"存放到p所指向的空间中printf("%c\n",*p); //输出字符Cprintf("%s\n",p); //输出字符串"China"free(p); //释放p指向的空间p1个地址空间，通常4字节10个字符空间大小China\0ChinaC计算机屏幕1.1数据结构概述44/105pp的值和p指向的空间是不同的p的值存放指向空间的起始地址p指向的空间没有名称，不能直接操作，只能用p间接操作45/105（3）C/C++语言的数组类型数组是同一数据类型的一组数据的有限序列。数组分为一维数组和多维数组。数组名标识一个数组，下标指示一个数组元素在该数组中的位置。数组下标的最小值称为下界，在C语言中总是为0。数组下标的最大值称为上界，在C语言中数组上界为数组长度减1。例如，inta[10]定义了包含10个整数的数组a，其数组元素是a[0]～a[9]。1.1数据结构概述46/105（4）C/C++语言中的结构体类型结构体是由一组称为结构体成员的数据项组成的。每个结构体成员都有自已的标识符，也称为数据成员域。structteacher

//教师结构体类型{intno; //成员编号，占4个字节charname[8]; //成员姓名，占8个字节intage; //成员年龄，占4个字节};1.1数据结构概述47/105

结构体类型是用于定义结构体变量的，当定义一个结构体类型的变量时，系统按照结构体类型声明为对应的变量分配存储空间。structteachert;structteacher {intno;charname[8];intage;};t.not.aget1.1数据结构概述48/105（5）C/C++语言中的共用体类型

共用体用于把不同的数据成员组织为一个整体，它们在内存中共享一段存储单元，但不同成员以不同的方式被解释。uniontag

//tag共用体{shortintn; //成员n，占2个字节charch[2]; //成员ch数组，占2个字节};1.1数据结构概述49/105

共用体类型是用于定义共用体变量的，当定义一个共用体类型的变量时，系统按照共用体类型声明为对应的变量分配存储空间。uniontagu;u.n=0x4142; //十六进制数printf("%c,%c\n",u.ch[1],u.ch[0]);uniontag{shortintn;charch[2]; };u.nuu.chch[1]ch[0]AB计算机屏幕0x41420x410x421.1数据结构概述50/105（6）C语言中的自定义类型C/C++语言中允许使用typedef关键字为一个数据类型指定一个别名，例如：该语句将char类型与ElemType等同起来。这样做有两个好处:typedefcharElemType;方便程序调试，例如，将上述语句改为typedefintElemType，则程序中所有ElemType都改为int类型了。可以简化代码。1.1数据结构概述51/105typedefstructstudent //student结构体类型{intno; //学号成员charname[10]; //姓名成员charsex; //性别成员intcno; //班号成员}StudType; //用StudType别名表示student结构体类型StudTypes1,s2;structstudents1,s2;等同1.1数据结构概述52/105抽象数据类型（ADT）是指一个数学模型以及定义在此数学模型上的一组操作。定义一个抽象数据类型时，需要给出其名称和各运算名称及其功能描述。抽象数据类型需要通过固有数据类型（高级编程语言中已实现的数据类型）来实现。3、抽象数据类型1.1数据结构概述53/105从数据结构的角度看，一个求解问题可以通过抽象数据类型来描述。

也就是说，抽象数据类型（ADT）对一个求解问题从逻辑上进行了准确的定义，所以抽象数据类型由数据逻辑结构和运算定义两部分组成。抽象数据类型（ADT）=数据逻辑结构+运算定义1.1数据结构概述54/105

【例1.4】定义单个集合的抽象数据类型ASet，其中所有元素为正整数，包含创建一个集合、输出一个集合和判断一个元素是否为集合中元素的基本运算。在此基础上再定义两个集合运算的抽象数据类型BSet，包含集合的并集、差集和交集运算。1.1数据结构概述55/105（1）抽象数据类型ASet的定义如下：ADTASet{

数据对象：D={di

|0≤i≤n，n为一个正整数}运算的定义： voidcset(&s,a,n)：由含n个元素的数组a创建一个集合s。 voiddispset(s)：输出集合s。 intinset(s,e)：判断元素e是否为集合s中的元素。}1.1数据结构概述56/105（2）抽象数据类型BSet的定义如下：ADTBSet{

数据对象：D={si∈ASet|0≤i≤n，n为一个正整数}

运算的定义：voidadd(s1,s2,s3)：s3=s1∪s2

//求集合的并集voidsub(s1,s2,s3)：s3=s1-s2

//求集合的差集voidintersection(s1,s2,s3)：s3=s1∩s2

//求集合的交集}1.1数据结构概述57/1051.2算法和算法分析1.2.1算法及其描述一个运算实现是通过算法来表述的。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每条指令表示一个或多个操作。1.2算法和算法分析58/105算法设计应满足以下几条目标：正确性：要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。可使用性：要求算法能够很方便地使用。这个特性也叫做用户友好性。可读性：算法应该易于人的理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。健壮性：要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查。不经常出现异常中断或死机现象。高效率与低存储量需求。好的时间空间效率。1.2算法和算法分析59/105算法有以下5个重要特性。有限性：一个算法必须总是（对任何合法的输入值）在执行有限步之后结束，且每一步都可在有限时间内完成。确定性：算法中每一条指令必须有确切的含义，不会产生二义性。可行性：算法中每一条运算都必须是足够基本的，就是说它们原则上都能精确地执行，甚至人们仅用笔和纸做有限次运算就能完成。输入性：一个算法有零个或多个输入。输出性：一个算法有一个或多个输出。1.2算法和算法分析60/105

这两段描述均不能满足算法的特性，试问它们违反了算法的哪些特性？【例1.6】有下列两段描述：描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }1.2算法和算法分析61/105描述1是一个死循环，违反了算法的有限性特性。1.2算法和算法分析62/105描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }描述2出现除零错误，违反了算法的可行性特性。1.2算法和算法分析63/105描述1： 描述2：voidexam1() voidexam2(){intn=2; {

intx,y;

while(n%2==0)

y=0;n=n+2; x=5/y;printf("%d\n",n);printf("%d,%d\n",x,y);} }描述算法的方式很多，有的采用类PASCAL语言，有的采用自然语言。本书采用C/C++语言来描述算法的实现过程，通常采用C/C++函数来描述算法。

算法如何描述？1.2算法和算法分析64/105

以设计求1+2+…+n值的算法为例说明C/C++语言描述算法的一般形式，该算法如下所示。1.2算法和算法分析intSum1(intn,ints){inti;if(n<=0)return0; //当参数错误时返回假s=0;for(i=1;i<=n;i++) s+=i;return1; //当参数正确并产生正确结果时返回真}算法的返回值：正确执行时返回真，否则返回假算法的形参65/105通常用函数返回值表示算法能否正确执行，另外还可以带有形参。任何算法（用函数描述）都是被调用的（在C/C++语言中除main函数外任何一个函数都会被其他函数调用，如何一个函数不被调用，这样的函数是没有意义的）。

1.2算法和算法分析66/105

C/C++语言中调用函数时只有从实参到形参的单向值传递，执行函数时若改变了形参而对应的实参不会同步改变。

例如，设计以下主函数调用Sum1函数：intmain(){inta=10,b=0;

if(Sum1(a,b))printf("%d\n",b);

elseprintf("参数错误\n");}1.2算法和算法分析intSum1(intn,ints){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}67/105执行时发现输出结果为0。b对应的形参为s，Sum1执行后s=55，但s并没有回传给b。在C语言中可以用传指针方式来实现形参的回传，但增加了函数的复杂性。

1.2算法和算法分析intmain(){inta=10,b=0;

if(Sum1(a,b))printf("%d\n",b);

elseprintf("参数错误\n");}intSum1(intn,ints){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}68/105C++语言中增加了引用型参数的概念，引用型参数名前需加上&，表示这样的形参在执行后会将结果回传给对应的实参。当将形参s改为引用类型的参数后，执行时main函数的输出结果就正确了即输出55。1.2算法和算法分析intSum1(intn,int&s){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++) s+=i;return1;}引用型参数：在变量名称前面加上&69/105算法中引用型参数的作用1.2算法和算法分析intmain(){…fun(a,b)…}intfun(intn,ints){ …}：单向值传递，：回传C语言中：

intmain(){…fun(a,b)…}intfun(intn,int&s){ …}C++语言中：

函数调用70/1051.2.2算法分析计算机资源主要包括计算时间和内存空间。算法分析是分析算法占用计算机资源的情况。所以算法分析的两个主要方面是分析算法的时间复杂度和空间复杂度。算法分析的目的不是分析算法是否正确或是否容易阅读，主要是考察算法的时间和空间效率，以求改进算法或对不同的算法进行比较。

1.2算法和算法分析71/105事后统计法。事前分析估算法。1.2算法和算法分析有两种衡量算法效率的方法：事后统计法存在这些缺点：一是必须执行程序，二是存在其他因素掩盖算法本质。通常采用事前分析估算法来分析算法效率。72/105采用事前分析估算方法分析算法的时间性能。一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的。算法的运行时间取决于两者的综合效果。1.2算法和算法分析1.算法时间复杂度分析73/105例如，如下算法Solve，其中形参a是一个m行n列的数组，当是一个方阵（m=n）时求主对角线所有元素之和并返回1，否则返回0。intSolve(doublea[][MAX],intm,intn,double&s){inti;s=0;if(m!=n)retun0;for(i=0;i<m;i++)s+=a[i][i];return1;

}顺序结构分支结构循环结构顺序结构1.2算法和算法分析74/105算法的执行时间主要与问题规模n有关。例如，数组的元素个数、矩阵的阶数等都可作为问题规模。所谓一个语句的频度，即指该语句在算法中被重复执行的次数。算法中所有语句的频度之和记做T(n)，它是问题规模n的函数。一个算法的语句的频度之和T(n)与算法的执行时间成正比，所以可以将T(n)看作算法的执行时间。当问题规模n趋向无穷大时，T(n)的数量级称为渐进时间复杂度，简称为时间复杂度，记作T(n)=O(f(n))。1.2算法和算法分析75/105“O”的含义是为T(n)找到了一个上界f(n)，其严格的数学定义是：1.2算法和算法分析T(n)表示为O(f(n))是指存在正常量c和n0（为一个足够大的正整数），使得当n≥n0时，总有T(n)≤cf(n)成立。n0nT(n)cf(n)执行时间76/105可以利用极限来证明，即如果则T(n)=O(f(n))，则：例如某算法A的所有语句的频度之和为

TA(n)=5n3-2n2+3n-100，可以表示为TA(n)=O(n3)，因为一个函数的上界可能不止一个，如TA(n)=O(n4)也成立，因为通常采用大O表示法时给出的是所有上界中最小的那个上界

应该表示为TA(n)=O(n3)而不是TA(n)=O(n4)。1.2算法和算法分析77/105算法的时间复杂度是T(n)的数量级。算法中基本运算语句的频度与T(n)同数量级。被视为算法基本运算的语句一般是最深层循环内的语句。所以通常采用算法中基本运算语句的频度来分析算法的时间复杂度。1.2算法和算法分析78/105一个没有循环的算法中基本运算次数与问题规模n无关，记作O(1)，也称作常数阶。一个只有一重循环的算法中基本运算次数与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等等。1.2算法和算法分析79/105

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)1.2算法和算法分析各种不同数量级对应的值存在着如下关系：80/105对于求1+2+…+n值，图1.17所示的算法（称为算法1）不如下面的算法（称为算法2）好。

intSum1(intn,int&s){inti;if(n<=0)return0;s=0;for(i=1;i<=n;i++)s+=i;return1;}intSum2(intn,int&s){if(n<0)return0;elsereturnn*(n+1)/2;}因为算法1的时间复杂度为O(n)，而算法2的时间复杂度为O(1)。算法1算法21.2算法和算法分析81/105voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①{for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}}【例1.7】分析以下算法的时间复杂度。1.2算法和算法分析82/105语句①的执行频度为n+1（注意i<n判断语句需执行n+1次）语句②的执行频度为n(n+1)语句③的执行频度为n2语句④的执行频度为n2(n+1)语句⑤的执行频度为n31.2算法和算法分析voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}解法1：从求算法中所有语句的频度来分析算法时间复杂度。T(n)=2n3+3n2+2n+1=O(n3)83/105基本运算是语句⑤其频度为n3

结论：从中看到，两种方法的结果相同，而第二种方法更加简洁。1.2算法和算法分析解法2：从算法中基本运算的频度来分析算法时间复杂度。T(n)=n3=O(n3)voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++) //①for(j=0;j<n;j++) //②

{c[i][j]=0; //③

for(k=0;k<n;k++) //④

c[i][j]=c[i][j]+a[i][k]*b[k][j]; //⑤

}}84/105【例1.9】给出以下算法的时间复杂度。voidfunc(intn){inti=1,k=100;while(i<=n){k++;i+=2;}}1.2算法和算法分析85/105

其中基本运算语句是while循环内的语句。

设while循环语句执行的次数为m，i从1开始递增，最后取值为1+2m，有：

i=1+2m≤n即

T(n)=m≤(n-1)/2=O(n)该算法的时间复杂度为O(n)。1.2算法和算法分析基本运算语句voidfunc(intn){inti=1,k=100;while(i<=n){k++;i+=2;}}86/1052.算法空间复杂度分析一个算法的存储量包括形参所占空间和临时变量所占空间等。对算法进行存储空间分析时，只考察临时变量所占空间。算法的临时空间一般也作为问题规模n的函数，以数量级形式给出，记作：S(n)=O(g(n))，其中“O”的含义与时间复杂度中的含义相同。1.2算法和算法分析87/1051.2算法和算法分析intmax(inta[],intn){inti,maxi=0;for(i=1;i<=n;i++){if(a[i]>a[maxi])maxi=i;}returna[maxi];}函数体内分配的变量空间为临时空间，不计形参占用的空间这里的仅计i、maxi变量的空间，其空间复杂度为O(1)88/105为什么算法占用的空间只考虑临时空间，而不必考虑形参的空间呢？voidmaxfun(){intb[]={1,2,3,4,5},n=5;printf("Max=%d\n",max(b,n));}intmax(int[]a,intn){inti,maxi=0;for(i=1;i<=n;i++){if(a[i]>a[maxi])maxi=i;}returna[maxi];}形参a仅仅为b数组的起始地址形参的空间会在调用该算法的算法中考虑89/105若算法所需临时空间相对于输入数据量来说是常数，则称此算法为原地工作或就地工作。若所需临时空间依赖于特定的输入，则通常按最坏情况来考虑。1.2算法和算法分析90/1051.2算法和算法分析【例1.10】分析例1.7和例1.9算法的空间复杂度。

解：这两个算法中，临时分配空间的变量只有固定几个变量，故它们的空间复杂度均为O(1)，即该算法为原时工作算法。voidadd(intn,a[N][N],b[N][N],intc[N][N]){inti,j;

for(i=0;i<n;i++)

{

for(j=0;j<n;j++)

{c[i][j]=0;

for(k=0;k<n;k++)

c[i][j]=c[i][j]+a[i][k]*b[k][j];

}}}voidfunc(intn){inti=1,k=100;

while(i<=n)

{ k++; i+=2;

}}例1.7例1.991/1051.3数据结构程序设计1.3.1数据结构程序设计步骤分析求解问题的数据和求解功能，采用抽象数据类型来描述求解问题，主要包括数据逻辑结构和运算定义。设计逻辑结构对应的存储结构。在存储结构上设计实现运算定义的算法。1.3数据结构程序设计一个数据结构程序用于求解一个数据结构问题。其设计的一般步骤如下：92/105③算法设计②设计存储结构①问题描述ADT

＝逻辑结构＋抽象运算（功能描述）映射存储结构1存储结构n…算法11…算法1m算法n1…算法nk运算实现最佳算法算法分析④算法分析数据结构解决问题的思路93/1051.3.2应用程序的结构1.3数据结构程序设计存储结构基本运算函数应用程序94/105【例1.11】设计实现例1.4功能的完整程序SetApp。1.3数据结构程序设计95/105

问题描述ADTASet{

数据对象：D={di

|0≤i≤n，n为一个正整数}运算的定义： voidcset(&s,a,n)：由含n个元素的数组a创建一个集合s。 voiddispset(s)：输出集合s。 intinset(s,e)：判断元素e是否为集合s中的元素。}ADTBSet{

数据对象：D={si∈ASet|0≤i≤n，n为一个正整数}

运算的定义：voidadd(s1,s2,s3)：s3=s1∪s2

//求集合的并集voidsub(s1,s2,s3)：s3=s1-s2

//求集合的差集voidintersection(s1,s2,s3)：s3=s1∩s2

//求集合的交集}1.3数据结构程序设计96/105采用一个整型数组存放集合的元素。由于C/C++语言中数组并没有一个标识数组中实际元素个数的值，为此用一个整型变量length表示数组中的实际元素个数。typedefstruct //集合结构体类型{intdata[MaxSize]; //存放集合中的元素，其中MaxSize为常量

intlength; //存放集合中