数据结构 基本概念

数据结构基本概念第1页，共40页，2023年，2月20日，星期六第一章基本概念什么是数据结构数据结构的抽象层次算法定义性能分析与度量第2页，共40页，2023年，2月20日，星期六“学生”表格初等项：如学生性别、籍贯等，不能再分割的最小数据单位。组合项：如一组成绩，可以再划分为物理成绩、化学成绩等更小的项。第3页，共40页，2023年，2月20日，星期六

选课关系包含如下信息

学号课程编号成绩

学生选课系统中实体构成的网状关系第4页，共40页，2023年，2月20日，星期六UNIX文件系统的系统结构图在应用程序中涉及到各种各样的数据，为了存储它们，组织它们，需要讨论它们的归类及它们之间的关系，从而建立相应的数据结构，并依此实现要求的软件功能。第5页，共40页，2023年，2月20日，星期六数据：信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数值性数据如整数、实数、双精度数等主要用于工程和科学计算，及商业事务处理中使用。非数值性数据如字符串、多媒体信息（文字、图形、语音）等。数据对象：数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}英文字母数据对象LETTER={‘A’,‘B’,…,‘Z’}学生数据对象第6页，共40页，2023年，2月20日，星期六什么是数据结构？定义:一组数据对象及数据对象之间的关系组成。记为：

Data_Structure={D,R}其中，D是数据对象的有限集合，R是该集合中所有数据对象之间的关系的有限集合。

n个网站之间的连通关系以最小代价将n个网站连通树形关系任一网站出现故障而整个网络畅通网状关系第7页，共40页，2023年，2月20日，星期六数据结构的分类

根据数据对象之间的关系不同，分为两大类：线性结构非线性结构线性结构中各个数据对象依次排列在一个线性序列中；非线性结构中各个数据对象不再保持在一个线性序列中，每个数据对象可能与零个或多个其它数据对象有某种特定的联系。第8页，共40页，2023年，2月20日，星期六根据考虑问题的角度不同，分为两大类：逻辑结构物理结构逻辑结构是指从解决问题出发，为实现必要的功能所建立的数据结构，属于用户视图，面向问题，根据问题所要实现的功能建立；物理结构是指数据应该如何在计算机中存放，是数据逻辑结构的存储方式，是属于具体实现的视图，面向计算机，根据问题所要求的响应速度、处理时间、修改时间、存储空间和单位时间的处理量等建立。 第9页，共40页，2023年，2月20日，星期六抽象数据类型数据类型

定义：一组性质相同的值的集合,以及定义于这个值集合上的一组操作的总称.由用户定义，用以表示应用问题的数据模型，由基本的数据类型组成,并包括一组相关的服务（或称操作）特征是使用与实现相分离，实行信息隐蔽和数据封装。在抽象数据类型设计时，把类型的声明与其实现分离开来。第10页，共40页，2023年，2月20日，星期六抽象数据类型第11页，共40页，2023年，2月20日，星期六严格区分抽象数据类型的两个不同视图从使用者角度只要了解该抽象数据类型的规格说明，就可以利用其公共界面中的服务来使用这个类型，而不必关心其物理实现，这样使用者可以在开发过程中抓住重点，集中精力考虑如何解决应用问题，使问题得到简化。从实现者角度把抽象数据类型的物理实现封装起来，有利于编码、测试以及将来修改。因为这样做可以使错误局部化，一旦出现错误，其传播范围不至于影响其它模块。如果为了提高效率希望改进数据结构，可能需要改变抽象数据类型的物理实现，但只要界面中的服务的使用方式不变，其它所有使用该数据类型的程序都可以不变，从而大大提高系统稳定性。第12页，共40页，2023年，2月20日，星期六

数据结构的抽象层次最高的数据抽象是一个聚集类，其作用是把所有的数据抽象关联在一起，代表数据结构，并给出数据结构都具有的操作——初始化(initial)、插入(insert)、删除(delete)和查找(search)。第13页，共40页，2023年，2月20日，星期六线性聚类——线性表类中所有数据成员都按某种次序排列在一个序列中。根据对聚集中元素存取方法的不同：直接存取类数组、记录、文件直接存取某一指定项而不须先访问其前驱。顺序存取类栈、队列、表只能从序列中第一个元素起，按序逐个访问到指定的元素。广义索引类散列表、词典“关键码——值”偶对的集合。第14页，共40页，2023年，2月20日，星期六非线性聚类所有数据元素与其它数据元素之间不存在简单的线性关系。根据关系的不同：层次聚集类树，二叉树，堆按层次划分的数据元素的集合，指定层次上元素可以有零个或多个处于下一层次上的直接后继。群聚集类集合，图所有元素之间没有任何顺序关系。第15页，共40页，2023年，2月20日，星期六线性聚集类中各数据成员之间的线性关系树形结构树二叉树二叉搜索树第16页，共40页，2023年，2月20日，星期六堆结构“最大”堆“最小”堆第17页，共40页，2023年，2月20日，星期六群聚类图结构网络结构第18页，共40页，2023年，2月20日，星期六算法定义定义：一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。特性：输入

