《数据结构域算法设计-第一章 数据结构绪论 课件》由会员分享，可在线阅读，更多相关《数据结构域算法设计-第一章 数据结构绪论 课件（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第一章 绪 论,本章主要介绍下列内容什么是数据结构基本概念和术语算法和算法分析,1.1 什么是数据结构,程序设计:为计算机处理问题编制一组指令集的过程 算法:处理问题的策略 数据结构:问题的数学模型 计算机解决的问题分为,Niklaus Wirth：Algorithm + Data Structures = Programs,数值计算问题 非数值计算问题,算法+数据结构=程序,1.1什么是数据结构,例1 学籍档案管理,假设一个学籍档案管理系统应包含如下表所示的学生信息。 (线性表),1.1什么是数据结构,例2输出n个对象的全排列,输出n个对象的全排列可以使用下图所示的形式描述。（树）
2、,1.1什么是数据结构,例 3铺设煤气管道问题,怎样铺设管道最省钱（图）,3,概括地说：数据结构是一门讨论“描述现实世界实体的数学模型(非数值计算)及其上的操作在计算机中如何表示和实现”的学科。,1.1什么是数据结构,概念及术语 数据： 计算机程序所处理的符号的总称。 数据元素： 数据的基本单位，它可由若干数据项组成。 数据对象： 是性质相同的数据元素的集合，是数据的子集。 数据结构： 是相互之间存在一种或多种特定关系的数据元素的集合。,数据的逻辑结构： 数据元素之间的逻辑关系，分： 集合数据元素间除“同属于一个集合”外，无其它关系线性结构一个对一个，如线性表、栈、队列树形结构一个对多个，如树
3、图状结构多个对多个，如图或网,概念及术语,数据的存储结构数据的逻辑结构在计算机存储设备中的映射，分：顺序存储结构、链式存储结构。,顺序存储： 以相对的存储位置表示逻辑关系链式存储 以以附加指针表示后继关系,a2 a1,概念及术语,数据类型(Data Type ):一个值的集合和定义在此集合上操作的总称 抽象数据类型（Abstract Data Type）:是指一个数学模型以及定义在此数学模型上的一组操作。,概念及术语,ADT 有两个重要特征,数据抽象用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装将实体的外部特性和其内
4、部实现细节分离，并且对外部用户隐藏其内部实现细节。,抽象数据类型的描述方法,ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： 其中基本操作的定义格式为:基本操作名（参数表）初始条件：初始条件描述操作结果：操作结果描述,2算法和算法分析,算法概念,对特定问题求解步骤的一种描述，是指令的有限序列，每条指令表示一个或多个操作。算法应具备的特性：,（2） 确定性：指令具有确切的含义，相同的输入有相同的输出。,（1） 有穷性：对合法的输入值在执行有穷步之后结束。,（3） 可行性：所有操作可经已实现的基本运算执行有限次来实现,（4） 输入：0个或多个,（5） 输出：一个或多个,（2）可读性：便于
5、阅读和交流,（3）健壮性 ：能够对输入的非法数据作出反应和处理,（4）效率与低存储量需求：效率指算法的执行时间；存储量需 求指算法执行过程中所需要的最大存储空间。,算法设计的要求,（1）正确性 ：算法应满足具体问题的需求。 a. 程序不含语法错误 b. 对于几组输入可得满足要求的结果c. 对于精心选择的几组典型、苛刻、带有刁难性的输入数据可得满足要求的结果 d.对一切合法的输入数据都能得出产生要求的结果,算法效率的度量 算法的时间效率主要由两个因素决定： l所需处理问题的数据量大小，数据量大，所花费的时间就多； l在解决问题的过程中，基本操作的执行次数时间复杂度：算法中基本操作重复执行的次数是
6、问题规模n的某个函数， T(n)=O(f(n)好的算法应该能够在数据量n增长的同时，函数T(n)的增长速度比较缓慢。,例1：下列算法为两个n阶方阵的乘积 (1) for (i=1; i n; +i) (2) for (j=1; j n; +j) (3) cIj=0 ; (4) for (k=1; k n; +k) (5) cij+=aik*bkj ,(2) n(n+1)；,(1) n+1；,(4) n2(n+1) ；,(3) n2 ；,时间复杂度：T(n)=O(n3),(5) n3 ；,总时间耗费为：2n3 +3n2+2n+1,x+; O(1)for (i=1; i=n; i+)x+; O(n
7、)for (i=1; in; i+)for (j=1; jn; j+)x+; O(n2),按数量级递增排列，常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n2)、立方阶O(n3)、k次方阶O(nk)、指数阶O(2n)。不同数量级时间复杂度的性状见下图,常见函数的增长率,空间效率的分析 空间复杂度：S(n)=O(f(n) ，辅助空间的度量 辅助空间就是除算法代码本身和输入输出数据所占据的空间外，算法临时开辟的存储空间单元。在有些算法中，占据辅助空间的数量与所处理的数据量有关，而有些却无关。后一种是较理想的情况。在设计算法时，应该
8、注意空间效率。,算法描述工具类C P101. 预定义常量及类型 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1 Status 是函数的类型，其值是函数结果状态代码typedef int Status;,2. 数据结构的表示（存储结构）用类型定义(typedef)描述。数据元素被约定为ElemType 类型，用户需要根据具体情况，自行定义该数据类型。 3. 算法描述为以下的函数形式：函数类型 函数名（函数参数表）语句序列； 函数中使用的局部变量可以不做变量说明，对重点语句段落添加注解。增添C+语言的引用调用的参数传递方式，形参表中以&打头的参数即为引用参数,
