数据结构第1章 绪论48525new

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

1、1.1数据结构及其概念《算法与数据结构》是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。第1章绪论数据(Data)：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素(DataElement)：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。一个数据元素可由若干个数据项(DataIte

2、m)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。数据对象(DataObject)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C={‘A’,’B’,’C,…}。1.1.2基本概念和术语数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的

3、数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。1.1.3数据结构的形式定义图1-3四类基本结构图1.1.4数据结构的存储方式数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序

4、存储结构和链式存储结构。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。顺序结构：数据元素存放的地址是连续的；链式结构：数据元素存放的地址是否连续没有要求。数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。数据结构的三个组成部分：逻辑结构：数据元素之间逻辑关系的描述D_S=（

5、D，S）存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储结构如图1-4所示。抽象数据类型(AbstractDataType，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。ADT的定义仅是一组逻辑特性描述，与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。ADT的形式化定义是三元组：ADT=(D，S，P)其中：D是数据对象，S是D

6、上的关系集，P是对D的基本操作集。1.2抽象数据类型1.3.1算法算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。算法具有以下五个特性①有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。②确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。③可行性：一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。1.3算法分析初步④输入：一个算法有零个或多个输入

7、，这些输入取自于某个特定的对象集合。⑤输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。时间复杂度与空间复杂度。算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种：事后统计：计算机内部进行执行时间和实际占用空间的统计。问题：必须先运行依据算法编制的程序；依赖软硬件环境，容易掩盖算法本身的优劣；没有实际价值。事前分析

8、：求出该算法的一个时间界限函数。1.3.3算法效率的度量与此相关的因素有：依据算法选用何种策略；问题的规模；程序设计的语言；编译程序所产生的机器代码的质量；机器执行指令的速度；撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。算法分析应用举例算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作T(n)=O(f(n))，称作算法的渐近