数据结构ch01

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

1、第一章绪论内容提要及考试重点：相关基本概念算法时间复杂度的度量1.1什么是数据结构1.2基本概念和术语1.3抽象数据类型的表示与实现1.4算法和算法分析1.4.1算法1.4.2算法设计的要求1.4.3算法效率的度量1.4.4算法的存储空间的需求1.1什么是数据结构数据结构与程序设计密切相关，1969年，NiklausWirth提出：Algorithm+DataStructure=Program程序设计：为计算机处理问题编制一组指令集如何进行处理？------算法对处理的信息如何表示？-----问题的数学模型----数据结构数值计算的程序设计

2、问题：桥梁结构压力---线性方程组预报人口增长---常微分方程是计算数学研究内容非数值计算的程序设计问题：图书馆的书目检索系统自动化问题人机对弈多叉路口交通灯的管理问题是数据结构的研究内容计算机的程序是对信息进行加工处理。在大多数情况下，这些信息并不是没有组织，信息（数据）之间往往具有重要的结构关系，这就是数据结构的内容。那么，什么是数据结构呢？先看以下几个例子。姓名电话号码张三…李四……………例1电话号码查询问题二维数组…算法的设计，依赖于计算机如何存储人的名字和对应的电话号码，或者说依赖于名字和其电话号码的结构。数据的结构，直接影响算法

3、的选择和效率。上述的问题是一种数据结构问题。可将名字和对应的电话号码设计成：二维数组、表结构、向量。概括地说，数据结构描述现实世界实体的数学模型（非数值计算）及其上的操作在计算机中的表示和实现。例2书目自动检索系统登录号：书名：作者名：分类号：出版单位：出版时间：价格：书目卡片书目文件按书名按作者名按分类号索引表线性表例3人机对奕问题……..……..…...…...…...…...例4多叉路口交通灯管理问题CEDABABACADBABCBDDADBDCEAEBECED图数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结

4、构定义相应的运算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。1.2基本概念和术语数据和数据结构数据（Data）是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并能被计算机处理的符号的总称。包括字符、图形、声音等等。1.2基本概念和术语数据元素（DataElement），是数据的基本单位，在计算机程序中通常作为一个整体进行考虑处理。一个数据元素可由若干个数据项（DataItem）组成。数据项是数据的不可分割的最小单位。姓名俱乐部名称出生日期年月日入队日期职位业绩1.2基本概念和术语例：一个12位的十进制数可以用三

5、个4位的十进制数表示：3214，6587，9345a1（3214），a2（6587），a3（9345）在a1，a2，a3之间存在“次序”关系：，3214，6587，9345不等于6587，3214，93451.2基本概念和术语例：2行3列的二维数组（a1，a2，a3，a4，a5，a6）行的次序关系row={，，，列的次序关系：col={，，}a1a2a3a4a5a61.2基本概念和术语数据对象（DataObject

6、）：是性质相同的数据元素的集合，是数据的一个子集。数据结构，是带结构的数据元素的集合，是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。逻辑结构和物理结构数据之间的相互关系称为逻辑结构。通常分为四类基本结构：1.2基本概念和术语1.2基本概念和术语一、集合结构中的数据元素除了同属于一种类型外，别无其它关系。二、线性结构结构中的数据元素之间存在一对一的关系。三、树型结构结构中的数据元素之间存在一对多的关系。四、图状结构或网状结构结构中的数据元素之间存在多对多的关系。1.2基本概念和术语概括地说，数据结构分为线性

7、结构和非线性结构。线性结构包括：线性表、向量、栈、队列、链表、字符串非线性结构包括：树、图、多维数组、稀疏矩阵等。数据结构的形式定义为：数据结构是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例复数的数据结构定义如下：Complex=(C，R)其中：C是含两个实数的集合﹛C1，C2﹜，分别表示复数的实部和虚部。R={P}，P是定义在集合上的一种关系{〈C1，C2〉}。1.2基本概念和术语数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。数据结构在计算机中有两种不同的表示方法：

8、顺序表示和非顺序表示由此得出两种不同的存储结构：顺序存储结构和链式存储结构顺序存储结构:用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。链式存储结构：在每一个数据元素