必须有0个或多个输入，是算法开始运算前给于算法的量。输出应有一个或多个输出(处理结果)，输出的量是算法计算的结果。确定性每步定义都是确切、无歧义的，对于每一种情况，需要执行的动作都应严格地、清晰地规定。有穷性算法应在执行有穷步后结束。有效性每一条运算应足够基本，原则上能够精确执行，甚至人们仅用笔和纸做有限次运算就能完成。第19页，共40页，2023年，2月20日，星期六事例学习：选择排序问题明确问题：非递减排序解决方案：逐个选择最小数据算法框架：

for(inti=0;i<n-1;i++){//n-1趟

从a[i]检查到a[n-1];

若最小的整数在a[k],交换a[i]与a[k];

}细化程序：程序SelectSort

如何选择值最小的数据；如何交换两个数据的值。算法设计

自顶向下，逐步求精

第20页，共40页，2023年，2月20日，星期六

voidselectSort(

inta[],constintn){

//对n个整数a[0],a[1],…,a[n-1],

按非递减顺序排序

for(

inti=0;i<n-1;i++){

int

k=i;

//从a[i]检查到a[n-1],找最小的整数,在a[k]

for(

intj=i+1;j<n;j++)

if(a[j]<a[k])k=j;

//k指示当前找到的最小整数

int

temp=a[i];a[i]=a[k];a[k]=temp;

//交换a[i]与a[k]}}

第21页，共40页，2023年，2月20日，星期六算法的性能分析与度量算法的性能标准算法的空间复杂性算法的时间复杂性第22页，共40页，2023年，2月20日，星期六算法的性能标准数据结构的优劣与算法直接有关，其性能由实现其各个服务的算法来体现。对数据结构的分析实质上是对实现其各个服务的算法的性能的分析。判断一个算法的优劣的标准：正确性——最重要标准要求算法能够正确地执行预先规定的功能和性能要求。要求算法的编写者对问题要求有正确的理解；正确地、无歧义地描述和利用某种编程语言正确地实现对算法的要求。第23页，共40页，2023年，2月20日，星期六可使用性——用户友好性要求算法能够很方便地使用。为了便于用户使用，要求算法具有良好的界面，完备的用户文档。算法设计必须符合抽象数据类型和模块化的要求；最好所有的输入和输出数据都通过参数表显示地传递，少用公共变量；每一个算法只完成一个功能。第24页，共40页，2023年，2月20日，星期六可读性算法应当可读，是理解、测试和修改算法的需要。为了达到这一要求，算法逻辑必须清晰、简单和结构化：所有的变量名、函数名的命名必须有实际含义，让人见名知义；在算法中必须加入注释，简要说明：算法的功能；输入与输出参数的使用规则；重要数据的作用；算法中各程序段完成的功能等。第25页，共40页，2023年，2月20日，星期六效率算法执行时计算机资源的消耗，包括存储（空间代价）和运行时间（时间代价）的开销。与多种因素有关：计算机系统、可用存储容量和算法复杂性。健壮性——容错性或例外处理要求在算法中加入对输入参数、打开文件、读文件记录、子程序调用状态进行自动检错、报错并通过与用户对话来纠错的功能。一个算法必须具有健壮性，能够对不合理的数据进行检查。在算法初写时可暂不管，待算法成熟时再追加。第26页，共40页，2023年，2月20日，星期六算法的运行时间依赖于所使用的计算机系统、编译器、可用存储空间大小等。同样的算法在速度不同的计算机上，执行速度相差非常大。算法用不同的编译器编译出的目标代码不一样长，完成同样功能所需时间不同。如果可用存储空间不够，算法需要的运行时间很多；如果空间足够大，则时间明显减少。通过比较算法的复杂性来评价。算法复杂性与具体运行环境和编译器无关。第27页，共40页，2023年，2月20日，星期六空间复杂性(SpaceComplexity)当问题的规模以某种单位从1增加到n时，解决这个问题的算法在执行时所占的存储空间也以某种单位由1增加到f(n)。问题的规模可以从问题的描述中找到。因为算法针对某一实例（类的对象），问题规模可视为实例的特性。在有n个记录的学生文件中查找某个学生，或者对一个n阶线性方程求解，n即为问题的规模。空间单位一般规定为一个工作单元所占的存储空间的大小。第28页，共40页，2023年，2月20日，星期六空间复杂性度量存储空间的固定部分

主要包括程序指令代码的空间，常数、简单变量、定长成分(如数组元素、结构成分等)变量所占的空间等，属静态空间，只要做简单的统计就可估算。可变部分

主要包括尺寸与实例特性有关的成分变量所占空间、引用变量所占空间、以及递归栈所用的空间，还有在算法运行过程中通过动态分配和动态删除动态使用的内存空间。第29页，共40页，2023年，2月20日，星期六时间复杂性和度量编译时间与编译程序有关，与实例特性无关。运行时间从程序结构着手，统计算法的程序步数。语法上或语义上有意义的一段指令序列执行时间与实例特性无关程序步数举例：

注释：0声明语句：0

表达式：1赋值语句：>0第30页，共40页，2023年，2月20日，星期六例以迭代方式求累加和的函数行

float

sum(float

a[],

constint

n)

1

{

2

floats=0.0;

3

for(

inti=0;i<n;i++)

4

s+=a[i];

5

returns;

6

}

程序步确定方法

在程序中插入计数全局变量count；

建表，列出程序内各个语句的程序步数。第31页，共40页，2023年，2月20日，星期六

在求累加和程序中加入count语句

float

sum(

floata[],

constint

n) {floats=0.0;count++;

//count是全局变量，统计执行语句条数

for(

inti=0;i<n;i++)

{

count++; //针对for语句

s+=a[i]; count++;

}

//针对赋值语句

count++; //针对for的最后一次

count++; //针对return语句

returns;}

执行结束得程序步数count=2*

n+3第32页，共40页，2023年，2月20日，星期六程序的简化形式

void

sum(

float

a[],

constint

n){for

(

inti=0;i<n;i++)count+=2;count+=3;}

第33页，共40页，2023年，2月20日，星期六注意：

一个语句本身的程序步数可能不等于该语句一次执行所具有的程序步数。

例如：赋值语句

x=sum(R,n);

本身的程序步数为1；

一次执行对函数sum(R,n)

的调用需要的程序步数为2*n+3；

一次执行的程序步数为

1+2*n+3=2*n+4第34页，共40页，2023年，2月20日，星期六时间复杂性的渐进表示法全面分析一个算法，需要考虑在最坏、最好、平均情况下的时间代价。大O表示法——最坏情况当且仅当存在正整数c和n0，使得T(n)≤cf(n)对所有的n≥n0成立，则称该算法的渐进时间复杂度为T(n)=O(f(n))。当实例特性n充分大时，算法的时间复杂度随n变化，在最坏情况下若存在一个增长的上界，即cf(n)，则该算法的时间复杂度增长的数量级为f(n)，即称该算法的渐进时间复杂度为T(n)=O(f(n))。第35页，共40页，2023年，2月20日，星期六大O表示法的使用需要考虑关键操作的程序步数；关键操作大多在循环和递归中；在大多数场合中，程序步骤与执行频度一一对应。如果给出的是渐进值，可直接考虑关键操作的执行频度，提出其与实例特性n的函数关系g(n)，从而得到渐进时间复杂度。渐进时间复杂度的计算单个循环在循环内的简单语句即为关键操作，该程序段的渐进时间复杂度应是此关键操作的执行频度的大O表示。第36页，共40页，2023年，2月20日，星期六几个并列的循环先分析每个循环的渐进时间复杂度，然后利用大O表示法的加法规则来计算渐进时间复杂度。大O表示法的加法规则当两个并列的程序段的时间代价分别为T1(n)=O(f(n))和T2(m)=O(g(m))时，则将两个程序段连在一起后整个程序段的时间代价为：

T(n,m)=T1(n)+T2(m)=O(max(f(n),g(m)))

所谓(max(f(n),g(m))，是指当n与m充分大时f(n)与g(m)中的大值，具有如下关系：

c<log2n<n<nlog2n<n2<n3<2n<3n<n!取c、log2n、n、nlog2n时间效率比较高；取n2、n3时间效率差强人意；取2n、3n、n!当n稍微大一点，算法的时间代价变为很大，以至于不能计算。第37页，共40页，2023年，2月20日，星期六两个并列循环的例子

void

example(floatx[][],intm,int

n,intk){float

sum[];for(inti=0;

i<m;i++){//x[][]中各行

sum[i]=0.0;//数据累加

for(intj=0;j<n;

j++)

sum[i]+=x[i][j];//关键操作1，渐进时间复杂度为O(m*n)。

}

for(i=0;i<m;i++)//打印各行数据和

printf(

"

Line%d:%d\n“,i,sum[i]);//关键操作2，渐进时间复杂度为O(m)。

}//根据大o表示法的加法规则，渐进时间复杂度为O(max(m*n,m))第38页，共40页，2023年，2月20日，星期六多层的嵌套循环关键操作应该在最内层循环中，先自外向内层层分析每层循环的时间渐进复杂度，然后利用大O表示法的乘法规则来计算渐进时间复杂度。大O表示法的乘法规则当两个嵌套的程序段的时间代价分别为T1(n)=O(f(n))和T2(m)=O(g(m))时，整个程序的时间代价为

T(n,m)=T1(n)*T2(m)=O(f(n)*g(m))如果一个程序的循环中有一个包含有循