计算机考研基础讲义-数据结构基础复习课程.ppt

《计算机考研基础讲义-数据结构基础复习课程.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构基础计算机考研小组(100)2019年计算机考研基础班讲义docin/sundae_meng第一章绪论什么是数据结构直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间关系和运算的一门学科。数据结构是指数据之间的关系按某种关系组织起来的一批数据。以一定的存储方式把它们存储到计算机的存储器中，并在这些数据上定义一个运算集合，这就是数据结构。学习数据结构的重要性“数据结构”在计算机科学中是一门综合性的专业基础课,在考研中占很大的分值。数据结构是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。数据结构这一门课的内容不仅是一般程序设计（特别是非数值性程序设计）的基础，而且是

2、设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。§1.2数据结构的概念一、基本概念数据：能输入计算机且被能计算机处理的一切对象。数据元素：对现实世界中某独立个体的数据描述。数据项：具有独立意义的最小数据单位。数据类型：每个数据项必须属于某确定的数据类型。基础§1.3数据的逻辑结构一、基本概念数据对象：具有相同特征的数据元素的集合。关系：在数据对象中各数据元素之间存在着某种关系（或联系）。这种关系反映了该数据对象中数据元素所固有的一种结构。在数据处理领域，通常把数据之间这种固有的关系简单的用前驱和后继关系描述。§1.3数据的逻辑结构二、数据的逻辑结构设D表示数据元素的集合，R

3、表示D上的关系的集合，则一个数据结构B可表示为：B=（D，R）由此可见数据结构由两部分构成（1）表示各元素的信息D（2）表示数据之间关系的信息R一般用二元组表示D中各数据元素之间的前驱、后继关系。假设a,b是D中的两个元素，则二元组表示a是b的前驱，b是a的后继。§1.3数据的逻辑结构三、数据结构的分类线性结构：除了一个根结点外，其他各结点有唯一的前驱；除了一个终端结点外，其他各结点有唯一的后继。树状结构：除了一个根结点外，各结点有唯一的前驱；所有的结点都可以有多个后继。网状结构：各结点可以有多个前驱或多个后继。§1.4数据的存储结构数据结构在计算机中的表示称为数据的存储结构。数据

4、结构包括结点的值及结点之间的关系，其存储结构除了必须存储结点的值外，还得能以直接或隐含的方式体现出结点之间的关系。四种基本的存储方式：1、顺序方式顺序结构最适合于线性结构，它把逻辑上相邻的结点存放到物理上相邻的存储单元中，顺序存储结构只存储结点的值，不存储结点的关系，结点的关系通过存储单元相邻关系隐含表示出来。§1.4数据的存储结构2、链接方式链接存储方式不仅存储结点的值，而且还存储结点之间的关系。它利用结点附加的指针字段，存储其后继结点的地址。3、索引方式在线性结构中，各结点可以依前驱、后继关系排成一个序列（a1,a2,a3,……an)。每个结点ai在序列中都对应一个序号i序号i也称为结点

5、ai的索引号。索引存储就是通过建立一个附加的索引表，然后利用索引表中的索引项的值来确定结点的实际存储单元的地址。§1.4数据的存储结构4、散列方式利用该结点的值确定该结点的存储单元地址。§1.5数据运算和算法1、数据运算按一定的逻辑结构把数据组织起来，采用适当的存储方式把数据结构存储到计算机中，最终的目的是为了有效地处理数据，提高数据的运算效率。1）插入：往数据结构中添加新的结点称为插入。2）删除：把指定的结点从数据结构中删除。3）更新：改变指定结点的值或者改变某些结点的关系称为更新。4）查找：在数据结构中查找某些满足条件的结点。5）排序：对线性表的各结点，按指定数据项的值从小到大或从大到小

6、的重新排列。排序运算实际上是破坏线性表的旧关系，重新建立线性表的新关系。§1.5数据运算和算法2、算法算法是对特定问题求解步骤的一种描述。算法应具有的几个特征：1）有穷性：算法应在计算机存储资源容许的条件下，在一定时间内执行完毕。2）确定性：算法的每一步骤应定义明确，没有二义。3）可行性：算法是可以被计算机执行的。当输入正确的数据后，应得到正确的结果。§1.5数据运算和算法3、算法的评价对算法评价的几个指标空间复杂度空间复杂度是指执行算法所需要的辅助空间大小。时间复杂度时间复杂度是指执行完算法所需的运算次数。第二章线性表线性表是一种最简单、最常用的数据结构。线性表的主要存储结构有两种：顺序存

7、储结构和链接存储结构。§2.1线性表的定义及基本运算一、线性表的定义线性表是由n(n≥0)个性质相同的数据元素a1,a2,a3,…an组成的有限序列，记为(a1,a2,a3,…an)。二、线性表的基本运算（1）置线性表为空表；（2）求线性表的长度；（3）读取线性表中的第i个元素；（4）修改线性表中的第i个元素；（5）查找线性表中具有某个特征值的数据元素；§2.1线性表的定义及基本运算二、线性表的基本运算（6）