【文档说明】计算机软件技术基础(邮电)112讲解课件.ppt，共(41)页，190.668 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-76544.html

以下为本文档部分文字说明：

计算机软件技术基础(邮电)112讲解第一单元第二单元第三单元第四单元第五单元第六单元第七单元第八单元第一章数据结构2024/12/2•§1.1数据结构的基本概念§1.1.1数据结构的研究内容及其重要性用计算机处理问题的步骤首先需要把客观对象抽象为某种形式的数据，然后设计对这

些数据进行处理的算法，由计算机执行设计好的算法，用某种计算机语言（例如：C语言）描述交计算机处理。数据结构的重要性程序=数据结构＋算法2024/12/2数学代数系统编码理论数据类型算子关系数据表示数据运算数据结构数据存取机器组织存储装置硬件（计算机系统设计）文件系统数据组织信息检索软件（计

算机程序设计）数据结构的学科地位2024/12/2数据结构的主要内容1968年美国的唐纳德·克努特（DonaldE.Kunth）教授出版了其名著《计算机程序设计艺术》第一卷《基本算法》，首次系统地阐述了数据

结构的主要内容，即：数据的逻辑结构数据的存储结构数据的操作2024/12/2§1.1.2数据结构的基本概念和术语数据(data)数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中、能被计算机程序识别和处理的符号的集合。数

据非数值性数据（字符、指令等不表示数值的代码)数值性数据（整数、实数、复数)数据的分类一、术语2024/12/2数据元素(dataelement)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数

据项（dataitem）数据项是具有独立含义的最小标识单位。数据对象(dataobject)数据的子集。具有相同性质的数据成员（数据元素）的集合。整数数据对象N={0,1,2,…}，学生数据对象

学号姓名外语数学计算机021001王强879096021002李一龙699189021003张映月877971021004何一端848868……………2024/12/2数据类型（datatype）是一个值的集合以及在这

些值上定义的一组操作的总称。数据结构（datastructure)数据元素相互之间的关系称为结构。四类基本结构集合结构中的数据元素之间除了“同属于一个集合”的关系外，别无其它关系。如下图所示：集合2024/12/2线性结构结构中的数据元素之间存在着一对一的

关系（结点之间的连线表示关系）。例如：学生名单。如图所示：树形结构结构中的数据元素之间存在着一对多的关系。只能与上一层的一个结点相关，可与下一层的多个结点相关。例如：博弈。树：2024/12/2•

图状结构或网状结构结构中的数据元素之间存在着多对多的关系。图中任一结点都可与多个其它结点关联，即图的结点之间的关系是任意的。树是图的一种特例。例如：交通规划；邮递员问题。图2024/12/2二、基本概念数据结构(datastructure

)数据结构是计算机存储、组织数据的方式。数据相互之间存在着一种或多种特定关系。学号姓名语文数学物理021001王强879096021002李一龙699189021003张映月877971021004何一

端848868……………2024/12/2•数据结构的分类逻辑结构逻辑结构就是数据元素之间的逻辑关系。线性结构数据逻辑结构中的一类,它的特征是若结构为非空集,则该结构有且只有一个开始结点和一个终端结点,并且所有结点都最多只

有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。非线性结构非线性结构的逻辑特征是该结构中一个数据元素可能有多个直接前趋和直接后继,非线性结构中最普遍的就是图的结构。2024/12/2•数据存储结构(

物理结构)反映数据元素在计算机中的存储方法就是数据的物理结构。有时也称为存储结构。它是逻辑结构在存储器里的实现。数据存储结构的四种基本存储方法❖顺序存储（SequentialStorageStructure）该方法把逻辑上相邻的数据元素存

储在物理位置上相邻的存储单元里，数据元素间的逻辑关系由存储单元的邻接关系来体现。数组内存2024/12/2•❖链式存储(LinkedStorageStructure)该方法不要求逻辑上相邻的数据元素在物理位置上

亦相邻，数据元素间的逻辑关系由附加的指针字段表示。由此得到的存储表示称为链式存储结构。可以将物理上不连续的数据元素在逻辑上相邻。例：链表。2024/12/2•❖索引存储（IndexStructure）该方法通常在储存数据元素信息的同时，还建立附加的索引表。索引表由若

