数据结构(第二版) 郑泳 方风波 第一章 概论新.pptVIP

第一章 概论 知识教学目标 数据结构的基本概念 数据的逻辑结构、存储结构 算法分析 能力培养目标 线性表的概念、逻辑结构、存储结构 数据的顺序存储方法和链式存储方法 算法的定义和特性 时间复杂度的概念和分析 1.1 基本概念和术语 数据（data）是一切能被计算机识别、存储和加工处理的对象，是对客观事务的符号表示，是信息的载体，也就是说数据是对有效地输入到计算机中并能被计算机程序处理的符号的总称。随着计算机技术的发展，数据这一观念的含义越来越广泛，它既可以是像整数、实数、复数这样的数值数据，又可以是像字符、文字、表格、图形、图像、声音这样的非数值数据。 数据元素（data element）是数据的基本单位，相当于“记录”，在计算机程序中要作为一个整体来考虑和处理。也就是说，数据元素被认为是运算的基本单位，并且具有完整确定的实际意义。在不同条件下，数据元素又可称为元素、顶点、记录等。例如上面职工花名册中的每个人的信息就是一个数据元素。 数据对象（data object）是由具有相同性质的数据元素组成的集合，是数据的一个子集，也称为数据元素类（Data Element Class）。在某个具体问题中，数据元素都具有相同的性质（元素值不一定相等），属于同一数据对象，数据元素是数据对象的一个实例。例如，整数数据对象是集合 N={0, ± 1, ± 2, … }。 数据结构（data structure）是指数据之间相互的关系，即数据的组织形式。它一般包括以下三个方面的内容： 1）数据元素之间的逻辑关系，即数据的逻辑结构。 2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构 ，也就是数据元素的物理结构。 3）对数据进行的运算，即算法。 1.1.1 逻辑结构 职工信息管理 学校组织结构 教学计划编排问题 1.1.2 存储结构 顺序存储 非顺序存储 索引存储 哈希存储 1.2 算法的描述与分析 1.2.1 算法的描述 算法（algorithm）是对特定问题求解的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有下列五个重要特性： 有穷性 、确定性 、可行性 、输入 、输出 算法的评价 要设计一个好的算法，除了满足以上五个条件外通常还有考虑以下几个方面： 1）正确性 2）可读性 3）健壮性 4）高效、低存储性 1.2.2 算法分析 要设计一个“好”的算法，首先要保证选用的算法是正确的，除此以外，还应考虑如下几个方面： 1）执行该算法所耗费的时间。 2）执行该算法所耗费的存储空间，其中主要考虑辅助存储空间。 3）该算法应便于理解，易于编码、调试等。 1.2.3时间复杂度 【例1.4】 两个N×N矩阵A和B的乘法，结果为矩阵C 。 (1) for(i=0 ; iN ;i++) (2) for(j=0 ;jN ;j++) (3) {c[i][j]=0 ; (4) for(k=0 ;kN ;k++) (5) c[i][j]+=a[i][k]*b[k][j] ; } 【例1.5】计算下列交换i和j内容程序段的时间复杂度。 temp=i; i=j; j=temp; 【例1.6】 求f1函数的时间复杂度。 void f1(int v[ ],int n) { int i,j,k,x; for(i=0;in-1;i++) { k=i; for(j=i+1;jn;j++) if(v[k]v[j]) k=j; x=v[i]; v[i]=v[k]; v[k]=x; } } 1.2.4. 空间复杂度 一个算法的空间复杂性是指程序运行从开始到结束所需的内存存储量。 类似于算法的时间复杂性，空间复杂性记为：S(n)=O(f(n))。其中n为问题的规模或大小。 1.3 本章小结 本章主要介绍了贯穿全书的基本概念和基本思想。数据是一切能够由计算机接受和处理的对象。数据结构主要描述数据中各种元素间的相互关系，往往是给出了有关这些元素的一组运算；其包括逻辑结构和存储结构。数据的逻辑结构指数据元素之间的逻辑关系，存储结构指数据元素在计算机存储器中的表示和安排。 算法指的是有穷的规则序列，这些规则决定了解决某一问题的一系列运算。而评价一个算法主要是研究算法的时间复杂度和空间复杂度。 * * * C2 操作系统 C9 C4 编译原理 C8 C9， C2 数据库原理 C7 C3 接口技术 C6 C2， C3， C4 计算机图形学 C5 C1 C语言设计 C4 C1 汇编语言 C3 C1，C4 数据结构 C2 无 计算机文化基础 C1 先修课程 课程名称 课程编号