计算机软件技术基础 第2章 数据结构概述课件.ppt

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

1、第二章数据结构概述沈捷自动化与电气工程学院2.1数据结构基本概念数据（data）数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合。数据元素（dataelement）数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位数据对象（dataobject）具有相同性质的数据元素的集合，是数据的一个子集。数据类型（datatype）对在计算机中表示的同一数据对象及在该数据对象上的一组操作的总称。数据结构（datastruct

2、ure）是指同一数据对象中各数据元素间存在的关系。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存储结构和对数据所施加的运算。这三个方面的关系为：数据的逻辑结构独立于计算机，是数据本身所固有的存储结构是逻辑结构在计算机存储器中的映像，必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存储结构。数据的逻辑结构是指数据元素之间的逻辑关系集合，元素间为松散的关系。线性结构,元素间为严格的一对一关系。通迅录、成绩单、花名册树形结构，元素间为严格的一对多关系。电子字典、家

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

4、的存储结构上进行。常用的运算有检索、插入、删除、更新、排序等算法及特征1.算法的基本概念解决某一特定问题的有限运算序列（解决问题的方法和步骤）。数据的运算是通过算法实现的2.算法的形式化定义和特征算法是一个四元组，即（Q，I，Ω，F）。其中：Q是一个包含子集I和Ω的集合，它表示计算的状态。I表示计算的输入集合。Ω表示计算的输出集合。F表示计算的规则，它是由Q至它自身的函数，且具有自反性，即对任何一个元素q∈Q，有F(q)=q。3.算法实例例：求1+2+3+…+100设变量X表示加数，Y表示被加数，用自然语言将算法描

5、述如下：1）将1赋值给X；2）将2赋值给Y；3）将X与Y相加，结果存放在X中；算法的特征有穷性（Finiteness）一个算法在执行有穷步之后必须结束。确定性（Definiteness）算法的每条指令必须要有确切的定义。指令执行结果确定，对相同输入必然产生相同输出。有效性（Effectiveness）算法指令可由程序语言在有限步内实现。输入（Input）算法有零个或多个输入。输出（Output）算法有一个或多个的输出。4）将Y加1，结果存放在Y中；5）若Y小于或等于100转到步骤3，继续执行；否则，算法结束，结果为

6、X。4.算法分析解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序的性能好坏。那么，在保证算法正确性的前提下，如何确定算法的优劣就是一个值得研究的课题。在算法的分析中，一般应考虑以下3个问题：1）算法的时间复杂度；2）算法的空间复杂度；3）算法是否便于阅读、修改和测试。算法时间复杂度（Timecomplexity）是指算法中有关操作次数的多少，它用T(n)表示，T(n)中的n表示问题规模的大小，如在累加求和中n表示待加数的个数，在矩阵相加问题中n表示矩阵的阶数，在图中n表示顶点数等。在算法的复杂度

7、分析中，经常使用一个记号Ο(解析数论，1892，Order，数量级)，如，该式表明，当n足够大时表达式左边约等于n2。设f(n)是一个关于正整数n的函数，频度为F(n)，算法时间复杂度T(n)可表示为：常见的大Ο表示形式有常数级Ο(1)，对数级Ο(lgn)，线性级Ο(n)，多项式级Ο(nc)，指数级Ο(cn)和阶乘级Ο(n!)等常见函数的增长一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间就多。时间复杂度一般用语句执行次数的数量级来衡量。例1for(i=1;i<=n;i++)fo

8、r(j=1;j<=n;j++)d[i][j]=data[i][j]+1;算法分析O(n2)例2for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)x=x+1;算法空间复杂度（SpaceComplexity）是指算法在执行过程中辅助单元所占存储空间的大小，它用S(n)表示。与算法的时间复杂度相同，算法的空间