数据结构(c语言版)第1章绪论解析.ppt

5. 数据类型(Data Type) 数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合，即该类型的取值范围，以及该类型中可允许使用的一组运算。 6. 抽象数据类型（Abstract Data Type） 数据类型 数据对象集 数据集合相关联的操作集 抽象：描述数据类型的方法不依赖于具体实现 与存放数据的机器无关 与数据存储的物理结构无关 与实现操作的算法和编程语言均无关 ADT只描述数据对象集和相关操作集“是什么”，并不涉及 “如何做到”的问题。 例4： 线性表的抽象数据类型定义  ADT List{ 数据元素： D={ai| ai∈ElemSet, i=1, 2, …，n, n≥0 ， ElemSet为某一数据对象} 数据关系：Ｓ＝｛ai, ai+1 | ai, ai+1∈D，i=1, 2, …, n-1} 基本操作： InitList（L）: 初始化线性表。 Length(L): 求线性表的表长; Get(L, i): 取线性表的第i个元素；  Insert(L, i, b): 在线性表的第i个位置插入元素b；  Delete(L, i): 删除线性表的第i个元素。 } ADT List 1.3 算法和算法分析 1. 算法（Algorithm） 算法是为求解一个问题需要遵循的、被清楚地指定的简单指令的集合。 2. 算法的特性  (1) 有穷性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。 (2) 确定性：组成算法的每条指令是清晰的，无歧义的。 (3)可行性：原则上能精确进行，操作可通过已实现的基本运算执行有限次而完成。 (4)输入：有多个或0个输入。  (5)输出： 至少有一个或多个输出。 在算法的五大特性中，最基本的是有穷性、确定性和可行性。 3. 算法设计的要求 １） 算法的正确性 (1) 所设计的程序没有语法错误；  (2) 所设计的程序对于几组输入数据能够得出满足要求的结果； (3) 所设计的程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。  (4) 程序对于一切合法的输入数据都能产生满足要求的结果。 例如：求n个正整数的最大值问题，给出示意算法如下：  max = 0;  for（i = 1; i = n; i++）  { scanf(″%d″, x);  if (x max) max = x;  } 2） 可读性 3） 健壮性 4） 高效率和低存储 程序： 程序与算法不同。程序是算法用某种程序设计语言的具体实现。程序可以不满足算法的“有穷性”这个性质。 例如：操作系统是一个在无限循环中执行的程序，因而不是一个算法。然而可把操作系统的各种任务看成是一些单独的问题，每一个问题由操作系统中的一个子程序通过特定的算法来实现，该子程序得到输入结果后便终止。 对算法作性能评价 空间复杂度S(n)——根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。 时间复杂度T(n)——根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。 有关数量关系的计算 1） 关于算法执行时间 一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。  2） 语句频度 语句频度是指该语句在一个算法中重复执行的次数。 例：两个n×n阶矩阵相乘。 3） 算法的渐进时间复杂度 原操作是指从算法中选取一种对所研究问题是基本运算的操作，用随着问题规模增加的函数来表征，以此作为时间量度。 而对于算法分析，我们关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级（Order of Magnitude）。在这里，我们用“O”来表示数量级，这样我们可以给出算法的时间复杂度概念。所谓算法的渐进时间复杂