《数据结构》课件(C语言)new

主讲：吴婷婷南京信息工程大学计算机与软件学院

数据结构写在前面的话本课程学习的是什么？学习在思考问题时，不仅按人的逻辑方式思考，也按计算机的逻辑思维方式思考学习在解决问题时，不仅考虑人的处理方式，也要考虑计算机的处理方式我是你亲密的朋友，你要理解和尊重我，也要能被我理解。对你而言，是一场有趣的思维体操；对我而言，是一座顺畅沟通的桥梁写在前面的话如何和我联系？办公室：电子楼201办公电话：Mobilmail：christina_tingting@126.com

考试方式闭卷笔试平时成绩(30%)到课率作业上机实习期终考试（70%）课程设计（单独测试）设计报告（30%），程序（40%），答辩（30%）《数据结构》课程概况英文名称

DataStructure先修课程离散数学,计算机高级语言后续课程数据库原理与应用,操作系统,软件工程等授课学时

48学时上机实践

16机时教学对象计算机科学与技术专业,信息工程专业参考文献教材：严蔚敏，吴伟民。数据结构（C语言版），清华大学出版社，2010.4配套习题：数据结构题集（C语言版），严蔚敏等编，清华大学出版社，2010.4参考教材：数据结构（C++版），王艳华，戴小鹏编，武汉大学出版社，2007.4数据结构（C++）复习题要与上机指导，王艳华，戴小鹏，武汉大学出版社，2007.4数据结构考研指导，李春葆等编，清华大学出版社，2003.1注意：请参看相关的C/C++的教材课程地位本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、数据库系统、人工智能系统和其它系统程序的重要基础，是一门核心课程，对培养计算机及有关专业人才具有重要意义。

1.熟悉各类典型的数据结构的逻辑特性、不同的存储方法与存储量、算法及效率的关系、定义于数据结构上的主要基本操作及其算法，了解它们的应用环境,为学习后续课程奠定基础；

2.进一步提高软件设计和编程水平；

3.增强根据求解问题性质,选择合适的数据结构及控制求解算法的时间与空间复杂性的能力。课程要求知识体系数据结构在软件从业人员的知识与技能结构中的地位系统分析员需求分析系统设计高级程序员详细设计程序设计程序员、初级程序员程序设计程序测试数据结构在软件从业人员的知识与技能结构中的地位编程语言解决问题的思想

任何受过专业训练的程序员，对“数据结构”这门课程中涉及到的各种数据结构都不会陌生，但是在实际的编程工作中，大部分的数据结构都不会用到，而且也永远都不会用到。虽然如此，深入地理解基本数据结构的概念和实现细节，仍然是每个程序员的任务。这不仅仅是因为，掌握这些知识将有利于更加正确和灵活地应用它们，而且也是因为，对于语言背后的实现细节的求知欲是一个优秀程序员的素质。

--摘自《最基础的数据结构》为什么要学数据结构？数据结构研究什么？重新理解算法。如何分析算法的优劣？第一章概论第一问题：

为什么要学数据结构Data

Structure？电子计算机的主要用途：早期：主要用于数值计算。后来：

处理逐渐扩大到非数值计算领域（能处理多种复杂的具有一定结构关系的数据）。1）数值问题例1已知：游泳池的长len和宽wide，求面积area◆设计求解问题的方法◆

编程main(){ intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);}◆建模型：

问题涉及的对象：游泳池的长len宽wide，面积area；

对象之间的关系：area=lenwide数值计算解决问题的一般步骤：在计算机发展初期，人们主要应用计算机来完成科学计算，即处理数值计算问题，对于这类问题，可以通过抽象出合适的数学模型，然后设计一个相应的算法来解决。数学模型→选择计算机语言→编出程序→测试→最终解答。数值计算的关键是：如何得出数学模型（方程）？非数值计算问题：随着计算机应用领域的不断扩大，计算机更多地应用于处理非数值计算问题，这类问题涉及到数据元素间复杂的相互关系，一般无法用数学方程来描述。2）非数值问题例2已知某级学生情况,要求分班按入学成绩排列顺序。

