数据结构简明教程（第3版）课件全套 李春葆 第1-9章 概论、线性表-排序

数据结构简明教程（第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; //存放集合中实际元素个数}Set; //将集合结构体类型用一个新类型名Set表示1.3数据结构程序设计

设计存储结构设计集合类型Set如下：97/105

设计运算算法

1.3数据结构程序设计ASet抽象数据类型中的运算算法对应的函数如下：voidcset(Set&s,inta[],intn)//由数组a创建集合s{for(inti=0;i<n;i++)s.data[i]=a[i];s.length=n;}98/1051.3数据结构程序设计voiddispset(Sets) //输出集合s中的所有元素{for(inti=0;i<s.length;i++)printf("%d",s.data[i]);printf("\n");}intinset(Sets,inte) //判断e是否在集合s中{for(inti=0;i<s.length;i++){if(s.data[i]==e)

return1;}return0;}99/1051.3数据结构程序设计BSet抽象数据类型中的运算算法对应的函数如下：voidadd(Sets1,Sets2,Set&s3) //求集合的并集{inti;for(i=0;i<s1.length;i++) //

将集合s1的所有元素

s3s3.data[i]=s1.data[i];s3.length=s1.length;for(i=0;i<s2.length;i++) //

将s2中不在s1中的元素

s3

{

if(!inset(s1,s2.data[i])){s3.data[s3.length]=s2.data[i];s3.length++;}}}100/1051.3数据结构程序设计voidsub(Sets1,Sets2,Set&s3) //求集合的差集{s3.length=0;for(inti=0;i<s1.length;i++) { //将s1中不出现在s2中的元素

s3if(!inset(s2,s1.data[i])){s3.data[s3.length]=s1.data[i];s3.length++;}}}101/105voidintersection(Sets1,Sets2,Set&s3)//求集合的交集{s3.length=0;for(inti=0;i<s1.length;i++)

//将s1中出现在s2中的元素

s3{if(inset(s2,s1.data[i])){s3.data[s3.length]=s1.data[i];s3.length++;}}}1.3数据结构程序设计102/105

设计主函数intmain(){inta[]={1,4,2,6,8};intb[]={2,5,3,6};Sets1,s2,s3;

cset(s1,a,5);

cset(s2,b,4);

printf("集合s1:"); dispset(s1);

printf("集合s2:"); dispset(s2);

add(s1,s2,s3);

printf(“集合s1和s2的并集:”);

dispset(s3);

sub(s1,s2,s3);

printf(“集合s1和s2的差集:”);

dispset(s3);

intersection(s1,s2,s3);

printf(“集合s1和s2的交集:”);

dispset(s3);}1.3数据结构程序设计103/105应用程序SetApp的结构：1.3数据结构程序设计maincsetdispsetinsetaddsubintersectionASetBSet104/105

程序执行结果集合s1:14268集合s2:2536集合s1和s2的并集:1426853集合s1和s2的差集:148集合s1和s2的交集:261.3数据结构程序设计105/105第2章线性表2.1线性表的基本概念2.2顺序表2.3单链表和循环单链表2.4双链表和循环双链表2.5线性表的应用第2章线性表106/1332.1线性表的基本概念2.1.1线性表的定义线性表是由n（n≥0）个相同类型的数据元素组成的有限序列。当n=0时为空表，记为()或Φ.当n>0时，线性表的逻辑表示为（al,a2,…,ai,…,an），也可以用下图所示的逻辑结构图表示。2.1线性表的基本概念a1a2aian……107/133a1a2aian……开始元素尾元素逻辑序号或位置为i逻辑特征：若至少含有一个元素，则只有唯一的开始元素和终端元素除了起始元素外其他元素有且仅有一个前驱元素除了终端结点外其他元素有且仅有一个后继元素2.1线性表的基本概念108/133线性表中的每个元素有唯一的序号（逻辑序号），同一个线性表中可以存在值相同的多个元素，但它们的序号是不同的。如一个整数线性表：（1，3，2，4，2，1，5）序号为1序号为62.1线性表的基本概念109/1332.1.2线性表的基本运算初始化InitList(L)。其作用是建立一个空表L（即建立线性表的构架，但不含任何数据元素）。销毁线性表DestroyList(L)。其作用是释放线性表L的内存空间。求线性表的长度GetLength(L)。其作用是返回线性表L的长度。求线性表中第i个元素GetElem(L,i,e)。其作用是返回线性表L的第i个数据元素。通常线性表List的基本运算如下：2.1线性表的基本概念110/133按值查找Locate(L,x)。若L中存在一个或多个值与x相等的元素，则其作用是返回第一个值为x的元素的逻辑序号。插入元素InsElem(L,x,i)。其作用是在线性表L的第i个位置上增加一个以x为值的新元素，删除元素DelElem(L,i)。其作用是删除线性表L的第i个元素ai。输出元素值DispList(L)。其作用是按前后次序输出线性表L的所有元素值。2.1线性表的基本概念111/133线性表抽象数据类型List=线性表中元素的逻辑结构+基本运算定义2.1线性表的基本概念112/133

【例2.1】利用线性表List的基本运算，设计一个在线性表A中删除线性表B中出现的元素的算法。

解：算法思路：依次检查线性表B中的每个元素x，看它是否在线性表A中。若x在线性表A中，则将其从A中删除。2.1线性表的基本概念113/133voidDelete(List&A,ListB) //A为引用型参数{inti,k;ElemTypex;for(i=1;i<=GetLength(B);i++){x=GetElem(B,i);//依次获取线性表B中的元素，存放在x中

k=Locate(A,x);

//在线性表A中查找x

