第1章算法与数据结构缩减版

第1章算法与数据结构缩减版第一页，共132页。第一章绪论1.1

课程描述1.2什么是数据结构1.3基本概念和术语1.4算法和算法分析

第二页，共132页。课程描述

地位和作用：算法与数据结构课程是计算机专业的一门核心课程，在整个计算机专业教学过程中起着承上启下的作用。第三页，共132页。C语言数据结构软件工程掌握基本编程方法掌握数据组织和数据处理的方法掌握大型软件开发方法学习识字学习写作文学习写小说基本要求课程关系与语文学习过程类比动手能力（上机）第四页，共132页。

知识单元划分：其内容按知识结构可以划分为三个部分：基础知识篇，数据结构篇，基本运算篇。第五页，共132页。

教-学目标：通过本课程的教学，为大家构建数据结构和算法设计两个方面的知识体系；通过本课程的学习，使大家了解和

掌握非数值类问题

求解时所用到的表、树、图等基本模型的特点和使用场合，从而在面对所遇到的问题时，能抽取问题的基本模型，选择合适的数据结构，设计出高效的算法，提高大家的程序设计能力。第六页，共132页。设计一个学生基本信息管理系统。假设某校学生基本信息主要包括：学号，姓名，年龄，性别，出生年月，班级，年级、系、地址，电话，E-mail等。本系统应能对这些基本信息进行管理，具体功能如下：

（课程设计）具有学生信息添加功能

具有学生信息删除功能具有学生信息浏览功能具有学生信息查询功能

：按学号查询

、按姓名查询

具有学生信息统计功能：按学生所在系和班级统计。具有学生信息排序功能

：按所在系-班级-学号采用菜单界面第七页，共132页。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表学生基本信息第八页，共132页。学生信息管理系统（毕业设计）系统要求：采用c/s或b/s模式，数据库根据自己开发的特点可任选；前台可以选择适合的前台设计语言（VB.NET，ASP.NET等）设计要求：

一、登录系统（包含用户名及密码检测）

二、创建合理的数据表，对表的字段值添加合适的约束、默认、规则等

三、数据管理。包括数据添加、数据删除、数据修改

四、查询功能。应包含多种查询功能（固定条件查询，模糊查询等）

五、整个系统的安全、维护及数据的备份

第九页，共132页。问题描述：学校工作总体规划由教务人员在学生信息管理系统中完成对运行教务处所需的基本数据的维护，包括这些信息的增加、修改及对各项信息的变动都将在这进行操作。

新的学年，教务人员首先加入年级信息，然后编排班级，再对来校学生进行基本的信息录入，新生入学后由教务人员在学籍系统中完成新学生信息的维护。

在每个学期开始，教务处根据班级的情况，以班为单位，为每个班级安排一个班主任及对此年级安排一个年级组长，并对各科老师进行安排。

每举行一次考试后由任课老师对成绩进行录入，班主任对本班的成绩汇总。并进行排名，然后年级组长再进行汇总，并对本年级各科成绩及总成绩进行排名。

教务处、年级组长、班主任及任课老师跟据实际情况对录入的成绩进行维护，各位同学对以上录入的信息可以跟据自己的需要进行适当的查询第十页，共132页。功能需求分析

权限功能：系统具有动态的权限分配功能，可按用户权限对用户进行分组。可分为管理员和学生用户。学生用户只能修改自己的个人信息，修改密码，以及查询班级成绩和个人成绩。

录入功能：管理员用户提供对所有信息的录入功能。

查询功能：管理员提供查询的功能，可查询允许范围内的所有信息，以及学生用户可以查询班级成绩。

维护功能：管理员用户提供对所有信息的修改删除功能。

退出功能：结束并关闭系统。本系统适用于中小学校，系统性能力求易于使用，具体有较高的扩展性和可维护性。第十一页，共132页。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表学生基本信息第十二页，共132页。

数据结构是一门研究数据（操作对象）的组织、存储（相互关系）和运算的一般方法的学科。1.1什么是数据结构第十三页，共132页。1.1什么是数据结构第十四页，共132页。计算机文件存储管理第十五页，共132页。上述的问题都是一种数据结构问题。首先，要建立解决该问题的一个数学模型。可选择表结构、树结构、图结构等。其次，要确立计算机如何存储所建模型中的相关数据，数据的存储结构，直接影响算法的选择和效率。接下来，数据结构还要提供每种结构类型所定义的各种运算的算法。第十六页，共132页。数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement):是数据的基本单位，即数据集合中的个体。在计算机程序中通常作为一个整体进行考虑和处理。数据项（DataItem)：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。数据元素亦称元素、节点、顶点或记录等。

