数据结构课件第1章-新1-

引言数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。要学会描述数据结构和算法，分析算法的时、空复杂度。第1章基础知识

数据结构DATASTRUCTURE1引言第1章基础知识数据结构DATASTRUCT内容提要1．给出数据结构的概念2．介绍数据抽象和抽象数据类型3．说明数据结构和算法描述的方法4．介绍算法和算法分析的基本方法√√2内容提要√√21.1算法和数据结构瑞士的Wirth博士图灵奖获得者提出：程序＝算法+数据结构31.1算法和数据结构瑞士的Wirth博士图灵奖获得者31.1算法和数据结构课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法

数据结构和算法是计算机学科的基础之一，更是软件技术的基础。

算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以带来更高效率的算法。程序＝算法+数据结构41.1算法和数据结构课堂提要数据结构和算法是计算机精心设计的数据结构真的可以带来更高效率的算法吗？5精心设计的数据结构真的可以带来更高效率的算法吗？5图一6

，图二7，

数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。

881.数据：计算机加工处理的对象

2.数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。数据元素由若干数据项组成。3.数据项是不可再分割的。1.2什么是数据结构

1.2.1基本概念91.数据：计算机加工处理的对象1.2什么是数据结构1.表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………数据项10表1.1学生情况表学号姓名性别其他信息B02040101王数据结构的由来

数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。

11数据结构的由来11什么是数据结构定义1----数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。12什么是数据结构12

数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。13数据结构包括三个方面13数据结构举例表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………逻辑结构，存储结构，运算14数据结构举例表1.1学生情况表学号姓名性别其他信息B021.2.2数据的逻辑结构数据结构的逻辑结构可以用一个二元组表示。即DS=（D，R）其中，D是数据元素的有限集合，R是D中数据元素序偶的集合。例如DS={D,R},D={a,b,c,d},R={<a,b>,<b,c>,<c,d>},

其中，序偶<a,b>表示a和b之间的关系，我们称为a是b的直接前驱，b是a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。abcd151.2.2数据的逻辑结构数据结构的逻辑结构4种基本的逻辑结构