if(k>0)DelElem(A,k); //若在线性表A中找到了，将其删除

}}线性表的基本运算算法2.1线性表的基本概念114/133

【例2.2】利用线性表List的基本运算，设计一个由线性表A和B中的公共元素产生线性表C的算法。

算法思路：先初始化线性表C，然后依次检查线性表A中的每个元素x，看它是否在线性表B中；若x在线性表B中，则将其插入到线性表C中。2.1线性表的基本概念115/133voidCommelem(ListA,ListB,List&C) //C为引用型参数{inti,k,j=1;ElemTypex;

InitList(C);

for(i=1;i<=GetLength(A);i++)

{x=GetElem(A,i); //依次获取线性表A中的元素，存放在x中k=Locate(B,x); //在线性表B中查找x

if(k>0)

{InsElem(C,x,j);

j++; //若在线性表B中找到了，将其插入到C中

}

}}2.1线性表的基本概念116/1332.2顺序表2.2.1顺序表的定义顺序表是线性表采用顺序存储结构在计算机内存中的存储方式，它由多个连续的存储单元构成，每个存储单元存放线性表的一个元素。顺序表逻辑上相邻的数据元素在内存的存储结构中也是相邻的，不需要额外的内存空间来存放元素之间的逻辑关系。2.2顺序表117/133假定线性表的数据元素的类型为ElemType，在C/C++语言中，顺序表类型声明如下：#defineMaxSize100typedefintElemType;

//假设顺序表中所有元素为int类型typedefstruct{

ElemTypedata[MaxSize]; //存放顺序表的元素

intlength; //顺序表的实际长度}SqList; //顺序表类型2.2顺序表118/133顺序表的示意图如下：

由于顺序表采用数组存放元素，而数组具有随机存取特性，所以顺序表具有随机存取特性。元素a1a2…an…下标01n-1MaxSize-1空闲2.2顺序表119/1332.2.2线性表基本运算在顺序表上的实现1.顺序表的基本运算算法（1）初始化线性表运算算法将顺序表L的length域置为0。voidInitList(SqList&L)

//由于L要回传给实参，所以用引用类型{

L.length=0;}2.2顺序表120/133（2）销毁线性表运算算法

这里顺序表L的内存空间是由系统自动分配的，在不再需要时由系统自动释放其空间。所以对应的函数不含任何语句。voidDestroyList(SqListL){}2.2顺序表121/133（3）求线性表长度运算算法返回顺序表L的length域值。intGetLength(SqListL){

returnL.length;}2.2顺序表122/133（4）求线性表中第i个元素运算算法

在逻辑序号i无效时返回特殊值0（假），有效时返回1（真），并用引用型形参e返回第i个元素的值。intGetElem(SqListL,inti,ElemType&e){if(i<1||i>L.length) //无效的i值返回0

return0;

else

{e=L.data[i-1]; //取元素值并返回1

return1;}}2.2顺序表123/133（5）按值查找运算算法

在顺序表L找第一个值为x的元素，找到后返回其逻辑序号，否则返回0（由于线性表的逻辑序号从1开始，这里用0表示没有找到值为x的元素）。intLocate(SqListL,ElemTypex) {inti=0;

while(i<L.length&&L.data[i]!=x)i++; //查找值为x的第1个元素,查找范围为0～L.length-1

if(i>=L.length)return(0);//未找到返回0

elsereturn(i+1);

//找到后返回其逻辑序号}2.2顺序表124/133（6）插入元素运算算法将新元素x插入到顺序表L中逻辑序号为i的位置（如果插入成功，元素x成为线性表的第i个元素）。当i无效时返回0（表示插入失败）。有效时将L.data[i-1..L.length-1]后移一个位置，在L.data[i-1]处插入x，顺序表长度增1，并返回1（表示插入成功。2.2顺序表125/133元素a1…an…下标0…

i-1

…

n-1均后移一个位置ai…元素a1…an…下标0…

i-1

i

…

nai…x插入元素x2.2顺序表126/133intInsElem(SqList&L,ElemTypex,inti){intj;

if(i<1||i>L.length+1||L.length==MaxSize)return0; //无效的参数ifor(j=L.length;j>=i;j--)//将位置为i的结点及之后的结点后移L.data[j]=L.data[j-1];L.data[i-1]=x; //在位置i处放入x

L.length++; //线性表长度增1

return1;}2.2顺序表127/133算法分析当i=n+1时（插入尾元素），移动次数为0，呈现最好的情况。当i=1时（插入第一个元素），移动次数为n，呈现最坏的情况。2.2顺序表128/133平均情况分析a1a2aian……n+1种插入情况在位置i插入新元素x，需要将ai～an的元素均后移一次，移动次数为n-i+1。假设在等概率下pi（pi=1/(n+1)），移动元素的平均次数为：2.2顺序表129/133插入算法的主要时间花费在元素移动上，所以算法InsElem()的平均时间复杂度为O(n)。2.2顺序表130/133（7）删除元素运算算法

删除顺序表L中逻辑序号为i的元素。在i无效时返回0（表示删除失败）。有效时将L.data[i..length-1]前移一个位置，顺序表长度减1，并返回1（表示删除成功。2.2顺序表131/133均前移一个位置元素a1…an…下标0…

i-1i

…

n-1ai+1…ai元素a1…an…下标0…

i-1…

n-2ai+1…删除元素ai2.2顺序表132/133intDelElem(SqList&L,inti){intj;

if(i<1||i>L.length) //无效的参数ireturn0;

for(j=i;j<L.length;j++) //将位置为i的结点之后的结点前移L.data[j-1]=L.data[j];

L.length--; //线性表长度减1

return1;}2.2顺