学号姓名性别出生日期籍贯入学成绩所在班级 00201杨润生男82/06/01广州56100计算机2

00102石磊男83/12/21汕头51200计算机1

00202李梅女83/02/23阳江53200计算机200301马耀先男82/07/12广州50900计算机3在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型称为线性模型。例

电话号码查询问题：（1）按顺序存储方式：须遍历表（2）按姓氏索引方式：索引要写出好的查找算法，取决于这张表的结构及存储方式。电话号码表的结构和存储方式决定了查找（算法）的效率。非数值计算问题：例

田径赛的时间安排问题（无向图的着色问题）：设有六个比赛项目，规定每个选手至多可参加三个项目，有五人报名参加比赛（如下表所示）设计比赛日程表，使得在尽可能短的时间内完成比赛。非数值计算问题：（1）设用如下六个不同的代号代表不同的项目：跳高跳远标枪铅球100米200米A B CDE F（2）用顶点代表比赛项目不能同时进行比赛的项目之间连上一条边。（3）某选手比赛的项目必定有边相连（不能同时比赛）。非数值计算问题

----田径赛的时间安排问题解法姓名项目1项目2项目3丁一

A

B

E马二

C

D

张三

C

E

F李四

D

F

A王五

B

FAEBFDC比赛时间比赛项目1A，C2B，D3E4F只需安排四个单位时间进行比赛多叉路口交通灯管理问题

为了设计一个交通信号灯的管理系统，首先需要分析一下所有车辆的行驶路线的冲突问题。这个问题可以归结为对车辆的可能行驶方向作某种分组，对分组的要求是使任一个组中各个方向行驶的车辆可以同时安全行驶而不发生碰撞。

根据这个路口的实际情况可以确定13个可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D。可以把A→B简写成AB，用一个结点表示，在不能同时行驶问题分析:的结点间画一条连线(表示它们互相冲突)，便可以得到如右图所示的表示。这样得到的表示可以称之为“图”。例3多叉路口交通灯管理问题ABACADBABCBDDADBDCEAEBECED图CEDAB求解非数值计算的问题：主要考虑的是设计出合适的数据结构及相应的算法。即：首先要考虑对相关的各种信息如何表示、组织和存储？因此，可以认为：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。现实中对象之间的关系线性关系：如列车中各车箱之间的关系、排队买车票人之间的关系、一叠盘子中各盘子之间的关系等。层次关系：如学校的组织结构、人的辈分关系等。网状关系：如城市铁路交通网、电话网、计算机网络等。实际问题中对象之间的关系——

学生成绩管理学号姓名大学英语C语言数据结构…A07001王萍908595…A07002马玲808590…A07003张兰959199…A07004李建708486…A07005黄勇827678…:：：：：：A07001王萍908595学生成绩表A07002马玲808590A07003张兰959199A07004李建708486A07005黄勇827678关系：线性特征：一个直接前趋，一个直接后继例2书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表实际问题中对象之间的关系例2：“井字棋”的人机对弈××OO××OOO××OOO××OOO××OOO××OOO××O×OO××OO×O…×××OOO×××OOO关系：树型特征：一个直接前趋，多个直接后继…实际问题中对象之间的关系例3：交通图的最短路径问题A4A2A6A3A1A554798612关系：图型特征：多个直接前趋，多个直接后继第一问题：

为什么要学数据结构？解决非数值问题的首要任务是选取一种合适的数据结构表示该问题，然后才考虑如何编写有效的算法。计算机处理的大多属于非数值计算问题。什么是数据结构简义：数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

数据结构是计算机科学专业的一门核心课程，它的研究对象为问题求解方法、程序设计方法及一些典型数据结构的算法。

