数据结构第1～4课时.ppt

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

1、021052班《数据结构基础》课程上机安排2012.4.6下午2:00~6:00E2072012.5.18下午2:30~6:30E2072012.6.1下午2:30~6:30E2071电子工程学院数据结构基础西安电子科技大学智能信息处理研究所学习指导信息同学们在学习本课程的过程中应当注意基本概念、基本方法、算法的阅读理解和算法的设计等方面。在学习过程中可以通过课件的内容、例题、习题来理解和掌握。3电子工程学院本课程的教学目的和要求掌握线性表、栈、队列、串、数组、树和图等数据的逻辑结构、存储结构及有关的算法，以及数据的查找和排序方法。使用类C语言描述算法，能够分析算法

2、和设计算法。数据结构的学习过程也是较复杂程序设计的训练过程。在编写程序解决实际问题时，应当采用规范的算法，并且按照软件开发方法所要求的模块独立性高的原则，设计出高质量的程序。4电子工程学院主要内容数据结构概述线性表栈队列串数组树图查找排序5电子工程学院一、数据结构概述主要内容：1.数据结构的基本概念和术语2.算法的概念3.算法的时间特性及时间复杂度的分析4.算法的空间特性及空间复杂度的分析6电子工程学院1.1数据结构的基本概念和术语数据：数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例如：一个二维表是一个数据。数据元素：数据的基本单位。数据元素

3、也称为元素、结点、顶点、记录。例如：二维表中的某一行是一个数据元素。数据项：一个数据元素可以由若干个数据项组成，数据项是具有独立含义的，不可再分割的最小标识单位。例如：二维表中某一行的某一列是一个数据项。7电子工程学院数据结构(datastructure)是相互之间存在一种或多种特定关系的数据元素的集合。在很多问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构（structure）。根据数据元素之间关系的不同特性，通常有下列四种基本结构：（1）集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系；（

4、2）线性结构结构中的数据元素之间存在一个对一个的关系；(3)树形结构结构中的数据元素之间存在一个对多个的关系；（4）图状结构或网状结构结构中的数据元素之间存在多个对多个的关系。8电子工程学院数据结构所研究的主要内容包括以下三个方面：（1）数据的逻辑结构——数据元素之间的逻辑关系（2）数据的存储结构——数据结构在计算机中的存储方法（3）数据的运算——对数据施加的操作9电子工程学院数据类型：确定了一个值域以及对该类型数据可以进行的操作。按“值”是否可分解，可以将数据类型划分为两类：（1）原子类型，其值不可分解。如C语言中的基本类型（整型、实型、字符型等）、指针类型。（2

5、）结构类型，其值可分解为若干个成分。如数组、结构体等类型的数据还可以进一步分解。10电子工程学院数据的逻辑结构分为两大类：（1）线性结构。其逻辑特征为：若数据结构是非空集，第一个结点没有直接前趋结点，最后一个结点没有直接后继结点，其余结点都有一个直接前趋结点和一个直接后继结点。线性表、栈、队列、串等都是线性结构。（2）非线性结构。其逻辑特征为：一个结点可能有多个直接前趋和直接后继结点。树、图等属于非线性结构。11电子工程学院数据的存储结构可以有以下四种基本的存储方法：（1）顺序存储方法。结点间的逻辑关系由存储单元的邻接关系来体现。（2）链接存储方法。通过指示元素存

6、储地址的指针表示数据元素之间的逻辑关系，即逻辑上相邻的结点在物理位置上不一定相邻。（3）索引存储方法。在存储结点的同时，还建立附加的索引表，索引表中的每一项称为索引项（索引项包括：关键字，地址），关键字是能够唯一标识一个结点的那些数据项。若每个结点在索引表中都有一个索引项，称为稠密索引；若一组结点在索引表中对应一个索引项，称为稀疏索引。12电子工程学院（4）散列存储方法。根据结点的关键字直接计算出该结点的存储地址。上述四种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储。例如采用拉链法表示散列表，是顺序存储方法与链式存储方法的组合。同一种逻辑结构采用

7、不同的存储方法，可以得到不同的存储结构。例如线性表可以采用顺序存储结构（顺序表）和链式存储结构（链表）。每一种数据的逻辑结构对应一组基本运算，而基本运算的实现与数据的存储结构有关。13电子工程学院总体说来，数据结构可定义为：按某种逻辑关系组织起来的一批数据，按一定的映射方式把它们存放在计算机的存储器中，并且在这些数据上定义一个运算的集合。数据结构与算法之间存在着本质联系。在某一类型数据结构上，总要涉及其上施加的运算，而只有通过对运算的研究，才能清楚地理解数据结构的定义与作用；在涉及运算时，总要联系到该算法处理的对象和结果的数据。N.Wirth（沃思，瑞典）数据结