数据结构第1章 绪论

《数据结构第1章 绪论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题：●信息的表示;●信息的处理。而信息的表示和组织又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，为了编写出一个“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。1.1什么是数据结构计算机解决一个问题的步骤：①从具体问题中抽象出一个适当的数学模型；②设计一个解此数学模型的算法；③编制程序（用程序设计语言描述算法）、测试，得到结果；例1：书、人→数据，

2、结构（分类法）：线性结构；算法→查找例2：格局→数据，结构（棋局之间的关系）：树结构；算法→搜索o××oo×o×ooo××××××××o×o×o×o×o×例3：通道（两个路口）→数据（顶点），结构（不可同时通行）：图结构；算法→图着色通道表示：EC,AC,AD,DA等。通道CABD1B颜色EEAA21.2基本概念和术语●数据(Data):是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。●数据元素(DataElement):是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。●数据项（DataItem):一个数

3、据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。●数据对象(DataObject)：是性质相同的数据元素的集合。是数据的一个子集。●数据结构(DataStructure)：是相互之间存在一种或多种特定关系的数据元素的集合。四种结构：①集合:结构中的数据元素除了同属于一种类型外，别无其它关系。②线性结构:结构中的数据元素之间存在一对一的关系。③树型结构:结构中的数据元素之间存在一对多的关系。④图状结构或网状结构:结构中的数据元素之间存在多对多的关系。数据结构的形式定义：数据结构是一个二元组：Data_Structure=(D,S)其中：D是数据元素的有限

4、集，S是D上关系的有限集。●数据的逻辑结构：数据之间的相互关系称为逻辑结构。（P6）●数据的物理结构（存储结构）数据结构在计算机中的表示（数据元素，关系）。●数据元素之间的关系在计算机中有两种不同的表示方法顺序映象和非顺序映象。●顺序映象的特点借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。●非顺序映象的特点：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。例1-5课题小组（P5）TG1G3G2S1S2S3T非顺序映象，链式G1ΛΛG2ΛΛG3ΛΛS1ΛΛΛS1ΛΛΛS1ΛΛΛ0123456789TG1G2G3S1S2S3顺序映象●数据类型（Data

5、Type）：是一个值的集合和定义在这个值集上的一组操作的总称。（出现在高级程序设计语言中，用以刻画操作对象的特性，如存储空间的大小和存储的方式等）●抽象数据类型(AbstractDataType)：是指一个数学模型以及定义在该模型上的一组操作。（数据类型的数学抽象，范畴更广，可包括用户自己定义的数据类型）。抽象数据类型可以用以下的三元组表示：ADT=（D，S，P）其中，D是数据对象，S是D上关系集，P是对D的基本操作集。本书的定义格式：ADT抽象数据类型名{数据对象：数据对象的定义数据关系：数据关系的定义基本操作：基本操作的定义}ADT抽象数据类型名1．3抽象数据类

6、型的表示和实现#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1（不可行的）#defineOVERFLOW–2typedefintStatus;数据类型约定为：ElemType1．4算法和算法分析1．4．1算法算法（Algorithm）：是对特定问题求解步骤的一种描述，它是指令的有限序列。特性：①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成.②确定性：算法中每一条指令必须有确切的含义，不存在二义性，且算法只有一个入口和一个出口。③可行性：一个算法是可行的。

7、即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。④输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。1．4．2算法设计的要求(1)正确性(Correctness)：算法应满足具体问题的需求。(2)可读性(Readability)：算法应该好读。以有利于阅读者对程序的理解。(3)健壮性(Robustness)：算法应具有容错处理。当输入非法数据时，算法应对其作出反应，而不是产生莫名其妙的输出结果。(4)效率与存储量需求：效率指的是算法执行的时间；存储量需求指算