《数据结构》在计算机科学技术中是一门综合性的专业基础课，计算机科学技术各个领域都要用到多种数据结构。在我国计算机及相关专业的教学计划中，它是核心课程之一。在我院教学计划中，《数据结构》已成为我院各计算机科学与技术专业和信息工程专业必修课程。其基本内容包括：基本数据结构，抽象数据类型，递归算法，复杂性分析，排序和查找，算法分析等。数据结构在计算机科学中所处的地位：什么是数据结构数据结构程序设计算法问题求解程序编写什么是数据结构“好”数据结构＋“好”算法＝“好”程序良好、合理的数据结构清晰、实用的算法简洁、高效的程序什么是数据结构第二问题

数据结构研究什么？数据结构涵盖的内容客观事物的符号表示，是计算机程序加工的原料。它是信息的载体，能被计算机识别、存储和加工处理。随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴。●数据(Data)1、基本概念和术语是数据的基本单位，即数据这个集合中的一个实体。通常作为整体进行考虑和处理。有些情况下，数据元素也称为元素、结点、顶点、记录等。一个数据元素可能仅含一个数据项，亦可包含若干个数据项。●数据元素(DataElement)1、基本概念和术语●数据项(DataItem)亦称字段、域,数据项是具有独立含义的不可分割的最小标识单位。●数据对象(DataObject)性质相同的数据元素的集合，是数据的一个子集。数据对象可以是有限的，也可以是无限的。如：整数对象是集合N={0,±1,±2,….}；字母字符的集合等。1、基本概念和术语●数据类型(DataType)简称类型，一个值的集合和定义在值集上的一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。原子类型(AtomicType)：如C中的标量类型（整型、实型、字符型）以及指针类型等。结构类型(StructuredType）：亦称结构类型，如C中的数组、记录、文件类型等。抽象数据类型(AbstractDataType,ADT）：下面有专门介绍。1、基本概念和术语●数据处理(DataProcessing)对数据进行诸如查找、插入、删除、合并、排序、统计、简单计算、输入、输出等的操作过程。1、基本概念和术语●结构(Structure)相互关联的元素之间的构成关系。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。

定义：是相互之间存在一种或多种特定关系的数据元素的集合。

组成：由某一数据对象及该对象中所有数据成员之间的关系组成。DataStructure

=（DataObject,Relationships）

数据结构是指在程序中信息的逻辑组织方法，一般来说，这种方法也受到所选择的程序设计语言的限制。

●数据结构(DataStructure)1、基本概念和术语数据结构可描述为DS=（D，R）有限个数据元素的集合有限个节点间关系的集合

数据的逻辑结构：指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。数据的物理结构：亦称数据的物理结构、存储结构，是指数据在计算机内的表示方法，即存储形式。●数据结构(DataStructure)1、基本概念和术语1）数据元素之间的逻辑关系，亦称数据的逻辑结构；●数据结构的三个方面（数据结构的三要素）2）数据元素及其关系在计算机存储器内的表示，亦称数据的存储结构；3）数据的运算，即对数据施加的操作。2、基本概念和术语

1．数据的逻辑结构

2、数据的存储结构3、数据的运算：检索、排序、插入、删除、修改等。A．线性结构

B．非线性结构A顺序存储

B链式存储线性表栈队树形结构图形结构数据结构的三个主要问题数据结构可描述为DS=（D，R）我和你们的逻辑结构是师生结构我和你们在教室中的位置根据要求而不同●数据结构的三个方面例1：

一个线性表

逻辑结构：哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。

存储结构：它的元素在存储器中是顺序地邻接存放，还是用指针连接在一起的；等等。

运算：在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。1、基本概念和术语●数据的四种基本逻辑结构与四种基本存储结构1）从逻辑角度看，数据可归结为四种基本结构：集合、线性结构、树结构和图结构2）从存储角度看，数据可归结为四种基本结构：顺序结构、链接结构、索引结构和散列结构1、基本概念和术语1）数据的四种基本逻辑结构●线性结构：结构中的数据元素之间存在一对一的关系●树结构：结构中的数据元素之间存在一对多的关系●图结构：结构中的数据元素之间存在多对多的关系。●集合：结构中的数据元素之间除“同属于一个集合”的关系，无其他关系1）数据的四种基本逻辑结构线性结构树结构图结构本课程主要讨论三种结构例：用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。（1）S=(D,R)D={a,b,c,d,e,f}R={<a,e>,<b,c>,<(c,a>,<e,f>,<f,d>}解：上述表达式可用图形表示为：此结构为线性的。b

c

a

e

f

d该结构是非线性的。解：上述表达式可用图形表示为：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d32）数据的四种基本存储结构●链接存储结构

不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。●顺序存储结构

把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

●散列存储结构

根据结点的关键字直接计算出该结点的存储地址。●索引存储结构

通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），关键字是能唯一标识一个结点的那些数据项。2）数据的四种基本存储结构顺序存储结构链式存储结构2）数据的四种基本存储结构数据的存储结构

顺序存储结构：把数据元素存储在一块连续地址空间的内存中，其特点是逻辑上相邻的数据元素在物理上也相邻，数据间的逻辑关系表现在数据元素存储位置关系上。指针是指向物理存储单元地址的变量。由数据元素域和指针域组成的一个结构体称为结点。链式存储结构：使用指针把相互直接关联的结点(即直接前驱结点或直接后继结点)链接起来，其特点是逻辑上相邻的数据元素在物理上不一定相邻，数据间的逻辑关系表现在结点的链接关系上。－2.303023.00300041503023.003000415－2.3法1：地址内容法2：地址内容2字节例：复数3.0－2.3i的两种存储方式：元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存储地址存储内容Loc(a)=Lo+（i-1)*m顺序存储每个元素所占用的存储单元个数元素n……..元素i……..元素2元素1存储内容顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。顺序存储结构的三个弱点：1.作插入或删除操作时，需移动大量元数。2.长度变化较大时，需按最大空间分配。3.表的容量难以扩充。1536元素21400元素11346元素3∧元素41345h

链式存储每个节点都由两部分组成：数据域和指针域。数据域存放元素本身的数据，指针域存放指针。数据元素之间逻辑上的联系由指针来体现。1536元素21400元素11346元素3∧元素4head

1346元素3

1536

…….

……..

…….

1536元素2

1400

…….

……..

…….∧元素4

1346

1400元素1

1345指针存储内容存储地址

链式存储13451536元素21400元素11346元素3∧元素41345h

链式存储1.比顺序存储结构的存储密度小

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

(不必移动节点，只要改变节点中的指针)。链接存储结构特点：数据的操作

从抽象角度，数据的操作主要讨论某种数据类型数据应具备的操作的逻辑功能，抽象角度下的操作一般和数据的逻辑结构一起讨论；具体来说，数据的操作主要讨论操作的具体实现算法。具体问题的操作实现必须在数据的存储结构确定后才能进行。

数据结构课程主要讨论表、堆栈、队列、串、数组、树、二叉树、图等典型的常用数据结构。在讨论这些典型数据结构时，主要从它们的逻辑结构、存储结构和数据操作三个方面进行分析讨论。1、基本概念和术语●定义在数据结构上的基本操作删除(Delete)

删去数据结构中某个指定的数据元素。插入(Insert)

在数据结构中的指定位置上增添新的数据元素。更新(Update)

改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。查找(Find)

在数据结构中寻找满足某个特定要求的数据元素(位置或值)。1、基本概念和术语●定义在数据结构上的基本操作排序(Sort)

（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。注：一般将插入、删除与修改统称为更新；查找亦称搜索(Search)

。

1、基本概念和术语

同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表——顺序表、链表、散列表。给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈、链栈、链队列。1、基本概念和术语抽象数据类型(AbstractDataType,ADT)是指一个数学模型以及定义在这个模型上的一组操作。抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用。一个ADT的定义并不涉及它的实现细节，这些实现细节对于ADT的用户是隐蔽的——封装性/信息隐蔽数据结构是ADT的物理实现。2、抽象数据类型(ADT)例2：整数的数学概念和施加于整数的运算构成一个ADT，不同计算机中实现可能不同，其数学特性是相同，因此对用户完全相同。2、抽象数据类型(ADT)例3：一个整数线性表的ADT应包含下列操作：

插入一个整数到线性表尾删除线性表中特定位置上的整数在线性表中查找特定整数ADT包括以下三部分内容：ADT的规格说明(Specification)ADT的表示(Representation)ADT的实现(Implementation)用三元组表示：ADT=(数据对象D,关系集R,处理集P)2、抽象数据类型(ADT)本书的表示格式：ADT

抽象数据类型名

{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>}ADT

抽象数据类型名2、抽象数据类型(ADT)用伪码表示基本操作名(参数表)

初始条件：<初始条件描述>

操作结果：<操作结果描述>

在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的－－

与具体实现无关。

ADT的主要目的之一是对用户隐蔽所有的表示方法，算法的详细细节、实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。

ADT的一个重要优点是其简单性。ADT的目的是将数据的本质特征、它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。2、抽象数据类型(ADT)例4：在数据结构中，复数可定义为一种简单的抽象数据类型：Complex=(C,R)其中C是含有两个实数的集合{C1,C2}，R={P}，P是定义在集合C上的一种关系{<C1,C2>}，有序偶<C1,C2>表示C1是复数的实部，C2是复数的虚部。2、抽象数据类型(ADT)SpecificationComplex元素（Elements）

元素的集合为两个实数的笛卡儿乘积

Z

=

R×R

其中R表示实数集，Z表示复数集。结构（Structure）

Complex的元素之间不存在任何结构，每一个元素表示定义在复数域Z中的一个孤立的值。抽象数据类型Complex的规格说明：2、抽象数据类型(ADT)ADTComplex{DataObjects:D={C1,C2|C1,C2

∈实数};DataRelationships:R={<C1,C2>|C1,C2

∈实数}Operations:InitComplex(&T,E1,E2)

操作结果：构造复数，E1,E2分别代替C1,C2。

Add(&T,E1,E2);

初始条件：复数T已知

操作结果：E1,E2分别加C1,C2Sub(&T,E1,E2);

初始条件：复数T已知

操作结果：E1,E2分别减C1,C2………}ADTComplex抽象数据类型Complex的规格说明：2、抽象数据类型(ADT)抽象数据类型Complex具体的表示和实现依赖于所采用的计算机语言。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型Complex。C语言表示如下：抽象数据类型Complex的表示：2、抽象数据类型(ADT)structComplex{realRealPart;realImagPart;}；Operation在Complex上可定义下列操作1）函数InitComplex生成一个复数Z，Z=x+iyComplexInitComplex(realx,realy);2）函数Add求两个复数Z1与Z2之和。ComplexAdd(ComplexZ1,ComplexZ2);或ComplexAdd(ComplexZ,realR1,realR2);3）函数Sub，求两个复数Z1与Z2之差ComplexSub(ComplexZ1,ComplexZ2);或ComplexSub(ComplexZ,realR1,realR2);2、抽象数据类型(ADT)继下页Operation4）函数Multiply求两个复数之积ComplexMultiply(ComplexZ1,ComplexZ2);ComplexMultiply(ComplexZ,realR1,realR2);5）函数GetRealPart取复数Z的实部realGetRealPart(ComplexZ);6）函数GetImagPart取函数Z的虚部

realGetImagPart(ComplexZ);2、抽象数据类型(ADT)续上页以上关于ADT的定义（规格说明、表示）没有涉及到实现。正象ADT的名字所暗示的那样，它是作为实现的公共特征的抽象。但是，从ADT的角度研究数据结构的最终目的仍在于应用，因此必须仔细考虑表示方法、算法、实现的技术及细节。而当ADT被实现时，ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。由于在ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的独立性是显而易见的。抽象数据类型Complex的实现：2、抽象数据类型(ADT)ComplexCreate(realx,realy){ComplexZ;Z.RealPart=x;Z.ImagPart=y;returnZ;}ComplexAdd(ComplexZ1,ComplexZ2){ComplexSum;Sum.RealPart=Z1.RealPart+Z2.RealPart;Sum.ImagPart=Z1.ImagPart+Z2.ImagPart;returnSum;}(以下略)……抽象数据类型Complex的C语言实现：2、抽象数据类型(ADT)实现ADT2、抽象数据类型(ADT)由于C语言是面向过程的语言，它能支持ADT的实现，但是不能很好的反映ADT的数据隐蔽原则。在Pascal语言中，库单元(Unit)是ADT的较好表示和实现。随着面向对象技术的成熟，用面向对象中的对象/类来描述和实现ADT是非常好的方法。这种方法在面向对象程序设计方面已经成熟，已经广泛应用于不同程序设计语言及开发环境当中（如：C++，ObjectPascal,VB,Java,

PowerBuilder等等）。下面是Complex采用C++的定义：classComplex{private:realRealPart;realImagPart;public:Complex(realx,realy); //构造函数

Complex(Complex&Z); //拷贝构造函数

ComplexAdd(ComplexZ); //加法

ComplexSub(ComplexZ); //减法

ComplexMultiply(ComplexZ); //乘法

realGetRealPart(void); //取实部

realGetImagPart(void); //取虚部

………}{C++实现略}C++实现ADT2、抽象数据类型(ADT)3、类C语言语法规则类C语言是介于伪码语言和高级语言之间的一种算法描述语言。使用类C语言描述算法的好处：1.保持C结构清晰、明确直观等特色；2.但又略去一些次要环节，抓住主干精华。2、类C语言语法规则函数类型过程名(参数表){//算法说明语句组;return结果；}//过程名当返回状态结果时，函数定义为Status类型。

1）算法以过程或函数的形式表示3、类C语言语法规则2）赋值语句简单赋值

变量名=表达式；串联赋值

变量1=变量2=···=表达式；成组赋值

(变量名1,···,变量名k)=(表达式1,···,表达式k);结构名=结构名; 结构名=(值1,···,值k)；3、类C语言语法规则2）赋值语句变换赋值

变量1变量2； if(

条件

)语句1;if(

条件

)语句1;

else语句2；//可以嵌套3）IF语句3、类C语言语法规则switch(

表达式){case

条件1：语句1；break;

•

•

•

case

条件n：语句n;break;

default:

语句n+1}4）Switch语句switch{case

条件1：语句1；break;

•

•

•

case

条件n：语句n;break;

default:

语句n+1}3、类C语言语法规则For语句：

for(

处置表达式序列;条件;修改表达式系列)语句；While语句：

while(

条件

)

语句；

Do-While语句：

do{

语句;}while(条件

);5）循环语句3、类C语言语法规则6）基本函数7）布尔运算符8）标识符9）常量和类型第二问题

数据结构研究什么？运算逻辑结构存储结构第三问题

重新理解算法Algorithm●算法的概念●算法的描述●算法设计的要求●算法效率的度量●算法的存储空间需求4、算法的描述和算法分析算法==程序？算法是为了描述解决某一问题的方法，而不涉及具体的实现细节。算法存在的辨证关系

数据结构与算法的辨证关系给定了数据的逻辑结构后，对同一逻辑结构而言，由于存储结构的不同，定义的运算也是不同的。如线性表是一种逻辑结构，若采用顺序存储方法表示，则称为顺序表；若采用链式存储方法表示，则称为链表。相同的运算在顺序表和链表上的实现方法是不同的。●算法的概念4、算法的描述和算法分析算法(Algorithm)是对特定问题求解步骤的一种描述，是能在计算机上经过有限时间完成的、毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。问题（Problem）是一个函数，或是输入和输出的一种联系。程序（Program）是用计算机程序设计语言实现的完成一定功能的代码。算法的实现一定是程序，但程序不一定是算法的实现。4、算法的描述和算法分析算法的五个重要特性

1）有穷性：执行有限步，每步均在有穷时间内完成。2）确定性：对相同的输入，必产生相同的输出，即无二义性。3）可行性：计算机可使用已实现的基本运算执行有限次来完成。4）输入：零个或多个输入。5）输出：一个或多个输出。4、算法的描述和算法分析关于算法性质的另一种描述1、正确性(Correctness)

它必须完成所期望的功能，把每一次输入转化为正确的输出。2、具体步骤(ConcreteSteps)

一个算法应该由一系列具体步骤组成。3、确定性(NoAmbiguity)

下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。4、有限性(Finite)

一个算法必须由有限步组成。5、可终止性(Terminable)

算法必须可以终止，即不能进入死循环。●算法的描述4、算法的描述和算法分析一个算法可以用各种不同的方法来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码语言或框图等其它形式来描述它。●算法的描述4、算法的描述和算法分析描述算法的语言形式1.文字形式:用中文或英文这样的文字来描述算法。2.伪码形式:用一种仿程序设计语言的语言来描述算法。3.程序设计语言形式:用某种程序设计语言描述算法。其优点是算法不用修改，直接作为程序语句键入计算机，计算机能调用和运行。这里我们采用上讲介绍的类C语言来描述算法4、算法的描述和算法分析例:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,…,a1,a0,并要求原数组中的数据元素值不能被改变。voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];//把数组a的元素逆置后赋给数组b}4、算法的描述和算法分析例1-2:设计一个把存储在数组中的有n个抽象数据元素a0,a1,…,an-1逆置的算法，即要求逆置后的数组中数据元素序列为an-1,…,a1,a0,并要求原数组中的数据元素值被改变。voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++)//进行m次调换{

temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}在程序设计中，对算法进行分析是十分重要的。对于一个具体的应用实例，通常可能有若干个算法可供选用，应判断哪一个算法在现有的计算机环境中对解决某个问题是最优的。例5：写一函数，用以计算1+2+•••+n的值，其中n为已知。longSumWork(intn){intsum=0;

for(inti=1;i++;i<=n)sum+=i;returnsum;}