1.1.1基本概念和术语第十七页，共132页。数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。数据元素其实就是数据对象中的一个“个体”

例如，201402班为一个学生数据对象，其中的“张三”是一个数据元素，张三所有的属性，如姓名、年龄、性别等就是它的数据项。第十八页，共132页。数据结构(DataStructure)：是指数据元素以及数据元素相互之间的联系。定义：是相互之间存在着某种特定关系的数据元素的集合。因此，可以把数据结构看成是带结构的数据元素的集合。数据结构包括三个方面：数据之间的逻辑结构：数据元素之间的逻辑关系数据的存储结构（物理结构）：数据元素及其关系在计算机存储器中的存储方式以及在这种结构上的运算：施加在该数据上的各种操作。

第十九页，共132页。

（1）线性结构结构中的数据元素之间存在一对一的关系。如线性表、栈、队列。

特点：开始节点和终端节点都是唯一的,除了开始节点和终端节点以外,其余节点都有且仅有一个前驱节点,有且仅有一个后继节点。线性表就是典型的线性结构。1.1.2逻辑结构类型

…逻辑结构：数据之间的相互关系称为逻辑结构，它通常分为四类基本结构。第二十页，共132页。例1学生信息检索系统类似的人事管理、物资管理、商品管理等大量问题都可以抽象出类似的线性数据结构。记录号学号姓名性别专业年级

1980001吴承志男计算机科学与技术98级

2980002李淑芳女信息与计算科学98级

3990301刘丽女数学与应用数学99级

4990302张会友男信息与计算科学99级

5990303石宝国男计算机科学与技术99级

6000801何文颖女计算机科学与技术2000级

7000802赵胜利男数学与应用数学2000级

8000803崔文靖男信息与计算科学2000级

9010601刘丽女计算机科学与技术2001级

10010602魏永鸣男数学与应用数学2001级（a）学生信息表线性表第二十一页，共132页。

（2）树形结构（层次结构）结构中的数据元素之间存在一对多的关系。

特点：开始节点唯一，终端节点不唯一。除终端节点以外，每个节点有一个或多个后续节点；除开始节点外，每个节点有且仅有一个前驱节点。第二十二页，共132页。例2人机对奕问题树……..……..…...…...…...…...第二十三页，共132页。

（3）图形结构结构中的数据元素之间存在多对多的关系。

特点：没有开始节点和终端节点，所有节点都可能有多个前驱节点和多个后继节点。第二十四页，共132页。例3多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图第二十五页，共132页。（4）集合：结构中的数据元素除了同属于一个集合外，别无其它关系。第二十六页，共132页。

为了更确切地描述一种数据结构，通常采用二元组表示：

B=(D,R)

其中，B是一种数据结构，它由数据元素的集合D和D上二元关系的集合R所组成。其中：

D={di|1≤i≤n,n≥0}

R={rj|1≤j≤m,m≥0}

di表示集合D中的第i个节点或数据元素。若n=0，则D是一个空集，因而B也就无结构可言，有时也可以认为它具有任一结构。rj表示集合R中的第j个关系，每个关系用序偶表示。特别地，若m=0，则R是一个空集，表明集合D中的元素间不存在任何关系，彼此是独立的。一种通用的逻辑结构表示方法第二十七页，共132页。序偶<x,y>（x,y∈D）x为第一元素，y为第二元素。x为y的前驱节点。y为x的后继节点。若某个节点没有前驱元素，则称该节点为开始节点；若某个节点没有后继元素，则称该节点为终端节点。

说明：<x,y>表示有向关系，(x,y)表示无向关系。采用离散数学的表示方法。每个关系的用序偶表示：第二十八页，共132页。区号城市名说明010Beijing首都021Shanghai直辖市027Wuhan湖北省省会029Xian陕西省省会025Nanjing江苏省省会City=(D,R)D={010,021,027,029,025}R={r}r={<010,021>,<021,027>,<027,029>,<029,025>}区号为关键字例如，有一个如下表所示的城市表，假设城市名是唯一的，给出其逻辑结构的二元组表示。城市表City中共有5个记录，其逻辑结构的二元组表示如下：第二十九页，共132页。又例如，有如下数据即一个矩阵：

对应的二元组表示为B=(D,R)，其中：

D={2,6,3,1,8,12,7,4,5,10,9,11}

R={r1,r2}其中，r1表示行关系，r2表示列关系

r1={<2,6>,<6,3>,<3,1>,<8,12>,<12,7>,<7,4>,<5,10>,<10,9>,<9,11>}

