第一章 数据结构及其基本概念.docx
- 文档编号:18480053
- 上传时间:2023-08-18
- 格式:DOCX
- 页数:11
- 大小:20.61KB
第一章 数据结构及其基本概念.docx
《第一章 数据结构及其基本概念.docx》由会员分享,可在线阅读,更多相关《第一章 数据结构及其基本概念.docx(11页珍藏版)》请在冰点文库上搜索。
第一章数据结构及其基本概念
第一章数据结构及其基本概念
1.1什么是数据结构(WhatisDataStructure)
数据结构是信息的组织方式。
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。
它用来反映一个数据的内部构成,即
一个数据由哪些成分数据构成,以什么方式构成,呈什么结构。
数据结构有逻辑上的数据结构和物理
上的数据结构之分。
逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分
数据在计算机内部的存储安排。
数据结构是信息的一种组织方式,好的数据结构可以提高算法的效率
,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。
从学
科角度来讲,数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关
系和操作等等的学科。
[二]数据结构学科的研究对象(TheObjectofDataStructureResearch)
数据结构作为一门学科,主要研究数据的各种逻辑结构和存储结构,以及对数据的各种操作。
因此
,主要有三个方面的内容:
数据的逻辑结构;数据的物理存储结构;对数据的操作(即算法)。
通常
,算法的设计取决于数据的逻辑结构,算法的实现取决于数据的物理存储结构。
数据结构的研究不仅
涉及到计算机硬件的研究,比如存储装置和存取方法,而且解决编译原理、操作系统、数据库系统的
数据元素在存储器中的分配问题的重要基础。
1.2基本概念与学科术语(BasicConceptsandTerminologies)
数据(Data):
是一个集合的概念,是对客观事物的符号表示,在计算机科学中是指所有能被输入到计
算机中,并被计算机处理的符号的总称。
是计算机处理的信息的某种特定的符号表示形式。
数据元素(DataElement):
是数据的基本单位,数据中的一个“个体”。
又称为“记录”或者“表目
”。
数据项(DataItem):
数据的不可分割的最小单位。
数据元素是数据项的集合。
数据对象(DataObject):
是性质相同的数据元素的集合,是数据的一个子集。
[总结]
数据项组成数据元素,数据元素组成数据对象,数据对象组成数据
数据结构(DataStructure):
是相互之间存在一种或多种特定关系的数据元素的集合。
它包括三个
方面:
数据元素的逻辑结构、存储结构和相适应的运算(操作)。
数据元素之间的逻辑关系被称为数据元素的逻辑结构,可以用一个二元组表示:
Data_Structure=(D,S)//Data_Structure=(Data-part,Logic-Structure-Part)
这里D是数据元素的集合,S是定义在D(或其他集合)上的关系的集合,
S={R│R:
D×D×...}。
数据的逻辑结构可归结为以下四类:
(1)集合结构
结构中的数据元素之间除了同属于一个集合的关系外别无其他关系
(2)线性结构
结构中的数据元素之间存在一个对一个的前趋后继关系
在此种结构下:
有且仅有一个元素无前趋元素
有且仅有一个元素无后继元素
其余任何一个元素均有且仅有一个前趋有且仅有一个后继元素。
(3)树形结构
结构中的数据元素之间存在一个对多个的关系
任何一个节点最多有一个前趋,可以有多个后继,是一种典型的非线性结构
(4)图状结构(网状结构)
结构中的数据元素之间存在多个对多个的关系
这种结构的特征是任何一个元素可以有多个前趋,也可以有多个后继,是一种多对多的前趋后继关系
表和树是最常用的两种高效数据结构,许多高效的算法可以用这两种数据结构来设计实现。
表是线
性结构的(全序关系),树(偏序或层次关系)和图(局部有序(weak/localorders))是非线性结构。
数据结构在计算机中的表示(又称为映像)称为数据的存储结构(物理结构)
数据结构的物理结构是指逻辑结构的存储映像(image)。
数据结构DS的物理结构P对应于从DS的
数据元素到存储区M(维护着逻辑结构S)的一个映射:
PD,S)-->M
存储器模型:
一个存储器M是一系列固定大小的存储单元,每个单元U有一个唯一的地址A(U),该
地址被连续地编码。
每个单元U有一个唯一的后继单元U'=succ(U)。
P的四种基本映射模型:
顺序(sequential)、链接(linked)、索引(indexed)和散列(hashing
)映射。
因此,我们至少可以得到4×4种可能的物理数据结构:
sequential(sets)
linkedlists
indexedtrees
hashing
graphs
需要指出的是:
并不是所有的可能组合都合理。
数据结构DS上的操作:
所有的定义在DS上的操作在改变数据元素(节点)或节点的域时必须保持DS的
逻辑和物理结构。
DS上的基本操作:
任何其他对DS的高级操作都可以用这些基本操作来实现。
最好将DS和他的所有基本
操作看作一个整体——称之为模块(model)。
我们可以进一步将该模块抽象为数据类型(其中DS的存
储结构被表示为私有成员,基本操作被表示为公共方法),称之为ADT(即是抽象数据类型Abstract
DataType,指一个数学模型以及定义在该模型上的一组操作)。
ADT按照其值的不同特性分为下列三种类型:
原子类型(AtomicDataType):
变量是不带结构的,不可分解的。
固定聚合类型(Fixed-aggregateDataType):
其值由确定数目的成分按照某种结构组成
可变聚合类型(Variable-AggregateDataType):
值的成分的数目不确定
抽象数据类型的描述方法
抽象数据类型可用(D,S,P)三元组表示
其中,D是数据对象,S是D上的关系集,P是对D的基本操作集。
ADT抽象数据类型名{
数据对象:
〈数据对象的定义〉
数据关系:
〈数据关系的定义〉
基本操作:
〈基本操作的定义〉
}ADT抽象数据类型名
其中,数据对象和数据关系的定义用伪码描述,基本操作的定义格式为
基本操作名(参数表)
初始条件:
〈初始条件描述〉
操作结果:
〈操作结果描述〉
基本操作有两种参数:
赋值参数只为操作提供输入值;引用参数以&打头,除可提供输入值外,还
将返回操作结果。
“初始条件”描述了操作执行之前数据结构和参数应满足的条件,若不满足,则操
作失败,并返回相应出错信息。
“操作结果”说明了操作正常完成之后,数据结构的变化状况和应返
回的结果。
若初始条件为空,则将其省略。
需要注意的是:
抽象数据类型需要通过固有数据类型(高级
编程语言中已实现的数据类型)来实现。
顺便提一句,多形数据类型(PolymorphicDataType)是指值的成分不确定的数据类型,不过这
个不太多见,或者是可以用ADT表示,所以我们在今后的章节再论述。
好的和坏的DS:
如果一个DS可以通过某种“线性规则”被转化为线性的DS(例如线性表),则称它
为好的DS。
好的DS通常对应于好的(高效的)算法。
这是由计算机的计算能力决定的,因为计算机本
质上只能存取逻辑连续的内存单元,因此如何没有线性化的结构逻辑上是不可计算的。
比如对一个图
进行操作,要访问图的所有结点,则必须按照某种顺序来依次访问所有节点(要形成一个偏序),必
须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。
树是好的DS——它有非常简单而高效的线性化规则,因此可以利用树设计出许多非常高效的算法。
树的实现和使用都很简单,但可以解决大量特殊的复杂问题,因此树是实际编程中最重要和最有用的
一种数据结构。
树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代,反之亦然。
实际上,每一种递归的结构都可以被转化为(或等价于)树形结构。
说到递归在北京大学的数据结构
课程里面有个老师经常说“不懂递归就不算北大计算机系的学生”,这样看来足以从侧面说明书的结
构的重要性。
1.3算法和算法分析
AlgorithmsandAlgorithmAnalysis
1.3.1算法
所谓算法(Algorithm)是对问题求解步骤的一种描述,是指令的有限序列,其中每一条指令表示
一个或多个操作。
在CLRS中是这样给出算法的定义的:
Informally,analgorithmisanywell-
definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputand
producessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceof
computationalstepsthattransformtheinputintotheoutput.
一个算法必须满足以下五个重要特性:
1.有穷性对于任意一组合法输入值,在执行有穷步骤之后一定能结束,即:
算法中的每个步骤都能
在有限时间内完成;
2.确定性对于每种情况下所应执行的操作,在算法中都有确切的规定,使算法的执行者或阅读者都
能明确其含义及如何执行。
并且在任何条件下,算法都只有一条执行路径;
3.可行性算法中描述的操作都可以通过已经实现的基本操作运算有限次实现之;
4.有输入作为算法加工对象的量值,通常体现为算法中的一组变量。
有些输入量需要在算法执行过
程中输入,而有的算法表面上可以没有输入,实际上已被嵌入算法之中;
5.有输出它是一组与输入有确定关系的量值,是算法进行信息加工后得到的结果。
1.3.2算法设计的原则
设计算法时我们应当严格考虑:
1.正确性(Correctness)
首先,算法应当满足以特定的“规格说明”方式给出的需求。
对算法是否“正确”的理解可以有以下
四个层次:
a.程序中不含语法错误;
b.程序对于几组输入数据能够得出满足要求的输出结果;
c.程序对于精心选择的、典型、苛刻的几组输入数据能够得出满足要求的结果;
d.程序对于一切合法的输入数据都能得出满足要求的结果;
通常以第c层意义的正确性作为衡量一个算法是否合格的标准。
因为作为输入,我们有时候不可能提前
做出所有的预期。
2.可读性(Readability)
算法主要是为了人的阅读与交流,其次才是为计算机执行。
因此算法应该易于人的理解;另一方面,
晦涩难读的程序易于隐藏较多错误而难以调试;有些程序设计者总是把自己设计的算法写的只有自己
才能看懂,这样的算法反而没有太大的价值。
3.健壮性(Rubustness)
当输入的数据非法时,算法应当恰当地作出反映或进行相应处理,而不是产生莫名奇妙的输出结果。
这就需要我们一定要充分的考虑异常情况(UnexpectedExceptions)并且,处理出错的方法不应是中
断程序的执行,而应是返回一个表示错误或错误性质的值,以便在更高的抽象层次上进行处理。
4.高效率与低存储量需求
通常,效率指的是算法执行时间;存储量指的是算法执行过程中所需的最大存储空间。
两者都与问题
的规模有关。
1.3.3算法效率的衡量方法与准则
通常有两种衡量算法效率的方法:
1.事后统计法
缺点:
(1)必须执行程序才能进行判断
(2)其它因素(如硬件、软件环境)掩盖算法本质
2.事前分析估算法
主要是看消耗的时间。
和算法执行时间相关的因素:
1.算法选用的策略
2.问题的规模
3.编写程序的语言
4.编译程序产生的机器代码的质量
5.计算机执行指令的速度
一个特定算法的“运行工作量”的大小,只依赖于问题的规模(通常用整数量n表示),或者说,它是
问题规模的函数。
假如,随着问题规模n的增长,算法执行时间的增长率和f(n)的增长率相同,则可记
作:
T(n)=O(f(n))
称T(n)为算法的渐近时间复杂度(AsymptoticTimeComplexity),简称时间复杂度。
O是数量级的
符号。
下面我们探讨一下如何估算算法的时间复杂度
算法=控制结构+原操作(固有数据类型的操作)
算法的执行时间=原操作(i)的执行次数×原操作(i)的执行时间
算法的执行时间与原操作执行次数之和成正比
我们先介绍一个概念:
for(j=1;j<=n;++j)
for(k=1;k<=n;++k){++x;x+=x;}
语句重复执行的次数被称为语句的频度(FrequencyCount)上程序段中++x的语句频度就是n2。
我们经常采用:
从算法中选取一种对于所研究的问题来说是基本操作的原操作,以该基本操作在算法
中重复执行的次数作为算法运行时间的衡量准则。
这个原操作多数情况下是最深层次循环内的语句中
的原操作。
例如:
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];
}
该算法的基本操作是乘法操作。
时间复杂度为O(n3)
1.3.4算法的存储空间(MemorySpaceforAlgorithms)
算法的空间复杂度S(n)=O(g(n))
表示随着问题规模n的增大,算法运行所需存储量的增长率与g(n)的增长率相同。
算法的存储量包括:
1.输入数据所占空间;
2.程序本身所占空间;
3.辅助变量所占空间。
若输入数据所占空间只取决与问题本身,和算法无关,则只需要分析除输入和程序之外的额外空间。
若所需额外空间相对于输入数据量来说是常数,则称此算法为原地工作。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 数据结构及其基本概念 数据结构 及其 基本概念
![提示](https://static.bingdoc.com/images/bang_tan.gif)