干索引项组成。例如：图书检索（按书名、作者、出版社、分类号索引）。若每个数据元素在索引表中都有一个索引项,则该索引表称之为稠密索引（DenseIndex）。若一组数据元素在索引表中只对应一个索引项,则该索引表称为稀疏索引（SpareIndex）。⧫索引项的一般形式

(1)关键字是能唯一标识一个数据元素的那些数据项。(2)稠密索引中索引项的地址指示数据元素所在的存储位置；(3)稀疏索引中索引项的地址指示一组结点的起始存储位置。关键字：地址2024/12/2•❖散列存储方

法（Structure）根据数据元素的关键字直接计算出该结点的存储地址。（哈希函数（算法））关键字数据哈希函数地址２主存储器地址１2024/12/2•对数据的操作（运算）数据结构除逻辑结构和物理结构外，第三个内容就是数据的操作，例如表的使用和维护（排序、查找、增加、修改、删除等）。在数据结构中，

数据的操作涉及比加减乘除算术运算更广义的运算，这些运算常常涉及算法问题。高效率地存储数据和管理数据需要分析和选择合适的算法。2024/12/2•算法算法的定义（Ａlgorithm）一个有穷的指令集，这些指令为解决某一特定任务规定了一个运算序列。

算法的特性输入:有0个或多个输入输出:有一个或多个输出(处理结果)确定性:每步定义都是确切、无歧义的有穷性:算法应在执行有穷步后结束有效性:每一条运算应足够基本2024/12/2•算法算法的分析(ＡlgorithmＡnalysis

)算法分析(algorithmanalysis)是指对算法的执行时间和所需内存空间的估算。同一问题的求解往往可以使用不同的算法,通过算法分析,可以比较两个算法的效率高低。2024/12/2•算法的时间复杂度执行一个算法所花费的时间代价。当要解决的问题的规模以某种单位由1增至n时，对应算法所耗费的

