数据结构第1单元(基础知识)

武汉大学国际软件学院薛超英2014年8月

数据结构用C++语言描述算法武汉大学国际软件学院薛超英2014年8月

课程简介

课程性质

计算机相关专业的专业基础课。

学习目的

学习如何组织数据、如何高效率的处理数据。

基本内容

学习线性表、栈、队列、树、搜索树、散列表、图等常见的数据结构，包括它们的逻辑结构、存储结构，以及相关的算法。武汉大学国际软件学院薛超英2014年8月

数据和数据结构数据抽象和抽象数据类型如何描述数据结构如何描述算法算法分析的基本方法第一单元基础知识

数据与数据结构基本术语

数据

：计算机加工处理的对象数值数据非数值数据

数据元素（结点、顶点）：组成数据的基本单位数据项（字段、域）：组成数据的最小单位武汉大学国际软件学院薛超英2014年8月

数据结构概念涉及三个方面

数据的逻辑结构：数据元素间的逻辑关系数据的存储结构：数据在计算机中的表示形式数据的运算：在数据上执行的操作武汉大学国际软件学院薛超英2014年8月南京邮电大学计算机学院陈慧南2006年9月

数据的逻辑结构

数据的逻辑结构对数据元素间逻辑关系的描述被称为数据的逻辑结构

。可以用二元组描述数据的逻辑结构：DS=（D，R）其中，D是数据元素的有限集合，R是D中元素序偶的集合。

（示例：P3）

武汉大学国际软件学院薛超英2014年8月

数据逻辑结构的分类

（a）集合结构（b）线性结构（c）树形结构

（d）图状结构

3类基本的逻辑结构：线性结构，树形结构，图状结构2类基本的逻辑结构：线性结构，非线性结构武汉大学国际软件学院薛超英2014年8月

数据的存储结构

顺序存储用一块连续的存储空间，把逻辑上相邻的数据元素依次存储在该连续的存储区中。

Loc（ak）＝102＋2*k武汉大学国际软件学院薛超英2014年8月

链接存储

基本存储结构

顺序存储结构链接存储结构索引存储结构散列存储结构DataLink

地址信息称为链。∧表示空链。武汉大学国际软件学院薛超英2014年8月

数据的运算创建运算:创建一个数据结构；清除运算:删除数据结构中的全部元素；插入运算:在数据结构的指定位置上插入一个新元素；删除运算:将数据结构中的某个元素删除；……武汉大学国际软件学院薛超英2014年8月

静态数据结构

一旦创建，其结构不再改变的数据结构。动态数据结构允许进行插入删除等操作，其结构是动态变化的数据结构。武汉大学国际软件学院薛超英2014年8月

数据结构的定义数据结构是指：按某种逻辑关系组织起来的一组数据元素，按一定的存储方法存储计算机中，并在其上定义了一个运算的集合。

没有公认的、标准的定义。武汉大学国际软件学院薛超英2014年8月数据抽象和抽象数据类型数据抽象和过程抽象封装和信息隐蔽数据类型和抽象数据类型数据结构和抽象数据类型

武汉大学国际软件学院薛超英2014年8月

数据抽象和过程抽象抽象：抽取共同的和本质的内容，忽略非本质的细节。

数据抽象：只关注数据元素间的逻辑关系，忽略数据在计算机中的具体表示。

过程抽象：只关注数据运算的定义，忽略运算的具体实现方法。抽象的好处：降低了问题求解的难度。武汉大学国际软件学院薛超英2014年8月

封装与信息隐蔽

封装:是指把数据和操纵数据的运算组合在一起的机制。使用者只能通过一组允许的运算访问其中的数据。信息隐蔽：对使用者隐藏了数据结构或程序的实现细节。通常将数据和操纵数据的运算组成模块。每个模块有一个明确定义的界面，模块内部信息只能经过这一界面被外部访问。武汉大学国际软件学院薛超英2014年8月

模块应采用封装和信息隐蔽原则来设计,这样的模块被称为黑盒子。

