1、计算机软件技术基础,教 师：曾晓东 电 话：13679007201 E_mail: ,第2章 数据结构概述,一、什么是数据结构 二、有关数据结构的基本概念和术语 三、算法 四、算法描述语言和算法分析,计算机软件技术基础,数据结构概述,第2章 数据结构概述,一、什么是数据结构程序=算法+数据结构 例： 表达式解释 6+5*4=？ 字符串匹配 串“ABCAC”出现在另一个串“ABCABCACAC”的第几个位置上 排序 一个序列，如何最快地对其进行排序 压缩编码 AAAABBBCDDE? 图的最短路径 地理研究中的交通网络,计算机软件技术基础,数据结构概述,第2章 数据结构概述,一、什么是数据结构
2、1、数值型与非数值型数据 （1）学生表格,计算机软件技术基础,数据结构概述,一、什么是数据结构,(2)选课表,(3)UNIX的文件系统,计算机软件技术基础,数据结构概述,一、什么是数据结构,2、数据结构简单来说，就是相互之间存在一种或多种特定关系的数据元素的集合。如线性关系、层次关系、网状关系等。,计算机软件技术基础,数据结构概述,第2章 数据结构概述,二、有关数据结构的基本概念和术语 1、数据(data)：计算机程序所处理的一切数值性的和非数值性的信息。 2、数据元素(data element)：是数据集合中的一个个体，是数据的基本单位。如数据集合N=1，2，3，4，5中整数1至5均为数据元
3、素。 数据元素不一定是单个的数字或字符，也可能是若干个数据项的组合，如学生信息。 学生（学号，姓名，性别，成绩） 数据项(data item)是数据不可再分的最小单位。 数据元素有时也称结点、节点或记录。,计算机软件技术基础,数据结构概述,二、有关数据结构的基本概念和术语,3、数据对象(data object)：是具有相同性质的数据元素的集合。如大写字母字符的数据对象是集合：C= A，B，.，Z 。 4、数据结构(data structure)：研究数据元素之间抽象化的相互关系和这种相互关系在计算机系统中的存储方式，并对每种数据结构定义相关的运算算法，确保经过运算后仍然是原来的数据结构类型。
4、5、数据的逻辑结构(logical structure):表示数据元素之间抽象化的相互关系，又可简称为数据结构。它研究数据元素及其关系的数学特性。集合、线性、树型、网状 6、数据的物理结构(physical structure):表示数据的逻辑结构在计算机系统中的存储方式，又可简称为存储结构。它是逻辑结构在计算机中的映象，也就是具体实现。顺序存储、链式存储、索引存储、散列存储,计算机软件技术基础,数据结构概述,第2章 数据结构概述,三、算法 1、算法：为解决某个计算任务而安排的有限操作过程的描述。 2、算法的特性 有穷性 确定性 数据输出 数据输入 能行性,计算机软件技术基础,数据结构概述,三
5、、算法,3、好的算法的特性 正确性 可读性 健壮性 高效率和低存储空间要求 简洁性,计算机软件技术基础,数据结构概述,第2章 数据结构概述,四、算法描述语言和算法分析 1.算法描述语言 本门课程基本采用标准C描述算法。 注释部分用/或/*.*/表示。 有些地方为方便起见，可能省略变量定义等有关内容。 请大家复习C语言的相关内容，特别是指针和结构两部分的内容,计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,2、算法的复杂性分析 一个可执行的算法不一定是一个好算法，算法的分析是一个复杂的问题，通常用计算机执行时在时间和空间两方面的消耗多少作为评价该算法优劣的标准。 这两个标准分别称为
6、时间复杂度和空间复杂度。一般时间复杂度考虑的较多。 度量一个程序的执行时间通常有两种方法： 事后统计和事前分析估算 这里我们介绍第二种方法。,计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,2.1 时间复杂度 频度：指一条语句重复执行的次数，记作：F(n) 时间复杂度：T(n)=O(F(n) 下面举例说明如何求时间复杂度？,计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,1. for (i=0; in; i+) 2. for (j=0; jn; j+) 3. bij=0; 4. for (k=0; kn; k+) 5. bij=bij+aik*akj; 6. 我们以
7、执行次数最多的语句（第5句）进行计算：语句频度为：F(n)=n3时间复杂度：T(n)=O(F(n)=O(n3),计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,思考下列程序段的时间复杂度1)、x=x+1;,2)、for (j=0; jn; j+) x=x+1;,3)、for (j=0; jn; j+) for (k=0; kn; k+) x=x+1;,4)、for (j=2; j=n; j+) for (k=2; k=j-1; k+) x=x+1;,T(n)=O(1),T(n)=O(n),T(n)=O(n2),T(n)=O(n2),计算方法：对于外层循环中的j，从2到n循环，计算
8、出j每取一个值时，内层循环执行的次数0、1、2、.、n-2，然后累加起来，得到一个n的多项式(n-1)(n-2)/2，取出次数最高的项即可。,计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,常见的时间复杂度1）O(1)：常量型2）O(n)、O(n2)、.、O(nk)：多项式型3）O(log2n)、O(2log2n)：对数型4）O(2n)、O(en)：指数型,计算机软件技术基础,数据结构概述,四、算法描述语言和算法分析,2、空间复杂度 空间复杂度是指在算法中所需的辅助空间单元而不包括问题的原始数据占用的空间（因为这些单元与算法无关），记作：S(n) 时间与空间是一对矛盾。要节约空间往往就要消耗较多时间，反之亦然，而目前由于计算机硬件的发展，一般都有足够的内存空间，因此在分析中着重考虑时间的因素。,计算机软件技术基础,数据结构概述,第2章 数据结构概述,五、小结 1、理解基本概念：数据、数据元素、数据对象、数据结构、数据类型、逻辑结构和物理结构、算法 2、会分析一般算法的语句频度和时间复杂度,计算机软件技术基础,数据结构概述,