●算法设计的要求4、算法的描述和算法分析longBetterSum(intn){return(n+1)*n/2;}●算法设计的要求4、算法的描述和算法分析在计算机科学中，通常使用算法的计算（执行）时间和所需的存储空间来评价算法或程序的优劣。在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个“好”的算法应考虑达到的下列目标。

1）正确性

2）可读性

3）健壮性

4）效率与低存储量需求●算法设计的要求4、算法的描述和算法分析1）正确性(Correctness)

能满足具体问题的需求。正确性对于选择算法来说，是首要的问题。正确性的四个层次：

a.程序不含语法错误；

b.程序对于输入数据能够得出满足规格说明要求的结果

(要算对)；

c.程序对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果；

d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。●算法设计的要求4、算法的描述和算法分析2）可读性(Readability)希望一个算法易于理解、易于编码，也易于调试。3）健壮性(Robustness)对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。4）效率(Efficiency)与低存储需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应。●算法效率的度量4、算法的描述和算法分析算法执行时间的度量——时间复杂度执行时间取决于下列因素：

a.选用哪种算法

b.问题的规模（输入的大小/复杂程度）；

c.所选用的语言；

d.编译程序所产生可执行代码的质量；

e.机器执行指令的速度。1）事后统计

对算法程序的执行进行计时。（有缺陷）2）事前估计

