第一章 绪论第 1页数 据 结 构主 讲,戴小鹏 教授
E-MAIL,hndxp_au@sina.com
OFFICE,6教 208
湖南农业大学信息科学技术学院第一章 绪论第 2页本章主要内容一,,数据结构,课程概况二,第一章 绪论
1,什么是数据结构
2,基本概念和术语
3,抽象数据类型 (ADT)
4,类 C语言语法规则
5,算法的描述和算法分析第一章 绪论第 3页一,,数据结构,课程概况课程编号 20359B1
英文名称 Data Structure
先修课程 离散数学,计算机高级语言后续课程 数据库原理与应用,操作系统,软件工程等授课学时 56学时上机实践 24机时教学对象 计算机科学与技术专业,信息工程专业第一章 绪论第 4页教 材,数据结构 (C语言版 )》,严蔚敏等编清华大学出版社,2005年 6月配套题集,数据结构题集 (C语言版 )》,严蔚敏等编清华大学出版社,2005年 5月参考教材
数据结构（ C++版）王艳华，戴小鹏编，武汉大学出版社，
2007年 4月
数据结构（ C++）复习提要与上机实验，王艳华，戴小鹏编，武汉大学出版社,2007年 4月
数据结构 -C++实现，缪淮扣等编，科学出版社,2002年 7月
数据结构 -C++实现习题解析与实验指导，缪淮扣等编,2002年 7月
数据结构考研指导，李春葆等编，清华大学出版社,2003年 1月注：可参考数据结构的 C++语言方面的书籍。
一,,数据结构,课程概况第一章 绪论第 5页一,,数据结构,课程概况课程地位本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、数据库系统、人工智能系统和其它系统程序的 重要基础,是一门 核心课程,对培养计算机及有关专业人才具有重要意义。
第一章 绪论第 6页课程任务讲授那些 最重要、最常用 的数据结构，阐明数据结构内在的 逻辑关系,讨论它们在计算机中的 存储表示,并结合各种典型应用说明它们在进行各种运算时的 动态性质 和实现 操作的算法 。
一,,数据结构,课程概况第一章 绪论第 7页课程要求
1.熟悉各类典型的数据结构的 逻辑特性,不同的存储方法与存储量、算法及效率的关系、定义于数据结构上的主要 基本操作 及其 算法,了解它们的应用环境,为学习后续课程奠定基础；
2.进一步 提高 软件设计和编程 水平 ；
3.增强根据求解问题性质,选择合适的数据结构及控制求解算法的时间与空间复杂性的 能力 。
一,,数据结构,课程概况第一章 绪论第 8页章次 内 容 授课学时一二三四五六七八九十绪论线性表栈和队列串
* 数组和广义表树和二叉树图
* 动态存储管理查找内部排序
4 ( 0 )
1 2 ( 8 + 4 )
1 0 ( 6 + 4 )
6 ( 4 + 2)
8 ( 6 + 2 )
1 2 ( 8 + 4 )
1 2 ( 8 + 4 )
0 (0)
8 ( 6 + 2 )
8 ( 6 + 2 )
小计 8 0 ( 5 6 + 2 4 )
第一章 绪论第 9页一,,数据结构,课程概况
知识体系第一章 绪论第 10页要求：
１、了解数据结构、算法的概念、基本的逻辑结构和存储结构、基本操作；
２、掌握类 C语言体系和抽象数据类型的概念；
３、知道算法的时间复杂性和空间复杂性概念。
重点：
１、数据结构与算法的概念；
２、类 C语言体系；
３、抽象数据类型。
二、第一章 绪论第一章 绪论第 11页
1、什么是数据结构二、第一章 绪论简义,数据结构是一门研究 非数值计算 的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和 操作 等的学科。
数据结构 是计算机科学专业的一门 核心课程
，它的研究对象为 问题求解方法,程序设计方法 及一些典型数据结构的 算法 。
第一章 绪论第 12页数据结构程序设计算 法问题求解程序编写
1、什么是数据结构第一章 绪论第 13页
“好” 数据结构 ＋,好” 算法 ＝,好” 程序良好、合理的 数据结构清晰、实用的 算法简洁、高效的 程序
1、什么是数据结构第一章 绪论第 14页
,数据结构,在计算机科学技术中是一门综合性的专业基础课,计算机科学技术各个领域都要用到多种数据结构。在我国计算机及相关专业的教学计划中，
它是 核心课程 之一。在我院教学计划中,,数据结构
,已成为我院各计算机科学与技术专业和信息工程专业必修课程。
其基本内容包括,基本数据结构，抽象数据类型，
递归算法，复杂性分析，排序和查找，算法分析 等。
数据结构在计算机科学中所处的地位：
1、什么是数据结构第一章 绪论第 15页
1、什么是数据结构数据结构涵盖的内容第一章 绪论第 16页客观事物的 符号表示,是计算机程序加工的 原料 。它是信息的载体，能被计算机识别、
存储和加工处理。
随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴 。
● 数据 (Data)
2、基本概念和术语二、第一章 绪论第一章 绪论第 17页是 数据的基本单位,即数据这个集合中的一个实体。通常作为 整体进行考虑和处理 。有些情况下，数据元素也称为元素、结点、顶点
、记录等。一个数据元素可能仅含一个数据项
，亦可包含若干个数据项。
● 数据元素 (Data Element)
2、基本概念和术语
● 数据项 (Data Item)
亦称字段、域,数据项是具有独立含义的不可分割的 最小标识单位 。
第一章 绪论第 18页
● 数据对象 (Data Object)
性质相同 的数据元素的 集合,是数据的一个子集。数据对象可以是有限的，也可以是无限的。
如：整数对象是集合 N={0,± 1,± 2,….}；字母字符的集合等。
2、基本概念和术语第一章 绪论第 19页
● 数据类型 (Data Type)
简称类型,一个 值的集合 和定义在值集上的 一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。
原子类型 (Atomic Type),如 C中的标量类型（整型、
实型、字符型）以及指针类型等。
结构类型 (Structured Type）,亦称结构类型，如 C
中的数组、记录、文件类型等。
抽象数据类型 (Abstract Data Type,ADT）,下面有专门介绍。
2、基本概念和术语第一章 绪论第 20页
● 数据处理 (Data Processing)
对数据进行诸如查找、插入、删除、合并
、排序、统计、简单计算、输入、输出等的操作过程。
2、基本概念和术语
● 结构 (Structure)
相互关联的元素之间的 构成关系 。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。
第一章 绪论第 21页定义,是相互之间存在 一种或多种 特定关系的数据元素的集合。
组成,由某一 数据对象 及该对象中所有数据成员之间的 关系 组成。
Data Structure = （ Data Object,Relationships ）
数据结构是指在程序中信息的逻辑组织方法，
一般来说，这种方法也受到所选择的程序设计语言的限制。
● 数据结构 (Data Structure)
2、基本概念和术语第一章 绪论第 22页数据结构可描述为 Group=（ D,R）
有限个数据元素的集合有限个节点间关系的集合第一章 绪论第 23页数据的逻辑结构,指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。
数据的物理结构,亦称数据的物理结构、
存储结构，是指数据在计算机内的表示方法，
即存储形式。
● 数据结构 (Data Structure)
2、基本概念和术语第一章 绪论第 24页
1）数据元素之间的逻辑关系，亦称数据的 逻辑结构 ；
● 数据结构的三个方面
2）数据元素及其关系在计算机存储器内的表示，亦称数据的 存储结构 ；
3）数据的运算，即对数据施加的 操作 。
2、基本概念和术语第一章 绪论第 25页
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储 B 链式存储线性表栈串 数组和广义表树形结构图形结构数据结构的三个主要问题数据结构可描述为 Group=（ D,R）
我和你们的逻辑结构是师生结构我和你们在教室中的位置根据要求而不同队
C 索引存储 D 散列存储第一章 绪论第 26页
● 数据结构的三个方面例 1,一个线性表逻辑结构,哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。
存储结构,它的元素在存储器中是顺序地邻接存放，还是用指针连接在一起的；等等。
运算,在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。
2、基本概念和术语第一章 绪论第 27页
● 数据的四种基本逻辑结构与四种基本存储结构
1）从逻辑角度看，数据可归结为四种基本结构：
集合、线性结构、树结构和图结构
2）从存储角度看，数据可归结为四种基本结构：
顺序结构、链接结构、索引结构和散列结构
2、基本概念和术语第一章 绪论第 28页
1）数据的四种基本逻辑结构
● 线性结构,结构中的数据元素之间存在一对一的关系
● 树结构,结构中的数据元素之间存在一对多的关系
● 图结构,结构中的数据元素之间存在多对多的关系 。
● 集合,结构中的数据元素之间除“
同属于一个集合”的关系，无其他关系第一章 绪论第 29页例,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。
（ 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
第一章 绪论第 30页该结构 是非线性 的。
解,上述表达式可用图形表示为：
（ 2） S=(D,R)
D={di | 1≤i≤5}
R={(di,dj ),i<j}
d1
d5 d2
d4 d3
第一章 绪论第 31页
2）数据的四种基本存储结构
● 链接存储结构不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
● 顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
● 散列存储结构根据结点的关键字直接计算出该结点的存储地址。
● 索引存储结构通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），
关键字是能唯一标识一个结点的那些数据项。
第一章 绪论第 32页
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节例,复数 3.0－ 2.3i 的两种存储方式：
第一章 绪论第 33页元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(a)=Lo+（ i-1)*m
顺序存储每个元素所占用的存储单元个数第一章 绪论第 34页元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个弱点：
1.作插入或删除操作时，需移动大量元数。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
第一章 绪论第 35页
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储每个节点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放指针。
数据元素之间逻辑上的联系由指针来体现 。
第一章 绪论第 36页
1536元素 21400元素 1 1346元素 3 ∧元素 4
head
1346元素 31536
……,……,.……,
1536元素 21400
……,……,.……,
∧元素 41346
1400元素 11345
指针存储内容存储地址链式存储
1345
第一章 绪论第 37页
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储
1.比顺序存储结构的存储密度小
(每个节点都由数据域和指针愈组成 )。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活
(不必移动节点，只要改变节点中的指针 )。
链接存储结构特点：
第一章 绪论第 38页
● 定义在数据结构上的基本操作删除 (Delete)
删去数据结构中某个指定的数据元素。
插入 (Insert)
在数据结构中的指定位置上增添新的数据元素。
更新 (Update)
改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。
查找 (Find)
在数据结构中寻找满足某个特定要求的数据元素 (位置或值 )。
2、基本概念和术语第一章 绪论第 39页
● 定义在数据结构上的基本操作排序 (Sort)
（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。
注,一般将插入、删除与修改统称为更新；查找亦称搜索 (Search) 。
2、基本概念和术语第一章 绪论第 40页同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。
常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表 ——顺序表、链表、散列表。
给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈、链栈、
链队列。
2、基本概念和术语第一章 绪论第 41页抽象数据类型 (Abstract Data Type,ADT)是指一个数学模型以及定义在这个模型上的一组操作。
抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即 无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用 。一个 ADT的定义并不涉及它的实现细节，这些实现细节对于 ADT的用户是隐蔽的 ——封装性 /信息隐蔽数据结构是 ADT的物理实现。
3、抽象数据类型 (ADT)
二、第一章 绪论第一章 绪论第 42页例 2,整数的数学概念和施加于整数的运算构成一个 ADT，不同计算机中实现可能不同，
其数学特性是相同，因此对用户完全相同
。
3、抽象数据类型 (ADT)
例 3,一个整数线性表的 ADT应包含下列操作：
插入一个整数到线性表尾
删除线性表中特定位置上的整数
在线性表中查找特定整数第一章 绪论第 43页
ADT包括以下三部分内容：
ADT的规格说明 (Specification)
ADT的表示 (Representation)
ADT的实现 (Implementation)
用三元组表示：
ADT = ( 数据对象 D,关系集 R,处理集 P )
3、抽象数据类型 (ADT)
3、抽象数据类型 (ADT)
第一章 绪论第 44页本书的表示格式：
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作的定义 >
} ADT 抽象数据类型名
3、抽象数据类型 (ADT)
3、抽象数据类型 (ADT)
用伪码表示基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
第一章 绪论第 45页在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的－－ 与具体实现无关 。
ADT的主要目的之一是对用户 隐蔽 所有的表示方法，算法的详细 细节,实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。
ADT的一个重要优点是其 简单性 。 ADT的目的是将数据的 本质特征,它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。
3、抽象数据类型 (ADT)
第一章 绪论第 46页例 4,在数据结构中，复数可定义为一种简单的抽象数据类型：
Complex=(C,R)
其中 C是含有两个实数的集合 {C1,C2}，
R={P},P是定义在集合 C上的一种关系
{<C1,C2>}，
有序偶 <C1,C2>表示 C1是复数的实部，
C2是复数的虚部。
3、抽象数据类型 (ADT)
第一章 绪论第 47页
Specification Complex
元素（ Elements）
元素的集合为两个实数的笛卡儿乘积
Z = R × R
其中 R表示实数集,Z表示复数集。
结构（ Structure）
Complex的元素之间不存在任何结构，每一个元素表示定义在复数域 Z中的一个孤立的值。
抽象数据类型 Complex的规格说明,
3、抽象数据类型 (ADT)
第一章 绪论第 48页
ADT Complex {
Data Objects,D = { C1,C2 | C1,C2 ∈ 实数 };
Data Relationships,R = {<C1,C2>|C1,C2 ∈ 实数 }
Operations:
InitComplex( &T,E1,E2 )
操作结果：构造复数,E1,E2分别代替 C1,C2。
Add( &T,E1,E2 );
初始条件：复数 T已知操作结果,E1,E2分别加 C1,C2
Sub( &T,E1,E2 );
初始条件：复数 T已知操作结果,E1,E2分别减 C1,C2
… … …
} ADT Complex
抽象数据类型 Complex的规格说明,
3、抽象数据类型 (ADT)
第一章 绪论第 49页抽象数据类型 Complex具体的 表示 和 实现依赖 于所采用的 计算机语言 。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型 Complex。 C语言表示如下：
抽象数据类型 Complex的表示：
3、抽象数据类型 (ADT)
struct Complex{
real RealPart;
real ImagPart;
}；
第一章 绪论第 50页
Operation
在 Complex上可定义下列操作
1）函数 InitComplex生成一个复数 Z,Z=x+iy
Complex InitComplex( real x,real y );
2） 函数 Add求两个复数 Z1与 Z2之和 。
Complex Add( Complex Z1,Complex Z2 );
或 Complex Add( Complex Z,real R1,real R2 );
3） 函数 Sub,求两个复数 Z1与 Z2之差
Complex Sub( Complex Z1,Complex Z2 );
或 Complex Sub(Complex Z,real R1,real R2 );
3、抽象数据类型 (ADT)
继下页第一章 绪论第 51页
Operation
4）函数 Multiply求两个复数之积
Complex Multiply( Complex Z1,Complex Z2 );
Complex Multiply( Complex Z,real R1,real R2);
5）函数 GetRealPart 取复数 Z的实部
real GetRealPart( Complex Z );
6）函数 GetImagPart取函数 Z的虚部
real GetImagPart( Complex Z );
3、抽象数据类型 (ADT)
续上页第一章 绪论第 52页以上关于 ADT的定义（规格说明、表示）没有涉及到实现。正象 ADT的名字所暗示的那样，它是作为实现的公共特征的 抽象 。但是，从 ADT的角度研究数据结构的最终目的仍在于应用，因此 必须仔细考虑表示方法、算法、
实现的技术及细节 。而当 ADT被实现时,ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。
由于在 ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的 独立性 是显而易见的。
抽象数据类型 Complex的实现：
3、抽象数据类型 (ADT)
第一章 绪论第 53页
Complex Create( real x,real y )
{ Complex Z;
Z.RealPart = x;
Z.ImagPart = y;
return Z;
}
Complex Add( Complex Z1,Complex Z2 )
{ Complex Sum;
Sum.RealPart = Z1.RealPart + Z2.RealPart;
Sum.ImagPart = Z1.ImagPart + Z2.ImagPart;
return Sum;
}
(以下略 )… …
抽象数据类型 Complex的 C语言实现,
3、抽象数据类型 (ADT)
第一章 绪论第 54页实现 ADT
3、抽象数据类型 (ADT)
由于 C语言是面向过程的语言，它 能支持 ADT
的实现，但是 不能很好 的反映 ADT的数据隐蔽原则。
在 Pascal语言中，库单元 (Unit)是 ADT的较好表示和实现。
随着 面向对象技术 的成熟，用面向对象中的对象 /类来描述和实现 ADT是 非常好 的方法。这种方法在面向对象程序设计方面 已经成熟,已经 广泛应用于 不同程序设计语言及开发环境当中（如,C++，
Object Pascal,VB,Java,PowerBuilder等等）。
第一章 绪论第 55页下面是 Complex采用 C++的定义：
class Complex{
private:
real RealPart;
real ImagPart;
public:
Complex( real x,real y ); //构造函数
Complex( Complex &Z ); //拷贝构造函数
Complex Add( Complex Z ); //加法
Complex Sub( Complex Z ); //减法
Complex Multiply( Complex Z ); //乘法
real GetRealPart( void ); //取实部
real GetImagPart( void ); //取虚部
… … …
}
{C++实现略 }
C++实现 ADT
3、抽象数据类型 (ADT)
第一章 绪论第 56页
4、类 C语言语法规则二、第一章 绪论类 C语言是介于伪码语言和高级语言之间的一种算法描述语言。
使用类 C语言描述算法的好处：
1,保持 C结构清晰、明确直观等特色；
2,但又略去一些次要环节，抓住主干精华。
第一章 绪论第 57页
4、类 C语言语法规则函数类型 过程名 (参数表 )
{
//算法说明语句组 ;
return 结果；
} //过程名当返回状态结果时，函数定义为 Status类型。
1）算法以过程或函数的形式表示第一章 绪论第 58页
4、类 C语言语法规则
2）赋值语句简单赋值 变量名 = 表达式；
串联赋值 变量 1 = 变量 2 = ··· = 表达式；
成组赋值
(变量名 1,··,变量名 k)=(表达式 1,···,表达式 k);
结构名 = 结构名 ;
结构名 = (值 1,···,值 k)；
第一章 绪论第 59页
4、类 C语言语法规则
2）赋值语句变换赋值 变量 1? 变量 2；
if( 条件 ) 语句 1;
if( 条件 ) 语句 1;
else 语句 2；
//可以嵌套
3） IF语句第一章 绪论第 60页
4、类 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
}
第一章 绪论第 61页
4、类 C语言语法规则
For语句：
for( 处置表达式序列 ; 条件 ; 修改表达式系列 ) 语句；
While语句：
while( 条件 ) 语句；
Do-While语句：
do{
语句 ;
}
while ( 条件 );
5） 循环语句第一章 绪论第 62页
4、类 C语言语法规则
6） 基本函数
7） 布尔运算符
8） 标识符
9） 常量和类型第一章 绪论第 63页
● 算法的概念
● 算法的描述
● 算法设计的要求
● 算法效率的度量
● 算法的存储空间需求
5、算法的描述和算法分析第一章 绪论第 64页
● 算法的概念
5、算法的描述和算法分析算法 (Algorithm)是对特定 问题求解步骤 的一种描述，是能在计算机上经过 有限时间完成 的、
毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。
问题 （ Problem） 是一个函数，或是输入和输出的一种联系。 程序 （ Program） 是用计算机程序设计语言实现的完成一定功能的代码。
算法的实现一定是程序，但程序不一定是算法的实现。
第一章 绪论第 65页
5、算法的描述和算法分析算法的五个重要特性
1） 有穷性,执行有限步，每步均在 有穷时间内完成。
2） 确定性,对相同的输入，必产生相同的输出，即 无二义性 。
3） 可行性,计算机可使用已实现的基本运算执行 有限次 来完成。
4） 输入,零个或多个输入。
5） 输出,一个或多个输出。
第一章 绪论第 66页
5、算法的描述和算法分析关于算法性质的另一种描述
1,正确性 (Correctness)
它必须完成所期望的功能，把每一次输入转化为正确的输出。
2,具体步骤 (Concrete Steps)
一个算法应该由一系列具体步骤组成。
3,确定性 (No Ambiguity)
下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。
4,有限性 (Finite)
一个算法必须由有限步组成。
5,可终止性 (Terminable)
算法必须可以终止，即不能进入死循环。
第一章 绪论第 67页
● 算法的描述
5、算法的描述和算法分析一个算法可以用 各种不同的方法 来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码 语言或框图等其它形式来描述它。
这里我们采用上讲介绍的 类 C语言 来描述算法第一章 绪论第 68页在程序设计中，对算法进行 分析 是十分重要的。对于一个具体的应用实例，通常可能有 若干个算法可供选用,
应判断哪一个算法在现有的计算机环境中对解决某个问题是 最优 的 。
例 5,写一函数，用以计算 1+2++n的值，其中 n为已知。
long SumWork( int n )
{ int sum = 0;
for( int i = 1; i++; i <= n ) sum += i;
return sum ;
}
● 算法设计的要求
5、算法的描述和算法分析
long BetterSum( int n )
{
return (n+1)*n/2;
}
第一章 绪论第 69页
● 算法设计的要求
5、算法的描述和算法分析在计算机科学中，通常使用算法的计算（执行）
时间 和所需的 存储空间 来评价算法或程序的优劣。
在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个,好,的算法应考虑达到的下列目标。
1）正确性
2）可读性
3）健壮性
4）效率与低存储量需求第一章 绪论第 70页
● 算法设计的要求
5、算法的描述和算法分析
1）正确性 (Correctness)
能满足具体问题的需求。正确性对于选择算法来说，
是首要的问题。
正确性的四个层次：
a,程序不含 语法错误 ；
b,程序对于输入数据能够得出满足规格说明要求的结果
(要算对 )；
c,程序对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果；
d,程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
第一章 绪论第 71页
● 算法设计的要求
5、算法的描述和算法分析
2）可读性 (Readability)
希望一个算法易于理解、易于编码，也易于调试。
3）健壮性 (Robustness)
对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。
4）效率 (Efficiency)与 低存储需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应 。
第一章 绪论第 72页
● 算法效率的度量
5、算法的描述和算法分析算法执行时间的度量 —— 时间复杂度执行时间取决于下列因素：
a,选用哪种算法
b,问题的规模（输入的大小 /复杂程度）；
c,所选用的语言；
d,编译程序所产生可执行代码的质量；
e,机器执行指令的速度。
1）事后统计对算法程序的 执行 进行 计时 。（ 有缺陷 ）
2）事前估计事先估算的主要因素 ——问题的规模。
第一章 绪论第 73页
● 算法效率的度量
5、算法的描述和算法分析一个算法是由控制结构（顺序、分支和循环）
和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是,从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据 。
2）事前估计第一章 绪论第 74页
● 算法效率的度量
5、算法的描述和算法分析例 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).
第一章 绪论第 75页
● 算法效率的度量
5、算法的描述和算法分析定义,某算法执行时间 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≤2 n2
第一章 绪论第 76页
5、算法的描述和算法分析大 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符合乘法规则。
有关数学问题,?/?型不定式极限有关数学定理,罗比塔法则第一章 绪论第 77页例 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).
5、算法的描述和算法分析第一章 绪论第 78页
● 存储空间需求
5、算法的描述和算法分析算法所需存储空间的度量 ——空间复杂度（性）
算法的空间复杂度 S(n)就是一个算法或程序所需要的存储单元数。
一个 非递归 程序，并且 不含有动态 数据结构,在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而 只统计与问题大小有关的数组等结构变量所需的内存量,有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。
含有动态 数据结构 的程序应统计 内存分配过程的次数乘以该过程产生的动态变量所占单元的大小 。 递归调用情况较复杂,所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量,后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。
第一章 绪论第 79页第一章 小结
基本内容
*数据和数据结构等名词和术语的确定含义
*抽象数据类型（ ADT）
*描述算法的类 C语言
*从时间和空间角度分析算法的方法
学习要点
*熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系
*了解怎样以 ADT的角度来描述数据结构
*熟悉类 C语言的书写规范
*理解算法五要素
*掌握计算语句频度和估算算法时间复杂度的方法第一章 绪论第 80页第一章 小结算法设计的基本步骤
明确需求
构造数学模型
设计算法
正确性验证
算法效率的分析
算法的实现
程序的测试与排错
编写文档资料
E-MAIL,hndxp_au@sina.com
OFFICE,6教 208
湖南农业大学信息科学技术学院第一章 绪论第 2页本章主要内容一,,数据结构,课程概况二,第一章 绪论
1,什么是数据结构
2,基本概念和术语
3,抽象数据类型 (ADT)
4,类 C语言语法规则
5,算法的描述和算法分析第一章 绪论第 3页一,,数据结构,课程概况课程编号 20359B1
英文名称 Data Structure
先修课程 离散数学,计算机高级语言后续课程 数据库原理与应用,操作系统,软件工程等授课学时 56学时上机实践 24机时教学对象 计算机科学与技术专业,信息工程专业第一章 绪论第 4页教 材,数据结构 (C语言版 )》,严蔚敏等编清华大学出版社,2005年 6月配套题集,数据结构题集 (C语言版 )》,严蔚敏等编清华大学出版社,2005年 5月参考教材
数据结构（ C++版）王艳华，戴小鹏编，武汉大学出版社，
2007年 4月
数据结构（ C++）复习提要与上机实验，王艳华，戴小鹏编，武汉大学出版社,2007年 4月
数据结构 -C++实现，缪淮扣等编，科学出版社,2002年 7月
数据结构 -C++实现习题解析与实验指导，缪淮扣等编,2002年 7月
数据结构考研指导，李春葆等编，清华大学出版社,2003年 1月注：可参考数据结构的 C++语言方面的书籍。
一,,数据结构,课程概况第一章 绪论第 5页一,,数据结构,课程概况课程地位本课程不仅是一般的程序设计的基本训练，而且是设计和实现编译程序、数据库系统、人工智能系统和其它系统程序的 重要基础,是一门 核心课程,对培养计算机及有关专业人才具有重要意义。
第一章 绪论第 6页课程任务讲授那些 最重要、最常用 的数据结构，阐明数据结构内在的 逻辑关系,讨论它们在计算机中的 存储表示,并结合各种典型应用说明它们在进行各种运算时的 动态性质 和实现 操作的算法 。
一,,数据结构,课程概况第一章 绪论第 7页课程要求
1.熟悉各类典型的数据结构的 逻辑特性,不同的存储方法与存储量、算法及效率的关系、定义于数据结构上的主要 基本操作 及其 算法,了解它们的应用环境,为学习后续课程奠定基础；
2.进一步 提高 软件设计和编程 水平 ；
3.增强根据求解问题性质,选择合适的数据结构及控制求解算法的时间与空间复杂性的 能力 。
一,,数据结构,课程概况第一章 绪论第 8页章次 内 容 授课学时一二三四五六七八九十绪论线性表栈和队列串
* 数组和广义表树和二叉树图
* 动态存储管理查找内部排序
4 ( 0 )
1 2 ( 8 + 4 )
1 0 ( 6 + 4 )
6 ( 4 + 2)
8 ( 6 + 2 )
1 2 ( 8 + 4 )
1 2 ( 8 + 4 )
0 (0)
8 ( 6 + 2 )
8 ( 6 + 2 )
小计 8 0 ( 5 6 + 2 4 )
第一章 绪论第 9页一,,数据结构,课程概况
知识体系第一章 绪论第 10页要求：
１、了解数据结构、算法的概念、基本的逻辑结构和存储结构、基本操作；
２、掌握类 C语言体系和抽象数据类型的概念；
３、知道算法的时间复杂性和空间复杂性概念。
重点：
１、数据结构与算法的概念；
２、类 C语言体系；
３、抽象数据类型。
二、第一章 绪论第一章 绪论第 11页
1、什么是数据结构二、第一章 绪论简义,数据结构是一门研究 非数值计算 的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和 操作 等的学科。
数据结构 是计算机科学专业的一门 核心课程
，它的研究对象为 问题求解方法,程序设计方法 及一些典型数据结构的 算法 。
第一章 绪论第 12页数据结构程序设计算 法问题求解程序编写
1、什么是数据结构第一章 绪论第 13页
“好” 数据结构 ＋,好” 算法 ＝,好” 程序良好、合理的 数据结构清晰、实用的 算法简洁、高效的 程序
1、什么是数据结构第一章 绪论第 14页
,数据结构,在计算机科学技术中是一门综合性的专业基础课,计算机科学技术各个领域都要用到多种数据结构。在我国计算机及相关专业的教学计划中，
它是 核心课程 之一。在我院教学计划中,,数据结构
,已成为我院各计算机科学与技术专业和信息工程专业必修课程。
其基本内容包括,基本数据结构，抽象数据类型，
递归算法，复杂性分析，排序和查找，算法分析 等。
数据结构在计算机科学中所处的地位：
1、什么是数据结构第一章 绪论第 15页
1、什么是数据结构数据结构涵盖的内容第一章 绪论第 16页客观事物的 符号表示,是计算机程序加工的 原料 。它是信息的载体，能被计算机识别、
存储和加工处理。
随着计算机软、硬件的发展，计算机应用领域的不断扩大，数据的含义也随之拓广。文字、表格、图像、声音、光和电的输入等等均可列入数据的范畴 。
● 数据 (Data)
2、基本概念和术语二、第一章 绪论第一章 绪论第 17页是 数据的基本单位,即数据这个集合中的一个实体。通常作为 整体进行考虑和处理 。有些情况下，数据元素也称为元素、结点、顶点
、记录等。一个数据元素可能仅含一个数据项
，亦可包含若干个数据项。
● 数据元素 (Data Element)
2、基本概念和术语
● 数据项 (Data Item)
亦称字段、域,数据项是具有独立含义的不可分割的 最小标识单位 。
第一章 绪论第 18页
● 数据对象 (Data Object)
性质相同 的数据元素的 集合,是数据的一个子集。数据对象可以是有限的，也可以是无限的。
如：整数对象是集合 N={0,± 1,± 2,….}；字母字符的集合等。
2、基本概念和术语第一章 绪论第 19页
● 数据类型 (Data Type)
简称类型,一个 值的集合 和定义在值集上的 一组操作的总称。它显式地或隐含地规定了变量或表达式所有可能的取值范围以及在这些值上允许进行的操作。
原子类型 (Atomic Type),如 C中的标量类型（整型、
实型、字符型）以及指针类型等。
结构类型 (Structured Type）,亦称结构类型，如 C
中的数组、记录、文件类型等。
抽象数据类型 (Abstract Data Type,ADT）,下面有专门介绍。
2、基本概念和术语第一章 绪论第 20页
● 数据处理 (Data Processing)
对数据进行诸如查找、插入、删除、合并
、排序、统计、简单计算、输入、输出等的操作过程。
2、基本概念和术语
● 结构 (Structure)
相互关联的元素之间的 构成关系 。这种关系可以是物理上的，也可以是逻辑上的，或其它关系。
第一章 绪论第 21页定义,是相互之间存在 一种或多种 特定关系的数据元素的集合。
组成,由某一 数据对象 及该对象中所有数据成员之间的 关系 组成。
Data Structure = （ Data Object,Relationships ）
数据结构是指在程序中信息的逻辑组织方法，
一般来说，这种方法也受到所选择的程序设计语言的限制。
● 数据结构 (Data Structure)
2、基本概念和术语第一章 绪论第 22页数据结构可描述为 Group=（ D,R）
有限个数据元素的集合有限个节点间关系的集合第一章 绪论第 23页数据的逻辑结构,指各数据元素之间的逻辑关系，是用户按使用需要建立起来的，呈现在用户面前的结构形式。
数据的物理结构,亦称数据的物理结构、
存储结构，是指数据在计算机内的表示方法，
即存储形式。
● 数据结构 (Data Structure)
2、基本概念和术语第一章 绪论第 24页
1）数据元素之间的逻辑关系，亦称数据的 逻辑结构 ；
● 数据结构的三个方面
2）数据元素及其关系在计算机存储器内的表示，亦称数据的 存储结构 ；
3）数据的运算，即对数据施加的 操作 。
2、基本概念和术语第一章 绪论第 25页
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储 B 链式存储线性表栈串 数组和广义表树形结构图形结构数据结构的三个主要问题数据结构可描述为 Group=（ D,R）
我和你们的逻辑结构是师生结构我和你们在教室中的位置根据要求而不同队
C 索引存储 D 散列存储第一章 绪论第 26页
● 数据结构的三个方面例 1,一个线性表逻辑结构,哪个元素是表中第一个元素；哪个元素是表中最后一个元素；哪些元素在一个给定元素之前或之后；等等。
存储结构,它的元素在存储器中是顺序地邻接存放，还是用指针连接在一起的；等等。
运算,在表中查找一个元素；从表中删去一个元素；向表中插入一个元素；等等。
2、基本概念和术语第一章 绪论第 27页
● 数据的四种基本逻辑结构与四种基本存储结构
1）从逻辑角度看，数据可归结为四种基本结构：
集合、线性结构、树结构和图结构
2）从存储角度看，数据可归结为四种基本结构：
顺序结构、链接结构、索引结构和散列结构
2、基本概念和术语第一章 绪论第 28页
1）数据的四种基本逻辑结构
● 线性结构,结构中的数据元素之间存在一对一的关系
● 树结构,结构中的数据元素之间存在一对多的关系
● 图结构,结构中的数据元素之间存在多对多的关系 。
● 集合,结构中的数据元素之间除“
同属于一个集合”的关系，无其他关系第一章 绪论第 29页例,用图形表示下列数据结构，并指出它们是属于线性结构还是非线性结构。
（ 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
第一章 绪论第 30页该结构 是非线性 的。
解,上述表达式可用图形表示为：
（ 2） S=(D,R)
D={di | 1≤i≤5}
R={(di,dj ),i<j}
d1
d5 d2
d4 d3
第一章 绪论第 31页
2）数据的四种基本存储结构
● 链接存储结构不要求逻辑上相邻的结点其物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示的。
● 顺序存储结构把逻辑上相邻的结点存储在物理位置上相邻存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。
● 散列存储结构根据结点的关键字直接计算出该结点的存储地址。
● 索引存储结构通常在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项，索引项的一般形式是：（关键字，地址），
关键字是能唯一标识一个结点的那些数据项。
第一章 绪论第 32页
－ 2.30302
3.00300
04150302
3.00300
0415 － 2.3
法 1,地址 内容 法 2,地址 内容
2字节例,复数 3.0－ 2.3i 的两种存储方式：
第一章 绪论第 33页元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(a)=Lo+（ i-1)*m
顺序存储每个元素所占用的存储单元个数第一章 绪论第 34页元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个弱点：
1.作插入或删除操作时，需移动大量元数。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
第一章 绪论第 35页
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储每个节点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放指针。
数据元素之间逻辑上的联系由指针来体现 。
第一章 绪论第 36页
1536元素 21400元素 1 1346元素 3 ∧元素 4
head
1346元素 31536
……,……,.……,
1536元素 21400
……,……,.……,
∧元素 41346
1400元素 11345
指针存储内容存储地址链式存储
1345
第一章 绪论第 37页
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储
1.比顺序存储结构的存储密度小
(每个节点都由数据域和指针愈组成 )。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活
(不必移动节点，只要改变节点中的指针 )。
链接存储结构特点：
第一章 绪论第 38页
● 定义在数据结构上的基本操作删除 (Delete)
删去数据结构中某个指定的数据元素。
插入 (Insert)
在数据结构中的指定位置上增添新的数据元素。
更新 (Update)
改变数据结构中某个数据元素的值，在概念上等价于删除和插入操作的组合。
查找 (Find)
在数据结构中寻找满足某个特定要求的数据元素 (位置或值 )。
2、基本概念和术语第一章 绪论第 39页
● 定义在数据结构上的基本操作排序 (Sort)
（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使之按值由小到大或大到小（即递增、不降或递减、不增）的次序排列。
注,一般将插入、删除与修改统称为更新；查找亦称搜索 (Search) 。
2、基本概念和术语第一章 绪论第 40页同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。选择何种存储结构来表示相应的逻辑结构，主要是使其运算方便及根据算法的时空要求来具体确定。
常将同一逻辑结构的不同存储结构以不同的数据结构的命名。如线性表 ——顺序表、链表、散列表。
给定了数据的逻辑结构和存储结构，若定义的运算集合及其运算的性质不同，也可能导致完全不同的数据结构。如线性表中的栈、队列、顺序栈、链栈、
链队列。
2、基本概念和术语第一章 绪论第 41页抽象数据类型 (Abstract Data Type,ADT)是指一个数学模型以及定义在这个模型上的一组操作。
抽象数据类型仅取决于它的逻辑特性，与其在计算集中的表示无关。即 无论其内部结构如何变化，只要它的数学特性没有变化，都不影响其外部使用 。一个 ADT的定义并不涉及它的实现细节，这些实现细节对于 ADT的用户是隐蔽的 ——封装性 /信息隐蔽数据结构是 ADT的物理实现。
3、抽象数据类型 (ADT)
二、第一章 绪论第一章 绪论第 42页例 2,整数的数学概念和施加于整数的运算构成一个 ADT，不同计算机中实现可能不同，
其数学特性是相同，因此对用户完全相同
。
3、抽象数据类型 (ADT)
例 3,一个整数线性表的 ADT应包含下列操作：
插入一个整数到线性表尾
删除线性表中特定位置上的整数
在线性表中查找特定整数第一章 绪论第 43页
ADT包括以下三部分内容：
ADT的规格说明 (Specification)
ADT的表示 (Representation)
ADT的实现 (Implementation)
用三元组表示：
ADT = ( 数据对象 D,关系集 R,处理集 P )
3、抽象数据类型 (ADT)
3、抽象数据类型 (ADT)
第一章 绪论第 44页本书的表示格式：
ADT 抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据关系的定义 >
基本操作,<基本操作的定义 >
} ADT 抽象数据类型名
3、抽象数据类型 (ADT)
3、抽象数据类型 (ADT)
用伪码表示基本操作名 (参数表 )
初始条件,<初始条件描述 >
操作结果,<操作结果描述 >
第一章 绪论第 45页在具体实现时，完成任务的算法、数据类型、数据结构、程序的逻辑组织，甚至采用哪种程序设计语言都是可以自由选择的－－ 与具体实现无关 。
ADT的主要目的之一是对用户 隐蔽 所有的表示方法，算法的详细 细节,实现操作的具体代码以及其它所有对外界不必要的细节，都被局限于具体实现的模块内部，从而实现了信息的隐蔽。
ADT的一个重要优点是其 简单性 。 ADT的目的是将数据的 本质特征,它们的结构及操作同它们的非本质的具体表示及实现细节相区分开来，从而得到了简化。
3、抽象数据类型 (ADT)
第一章 绪论第 46页例 4,在数据结构中，复数可定义为一种简单的抽象数据类型：
Complex=(C,R)
其中 C是含有两个实数的集合 {C1,C2}，
R={P},P是定义在集合 C上的一种关系
{<C1,C2>}，
有序偶 <C1,C2>表示 C1是复数的实部，
C2是复数的虚部。
3、抽象数据类型 (ADT)
第一章 绪论第 47页
Specification Complex
元素（ Elements）
元素的集合为两个实数的笛卡儿乘积
Z = R × R
其中 R表示实数集,Z表示复数集。
结构（ Structure）
Complex的元素之间不存在任何结构，每一个元素表示定义在复数域 Z中的一个孤立的值。
抽象数据类型 Complex的规格说明,
3、抽象数据类型 (ADT)
第一章 绪论第 48页
ADT Complex {
Data Objects,D = { C1,C2 | C1,C2 ∈ 实数 };
Data Relationships,R = {<C1,C2>|C1,C2 ∈ 实数 }
Operations:
InitComplex( &T,E1,E2 )
操作结果：构造复数,E1,E2分别代替 C1,C2。
Add( &T,E1,E2 );
初始条件：复数 T已知操作结果,E1,E2分别加 C1,C2
Sub( &T,E1,E2 );
初始条件：复数 T已知操作结果,E1,E2分别减 C1,C2
… … …
} ADT Complex
抽象数据类型 Complex的规格说明,
3、抽象数据类型 (ADT)
第一章 绪论第 49页抽象数据类型 Complex具体的 表示 和 实现依赖 于所采用的 计算机语言 。用户可以用某种高级语言的固有数据类型和自定义数据类型，并借助于过程和函数来表示和实现抽象数据类型 Complex。 C语言表示如下：
抽象数据类型 Complex的表示：
3、抽象数据类型 (ADT)
struct Complex{
real RealPart;
real ImagPart;
}；
第一章 绪论第 50页
Operation
在 Complex上可定义下列操作
1）函数 InitComplex生成一个复数 Z,Z=x+iy
Complex InitComplex( real x,real y );
2） 函数 Add求两个复数 Z1与 Z2之和 。
Complex Add( Complex Z1,Complex Z2 );
或 Complex Add( Complex Z,real R1,real R2 );
3） 函数 Sub,求两个复数 Z1与 Z2之差
Complex Sub( Complex Z1,Complex Z2 );
或 Complex Sub(Complex Z,real R1,real R2 );
3、抽象数据类型 (ADT)
继下页第一章 绪论第 51页
Operation
4）函数 Multiply求两个复数之积
Complex Multiply( Complex Z1,Complex Z2 );
Complex Multiply( Complex Z,real R1,real R2);
5）函数 GetRealPart 取复数 Z的实部
real GetRealPart( Complex Z );
6）函数 GetImagPart取函数 Z的虚部
real GetImagPart( Complex Z );
3、抽象数据类型 (ADT)
续上页第一章 绪论第 52页以上关于 ADT的定义（规格说明、表示）没有涉及到实现。正象 ADT的名字所暗示的那样，它是作为实现的公共特征的 抽象 。但是，从 ADT的角度研究数据结构的最终目的仍在于应用，因此 必须仔细考虑表示方法、算法、
实现的技术及细节 。而当 ADT被实现时,ADT中的元素成了数据结构的一个实例,而那些操作就成了算法。
由于在 ADT的规格说明中，只指明了其功能而未指定要采用何种方法，因此，实现的 独立性 是显而易见的。
抽象数据类型 Complex的实现：
3、抽象数据类型 (ADT)
第一章 绪论第 53页
Complex Create( real x,real y )
{ Complex Z;
Z.RealPart = x;
Z.ImagPart = y;
return Z;
}
Complex Add( Complex Z1,Complex Z2 )
{ Complex Sum;
Sum.RealPart = Z1.RealPart + Z2.RealPart;
Sum.ImagPart = Z1.ImagPart + Z2.ImagPart;
return Sum;
}
(以下略 )… …
抽象数据类型 Complex的 C语言实现,
3、抽象数据类型 (ADT)
第一章 绪论第 54页实现 ADT
3、抽象数据类型 (ADT)
由于 C语言是面向过程的语言，它 能支持 ADT
的实现，但是 不能很好 的反映 ADT的数据隐蔽原则。
在 Pascal语言中，库单元 (Unit)是 ADT的较好表示和实现。
随着 面向对象技术 的成熟，用面向对象中的对象 /类来描述和实现 ADT是 非常好 的方法。这种方法在面向对象程序设计方面 已经成熟,已经 广泛应用于 不同程序设计语言及开发环境当中（如,C++，
Object Pascal,VB,Java,PowerBuilder等等）。
第一章 绪论第 55页下面是 Complex采用 C++的定义：
class Complex{
private:
real RealPart;
real ImagPart;
public:
Complex( real x,real y ); //构造函数
Complex( Complex &Z ); //拷贝构造函数
Complex Add( Complex Z ); //加法
Complex Sub( Complex Z ); //减法
Complex Multiply( Complex Z ); //乘法
real GetRealPart( void ); //取实部
real GetImagPart( void ); //取虚部
… … …
}
{C++实现略 }
C++实现 ADT
3、抽象数据类型 (ADT)
第一章 绪论第 56页
4、类 C语言语法规则二、第一章 绪论类 C语言是介于伪码语言和高级语言之间的一种算法描述语言。
使用类 C语言描述算法的好处：
1,保持 C结构清晰、明确直观等特色；
2,但又略去一些次要环节，抓住主干精华。
第一章 绪论第 57页
4、类 C语言语法规则函数类型 过程名 (参数表 )
{
//算法说明语句组 ;
return 结果；
} //过程名当返回状态结果时，函数定义为 Status类型。
1）算法以过程或函数的形式表示第一章 绪论第 58页
4、类 C语言语法规则
2）赋值语句简单赋值 变量名 = 表达式；
串联赋值 变量 1 = 变量 2 = ··· = 表达式；
成组赋值
(变量名 1,··,变量名 k)=(表达式 1,···,表达式 k);
结构名 = 结构名 ;
结构名 = (值 1,···,值 k)；
第一章 绪论第 59页
4、类 C语言语法规则
2）赋值语句变换赋值 变量 1? 变量 2；
if( 条件 ) 语句 1;
if( 条件 ) 语句 1;
else 语句 2；
//可以嵌套
3） IF语句第一章 绪论第 60页
4、类 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
}
第一章 绪论第 61页
4、类 C语言语法规则
For语句：
for( 处置表达式序列 ; 条件 ; 修改表达式系列 ) 语句；
While语句：
while( 条件 ) 语句；
Do-While语句：
do{
语句 ;
}
while ( 条件 );
5） 循环语句第一章 绪论第 62页
4、类 C语言语法规则
6） 基本函数
7） 布尔运算符
8） 标识符
9） 常量和类型第一章 绪论第 63页
● 算法的概念
● 算法的描述
● 算法设计的要求
● 算法效率的度量
● 算法的存储空间需求
5、算法的描述和算法分析第一章 绪论第 64页
● 算法的概念
5、算法的描述和算法分析算法 (Algorithm)是对特定 问题求解步骤 的一种描述，是能在计算机上经过 有限时间完成 的、
毫不含糊的指令的有限序列。其中每一条指令表示一个或多个操作。
问题 （ Problem） 是一个函数，或是输入和输出的一种联系。 程序 （ Program） 是用计算机程序设计语言实现的完成一定功能的代码。
算法的实现一定是程序，但程序不一定是算法的实现。
第一章 绪论第 65页
5、算法的描述和算法分析算法的五个重要特性
1） 有穷性,执行有限步，每步均在 有穷时间内完成。
2） 确定性,对相同的输入，必产生相同的输出，即 无二义性 。
3） 可行性,计算机可使用已实现的基本运算执行 有限次 来完成。
4） 输入,零个或多个输入。
5） 输出,一个或多个输出。
第一章 绪论第 66页
5、算法的描述和算法分析关于算法性质的另一种描述
1,正确性 (Correctness)
它必须完成所期望的功能，把每一次输入转化为正确的输出。
2,具体步骤 (Concrete Steps)
一个算法应该由一系列具体步骤组成。
3,确定性 (No Ambiguity)
下一步（通常是指算法描述中的下一步）应执行的步骤必须明确。
4,有限性 (Finite)
一个算法必须由有限步组成。
5,可终止性 (Terminable)
算法必须可以终止，即不能进入死循环。
第一章 绪论第 67页
● 算法的描述
5、算法的描述和算法分析一个算法可以用 各种不同的方法 来进行描述。比如可使用某种高级语言、汇编语言甚至机器语言来描述某个算法，亦可使用伪码 语言或框图等其它形式来描述它。
这里我们采用上讲介绍的 类 C语言 来描述算法第一章 绪论第 68页在程序设计中，对算法进行 分析 是十分重要的。对于一个具体的应用实例，通常可能有 若干个算法可供选用,
应判断哪一个算法在现有的计算机环境中对解决某个问题是 最优 的 。
例 5,写一函数，用以计算 1+2++n的值，其中 n为已知。
long SumWork( int n )
{ int sum = 0;
for( int i = 1; i++; i <= n ) sum += i;
return sum ;
}
● 算法设计的要求
5、算法的描述和算法分析
long BetterSum( int n )
{
return (n+1)*n/2;
}
第一章 绪论第 69页
● 算法设计的要求
5、算法的描述和算法分析在计算机科学中，通常使用算法的计算（执行）
时间 和所需的 存储空间 来评价算法或程序的优劣。
在选择算法时，除了要考虑算法的运算时间和所需内存外，往往还要考虑其它一些重要的因素，即所谓设计一个,好,的算法应考虑达到的下列目标。
1）正确性
2）可读性
3）健壮性
4）效率与低存储量需求第一章 绪论第 70页
● 算法设计的要求
5、算法的描述和算法分析
1）正确性 (Correctness)
能满足具体问题的需求。正确性对于选择算法来说，
是首要的问题。
正确性的四个层次：
a,程序不含 语法错误 ；
b,程序对于输入数据能够得出满足规格说明要求的结果
(要算对 )；
c,程序对于精心选择的典型、苛刻而带有刁难性的输入数据能够得出满足规格说明要求的结果；
d,程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
第一章 绪论第 71页
● 算法设计的要求
5、算法的描述和算法分析
2）可读性 (Readability)
希望一个算法易于理解、易于编码，也易于调试。
3）健壮性 (Robustness)
对于异常的处理能力。能作出判断，并给出适当的提示或警告信息，以等待操作员的干预或能自动进行适当处理。
4）效率 (Efficiency)与 低存储需求效率指算法执行时间。同一问题，算法执行时间越短，效率越高。存储量需求指算法执行过程中所需的最大存储空间。此所谓时（执行时间）、空（运行空间）效应 。
第一章 绪论第 72页
● 算法效率的度量
5、算法的描述和算法分析算法执行时间的度量 —— 时间复杂度执行时间取决于下列因素：
a,选用哪种算法
b,问题的规模（输入的大小 /复杂程度）；
c,所选用的语言；
d,编译程序所产生可执行代码的质量；
e,机器执行指令的速度。
1）事后统计对算法程序的 执行 进行 计时 。（ 有缺陷 ）
2）事前估计事先估算的主要因素 ——问题的规模。
第一章 绪论第 73页
● 算法效率的度量
5、算法的描述和算法分析一个算法是由控制结构（顺序、分支和循环）
和原操作（指固有数据类型的操作）构成的，算法时间取决于两者的综合效果。但是，为便于比较同一问题的不同算法，通常的做法是,从算法中选取一种对于所研究的问题（或算法类型）来说是基本运算的原操作，以该基本运算重复执行的次数作为算法的时间量度的依据 。
2）事前估计第一章 绪论第 74页
● 算法效率的度量
5、算法的描述和算法分析例 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).
第一章 绪论第 75页
● 算法效率的度量
5、算法的描述和算法分析定义,某算法执行时间 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≤2 n2
第一章 绪论第 76页
5、算法的描述和算法分析大 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符合乘法规则。
有关数学问题,?/?型不定式极限有关数学定理,罗比塔法则第一章 绪论第 77页例 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).
5、算法的描述和算法分析第一章 绪论第 78页
● 存储空间需求
5、算法的描述和算法分析算法所需存储空间的度量 ——空间复杂度（性）
算法的空间复杂度 S(n)就是一个算法或程序所需要的存储单元数。
一个 非递归 程序，并且 不含有动态 数据结构,在它还未开始执行前，所需存储单元总数即已确定。为简化计算，在算法的空间复杂度分析中，将忽略程序中所有的简单变量和程序的执行代码本身所占的内存空间，而 只统计与问题大小有关的数组等结构变量所需的内存量,有时当一些数据、结构变量要占用相当可观的常数量单元时，也可进行统计。
含有动态 数据结构 的程序应统计 内存分配过程的次数乘以该过程产生的动态变量所占单元的大小 。 递归调用情况较复杂,所需内存单元数等于递归调用的最大深度乘以该递归过程本身所需的内存量,后者包括简单变量、参数变量、调用时系统所需的辅助内存量等。
第一章 绪论第 79页第一章 小结
基本内容
*数据和数据结构等名词和术语的确定含义
*抽象数据类型（ ADT）
*描述算法的类 C语言
*从时间和空间角度分析算法的方法
学习要点
*熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系
*了解怎样以 ADT的角度来描述数据结构
*熟悉类 C语言的书写规范
*理解算法五要素
*掌握计算语句频度和估算算法时间复杂度的方法第一章 绪论第 80页第一章 小结算法设计的基本步骤
明确需求
构造数学模型
设计算法
正确性验证
算法效率的分析
算法的实现
程序的测试与排错
编写文档资料