封装和信息隐蔽的好处：错误局部化，降低问题求解的复杂性，提高程序的可靠性。C++语言的类可以封装数据和运算，其公有、保护和私有成员机制有利于实现信息隐蔽。武汉大学国际软件学院薛超英2014年8月

数据类型和抽象数据类型

数据类型是程序设计语言中的概念，它是数据抽象的一种方式。一个数据类型定义了一个值的集合以及作用于该值集的运算集合。程序设计语言中，一个数据类型不仅规定了该类型的变量（或常量）的取值范围，还定义了该类型允许的运算。武汉大学国际软件学院薛超英2014年8月

抽象数据类型（abstractdatatypeADT）是一个数据类型，其主要特征是该类型的对象及其运算的规范,与该类型对象的表示和运算的实现分离，实行封装和信息隐蔽，即所谓使用和实现分离。武汉大学国际软件学院薛超英2014年8月

数据结构与抽象数据类型

数据的逻辑结构和数据的运算定义组成了数据结构的规范。数据的存储表示和运算算法的描述构成数据结构的实现。

从规范和实现两方面来讨论数据结构的方式是抽象数据类型的观点。一种数据结构被视为一个抽象数据类型。武汉大学国际软件学院薛超英2014年8月

描述数据结构和算法

数据结构的规范数据结构的实现武汉大学国际软件学院薛超英2014年8月

数据结构的规范

数据结构被看成是一个抽象数据类型(ADT)，用格式化的自然语言来描述。数据结构可以形式地用一个C++的抽象模板类描述。武汉大学国际软件学院薛超英2014年8月

ADT1.1栈ADTADTStack{

数据：

0个或多个元素的线性序列（a0,a1,...,an-1）,其最大允许长度为MaxStackSize。

运算：

Create()：建立一个空栈

Destroy()：撤消一个栈

Push(x)：值为x的新元素进栈，成为栈顶元素

Pop()：从栈中删除栈顶元素

Top(x)：在x中返回栈顶元素}武汉大学国际软件学院薛超英2014年8月

template<classT>classStack{//栈类Stack是一个模板抽象类，其成员函数为纯虚函数，未定义数据成员。

public: virtualboolPush(Tx)=0;virtualboolPop()=0;virtualboolTop(T&x)const=0;……};武汉大学国际软件学院薛超英2014年8月