事先估算的主要因素——问题的规模。●算法效率的度量4、算法的描述和算法分析

一个算法是由控制结构（顺序、分支和循环）和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据。2）事前估计

●算法效率的度量4、算法的描述和算法分析例6：两个n×n矩阵相乘，令乘法运算作为基本运算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];};

整个算法执行时间与乘法操作重复执行的次数n3成正比，记作T(n)=O(n3).

两个n×n矩阵相乘的时间复杂度为O(n3).●算法效率的度量4、算法的描述和算法分析定义：某算法执行时间T(n)是O(f(n))，意指存在正的常数M和n0，使对于一切n>n0，T(n)≤Mf(n)都成立。如果一个程序的时间复杂度是O(f(n))，就说该程序的运行时间增加率的一个上界为f(n)，或说T(n)是f(n)的大O函数。

例7：设T(n)=n2+4n，则有f(n)=n2，即有：n2+4n=O(n2).因为存在M=2，n0=4，使对于一切n>n0，恒有n2+4n≤2n24、算法的描述和算法分析大O运算规则

规则一

对于任何的常数k和任何的函数f，恒有kf(n)=O(f(n))，即大O忽略常数因子。

规则二若f(n)=O(g(n))且g(n)=O(h(n))，则f(n)=O(h(n))，即大O的概念是传递的。