r2={<2,8>,<8,5>,<6,12>,<12,10>,<3,7>,<7,9>,<1,4>,<4,11>}一个二维数组第三十页，共132页。1.1.3存储结构类型（2）链式存储方法

（3）索引存储方法

（4）散列（哈希）存储方法

（1）顺序存储方法

第9章介绍存储结构（物理结构）：数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。通常有四种不同的存储结构其中最基本的是顺序存储和链式存储。第三十一页，共132页。（1）顺序存储结构：数据元素依次存放在地址连续的存储单元。逻辑结构相邻的数据元素其物理位置也相邻。（用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。）即把所有记录依次存储在一个数组中。第三十二页，共132页。

例

建立一个住院病人押金情况表。住院病人押金情况表包括：姓名、性别、年龄、住院押金。数组下标姓名性别年龄住院押金

0张三m40500．00（13个字节）1李四f50100．00

：：：：：

第三十三页，共132页。元素n……..元素i……..李四、f、50、100.0张三、m、50、500.00000H000DH0000H+(i-1)*13存储地址存储内容顺序存储第三十四页，共132页。元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m顺序存储每个元素所占用的存储单元个数第三十五页，共132页。元素n……..元素i……..元素2元素1存储内容顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。优点：1.存储密度大，空间利用率比链式存储结构高2.在存储操作上：可以随机存取，存取方便。缺点：1.作插入或删除操作时，需移动大量元数。2.空间限制：表的容量难以扩充。长度变化较大时，需按最大空间分配。第三十六页，共132页。（2）链式存储结构：数据元素存放在任何一个可能的存储单元，但对每一个数据元素存储单元，都增加一个存放地址的指针，用此指针来表示数据元素之间的逻辑关系。即把每个记录看作一个结点，让所有结点依次链接。L→张三m40500.00

→李四f50100.00

…第三十七页，共132页。1536元素21400元素11346元素3∧元素41345h数据元素之间逻辑上的联系由指针来体现。第三十八页，共132页。1536元素21400元素11346元素3∧元素4head1346

元素31536

…….

……..

…….1536

元素21400

…….

……..

…….∧

元素413461400

元素11345

指针

存储内容存储地址1345head第三十九页，共132页。1.比顺序存储结构的存储密度小，空间利用率较低

(每个节点都由数据域和指针愈组成)。2.逻辑上相邻的节点物理上不必相邻。3.插入、删除灵活

(不必移动节点，只要改变节点中的指针)。4.没有空间限制5.不能随机访问链接存储结构特点：第四十页，共132页。索引存储：类似链式存储，除了数据存放的存储单元外，还另外设立一个索引表，来指示数据元素所在的存储单元。不同之处是索引项由（关键字，地址）组成。散列存储：数据存放也是任意的在存储单元中，和链式不同的是它不是依靠指针来指示数据元素，而是通过一个散列函数来寻找数据元素所存放的位置（即物理地址）。1.1.3存储结构类型第四十一页，共132页。相关运算：在所定义的结构上进行运算，通常有查找、插入、删除、构建等：

1.查找:在所定义的结构上查找指定数据元素的位置，并返回其值。

2.插入：在指定位置插入一个新的数据元素，并保证插入后仍保持其原有结构的特性。

3.删除：删除指定位置的数据元素，并保证删除后仍保持其原有结构的特性。

4.构建：构建存储数据元素的初始结构。。。。。。。第四十二页，共132页。1．数据的逻辑结构2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构B．非线性结构A顺序存储B链式存储线性表栈队树形结构图形结构数据结构的三个方面(亦称物理结构)第四十三页，共132页。

例1.1设计一个学生基本信息管理系统。假设某校学生基本信息主要包括：学号，姓名，性别和班号。学生表如表1.1所示。本系统应能对这些基本信息进行管理，具体功能如下：

具有学生信息添加功能

具有学生信息删除功能具有学生信息浏览功能具有学生信息查询功能

：按学号查询

、按姓名查询

逻辑结构存储结构运算实现第四十四页，共132页。学号姓名性别班号1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901表1.1学生表

逻辑结构表示1（表）（1）逻辑结构这个系统中处理的数据元素是学生记录，每个数据元素由四个数据项（即学号、姓别、性别）组成。第四十五页，共132页。

该表中的记录顺序反映了数据元素之间的逻辑关系,为线性关系。用学号标识每个学生记录，这种逻辑关系可以表示为：

<1,8>,<8,34>,<34,20>,<20,12>,<12,26>,<26,5>

