《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－1》由会员分享，可在线阅读，更多相关《软件技术基础 教学课件 ppt 作者 张选芳 傅茂洺 王欣 计算机软件技术基础(邮电)1－1（36页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础,课件,第一章 数据结构,第二章 操作系统,第三章 软件工程,第四章 数据库,制作者：张选芳 Email: 电话:5182508,第一章 数据结构,第一单元,第二单元,第三单元,第四单元,第五单元,第六单元,第七单元,第八单元,数据结构的基本概念,第一单元,第一章 数据结构,1.1数据结构的基本概念,1.1.1数据结构的研究内容及其重要性 用计算机处理问题的步骤 首先需要把客观对象抽象为某种形式的数据， 然后设计对这些数据进行处理的算法，由计算机执行设计好的算法， 最后获得问题的处理结果。 数据结构的重要性 程序=数据结构算法,数据结构的主要内容,1968年美国的唐纳德克努特
2、（Donald E. Kunth）教授出版了其名著计算机程序设计艺术第一卷基本算法，首次系统地阐述了数据结构的主要内容，即 数据的逻辑结构、 存储结构 以及对数据进行操作的各种算法。,1.1.2 数据结构中的基本概念和术语,一、术语 数据(data)： 数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。 数据的分类,数据,非数值性数据 （字符、字符串、文字、图形、语音等),数值性数据（整数、实数、复数、 双精度、工程和科学计算), 数据对象(data object) 数据的子集。具有相同性质的数据成员（数据元素）的集合。 整数数据对象
3、N = 0, 1, 2, 学生数据对象 英文字母数据对象 LETTER A ， B,Z,数据元素(data element)：,是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据项（data item） 数据项是具有独立含义的最小标识单位。,数据类型（data type）：,是一个值的集合以及在这些值上定义的一组操作的总称。 结构(structure)： 数据元素相互之间的关系称为结构。 四类基本结构 集合： 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系。如下图所示：,集合,线性结构： 结构中的数据元素之间存在着一个对一个的关系。如图所示：,树形结构：
4、结构中的数据元素之间存在着一个对多个的关系。如图所示：,树：,图状结构或网状结构： 结构中的数据元素之间存在着多个对多个的关系。如下图所示：,图：,二、基本概念 数据结构(data structure)： 相互之间存在着一种或多种特定关系的数据元素的集合。, 数据结构的分类 逻辑结构(数据结构) 逻辑结构就是数据元素之间的逻辑关系。 线性结构 数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个 开始结点和一个终端结点,并且所有结点都最多只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。 非线性结构 非线性结构的逻辑特征是该结构中一个数据元素可能有多个直接前趋和直接
5、后继,非线性结构中最普遍的就是图的结构。,数据存储结构：(物理结构) 反映数据元素在计算机中的存储方法就是数据的物理结构。有时也称为存储结构。它是逻辑结构在存储器里的实现。 数据存储结构的四种基本存储方法 顺序存储方法： （Sequential Storage Structure） 该方法把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，数据元素间的逻辑关系由存储单元的邻接关系来体现。, 链接存储方法:(Linked Storage Structure) 该方法不要求逻辑上相邻的数据元素在物理位置上亦相邻，数据元素间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构。 索
6、引存储方法： （ Index Structure） 该方法通常在储存数据元素信息的同时，还建立附加的索引表。索引表由若干索引项组成。 稠密索引（Dense Index） 若每个数据元素在索引表中都有一个索引项,则该索引表称之为稠密索引。,稀疏索引（ Spare Index） 若一组数据元素在索引表中只对应一个索引项,则该索引表称为稀疏索引。 索引项的一般形式 (关键字、地址),(1)关键字 关键字是能唯一标识一个数据元素的那些数据项。 (2) 稠密索引中索引项的地址指示数据元素所在的存储位置； (3) 稀疏索引中索引项的地址指示一组结点的起始存储位置。,散列存储方法（Structure） 根据
7、数据元素的关键字直接计算出该结点的存储地址。 对数据的操作（运算） 它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 算法 算法的定义 一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。,算法的特性： 输入:有0个或多个输入 输出:有一个或多个输出(处理结果) 确定性:每步定义都是确切、无歧义的 有穷性: 算法应在执行有穷步后结束 有效性: 每一条运算应足够基本 算法的分析(algorithm analysis) 算法分析(algorithm analysis)是指对算法的执行时间和所需内存空间的估算。同一问题的求解往往可以使用不同的算法,通过算法分析,
8、可以比较两个算法的效率高低。, 算法的时间复杂度 执行一个算法所花费的时间代价。 当要解决的问题的规模以某种单位由1增至n时，对应算法所耗费的时间也以某种单位由f(1)增至f(n)。此时称该算法的时间复杂度为f(n)。 问题的规模 例：顺序查找算法的关键操作是ai 的值与给定值做比较。 顺序查找成功的平均比较次数为：, 关键操作 顺序查找成功的平均比较次数为：, 函数f (n),时间代价（最坏、最好和平均情况） 最好情况下的时间代价。 在平均情况下的时间代价。 最坏情况下的时间代价，主要采用大 表示法来描述。,大O表示法, 一般提法 当且仅当存在正整数c和n0,使得T(n) cf (n)对所有
9、的nn0成立,则称该算法的渐进时间复杂度为T( n ) = O(f( n )。这时也称该算法的时间代价的增长率为f(n)。 基本思想 关注复杂性的数量级，而忽略数量级的系数，这样在分析算法的复杂度时，可以忽略个别语句的执行时间重点分析算法的主要代价。,假设f(n) = 2n3 +2n2 + 2n + 1， 当n充分大时： T( n ) = O(n3 ),算法的空间复杂度,执行一个算法所需占用的空间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所需占用的空间也以某种单位由g(1)增至g(n)。此时称该算法的空间复杂度为g(n)。 设S (n) 是算法的渐进空间复杂度，在最坏情况下它可
10、以表示为实例特性n的某个函数f (n)的数量级，记为 ： S (n) = O(f (n), 是为解决问题所需要的辅助存储空间。 只有完成同一功能的几个算法之间才具有可比性 可以使用大O表示法来标记这些空间,用以比较各算法的优劣。 这样在分析算法的空间复杂度时，可以忽略零星变量的存储空间,常见的时间复杂度 常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。 1.1.3 数据结构、数据类型和抽象数据类型 数据结构 数据结构是数据存在的形式。,逻辑上的数据结构 逻辑上的数据结构反映数据元素之
11、间的逻辑关系。 物理上的数据结构 物理上的数据结构反映数据元素在计算机内的存储安排。 数据类型 同一类数据的全体称为一个数据类型。 定义 一组性质相同的值的集合, 以及定义于 这个值集合上的一组操作的总称。, C+语言中的数据类型,双精度型double,基本数据类型,整型int,字符型,单字符型char,宽字符型w_char,实型,单精度型float,逻辑型bool,数组type ,指针type *,空类型 void,结构 struct,联合 union,枚举enum,类 class,数据 类型,非基本数据类型,char int float double void 字符型 整型 浮点型 双精度
12、型 无值 数据类型 在高级程序设计语言中已实现了的，或非高级语言直接支持的数据结构。 变量的数据类型 在程序设计语言中，一个变量的数据类型不仅规定了这个变量的取值范围，而且定义了这个变量可用的操作。 数据结构与数据类型 基本数据类型对应于简单的数据结构; 数据结构反映数据内部的构成方式，它常常用一个结构图来描述,非基本数据类型对应于复杂的数据结构。 数据结构有线性与非线性之分。 在非线性数据结构中又有层次与网状之分。 由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。 数据类型有线性与非线性之分 数据类型按照该类型中的数据所呈现的结构也有线性与非线性之分，层次与网状之分。
13、一个数据变量，在高级语言中的类型说明必须是该变量所具有的数据结构所对应的数据类型。,数组结构的特点 数据元素的个数固定，它们之间的逻辑关系由数据元素的序号(或叫数组的下标)来体现。这些数据元素按照序号的先后顺序一个挨一个地排列起来。 每一个数据元素具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。 所有的数据元素被依序安排在一片连续的存储单元中。,记录结构的特点 与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。
14、 不同的域允许有不同的结构，因而允许属于不同的数据类型。 数组结构一样，它们可以随机访问，但访问的途径靠的是域名。 在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。,抽象数据类型（Abstract Data Type，ADT） 抽象数据类型的概念 是带有一些操作的数据元素的集合，它是一种描述用户和数据之间接口的抽象模型，ADT的主要功能是简单而明确地描述数据结构的操作。此处的“抽象”意味着我们应该从与实现方法无关的角度去研究数据结构。抽象数据类型为用户提供了一种定义数据类型的手段，其关键的两要素为数据的结构以及在该结构上相应的操作的集合。 抽象数据类型的目
15、的 引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的应用隔开，使它们相互独立。,抽象数据类型,查找 登录 删除 修改,符 号 表,小结 为什么要学习数据结构?,它研究了计算机需要处理的数据对象和对象之间的关系。 它刻画了应用中涉及到的数据的逻辑组织。 它描述了数据在计算机中如何存储、传送、转换。,主要讨论哪几种数据结构？,数据结构的类型 数据的逻辑结构 线性结构 非线性结构,A,B,C,D,E,F,A,B,D,E,G,C,A,B,C,D,E,线性结构,数据的物理结构 顺序结构 链表结构 散列结构 索引结构 在该数据结构上的操作 作业：p78-84(一、1,2,4,5,6,7 二、1),注意,