规则三

若定义max{f(n)，g(n)}为f(n)与g(n)两者中增长率较快的函数，则有f(n)+g(n)=O(max{f(n),g(n)}).

规则四若f1(n)=O(g1(n))且f2(n)=O(g2(n))，则f1(n)•f2(n)=O(g1(n)•g2(n))，即大O符合乘法规则。有关数学问题：/型不定式极限有关数学定理：罗比塔法则例8

求时间函数8nlog(n)+4n3/2的大O.(1)log(n)=O(n1/2)定义

(2)nlog(n)=O(n•n1/2)=O(n3/2)

规则四

(3)8nlog(n)=8O(n3/2)=O(n3/2)

规则一

(4)4n3/2=O(n3/2)

规则一

(5)8nlog(n)+4n3/2

=O(max{8nlog(n)，4n3/2}）规则三

max{8nlog(n)，4n3/2}=max{O(n3/2)，O(n3/2)}=O(n3/2)8nlog(n)+4n3/2=O(O(n3/2))

所以有=O(n3/2)规则二

8nlog(n)+4n3/2=O(n3/2).4、算法的描述和算法分析例9:设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算算法的时间复杂度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本语句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本语句2}解:设基本语句的执行次数为f(n),有f(n)=c1×n2+c2×n3,因 T(n)=f(n)=c1×n2+c2×n3≤c×n3,其中c1,c2,c均为常数，所以该算法的时间复杂度为

