DS01-概论【荐】.ppt

第 1 章 概 论 ???? 什么是数据结构 ???? 为什么要学习数据结构 ???? 算法和算法分析 人们通常采用大O表示法来描述算法分析的结果。 f(n)是某个值非负的函数，这种说法意味着：当n充分大时，该算法的复杂度不大于f(n)的一个常数倍。 一般，求时间复杂度时，只考虑与程序规模有关的频度最大的语句，如循环语句的循环体，多重循环的内循环等。 学习数据结构要达到的目的 一个算法所耗费的时间是算法中所有语句执行时间之和，而每条语句的执行时间是该语句的执行次数（频度）与该语句执行一次所需时间（略，因机器不同而不同）的乘积。 求时间复杂度方法： * —— C语言版 清华大学出版社 2009年9月 1.1.1 数据和数据元素 数据（data）是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储和加工处理。 1.1 什么是数据结构 数据——在计算机科学中指所有能输入到计算机中并被计算机程序处理的符号的总称。如图像、数、字符、声音、视频等都可以通过编码而由计算机处理，因此它们也属于数据的范畴。 是数据的基本单位。通常在计算机程序中作为一个整体进行考虑和处理。数据元素也称为元素、结点或记录。一个数据元素可以由若干个数据项（也称字段、域）组成，数据项是数据不可分割的最小单位。 数据元素（data element）： 数据对象（data object）： 是性质相同的数据元素的集合，它是数据的一个子集。例如，所有的“数”构成了数据集合，而正整数集合N={1，2，3，…}是“数”的数据对象；所有的字符是数据，大写字母集合C={‘A’，‘B’，…，‘Z’}是该数据的数据对象。 1.1.2 数据对象和数据类型 要注意的是：计算机中的正整数数据对象集合N1应该是上述集合N的一个子集，N1={1，2，…，maxint}，其中maxint是依赖于所使用的计算机和语言的最大整数。 数据类型（data type）是计算机程序中的数据对象以及定义在这个数据对象集合上的一组操作的总称。可以看作是数据结构的实现。 例如，C语言中的整数类型是区间[-maxint，maxint]上的整数，在这个集合上可以进行加、减、乘、整除、求余等操作。 数据结构（data structure） 是指数据对象（集合）以及该数据对象集合中的数据元素之间的相互关系的集合（即数据元素的组织形式）。 一组数据元素和一组运算（关系）两个集合组成的集合 1.1.3 数据结构 根据数据元素之间关系的不同，数据结构分为两大类： 线性结构 非线性结构 ① 集合：数据元素之间除了“属于同一个集合”的关系以外，别无其他关系。 ② 线性结构：数据元素之间存在一对一的关系。 ③ 树型结构：数据元素之间存在一对多的关系。 ④ 图状结构（或称网状结构）：数据元素之间存在多对多的关系。 ⑴ 数据元素之间的逻辑关系，也称为数据的逻辑结构。是数据元素之间抽象化的相互关系。是用户所看到的数据结构，是面向问题的，它不考虑数据的存储。数据的逻辑结构通常有下列4类： ⑶ 数据元素之间的运算（关系）：对数据元素施加的操作，有时也直接称为数据的运算或操作。 ⑵数据的物理结构： 又称存储结构。是数据的逻辑结构在计算机存储器内的表示（又称映象）。它属于具体实现的视图，是面向计算机的。 例1.1 学生成绩表（表1.1）是一个数据结构。 表1.1 学生成绩表(每行是一个数据元素) 78 75 88 70 张吉祥┆ ┆ ┆ ┆ ┆ ┆ 89 93 85 90 王澄娟75 66 78 82 林春英74 78 68 75 马丽丽85 85 90 80 陈小洁平均成绩 普通物理 高等数学 计算机导论 姓名 学号 数据结构可以理解为：按某种逻辑关系组织起来的一批数据，应用计算机语言，按一定的存储表示方式把它们存储在计算机的存储器中，并在这些数据上定义了一个运算的集合。 数据结构主要研究什么？ （或者说数据结构的研究对象是什么？） 数据结构的内容可归纳为三个部分： 按某种逻辑关系组织起来的一批数据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做数据结构。 逻辑结构 存储结构 运算集合 上述4种基本的存储方法，既可以单独使用，也可以组合起来对数据结构进行存储映象。同一种逻辑结构，若采用不同的存储方法，则可以得到不同的存储结构。