时间也以某种单位由f(1)增至f(n)。此时称该算法的时间复杂度为f(n)。问题的规模例：顺序查找算法的关键操作是a[i]的值与给定值做比较。顺序查找成功的平均比较次数为（设：有ｎ个数据）：2111+==ninni2/)1(}1)2()1({1)(+=++−+−+=nnnnnnf

2024/12/2•时间代价（最坏、最好和平均情况）❖最好情况下的时间代价❖在平均情况下的时间代价❖最坏情况下的时间代价主要采用大Ｏ表示法来描述。大O表示法O(n)f(n)T(n)==2024/1

2/2一般提法当且仅当存在正整数c和n0,使得T(n)≤cf(n)对所有的n≥n0成立,则称该算法的渐进时间复杂度为T(n)=O(f(n))这时也称该算法的时间代价的增长率为f(n)，意味着当ｎ充分大时，该算法的复杂度不大于f(n)的一个常数倍。2024/12/2•基本思想关

注复杂性的数量级，而忽略数量级的系数，这样在分析算法的复杂度时，可以忽略个别语句的执行时间，重点分析算法的主要代价。假设：f(n)=2n3+2n2+2n+1，当n充分大时：T(n)=O(n3)2024/12/2•算法的空间复杂度执行一个算法所需占用的空间代价。当要解决的问

题的规模以某种单位由1增至n时，对应算法所需占用的空间也以某种单位由g(1)增至g(n)。此时称该算法的空间复杂度为g(n)。设S(n)是算法的渐进空间复杂度，在最坏情况下它可以表示为实例特性n的某个函数f(n)的数量级，记为：S(n)=O(f(n))2024/12/2是为解决问题所需要的辅助

存储空间。只有完成同一功能的几个算法之间才具有可比性可以使用大O表示法来标记这些空间复杂度,用以比较各算法的优劣。这样在分析算法的空间复杂度时，可以忽略零星变量的存储空间2024/12/2常见的时间复杂度常数阶O(1)对数阶O(log2n)线性阶O(n)线性对数阶O(nl

og2n)平方阶O(n2)立方阶O(n3)k次方阶O(nk)指数阶O(2n)2024/12/2•§1.1.3数据结构、数据类型和抽象数据类型数据结构数据结构是数据存在的形式。◼逻辑上的数据结构◼逻辑上的数据结

构反映数据元素之间的逻辑关系。◼物理上的数据结构◼物理上的数据结构反映数据元素在计算机内的存储安排。2024/12/2•数据类型概念数据以数据结构分类，具有相同数据结构的数据属同一类，数据类型表示某数据在数据分类中的归属，是数据的一种属性。定义一组性质相同的值的集合,以及定义于这

个值集合上的一组操作的总称。2024/12/2•C++语言中的数据类型双精度型double基本数据类型整型int字符型单字符型char宽字符型w_char实型单精度型float逻辑型bool数组type[]指针type*空类型void结构st

ruct联合union枚举enum类class数据类型非基本数据类型2024/12/2•charintfloatdoublevoid字符型整型浮点型双精度型无类型数据类型在高级程序设计语言中已实现了的

，或非高级语言直接支持的数据结构。变量的数据类型在程序设计语言中，一个变量的数据类型不仅规定了这个变量的取值范围，而且定义了这个变量可用的操作。数据结构与数据类型基本数据类型对应于简单的数据结构数据结构反映数据内部的构成方式

，它常常用一个结构图来描述2024/12/2•非基本数据类型对应于复杂的数据结构。数据结构有线性与非线性之分在非线性数据结构中又有层次与网状之分。由于数据类型是按照数据结构划分的，因此，一类数据结构对应着一种数据类型。数据类型有线性与非线性之分数据类型按照该类型中的数据所呈现的结构也有线

性与非线性之分，层次与网状之分。一个数据变量，在高级语言中的类型说明必须是该变量所具有的数据结构所对应的数据类型。2024/12/2•数组结构的特点数据元素的个数固定，它们之间的逻辑关系由数据元素的序号

(或叫数组的下标)来体现。这些数据元素按照序号的先后顺序一个挨一个地排列起来。每一个数据元素具有相同的结构(可以是简单结构，也可以是复杂结构)，因而属于同一个数据类型(相应地是简单数据类型或构造数据类型)。这种同一的数据类型称为基类型。所有的数据元素被依序安排在一片连续

的存储单元中。2024/12/2•记录结构的特点与数组结构一样，成分数据的个数固定。但成分数据之间没有自然序，它们处于平等地位。每一个成分数据被称为一个域并赋予域名。不同的域有不同的域名。不同的域允许有不同的结构，因而允许属于不同的数据类型。数组结构一样，它们可以随机访问，

但访问的途径靠的是域名。在高级语言中记录结构对应的数据类型是记录类型。记录结构的数据的变量必须说明为记录类型。2024/12/2•抽象数据类型（AbstractDataType，ADT）抽象数据类型的概念是带有一些操作的数据元素

的集合，它是一种描述用户和数据之间接口的抽象模型，ADT的主要功能是简单而明确地描述数据结构的操作。此处的“抽象”意味着我们应该从与实现方法无关的角度去研究数据结构。抽象数据类型为用户提供了一种定义数据类型的手段，其关键的两要素为数据的结构以及在该结

构上相应的操作的集合。抽象数据类型的目的引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的应用隔开，使它们相互独立。2024/12/2•抽象数据类型查找登录删除修改符号表2024/1

2/2•小结为什么要学习数据结构?它研究了计算机需要处理的数据对象和对象之间的关系。它刻画了应用中涉及到的数据的逻辑组织。它描述了数据在计算机中如何存储、传送、转换。2024/12/2主要讨论哪几种数据结构？数据结构的类型数据的逻辑结构❖线性结构❖非线

性结构2024/12/2ABCDEFABDEGCABCDE线性结构非线性结构非线性结构2024/12/2•数据的物理结构❖顺序结构❖链表结构❖散列结构❖索引结构在该数据结构上的操作作业：p78-84(一、1,2,4,5,6,

7二、1)2024/12/2注意2024/12/2•感谢聆听