其中尖括号“<ai,ai+1>”表示元素ai和ai+1之间是相邻的，即ai在ai+1之前，ai+1在ai之后。逻辑结构表示2（定义）B=(D,R)D={1,8,34,20,12,26,5}R={r}r={<1,8>,<8,34>,<34,20>,<20,12>,<12,26>,<26,5>第四十六页，共132页。

数据在计算机存储器中的存储方式就是存储结构。

逻辑结构存储结构映射映射应满足两个条件：存储元素存储关系第四十七页，共132页。存放学生表的结构体数组Stud定义为：

struct{ intno;//存储学号

charname[8];//存储姓名

charsex[2];//存储性别

charclass[4];//存储班号

}Stud[7]={{1,“张斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};

C/C++语言中，通常采用结构体数组和链表两种方式实现其存储结构。（2）存储结构第四十八页，共132页。

结构体数组Stud各元素在内存中顺序存放，即第i（0≤i≤6）个学生对应的元素Stud[i]存放在元素Stud[i+1]之前，Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男张斌1Stud[0]Stud[6]Stud数组起始地址1.顺序存储结构表示第四十九页，共132页。链表首节点地址head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧

学生表构成的链表如右图所示。其中的head为第一个数据元素的指针。

学生表构成的链表2.链式存储结构表示第五十页，共132页。存放学生表的链表的节点类型StudType声明为：typedefstructstudnode{intno; //存储学号

charname[8]; //存储姓名

charsex[2]; //存储性别

charclass[4]; //存储班号

structstudnode*next; //存储指向下一个学生的指针}StudType；StudType*head;2.链式存储结构定义1张斌男99018刘丽女9902第五十一页，共132页。对于“学生表”这种数据结构，可以进行一系列的运算：（3）运算实现增加一个学生记录；删除一个学生记录；查找性别为“女”的学生记录；查找班号为“9902”的学生记录；……第五十二页，共132页。

例如，查找学号为20的学生的姓名：对于Stud数组：从Stud[0]开始比较，Stud[0].no不等于20，再与Stud[1].no比较，…，直到Stud[3].no等于20，返回Stud[3].name。

9902男陈华20…9901男张斌1Stud[0]Stud[3]i＝3运算的实现过程1第五十三页，共132页。

对于head为首节点指针的链表：从p=head所指节点开始比较，p->no不等于20，从它的next得到下一个节点的地址，再与下一个节点的no域比较，…，直到某节点的no域等于20，返回其p->name域。head1张斌男99018刘丽女990234李英女990120陈华男990212王奇男990126董强男99025王萍女9901∧p运算的实现过程2第五十四页，共132页。结论：同一逻辑结构可以对应多种存储结构。同样的运算，在不同的存储结构中，其实现过程是不同的。第五十五页，共132页。

（1）数据类型是高级程序设计语言中的一个基本概念，它是一个值的集合和在这个集合上定义的一组操作的总称。高级程序语言中，必须对程序中出现的每个变量、常量或表达式,明确说明它们所属的数据类型。不同类型的变量，其所能取的值的范围不同，所能进行的操作不同。它和数据结构的概念密切相关。分两类：原子类型和结构类型。例1、在FORTRAN语言中，变量的数据类型有整型、实型、和复数型。例2、在C语言中：原子类型：整型、浮点型、字符型构造数据类型：数组、结构、联合、指针、枚举型、自定义1.1.4数据结构和数据类型

第五十六页，共132页。

如C/C++中的int就是整型数据类型。它是所有整数的集合（在16位计算机中为－32768~32767的全体整数）和相关的整数运算（如＋、－、＊、／等）。inti=2,j=5,k;k=i+j;...因为i、j和k都属于int，而int提供了各种运算，所以可以进行相应运算。inti=9999999999;i**;第五十七页，共132页。构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;第五十八页，共132页。

抽象数据类型的表示和实现

抽象数据类型ADT

（AbstractDataType）

：从问题数学模型中抽象出来的逻辑结构和在逻辑结构上的一组运算，不考虑计算机的具体存储结构和运算的具体实现算法（与计算机无关）。

抽象数据类型=逻辑结构＋抽象运算

抽象数据类型实质上就是描述一个求解问题本身,计算机人员就是在理解问题基础上实现用计算机求解问题的过程。它由用户来定义，用以表示应用问题的数据类型，抽象数据类型由基本的数据类型组成，并包括一组相关的服务（或称操作）用三元组表示和描述如下：（Ｄ，Ｓ，Ｐ）

D是数据对象；S是数据的关系集合；P是对数据的基本操作。第五十九页，共132页。

抽象数据类型的表示和实现例复数的抽象数据类型表示和实现如下：ADTComplex{数据对象D

：

D={e1,e2|e1,e2均为实数}数据关系S

：

S={<e1,e2>|e1是复数的实数部分，e2是复数的虚数部分}基本操作P：

AssignComplex(&z,v1,v2)：构造复数Z。

DestroyComplex(&z)：复数z被销毁。

GetReal(z,&real)：返回复数z的实部值。

GetImag(z,&Imag)：返回复数z的虚部值。

Add(z1,z2,&sum)：返回两个复数z1、z2的和。}ADTComplex复数形式：e1+e2i或（e1，e2）第六十页，共132页。

数据结构侧重于解决问题的策略和方法，即研究算法。它不但要求给出问题的一种算法，还要求算法的时空效率高、算法结构和可读性好、容易验证等等。第六十一页，共132页。1.2.1什么是算法

数据元素之间的关系有逻辑关系和物理关系，对应的操作有逻辑结构上的操作功能和具体存储结构上的操作实现。即具体存储结构上的操作实现步骤或过程。属ADT的一部分算法实现1.2算法及其描述

第六十二页，共132页。

1.2算法和算法分析1.2.1什么是算法算法：是对特定问题求解步骤的一种描述。算法是指令的有限序列，其中每一条指令表示一个或多个操作。算法的五个特性：ïïïîïïïíì输出，即为算法的功能一个算法有一个或多个—输出输入一个算法有零个或多个—输入所有操作都可以通过有限次的运算实现—可行性在任何条件下，算法都只有一条执行路径算法，只有一个入口和一个出口。确定性一个算法必须在执行有限步骤之后结束有穷性——第六十三页，共132页。第六十四页，共132页。例

一个不超过100次计数的算法

n=1;s=0;while(n<=100){s+=n;n++;}

输出n的值；例

一个不是算法的例子

n=1;while(n>0)

{n=n+1;}

输出n的值；第六十五页，共132页。例如，考虑下列两段描述：（1）描述一

voidexam1() {intn＝2; while(n%2＝＝0) n＝n+2; printf("%d\n",n); }华中科大考研题

（2）描述二

voidexam2() {intx,y; y=0; x=5/y; printf(“%d,%d\n”,x,y); }这两段描述均不能满足算法的特征，试问它们违反了哪些特征？解：（1）算法是一个死循环，违反了算法的有穷性特征。（2）算法包含除零错误，违反了算法的可行性特征。思考题：

算法和程序有什么不同？第六十六页，共132页。(1)预定义常量和类型的说明；(2)数据结构的表示（存储结构）用类型定义(typedef)描述。数据元素类型约定为ElemType，由用户在使用这个数据类型时自行定义；(3)基本操作的算法所用的函数描述形式；(4)赋值语句；(5)选择语句；(6)循环语句；(7)结束语句；(8)输入和输出语句；(9)注释；(10)基本函数；(11)关于逻辑运算的约定；

1.2.2算法描述本书中采用C/C++语言描述算法。三种描述算法的方式：自然语言（例1.7）、伪代码、程序流程图第六十七页，共132页。补充1：C语言指针讲解第六十八页，共132页。

1.2.2算法描述补充2：引用

C++语言中提供了一种引用运算符“&”，引用是个别名，当建立引用时，程序用另一个已定义的变量或对象（目标）的名字初始化它，从那时起，引用作为目标的别名而使用，对引用的改动实际就是对目标的改动。

注意：TurboC不支持引用类型，VC++、DevC++支持引用类型。第六十九页，共132页。“引用”的概念例如：

inta=4; //a为普通的整型变量

int&b=a;//b是a的引用变量这里说明b变量是变量a的引用，b也等于4，之后这两个变量同步改变。当a改变时b也同步改变，同样，当b改变时a也同步改变。第七十页，共132页。voidmain(){inta=2;int&b=a;printf("a=%d,b=%d\n",a,b);b++;printf("a=%d,b=%d\n",a,b);a++;printf("a=%d,b=%d\n",a,b);}//输出：a=3,b=3//输出：a=4,b=4//输出：a=2,b=2第七十一页，共132页。void

fun1(intn){intm=2;

fun2(m);

printf(“%d\n”,m);}voidfun2(int

x){x++;printf(“%d\n”,x);}实参普通形参fun1(m)fun2(x)实参到形参单向值传递普通的参数传递第七十二页，共132页。voidfun1(intn){intm=2;

fun2(m);printf(“%d\n”,m);}voidfun2(int&x){x++;printf(“%d\n”,x);}实参引用型形参fun1(m)fun2(x)实参到形参单向值传递引用类型的参数传递形参回传给实参，实参和形参同步发生改变第七十三页，共132页。引用与指针的区别首先，引用不可以为空，但指针可以为空。

引用是对象的别名，引用为空——对象都不存在，怎么可能有别名！故定义一个引用的时候，必须初始化。而声明指针是可以不指向任何对象，也正是因为这个原因，使用指针之前必须做判空操作，而引用就不必。其次，引用不可以改变指向，对一个对象“至死不渝”，但是可以改变初始化对象的内容。而指针可以改变指向，指向其它对象。再次，引用的大小是所指向的变量的大小，因为引用只是一个别名而已；指针是指针本身的大小，4个字节。第七十四页，共132页。

编写一个函数swap1(x,y)，当执行语句swap1(a,b)时，交换a和b的值。

voidswap1(intx,inty){inttmp;tmp=x;x=y;y=tmp;}

注意：a和b的值不会发生了交换。第七十五页，共132页。

为此，采用指针的方式来回传形参的值，需将上述函数改为：

voidswap2(int*x,int*y){

inttmp;tmp=*x; //将x的值放在tmp中 *x=*y; //将x所指的值改为*y*y=tmp；//将y所指的值改为tmp}

上述函数的调用改为swap2(&a,&b)，显然远不如采用引用方式简洁。所以本书后面很多算法都采用引用形参。第七十六页，共132页。

引用常用于函数形参中，采用引用型形参时，在函数调用时将形参的改变回传给实参，例如，有如下函数（其中的形参均为引用型形参）：

void

swap(int&x,int&y)//形参前的“&”符号不是指针运算符

{inttmp=x;x=y;y=tmp}

当用执行语句swap(a,b)时，a和b的值发生了交换。第七十七页，共132页。#include

<iostream>

using

namespace

std;

int

main()

{

int

iv;

//正确很正常的声明了一个整型变量

int

iv2

=

1024;

//正确很正常的声明了一个整型变量，同时初始化了这个变量

int

iv3

=

399;

//正确同上

int

&reiv;

//错误声明了一个引用，但引用不能为空，必须同时初始化

int

&reiv2

=

iv;

//正确声明了一个引用&reiv2，同时初始化了它，也就是reiv2是iv的别名

int

&reiv3

=

iv;

//正确同上

int

*pi;

//正确声明了一个整形指针，但是并没有定义这个指针所指向的地址

*pi

=

5;

//错误指针pi并没有指向实际的地址。在这种情况下就给他赋值是错误的，因为赋得值不知道该放到哪里去。pi没有指向，不可以对其赋值。

判断语句是否正确第七十八页，共132页。指针指向一块内存，它的内容是所指内存的地址；而引用则是某块内存的别名，引用不改变指向。

pi

=

&iv3;

//正确指针pi指向iv3的实际地址

const

double

di;

//错误const常量赋值时，必须同时初始化。本地的const常量必须在第一次声明时就初始化。

const

double

maxWage

=

10.0;

//正确const常量赋值并同时初始化

const

double

minWage

=

0.5;

//正确同上

const

double

*pc

=

&maxWage;

//正确const常量指针赋值并同时初始化

cout

<<

pi;

return

0;

}

第七十九页，共132页。1.3算法分析

1.3.2算法时间复杂度分析

1.3.3算法空间复杂度分析

1.3.1算法设计的目标第八十页，共132页。如何估算算法的好坏？第八十一页，共132页。第八十二页，共132页。1.3.1算法设计的目标算法设计应满足以下几条目标：（1）正确性要求算法能够正确地执行预先规定的功能和性能要求。这是最重要也是最基本的标准。（2）可使用性要求算法能够很方便地使用。这个特性也叫做用户友好性。（3）可读性算法应该易于人的理解，也就是可读性好。为了达到这个要求，算法的逻辑必须是清晰的、简单的和结构化的。第八十三页，共132页。求三个数中的最大值和最小值第八十四页，共132页。（4）健壮性要求算法具有很好的容错性，即提供异常处理，能够对不合理的数据进行检查。不经常出现异常中断或死机现象。

voidexam2() {intx,y; y=0; x=5/y; printf(“%d,%d\n”,x,y); }第八十五页，共132页。算法的效率：即算法的执行时间，依据算法编制成程序后在计算机中运行时所消耗的时间。算法存储量：即算法执行过程中所需的最大存储空间。依据算法编制成程序后在计算机中所占存储量的大小。（5）高效率与低存储量需求

效率和低存储量这两者都与问题的规模有关。第八十六页，共132页。通常有两种衡量算法效率的方法:

事后统计法事前分析估算法1.3.2算法效率分析第八十七页，共132页。算法描述的语言不同算法执行的环境不同其他因素所以不能用绝对执行时间进行比较。

同一问题可以采用多种算法实现。如何比较算法执行效率？第八十八页，共132页。和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度第八十九页，共132页。

一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。第九十页，共132页。1．程序运行时所需输入的数据总量。2．对源程序进行编译所需时间。3．计算机执行每条指令所需时间。4．程序中的指令重复执行的次数。程序在计算机上运行所耗时间取决于：1.算法时间复杂度分析（运行时间)：与问题的规模有关第九十一页，共132页。算法的时间复杂度：通常把算法中包含基本运算次数的多少称为算法的时间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数。是问题规模n的某个函数，记作

T(n)=O(f(n))O的定义：f(n)是正整数n的函数，如果存在两个正常数c和n0，使得当n≧n0时，有T(n)≦cf(n)。

则记作T(n)=O(f(n))

1.算法时间复杂度分析

第九十二页，共132页。

也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。例如，T(n)=3n2-5n+10000=O(n2)本质上讲，是一种最高数量级的比较第九十三页，共132页。

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如n++等）构成的，则算法时间取决于两者的综合效果。1.算法时间复杂度分析

控制语句1原操作控制语句n原操作…一个算法的构成算法=控制结构+基本操作(基本数据类型的操作)第九十四页，共132页。一般情况下，f(n)是通过算法中基本运算（原操作）重复执行最多的次数来度量。通常被视为算法基本运算的一般是最深层循环内的语句。频度：是指算法中某条语句重复执行的次数。1.算法时间复杂度分析

第九十五页，共132页。例如：voidfun(inta[],intn){inti;for(i=0;i<n;i++)a[i]=2*i;for(i=0;i<n;i++)printf(“%d“,a[i]);printf(“\n”);}如何估算算法的时间复杂度？算法的执行时间=∑(基本操作的执行次数×基本操作的执行时间)第九十六页，共132页。基本操作的执行时间

与

基本操作执行次数之和

成正比。从算法中选取一种对于所研究的问题来说是基本操作的操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。如何估算算法的时间复杂度？算法的执行时间=∑(基本操作的执行次数×基本操作的执行时间)第九十七页，共132页。一个没有循环的算法的基本运算次数与问题规模n无关，记作O(1)，也称作常数阶。一个只有一重循环的算法的基本运算次数与问题规模n的增长呈线性增大关系，记作O(n)，也称线性阶。其余常用的还有平方阶O(n2)、立方阶O(n3)、对数阶O(log2n)、指数阶O(2n)等。第九十八页，共132页。

常见函数的增长率常见函数的时间复杂度按数量递增排列及增长率。常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nlog2n)平方阶O(n2)立方阶O(n3)……k次方阶O(nk)指数阶O(2n）O(n!)O(nn)第九十九页，共132页。例１、for(i=1;i<=n;++i)for(j=1;j<=n;++j){c[i][j]=0;for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}由于是一个三重循环，每个循环从1到n，则总次数为:(n+1)+n(n+1)+n2+n2(n+1)+n3=2n3+3n2+2n+1最深层循环的语句执行次数：n3时间复杂度为T(n)=O(n3)第一百页，共132页。例２、{++x;s=0;}将x自增看成是基本操作，则语句频度为１，即时间复杂度为Ｏ(1)如果将s=0也看成是基本操作，则语句频度为２，其时间复杂度仍为Ｏ(1)，即常数阶。例３、for(i=1;i<=n;++i){++x;s+=x;}

语句频度为：2n其时间复杂度为：O(n)

即时间复杂度为线性阶。第一百零一页，共132页。例４、for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}语句频度为：2n2其时间复杂度为：O(n2)即时间复杂度为平方阶。第一百零二页，共132页。

例1.8

求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。+第一百零三页，共132页。

例1.8

求两个n阶方阵的相加C=A+B的算法如下,分析其时间复杂度。

#defineMAX20//定义最大的方阶

voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}

该算法中的基本运算是两重循环中最深层的语句C[i][j]=A[i][j]+B[i][j]，分析它的频度，即：

T(n)=n+1+n(n+1)+n2=O(n2)+第一百零四页，共132页。例分析以下算法的时间复杂度。int

fun(intn){inti,j,k,s;s=0;for(i=0;i<=n;i++)for(j=0;j<=i;j++) for(k=0;k<=j;k++)

s++;

return(s);}基本语句或基本操作

解：该算法的基本操作是语句s++，其频度：

T(n)==O(n3)则该算法的时间复杂度为O(n3)。第一百零五页，共132页。

解：对于while循环语句，设执行的次数为m，i从0开始递增1，直到m为止，有：

s=0+1+2+…+(m-1)=m(m-1)/2，并满足s=m(m-1)/2<n，则有m＜。

T(n)=O()

所以，该算法的时间复杂度为O()。例

分析以下算法的时间复杂度。voidfunc(intn){inti=0,s=0;while(s<n){i++;s=s+i;}}基本语句第一百零六页，共132页。

例1.10

有如下算法：

voidfun(inta[],intn,intk)//数组a共有n个元素

{ inti; if(k==n-1) for(i=0;i<n;i++)

//n次

printf("%d\n",a[i]); else {for(i=k;i<n;i++)

//n-k次

a[i]=a[i]+i*i;

fun(a,n,k+1); }}

调用上述算法的语句为fun(a,n,0)，求其时间复杂度。第一百零七页，共132页。

解：设fun(a,n,0)的时间复杂度为T(n)，则fun(a,n,k)的执行时间为T1(n,k)，由fun()算法可知：

T1(n,k)=n

当k=n-1时

T1(n,k)=(n-k)+T1(n,k+1)其他情况则

T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)