(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：164种基本的逻辑结构(a)集合结构(b)线性结构(c)树形结构

线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。树形结构：数据元素之间存在一对多的关系。图结构：数据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系17线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。几种存储结构

顺序结构链接结构索引结构散列结构地址信息称为链。∧表示空链。1.2.3数据的存储表示存储结构:数据结构的实现形式，是数据结构在计算机内的表示，即数据元素及其关系在计算机存储器中的存储方式。其中，顺序和链接是两种最基本的存储表示方法。18几种存储结构地址信息称为链。∧表示空链。1.2.3数顺序存储顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。例如，由4个元素组成的线性数据结构（a0,a1,a2,a3），存储在某个连续的存储区内，设存储区的起始地址是102，假定每个元素占2个存储单元。Loc(ak)=102+2×k19顺序存储例如，由4个元素组成的线性数据结构（a链式存储

例如，线性结构（a0,a1,a2,a3）的链接存储表示。结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。

DataLink链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。20链式存储例如，线性结构（a0,a1,a2,a3）逻辑结构存储结构概念数据元素之间逻辑关系的描述数据及其关系在计算机内的组织方式面向面向应用问题面向计算机关系存储结构是逻辑结构在计算机内的映像小结21逻辑结构存储结构概念数据元素之间逻辑关系的描述数据及其关系在1.2.4数据结构的运算数据结构最常见的运算创建运算:创建一个数据结构；

清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……221.2.4数据结构的运算数据结构最常见的运算22静态数据结构和动态数据结构

如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。23静态数据结构和动态数据结构23小结

数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。24小结241.3数据抽象和抽象数据类型

抽象，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性的重要手段．本书采用抽象数据类型的观点讨论数据结构。课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法251.3数据抽象和抽象数据类型抽象，封装和信息隐蔽是控制软1.C语言的数据类型(1)基本类型：字符、整型……(2)构造类型：数组、结构和联合(3)指针类型：指针例如，inta;变量a的取值范围是：-3276832767对变量a执行的操作有：算术运算+、-、*、/、%关系运算<、>、<=、>=、==、!=2.数据类型一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。1.3.3数据类型和抽象数据类型

261.C语言的数据类型例如，inta;2.数据抽象数据类型（AbstractDataType,ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。例如，C++中的整型int就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量执行操作。3.抽象数据类型27抽象数据类型（AbstractDataType,ADT规范指明“做什么”，实现解决“怎样做”。规范是实现的准则和依据2828一个数据结构包含两个层次：(1)数据结构的规范（抽象层）：逻辑结构和运算的定义组成了数据结构的规范(2)数据结构的实现（实现层）：

存储结构和运算算法实现构成了数据结构的实现1.3.4数据结构和抽象数据类型

一种数据结构被视为一个抽象数据类型。29一个数据结构包含两个层次：1.3.4数据结构和抽象数据类型1.4描述数据结构和算法301.4描述数据结构和算法30本书是怎样描述每种数据结构？1.4描述数据结构和算法首先描述数据结构的规范（逻辑结构和运算的定义）然后介绍数据结构的实现（存储结构和运算的具体程序实现），31本书是怎样描述每种数据结构？1.4描述数据结构和算法首先

（1）用格式化的自然语言来描述数据结构的规范。（2）用一个C++的抽象模板类描述数据结构的规范。1.4.1数据结构的规范1.4描述数据结构和算法对数据结构的规范的描述：321.4.1数据结构的规范1.4描述数据结构和算法数据结构描述举例---堆栈1.4.1数据结构的规范33数据结构描述举例---堆栈1.4.1数据结构的规范33ADT1.1栈抽象数据类型ADTStack{Data:(描述逻辑结构)0个或多个元素的线性序列（a0，a1，，an-1)，遵循LIFO原则。

Operations:(描述运算的定义)Create()：创建一个空栈。Destroy():撤消一个栈。

Push(x)：元素x插入栈顶。Pop()：删除栈顶元素。Top(x)：在x中返回栈顶元素。}

（1）用ADT描述数据结构——堆栈的例子对堆栈的规范的描述：34ADT1.1栈抽象数据类型（1）用ADT描述数据结构—程序1.1栈的C++模板抽象类template<classT>classStack{public:

virtualvoidPush(Tx)=0;

virtualvoidPop()=0;virtualTTop(T&x)const=0;…};除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。（2）用C++模板抽象类描述数据结构35程序1.1栈的C++模板抽象类（2）用C++模板抽象类描template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}1.4.２实现数据结构堆栈的实现：36template<classT>1.4.２实现数据结构堆1.5算法分析的基本方法内容提要

算法及其性能分析算法的空间复杂度算法的时间复杂度渐近时间复杂度课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型

1.4描述数据结构和算法1.5算法分析的基本方法371.5算法分析的基本方法内容提要课堂提要371.什么是算法

一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：(1)输入算法有零个或多个输入。(2)输出算法至少产生一个输出(3)确定性算法的每一条指令都有确切的定义，没有二义性。(4)能行性算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。(5)有穷性算法必须总能在执行有限步之后终止。

1.5.1算法及其性能分析

