第1章 绪论,1.1 数据结构的基本概念和术语 1.2 算法描述和算法分析,普通高等教育“十一五”国家级规划教材,主要内容,返回目录,1.1 数据结构的基本概念和术语,1. 数据（Data） 是指能输入到计算机中并能被计算机处理的一切对象。 2. 数据元素（Data Element） 是一个数据整体中相对独立的单位。 3. 数据对象（Data Object） 是具有相同性质的数据元素的集合,是数据的一个子集。 4.数据结构（Data Structure） 是指相互之间存在着一种或多种特定关系的数据元素的集合。,数据元素之间的相互关系包括三个方面：数据的逻辑结构、存储结构和运算方法。 逻辑结构 数据的逻辑结构可以看作是从具体问题抽象出来的数学模型，它反映的是数据元素之间的相互关系。,线性结构,集合结构,树型结构,图形结构,用二元组表示： Data_Structure=(D,S),Data_Structure=(D,S),其中Data_Structure表示某一种逻辑结构，D是该结构中数据元素的有限集合，S是D上关系的有限集合。 例 根据下表所给数据，用二元组表示法和图形表示法构造线性结构、树形结构和图形结构。,1) 线性结构的二元组表示 Line_List=(D,S) 其中,不难看出，S是按职工年龄从大到小排列的关系。,D=1,2,3,4,5,6,7,8,9,S=， ，,2) 树形结构的二元组表示 Tree=(D,S) 其中,不难看出，S是人员之间领导与被领导的关系。,D=1,2,3,4,5,6,7,8,9,S=， ，,3) 图形结构的二元组表示 Graph=(D,S) 其中 D=1,2,3,4,5,6,7 S=，,简化: S=(1,2)，(1,4)，(2,3)，(2,6)，(2,7)， (3,7)，(4,6)，(5,7), 物理结构（存储结构） 存储结构表示的是数据元素及其关系在计算机的存储器中的物理位置。,1)顺序存储 把逻辑上相邻的元素存储在物理位置相邻的存储单元中。 2)链式存储 对逻辑上相邻的元素并不要求其物理位置一定相邻，元素间的逻辑关系可以通过指针的链接来表示。 3)索引存储 在存储数据元素本身之外，再建立一张指示逻辑数据与物理数据之间一一对应关系的表，即索引表。 4)散列存储 由数据元素的值来确定存储地址，由于该地址是元素值的函数，因此，该函数也称散列函数。, 运算方法 是对已建立的逻辑结构和存储结构的具体操作。,1) 加工型运算 其操作改变了原结构中数据元素的个数或数据元素的内容。 基本运算 ：插入、删除、更新、排序 2) 引用型运算 其操作不改变原结构中数据元素的个数或数据元素的内容，只是从结构中提取某些信息作为运算的数据。 基本运算 ：查找、读取,5. 数据类型(Data Type) 是一个值的集合和定义在这个值集合上的一组操作的总称。,数据类型中定义了两个集合：值的集合和操作集合 数据类型可分为两类：一类是原子类型，另一类则是结构类型。原子类型的值是不可分解的。而结构类型的值是由若干成分按某种结构组成的。,6. 抽象数据类型（Abstruct Data Type，简称ADT）,由一组数据结构和在该组数据结构上的一组操作所组成。 抽象数据类型和数据类型实质上是一个概念 。 抽象数据类型可以用以下三元组表示： （D,S,P） 其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。,7. 算法（Algorithm）,是对特定问题求解步骤的一种描述，是指令的有限序列。 有穷性 一个算法必须在执行有限步之后结束，即必须在一定时间内完成。 确定性 算法中的每一条指令必须有确切的定义，无二义性。在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入仅有唯一的一条输出路径。 可行性 一个算法是可行的，即算法中描述的各种操作都可以通过已知的一组基本运算来实现。 输入 一个算法可以具有零个或多个输入，这些输入取自特定的数据对象集合。 输出 一个算法必须有一个或多个输出，这些输出是算法对输入进行运算的结果。,作业,1.数据的非线性结构有那几种,各自的特点是什么? 2.做教材习题中的以下题目。 单项选择题：(1),(3) 填空题：(1),(2),(3) 应用题：(1),1.2 算法描述和算法分析,1.2.1 算法描述 1.2.2 算法分析 作业,1.自然语言 用自然语言来描述算法的优点是简单直观且便于人们对算法的阅读。 2. 数学公式 用数学公式表达算法特别适应于数值计算的问题。 3. 流程图 可以使用程序流程图等算法描述工具。,1.2.1 算法描述,程序流程图,N-S结构图, 程序设计语言和伪代码,直接使用某种程序设计语言来描述算法 。 伪码语言介于高级程序设计语言和自然语言之间，它忽略高级程序设计语言中一些严格的语法规则与描述细节。因此它比程序设计语言更容易描述和被人理解，而比自然语言更接近程序设计语言。,5. C语言做为算法描述语言, C数据类型概述 C语言数据类型如表所示。, C语言使用的基本语句, C语言使用的基本语句(续), 常用动态存储函数,指针是实现动态存储结构的重要手段,动态存储函数,1.2.2 算法分析,1.算法设计要求, 正确性 算法的执行结果应当满足预先规定的 功能和性能要求。一个不能保证正确的算法，根本不 能称为算法。, 可读性 一个算法应当思路清晰、层次分明、 简单明了、易读易懂。, 健壮性 当输入不合法数据时，算法能适当作 出反映或进行处理，不会产生莫名其妙的运行结果或 死机。, 高效率 存储空间 在算法执行过程中所占 空间越小越好。时间效率 算法执行过程中执行的 时间短的算法其效率较高。,2. 算法性能分析与度量, 时间复杂度 一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。 若解决一个问题的规模为n那么算法的时间复杂度就是n的一个函数，通常记为T(n)。,用求累加和的算法介绍时间复杂度的计算。,float sum(int n) int i=1; float s=0,x; while (i=n) n+1次 scanf(“%f“, 1次 ,时间复杂度T(n)=4n+2。,T(n)=O(f(n),其中f(n)是问题规模为n的某个函数。 大写字母O为英文Order（即数量级）一词的第一个字母。 这样表示的意思是指T(n)不超过一个正的常数同f(n)的乘积。 T(n)(n) 或记为(n) 而T(n)2n2+3n+5，可以记为： T(n)(n2)或记为(n2)。,算法的运行时间与T(n)的关系,(1)(log2n)(n)(nlog2n)(n2)(n3)(2n) (n!),通常用(1)表示常数计算时间。使用大记号表示的 算法的时间复杂度，也称为算法的渐进时间复杂度。, 空间复杂度,空间复杂度（Space complexity）是指程序运行从开始到结束所需的存储量，记作： S(n)=O(f(n) 其中n为问题的规模。 程序运行所需的存储空间包括以下两部分： 固定部分 可变部分 算法的时间复杂度和空间复杂度是相互矛盾的，难以兼得 。,作业,1.在算法设计要求中那一点是最主要的? 2.做教材习题中的以下题目。 单项选择题：(2),(4),(5) 填空题：(4),(5) 应用题：(2),