=…=n+(n-1)+…+2+T1(n,n-1)

=n+(n-1)+…+2+n

=O(n2)

所以调用fun(a,n,0)的时间复杂度为O(n2)。

第一百零八页，共132页。有的情况下，算法中基本操作重复执行的次数还随问题的输入数据集不同而不同。例如：

Voidbubble-sort(inta[]，intn)for(i=n-1,change=TURE;i>1&&change;--i){change=false;for(j=0;j<i;++j)if(a[j]>a[j+1]){

a[j]←→a[j+1];change=TURE}}最好情况：0次。最坏情况：1+2+3+…+n-1=n(n-1)/2平均时间复杂度为:O(n2)，即所有可能数据的期望值∑PiCi第一百零九页，共132页。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出,记作：S(n)=O(g(n))1.3.3算法空间复杂度分析：所占存储容量

若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。若所需存储量依赖于特定的输入，则通常按最坏情况考虑。(见P16例1.12)算法的存储量包括:输入数据所占空间程序本身所占空间辅助变量所占空间第一百一十页，共132页。1.4数据结构＋算法＝程序

《数据结构＋算法＝程序》的作者：N.Wirth（1934年～），瑞士计算机科学家，1960年获加利福尼亚大学伯克利分校博士学位。曾任斯坦福大学、苏黎世联邦理工学院教授。发明多种计算机语言（包括Pascal、Modula和Oberon等），并为软件工程领域作出过开拓性的贡献。于1980年获得计算机科学界最高奖－图灵奖（）。程序是由数据结构和算法组成的，程序设计的本质是对要处理的问题选择好的数据结构，同时在此结构上施加一种好的算法。第一百一十一页，共132页。1.4.1程序和数据结构