数据结构的实现template<classT>classSeqStack:publicStack<T>{public:

……private:inttop;//top记录最后入栈的元素在s的下标

intmaxTop;//最大栈顶指针

T*s;//s指向动态生成的一维数组，存放元素};武汉大学国际软件学院薛超英2014年8月

template<classT>SeqStack<T>::SeqStack(intmSize){maxTop=mSize-1;//设置栈的容量值

s=newT[mSize];//生成存储栈的数组

top=-1;//top==－1表示空栈}武汉大学国际软件学院薛超英2014年8月

算法分析的基本方法

算法及其性能标准算法的时间复杂度渐近时间复杂度算法的空间复杂度最好、最坏和平均时间复杂度武汉大学国际软件学院薛超英2014年8月

算法及其性能标准

计算机算法的定义

一个有穷的指令序列，它规定了解决某一特定问题的一系列运算。问题：你知道“计算机程序”是如何定义的吗？武汉大学国际软件学院薛超英2014年8月

计算机算法具有下列5个特征输入：算法有零个或多个输入输出：算法至少产生一个输出确定性：算法的每一条指令都有确切的定义，没有二义性。能行性：算法的每一条指令都足够基本，它们可以通过已经实现的基本运算执行有限次来实现。有穷性：算法能在执行有限步之后终止。问题：计算机程序具有哪些特征？武汉大学国际软件学院薛超英2014年8月

“好算法”的4个特征正确：执行结果满足预先规定的功能和性能要求。简明：思路清晰、层次分明、易读易懂。健壮：输入不合法数据时，应能做适当处理。效率：高的时间效率、低的空间需求。问题：算法和程序是同一个概念吗？武汉大学国际软件学院薛超英2014年8月

算法的时间复杂度

算法的执行时间

算法的执行时间等于算法中各语句执行时间的总和，而某个语句的执行时间等于该语句执行一次所需时间与执行次数的乘积。问题规模

算法的执行时间一般都与问题规模有关。问题规模通常是一个与输入有关的量。算法分析的目标找出算法执行时间与问题规模之间的关系。武汉大学国际软件学院薛超英2014年8月

渐近时间复杂度算法的执行时间通常用数量级的形式（大O记号）表示：T(n)=O(f(n))其含义为：当问题规模n足够大时，算法的执行时间T(n)和函数f(n)成正比。或者说，存在正常数c和n0，当n≥n0时，有

|T(n)|≤c|f(n)|。如果算法执行时间T(n)与问题规模n无关，则记作

T(n)=O(1)。武汉大学国际软件学院薛超英2014年8月

用数量级形式表示的算法的执行时间，通常称为算法的渐近时间复杂度，或简称为时间复杂度。用O(f(n))表示算法执行时间T(n)的时候，函数f(n)通常取较简单的形式，例如

1、log2n、n、nlog2n、n2、n3、2n

在n较大的情况下，常见的时间复杂度之间存在下列关系：O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)

武汉大学国际软件学院薛超英2014年8月定理1

若T(n)=amnm+am–1nm–1+…+a1n+a0是一个m次多项式,则

T(n)=O(nm)武汉大学国际软件学院薛超英2014年8月定理2

若T1(n)、T2(n)分别是算法P1、P2的执行时间，并且T1(n)=O(f(n))T2(n)=O(g(n))则依次执行算法P1和P2，总的执行时间

T(n)=O(max(|f(n)|，|g(n)|))武汉大学国际软件学院薛超英2014年8月定理3

若T1(n)、T2(n)分别是算法P1、P2的执行时间，并且

T1(n)=O(f(n))T2(n)=k(n)T1(n)则

T2(n)=O(k(n)f(n))武汉大学国际软件学院薛超英2014年8月分析举例1

假设A[1]～A[n]中存放了n个整数，下面程序段的功能是确定其中值最大的整数在数组中的下标i。请分析程序段中每个语句的执行次数，并用数量级形式表示这个程序段的执行时间。i=1;for(j=2;j<=n;j++)if(A[j]>A[i])i=j;1次n次n–1次最多n–1次语句总的执行次数是2n~3n–1次，程序段执行时间是O(n)。武汉大学国际软件学院薛超英2014年8月分析举例2

假设A[1]～A[n]中存放了n个整数，其中n>100。下面程序段的功能是求其中前100个整数的平均值。请分析程序段中每个语句的执行次数，并用数量级形式表示这个程序段的执行时间。s=0.0;for(i=1;i<=100;i++)s=s+A[i];cout<<s/100;1次101次100次1次语句的执行次数和n无关，程序段的执行时间是O(1)。武汉大学国际软件学院薛超英2014年8月分析举例3下面程序段的功能是从n阶整型矩阵中找出两个值最小的整数。请分析其时间复杂度。m1=32767;m2=m1;for(i=0;i<n;i++)for(j=0;j<n;j++)if(A[i][j]<m1){m2=m1;m1=A[i][j];}elseif(A[i][j]<m2)m2=A[i][j];

执行第1行赋值语句所需时间是O(1)。执行一遍内循环体所需时间也是O(1)。由于内循环体总共执行了n2次,因此,程序段的执行时间为O(n2)。武汉大学国际软件学院薛超英2014年8月分析举例4

下面的程序段可用于求xn。请分析其时间复杂度。y=1;u=x;v=n;while(v>0){

if(v%2==1)y=y*u;u=u*u;v=v/2;}cout<<y;

执行时间主要用在while循环上。由于v的初始值是n，每循环一遍，v值被减半，因此，循环次数不超过log2n次。执行一遍循环体所需时间是O(1)。程序段的执行时间为T(n)=(log2n)O(1)=O(log2n)问题：这是个“好程序”吗？请你写一个功能相同的“好程序”，并分析其时间复杂度。武汉大学国际软件学院薛超英2014年8月分析举例5