计算机软件技术基础 教学课件 作者 牟艳 陈慧萍 第2章 数据结构概述.ppt

《计算机软件技术基础 教学课件 作者 牟艳 陈慧萍 第2章 数据结构概述.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章数据结构概述本章基本内容与要求基本内容基本概念、常用术语、抽象数据类型、算法的特征以及算法分析与评价要求掌握算法分析的时间和空间复杂度本节重点：基本概念、常用术语，抽象数据类型第一节数据、数据元素、数据类型、抽象数据类型数据是能输入到计算机中并被计算机程序处理的符号的总称。数据元素（DataElement）是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理，有时也称作元素、结点、顶点、记录等。数据对象（DataObject）是具有相同性质的数据元素的集合，是数据的一个子集。数据类型（DataType）是对在计算机

2、中表示的同一数据对象及在该数据对象上的一组操作的总称。抽象数据类型（AbstractDataType简记为ADT）是一个数据结构以及定义在该结构上一组操作的总称。数据及其概念第二节数据结构的基本概念一、什么是数据结构数据结构（DataStructure）是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构通常包含以下三个方面的内容：数据的逻辑结构、数据的存储结构、数据的运算及实现。1.数据的逻辑结构是指数据元素之间的逻辑关系：a集合，元素间为松散的关系。b线性结构,元素间为严格的一对一关系。c树形结构，元素间为严

3、格的一对多关系。d图状结构（或网状结构），元素间为多对多关系。2.数据的存储结构是指数据及数据元素之间的关系在计算机内存中的表示。数据结构的主要存储方式有顺序存储和链式存储两种，此外还有索引存储和散列存储等其它方式。顺序存储方式是在计算机内存储器中开辟一片地址连续的存储单元顺序存放数据中的各个元素。链式存储方式是把数据元素和反映元素间关系（后继和/或前趋）的地址一块存储在计算机内。索引存储方式和散列存储方式通常是为了检索的方便所采用的存储表示方法。3.数据的运算及实现程序中的数据运算是定义在数据的逻辑结构上的运算，但运算的实现

4、要在相应的存储结构上进行。常用的运算有检索、插入、删除、更新、排序等。二.算法及特征1.算法的基本概念数据的运算是通过算法实现的、解决某一特定问题的有限运算序列（解决问题的方法和步骤）。算法的非形式化定义一个算法，就是一个有穷规则的集合，其中的规则规定了一个解决某一特定类型问题的运算序列。2.算法的定义和特征算法的重要性质有穷性（Finiteness）一个算法在执行有穷步之后必须结束。确定性（Definiteness）算法的每一个步骤必须要有确切的定义。输入（Input）算法有零个或多个输入。输出（Output）算法有一个或多

5、个的输出。有效性（Effectiveness）算法中有待执行的运算和操作必须是相当基本的，换言之，它们都是能够精确地进行的。算法的形式化定义算法的形式化定义如下所述：算法是一个四元组，即（Q，I，Ω，F）。其中：Q是一个包含子集I和Ω的集合，它表示计算的状态。I表示计算的输入集合。Ω表示计算的输出集合。F表示计算的规则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q∈Q，有F(q)=q。3.算法实例【例1】：求1+2+3+…+100设变量X表示加数，Y表示被加数，用自然语言将算法描述如下：1）将1赋值给X；2）将2赋

6、值给Y；3）将X与Y相加，结果存放在X中；4.算法分析解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序的性能好坏。那么，在保证算法正确性的前提下，如何确定算法的优劣就是一个值得研究的课题。在算法的分析中，一般应考虑以下3个问题：1）算法的时间复杂度；2）算法的空间复杂度；3）算法是否便于阅读、修改和测试。4）将Y加1，结果存放在Y中；5）若Y小于或等于100转到步骤3，继续执行；否则，算法结束，结果为X。算法时间复杂度（Timecomplexity）是指算法中有关操作次数的多少，它用T(n)表示，T(n)中

7、的n表示问题规模的大小，如在累加求和中n表示待加数的个数，在矩阵相加问题中n表示矩阵的阶数，在图中n表示顶点数等。在算法的复杂度分析中，经常使用一个记号Ο如，该表达式表示，当n足够大时表达式左边约等于n2。设f(n)是一个关于正整数n的函数，若存在一个正整数n0和一个常数C，当时，均成立，则称f(n)为T(n)的同数量级的函数。于是，算法时间复杂度T(n)可表示为：常见的大Ο表示形式有常数级Ο(1)，对数级Ο(logn)，线性级Ο(n)，多项式级Ο(nc)，指数级Ο(cn)和阶乘级Ο(n!)等常见函数的增长算法空间复杂度（Sp

8、aceComplexity）是指算法在执行过程中所占存储空间的大小，它用S(n)表示。S为英文单词Space的第一个字母，与算法的时间复杂度相同，算法的空间复杂度S(n)也可表示为S(n)=Ο(g(n))。程序的一次运行是针对所求解的问题的某一特定实例而言的。程序运行所需的存