沃思指出：程序就是在数据的某些特定的表示方法和结构的基础上，对抽象算法的具体表述，所以说程序离不开数据结构。

程序设计语言：

类型定义与对象说明和语句——>数据结构（主要部分）

语句——>算法（描述程序的行为）第一百一十二页，共132页。算法是对特定问题求解步骤的描述，它是指令的有限序列（与计算机无关）。

例：求1*2*3*4*5

步骤1：先求1*2，得到结果2。

步骤2：将步骤1得到的乘积2再乘以3，得到结果6。

步骤3：将步骤2得到的乘积6再乘以4，得到结果24。

步骤4：将步骤3得到的乘积24再乘以5，得到最后结果120。1.4.2算法和程序第一百一十三页，共132页。算法与程序的关系

算法和程序都是指令的有限序列，算法和程序的区别主要在于：

(1)在语言描述上，程序必须是用规定的程序设计语言来写，而算法很随意；自然语言、程序框图和程序语句是算法的三种表示方法.

(2)在执行时间上，算法所描述的步骤一定是有限的，而程序可以无限地执行下去。

(3)算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序1.4.2算法和程序第一百一十四页，共132页。1.4.3算法和数据结构解决问题的过程：分析问题——>抽取数据及其结构——>建立抽象数据类型——>设计算法，实现数据结构——>编写程序，求解的问题可以通过抽象数据类型描述，它由数据的逻辑结构和抽象运算两部分组成。算法和数据结构的关系第一百一十五页，共132页。1.4.3算法和数据结构一种数据的逻辑结构可以映射成多种存储结构，抽象运算在不同的存储结构上实现可以对应多种算法，在同一种存储结构上实现也可能有多种算法，通过算法的时间复杂度和空间复杂度等分析，可以得到好的算法。数据的逻辑结构数据的存储结构对应多种算法第一百一十六页，共132页。好算法与以下因素有关：算法的正确性、可读性和可维护性等。算法的时间和空间复杂度。第一百一十七页，共132页。（1）数据上的算法决定