《数据结构复习》PPT课件

《《数据结构复习》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构主讲：刘仁芬<识记>熟悉各名词、术语的含义，掌握基本概念。<重点>理解算法五个要素的确切含义。<难点>掌握计算语句频度和估算算法时间复杂度的方法。本章知识点第一章绪论1.1什么是数据结构本章目录1.2基本概念和术语1.3抽象数据类型的表示和实现第1章绪论本节总结1.4算法和算法分析数据（data)—对客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的集合，计算机操作对象的总称.如整数，实数，字符串，图像，声音是数据。数据元素（dataelement）—数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据

2、元素可由若干个数据项组成。数据项（dataitem）—数据的不可分割的最小单位.如一本书的书目信息为一个数据元素，书目信息中的每一项（如书名，作者名，出版日期（组合项））为一个数据项。1.2基本概念和术语数据对象是性质相同的数据元素的集合，是数据的一个子集。如整数数据对象是集合N={0,±1,±2,…}，字母字符数据对象是集合C={‘A’,’B’,’C’,……，’Z’}。数据结构（datastructure)—是相互之间存在一种或多种特定关系的数据元素的集合。结构（数据元素相互之间的关系）（集合）——数据元素间除“同属于一个集合”外，无其它关系线

3、性结构——一个对一个，如线性表、栈、队列树形结构——一个对多个，如树图状结构——多个对多个，如图根据数据元素间关系的不同特性，有四种基本结构数据结构的形式定义为：数据结构是一个二元组Data_Structure=(D,S)其中：D是数据元素的有限集，S是D上关系的有限集数据的逻辑结构—结构定义中的“关系”，描述的是数据元素之间的逻辑关系，因此称为数据的逻辑结构。是对操作对象的一种数学描述，从操作对象抽象出来的数学模型。从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据的存储（物理）结构—是数据结构在计算机中的表示（又称映像）。包括数据

4、元素的表示和关系的表示。指数据元素及其关系在计算机存储器内的表示。存储结构是逻辑结构用计算机语言的实现，依赖于计算机语言。数据元素的表示：位：二进制数的一位，表示信息的最小单位。数据元素/结点：由若干位组合起来形成的一个位串，即数据元素在计算机中的映像。数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。数据元素之间的关系的表示：关系都可以表示成有序对的集合。a1a2a3a4a5a6,,,数据元素之间的关系的表示即有序对集合的映像

5、。数据元素之间的关系的表示方法：顺序映像和非顺序映像。对应两种不同的存储结构：顺序存储结构和链式存储结构。顺序映像特点:是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。中y的存储位置与x相差一个常量C，C是一个隐含值。xyc非顺序映像特点:是借助附加信息（指示元素存储地址的指针）来表示数据元素之间的逻辑关系。中附加信息与x存储在一起，指向y的存储地址。yx不同的编程环境数据结构的描述不同，比如高级语言就可以用数组来描述顺序存储结构。数据的逻辑结构数据的存储结构线性结构非线性结构顺序存储链式存储线性表栈队列树形结构图

6、形结构数据结构数据的运算：检索、排序、插入、删除、修改等数据类型：是一个值的集合和定义在这个集上的一组操作的总称。数据类型分为两类：一类是非结构的原子类型。原子类型的值是不可分解的。如C语言中的基本类型（整型、实型、字符型和枚举），指针类型和空类型。另一种是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是结构的，也可以是非结构的。如数组是由若干分量组成，每个分量可以是整数，也可以是数组。结构类型可以看成由一种数据结构和定义在其上的一组操作组成。抽象数据类型（ADT）：是指一个数学模型以及定义在该模型上的一组

7、操作。抽象数据类型可用（D，S，P）三元组表示，其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。D+S=数据结构，D+S+P=抽象数据类型。抽象数据类型的特性：数据抽象：强调本质特征及所能完成的功能和外部接口。数据封装：将实体的外部特性和内部实现细节分离，并且隐藏实现细节。1.4算法和算法分析算法（algorithm）—对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法着重于思想的描述,可能会省略很多细节,因此,算法需要进行适当修改才能变成程序在机器上实现.(1)有穷性：一个算法必须总是在执行有穷

8、步之后结束，且每一步都可在有穷时间内完成。(2)确定性：算法的每一条指令必须有确切的含义，理解时不会产生二义性,并且在任何条件下都只有一