数据结构：第一章 绪论ppt课件.ppt

《数据结构：第一章 绪论ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法+数据结构=程序N.沃思(NiklausWirth)教授:不了解施加于数据上的算法就无法决定如何构造和组织数据,反之,算法的选择常常在很大程度上要依赖于作为基础的数据结构.7/27/202111.1什么是数据结构（定义）7/27/20212定义:数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。数据包含整型、实型、布尔型、图象、字符、声音等一切可以输入到计算机中的符号集合。数据（Data）7/27/20213数据元素（DataElement）定义：数据元素是组成数据的基本单位，是数据集合的个体，在计算机中通常作为一个整体进行考虑和处理。例如：.............

2、.....北京1983.11河北女赵虹玲101住址出生年月籍贯性别姓名学号数据元素数据项7/27/20214数据结构（DataStructure）定义：数据结构是指相互之间存在一种或多种特定关系的数据元素集合，是带有结构的数据元素的集合，它指的是数据元素之间的相互关系，即数据的组织形式。7/27/20215集合结构定义：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。集合例如：7/27/20216线性结构定义：结构中的数据元素之间存在着一对一的线性关系。例如：线性表7/27/20217树型结构定义：结构中的数据元素之间存在着一对多的层次关系。例如：树7/27/20218图状结

3、构或网状结构定义：结构中的数据元素之间存在着多对多的任意关系。例如：图7/27/20219逻辑结构定义：数据的逻辑结构是指数据元素之间逻辑关系描述。形式化描述：Data_Structure=（D,R）其中D是数据元素的有限集，R是D上关系的有限集。四类基本的结构集合结构、线性结构、树型结构、图状结构。7/27/202110综上所述，数据的逻辑结构可概括为：线性结构——线性表、栈、队、字符串数组、广义表逻辑结构非线性结构——树、图逻辑结构7/27/202111存储结构定义：存储结构（又称物理结构）是逻辑结构在计算机中存储映象，是逻辑结构在计算机中的实现，它包括数据元素的表示和关系的表示。形式化

4、描述：D要存入机器中，建立一从D的数据元素到存储空间M单元映象S，D→M，即对于每一个d，d∈D,都有唯一的z∈M使S（D）=Z,同时这个映象必须明显或隐含地体现关系R。7/27/202112逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身映象，是数据结构的实现；逻辑结构是数据结构的抽象。数据元素之间关系在计算机中的表示方法：顺序映象（顺序存储结构）非顺序映象（非顺序存储结构）存储结构7/27/202113数据结构的内容综上所述，数据结构的内容可归纳为三个部分，逻辑结构、存储结构和运算集合：按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机存贮器中，并在这些数据

5、上定义了一个运算的集合，就叫做数据结构。7/27/2021141.2数据抽象与抽象数据类型7/27/202115数据的抽象汇编语言中十进制表示的数据98.65、9.6E3等,它们是二进制数据的抽象;高级语言中，给出更高一级的数据抽象，如整型、实型、字符型等，还可以进一步定义更高级的数据抽象，如各种表、队、栈、树、图、窗口、管理器等复杂的抽象数据类型。7/27/202116抽象数据类型(AbstractDataType)定义：抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但

6、将运算的实现过程隐藏起来。7/27/202117ADT的表示与实现ADT的定义：ADT{数据对象:<数据对象的定义>结构关系:<结构关系的定义>基本操作:<基本操作的定义>}ADT基本操作的定义格式为：<操作名称>(参数表)操作前提:<操作前提描述>操作结果:<操作结果描述>7/27/2021181.3算法7/27/202119算法（Algorithm）定义定义：Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.算法是规则的有限集合，是为

7、解决特定问题而规定的一系列操作。7/27/202120算法的特性1.有限性：有限步骤之内正常结束，不能形成无穷循环2.确定性：算法中的每一个步骤必须有确定含义，无二义性得以实现。3.输入：有多个或0个输入4.输出：至少有一个或多个输出。5.可行性：原则上能精确进行，操作可通过已实现基本运算执行有限次而完成。7/27/202121算法设计的要求算法的正确性可读性健壮性高效率和低存储量例如要求n个数的最大值问题给