381.什么是算法1.5.1算法及其性能分析382.算法描述方法算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用C++语言描述。3.算法的性能标准正确性：算法的执行结果应当满足预先规定的功能和性能要求。(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。(4)效率：有效使用存储空间和有高的时间效率。(5)最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。392.算法描述方法3.算法的性能标准391.5.2算法的时间复杂度

程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。算法的时间复杂度是程序运行从开始到结束所需的时间。401.5.2算法的时间复杂度程序步算法的时间复杂度40程序1.3求一个数组元素的累加之和floatsum(floatlist[],constintn){floattempsum=0.0;for(inti=0;i<n;i++)tempsum+=list[i];returntempsum;}程序步数为2n+3。41程序1.3求一个数组元素的累加之和程序步数为2n+3。41.5.3渐近时间复杂度

大O记号如果存在两个正常数c和n0，使得对所有的n，nn0，有f(n)cg(n)则有f(n)=O(g(n))。渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。421.5.3渐近时间复杂度大O记号渐近时间复杂度42渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。大O记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。例如，设

T(n)=3.6n3+2.5n2+2.88.9n3则根据大O记号的定义容易证明

T(n)=O(n3)43渐近时间复杂度大O记号用以表达一个算法运行时间的上界例如，程序1.2为求一个数组元素的累加之和的算法。floatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（1）总的程序步数为2n+3，则渐近时间复杂性为O(n)。44例如，程序1.2为求一个数组元素的累加之和的算法。floatfloatsum(floatlist[],constintn){floattempsum=0.0;//1for(inti=0;i<n;i++)//n+1

tempsum+=list[i];//nreturntempsum;//1}（2）语句tempsum+=list[i]可认为是关键操作，它的执行次数为n次，则渐近时间复杂性为O(n)。很多情况下，可以通过考察一个算法中的关键操作（关键操作被认为是一个执行次数最多的程序步）的执行次数来计算算法的渐近时间复杂性。45floatsum(floatlist[],consti常见的渐近时间复杂性从小到大排列有：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)例如：若某算法程序的总程序步为4,则其渐近时间复杂性为多少？O(4)是错误写法。应为O(1)46常见的渐近时间复杂性从小到大排列有：46voidMult(inta[n][n],b[n][n],c[n][n],intn){//nn矩阵a与b相乘得到c。for(inti=0;i<n;i++)//n+1for(intj=0;j<n;j++)//n(n+1){c[i][j]=0;//n2 for(intk=0;k<n;k++)//n2（n+1)

c[i][j]+=a[i][k]*b[k][j];//n3}}程序步为：2n3+3n2+2n+1渐近时间复杂度为：T(n)=O(n3)再看一例：47voidMult(inta[n][n],b[n][n]1.5.4最好、最坏和平均情况时间复杂度

对于某些算法，即使问题实例的规模相同，如果输入的数据不同，算法所需的时间开销也会不同。比如在有n个元素的一维数组上查找一个给定元素。481.5.4最好、最坏和平均情况时间复杂度对于某些算法，即算法的空间复杂度是程序运行从开始到结束所需的存储量。1.5.5算法的空间复杂度

49算法的空间复杂度1.5.5算法的空间复杂度49程序运行所需的存储空间包括两部分：（1）固定部分

这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。（2）可变部分

这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如，分别为100个元素的两个数组相加，与分别为10个元素的两个数组相加，所需的存储空间显然是不同的。50程序运行所需的存储空间包括两部分：50本章小结需要重点掌握的知识点数据结构的概念（包括三个方面）渐近时间复杂度51本章小结需要重点掌握的知识点51引言数据结构的概念及其研究的问题，是本章中重要的概念，它们贯穿整本书。除了数据结构研究的三个方面，我们对每种数据结构都会给出应用的实例。要学会描述数据结构和算法，分析算法的时、空复杂度。第1章基础知识

数据结构DATASTRUCTURE52引言第1章基础知识数据结构DATASTRUCT内容提要1．给出数据结构的概念2．介绍数据抽象和抽象数据类型3．说明数据结构和算法描述的方法4．介绍算法和算法分析的基本方法√√53内容提要√√21.1算法和数据结构瑞士的Wirth博士图灵奖获得者提出：程序＝算法+数据结构541.1算法和数据结构瑞士的Wirth博士图灵奖获得者31.1算法和数据结构课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法

数据结构和算法是计算机学科的基础之一，更是软件技术的基础。

算法设计通常建立在所处理的数据之上的，精心选择的数据结构可以带来更高效率的算法。程序＝算法+数据结构551.1算法和数据结构课堂提要数据结构和算法是计算机精心设计的数据结构真的可以带来更高效率的算法吗？56精心设计的数据结构真的可以带来更高效率的算法吗？5图一57

，图二58，

数据在计算机中的表示和存储不能是无组织的，是有规律，有结构的。

5981.数据：计算机加工处理的对象

2.数据元素：是组成数据的基本单位，在计算机程序中通常作为一个整体来处理。数据元素由若干数据项组成。3.数据项是不可再分割的。1.2什么是数据结构

1.2.1基本概念601.数据：计算机加工处理的对象1.2什么是数据结构1.表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………数据项61表1.1学生情况表学号姓名性别其他信息B02040101王数据结构的由来

数据结构主要是为研究和解决如何使用计算机组织和处理这些非数值问题而产生的理论、技术和方法。它已成为计算机学科研究的基本课题之一。

62数据结构的由来11什么是数据结构定义1----数据元素之间的相互关系称为结构，带有结构的数据元素的集合称为数据结构。定义2----按某种逻辑关系组织起来的一批数据（或称带结构的数据元素的集合）应用计算机语言并按一定的存储表示方式把它们存储在计算机的存储器中，并在其上定义了一个运算的集合。63什么是数据结构12

数据结构包括三个方面逻辑结构：数据元素间的逻辑关系；存储结构：数据在计算机内的表示形式；运算：在数据上执行的操作。64数据结构包括三个方面13数据结构举例表1.1学生情况表学号姓名性别其他信息B02040101王小红女…B02040102林悦女…B02040103陈菁女…B02040104张可可男……………逻辑结构，存储结构，运算65数据结构举例表1.1学生情况表学号姓名性别其他信息B021.2.2数据的逻辑结构数据结构的逻辑结构可以用一个二元组表示。即DS=（D，R）其中，D是数据元素的有限集合，R是D中数据元素序偶的集合。例如DS={D,R},D={a,b,c,d},R={<a,b>,<b,c>,<c,d>},

其中，序偶<a,b>表示a和b之间的关系，我们称为a是b的直接前驱，b是a的直接后继。小圆圈代表数据元素，两个不同元素的序偶称为边。abcd661.2.2数据的逻辑结构数据结构的逻辑结构4种基本的逻辑结构

(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系对数据元素间逻辑关系的描述称为数据的逻辑结构。根据数据结构中数据元素之间关系的不同特征，可以划分为以下四种基本逻辑结构：674种基本的逻辑结构(a)集合结构(b)线性结构(c)树形结构

线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。树形结构：数据元素之间存在一对多的关系。图结构：数据元素之间存在多对多的关系。每个结点的前驱和后继的数目都不同。集合结构：结构中的数据元素之间除了“同属于一个集合”的关系外，没有其它关系。四种逻辑结构也可以分成两类：线性结构和非线性结构。(a)集合结构(b)线性结构(c)树形结构(d)图结构图1-2四种基本的结构关系68线性结构：数据元素之间存在一对一的关系。一个前驱，一个后继。几种存储结构

顺序结构链接结构索引结构散列结构地址信息称为链。∧表示空链。1.2.3数据的存储表示存储结构:数据结构的实现形式，是数据结构在计算机内的表示，即数据元素及其关系在计算机存储器中的存储方式。其中，顺序和链接是两种最基本的存储表示方法。69几种存储结构地址信息称为链。∧表示空链。1.2.3数顺序存储顺序（或称连续）表示方法需要一块连续的存储空间，并把逻辑上相关的数据元素一次存储在该连续的存储区中。例如，由4个元素组成的线性数据结构（a0,a1,a2,a3），存储在某个连续的存储区内，设存储区的起始地址是102，假定每个元素占2个存储单元。Loc(ak)=102+2×k70顺序存储例如，由4个元素组成的线性数据结构（a链式存储

例如，线性结构（a0,a1,a2,a3）的链接存储表示。结点存储块分成两部分，元素本身和该元素后继元素所在结点的存储地址。

DataLink链接存储表示下，为在机内存储一个元素，除了需要存放该元素本身的信息外，还需要存放于该元素相关的其它元素的地址信息。这两部分信息组成一个数据元素的结点。71链式存储例如，线性结构（a0,a1,a2,a3）逻辑结构存储结构概念数据元素之间逻辑关系的描述数据及其关系在计算机内的组织方式面向面向应用问题面向计算机关系存储结构是逻辑结构在计算机内的映像小结72逻辑结构存储结构概念数据元素之间逻辑关系的描述数据及其关系在1.2.4数据结构的运算数据结构最常见的运算创建运算:创建一个数据结构；

清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……731.2.4数据结构的运算数据结构最常见的运算22静态数据结构和动态数据结构

如果一个数据结构一旦创建，其结构不发生改变，则称为静态数据结构，否则成为动态数据结构。74静态数据结构和动态数据结构23小结

数据结构是一门研究程序设计问题中计算机的操作对象（数据）以及它们之间的关系和运算的学科。75小结241.3数据抽象和抽象数据类型

抽象，封装和信息隐蔽是控制软件开发复杂度，提高软件可靠性的重要手段．本书采用抽象数据类型的观点讨论数据结构。课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型1.4描述数据结构和算法1.5算法分析的基本方法761.3数据抽象和抽象数据类型抽象，封装和信息隐蔽是控制软1.C语言的数据类型(1)基本类型：字符、整型……(2)构造类型：数组、结构和联合(3)指针类型：指针例如，inta;变量a的取值范围是：-3276832767对变量a执行的操作有：算术运算+、-、*、/、%关系运算<、>、<=、>=、==、!=2.数据类型一个数据类型定义了一个值的集合以及作用于该值集的操作的集合。即一组值和一组操作。1.3.3数据类型和抽象数据类型

771.C语言的数据类型例如，inta;2.数据抽象数据类型（AbstractDataType,ADT）是一个数据类型，其主要特征是该类型的对象及其操作的规范,与该类型对象的表示和操作的实现分离，实行封装和信息隐蔽，即使用和实现分离。使用和实现分离：使用者通过规范使用该类型的数据，而不必考虑其实现细节；改变实现将不影响使用。例如，C++中的整型int就是抽象数据类型。它的实现是隐蔽的，使用者只能通过整型上定义的一组运算对整型变量执行操作。3.抽象数据类型78抽象数据类型（AbstractDataType,ADT规范指明“做什么”，实现解决“怎样做”。规范是实现的准则和依据7928一个数据结构包含两个层次：(1)数据结构的规范（抽象层）：逻辑结构和运算的定义组成了数据结构的规范(2)数据结构的实现（实现层）：

存储结构和运算算法实现构成了数据结构的实现1.3.4数据结构和抽象数据类型

一种数据结构被视为一个抽象数据类型。80一个数据结构包含两个层次：1.3.4数据结构和抽象数据类型1.4描述数据结构和算法811.4描述数据结构和算法30本书是怎样描述每种数据结构？1.4描述数据结构和算法首先描述数据结构的规范（逻辑结构和运算的定义）然后介绍数据结构的实现（存储结构和运算的具体程序实现），82本书是怎样描述每种数据结构？1.4描述数据结构和算法首先

（1）用格式化的自然语言来描述数据结构的规范。（2）用一个C++的抽象模板类描述数据结构的规范。1.4.1数据结构的规范1.4描述数据结构和算法对数据结构的规范的描述：831.4.1数据结构的规范1.4描述数据结构和算法数据结构描述举例---堆栈1.4.1数据结构的规范84数据结构描述举例---堆栈1.4.1数据结构的规范33ADT1.1栈抽象数据类型ADTStack{Data:(描述逻辑结构)0个或多个元素的线性序列（a0，a1，，an-1)，遵循LIFO原则。

Operations:(描述运算的定义)Create()：创建一个空栈。Destroy():撤消一个栈。

Push(x)：元素x插入栈顶。Pop()：删除栈顶元素。Top(x)：在x中返回栈顶元素。}

（1）用ADT描述数据结构——堆栈的例子对堆栈的规范的描述：85ADT1.1栈抽象数据类型（1）用ADT描述数据结构—程序1.1栈的C++模板抽象类template<classT>classStack{public:

virtualvoidPush(Tx)=0;

virtualvoidPop()=0;virtualTTop(T&x)const=0;…};除了构造函数，其余成员函数都是纯虚函数。顺序栈类SeqStack是类Stack在顺序存储表示下的一种实现，它是从抽象类Stack派生出来的，它可以实例化。（2）用C++模板抽象类描述数据结构86程序1.1栈的C++模板抽象类（2）用C++模板抽象类描template<classT>boolSeqStack<T>::Push(T&x){if(IsFull()){cout<<"Overflow"<<endl;returnfalse;}s[++top]=x;returntrue;}1.4.２实现数据结构堆栈的实现：87template<classT>1.4.２实现数据结构堆1.5算法分析的基本方法内容提要

算法及其性能分析算法的空间复杂度算法的时间复杂度渐近时间复杂度课堂提要第1章基础知识1.1算法和数据结构1.2什么是数据结构1.3数据抽象和抽象数据类型

1.4描述数据结构和算法1.5算法分析的基本方法881.5算法分析的基本方法内容提要课堂提要371.什么是算法

一个算法(algorithm)是对特定问题的求解步骤的一种描述，它是指令的有限序列；此外，算法具有下列五个特征：(1)输入算法有零个或多个输入。(2)输出算法至少产生一个输出(3)确定性算法的每一条指令都有确切的定义，没有二义性。(4)能行性算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。(5)有穷性算法必须总能在执行有限步之后终止。

1.5.1算法及其性能分析

891.什么是算法1.5.1算法及其性能分析382.算法描述方法算法可以自然语言、流程图或程序设计语言描述。当一个算法用程序设计语言描述时，便成为程序。本书中，主要使用C++语言描述。3.算法的性能标准正确性：算法的执行结果应当满足预先规定的功能和性能要求。(2)简明性：一个算法应当思路清晰、层次分明、易读易懂。(3)健壮性：当输入不合法数据时，应能做适当处理，不至于引起严重后果。(4)效率：有效使用存储空间和有高的时间效率。(5)最优性：解决同一个问题可能有多种算法，应进行比较，选择最佳算法。902.算法描述方法3.算法的性能标准391.5.2算法的时间复杂度

程序步一个程序步是指在语法上或语义上有意义的程序段，该程序段的执行时间与问题实例的特征无关。算法的时间复杂度是程序运行从开始到结束所需的时间。911.5.2算法的时间复杂度程序步算法的时间复杂度40程序1.3求一个数组元素的累加之和floatsum(floatlist[],constintn){floattempsum=0.0;for(inti=0;i<n;i++)tempsum+=list[i];returntempsum;}程序步数为2n+3。92程序1.3求一个数组元素的累加之和程序步数为2n+3。41.5.3渐近时间复杂度

大O记号如果存在两个正常数c和n0，使得对所有的n，nn0，有f(n)cg(n)则有f(n)=O(g(n))。渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。931.5.3渐近时间复杂度大O记号渐近时间复杂度42渐近时间复杂度使用大O记号表示的算法的时间复杂性，称为算法的渐近时间复杂度,简称时间复杂度。大O记号用以表达一个算法运行时间的上界，可用程序步在数量级上估计算法的执行时间。例如，设

T(n)=3.6n3+2.5n2+2.88.9n3则根据大O记号的定义容易证明

T(n)=O(n3)94渐近时间复杂度