T(n)=O(n3)例：求两个方阵的乘积C＝A*B＃definen自然数MATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti,j,k;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]=A[i][k]*B[k][j]}}//n+1//n(n+1)//n*n//n*n*(n+1)//n*n*n

例10:设n为如下算法处理的数据个数，求如下算法的时间复杂度。

for(i=1;i<=n;i=2*i)cout<<"i="<<i;解:设基本语句的执行次数为f(n),有2f(n)≤n,即有f(n)≤log2n。因T(n)=f(n)≤log2n≤c×

log2

n,所以该算法的时间复杂度为

T(n)=O(log2n)。例11:下边的算法是用冒泡排序法对数字a中的n个整数类型的数据元素(a[0]~a[n-1])，从小到大进行排序，求该算法的时间复杂度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}解:设基本语句的执行次数为f(n),最坏情况下有

f(n)≈n+4*n2/2因 T(n)=f(n)≈n+2*n2≤c*

n2,其中c为常数，所以该算法的时间复杂度为

T(n)=O(n2)。

算法的时间复杂度是衡量一个算法好坏的重要指标。一般来说，具有多项式时间复杂度的算法，是可接受、可实际使用的算法;具有指数时间复杂度的算法，是只有当n足够小时才可使用的算法。例12下面的算法是在一个有n个数据元素的数组a中删除第I个位置的数组元素，要求当删除成功时数组元素个数减1，求该算法的时间复杂度。其中数组下标从0至Delete(inta[],int&n,inti){intj;if(i<0||i>=n)return0;//删除位置错误，失败返回f